가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장: 안정 해시 설계

안정 해시 설계에 대해 배운 점을 정리하였습니다.

 

샤딩이 뭐냐? 하면 이런겁니다. 데이터베이스 노드가 3개 있다면, 데이터베이스에 데이터를 읽고 쓸 때 어떠한 알고리즘을 통해 데이터를 저장할 장소를 분리합니다. 이렇게 하면 수평적으로 확장하기 용이합니다 (read replica를 기용하는 방법은 어쨌든 모든 데이터베이스에 데이터가 sync 되어있어야 하기 때문에 그런 점을 따져보면 샤딩이 확장성이 좋습니다).

 

해시 키 재배치 문제

rehash 문제는 이런겁니다. 만약 서버가 3개인 상태에서 서버가 scale out을 했다고 가정해봅시다. 그러면 나머지 연산 알고리즘 결과가 아예 달라지면서 각 서버에 들어가야 할 데이터가 거의 전부 바뀌어버리게 됩니다. 이런 현상이 해시 키 재배치 문제입니다. 이는 곧 대규모 캐시 미스로 이어지며, 서버에 스케일링 이벤트가 발생할 때마다 성능 저하의 큰 요인이 될 수 있습니다.

 

안정 해시

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술입니다. 여기서 k는 키의 개수이고, n은 슬롯의 개수입니다. 앞서 말씀드린 재배치 문제를 어떻게 k/n개로 최소화 할 수 있는걸까요?

 

해시 공간과 해시 링

hash(key) 함수의 출력 값 범위를 x0 ~ xn 까지라고 해봅시다. 어떤 키 값을 넣어도 저 슬롯 중 하나의 공간을 차지하게 될 겁니다. 안정 해시의 핵심은 바로 hash ring을 사용하는 겁니다. 쉽게 이해하기 위해 위 그림의 직선형 공간을 구부려서 원으로 만든다고 생각해봅시다.

그러면 이러한 모양이 나옵니다. 이 해시 링 위에 서버를 배치시키면 아래와 같은 그림이 될 겁니다.

이렇게 슬롯 사이에 서버를 배치하고, 가령 s0 ~ s1 사이 슬롯에 할당된 키는 서버 0에 저장하고, s1 ~ s2 사이 슬롯에 할당된 키는 서버 1에 저장하는 식으로 데이터를 저장하는 방식을 안정 해시라고 합니다. 

• 이런 방식으로 데이터를 저장하면 가령 s1에 해당하는 서버 1이 다운되었을 때 s1 ~ s2 사이에 있는 데이터를 서버 0으로 옮기면 되기 때문에 k/n개의 키만 이동할 수 있는 원리입니다.
• 서버가 새로 추가될 때에도, 해당 구간에 존재하는 키 값만 이동시키면 되기 때문에 마찬가지로 k/n개의 키만 이동시켜도 됩니다.
• 이 방법은 이전에 사용한 나머지 연산(%)을 사용하는 것이 아닌 것이 유의합니다.

 

구현 방법과 두 가지 문제점

구현 방법을 정리하면 아래와 같습니다:

• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치합니다.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버입니다.

하지만 이는 두 가지 문제점이 존재합니다:

• 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능합니다 (예를 들어, 서버가 다운되었을 때 그 빈 공간에 새로운 서버가 생기지 않는 한 그 부분의 파티션이 커질 수 밖에 없습니다)
• 키의 균등 분포(uniform distribution)을 달성하기가 어렵습니다 (특정 구간의 키 값들이 한 서버로 병합되기 때문입니다)

 

따라서 위의 두 가지 문제를 해결하기 위해 아래의 두 가지 방법이 제시됩니다.

문제 해결 방법: 가상 노드

virtual node는 실제 노드를 가리키는 노드(pointer)로서, 하나의 서버가 링 위에 여러 개의 가상 노드를 갖도록 합니다. 이렇게 가상 노드를 여러 개 배치함으로써 파티션 간의 간격이 좁아지며, 가상 노드의 개수가 많을수록 키의 분포는 점점 더 균등해집니다. (가상 노드의 배치는 랜덤하게 둡니다)

 

따라서 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 합니다. 만약 하나의 서버가 다운된다면, 한 연속적인 공간이었던 파티션이 여러개로 분할되어 있기 때문에 한 파티션으로 키가 몰리는 현상을 방지할 수 있습니다. 그림에서는 몇 개 그리지 않았지만 실제로는 많은 수의 가상 노드를 기용한다고 합니다.

 

가상 노드의 개수를 늘리면 표준 편차의 값은 더 떨어지지만, 가상 노드 데이터를 저장할 공간이 더 많이 필요하게 됩니다. 따라서 이 tradeoff를 고려하여 가상 노드의 개수를 적절히 설정해야 합니다.

 

이론 정리

안정 해시의 이점은 아래와 같습니다:

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화됩니다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽습니다.
• 핫스팟 키 문제를 줄입니다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있습니다. 

안정 해시는 실제로 널리 쓰이는 기술이며, DynamoDB나 Apache Cassandra, Discord 등 여러곳에서 해당 기술이 쓰인다고 합니다.