5장 안정 해시 설계

이번장에서 이야기 할 주제는 안정 해시 설계입니다. 해시 키를 재 배치하는 문제에 대해서 알아볼 것입니다. 수평적 규모 확장을 하기 위해 데이터를 서버에 균등하게 나누는 것인데,  데이터를 서버에 균등하게 나누었을 때 서버의 변화에 따라 생기는 문제에 대한 내용입니다.

서버를 분산했을 때 임의의 데이터를 어떤 서버에 배치시킨다고 할 때 그 데이터를 대표하는 키를 만들고 키에 모듈러 연산을 수행하여 데이터를 해당 서버로 넣습니다. 이 방법이 가장 간단한 방법인데, 간단한 방법이지만, 안타깝게도 서버의 수가 변경한다면 모듈러 연산의 분모가 변경되므로 전반적인 데이터가 저장될 데이터가 변경되게 됩니다. 캐시미스가 많이 발생할 것이고, 이는 감당하기 힘든 문제입니다. 안정해시는 이 문제를 아름답게 해결합니다.

안정해시란 키와 서버를 모두 해시 공간에 두는 것으로 시작합니다. 이전, 모듈러 연산인 경우 서버만 해시 공간에 둔 것입니다. 키를 해시 공간에 두게 되면 키와 해시 서버를 1:1 매핑할 수 있고, 서버가 변경된 경우에 키와 서버를 1:1 매핑 하는 해당 로직에 따라, 삭제되거나 추가되는 변경된 서버만 업데이트 할 수 있습니다. 

 

키와 서버를 해시공간에 놔둘 시 1:1 매핑하는 방식은 해당 키의 위치로부터 시계 방향으로 링을 탐색해 만나는 첫 번 째 서버라고 정의 합니다. 서버가 추가 되는 경우에 해당 서버와 매핑 되는 키는 서버의 반시계 방향 키입니다. 아래 그림 예에서 s1에는 데이터가 저장되지 않을 것입니다. 기존 데이터만 유지하고 있을 것 입니다.

서버제거시 새로 들어오는 데이터에 해당 키에 매핑되는 경우는 s2로 저장될 것입니다. 이로써 우리는 모듈러 연산보다 훨씬 더 아름다운 방식으로 서버 변경에 대응 할 수 있습니다.

아쉽게도, 이러한 방식의 문제 또한 있는데, 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는게 불가능 하다는 점입니다. 서버를 삭제하였을 경우 그 서버가 파티션하고 있는 (균등하게) 되는 부분이 깨집니다. 그리고, 서버가 삭제되는 경우 어떤 서버는 과도하게 특정 키들에 대한 값을 저장하고 있을 것이고, 서버가 추가되는 경우, 어떤 서버는 과도하게 유휴상태로 있을 것입니다. 이러한 상황을 두고 파티션 크기가 균등하지 않게 되었다. 그리고 키의 균등분포가 깨졌다. 라고 할 수 있습니다.

이러한 방법을 우아하게 해결하는 방법은 해시공간에 물리적 서버를 둘 때 논리적으로 분산하여 여러대의 논리적 서버로 해시공간에 흩뿌리는 방법입니다. 이 논리적 서버를 두고 가상노드라고 합니다. 100~200개의 가상노드를 사용하는 경우 10%~5%의 표준편차를 가집니다. 더 많은 가상노드를 두는 것이 바람직하겠지만, 서버 하나에 대한 가상 노드 데이터를 저장할 공간이 늘어나는 trade off가 생기게 됩니다. 하지만, 적어도 100~200개를 두는 것이 바람직 한 것을 알 수 있습니다.

 

이번 장에서는 안정해시의 필요성을 알 수 있었습니다. 서버가 추가되거나 삭제될때 재배치 되는 키의 수를 최소화하며, 데이터가 균등하게 분포하므로 수평적 규모 확장성을 달성하기 쉬웠습니다. 그리고 핫스팟 키 문제를 줄일 수 있습니다. 특정 샤드에 대한 접근을 지나치게 빈번하게 몰리는 문제를 우아하게 해결할 수 있습니다.

감사합니다.