5장 안정 해시 설계

안정 해시(Consistent hash)란?

수평적 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 보편적으로 사용되는 기술이다.
안정 해시 기술이 풀려고 하는 문제를 알아보자.

 

해시 키 재배치(rehash) 문제

 

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

 

serverIndex = hash(key) % N (N은 서버의 개수이다.)

주어진 각각의 키에 대해서 해시 값과 서버 인덱스를 계산한 예제 & 키 값이 어떻게 분산되는지 보여주는 그림

서버 풀(Server poll)의 크기가 고정되어 있을 때, 그리고 데이터 분포가 균등할 때는 잘 동작한다.

 

하지만 서버가 추가되거나 기존 서버가 삭제되면 키가 균등하게 분포되지 않는 문제가 발생한다. 

1번 서버를 삭제하고 기존 해시 함수로 대응했을때 발생하는 문제점 (균등하지 않음) => 대규모 캐시 미스(cache miss)

 

안정 해시

위키피디아에 따르면 "안정 해시(consistent hash)는
해시 테이블 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술이다.
여기서 k는 키의 개수, n은 슬롯(slot)의 개수이다.
이와는 달리 대부분의 전통적 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분 키를 재배치한다."

해시 공간과 해시 링

해시 함수 f로는 SHA-1을 사용, 그 함수의 출력 값 범위는 x0, x1, x2, x3, ... xn과 같다고 하자.

SHA-1의 해시 공간(hash space) 범위는 0부터 2¹⁶⁰-1까지라고 알려져 있다.

따라서 x0는 0, xn은 2¹⁶⁰-1이며, 나머지 x1부터 xn-1까지는 그 사이의 값을 가진다.

해시 공간을 그림으로 표현하고 양쪽을 구부려 접어 해시 링(hash ring)을 만든 모습

해시 서버 & 해시 키

기존 나머지(modular) 연산 %는 사용하지 않는 해시 함수이다.

해시 함수 f를 사용해 서버 IP나 이름을 링 위의 어떤 위치에 대응 시킬 수 있다.

캐시할 키 key0, key1, key2, key3 또한 해시 링 위의 어느 지점에 배치할 수 있다.

 

서버 조회 & 서버 추가 & 서버 제거

 

• 서버 조회
  • 어떤 키가 저장되는 서버는 해당 키의 위치로 부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버다.
  • 첫 번째 그림은 해당 과정을 보여준다.
• 서버 추가
  • 서버 4가 추가되어 k0 - s0이 mapping 되었던 것이 k0 - s4로 mapping 되었다.
  • 두 번째 그림은 서버가 추가되는 과정을 보여준다.
• 서버 제거
  • 하나의 서버가 제거되면 키 가운데 일부만 재배치된다. / 서버 1이 삭제되었을 때 key1만이 서버 2로 재배치 됨
  • 세 번째 그림은 서버가 삭제되는 과정을 보여준다.

 

기본 구현법의 두 가지 문제

MIT에서 처음 제안된 안정 해시 알고리즘은 다음과 같은 절차를 가진다.

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

 

이 접근법에는 두 가지 문제가 있다.

 

첫 번째

서버가 추가되거나 삭제되는 상황을 감안하면 파티션(partition)의 크기를 균등하게 유지하는 게 불가능하다는 것
파티션은 인접한 서버 사이의 해시 공간이다. / 서버 별로 할당되는 해시 공간의 크기가 다른 상황이 발생

s1이 삭제되어 s2의 파티션이 다른 파티션 대비 거의 두 배로 커지는 상황

 

 

두 번째

키의 균등 분포(uniform distribution)를 달성하기 어렵다.

서버1과 서버 3은 아무 데이터도 갖지 않지만 대부분의 키를 서버2가 보관하는 상황

 

가상 노드 (virtual node) / 복제 (replica)

위 두 가지 문제를 해결하기 위해 나온 방안이다.

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

 

s0 - 서버 0이 관리하는 파티션 / s1 - 서버 1이 관리하는 파티션

첫 번째 그림은 가상 노드를 배치하는 예이다

s0과 s1은 각각 3개의 가상 노드를 가지고 각 서버는 하나가 아닌 여러 개 파티션을 관리해야 한다.

(실제 시스템에서는 3보다 훨씬 큰 값이 사용된다.)

 

두 번째 그림은 가상 노드와 키의 탐색에 관련한 예이다.

키의 위치로부터 시계방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버가 된다.

k0가 저장되는 서버는 k0의 위치로부터 링을 시계방향으로 탐색하다 만나는 최초의 가상 노드 s1_1 즉 서버 1이다.

 

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해진다.
표준 편차(standard deviation)가 작아져서 데이터가 고르게 분포되기 때문이다.
표준 편차는 데이터가 어떻게 퍼져 나갔는지를 보이는 척도다.
가상 노드의 개수를 늘리면 표준 편차 값은 떨어지나 가상 노드 데이터를 저장할 공간이 더 많이 필요하다.
시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정하는 타협적 결정(tradeoff)가 필요하다.

 

재배치할 키 결정

서버가 추가되거나 제거되면 데이터 일부는 재배치해야 한다.
어느 범위의 키들이 재배치되어야 할까?
새로 서버가 추가되거나 삭제되는  반시계 방향에 있는 첫 번째 서버 까지 재배치 하여야 한다.

서버가 추가되거나 삭제되면 키가 재배치 되는 기준

 

마치며

안정 해시가 왜 필요하며 어떻게 동작하는지 알아보았다.

 

안정 해시의 이점

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

실제로 사용되는 유명한 안정 해시

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

 

---

참고 포스팅 및 문헌

 

가상 노드 개수와 표준 편차의 상관관계

 

 

Java HashMap은 어떻게 동작하는가?

 

 

https://velog.io/@dev-log/%EC%95%88%EC%A0%95-%ED%95%B4%EC%8B%9C-%EC%84%A4%EA%B3%84Consistent-hashing

안정 해시 (Consistent hashing)