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

https://haril.dev/blog/2023/06/04/Consistent-Hashing

안정 해시 설계

먼저 해시(Hash)란, 임의의 문자열이나 숫자를 정해진 규칙에 따라 특정 숫자로 변환하는 것으로 이해하면 된다.

이러한 해시 기법은 서버 부하를 균등하게 분산하기 위한 방법으로도 활용되었으며,
보통 key를 해시한 값에 서버 풀의 크기를 나눈 나머지를 기준으로 어느 서버에 데이터를 저장할지 결정하는 방식을 사용한다.

hash(key n) % (서버 풀의 크기)

 

하지만 이 방식은 서버 풀의 크기가 고정되어 있지 않은 환경에서는 해시 결과가 전반적으로 달라진다는 치명적인 단점을 가지고 있다.

단순히 서버를 추가하거나 제거하는 경우뿐만 아니라, 서버 장애로 인해 서버 수가 변경되는 상황에서도 기존에 저장된 대부분의 데이터가 다른 서버로 재배치되는 문제가 발생한다. (해시 키 재배치 문제)

 

이러한 문제를 효과적으로 해결하기 위해 등장한 방식이 바로 안정 해시이다.

 

• 해시(Hash)
  → 임의의 키를 해시 함수로 고정된 범위의 값으로 매핑해 O(1) 조회를 가능하게 하는 기법
• 일반 해시의 문제점
  → 노드 수 변경 시 해시 결과가 전반적으로 달라져 대부분의 키가 재배치되는 문제
• 안정 해시(Consistent Hashing)의 개념
  → 키와 노드를 동일한 해시 공간(링)에 배치해, 키를 시계 방향의 가장 가까운 노드에 할당하는 방식
• 안정 해시의 이점
  → 노드 추가·삭제 시 전체 키가 아닌 일부 키만 이동하도록 보장해 재배치 비용을 최소화함

 

 

해시 공간과 해시 링

해시 함수로는 SHA-1을 사용한다 했을 때, SHA-1의 해시 공간 범위는 0부터 2^160-1 까지 이기 때문에

결과적으로 x0(0)부터 xn(2^160-1)까지의 값을 갖게 된다.

이 시작과 끝을 만날 수 있도록 접으면 원의 형태가 되는데, 이를 해시 링이라고 부른다.

 

해시 서버

해시 함수(f)를 사용하면 서버 IP나 이름을 해당 링 위의 특정 위치에 대응시킬 수 있다.

아래 그림은 4개의 서버를 해시 링 위에 배치한 결과이다.

 

해시 키 및 서버 조회

해시 링 위에 서버를 배치한 것처럼 key도 배치를 해준다.

이 때 key가 저장되는 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색하여 가장 가까이에 있는 (첫 번째로 만나는) 서버이다.

아래 그림으로 보게 된다면 (k0, s0) (k1, s1) (k2, s2) (k3, s3) 로 짝이 맞게 된다.

 

서버 추가

이 글 처음에 '해시 키 재배치 문제'를 안정 해시가 해결한다고 언급했었다.

아래 그림은 안정 해시가 그 문제를 어떻게 해결하는지 직관적으로 보여주고 있다.

k0은 기존에 s0 서버에 저장되고 있었으나, 해시 링을 시계 방향으로 탐색한 결과 더 가까운 s4 서버를 발견했다.

그러면 이제 k0은 s0이 아닌 s4에 저장된다. 다른 키들은 탐색을 해도 동일한 결과가 나오기 때문에 재배치가 일어나지 않는다.

 

서버 제거

서버 제거 또한 마찬가지이다.

기존에 s1에 저장되었던 k1은, s1이 제거되며 가장 가까운 서버를 탐색할 때 s2를 찾게 된다.

이렇게 서버가 제거 될 때도 k1만 재배치가 되고, 나머지 key들은 재배치가 되지 않는다.

 

기본 구현법의 두 가지 문제

그럼에도 위에서 언급한 구현법이 완벽하지는 않다.

이유는 아래와 같다.

 

1. 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치하는 방법
   -> 서버가 추가되거나 삭제되는 상황이 생길 경우, 파티션(인접한 서버 사이의 해시 공간)의 크기를 균등하게 유지하는 게 불가능하기 때문
2. 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장되도록 하는 방법
   -> 1번 문제로 인해 파티션의 크기가 매우 넓은 공간이 생길 경우, 해당 공간에 키가 몰려 하나의 서버에만 집중될 수 있기 때문

그리하여 이 문제를 또 다시 해결할 수 있는 가상 노드 또는 복제라 불리는 기법이 생겨났다.

 

가상 노드

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

아래의 그림으로 보게 된다면 s0으로 시작하는 s0 소속의 가상 노드들과, s1으로 시작하는 s1 소속의 가상 노드들이 있다.

 

가상 노드의 개수를 늘리면 늘릴수록 키의 분포는 당연히 더 균등해진다.

그러나 가상 노드 데이터를 저장할 공간이 더 많이 필요해질 것이므로, 시스템 요구사항에 맞도록 개수는 적당히 조절할 필요가 있다.

 

 

안정 해시의 이점

• 서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화됨
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉬움
• 핫스팟 키 문제를 줄일 수 있음
  특정한 샤드에 대한 접근이 지나치게 빈번하면 서버 과부하 문제가 생길 수 있는데, 이를 방지

참고 블로그
https://dewble.tistory.com/entry/consistent-hash-architecture