대규모 시스템 설계 스터디 05. 안정 해시

분산 캐시나 분산 데이터베이스에서는 데이터를 여러 서버에 나누어 저장합니다. 이때 중요한 질문이 생깁니다. “어떤 키를 어떤 서버에 저장할 것인가”입니다.

단순한 방법은 hash(key) % N입니다. 하지만 서버 수가 바뀌면 대부분의 키가 다른 서버로 이동하는 문제가 생깁니다. 캐시에서는 이 문제가 캐시 미스로 이어지고, 데이터 저장소에서는 대규모 데이터 이동으로 이어질 수 있습니다.

5장은 이 문제를 안정 해시로 해결하는 방법을 다룹니다. 해시 링을 만들고, 서버와 키를 같은 링 위에 배치하고, 가상 노드로 데이터 쏠림을 줄이는 흐름입니다.

먼저 알아야 할 기본 용어

용어	뜻
키	데이터를 찾기 위한 식별자입니다. 사용자 ID, 세션 ID, 캐시 키가 예시입니다.
해시 함수	입력값을 고정된 숫자 범위의 값으로 바꾸는 함수입니다. 같은 입력은 항상 같은 결과를 냅니다.
나머지 연산	어떤 수를 N으로 나누고 남은 값을 구하는 연산입니다. hash(key) % N에서 %가 나머지 연산입니다.
노드	데이터를 저장하거나 요청을 처리하는 서버 한 대를 뜻합니다.
샤드	데이터를 나누어 저장한 조각 또는 그 조각을 담당하는 저장소입니다.
키 재배치	서버 추가나 삭제 때문에 키가 담당 서버를 바꾸는 과정입니다.
캐시 미스	캐시에 기대한 데이터가 없어 원본 저장소로 다시 조회해야 하는 상황입니다.
해시 링	해시 값의 범위를 원처럼 이어 붙인 구조입니다. 안정 해시에서 서버와 키를 배치하는 공간입니다.
가상 노드	실제 서버 하나를 해시 링 위 여러 위치에 배치하기 위해 만든 가짜 노드입니다.

나머지 연산 해시는 서버 수가 바뀔 때 크게 흔들립니다

가장 직관적인 분산 방식은 다음 공식입니다.

serverIndex = hash(key) % N

N은 서버 수입니다. 서버가 4대라면 결과는 0, 1, 2, 3 중 하나가 됩니다. 각 키는 이 결과에 따라 특정 서버로 갑니다.

서버 수가 고정되어 있으면 이 방식은 단순하고 잘 동작합니다. 문제는 서버 수가 바뀌는 순간입니다.

기존: hash(key) % 4
변경: hash(key) % 3

같은 키라도 4로 나눈 나머지와 3으로 나눈 나머지는 대부분 다릅니다. 서버 한 대를 제거했을 뿐인데 많은 키가 다른 서버로 이동합니다.

캐시 시스템에서는 키가 다른 서버로 이동하면 기존 캐시를 찾지 못합니다. 캐시 미스가 늘고, 원본 데이터베이스로 요청이 몰립니다. 서버를 늘려 성능을 높이려 했는데 오히려 장애 위험이 커질 수 있습니다.

안정 해시는 키가 움직이는 범위를 줄입니다

안정 해시는 서버 수가 바뀌어도 가능한 한 적은 키만 이동하게 만드는 방식입니다. 핵심 아이디어는 해시 공간을 원처럼 보는 것입니다.

먼저 해시 함수가 만들 수 있는 전체 값의 범위를 생각합니다. 예를 들어 SHA-1은 매우 큰 숫자 범위의 해시 값을 만듭니다. 이 숫자 범위의 시작과 끝을 이어 붙이면 원이 됩니다. 이것이 해시 링입니다.

0 ---------------------- 최대 해시값
|                        |
+-------- 해시 링 --------+

그다음 서버와 키를 같은 링 위에 배치합니다. 서버 이름이나 IP를 해시해서 링 위 위치를 정합니다. 키도 해시해서 링 위 위치를 정합니다.

규칙은 하나입니다.

키 위치에서 시계 방향으로 이동했을 때 처음 만나는 서버가 그 키를 담당합니다.

예를 들어 keyA가 server1과 server2 사이에 있다면, 시계 방향으로 처음 만나는 server2가 keyA를 담당합니다.

서버를 추가해도 일부 키만 이동합니다

안정 해시의 장점은 서버 추가와 삭제 상황에서 드러납니다.

server4를 새로 추가한다고 가정하겠습니다. server4는 해시 링 위의 한 지점에 배치됩니다. 그러면 server4 바로 앞 구간에 있던 일부 키만 server4로 이동합니다. 나머지 구간의 키는 기존 서버에 그대로 남습니다.

서버를 제거할 때도 비슷합니다. server1을 제거하면 server1이 담당하던 구간의 키만 시계 방향 다음 서버로 이동합니다. 다른 서버가 담당하던 키는 그대로입니다.

단순 나머지 해시는 서버 수 N이 바뀌면 전체 키의 상당수가 다시 배치됩니다. 안정 해시는 변경된 서버 주변 구간의 키만 움직입니다.

이 차이가 분산 캐시에서는 매우 중요합니다. 서버 추가나 삭제가 캐시 전체를 흔들지 않고, 일부 구간의 캐시 미스로 제한되기 때문입니다.

기본 해시 링은 데이터 쏠림 문제가 생길 수 있습니다

해시 링만으로 모든 문제가 끝나지는 않습니다. 실제 서버가 링 위에 몇 개만 배치되면 구간 크기가 불균등해질 수 있습니다.

예를 들어 서버 4대가 링 위에 있는데, 우연히 server2가 매우 넓은 구간을 담당하게 될 수 있습니다. 그러면 전체 키의 많은 부분이 server2로 몰립니다.

이 문제는 두 가지로 나타납니다.

문제	설명
파티션 불균등	서버별 담당 구간 크기가 달라집니다.
키 쏠림	특정 서버에 키와 요청이 과도하게 몰립니다.

파티션은 나뉜 구간을 뜻합니다. 키가 균등하게 분포하지 않으면 어떤 서버는 바쁘고 어떤 서버는 거의 놀게 됩니다. 분산 시스템을 만들었는데 부하 분산이 제대로 되지 않는 상황입니다.

가상 노드는 링 위의 분포를 더 고르게 만듭니다

가상 노드는 실제 서버 하나를 링 위 여러 지점에 배치하는 방법입니다.

server0 -> server0-0, server0-1, server0-2
server1 -> server1-0, server1-1, server1-2
server2 -> server2-0, server2-1, server2-2

각 가상 노드는 링 위에서 독립된 위치를 가집니다. 키는 시계 방향으로 처음 만나는 가상 노드에 배정되고, 그 가상 노드가 가리키는 실제 서버가 데이터를 담당합니다.

가상 노드가 많아지면 각 실제 서버가 링 위 여러 구간을 나누어 갖습니다. 한 구간이 조금 커도 다른 구간에서 보정될 가능성이 커집니다. 결과적으로 서버별 키 분포가 더 균등해집니다.

트레이드오프도 있습니다. 가상 노드가 많을수록 분포는 좋아지지만, 링 정보를 저장하고 관리하는 비용이 늘어납니다. 그래서 시스템 규모와 운영 비용을 고려해 적정 개수를 정합니다.

안정 해시는 캐시와 데이터 파티셔닝에 자주 쓰입니다

안정 해시는 특정 알고리즘 하나를 외우기 위한 주제가 아닙니다. 서버 추가와 삭제가 잦은 분산 시스템에서 데이터 이동을 줄이기 위한 기본 도구입니다.

대표적인 사용처는 다음과 같습니다.

사용처	안정 해시가 필요한 이유
분산 캐시	서버 증설이나 장애 시 캐시 미스를 최소화합니다.
분산 키-값 저장소	키를 여러 노드에 나누어 저장합니다.
데이터 파티셔닝	데이터가 특정 서버에 몰리지 않게 분배합니다.
로드밸런싱	요청을 여러 백엔드에 안정적으로 분산합니다.

Amazon DynamoDB, Apache Cassandra, Akamai CDN 같은 대규모 시스템에서도 안정 해시 계열의 아이디어가 사용됩니다. 세부 구현은 다르지만, 서버 변화에 따른 데이터 이동을 줄인다는 목표는 같습니다.

핵심은 서버 변화가 전체 데이터를 흔들지 않게 하는 것입니다

5장의 핵심은 다음과 같습니다.

개념	정리
hash(key) % N	단순하지만 서버 수 N이 바뀌면 많은 키가 이동합니다.
해시 링	서버와 키를 같은 원형 해시 공간에 배치합니다.
안정 해시	서버 추가와 삭제가 일부 구간의 키에만 영향을 주게 합니다.
가상 노드	서버별 담당 구간을 더 균등하게 만듭니다.

안정 해시는 “어느 서버에 저장할지”를 정하는 기술입니다. 동시에 “서버가 바뀔 때 얼마나 많은 데이터를 다시 움직일지”를 줄이는 기술입니다.

분산 시스템에서는 서버가 추가되고, 제거되고, 장애가 납니다. 안정 해시는 그 변화가 전체 시스템을 흔들지 않도록 영향 범위를 제한합니다.

다음 단계에서는 이 개념이 키-값 저장소, 캐시, 데이터 파티셔닝 같은 더 큰 설계 문제 안에서 어떻게 재사용되는지 확인할 수 있습니다.