가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장 - 안정 해시 설계
가상 면접 사례로 배우는 대규모 시스템 설계 기초 책 정리 글입니다.
개요
요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.
✏️ 해시 키 재비치(rehash) 문제
보편적으로 해시 함수는 다음과 같이 사용한다.
1
serverIndex = hash(key) % N(서버의 개수)
만약 서버의 개수4 라고 하면
| 키 | 해시값 | 해시 % 4 |
|---|---|---|
| key0 | 5 | 1 |
| key1 | 6 | 2 |
| key2 | 7 | 3 |
| key3 | 8 | 0 |
그러면 서버 입장에서는 hash(key0) % 4 =1이면, 클라이언트는 캐시에 보관된 데이터를 가져오기 위해 서버 1에 접속해야한다.
위와 같은 방법은 서버 풀(pool)의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때 잘 작동한다. 하지만 서버가 삭제가 되거나 추가되면 어떻게 될까?
예로 서버1이 장애를 일으켜 동작이 중지되었다면 서버 풀의 크기는 3이 될 것이고, 그에따른 해시 값의 나머지 연산들은 바뀔 것이다.
| 키 | 해시값 | 해시 % 3 |
|---|---|---|
| key0 | 5 | 2 |
| key1 | 6 | 0 |
| key2 | 7 | 1 |
| key3 | 8 | 2 |
서버가 하나 줄음에 따라 해시의 나머지값들이 기존 값과 동일한 것이 단 하나도 없다. 이러면 1번 서버가 죽으면 모든 캐시 클라이언트가 데이터가 없는 서버에 접근하게 된다는 것이다. 그 결과로 대규모 캐시 미스(cache miss)가 발생할 것이다. 안정 해시는 이 문제를 효과적으로 해결하는 기술이다.
✏️ 안정 해시
해시 테이블 크기가 조정될 때 오직 k/n개의 키만 재배치하는 해시 기술 k는 키의 개수, n은 슬롯(slot)의 개수이다.
해시 공간과 해시 링
해시 함수f는 SHA-1을 사용한다고 가정하면 해시를 통해 나온 값의 범위는 0부터 $ 2^{160} -1$ 까지라고 알려져 있다.
x0을 0, xn은 $ 2^{160} -1 $ 라고 하면
이러한 길이를 가지는 공간을 가질 것이다. 사이사이 공간들은 x1,x2,x3…라고 가정한다. 이 공간을 해시 공간(hash space)이라고 한다.
그리고 이를 양쪽을 접어 구부리면
이러한 그림의 형태인 해시 링(hash ring)이라고 한다.
해시 서버
이를 해시 함수 f를 통해서 서버IP나 이름을 이 링 위의 어떤 위치에 대응시킬 수 있다. 만약 4개의 서버가 있다고 하고 서버를 배치한다고 하면
이런식으로 배치할 수 있다.
해시 키
여기서 사용된 해시 함수f는 나머지 연산을 하지 않고 있음을 알고 있어야한다. 때문에 해시 키는 링 위의 어느 지점에 배치할 수 있다.
서버 조회
어떠한 키가 저장되는 서버는, 해당 키가 시계 방향으로 링을 탐색했을때 조우하는 첫 번째 서버다. 때문에 위 그림에서 key0은 server0에 저장되고 key1는 server1에 저장되는 식이다.
서버 추가
만약 서버가 추가되더라도 키 가운데 일부만 재배치하면 된다.
server4가 추가되자 key0은 server0에 저장되는것이 아닌 server4에 저장될 것이다.
그림이 너무 당연해서 뭐가 바뀐건지 헷갈릴 수 있는데, 나머지연산으로 재배치했던 해시함수는 모든 키의 저장 위치가 바뀔 수 있었는데 이 방식은 서버가 추가되어도 모든 키에 영향을 미치는게 아니라는 것이다.
서버 제거
마찬가지로 서버가 하나 제거 되었을때 그 서버가 저장하고 있던 키들만 재배치 해주면 될 것이다.
기본 구현법의 두 가지 문제
기본 절차는 다음과 같다.
- 서버와 키를 균등 분포(uniform distribution) 해시 함수를 사용해 해시 링에 배치한다.
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
생각해보면 첫 번째 조건이 굉장히 이상적이라고 볼 수 있다. 당장 위의 예제만 봐도 서버 하나가 지워지거나 추가될 때마다 균등성이 깨져버린다.
또 다른 문제는 키가 하나의 서버에 몰려서 저장될 가능성이 높아서 균등성 문제가 생긴다는 것이다.
s1,s3는 아무 키도 저장되어있지 않은데 s2에 대부분의 키가 저장되어있는걸 볼 수 있다.
이를 해결하기 위해서 가상 노드(virtual node) 또는 복제(replica)라 불리는 기법이 생겼다.
가상 노드
가상 노드는 실제 노드 또는 서버를 가리키는 노드다.
결과적으로 이 노드들을 링위에 많이 넣어버려서 해시 링에 균등성을 주는 것이다.
동작 방식
- 서버0과 서버1이 있다. (더 추가 가능)
- 서버0과, 서버1은 N개의 가상 노드를 가진다.(여기서 N은 3이라 가정)
- s0_0, s0_1, s0_2는 서버0의 가상노드들이고, s1_0, s1_1, s1_2는 서버 1의 가상노드들이다.
- 서버0과 서버1은 이 노드들의 경계들(파티션)을 관리하게 된다.
이제 새로운 키가 서버에 저장되어야 한다고 하면, 키의 위치가 임의적으로 정해지고 링을 탐색하면서 가장 가까운 서버에 저장될 것이다.
k0이라고 불리는 키가 s1.1에 저장되는데 s1.1은 가상노드이고 실제 가리키는 건 서버1이므로 서버1에 저장될 것이다.
이렇듯, 가상 노드를 늘리면 키의 분포는 점점 균등해지지만 저장할 공간이 더 필요해진다는 트레이드 오프가 있다.
때문에 적절히 노드 개수를 조절해야한다.
🤔 정리
안정 해시가 나오게 된 배경은 보편적으로 사용하는 해시 함수의 경우 서버가 삭제나 추가 되었을 때 키가 재분배 되느라 없는 캐시에 접근하여 캐시 미스가 발생하는 확률을 줄이고 키가 최대한 덜 재분배되고 균등하게 맞추는 목표에 있다.
안정 해시의 이점은 다음과 같다.
- 서버가 추가되거나 삭제될 때 재배치 되는 키의 수가 최소화된다.
- 데이터가 보다 균등하게 분포되어 수평적 규모 확장이라는 목표에 달성하기 쉬워졌다.
- 핫스팟(hotspot) 키 문제를 줄인다. 특정 샤드(shard)에 접근이 지나치게 빈번하거나 등의 문제를 말한다. 안정 해시는 데이터를 좀 더 균등하게 분배하므로 이런 문제가 생길 가능성을 줄여준다.
안정 해시는 실제로 널리 쓰이는 기술이고, 네트워크 부하 분산기, CDN, 디스코드 채팅 어플리케이션, 아파치 카산드라 클라스터에서의 데이터 파티셔닝, 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트에서 쓰인다.