portal-tunnel의 MOLS 라우팅: 수학적 직교성과 실전 시스템 공학의 만남

분산 네트워크에서 여러 릴레이 서버에 트래픽을 분배할 때 풀어야 할 숙제는 두 가지입니다.

평소에 모든 서버가 일을 골고루 나누어 하여 특정 서버만 지치지 않게 하는 것
서버 하나가 갑자기 꺼졌을 때 그곳을 쓰던 트래픽이 다른 멀쩡한 서버들까지 연쇄적으로 무너뜨리지 않게 막는 것

보통은 랑데부 해싱 같은 분산 해싱 방식을 떠올리지만, portal-tunnel은 스도쿠 판의 원리인 직교 라틴 방진, 즉 MOLS를 가져와 후보 경로를 설계했습니다.

하지만 MOLS라는 수학적 도구는 이론일 뿐, 실제 프로덕션 환경에서는 서버 수가 수시로 바뀌고 지연 시간도 요동칩니다. portal-tunnel 팀이 주방 비유처럼 명쾌한 MOLS의 원리를 살리기 위해 그 위에 어떤 시스템 공학 계층을 쌓아 올렸는지, 그리고 랑데부 해싱과는 시스템적으로 어떤 다른 트레이드오프를 선택했는지 살펴봅니다.

1. MOLS는 무엇이고 어떻게 움직이는가

MOLS는 쉽게 말해 가로세로 숫자가 겹치지 않는 스도쿠 판 두 장을 겹쳐 놓은 구조입니다.

주방에 7명의 요리사가 있고, 0번부터 6번까지 번호가 붙은 7개의 도구가 있다고 상상해 보겠습니다. 요리사는 클라이언트이고, 도구는 릴레이 서버입니다.

첫 번째 판: 평상시 도구 고르기

요리사는 각자의 고유 번호를 바탕으로 주방 바닥 격자판의 한 자리에 섭니다. 그리고 첫 번째 스도쿠 규칙에 따라 자기가 쓸 1순위 도구를 고릅니다. 스도쿠 규칙 덕분에 7명의 요리사는 겹치지 않고 0번부터 6번 도구를 하나씩 골고루 쥐게 됩니다. 한 도구에 줄을 서는 일 없이 평화롭게 일이 시작됩니다.

두 번째 판: 도구가 고장 났을 때

진짜 핵심은 쓰던 도구가 고장 났을 때 나타납니다. 만약 "칼이 고장 나면 다 같이 2번 냄비를 쓰자"는 식으로 단순하게 정해두면, 요리사들이 한꺼번에 냄비로 몰려들어 재료가 넘쳐나고 주방이 마비됩니다.

MOLS는 이를 막기 위해 첫 번째 판과 완전히 독립적인 두 번째 스도쿠 판을 둡니다. 두 판이 직교한다는 것은 첫 번째 판에서 같은 도구를 골랐던 사람들이라도, 두 번째 판에서는 무조건 각자 다른 도구를 고르게 된다는 약속입니다. 따라서 1번 칼을 쓰던 요리사들의 2순위 도구는 냄비, 프라이팬, 찜기 등으로 제각기 흩어집니다. 서버 하나가 죽어도 그 여파가 주방 전체로 얇게 분산되는 것입니다.

2. 교과서 공식이 실제 서버에서 망가지는 이유

이론은 완벽해 보이지만, 서버가 실시간으로 꺼지고 켜지는 실제 환경에서는 세 가지 큰 장벽에 부딪힙니다.

1) 대체 경로의 쏠림

교과서의 단순한 선형 수식을 코드로 그대로 옮긴 초기 순정 구현에서는, 기대와 달리 1순위 서버가 꺼졌을 때 2순위 트래픽의 100%가 특정 대체 서버 한 곳으로 우르르 몰려가는 병목이 발생했습니다.

2) 서버 하나 빠졌을 때의 재연결

MOLS는 전체 서버 대수를 기준으로 자리를 나눕니다. 그런데 7대 중 1대가 꺼져서 6대가 되면 격자판 기준 자체가 통째로 바뀝니다. 그 바람에 고장 난 서버와 아무 상관없이 다른 정상 서버에 잘 붙어있던 클라이언트의 80% 이상이 엉뚱하게 연결을 끊고 새 서버를 찾아 헤매는 혼란이 일어났습니다.

3) 짝수 대수에서의 한계

스도쿠 두 장이 서로 겹치지 않으려면 숫자 간의 궁합이 맞아야 합니다. 특히 6대 환경에서는 수학적으로 두 번째 직교 판 자체가 아예 존재하지 않고, 다른 짝수 대수도 실시간으로 직교 쌍을 찾아내려면 계산 시간이 너무 오래 걸립니다. 그렇다고 간단한 선형 수식으로 때우면 특정 서버 하나에 트래픽 50%가 쏠려버렸습니다.

3. MOLS 위에 쌓아 올린 portal-tunnel의 시스템 공학

portal-tunnel은 MOLS 수식 하나로 모든 문제를 해결하려 하지 않았습니다. MOLS를 후보 서버들을 기하학적으로 흩뿌리는 뼈대로 삼고, 그 위에 실제 시스템의 상태를 반영하고 연결을 조율하는 파이프라인을 얹었습니다.

[후보 노드 발견 및 해시 정렬] 
           ↓
[짝수/홀수 판별 및 이중 목표 점수 매기기] (MOLS 기하학 계층)
           ↓
[실시간 텔레메트리 기반 P2C 부하 조절]   (동적 부하 계층)
           ↓
[기존 정상 세션을 보호하는 조건부 연결 유지] (안정성 계층)

1단계: 짝수와 홀수를 가리지 않는 안전한 점수 계산

서버가 6대처럼 짝수일 때는 무리하게 직교 판을 찾느라 시간을 쓰지 않습니다. 대신 순서가 겹치지 않고 한 바퀴 도는 단일 스도쿠 모드로 전환하여 50% 쏠림을 막고 17% 수준의 균등한 분산을 지킵니다. 그리고 1순위와 2순위 목표점을 각각 계산한 뒤 거리에 따라 점수를 매겨, 1순위 서버가 꺼져도 특정 대체 서버로 쏠리지 않고 남은 서버들로 고르게 분산되도록 점수 체계를 잡았습니다.

2단계: 실시간 주방 상태를 보는 지배인의 개입

수학 공식으로 점수를 매겼더라도 지금 당장 냄비 앞에 줄이 길다면 조정이 필요합니다. 1등 후보 서버의 부하가 2등보다 30% 이상 높으면 둘의 순서를 맞바꿔 짐을 덜어줍니다. 주방 전체의 지연 시간이 500ms를 넘어가면 핑이 빠른 서버를 위로 올립니다.

3단계: 멀쩡한 연결을 지키고 병목을 털어내는 방어막

서버 대수가 바뀌어 1~2단계 계산 결과가 달라지더라도, 내가 지금 쓰고 있는 서버가 건강하다면 새 계산 결과를 무시하고 기존 연결을 유지한다는 룰을 최우선으로 둡니다. 덕분에 서버 하나가 꺼져도 다른 정상 서버에 붙어 있던 클라이언트들은 불필요한 재연결 없이 기존 통신을 이어갑니다. 다만 특정 서버에 부하가 0.5를 넘게 쌓이거나 2초 이상 응답이 느려지면 미련 없이 연결을 끊고 새 서버를 찾게 하여 한 서버에만 짐이 굳어지는 것을 막습니다.

4. 서버가 늘고 줄어들 때 왜 MOLS가 꼭 필요한가

"어차피 짝수에서 안전 모드로 돌리고 기존 연결을 지켜줄 거라면, 왜 굳이 홀수에서 MOLS를 켜는가? 그냥 단순한 방식 하나로 통일하면 안 되는가?"라는 의문이 들 수 있습니다.

분산 환경은 서버가 5대, 6대, 7대, 8대로 끊임없이 늘고 줄어듭니다. 이 동적 흐름 속에서 MOLS의 진짜 가치가 드러납니다.

단순 순환 방식만 계속 쓸 때의 위험:
단순한 순환 방식만 쓰면서 기존 연결을 계속 지켜주면, 1번이 꺼지면 2번, 2번이 꺼지면 3번을 바라보는 거대한 도넛 모양 순환 고리가 네트워크에 영구적으로 굳어집니다. 이 상태에서는 서버 하나가 쓰러지면 옆 서버로 부하가 도미노처럼 쏟아집니다.
홀수 MOLS가 주는 환기 효과:
서버 대수가 홀수 구간을 지나갈 때마다, MOLS의 두 번째 스도쿠 규칙이 새롭게 들어오는 연결들의 예비 경로를 사방으로 흩뿌려줍니다. 기존의 건강한 연결은 방어막이 지켜주는 동안, 새로 생기는 백업 경로들이 원형 고리를 깨부수고 입체적인 그물망 구조를 형성하도록 돕는 것이 portal-tunnel의 설계상 의도이자 효과입니다.

결국 짝수 안전 모드가 발을 헛디디지 않게 받쳐주는 디딤돌이라면, 홀수 MOLS는 네트워크 연결망이 한 방향으로 찌그러지지 않도록 주기적으로 균형을 맞춰주는 핵심 엔진 역할을 합니다.

5. 랑데부 해싱과의 시스템적 트레이드오프 비교

랑데부 해싱은 분산 시스템에서 검증된 훌륭한 기법입니다. 클라이언트와 서버의 식별자를 조합해 해시 점수를 매기고 점수순으로 서버를 선택합니다.

MOLS가 랑데부 해싱보다 본질적으로 우월한 것은 아닙니다. 두 기법은 문제를 해결하는 철학과 지향하는 트레이드오프가 완전히 다릅니다.

1) 해시 점수 분포의 통계적 변동 vs 기하학적 균등 배치

랑데부 해싱: 랑데부 해싱 역시 완벽히 결정론적입니다. 동일한 키와 서버 목록이면 언제나 동일한 결과를 냅니다. 다만 독립적인 해시 점수 분포의 특성상 통계적 부하 편차가 존재하며, 특정 벤치마크 환경에서는 특정 서버에 부하가 조금 더 실리는 편차가 관측되기도 합니다.
MOLS: 순수한 조합수학의 직교 격자 구조를 활용하므로, 정적인 노드 풀 안에서는 이론적으로 모든 서버에 매우 균등한 초기 부하를 배치합니다.

2) 알고리즘 자체의 안정성 vs 시스템 계층이 만드는 안정성

랑데부 해싱: 알고리즘 자체가 수학적 단조성을 지닙니다. 서버 하나가 빠지면 그 서버를 쓰던 클라이언트만 자신의 2순위 서버로 이동하고, 나머지 클라이언트는 재연결 없이 기존 서버를 유지함을 알고리즘 수준에서 자연스럽게 보장받습니다.
portal-tunnel MOLS: 순수 MOLS 수식 자체는 서버 대수 변동에 취약합니다. portal-tunnel은 이를 MOLS 수식으로 푼 것이 아니라, 그 위에 얹은 활성 연결 유지 계층을 통해 건강한 기존 연결을 그대로 유지하도록 설계한 것입니다. 즉, MOLS의 약점을 시스템 공학적인 안전장치로 상쇄한 구조입니다.

3) 연산 특성과 확장성

랑데부 해싱: 서버 수에 비례하여 해시 함수를 호출하고 정렬해야 하므로 연산 비용이 상대적으로 큽니다. 대신 전역 상태 합의 없이 각자 독립적으로 경로를 계산하는 비동기 분산 환경에 매우 강합니다.
MOLS: 단순 사칙연산 위주로 구성되어 마이크로벤치마크 환경에서 매우 빠른 연산 속도를 보여줍니다. 다만 모든 참여자가 동일하게 정렬된 서버 목록 뷰를 공유해야 하는 구조적 전제가 필요합니다.

6. 실험 조건 및 벤치마크 한계 명시

본 문서에 인용된 벤치마크 수치(portal-tunnel/docs/routing_strategy_comparison.md)는 특정 합성 네트워크 테스트 조건에서 측정된 상대적 비교 지표이며, 일반적인 분산 네트워크 전체를 대변하는 보편적 성능 수치가 아닙니다.

2차 분산 및 재연결 측정 조건: 700개의 합성 클라이언트와 7대의 릴레이 서버(N=7) 환경에서 가장 바쁜 1대 서버를 고의로 중단시켰을 때의 거동을 측정한 결과입니다.
- 순정 MOLS (초기 구현): 해당 구현에서는 1순위 장애 시 특정 대체 노드로 트래픽의 100%가 몰리는 현상이 관측되었고, 서버 이탈( $N=7 \to 6$ ) 시 기존 연결 클라이언트의 82.4%(492/597)가 재배치되었습니다.
- portal-tunnel MOLS: 이중 목표 점수제를 통해 대체 노드 최대 점유율을 28.8% 수준으로 분산시켰으며, 활성 연결 유지 계층을 통해 해당 실험 조건에서 무관한 정상 클라이언트의 불필요한 재연결을 0.0%(0/590)로 방어했습니다.
- 랑데부 해싱: 알고리즘 단조성에 의해 해당 조건에서 0.0%(0/590)의 재연결을 자연스럽게 보장했습니다.
연산 속도 측정 조건 (291ns vs 1,106ns): 10개 후보 서버( $K=10$ )를 대상으로 단일 경로 선택 함수를 반복 실행한 단일 스레드 CPU 마이크로벤치마크 결과입니다. 터널 수립 시점의 0.8µs 차이는 일반적인 유선 지연 시간(수십 ms)에 비하면 미미하지만, 대규모 동시 연결 폭주 시 릴레이 노드의 CPU 점유율을 낮추는 의미를 갖습니다.

7. 한눈에 보는 요약

비교 항목	순정 MOLS (초기 구현)	랑데부 해싱	portal-tunnel의 MOLS 체계
기본 철학	조합수학적 직교 행렬 계산	독립적인 해시 가중치 기반 정렬	MOLS 기하학 뼈대 + 시스템 공학 제어
연산 특성 (특정 벤치마크, $K=10$ )	291 ns (단순 사칙연산)	1,106 ns (해시 반복 호출 및 정렬)	291 ns (가벼운 연산 속도 유지)
초기 부하 분산	수학적 균등 분산	결정론적이나 통계적 부하 편차 존재	초기 기하학적 균등 분산 유지
1순위 장애 시 2차 분산	특정 서버 1곳으로 100% 몰림	통계적 다중 분산	거리 점수제로 여러 서버 분산 (측정치 최대 28.8%)
서버 변동 시 재연결 ( $N=7 \to 6$ 실험치)	82.4% 재배치 발생	0.0% (알고리즘 단조성으로 자연 보장)	0.0% (활성 연결 유지 계층을 통해 달성)
서버 목록 일치성 요구	엄격한 정렬 뷰 일치 필요	뷰가 달라도 부분 순위 일관성 보장	로컬 해시 정렬 및 연결 유지로 보완
실시간 상태 반영	불가 (정적 계산)	기본형은 정적 (가중치 변형 기법 필요)	P2C 부하 스왑 및 지연 시간 역전 파이프라인

portal-tunnel의 MOLS 라우팅: 주방 비유로 이해하기