일관된 해싱 원리 쉽게 이해하기: 서버 추가 시 키 이동을 K/N으로 줄이는 링과 가상 노드

핵심 메시지

• 해시값을 서버 대수로 나눈 나머지로 담당 서버를 정하면, 서버가 한 대만 늘어도 거의 모든 키의 주소가 바뀐다.
• 일관된 해싱은 키와 서버를 모두 크기가 고정된 해시 공간, 즉 링 위에 올려 서버 대수를 계산식에서 빼버린다.
• 각 키는 링을 시계 방향으로 돌다 처음 만나는 서버가 담당하므로, 서버를 추가해도 새로 생긴 구간의 키만 주인이 바뀐다.
• 서버를 한 지점씩만 올리면 담당 구간의 크기가 들쭉날쭉해지므로, 서버마다 여러 개의 가상 노드를 흩어 놓아 부하를 고르게 만든다.
• 가상 노드 개수를 조절하면 성능이 좋은 장비에 더 많은 부하를 자연스럽게 배분할 수 있다.

쉽게 이해하기

여러 대의 서버에 데이터를 나눠 저장할 때 가장 먼저 떠오르는 방법은 키의 해시값을 서버 대수로 나눈 나머지를 주소로 쓰는 것이다. 코드 한 줄이면 되고 키도 고르게 퍼진다. 문제는 서버 대수가 바뀌는 순간에 드러난다. 네 대에서 다섯 대로 늘리면 나누는 수가 달라져 거의 모든 키가 다른 서버를 가리키게 되고, 장비 한 대를 추가한 대가로 저장해둔 데이터의 주소가 통째로 무효가 된다.

일관된 해싱은 계산식에서 서버 대수를 아예 빼는 방식으로 이 문제를 푼다. 키를 0부터 서버 수 직전까지의 범위가 아니라 크기가 고정된 큰 해시 공간에 대응시키고, 그 공간을 양 끝이 이어진 링으로 그린다. 서버도 이름을 해시해 같은 링 위에 올린다. 담당 규칙은 단순하다. 각 키는 링을 시계 방향으로 따라가다 처음 만나는 서버의 것이다. 이렇게 하면 링은 서버 하나당 하나의 호(arc)로 나뉘고, 링의 모양은 서버가 몇 대인지와 무관하게 유지된다.

서버를 추가하면 새 서버의 이름이 링 어딘가에 놓이면서 기존 이웃이 맡던 영역 안에 새로운 구간이 생긴다. 주인이 바뀌는 키는 그 구간 안에 있는 것뿐이고, 나머지는 그대로다. 평균적으로 전체 키 K개 중 K/N개, 즉 서버 한 대분만 이동한다. 서버를 제거할 때도 대칭적으로 작동해, 사라진 서버의 구간이 시계 방향으로 다음 서버에 흡수될 뿐 나머지 클러스터는 아무 영향을 받지 않는다. 장비가 죽거나 점검을 위해 트래픽을 뺄 때도 이웃 한 대만 부담을 넘겨받는다.

다만 서버마다 링 위에 점을 하나씩만 찍으면 담당 구간의 크기가 무작위로 정해져 어떤 서버는 아주 넓은 구간을, 어떤 서버는 좁은 구간을 맡게 된다. 해시가 고르더라도 부하는 고르지 않은 것이다. 해법은 서버 하나를 링 위 여러 위치에 배치하는 가상 노드다. 같은 서버가 작은 구간을 여러 개 나눠 맡게 되면 뽑기를 여러 번 하는 셈이어서 합계가 평균에 수렴한다. 덤으로 성능이 좋은 장비에는 가상 노드를 더 많이 배정해 더 큰 몫을 맡길 수도 있다.

영상은 이 아이디어를 시스템 설계 전반에 통하는 원칙으로 정리한다. 나머지 연산 방식은 배치 규칙 안에 서버 대수라는 숫자를 박아 넣었기 때문에 그 숫자가 바뀔 때마다 모든 것이 흔들린다. 일관된 해싱은 그 숫자를 좌표계 밖으로 밀어낸다. 어떤 값이 바뀔 때마다 시스템이 깨진다면, 그 값을 설계 안에 인코딩하는 일을 멈추라는 것이 핵심 교훈이다.

주요 인사이트

• 일관된 해싱의 이점은 '더 고르게 분배한다'가 아니라 '변화의 영향 범위를 좁힌다'는 데 있다. 분배 자체는 나머지 연산도 충분히 고르게 해낸다.
• 가상 노드는 편차를 줄이는 장치이자 이질적인 장비를 한 클러스터에 섞을 수 있게 하는 장치다. 노드 수라는 하나의 손잡이로 부하 비중을 조절할 수 있다.
• 서버 제거가 추가와 대칭으로 동작한다는 점은 장애 대응 설계에서 특히 중요하다. 한 대가 죽어도 그 이웃만 영향을 받으므로 전체 캐시가 동시에 비워지는 사태를 피할 수 있다.
• 설계에서 바뀌는 숫자를 규칙 안에 넣지 말라는 원칙은 해싱을 넘어 여러 분산 시스템 설계에 반복해서 등장한다.

자주 묻는 질문

관련 AI 소식