[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 5. 안정 해시 설계

 

대규모 시스템 설계를 하기 위해서는 기본적으로 스케일 업보다 스케일 아웃이 좋다고 배웠다. 스케일 아웃을 적용하면서 여러 대의 서버를 둘 때 주의할 점은 데이터를 각 서버에게 균등하게 나누어주는 것이다. 5장에서 배울 안정 해시가 서버에게 데이터를 균등하게 나누어줄 때 사용된다. 이어서 안정 해시에 대해서 알아보도록 하겠다.

 

해시 키 재배치 문제 (rehash)

N개의 캐시 서버가 있다고 가정했을 때, 이 서버에게 균등하게 부하를 나누려면 해시 함수를 이용해야 한다. 해시 값을 서버의 개수 N개로 나눈 나머지를 인덱스로 삼고 해당 서버에 저장하면 된다.

serverIndex = hash(key) % N // N은 서버의 개수

 

4대의 서버를 사용하는 예제로 해시가 어떻게 동작하는지 알아보겠다.

 

키	해시	해시 % 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에 접속해야 한다. key0 ~ key7까지 키 값이 서버에 분산된 것을 그림으로 보면 다음과 같다.

 

 

이러한 방법은 서버 풀이 고정되어 있을 때는 잘 동작할 수도 있지만, 서버가 추가되거나 삭제된다면 문제가 생긴다. 만약 1번 서버가 장애를 일으켜서 동작이 중단되면 서버의 수가 1만큼 줄어드니 서버 풀은 3으로 변한다. 그 결과로, 해시 값은 변하지 않더라도 서버의 인덱스 값이 달라져 올바르지 않은 서버에 접근하게 된다.

 

 

위 그림과 같이 1번 서버가 장애로 죽으면 대규모 캐시 미스가 발생하게 될 것이다. 앞으로 알아볼 안정 해시는 이 문제를 효과적으로 해결할 수 있는 기술이다.

 

안정 해시

안정 해시란 해시 테이블 크기가 조정될 때 평균적으로 k / n개의 키만 재배치하는 기술이다. k는 키의 개수이고, n은 슬롯의 개수이다. 안정 해시를 이해하려면 해시 공간과 해시 링에 대해서도 알아야 동작 원리를 이해할 수 있다.

 

해시 공간

해시 함수의 출력 값 범위가 x0, x1, x2, ... , xn 이라고 했을 때 해시 함수로 SHA-1를 사용한다고 하면 해시 공간의 범위는 0부터 2¹⁶⁰ - 1까지로 알려져 있고 이 공간을 그림으로 표현한 것이 위의 그림이다.

 

해시 링

 

해시 링은 이 해시 공간의 양족을 구부려서 접어서 만들어지게 된다. 해시 링 위에 서버와 키를 올림으로 안정 해시를 구현할 수 있는데, 이어서 해시 서버와 해시 키, 조회까지 알아보도록 하겠다.

 

---

해시 서버

 

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

 

해시 키

위의 그림과 같이 캐시할 키 key0, key1, key2, key3를 해시 링 위의 어느 지점에 배치할 수 있다. 앞에서 언급했던 해시 키 재배치 문제에서 언급한 함수와는 다르고, 나머지 연산(%)은 현재 사용하지 않고 있다.

 

✨ 서버 조회

키가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 돌았을 때 가장 가까이에 위치한 서버이다.

그림에 따라 key 0은 서버 0에 저장되고, key 3은 서버 3에 저장되게 된다. 이렇게 해시 링 위에 해시 서버와 해시 키를 올려서 키가 적절한 서버에 안정적으로 할당될 수 있는 것이 안정 해시이다.

 

서버의 추가 & 제거, 키의 재배치

안정 해시를 구현하면 서버를 추가하거나 제거해도 해시 키 재배치 문제와 같이 많은 캐시 미스가 일어나지 않고, 안정적으로 키가 저장된다.

좌 - S4 서버 추가 / 우 - S2 서버 삭제

 

서버를 추가하더라도 일부 키만 재배치 하면 된다. k1, k2, k3 키는 같은 서버에 남는다. key 0는 서버 4가 추가 되기 전에는 서버 0에 저장되어 있었지만, 서버 4가 추가됨에 따라 key 0과 시계 방향으로 가장 가까운 서버가 서버 4로 변했기 때문에 key 0만 재배치 되면 된다.

 

서버를 삭제할 때도 마찬가지로 일부 키만 재배치된다. key 1만 재배치가 되었고, 나머지 key들에게는 영향이 가지 않은 것을 확인할 수 있다.

 

📌 키의 배치는 항상 시계 방향으로 가까운 서버에 배치되었기 때문에, 재배치도 이와 같은 규칙을 적용하여 재배치하면 된다.

 

---

기본 구현법의 두 가지 문제

MIT에서 처음 제안된 안정 해시 알고리즘의 절차는 다음과 같다.

 

1. 균등 분포 해시 함수를 통해 서버와 키를 해시 링에 배치

2. 키의 위치에서 링을 시계 방향으로 탐색하다가 만나는 최초의 서버가 키가 저장될 서버

 

하지만 이 접근법에는 두 가지 문제가 있다.

 

첫 번째 문제는 파티션의 크기를 균등하게 유지하기 어렵다

서버가 추가되거나 삭제되는 상황을 감안했을 때 파티션의 크기를 균등하게 유지하는 것이 어렵다. 여기에서 파티션이란 말은 인접한 서버 사이의 해시 공간이다. 

 

그림을 보면 S1이 삭제됨에 따라 S2의 파티션이 다른 파티션 대비 2배 가까이 커진 상황이 발생하였다.

 

두 번째 문제는 키의 균등 분포를 달성하기 어렵다.

 

 

그림과 같이 서버가 배치되어 있다고 하면, 서버 1과 3은 아무 데이터도 갖지 않는 방면 서버 2에 대부분의 키가 저장되는 문제점이 존재한다.

이러한 문제를 해결하기 위하여 제안된 기법이 바로 가상 노드이다.

---

가상 노드

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

 

가상 노드 / 가상 노드에 붙는 Key

 

왼쪽 그림을 보면 서버 0과 서버 1은 3개의 가상 노드를 갖는다. 서버 0은 S0을 하나 쓰는 대신 S0_0, S0_1, S0_2을 사용했고, 서버 1도 동일하게 3개의 가상 노드를 해시 링 위에 배치하였다. 따라서 각 서버는 여러 개의 파티션을 관리해야 한다.

오른쪽 그림과 같이 키가 링 위에 배치되었을 때 이전과 마찬가지로 가장 가까운 오른쪽에 있는 파티션이 해당한 서버가 바로 키가 저장될 서버이다. k0는 서버 1에 저장될 것이다.

 

가상 노드의 개수를 늘릴 수록 키의 분포는 더욱 균등해질 것이다. 표준 편차가 낮아지기 때문에 데이터가 고르게 분포된다. 가상 노드를 많이 배치할수록 표준 편차는 떨어지겠지만 가상 노드를 저장할 공간이 더욱 필요해지게 되기 때문에 타협적 결정(trade-off)가 필요하다.

 

마치며

5장에서는 안정 해시가 왜 필요한지, 그리고 어떻게 동작하는 살펴보았다. 안정해시를 사용해서 얻는 장점을 정리하고 마치도록 하겠다.

 

 • 서버가 추가 / 삭제될 때 재배치되는 키가 최소화 됨

 • 데이터가 균등하게 분포되어 스케일 아웃을 달성하기 쉬움

 • 유명인사 문제 (hotspot key)를 줄일 수 있다.