안정 해시 설계 2

안정 해시에 대해 더 깊게 알아보자.

(Consistence Hashing, 일관된 해싱)

 

안정 해시 알고리즘은 MIT에서 처음 제안 되었다.

 

안정 해시 알고리즘의 기본 절차는 다음과 같다.

1. 서버와 키를 균등 분포 해시 함수를 사용하여 해시 링에 배치한다.

2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다.

 

위 절차는 문제점이 있다..

1. 서버가 추가되거나 삭제되는 상황에서 각 서버에 매핑될 파티션 크기를 균등하게 유지할 수가 없다..

-> 서버가 하나 제거된다면 제거된 서버의 매핑 공간은 다음 서버에 추가되므로

-> 서버간 매핑 공간은 불균형을 이루게 된다.

 

2. 키의 균등 분포를 달성하기 어렵다.

-> 서버가 추가되거나 삭제되는 상황이 지속되면..

-> 어떤 하나의 서버 공간은 지나치게 많고.. 어떤 서버는 정말 좁은 현상이 나타날 수 있다.

-> 이에 따라.. 키의 균등 분포가 이루어 지지 않을 가능성이 높다.

 

 

문제점을 해결해보자.

가상 노드

해시 링위에 A server에 대한 노드를 1개만 둘 것이 아니라..

여러개의 노드를 둔다.

server1에 대한 노드가 총 3개, server2에 대한 노드도 총 3개이다.

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해질 것이다.

(표준 편차가 작아져서 데이터가 균등하게 분포됨.)

-> 서버가 제거(or 추가) 되더라도 가상노드가 많아서..

-> 하나의 큰 파티션이 다음 서버의 파티션으로 추가되는 현상은 없어진다.

-> 잘게 쪼개진 파티션들이 각각 다음 서버의 파티션으로 추가 될 것이다.

 

주의점

가상 노드를 늘리면 그만큼 가상 노드 데이터를 저장할 공간은 늘어난다.

(tradeoff)

 

 

 

마지막으로 안정 해시의 장점에 대해 서술하며 정리해보자.

1. 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화 된다.

2. 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.

3. 핫스팟 키 문제를 줄인다.

-> 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제인데..

-> 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제의 가능성을 줄인다.

 

 

어디에 사용되고 있는가..

Amazon DynamoDB

Apache Cassandra

Discord

Akamai CDN

Meglev