[Architecture]안정 해시 설계(consistent hash)

개요

수평적 규모 확작성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는게 중요합니다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술입니다.

당면한 문제 : 해시 키 재배치(rehash) 문제

전통적인 해시 테이블에서 서버(노드)를 추가하거나 제거할 때 대부분의 키가 재배치되어야 하는 문제가 발생합니다. 이는 시스템에 큰 부하를 주고, 수평적 확장성을 제한하는 주요 원인이 됩니다.

서버의 개수 변하지 않을때: 문제 없음

서버의 개수가 변할때: 대규모 캐시 미스 발생

문제가 발생한 1번 서버에 보관되어 있는 키 뿐만 아니라 대부분의 키가 재분배 되었다. 1번 서버가 죽으면 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다.

해결 방법: 안정 해시(consistent hash)

안정 해시는 테이블 크기가 조정 될 때 평균적으로 오직 k(키의 개수)/n(슬롯의 개수)개의 키만 재배치하는 해시 기술이다. 이를 통해 서버 추가나 제거가 빈번한 대규모 분산 시스템에서도 효과적인 데이터 관리가 가능해집니다.

동작 원리

해시 공간과 해시 링

해시 공간: 모든 가능한 해시 값들을 포함하는 범위입니다.

해시 링: 해시 공간을 원형으로 나타낸 것으로, 각 서버나 키는 이 링 위의 특정 지점에 매핑됩니다.

해시 서버

서버는 해시 링 위의 한 지점에 배치됩니다. 이 위치는 해시 함수 f를 사용하면 서버 IP나 이름을 이 링 위의 어떤 위치에 대응할 수 있습니다.

해시 키

데이터 항목(키)도 해시 함수를 통해 해시 링의 지점에 배치됩니다. 여기에 사용된 해시 함수는 "해시 키 재배치 문제"에 언급된 함수와는 다릅니다.

캐시할 키 key0, key1, key2, key3 또한 해시 링 위의 어느 지점에 배치할 수 있습니다.

서버 조회

키를 조회할 때는 해시 링을 따라 시계 방향으로 탐색을 진행, 만나는 첫 번째 서버에서 해당 키를 찾습니다.

e.g.) key0은 server0에 저장, key1은 server1에 저장 된다.

서버 추가

서버를 추가하면 해시 링의 일부 키만 새 서버로 이동합니다.

server4가 추가 되기 전 key0은 서버 0에 저장되어 있었다. key0의 위치에서 시계 방향으로 순회했을 때 처음으로 만나게 되는게 server4이기 때문에 server4가 추가된 뒤에 key0은 server4에 저장된다.

서버 제거

서버를 제거하면 해당 서버에 있던 키들이 인접한 서버로 이동합니다.

server1이 삭제 됐을 때 key1만 server2로 재배치 된다.

기본 구현법의 두 가지 문제

기본 절차

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

첫 번째 문제: 불균등한 파티션

서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기(인접한 서버 사이의 해시 공간)를 균등하게 유지하는 게 불가능하다. 서버 사이의 해시 공간이 균등하지 않으면, 일부 서버에 더 많은 키가 할당될 수 있습니다.

두 번째 문제: 키의 불균등 분포

• 키가 해시 공간에 균등하게 분포되지 않으면, 일부 서버에 과부하가 발생할 수 있습니다.

해결하기 위한 기법

가상 노드

각 서버를 여러 가상 노드로 나누어 해시 링에 배치합니다. 이를 통해 키와 서버의 분포를 더욱 균등하게 만들 수 있습니다.

가상 노드 개수를 늘리면 표준 편차가 작아져서 데이터가 더 고르게 분포된다. 그러나 그렇게 된다면 가상 노드 데이터를 저장할 공간이 더 많이 필요하게 될 것입니다.

적절한 수준에서 tradeoff가 필요합니다.

재배치할 키 결정

서버가 추가되거나 제거될 때, 가능한 한 적은 수의 키를 다른 서버로 옮겨야 전체 시스템의 부하와 성능 저하를 최소화할 수 있습니다.

재배치할 키 결정 과정

1. 서버의 해시 위치 파악: 새로운 서버가 추가되거나 기존 서버가 제거될 때, 해당 서버의 해시 위치를 파악합니다.
2. 영향받는 키의 범위 결정:
   • 서버 추가 시: 새 서버는 해시 링에서 특정 구간을 담당하게 됩니다. 이 구간은 새 서버와 해시 링 상에서 가장 가까운 이웃 서버 사이에 있습니다. 이 구간에 속한 키들이 재배치 대상입니다.
   • 서버 제거 시: 제거되는 서버에 있던 키들은 이 서버의 다음 이웃 서버로 이동합니다.
3. 가상 노드 활용: 가상 노드를 사용하면 더욱 세밀한 키 분배가 가능합니다. 각 서버는 여러 개의 가상 노드를 가질 수 있으며, 각 가상 노드는 해시 링의 작은 부분을 담당합니다. 서버를 추가하거나 제거할 때, 영향을 받는 가상 노드의 키들만 재배치합니다. 이 방법으로 재배치해야 할 키의 수를 줄일 수 있습니다.

마치며

안정 해시의 이점

• 재배치 최소화: 서버가 추가되거나 제거될 때, 재배치되는 키의 수가 최소화되어 시스템의 안정성과 효율성이 향상됩니다.
• 균등한 데이터 분포: 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 가상 노드를 사용하면 데이터가 보다 균등하게 분포되어, 서버 간 부하가 고르게 분산됩니다.
• 핫스팟 문제 감소: 안정 해시는 데이터를 좀 더 균등하게 분배하므로, 특정 서버에 대한 과도한 접근으로 인한 핫스팟 문제를 줄일 수 있습니다.

가상 면접 사례로 배우는 대규모 시스템 설계 기초