•
수평적 규모 확장 시, 요청을 균등하게 분배하기 위해서 필요한 기술이다.
•
이 해시 기술이 풀어내야 하는 문제부터 알아보자.
해시 키 재배치 문제
•
N개의 서버가 있을 때, 이 서버들에게 부하를 균등하게 나누는 보편적인 방법은 serverIndex = hashKey % N 해시 함수를 사용하는 것이다.
•
이 방법은 보통 평상시에는 문제가 발생하지 않다가 서버가 추가되거나 삭제되면 문제가 발생한다.
•
재배치 과정에서 기존 해시 함수를 사용하는 경우, 키가 특정 서버에 몰리거나 아예 할당되지 않는 경우도 발생하기 때문에, 안정 해시가 등장했다.
안정 해시
•
안정 해시란 해시 테이블의 사이즈가 조정될 때, 평균적으로 k/n 개의 키만 재배치하는 기술이다.
◦
여기서 k는 키의 갯수이고, n은 슬롯, 서버의 갯수다.
해시 공간과 해시 링
•
해시 함수로 SHA-1을 사용한다고 했을 때, SHA-1의 해시 공간 범위는 0부터 2^160-1이다
•
해시 링의 경우, 해시 공간을 구부려 원형 큐와 같은 형태를 만들었다고 가정하면 이해가 쉽다.
•
이후, 해시 함수를 사용해서 서버의 이름이나, IP에 연산을 가한 결과값을 토대로 이 해시 링 위에 위치시킨다.
•
키 역시 특정 값을 만들어 연산을 가한 후, 결과 값을 해시 링 위에 위치시킬 수 있다.
서버 조회
•
각 키가 저장되는 서버는, 해당 키의 위치로부터 시계 방향으로 링을 탐색해나갈때 처음으로 발견할 수 있는 서버다.
•
이때, 서버 추가와 삭제가 발생하는 경우, 재배치는 특정 key만 재배치되고 나머지는 그대로임이 보장된다.
기본 구현법의 두 가지 문제
•
안정 해시 알고리즘의 기본 절차는 다음을 따른다.
◦
서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치한다.
◦
키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버다.
•
이 접근법은 두 가지 문제를 가진다.
◦
하나는 서버가 추가되거나 삭제되는 상황을 고려했을 때, 파티션의 크기를 균등하게 유지하는 것이 불가능하다는 것이다.
◦
나머지 하나는 키의 균등 분포를 달성하기가 어렵다는 것이다.
•
이런 문제를 해결하기 위해 가상 노드 또는 복제라 불리는 기법을 사용한다.
◦
가상 노드의 경우, 각 노드마다 할당된 파티션의 크기가 너무 크기 때문에, 그 크기를 줄이기 위해 노드를 여럿 할당하여 할당되는 파티션의 사이즈 자체를 줄여, 편차를 줄이는 방법이다.
◦
키의 균등 분포를 위해 키를 재배치할 수 있다.
▪
추가되는 경우, 새로이 추가된 서버와 새로이 추가된 서버에서 반시계 방향으로 탐색을 진행하다 만나는 처음 만나는 서버 사이의 키를 재배치해야 한다.
▪
삭제되는 경우, 삭제되는 서버의 반시계 방향에 있는 최초 서버 사이에 있는 키들이 삭제되는 서버의 시계 방향에 있는 최초 서버에 배치되어야 한다.
마치며
•
안정 해시가 왜 필요한지, 어떻게 동작하는지를 확인하였으며, 안정 해시의 이점은 다음과 같다.
◦
서버가 추가되거나 삭제될 때, 재배치되는 키의 수가 최소화된다.
◦
데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
◦
핫스팟 키 문제를 줄인다. 특정 샤드에 대한 과부하를 안정 해시는 데이터를 좀 더 균등하게 분배하여 이런 문제가 생길 가능성을 줄인다.
•
안정 해시를 사용하는 대표적인 예시는 다음과 같다.
◦
아마존 다이나모 데이터베이스의 파티셔닝 관련 컴포넌트
◦
아파치 카산드라 클러스터에서의 데이터 파티셔닝
◦
디스코드 채팅 어플리케이션
◦
아카마이 CDN
◦
매그레프 네트워크 부하 분산기
