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

안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

해시 키 재배치(rehash) 문제

N개의 캐시 서버가 있을 때, 부하를 균등하게 나누는 보편적 방법은 해시 함수를 사용하는 것이다.

1

serverIndex = hash(key) % N

총 4대의 서버를 사용한다면, 주어진 각각의 키에 대해 아래와 같이 계산될 수 있다.

키 값을 해싱한 값에 나머지 연산을 하여 저장될 서버가 결정된다.

이 방식은 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때 잘 동작한다.

하지만 서버가 추가되거나, 기존 서버가 삭제되면 나머지 연산 결과 값이 변하기 때문에 문제가 발생한다.

따라서 아래와 같은 형태로 키의 분포가 바뀐다.

장애가 발생한 1번 서버에 보관되어 있는 키 뿐만 아닌 대부분의 키가 재분배되어, 대부분 캐시 클라이언트가 데이터가 없는 서버에 접속하게된다.

이로 인해 대규모 캐시 미스가 발생하게되는데, 안정 해시는 이러한 문제를 효과적으로 해결하는 방식이다.

안정 해시

안정 해시는 해시 테이블 크기가 조정될 때 평균적으로 k/n개의 키만 재비치하는 해시 기술이다.

• k: 키의 개수
• n: 슬롯의 개수

이와는 달리 대부분의 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다.

해시 공간과 해시 링

• SHA-1 해시함수를 사용하며, 출력 값의 범위는 x0, x1 ... xn이라고 가정한다.
• SHA-1의 해시 공간(hash space) 범위는 0 부터 2^160 - 1 까지라고 알려져 있다.

따라서 x0 = 0, xn -1 = 2^160 - 1이며, 두 수 사이의 값을 갖게 된다.

이 해시 공간의 양쪽을 연결하변 해시 링이 만들어진다.

해시 서버

해시 함수 f를 사용하면 서버(IP, 이름 등)를 링 위의 어딘가에 대응시킬 수 있다.

해시 키

안정 해시에서 사용되는 해시 함수는 전통적인 해시 키 방식에서 언급된 방식과 다르며, 만들어질 수 있는 모든 해시 공간 x0 ... xn을 연결한 형태이므로 나머지 연산을 사용하지 않는다.

캐시할 키 또한 서버와 함께 해시 링 위의 어느 지점에 배치할 수 있다.

서버 조회

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

따라서 k0는 s0 에 저장된다.

서버 추가

키가 저장되는 서버가 키의 위치로부터 시계 방향으로 링을 돌면서 만나는 첫 서버이므로, 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.

위 그림처럼 s4가 추가되면, k0만 재배치하면 되며, 나머지 키들은 같은 서버에 남게된다.

• k0가 만나는 첫 서버가 s4로 바뀌기 때문

서버 제거

마찬가지로 한 서버가 제거되면 키 일부만 재배치된다.

• s1이 삭제되었을 때 k1의 첫 서버만 s2로 바뀌므로 k1만 s2로 재배치된다.

기존 구현법의 두 가지 문제

안정 해시 알고리즘은 MIT에서 처음 제안되었는데, 기본 절차는 아래와 같다.

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

안정 해시는 근본적으로 최소한의 추가/삭제에 대해 최소한의 재배치를 고려한다. 따라서 이러한 방식에는 두 가지 문제가 발생한다.

파티션 크기 문제

서버가 추가되거나 삭제되는 상황을 감안하면 사용하더라도 파티션의 크기를 균등하게 유지하는 게 불가능하다.

• 파티션의 크기는 시계 방향으로 제일 가까운 서버 사이와의 거리만큼의 해시 공간으로, 서버의 해시 공간이 균등하지 않다.
  • 추가 삭제될 때 시계 방향으로 제일 가까운 서버에 키들이 집중된다.

키의 균등 분포 문제

균등 분포 해시 함수는 충돌을 최소화하며 입력 키들이 해시 공간 전체에 고르게 분포되어 특정 영역에 물리지 않도록 구현되지만 완전하지는 않다.

• 데이터의 비균등한 본질:
  • 실제 데이터는 해시 함수의 이상적인 균등 분포를 따르지 않을 수 있다.
  • 특정 패턴이나 값들이 특정 해시 영역에 몰리는 경우가 있다.
• 해시 함수의 한계:
  • 모든 해시 함수는 완벽한 균등 분포를 보장할 수 없다.
  • 특히 입력 키의 분포가 고르지 않을 경우, 해시 값의 분포도 고르지 않을 수 있다.

따라서 키의 균등 분포가 매우 달성하기 어려워 위와 같은 상황이 발생하게된다.

+ 실제 서버의 처리 능력 차이

노드(서버)마다 처리 능력이나 저장 용량이 다를 경우, 파티션 크기의 균등성이 실제 부하의 균등성을 의미하지 않을 수 있다.

가상 노드

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

서버들의 비슷한 해시 공간을 가질 수 있도록 하는 기법으로 해시 링 위에 실제 서버를 가르키는 가상 노드들을 분포시킨 후 가상 노드에 할당되는 해시 영역을 가상 노드가 가르키는 서버가 처리하도록 한다.

• 따라서 각 서버는 하나가 아닌 여러 개의 파티션을 관리해야 한다.

가상 노드의 개수를 늘리면 표준 편차가 작아져 데이터가 고르게 분포되므로, 키위 분포는 점점 더 균등해지지만

가상 노드 데이터를 저장할 공간이 더 많이 필요해지므로, 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정하는 트레이드오프가 필요하다.

재배치할 키 결정

서버가 추가되거나 제거되면 데이터의 일부는 재배치해야 한다.

서버가 추가되었을 때

s4가 추가되었다고 가정하면, 영향을 받는 위는 s4 부터 그 반시계 방향에 있는 s3 까지이다.

따라서 s3 부터 s4 사이에 있는 키들을 s4로 재배치해야한다.

서버가 삭제되었을 때

s1이 삭제되면 s1 부터 그 반시계 방향에 있는 최초 서버 s0 사이에 있는 키들이 s2로 재배치되어야 한다.

마치며

안정 해시의 이점은 다음과 같다.

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

안정해시는 실제로 널리 쓰이는 기술이다.

• 아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
• 아파치 카산드라 클러스터에서 데이터 파티셔닝
• 디스코드 채팅 어플리케이션
• 아카마이 CDN
• 매그레프 네트워크 부하 분산기 등