TIL

5장 안정 해시 설계

안정 해시는 수평적 규모 확장에서 요청 또는 데이터를 균등하게 나누기 위해 보편적으로 사용하는 기술

해시 키 재배치(rehash) 문제

• N개의 캐시 서버에서 서버 부하를 균등히 나누는 방법은 해시 함수를 사용하는 것이다.
  • serverIndex = hash(key) % N (N은 서버 개수)
  • 특정 키가 보관된 서버를 알기 위해 해시 함수를 적용하게 된다. (hash(key0) % N = 1이면 1번 서버에 접속)
• 위 단순한 나머지 해시 함수가 잘 동작하는 경우
  • 서버 풀 크기가 고정되어 있을 때
  • 데이터 분포가 균등할 때
• 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.
  • 서버 하나가 다운되면 키에 대한 해시 값은 변하지 않지만(hash(key0)의 값) 서버 풀 크기(N)는 변한다.
  • 대부분의 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속하게 된다. → 대규모 캐시 미스 발생

안정 해시

• ‘안정 해시(consistent hash)’는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개 키만 재배치하는 해시 기술
  • k: 키의 개수, n: 슬롯(slot) 개수
  • 전통적인 해시 테이블은 슬롯 수가 바뀌면 대부분 키를 재배치

해시 공간과 해시 링

• 안정 해시 동작 원리를 이해하기 위한 사전 조건
  • 해시 함수 f로 SHA-1을 사용
  • 함수의 출력 값 범위는 x0, x1, x, … xn
  • SHA-1 해시 공간은 0 ~ 2^160 - 1까지 이므로 x0 = 0, xn = 2^160 - 1

• 이 해시 공간을 원으로 구부리면 해시 링(hash ring)이 만들어진다.

  

• 해시 함수 f를 사용하여 서버 IP나 이름을 이 링 위 위치에 대응시킬 수 있고 캐시할 키(key) 또한 배치할 수 있다.

  

• 안정 해시 알고리즘의 기본 절차
  • 서버와 키를 균등 분포 해시 함수를 사용해 해시 링의 배치
  • 키의 위치를 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버

• 위 방법에 따르면 서버를 중간에 추가하더라도 키 일부만 재배치하면 된다.

  

  • s4가 추가되면 k0만 재배치되고 나머지는 재배치되지 않는다.
• 한 서버를 제거하더라도 키 가운데 일부만 재배치될 것이다.

기본 구현법의 두 가지 문제

1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는 것이 불가능하다.
   • 해시 링에서 최초에는 4개 서버가 균등하게 배치되었다고 해도 하나만 제거되더라도 엄청난 불균형 배치로 변하게 된다.

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

   

   • 위 상황에서 s3 서버와 s1 서버는 아무 데이터도 갖지 않고 대부분의 데이터는 s2에 보관될 것이다. - 이 문제를 해결하기 위해 가상 노드 또는 복제라 불리는 기법을 사용한다.

가상 노드 (virtual node)

• 가상 노드는 실제 노드 또는 서버를 가리키는데 하나의 서버는 링 위에 여러 가상 노드를 가질 수 있다.

  

  • 즉 각 서버는 여러 개 파티션을 관리
  • s0으로 시작하는 3개 노드는 s0 서버의 가상 노드, s1로 시작하는 3개 노드는 s1 서버의 가상 노드이다.
• 키 위치에서 시계 방향 탐색하다 만나는 최초의 가상 노드가 키가 저장될 서버가 된다.
• 가상 노드 개수를 늘리면 키 개수가 점점 더 균등해진다.
  • 표준 편차가 작아져 데이터가 고르게 분포되기 때문
• 가상 노드 개수를 늘리면 저장 공간이 더 많이 필요하게 되기 때문에 tradeoff가 필요

마치며

안정 해시의 이점은 다음과 같다.

• 서버가 추가/삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟 키 문제를 줄인다.
  • 특정 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 발생
  • 안정 해시는 데이터를 고르게 분포하기에 이런 문제를 줄인다.