안정 해시 설계(hash ring)

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

안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

 

보편적인 해시 함수와 문제점

• N개의 서버가 있을 때, 부하를 균등하게 나누기 위해 해시 함수 사용 
• serverIndex = hash(key) % N(서버의 개수) 
• hash(key0) % 4 = 1인 경우, 클라이언트가 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속 
• 서버 풀(server pool) 크기가 고정되어 있고, 데이터 분포가 균등할 때 잘 동작한다.

하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.

• 1번 서버 장애 -> 1번 동작 중지 -> 서버 풀 크기 3 변경 -> 나머지 서버 인덱스 값들이 달라짐
  • 대규모 캐시 미스(cache miss)

안정 해시

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n 개의 키만 재배치하는 해시 기술이다. 

여기서 k는 키의 개수이고, n은 슬롯(slot)의 개수이다. 

이와는 달리 대부분 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다

 

해시 공간 & 해시 링

해시 함수 f -> SHA-1

해시 함수 f 출력값 범위 -> 0  ~ 2^160-1 -> x0, x1, x2 ,,, xn

x0 = 0, xn = 2^160-1

 

해시 서버 

해시 함수 f를 이용하여 ip나 이름을 해시 링 위의 어떤 위치에 대응

 

해시 키

나머지 연산 % 는 사용하지 않는다.

 

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

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

 

• 서버 조회 
  • 해시 함수를 사용해서 서버 4개를 해시 링 위에 해시 서버 배치 : s0, s1, s2, s3 
  • 해시 링 어느 지점에 해시 키 배치 : k0, k1, k2, k3 
  • 키가 저장되는 서버 : 해당 키 위치로부터, 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버
•   서버 추가 
  • 키 가운데 일부만 재배치 
  • 서버 4 추가 시, key0 만 재배치 
  • key0은 서버 4에 저장된다.
• 서버 제거 
  • 하나의 서버가 제거되면 키 가운데 일부만 재배치
  • 서버 1이 삭제되면, key1 만 서버 2로 재배치

 

 

 

기본 구현법의 두 가지 문제 

• 서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다.
  • 파티션 : 인접한 서버 사이의 해시 공간
• 해시 값에 따라 배치가 되기 때문에 균등 분포가 달성되기 어려울 수도 있다.

해결법 -> 가상 노드 또는 복제 

 

가상 노드

• 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음 
• 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 함
•  키 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버 
• 가상 노드의 개수를 늘릴수록 키의 분포는 점점 더 균등해짐 
• 표준 편차가 작아져서 데이터가 고르게 분포되기 때문 
• 가상 노드의 개수를 늘리면 표준 편차가 줄어들지만 저장할 공간이 늘어나니 트레이드오프 발생

 

안정 해시의 이점 

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