5장 안정 해시 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초

안정 해시 설계

수평적 규모 확장하려면 요청 이나 데이터를 서버에 균등하게 나누는 것이 중요합니다.

안정 해시를 보편적으로 사용 하는 기술입니다.

 

 

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있다고 가정

부하를 균등하게 나누기 위해 serverIndex = hash(key) % N(N은 서버 개수)

 

키	해시	해시 % 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

 

만약 hash(key0) % 4 = 1이면, 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야 한다.

 

키 분포도

서버 인덱스	0	1	2	3
서버	server 0	server 1	server 2	server 3
키	key1 key3	key0 key4	key2 key6	key5 key7

 

서버 풀의 크기가 고정이고 데이터 분포가 균등할 때는 잘 동작합니다.

 

만약 서버 1개가 추가되거나 삭제되면 문제가 생깁니다.

서버 1이 내려갔다면? 서버의 풀 크기는 3으로 변하고, 키에 대한 해시 값은 변하지 않지만 나머지(%)연산을 적용하면 서버 인덱스가 달라집니다.

 

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

 

변화된 키 분포도

서버 인덱스	0		1	2
서버	server 0	server 1	server 2	server 3
키	key0 key1 key5 key7		key2 key4 key6	key3

 

1번이 죽으면서 키가 재분배가 되면서 캐시 클아이언트가 데이터가 없는 엉뚱한 서버에 접속하게 됩니다.

그 결과로 대규모 캐시미스가 발생하게 됩니다.

안정 해시는 이 문제를 효과적으로 해결하는 기술입니다.

 

 

안정 해시

위키피디아 왈

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

 

해시 공간과 해시 링

해시 함수 f로 SHA-1을 사용, 함수의 출력 값 범위는 x0, x1, x2 ... xn과 같다고 하자.

SHA-1의 해시 공간 범위는 0 부터 2^160-1까지 이다.

x0 = 0, xn은 2^160-1

해시 공간 펼친 모양

해시 공간 링모양

 

해시 서버

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

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

서버를 해시 링뒤에 배치한 결과

 

해시 링

여기 사용된 해시 함수는 해시 키 재배치 문제에 업근된 함수와 다름

나머지 연산 사용하고 있지 않음

캐시할 키 key0, key1, key2, key3를 해시 링 위의 배치한 결과

 

캐시 키를 해시 링에 배치한 결과

 

서버 조회

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

key0 -> 서버 0에 저장, key 1 -> 서버 1에 저장, key 2 -> 서버 2에 저장, key 3 -> 서버 3에 저장

서버 조회

 

서버 추가

서버를 추가하더라도 키 가운데 일부만 재배치하면 됩니다.

 

서버 추가

서버 4를 추가하더라도 key0만 재배치됨을 보여집니다.

k1, k2, k3는 같은 서버에 그대로 남습니다.

왜냐하면 key0으 위치에서 시계 방향으로 순회했을 때 처음 만나는 서버가 서버4 이기 때문에 다른키들은 재배치를 안해도 된다.

 

서버 삭제

서버를 삭제 하더라도 키 일부분만 재배치 됩니다.

서버 삭제

 

기본 구현법의 두 가지 문제

안정 해시 알고리즘은 MIT에서 처음 제안이 된 알고리즘입니다.

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

이 접근법에는 2가지의 문제가 있습니다.

서버 추가/삭제로 인한 불균등한 저장 공간

2. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능하다.

• 파티션은 인접한 서버 사이의 해시 공간을 의미
• 어떤 서버는 굉장한 해시 공간을 할당 받고, 어떤 서버는 굉장한 큰 해시 공간을 할당 받는 상황이 가능
• s1 서버 삭제로 인한 s2의 파티션이 다른 파티션 대비 거의 2배로 커지는 상황

 

2. 키의 균등 분포를 달성하기가 어려움

• 서버 1과 서버3은 아무 데이터도 갖지 않는 반면, 대부분의 키는 서버2에 보관될 것

 

가상 노드

가상노드 적용

• 가상 노드(virtual node)는 실제 노드 또는 서버를 가리키는 노드
• 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다.
• 위 사진은 서버 0과 서버 1은 3개의 가상 노드를 가진다.
• 서버는 여러개 파티션을 관리해아한다.
• s0으로 표시된 파티션은 서버 0이 관리하는 파티션이고, s1은 서버1이 관리하는 파티션

 

가상노드에 키 추가

• 키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.
• k0이 저장되는 서버는 노드 s1_1, 서버 1이다.

 

가상 노드의 개수를 늘리면 키의 분포는 점점 균등해집니다.

표준 편차가 작아져서 데이터가 고르게 분포되기 때문입니다.

표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도

 

 

재배치할 키 결정

서버 추가로 인한 재배치할 키 결정

• 서버가 추가되거나 제거되면 데이터 일부는 재배치 해야합니다.
• 서버 4가 추가되었을 경우 s4로부터 반시계 방향에 있는 첫 번째 서버 s3 까지입니다.
• 즉 s3 ~ s4까지 재배치

 

서버 삭제로 인한 재배치할 키 결정

• 만약 s1 삭제가 될 경우 s1기준 반시계 반향에 있는 s0 ~ s2 까지는 재배치 해야한다.

 

마치며

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확정성을 달성하기 쉬움
• 핫스팟 키 문제를 줄인다. 특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있음
• 안정 해시 사용하는 곳
  • 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
  • 아파치 카산드라 클러스터에서의 데이터 파티셔닝
  • 디스코드 채팅 어플리케이션
  • 아카마이 CDN
  • 매그레프 네트워크 부하 분산기