개요
수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 분배하는 것이 중요하다. 다음의 해시 키 재배치 문제를 살펴보고, 안정 해시 기술을 통해 어떻게 이러한 목표를 달성하는지 알아보자.
해시 키 재배치(rehash) 문제
N개의 캐시 서버가 있을 때, 서버에 부하를 균등하게 나누기 위해 보편적으로 모듈러 해시 함수를 사용한다.
이와 같이 데이터를 분산하여 저장할 때, 서버 풀(pool)의 크기가 고정되어 있다면 잘 동작하지만 서버가 추가되거나 기존 서버를 삭제하는 경우 문제가 발생한다.
위 예시에서 서버 수를 1개만큼 줄이면,
이와 같이 장애가 발생한 1번 서버에 저장된 키 뿐만 아니라 대부분의 키가 재분배 될 것이다. 그렇게 된다면 캐시된 데이터 역시 대규모 캐시 미스가 발생하게 될 것이다. 이러한 문제를 해결할 수 있는 방법이 안정 해시이다.
안정 해시
안정 해시
안정 해시는 해시 테이블의 크기가 조정될 때 평균적으로 k(키의 수)/n(슬롯의 수)개의 키만 재배치하는 해시 기술이다.
해시 공간과 해시 링
해시를 적용하기 위해 해시 함수를 적용하면, 그 결과의 범위는 x0 ~ xn이라고 할 수 있을 것이다. 이러한 값을 가지는 해시 공간을 그림으로 표현하면 아래와 같다.
이러한 해시 공간을 양쪽을 이어붙이면 아래와 같은 해시 링을 만들 수 있다.
해시 서버
이러한 해시 링 위에 서버를 배치하면
이처럼 배치할 수 있을 것이다.
해시 키
이렇게 배치된 서버들에 키를 배치할 때, 해시 함수를 통해 얻은 해시 키 값을 다음과 같이 표현될 것이다.
서버 조회
이렇게 배치된 특정 해시 키는 해당 키의 위치부터 시계 방향으로 링을 탐색하다가 만나는 첫 번째 서버에 저장한다.
서버 추가
만약 s4라는 새로운 서버가 추가된다면, 해시 링 위의 키들 중 일부만 재배치 하면 된다.
서버 제거
반대로 서버를 제거할 때는, 제거한 서버에 저장된 키들만 재배치하면 된다.
안정 해시 문제점
안정 해시는 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치하고, 키의 위치에서 링을 시계 방향으로 탐색할 때 만나는 가장 첫 서버에 키를 저장하는 방식이다.
하지만 안정 해시 알고리즘에는 두 가지 문제가 있다.
첫 번째로는 서버가 추가되거나 삭제되는 상황을 감안했을 때, 파티션(partition)의 크기를 균등하게 유지하는 것이 불가능하다는 것이다. 서버가 추가된다면 특정 서버는 작은 해시 공간을 할당 받을 수 있고, 반대로 제거된다면 인접한 서버가 큰 해시 공간을 할당 받게 된다.
두 번째 문제는 해시 함수를 통해 얻는 키의 균등 분포(uniform disttribution)를 달성하기 어렵다는 점이다. 아래와 같이 키가 배치된다면 s0와 s2 서버에만 키가 저장될 것이다.
가상 노드
안정 해시의 문제점을 해결하기 위한 기법이 가상 노드(vitrual node) 혹은 복제(replica)라고 불리는 기법이다.
가상 노드는 실제 노드 혹은 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 가상 노드를 가질 수 있다.
위 그림처럼 서버를 s0 하나만 사용하는 것이 아니라 s0_0, s0_1, s0_2 세 개의 가상 노드를 사용한다. 각 서버는 이처럼 하나가 아닌 여러 개의 파티션을 관리하는데, 마찬가지로 키 배치 시 시계 방향으로 탐색하다 만나는 가상 노드 서버가 키를 관리한다.
해시 링 위에 가상 노드의 수를 늘릴수록 키의 분포는 점점 균등해진다. 데이터가 얼마나 퍼져있는지를 나타내는 표준 편차가 점점 작아지고, 100~200개의 가상 노드를 사용하면 표준편차는 평균의 5~10% 사이로 유지된다. 다만 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 되니, tradeoff를 잘 고려해 시스템 요구사항에 맞도록 가상 노드 개수를 적절히 조정해야할 것이다.
결론
이번 장을 통해 안정 해시 설계 방법을 알게 되었는데, 안정 해시의 이점은 다음과 같다.
•
서버가 추가되거나 삭제될 때 재배치되는 키의 수가 최소화된다.
•
데이터 분포를 균등하게 나눌 수 있기 때문에 수평적 규모 확장성을 달성하기 쉽다.
•
특정한 샤드(shard)에 대한 접근이 지나치게 빈번한 핫스팟(hotspot) 키 문제를 줄일 수 있다.
이러한 안정 해시는 다음과 같이 사용되고 있다.
•
아마존의 DynamoDB의 파티셔닝 관련 컴포넌트
•
아파치 카산드라(Cassandra) 클러스터에서의 데이터 파티셔닝
•
디스코드(Discord) 채팅 애플리케이션
•
아카마이(Akamai) CDN
•
매그레프(Meglev) 네트워크 부하 분산기