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

해시 키 재배치(rehash) 문제

• N개의 캐시 서버가 있다고 할 때, 이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래와 같은 해시 함수를 사용
• N = 서버의 개수

serverIndex = hash(key) % N

위와 같은 방법의 특징

장점

• 서버 풀의 개수가 고정되어 있을 때에나 부하를 균등하게 나눌 수 있다.

단점

• 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.
  • 서버 4개가 동작한다고 하자. 중간에 1번 서버가 장애를 일으켜 동작을 중단하면 서버 풀의 크기가 3으로 변한다.
  • 결과로, 키에 대한 해시 값은 변하지 않지만 나머지(%) 연산을 적용하여 계산한 서버 인덱스 값은 달라진다. (hash % 4 → hash % 3)
  • 즉 한 서버가 죽으면 대규모 캐시미스가 발생하게 된다.
  • 안정 해시는 이 문제를 해결할 수 있다.

---

안정 해시 (Consistent Hash)

• 안정 해시는 해시 테이블의 크기가 조정될 때 평균적으로 k/n개의 키만 재배치하는 해시 기술이다. (k = 키의 개수, n = 슬롯 개수)
  • 나머지(%) 연산을 사용하지 않는다.
• 키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
  • Nick Smith 는 Partition 1
  • Steven King 은 Partition 2

서버 추가한 경우

• 서버를 중간에 추가하여 Partition 4가 생겼을 경우 Partition 4의 위치가 Mary Drake 와 Nick Smith 의 사이에 위치하게 된다면?
• Mary Drake는 Partition 1에서 Partition 4로 재배치된다.

서버 제거한 경우

• Partition 3이 제거된 경우 Alex Hue와 Josh Ernst만 Partition 1로 재배치하면 된다.

안정 해시의 문제점

• 서버가 추가되거나 삭제될 때, 재배치가 이루어지면서 해당 서버에 키가 집중되기 때문에 파티션의 크기를 균등하게 유지하는 것이 불가능하다. (핫스팟 키 문제)
• 특정 상황에 따라 키가 균등하게 분포되지 않을 수도 있다.

문제점을 해결하는 가상 노드 (Virtual Node)

• 가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
• 가상 노드의 개수를 늘리면 표준 편차가 작아져서 키의 분포도는 점점 균등해진다.
  • 100~200개의 가상 노드를 사용했을 경우 표준 편차 값은 평균의 5%(가상 노드가 200개인 경우)에서 10%(가상 노드가 100개인 경우) 사이다.

가상 노드의 수를 계속 늘린다면?

장점

• 키의 분포도가 균등해진다.

단점

• 가상 노드 데이터를 저장할 공간이 더 많이 필요하다.

그림 참고

https://velog.io/@haron/가상-면접-사례로-배우는-대규모-시스템-설계-기초-5장-안정-해시-설계