05장. 안정해시

개요

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

 

해시 키 재배치(refrash)문제

• N개의 캐시 서버에서 부하를 균등하게 나누기 위한 해시 함수 사용
  • serverIndex = hasy(key) % N (N, 서버의 개수)
• 특정한 키가 보관된 서버를 알아내기 위해 나머지 연산을 f(key)%4와 같이 적용한 키
  • 예를 들어 hash(key0) % 4=1 이면 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 함

키	해시	해시 % 4 (서버 인덱스)
key0	18358617	1
key1	26143584	0
key2	18131146	2
key3	35863496	0
key4	34085809	1
key5	27581703	3
key6	38164978	2
key7	22530351	3

 

 

위 표에서 키 값이 서버에 어떻게 분산되는지 보여줌

• 서버 풀의 크기가 고정되어있고 있고 데이터 분포가 균등할 때 잘 동작하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생김
• 1번서버가 장애를 일으켜 장애가 났을 시 서버 풀의 크기는 3으로 변하면서 키에 대한 해시 값은 변하지 않지만 자머지 연산을 적용해 서버 수가 1만큼 줄어들어 계산한 서버 인덱스 값은 달라진다. (해시 %3 )
• 해시 % 3의 결과

키	해시	해시 % 4 (서버 인덱스)
key0	18358617	1
key1	26143584	0
key2	18131146	2
key3	35863496	0
key4	34085809	1
key5	27581703	3
key6	38164978	2
key7	22530351	3

 

변화된 키 분포

 

• 장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아니라 대부분의 키가 재분배 됨으로써 대부분 캐시 클라이언트가 데이터가 없는 서버에 잘못 접속하게 됨 (대규모 cache miss가 발생하고 이 문제를 해결하기 위해 안정 해시를 사용)

 

안정해시

위키피디아의 정의

• 안정해시는 해시 테이블 크기가 조정될 때 평균적으로오직 k/n개의 키만 재배치하는 해시 기술 (k = 키의 개수, n = 슬롯의 개수)
  • 이와 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치 함

 

해시공간과 해시 링

• 해시 함수 f로 SHA-1을 사용, 그 함수의 출력 값 범위는 x1,x2, ... xn
• SHA-1의 해시 공간 범위는 0부터 2¹⁶⁰ -1까지라고 알려져 있음
• x0은 0, xn은 2¹⁶⁰ -1 이며, 나머지 x1부터 xn -1 까지는 그 사이의 값을 갖게 될 것.

해시 공간을 그림으로 표현한 것

 

• 이 해시 공간의 양쪽을 구부려 접으면 해시 링이 만들어짐

해시서버

• 해시 함수 f를 사용하면 서버IP나 이름을 이 링 위의 어떤 위치에 대응 시킬 수 있음

서버 4개를 해시 링 위에 배치한 결과

 

해시 키

• 여기서 사용된 해시 함수는 해시 키 재배치 문제에 언급된 함수와 다르며 나머지 연산 %는 사용안하고 있음에 유의
• 캐시할 키 key0~key3 또한 해시 링 위의 어느 지점에 배치할 수 있음

 

 

서버조회

• 어떤 키가 저장되는 서버는 해당 키의 위치로부터 시계방향으로 링을 탐색해 나가면서 만나는 첫번째 서버로 key0은 서버0에 저장, ,key1은 서버1에 저장, key2는 서버 2, key3은 서버3에 저장

서버추가

• 서버를 추가해도 키 가운데 일부만 재배치하면 됨
• 새로운 서버 4가 추가된 뒤에 key0만 재배치되고 key1~key3은 같은 서버에 남음
• 서버4가 추가되기 전 key0은 서버 0에 저장되어있지만 서버 4가 추가된 뒤 key0은 key0의 위치에서 시계방향으로 순회했을 때 처음으로 만나게 되는 서버가 서버4이기 때문에 서버4에 저장 (다른 키들은 재배치 X)

 

서버제거

• 하나의 서버가 제거되면 키 가운데 일부만 재배치되고 서버1이 삭제됐을 때 key1만이 서버2로 재배치 됨 (나머지 키에는 영향 X)
• 기본 구현법의 두가지 문제
  • 안정해시 알고리즘은 MIT에서 처음 제안

 

• 기본절차
• 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치
• 키의 위치에서 링을 시계방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
• 기본절차의 문제점
  • 서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는게 불가능
    • 파티션은 인접한 서버 사이의 해시공간인데 어떤 서버는 큰 공간을 할당 받는 반면 다른 서버는 아주 작은 공간을 할당 받을 수 있음

• 키의 균등 분포를 달성하기 어려움
• 아래 그림 처럼 서버가 배치되어 있을 때 서버1과 서버3은 아무 데이터도 갖지 않는 반면 대부분의 키는 서버 2에 보
  • 이를 해결하기 위해 제안된 기법이 가상노드 또는 복제라 불리는 기법 사용

가상노드

• 가상 노드는 실제 노드 또는 서버를 가리키는 노드로서 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있음
• 아래 그림에서 서버0과 서버1은 각각 3개의 가상 노드를 가짐
• 서버0과 서버1을 링에 배치하기 위해 s0_0~s0_2, s1_0~s1_2의 세 가상 노드 사용. 
• 각 서버는 여러 파티션을 관리해야 함
  • s0 : 서버0이 관리하는 파티션
  • s1 : 서버 1이 관리하는 파티션
• 키의 위치로부터 시계방향으로 링응ㄹ 탐색하다 만나는 최초 가상노드가 해당 키가 저장될 서버로 k0가 저장되는 서버는 k0위치로부터 링을 시계방향으로 탐색하다 만나는 최초 가상노드는 s1_1가 나타내는 서버인 서버1

• 가상 노드 개수를 늘리면 표준편차가 작아져 데이터가 고르게 분포되어 키의 분포는 점점 더 균등해짐
• 가상 노드의 개수를 더 늘리면 표준편차는 떨어지지만 그만큼 가상 노드 데이터를 저장할 공간이 많이 필요
  • 타협적 결정(trade off) 필요

 

재배치할 키 결정

• 서버 추가/제거 시 데이터 일부는 재배치 해야 함

서버 4 추가

• 서버4가 추가 될 경우 영향받은 범위는 s4부터 그 반시계 방향에 있는 첫번째 서버 s3까지임 즉, s3부터 s4사이에 있는 키들을 s4로 재배치 필요

서버1 삭제

• s1(삭제된 노드) 부터 그 반시계 방향에 있는 최초 서버 s0사이에 있는 키들이 s2로 재배치 되어야 함

 

정리

안정해시의 이점

• 서버가 추가 되거나 삭제될 때 재배치 되는 키의 수가 최소화 됨
• 데이터가 보다 균등하게 분포되어 수평적 규모 확장성을 달성하기 쉬움
• 핫스팟 키 문제를 줄여줌
• 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하가 생길수 있는데 안정 해시는 데이터를 균등하게 분배함으로써 이 문제가 발생할 가능성을 줄여줌

 

안정해시를 사용하기로 유명한 것들

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서의 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카이 CDN
• 매그래프 네트워크 부하 분산기