해시
해시 함수란 자료 구조를 공부한 사람이라면 누구나 알고 있는 개념일 것이다.
가장 간단한 해시 함수는 다음과 같다.
key % MOD = value (MOD보다 작은 수)
MOD를 앞으로 슬롯(slot)이라고 칭하자.
우리는 이런 해시 함수를 통해 특정 key를 가진 객체를 특정 위치에 넣어 두고, 한 번에 조회할 수 있다.
이를 통해 시간 복잡도 O(1)을 달성할 수 있다.
하지만 만약 해시 함수의 슬롯 개수가 바뀌게 된다면 어떻게 될까?
해시 키 재배치(rehash) 문제
슬롯이 3이라고 가정해 보자.
이때 key가 4 혹은 6인 경우를 계산해 보면 다음과 같다.
- 4 % 3 = 1
- 6 % 3 = 0
만약 슬롯이 4로 변경된다면?
- 4 % 4 = 0
- 6 % 4 = 2
이전과 결과값이 완전히 달라지게 된다.
이처럼 해시 함수가 변경되면 재배치해야 할 key가 상당히 많아진다는 것을 알 수 있다.
최악의 경우 모든 key를 재배치해야 할 수도 있다.
안정 해시 정렬이란 무엇일까?
앞에서는 해시 함수로 정해지는 value를 단순히 특정 장소라고 표현했지만, 만약 그것이 서버 혹은 DB라면 어떨까?
DB 관점에서 보면, 샤딩을 통해 배치한 데이터들을 거의 모두 재배치해야 한다면 DB 개수를 유연하게 조정할 수 없을 것이다.
DB 개수를 조정할 때마다 엄청난 지연이 발생할 것이기 때문이다.
안정 해시 정렬 알고리즘은 이러한 재배치 문제를 해결하는 데 매우 중요한 알고리즘이다.
안정 해시란 평균적으로 오직 k / n 개의 키만 재배치하는 해시 기술이다.
여기서 k는 키의 개수, n은 슬롯의 개수(예: DB 개수)이다.
전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.
해시 공간과 해시 링
안정 해시의 원리를 살펴보기 전에, 해시 함수의 출력 값 범위를 x0, x1, x2 … xn이라고 해 보자.
이를 일렬로 늘여 표현하면 다음과 같을 것이다.
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
여기서 x0와 xn을 연결하면 링이 완성된다.
그 링은 다음과 같다.
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
이 링 위에 서버를 배치하고 데이터까지 함께 위치시켜 보자.
서버 조회
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
sx는 서버를 의미한다.
kx는 자원을 의미한다.
kx는 sx에 포함되어 있는 자원이다.
만약 특정 k를 조회하고 싶다면, 링을 따라가며 가장 먼저 만나는 서버를 찾아 조회하면 된다.
앞서 안정 해시가 등장한 이유였던, 슬롯 개수가 변경되는 경우를 살펴보자.
서버 추가
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
s3와 s0 사이에 s4를 추가하는 경우,
위와 같이 k0는 s4로 재배치된다.
서버 삭제
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
s1이 삭제되면 k1은 s2로 재배치된다.
하지만 눈치가 빠른 사람이라면, 현재의 안정 해시 방식에 대해 문제를 느꼈을 것이다.
안정 해시에서 발생하는 문제
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
서버가 삭제되는 경우, s0와 s2 사이의 간격은 더 멀어지게 되고, 그에 따라 s2에 더 많은 자원이 몰릴 수밖에 없다.
그렇게 되면 데이터가 몰려 있는 서버가 삭제될 경우, 기존 해싱 방법과 마찬가지로 상당히 많은 key가 재배치될 것이다.
안정 해시는 이러한 문제를 해결하기 위해 등장한 알고리즘이므로, 이 문제 역시 해결해야 한다.
다행히 이를 해결할 수 있는 방법이 존재하는데, 바로 가상 노드이다.
가상 노드
출처 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초
해시 링에서 노드가 사라질수록 각 노드 간의 간격은 점점 멀어지게 된다.
이를 해결하기 위해 서버를 최대한 촘촘하게, 번갈아 가며 해시 링 위에 배치하면 된다.
가상 노드의 개수가 늘어날수록 해시 키의 분포는 점점 더 균등해진다.
하지만 가상 노드가 많아질수록, 가상 노드 정보를 저장하기 위한 공간 역시 더 많이 필요하게 된다.
추후 안정 해시를 사용할 기회가 있다면, 이러한 trade-off를 고려하는 것이 좋다.
