안정 해시 설계

언제?

---

언제 우리는 안정 해시를 필요로 할까

• 대용량 트래픽에 버티기 위해서 DB를 분할하여 여러 대의 샤드를 구축했다고 하자
• 수평적 규모 확장성을 달성하기 위해서는 데이터를 여러 샤드에 균등하게 나누는 것이 중요하다.
  • API 요청에 대해서도 동일하다. 요청이 여러 서버에 균등하게 나눠지는 것이 중요하다.
• 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술

 

해시 키 재배치 문제

---

여러 대의 서버를 뒀는데, 그 중에 하나가 고장난다면?

N개의 캐시 서버가 있다고 해보자.
이 서버들에 부하를 균등하게 나누는 보편적인 방법은 아래의 해시 함수를 사용하는 것이다.

serverIndex = hash(key) % 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

특정 키가 보관된 서버를 알아내기 위해서 나머지(Moudlar)연산을 적용하였다.
모듈러 연산을 통해 알아낸 서버 인덱스가 1이면 해당 키는 1번 서버에 저장이 되어 있다는 뜻이다.
그렇다면 클라이언트는 캐시에 저장된 데이터를 가져오기 위해서는 서버 1에 접속을 해야 한다.

이러한 방법은 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할 때는 잘 동작한다.
하지만 서버가 추가되거나, 기존 서버가 삭제되면 문제가 발생한다.

예를 들어 1번 서버가 장애를 일으켜 동작을 중단했다고 해보자.
그러면 서버 풀의 크기 N은 3으로 감소한다.

 

[서버 1 삭제 이후]

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

이전과 비교했을 때, 대부분의 키에 대해서 서버 인덱스가 변경되었다.
장애가 발생한 1번 서버의 키 뿐만 아니라, 대부분의 키가 재분배되는 것이 해당 방식의 문제점이다.
서버 한대가 죽으면 이후에 대부분의 키가 엉뚱한 서버(캐시값이 없는)에 접속을 해서, 대규모 캐시 미스가 발생할 것.

이러한 문제를 해결하기 위해서 안정 해시가 필요하다.

 

안정 해시?

---

안정 해시란 정확히 어떤 해시를 의미할까

• 해시 테이블의 크기가 조정될 때, 오직 k/n개의 키만 재배치하는 해시 기술
• 여기서 k는 키의 개수이고, n은 슬롯의 개수

 

해시 공간과 해시 링

---

안정 해시의 동작 원리를 이해하기 위해 필요한 개념

• 해시 값이 될 수 있는 범위를 x0 ~ xn 이라고 하자.
• SHA-1 함수를 예시로 들면, 값의 범위는 0부터 2^160 - 1이 된다.
• 해시 공간의 양쪽을 구부려서 접으면 그림과 같이 해시 링이 만들어지게 된다.

 

해시 서버

---

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

• 위의 그림은 4개의 서버를 해시 링 위에 배치한 결과

 

해시 키

---

여기서 사용되는 해시 함수는 모듈러 연산을 사용하는 해시 함수가 아니다

• 캐시 키 역시 링 위의 어느 지점에 배치할 수 있다.
• 그리고 어떤 키가 저장되는 서버는 키의 위치로부터 시계 방향으로 링을 탐색해서 처음으로 만나는 서버가 된다.

 

서버 추가

---

서버 추가를 하면 어떻게 될까?

• 서버를 추가하더라도 기존의 키들은 재배치가 되지 않는다.
• 추가된 서버와 추가된 서버 직전의 서버 사이에 있는 키들만 재배치가 이루어진다.

 

서버 삭제

---

서버를 삭제하면 어떻게 될까?

• 서버를 제거되면 키 가운데 일부만 재배치가 된다.
• 제거된 서버에 할당되어 있던 키들만 재배치가 되면 된다.
  • 즉, 위의 그림에서는 S0 ~ S1 사이에 있던 키들만 재배치가 된다.

 

기본 구현법의 2가지 문제

---

위에서 소개한 기본적인 해시 링 방식 구현법에는 문제가 존재한다.

1. 키를 서버에 균등하게 분포시키는 것이 어렵다는 문제이다.
2. 서버가 추가되거나 삭제되게 되면, 파티션의 크기를 균등하게 유지하는 게 불가능하다.
   • 임의의 두 서버 사이의 구간의 길이가 일정하지 않다는 것이다.

 

가상 노드

---

위의 2가지 문제를 해결하기 위해서 제시된 방법

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

• 가상 노드의 수를 늘리게 되면, 키의 분포는 점점 더 균등해질 것이다.
• 서버가 추가되거나 삭제되었을 때 재배치되는 키의 수가 최소화 된다.
• 또한 재배치되는 키들을 남아 있는 서버들이 균등하게 가져갈 확률이 높아진다.

 

[참고문헌]

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