"Amazon's Dynamo"를 읽고 나서 - 2. Consistent Hashing / Virtual Nodes

분산 시스템에서의 ““데이터를 어떻게 나누고 배치할 것인가” 라는 문제에 대한 해법은 Consistent Hashing과 Virtual Nodes의 조합이었다. 아마존이 실제 운영하면서 이 전략을 어떻게 진화시켰는지 살펴본다.

1. Consistent Hashing

일반적인 분산 방식에서는 BLOB의 해시값 β를 구한 뒤 서버 개수 n으로 모듈러 연산을 수행하여 ζ = β % n으로 서버를 결정한다. 그러나 이 경우 서버 수가 변하면 모든 BLOB을 재배치해야 하므로 비용이 크다.

안정 해싱(Consistent Hashing)은 서버 추가나 제거가 빈번한 분산 시스템에서 재해싱 부담을 줄이기 위해 설계된 기법이다. BLOB과 서버를 모두 동일한 해시 함수로 원형 해시 공간(예: 0~360도)에 매핑한다. 각 BLOB은 시계 방향으로 가장 가까운 서버에 할당된다. 이 구조에서는 서버가 추가되거나 제거되더라도 전체 BLOB의 대부분은 이동하지 않고, 평균적으로 1/n 비율의 BLOB만 재할당된다.

이 방식의 가장 큰 장점은 노드가 추가되거나 제거될 때 최소한의 데이터만 이동하면 된다는 것. 전통적인 해싱 방식이 노드 수 변경 시 거의 모든 데이터를 재배치해야 하는 것과 대조적이다.

구현

BLOB 삽입 시 해시값 $\zeta$를 계산한 뒤 이 값을 초과하는 첫 번째 서버 ID를 찾아 그 서버에 저장한다. 만약 $\zeta$가 모든 서버 ID보다 크면 가장 작은 서버 ID를 가진 서버가 선택된다. 삭제의 경우, 삽입과 동일한 과정으로 후속 서버를 찾은 뒤 해당 서버에서 BLOB을 제거한다.

새 서버를 추가할 경우, 식별자(IP 주소, UUID 등)를 해싱하여 값 $\theta$를 계산한다. $\theta = h_s(x) % 360$으로 원형 해시 공간에 매핑한다. 이후 $\theta$보다 작은 해시값을 가진 모든 BLOB을 $\theta$의 후속 서버(successor server)로부터 가져와 새 서버에 할당한다. 만약 $\theta$가 모든 서버 ID 중 가장 큰 값이라면, 가장 작은 서버 ID를 가진 서버로부터 해당 BLOB들을 가져와 $\theta$ 서버에 할당한다.

서버를 제거할 경우, 제거할 서버의 해시값 $\theta$를 기준으로 후속 서버를 찾는다. 해당 서버에 존재하는 모든 BLOB은 후속 서버로 이동시킨다. 만약 후속 서버가 없다면, 가장 작은 서버 ID를 가진 서버로 BLOB들을 이동한다.

BLOB과 서버 식별자를 위해 각각 $h_b(x)$와 $h_s(x)$ 해시 함수를 사용한다. BLOB의 해시값과 서버의 해시값을 원형 해시 공간에 매핑하여 분산을 관리한다. 실제 구현에서는 서버 ID를 동적으로 관리하고 후속 서버(successor)나 최소값을 빠르게 찾기 위해 이진 탐색 트리(BST)를 사용한다. 후속 서버를 찾거나 최소값을 탐색할 때는 트리 순회(tree traversal) 방식을 활용한다. BST를 활용하면 서버 추가, 삭제, BLOB 할당 시 효율적인 탐색이 가능하며, 연산 복잡도는 일반적으로 $O(\log N)$ 수준으로 유지된다.

2. Virtual Nodes

하지만 안정 해싱에는 두 가지 심각한 문제가 있다. 노드들이 링 위에 무작위로 배치되면 각 노드가 담당하는 범위의 크기가 크게 달라져 불균등한 데이터 분포를 이루게 된다. 또한 성능이 다른 서버들을 효과적으로 활용할 수 없다.

“Instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring.”

Dynamo는 이 문제를 Virtual Nodes(가상 노드)로 해결했다. 하나의 물리 노드가 링 위의 여러 위치를 담당하도록 매핑하여 균등성을 높이는 방식이다. 또한 가상 노드의 개수는 곧 서버의 가중치로 해석되며, 성능이 좋은 서버에는 많은 가상 노드를 배치하고 성능이 낮은 서버에는 적은 수를 배치하여 이기종 하드웨어 환경에서도 부하 분산이 가능하다. 고성능 서버는 더 많은 가상 노드를 할당받아 더 많은 부하 처리할 수 있게 된다.

Strategy 1: 노드당 T개의 랜덤 토큰 (초기 프로덕션)

Dynamo의 초기 전략은 단순했다. 각 노드는 해시 공간에서 $T$개의 토큰을 무작위로 선택하여 자신이 담당할 위치를 정했다. 예를 들어 $T=100$이라면, 하나의 노드는 링 위의 100개 무작위 지점을 담당하게 된다. 이렇게 생성된 토큰들은 정렬되어 자연스럽게 각 노드가 담당하는 범위를 형성했다.

“When a new node joins the system, it needs to ‘steal’ its key ranges from other nodes. However, the nodes handing the key ranges off to the new node have to scan their local persistence store to retrieve the appropriate set of data items.”

하지만 이 접근 방식은 운영에서 큰 문제를 일으켰다. 새로운 노드가 클러스터에 합류하면 기존 노드들은 자신이 담당하던 키 범위 중 일부를 새 노드에 전달해야 했다. 이 과정에서 각 노드는 로컬 스토리지를 스캔해 정확한 데이터를 찾아야 했는데, 피크 시간대에는 이 스캔이 하루 이상 걸리기도 했다.

또한, 각 노드의 Merkle Tree를 재계산해야 했고, 랜덤하게 배치된 범위 때문에 전체 키 공간의 스냅샷을 만들기 어렵다는 문제가 있었다. 결국 초기 전략은 이론적으로는 동작하지만, 실제 운영 환경에서는 심각한 부하와 관리 어려움을 야기했다.

“There was no easy way to take a snapshot of the entire key space due to the randomness in key ranges”

전체 키 공간의 스냅샷을 만들려면 각 노드에서 개별적으로 키를 추출해야 했다. 랜덤한 범위 때문에 효율적인 백업이 불가능했다.

Strategy 2: 균등 파티션과 랜덤 토큰 (임시 전환기)

문제의 근본 원인은 파티셔닝과 노드 배치가 결합되어 있었기 때문이었다. 아마존은 이를 분리하기로 결정했다. 해시 공간을 $Q$개의 동일한 크기의 파티션으로 나누고, 각 노드는 여전히 $T$개의 랜덤 토큰을 보유했다. ($Q$가 $N$보다 훨씬 크다.) 이제 토큰은 실제 데이터 위치가 아니라, 노드가 어느 파티션을 담당할지만 결정하는 역할을 했다.

이 방식에서는 파티션이 고정되어 있어 범위가 예측 가능하고, 런타임에 노드가 추가되거나 제거될 때 배치 방식을 유연하게 변경할 수 있었다. 그러나 랜덤 토큰 방식의 복잡성은 여전히 남아 있었고, 로드 밸런싱 효율성이 앞으로 나올 전략을 포함해 최악이었다고 한다.

Strategy 3: 균등 파티션과 균등 토큰

최종적으로 아마존은 매우 단순하면서도 강력한 전략을 선택했다. 해시 공간을 $Q$개의 균등한 파티션으로 나누고, 클러스터에 $S$개의 노드가 있을 때, 각 노드는 정확히 $Q/S$개의 파티션을 담당하도록 했다. 새로운 노드가 들어오면 기존 노드들로부터 균등하게 파티션을 가져오고, 노드가 제거되면 남은 노드들이 균등하게 그 파티션을 분배받는다.

“Faster bootstrapping/recovery: Since partition ranges are fixed, they can be stored in separate files, meaning a partition can be relocated as a unit by simply transferring the file”

이 접근 방식의 가장 큰 장점은 부트스트래핑과 복구가 즉각적이라는 점이다. 파티션이 파일 단위로 저장되기 때문에, 스캔 없이 파일을 그대로 복사하여 이동할 수 있다. 또한 각 파티션을 독립적으로 아카이빙할 수 있어 전체 데이터셋을 병렬로 효율적으로 백업할 수 있다. 멤버십 정보 역시 크게 줄어들어, 가십 프로토콜로 주고받는 메타데이터가 1000분의 1 수준으로 감소했다.

다음 글에서 Quorum 를 다룹니다.