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

장선규·2025년 1월 21일

Study

목록 보기

6/12

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

해시 키 재배치 문제

N개의 캐시 서버가 있다고 하자. 아래의 해시 함수를 사용하여 서버의 부하를 균등하게 나누어보자.

serverIndex = hash(key) % N

4대의 서버가 있다고 가정 (N=4)
key는 아래의 표를 따름

위의 해시 함수를 적용하면 키 값이 다음과 같이 서버에 분산된다.

해시 키 재배치

하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다. 예를 들어 서버 1이 중단되었다고 하면, 해시 키가 재분배된다.

데이터가 재분배되면 대부분의 클라이언트는 캐시 데이터가 없는 서버로 접근하게 됨
그 결과 대규모 캐시 미스 발생

전통적인 해시 테이블은 슬롯(N) 수가 바뀌면 대부분의 키를 재배치한다.
안정 해시를 통해 해시 테이블의 재배치 문제를 해결할 수 있다.

안정 해시

안정 해시(consistent hash)는 해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다. (k: 키의 개수, n: 슬롯 수).

해시 공간과 해시 링

안정 해시의 동작 원리에 대해 알아보자.

해시 함수 f: SHA-1
출력 값 범위: x0, x1, x2, … , xn
- SHA-1 함수의 출력 범위는 0부터 $2^{160}-1$ 까지이므로 x0 = 0 이고 xn = $2^{160}-1$ 이다.

위의 해시 공간을 구부려서 해시 링을 만든다. x0과 xn은 끝 지점에서 서로 맞닿아 있다.

해시 서버 & 키

해시 함수 f를 사용하여 서버 IP나 이름을 링 위에 배치시킬 수 있다. 마찬가지로 캐시할 키 k0, k1, k2, k3 또한 해시 링 위의 임의의 지점에 배치할 수 있다.

사용된 함수 f는 % 연산은 사용하지 않고 있음에 유의
아직까지는 초기 작업이라고 생각해도 무방

서버 조회

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

서버 추가 & 제거

따라서 서버가 추가된 경우, 키 가운데 일부만 재배치하면 된다.

s4 서버가 k0과 s0 사이에 추가되었다고 가정
k0 기준 시계방향으로 가장 가까운 서버가 s4로 바뀌었으므로, s4로 재배치
재배치 범위: s3~s4

마찬가지로 서버가 제거될 때도 일부 키만 재배치된다.

s1이 삭제되었다고 가정
k1 기준 시계방향으로 가장 가까운 서버가 s2로 바뀌었으므로, s2로 재배치
재배치 범위: s0~s2

기본 구현법의 두 가지 문제

살펴본 안정 해시 알고리즘은 다음과 같다.

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

하지만 해당 접근법은 두 가지 문제점을 가진다.

문제점

서버 추가/삭제를 감안하면 파티션의 크기를 균등하게 유지하는 것이 어렵다.
- 위의 경우에서 만약 s1 서버가 삭제되면, s2 서버는 다른 서버에 비해 훨씬 큰 해시 공간을 가지게 됨
키의 균등 분포를 달성하기가 어렵다.
- 위의 경우, 대부분의 키는 s2에 저장될 것이며, s3에는 아무 키도 보관되지 않을 것

가상 노드

위의 문제를 해결하기 위해 제안된 기법이 가상 노드(또는 복제, replica) 기법이다.

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

Open image-20250106-161509.png

두 서버 s1, s2가 존재하며, 각 서버는 3개의 가상 노드(sx_0, sx_1, sx_2)를 가진다고 가정
k0의 경우 시계방향으로 가장 가까운 s1_1에 저장됨

특징

가상 노드 수가 늘어나면 표준편차가 작아져서 키의 분포가 더 균등해짐
- 100~200개의 가상 노드 사용 시 표준편차는 5~10%
가상 노드 수가 늘어나면 데이터를 저장할 공간이 더 필요해짐
시스템 요구사항에 맞도록 가상 노드에 대한 적절한 trade-off 필요
- https://dgryski.medium.com/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8

마치며

안정 해시 도입 시 이점

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

안정해시 사례

다른 안정 해시 알고리즘

구글 Jump Consistence Hash
- 노드 추가/제거 시 데이터(키) 재배치 비용 최소화 및 균등 배치 목적
- 핵심 원리: 버킷 사이즈를 넘어갈 때까지 시도한 횟수가 해시값이 됨
  - 목적지까지의 거리(버킷 크기)가 4라면 1, 1/2, 1/3, 1/4의 확률을 가진다. 이 주사위를 매 판마다 던지면 된다.
- 동작 과정
```
def jump_consistent_hash(key, num_buckets):
    key = hash(key)  # 64-bit hash
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = ((key * 2862933555777941757) & 0xFFFFFFFFFFFFFFFF) + 1  # 해시 업데이트
        j = int((b + 1) * (1 << 31) / ((key >> 33) + 1)) # 1/N으로 확률이 점점 감소
    return b
```
  - shift 연산을 이용한 바이너리 값이 (거의)랜덤 하다는데 착안한 알고리즘
  - (거의) 랜덤한 해시 키가 생성됨
  - 분모로 나누면 1/N로 확률이 점점 낮아지는 결과를 얻을 수 있음
  - 이 과정을 반복하여 j가 버킷 사이즈를 넘어가면, 그때의 b 값이 저장될 위치가 됨
- 비교
- 참고) https://www.popit.kr/jump-consistent-hash/, https://chongkong.github.io/jump-consistent-hash
Multi-probe 안정 해시
- 구현: https://github.com/dgryski/go-mpchash
Rendezvous 해시
- 구현: https://github.com/dgryski/go-rendezvous