[System Design Interview] Chapter05. 안정 해시 설계

 

이번 장에서는 어떻게 데이터를 고르게 분산할 수 있는지에 대해 알아본다.

일반적으로, 데이터를 N 개의 서버에 나누어서 저장하게 될 때 해시 함수를 이용해서 데이터를 분배해서 저장하는 방법을 생각하게 된다. (해시 테이블과 유사)

그러나 이 방법은 다음과 같은 취약점이 있다.

• 특정 서버에 장애가 발생할 경우, 장애가 발생한 서버에 저장된 데이터가 모두 재배치 되어야 한다
• 캐시 서버일 경우, 장애가 발생한 서버에 저장된 키였을 경우 그 키에 대한 데이터가 없는 다른 서버에 접속하게 되어 대규모 cache miss 가 날 수 있다
• Hotspot key 문제가 발생할 수 있다 → 데이터를 균등하게 배치하지 못해 특정한 샤드에 대한 접근이 많을 경우이다.

안정 해시(consistent hash) 는 해시 테이블 크기가 조정될 때, 평균적으로 k/n 개의 키만 재배치하는 해시 기술이다. (k=키의 갯수, n=슬롯(서버)의 개수)

안정 해시 기술의 특징은

• 샤드에 걸쳐 키를 균등하게 배포
• 서버 추가 및 삭제 시 재배치되는 키의 갯수를 최소화함, 각 서버에 균등하게 키가 배포됨

안정 해시는 다음과 같이 동작한다.

해시 공간의 범위(SHA-1 기준, 보통 0 부터 2^160 - 1 까지) 가 있고, 이 범위의 공간을 갖는 링이 존재한다고 생각해보자.

각 서버와 키의 해시 값을 해시 함수를 이용해 구한 뒤, 링의 특정 지점에 배치한다

어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 가면서 만나는 첫번째 서버이다.

 

 

A, B, C 가 서버이고 1,2,3,4 가 키 일때, 1은 A, 2는 B, 3과 4는 D 로 배치되게 된다.

즉 기본 절차는 다음과 같다.

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

그러나 다음과 같은 drawback 이 발생할 수 있다

• 서버가 추가 및 삭제될 때 파티션의 크기를 균등하게 유지하기 힘듦
• 키의 균등 배포를 달성하기 어려움

따라서 이 문제를 해결하기 위해 가상 노드 가 존재

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 가상 노드를 가질 수 있다

가상 노드의 갯수를 늘리면 키의 분포도 균등해 지게 된다 (아래의 표와 같이)

 

가상 노드는 데이터를 균등하게 분배하여 부하 균형을 유지하게 된다

 

 

출처:

가상 면접 사례로 배우는 대규모 설계 기초 5장

https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

https://tom-e-white.com/2007/11/consistent-hashing.html