[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 5. 안정 해시 설계

안정 해시는 요청이 들어왔을때 이를 균등하게 작업 서버로 나누기 위한 방법이다. 요청을 균등하게 나누기 위해서 고려해야 하는 사항과 안정해시 알고리즘 등을 정리한다.

1. 해시 키 재배치 문제

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

인덱스 = hash(key) % N // (서버의 개수 N)

이 방법은 서버 풀 (server pool) 의 크기가 고정되어 있고 데이터의 분포가 균등할 때는 잘 동작한다. 하지만 서버의 추가, 삭제가 발생하거나 데이터의 분포가 특정 서버로 몰리는 경우에는 문제가 된다.

- 안정 해시 (Consistent hash)

안정 해시는 해시 테이블의 크기가 고정될 때, 평균적으로 k/n 개의 키만 재배치하는 해시 기술이다. 이때 k는 키의 개수이고, n은 슬롯의 개수이다.

 

해시 함수로 저장하는 공간을 0 ~ n 까지 있다고 하자. 이때 해시 공간의 양쪽을 구부려서 양 끝을 맞닿게 하면 해시 링이 만들어진다. 이 해시 링 위에는 각 데이터에 해시 함수를 적용하여 만든 해시 키와 서버의 위치를 배치시킬 수 있다.

 

데이터의 해시 키와 서버를 배치시킨 후에는 각 데이터가 저장될 서버의 위치 조회, 서버의 추가 제거에 따른 키 재배치 등을 해시 링 위에서 수행할 수 있다.

 

각 데이터가 저장되는 서버는 해시 키의 위치로부터 시계 방향으로 탐색하여 만나는 첫번째 서버가 된다. 서버가 추가되어 해시 링 위의 특정 위치에 배치되면 추가된 서버의 위치에서 시계 반대 방향으로 탐색해서 다음 서버를 만나기 전까지 조회되는 키들에 대해서만 새로운 서버로 재배치하면 된다. 반대로 서버가 제거되면 시계 반대 방향으로 탐색해서 만나는 키들을 시계 방향으로 탐색해서 만나는 서버로 재배치하면 된다. 이를 통해서 서버의 모든 키를 재배치하지 않도록 서버의 추가, 제거가 동작한다.

- 문제점

이러한 안정 해시 알고리즘은 두가지 문제점이 있다. 첫번째는 서버가 추가 삭제되는 과정에서 키가 배치되는 파티션의 크기가 균등하게 유지되지 않는 다는 것이다. 두번째는 키가 균등하게 분포되지 않을 수 있다는 것이다. 이러한 문제를 해결하기 위해 제안된 기법이 가상 노드 (virtual node) 또는 복제 (replica) 라 불리는 기법이다.

- 가상 노드

가상 노드는 실제 노드 또는 서버를 가리키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. 데이터는 안정 해시에서와 같이 시계방향으로 탐색하며 처음 만난 가상 노드를 가지는 서버에 저장된다.

 

링 위에 여러개의 가상 노드를 분산하여 배치하여 파티션을 분리함으로 데이터의 뷸균형을 해결하는 방법이다. 가상 노드의 개수가 많을수록 더 잘개 파티션이 분리되고 키의 분포는 더욱 균등해진다. 그러나 무작정 가상 노드를 늘리면 가상 노드를 저장할 공간이 많이 필요해지기 때문에 이에 대한 trade-off 가 필요하다.