[대규모 시스템 설계] 5. 안정 해시 설계

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는것이 중요하다.

그렇다면 안정 해시 설계는 무엇이고, 무엇을 해결하기 위한 설계인가?

 

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있다면 이 서버들에 부하를 균등하게 나누기 위해선 다음과 같이 나머지 연산을 통해 서버에 부하를 나눌것이다

serverIndex = hash(key) % N (N: 서버 개수)

 

아래는 N이 4로 고정일때의 예시다

해시가 서버에 나눠지는 방식

 

나눠진 형태

하지만 만약 서버가 추가되거나 삭제 혹은 에러가 발생해서 죽는다면?

1번 서버가 죽은 경우

위의 그림처럼 1번 서버가 죽은 경우, Module 연산이 4에서 3으로 변경됨에 따라 대부분의 키 재분배

→ 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속

→ 대규모 캐시 미스 발생

 

안정 해시

해시 테이블의 크기가 조정되면 평균적으로 k/n개의 키만 재배치.(k: Key 개수, n: 슬롯 개수)

SHA-1와 같은 해시 함수를 통해 출력 값의 범위가 x0 ~ xn이라고 가정하고 이를 해시 링 형태로 만들면 아래와 같다

해시 함수의 출력 값

위의 표를 이어서 만든 해시 링

 

1. (Module 연산을 사용하지 않는) 균등분포 해시 함수 f를 사용하면 서버 IP나 이름을 링 위의 특정 위치와 매칭할 수 있다

2. 해시할 키 k0, k1, ... 또한 해시 링 위의 특정 위치에 배치할 수 있다

3. 링위에 배치된 키는 시계 방향에서 만나는 가장 가까운 서버에 저장된다

위 3개를 종합하면 아래 그림으로 표현할 수 있다

안정 해시 기본 구현법

서버가 추가되거나 제거가 된다면, 평균적으로 k/n개의 키가 재배치된다(위의 3번에 따라 저장되는 서버 재배치)

 

기본 구현법의 문제점은 2가지가 있다

- 추가와 삭제를 한다면 파티션의 크기(인접한 서버 사이의 해시 공간)를 균등하게 유지하지 못한다

- 키의 균등 분포를 달성하기 어렵다

 

1. 서버 삭제 이후 발생하는 파티션 크기 불균등

2번의 예로 아래와 같이 S3에는 아무것도 할당되지 않는 경우가 발생할 수 있다

 

2. 키의 균등 분포를 달성하지 못한 경우

 

 

가상 노드(Replica, 복제)

위 문제를 해결하기 위해 제안된 기법이다.

하나의 서버는 링 위에 임의의 숫자 K개의 가상 노드를 가질 수 있다

→ K가 높을수록 키의 분포는 점점 더 균등해진다. 표준 편자가 작아져서 데이터가 고르게 분포되기 때문

→ K를 약 100~200으로 설정한다면 표준 편차 값은 평균의 10%~5%밖에 되지 않는다

→ K값을 더 늘릴수록 표준 편차의 값은 더 작아지지만, 가상 노드 데이터를 저장할 공간이 더 필요해지므로 적절한 trade off가 필요

가상 노드 3개씩 가지고 있는 서버0, 1

 

만약 서버가 사라진다면?

각 서버의 가상 노드 기준으로 반시계 방향에 있는 다른 서버의 가상노드 사이에 있는 키들만 재배치를 하면 된다.

추가 또한 마찬가지로 추가된 서버부터 반시계 방향에 있는 다른 서버의 가상노드 사이에 있는 키들만 추가된 서버로 재배치하면 된다