5_안정_해시_설계.md

5. 안정 해시 설계

• 수평적 규모 확장성을 달성하기 위해선 요청/데이터를 서버에 균등 분배하는 것이 중요
• 안정 해시 (Consistent Hash) 는 이를 위한 대표적인 기술

해시 키 재배치 문제

• 가장 간단하게 사용되는 전통적인 해싱 방법은 mod 연산
  • serverIndex = hash(key) % N
• 이는 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등한 경우 잘 동작함
• 하지만 서버가 추가되거나 삭제되면 모든 해시값이 바뀌게 되는 단점이 있음
• 안정 해시는 이를 효과적으로 해결하는 기술

안정 해시 (Consistent Hash)

• wikipedia: 안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술
  • k는 키의 개수, n은 슬롯의 개수

해시 공간과 해시 링

• SHA-1 기준 hash space 범위는 0 ~ 2^160 - 1 까지임
• 이를 원형으로 만들면 hash ring 을 구성할 수 있음.
• 

해시 서버

• 안정 해시를 사용하는 함수 f를 사용하면 서버 IP 나 이름을 해시 링 위의 특정 위치에 대응 가능
• 

해시 키

• 해시 서버와 마찬가지로 해싱 대상 key 를 링 위의 특정 위치에 배치 가능
• 

서버 조회

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

서버 추가

• 서버 조회의 내용을 기반으로 유추해보면, 서버가 추가되더라도 키 가운데 일부만 재배치하면 됨
• 

서버 제거

• 서버 제거 역시 키 가운데 일부만 재배치하면 됨
• 

Consistent hasing 의 기본 구현법의 두 가지 문제

• 안정 해시 알고리즘은 MIT에서 처음 제안되었고, 기본 절차는 아래와 같음
  1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치
  2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 첫 서버가 키가 저장될 서버
• 위 케이스에서 발생 가능한 2개의 문제점
  1. 서버 추가/삭제 경우 파티션 크기의 균등 유지가 불가
  • 이 때 파티션은 인접한 서버 사이의 해시 공간
  • 어떤 서버는 매우 작은 해시 공간 / 어떤 서버는 매우 큰 해시 공간 할당 가능
  • 
  2. 키의 균등 분포 어려움
  • 아래 그림에서 볼 수 있듯이 서버1, 서버3은 아무런 데이터도 없고 대부분의 데이터가 서버 2에 저장될 수 있음
  • 
• 이런 문제점들을 해결하기 위해 가상 노드 (virtual node) 또는 복제 (replica) 의 기법 등장

가상 노드 (virtual node)

• 가상 노드는 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에 여러개의 가상 노드를 가질 수 있으며, 결과적으로 각 서버는 여러개의 파티션을 관리하게 됨
  • 
• 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버의 위치
  • 
• 가상 노드의 개수를 늘릴수록 키의 분포는 더 균등해지는 경향이 있음
• 하지만 그렇다고 가상 노드의 개수를 너무 늘리면 데이터 저장 공간이 더 필요하기 때문에 trade off 발생

마무리

• 안정 해시를 사용하는 대표적인 케이스
  • Amazon dynamo DB
  • Apache Cassandra
  • Akamai CDN
• 안정 해시의 이점 요약
  • 서버가 추가/삭제될 때 재배치되는 키의 수가 최소화
  • 데이터가 보다 균등 분포되므로 수평적 규모 확장 달성 쉬움
  • 핫스팟 키 문제 줄여줌 (특정 샤드에 트래픽이 몰리는 것)