[대규모 시스템 설계 기초] 5장 - 안정 해시 (Consistent Hash) 설계

 

 

# 서론

수평적 규모 확장을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.

-> 이 목표를 달성하기 위해 보편적으로 안정 해시 기술을 사용함

이 해시 기술이 풀려고 하는 문제를 자세히 살펴보자

 

# 일반 해시 함수의 해시 키 재배치 (rehash) 문제

• N개의 캐시 서버가 있다고 가정해보자
• 이 서버들에 부하를 균등하게 나누기 위해, 보편적으로는 아래와 같은 해시 함수를 사용한다.
  serverIndex = hash(key) % N
• 예를 들어, 서버 대수(N)가 4대일 때, hash(key0) % 4 = 1 이면 데이터를 찾기 위해 1번 서버에 접속하게 됨
• 이 방법은 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할 때 잘 동작한다. 그러나....서버가 새로 추가되거나 삭제되면?
• -> 키에 대한 해시 값은 안 변하는데, 나머지연산을 적용할 N 수가 바뀌니까 키들에 대한 서버 인덱스 값이 전부 달라짐
• 없어지거나 추가된 서버에 저장된 키 뿐 아니라, 대부분의 키가 재분배 됨 -> 대부분 캐시 클라이언트가 없는 엉뚱한 서버에 접속
• -> 대규모 캐시 미스 발생

# 안정 해시 (consistent hash)

• 안정 해시 : 해시 테이블 크기(서버 대수)가 조정될 때, 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술
  • k : 키 개수 / n : 서버 개수
  • 원래 서버 한대당 평균적으로 k/n 개의 키를 처리하고 있었음 -> 서버 한 대가 사라질 때 해당 서버가 처리하던 애들만 재배치하겠다! 는 뜻

동작 원리를 살펴보자

• 해시 링 : 해시 공간의 양쪽을 구부려 붙여 만든 링

• 해시 서버와 해시 키들을 링 위의 특정 지점에다가 배치를 한다
• 서버 조회는, 해당 키의 위치로부터 시계 방향 탐색 중 만나는 가장 첫번째 서버에서 진행
• 예시
  • 서버 A, B, C ...
  • 키 1, 2, 3 ...
  • A < 1 < 2 <= B < 3 <= C 인 경우 : 1, 2는 B에, 3은 C에 저장

서버가 새로 하나 추가되거나 죽는 경우에, 키 가운데 일부만 재배치하게 된다!

 

이런 안정 해시 알고리즘의 기본 절차는 아래와 같다.

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

여기엔 2가지 문제가 있다.

• 서버가 추가되거나 삭제되는 상황을 감안할 시, 파티션(서버 사이)의 크기가 균등하게 유지될 수 없다.
• 키의 균등 분포를 달성하기 어렵다
• -> 가상노드(virtual node)기법 사용

# 가상 노드 (replica라고도 함)

• 가상 노드 : 실제 서버를 가리키는 서버
• 한 서버는 여러 개의 가상 노드를 가질 수 있으며, 가상 노드의 개수가 늘어날수록 표준 편차가 작아져 데이터가 고르게 분포됨
• 가상 노드 개수는 100-200개 사용하는 경우 표준 편차 값이 평균의 5~10%사이임
• 타협적 결정 (tradeoff) - 내가 설계할 목적에 맞게 조절해야 함
  • 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐
  • 그러나 그럴수록 가상 노드 데이터를 저장할 공간이 더 많이 필요해짐

# 안정 해시의 이점

• 서버가 추가되거나 삭제될 때, 재배치되는 키의 수가 최소화 됨
• 데이터가 보다 균등하게 분포하게 되므로, 수평적 규모 확장성 달성하기 쉬움
• 핫스팟(hotspot) 키 문제를 줄임 : 특정 서버에만 접근이 지나치게 빈번하면 서버 과부하 문제 생길 수 있다

핫스팟 : 파티셔닝이 고르게 이뤄지지 않아 다른 애들에 비해 부하가 높아진 파티션

# 안정 해시를 사용하는 유명한 애들

• AWS DynamoDB 파티셔닝 관련 컴포넌트
• Apache Cassandra Cluster에서의 데이터 파티셔닝
• Discord 채팅 어플리케이션
• Akamai CDN

 

끝