서버 한 대를 추가했더니 캐시가 통째로 사라졌다, 안정 해시(Consistent Hashing) 설계

가상면접 사례로 배우는 시스템 설계 시리즈 08편

개요

캐시 서버가 4대로 운영 중이라고 상상해 보자. 어느 날 트래픽이 늘어 서버를 1대 추가했다. 그런데 갑자기 캐시 적중률이 바닥으로 떨어지고, DB에 읽기 요청이 수십 배로 몰리기 시작한다. 서버를 늘렸는데 왜 시스템은 더 느려지는 걸까.

원인은 hash(key) % N 이다. 이 글은 왜 나머지 연산(Modulo)이 서버 증감 앞에서 붕괴하는지, 그리고 이를 해결하는 안정 해시(Consistent Hashing)가 어떤 원리로 "재배치를 최소화"하는지를 설계 관점에서 설명한다.

1. hash(key) % N의 함정 — 재배치 폭풍

캐시 서버가 4대 있다고 하자. 특정 키가 어느 서버에 저장될지는 보통 이렇게 결정한다.

server_index = hash(key) % 4   // 결과는 0, 1, 2, 3 중 하나

해시 값이 고르게 분포한다고 가정하면 키는 네 서버에 대략 균등하게 나뉜다. 구현은 단순하고 직관적이다. 문제는 서버 수 N이 변하는 순간 터진다.

서버 4대 중 1대가 장애로 죽었다고 해 보자. 라우팅 식은 즉시 hash(key) % 3으로 바뀐다. 그런데 hash(key) % 4와 hash(key) % 3의 나머지는 거의 항상 다르다. 나머지 연산은 "서버 수"가 매핑 기준의 일부로 들어가므로, 서버 수가 바뀌는 순간 매핑 기준 자체가 통째로 바뀐다. 결과적으로 전체 키 중 대부분이 다른 서버로 옮겨가야 하는 상황이 된다. 서버를 새로 한 대 늘리는 경우도 마찬가지다. 4 → 5가 되어도 기준이 바뀌니 같은 일이 벌어진다.

이때 시스템에서 무슨 일이 벌어지는지 순서대로 따라가 보자.

1. 기존 캐시 키의 대부분이 "자기가 어느 서버에 있는지"를 잃는다.
2. 요청이 들어올 때마다 캐시 미스(Cache Miss)가 발생한다.
3. 폭발한 캐시 미스 요청이 전부 원본 DB로 향한다.
4. 수천 개의 요청이 같은 DB에 한꺼번에 몰려 과부하로 쓰러진다.

이 4번째 단계를 캐시 스탬피드(Cache Stampede)라고 부른다. 캐시가 무너진 순간 DB가 읽기 폭탄을 맞는 것이다. 서버를 늘려 안정성을 높이려다가 오히려 시스템 전체를 죽이는 아이러니, 그 시작이 바로 % N 한 줄이다. 캐시 TTL이 일괄적으로 같은 시각에 만료되도록 설계된 시스템일수록 이 폭탄은 더 크게 터진다. 만료된 키를 찾으러 온 요청들이 동시다발적으로 DB를 두드리니까.

비유: 4개의 창고에 책을 골고루 나눠 두었다. 그런데 창고 하나가 문을 닫아 3개 창고 체제로 재편한다고 하자. 단순히 "닫힌 창고의 책만 옮기면" 될 텐데, % N 방식은 모든 책이 "어느 창고에 있어야 하는지"를 처음부터 다시 계산하도록 만든다. 결과적으로 거의 모든 책이 다른 창고로 이동하고, 그 순간 책을 찾으러 오는 손님들은 빈자리만 확인하다가 전부 본 창고(DB)로 몰려든다.

2. 안정 해시 — 원형 링 위에 서버를 배치하다

안정 해시(Consistent Hashing)의 핵심 통찰은 "서버 수"를 매핑 기준에서 아예 빼자는 것이다. 대신 해시 함수의 출력 공간 전체를 하나의 원(링)으로 보고, 그 위에 서버와 키를 각각 해시해서 점으로 배치한다. 책은 SHA-1을 해시 함수로 쓸 때 출력 범위(0 ~ 2^160-1)를 예로 드는데, 핵심은 "해시 출력 공간을 원으로 이어 붙인다"는 점이다.

동작은 네 단계로 요약된다.

1. 해시 출력 범위의 최솟값과 최댓값을 이어 붙여 원형 링을 만든다.
2. 각 서버를 해시해 링 위 한 점에 배치한다.
3. 각 키도 해시해 링 위 한 점에 떨어뜨린다.
4. 키는 시계 방향으로 걸어가 처음 만나는 서버에 저장된다.

서버의 링 배치는 서버 이름이나 IP 주소를 해시한 값으로 정한다. 서버가 물리적으로 어디에 서 있는지는 중요하지 않고, 해시 결과가 링의 어느 지점에 떨어지느냐가 전부다. 가상 노드를 쓰는 환경에서는 이 배치 과정이 "물리 서버 하나당 여러 가상 노드를 각각 해시해 링에 흩어 놓는" 것으로 바뀌고, 키는 여전히 시계 방향으로 가장 가까운 가상 노드를 찾은 뒤, 그 가상 노드가 속한 물리 서버로 라우팅된다.

이 방식이 강력한 이유는 서버가 늘거나 줄어도 "매핑 공식"이 바뀌지 않는다는 데 있다. 키가 어느 서버에 저장될지는 오직 "링 위에서 시계 방향으로 가장 가까운 서버"로만 결정된다. 서버 목록과 무관하게, 키의 위치와 링 위 서버 배치만으로 답이 나오는 것이다.

서버 S를 1대 새로 추가했다고 하자. 새 서버 S는 링 위의 어느 한 점에 배치되고, 영향받는 데이터는 S와 그 "이전" 서버 사이 구간에 있던 키들뿐이다. 그 구간의 키들은 S로 이동하고, 나머지 전체 구간의 키들은 아무 변화가 없다. 서버가 죽는 경우도 대칭이다. 죽은 서버가 담당하던 구간의 키만 시계 방향의 다음 서버로 넘어간다. 재배치 비용이 "전체"가 아니라 "인접 구간"으로 국한되는 것이 바로 안정 해시의 존재 이유다.

방식	서버 1대 추가 시	서버 1대 제거 시	매핑 공식
해시 % N	전체 키의 대부분이 재배치	전체 키의 대부분이 재배치	서버 수 N이 공식에 포함
안정 해시	새 서버와 이전 서버 사이 구간의 키만 이동	죽은 서버 담당 구간의 키만 다음 서버로 이동	링 위 "가장 가까운 서버"만 사용

면접에서 이 차이를 숫자로 설명할 준비를 하자. 서버가 N대일 때 안정 해시는 서버 1대 증감 시 약 1/N의 데이터만 재배치된다. 반면 % N 방식은 나머지 연산의 기준 자체가 바뀌어 거의 전 키가 다시 매핑된다. "1/N vs 거의 전부"라는 두 숫자만 기억해도 이 챕터의 첫 문장은 열린다.

비유: 원형 트랙 위에 편의점이 몇 개 늘어서 있다. 물건을 맡기러 온 사람은 트랙을 걷다가 처음 만나는 편의점에 맡긴다. 어떤 편의점이 문을 닫아도 "조금 더 걸어서 다음 편의점에 맡기면" 그만이다. 나머지 편의점들과 그곳에 보관된 물건은 전혀 흔들리지 않는다. 이것이 안정 해시가 재배치를 최소화하는 방식이다.

3. 가상 노드(Virtual Node) — 소수 서버의 불균등 분포

안정 해시에도 약점이 있다. 서버 수가 적을 때다. 링 위에 서버가 2~3개뿐이면, 서버 사이의 구간 길이가 제각각이라 키 분포가 크게 어긋난다. 어떤 서버는 전체 키의 절반 가까이를 떠안고, 어떤 서버는 거의 놀게 된다. 설상가상으로 서버 한 대가 장애로 죽으면 그 옆 서버가 죽은 서버의 몫까지 떠안으며 부하가 급증하는 상황도 생긴다. 링 위 배치는 해시 함수의 결과에 달려 있어 우리가 "멋대로" 간격을 정할 수 없기 때문에, 소수 서버 환경에서는 이 편차를 구조적으로 막기 어렵다.

이를 해결하는 장치가 가상 노드(Virtual Node)다. 물리 서버 하나를 링 위에 한 점이 아니라 여러 개의 점으로 배치하는 것이다. 예를 들어 서버 A가 가상 노드 A0, A1, A2, ... 를 링 곳곳에 흩어 놓고, 서버 B도 같은 수의 가상 노드를 흩어 놓는다. 키는 여전히 "시계 방향으로 가장 가까운 가상 노드"로 라우팅되지만, 그 가상 노드가 실제로 어느 물리 서버에 속하는지 매핑 테이블에서 찾아가면 된다.

가상 노드가 많아질수록 링 위의 분포는 균등해진다. 물리 서버 1대당 K개의 가상 노드를 생성해 링 전체에 흩뿌려두면, 링의 어느 구간을 잘라 봐도 각 물리 서버의 키 비중이 고르게 섞인다(실무에서는 일반적으로 서버당 100~200개의 가상 노드를 둔다).

각 가상 노드는 생성 시 물리 서버의 식별자에 고유한 인덱스(예: S1-vnode0, S1-vnode1, ...)를 붙여 해시한 값을 위치로 사용한다. 즉, 각 가상 노드는 링 위에 독립적인 위치로 배치되며, 그 위치는 생성될 때 정해져 고정된다. 각 가상 노드는 처음부터 특정 물리 서버 1대가 소유한다.

서버가 추가되면, 기존 가상 노드는 링 위에서 움직이지 않고 제자리에 둔 채, 신규 물리 서버용 가상 노드 K개만 새로 링 위에 추가한다. 여기서 주목할 점은 기존의 가상 노드들은 하나도 움직이지 않고, 단지 신규 물리 서버의 가상 노드 K개만 새롭게 링 위에 배치된다는 것이다. 그 결과, 새로 추가된 가상 노드들이 위치한 시계방향 구간에 속한 키들만 기존 물리 서버에서 신규 물리 서버로 소유권이 이전된다. 서버가 제거될 때는 반대로, 제거되는 물리 서버가 소유하던 가상 노드들을 링에서 제거하면 되고, 그 가상 노드들이 담당하던 구간들은 시계방향으로 다음에 만나는 가상 노드(물리 서버)가 이어받는다. 기존 가상 노드는 링 위 위치를 그대로 유지한 채, 신규 물리 서버용 가상 노드만 추가되기 때문에 데이터 이동량은 약 1/N으로 최소화된다.

대신 트레이드오프가 하나 생긴다. 가상 노드 수가 늘수록 라우팅 테이블(가상 노드 → 물리 서버 매핑)의 크기가 커져 저장·조회 비용이 증가한다. 그래서 실무 구현들은 서버 상태 변화에 맞춰 서버당 가상 노드 수를 조정하는 식으로 균형을 잡는다.

구분	가상 노드 도입 전	가상 노드 도입 후
물리 서버 배치	서버 1대 = 링 위 1개 점	서버 1대 = 링 위 수십~수백 개 점
키 분포	서버 수가 적으면 편차가 큼	구간 단위로 잘라 봐도 고르게 섞임
서버 1대 장애 시	옆 서버가 몫까지 떠안아 부하 급증	부하가 여러 서버로 분산되어 완만
라우팅 비용	테이블이 작아 단순	테이블이 커져 저장·조회 비용 증가

4. 실전 재사용 — KV 저장소, CDN, 로드 밸런서

안정 해시는 특정 제품의 기능이 아니라 "데이터를 여러 노드에 나눠 담는 모든 곳"의 공용 부품이다. 대표적인 세 곳을 짚으면 다음과 같다.

• 키-값 저장소(Key-Value Store) 파티셔닝: 데이터를 링 위에 분산하고 각 키를 N개 노드에 복제한다. 노드 증감 시 이동하는 데이터가 최소화되어 리샤딩 비용이 줄어든다. 이 패턴은 다음 편에서 본격적으로 다룬다.
• CDN 캐시 라우팅: CDN 서버의 증설과 폐기를 매끄럽게 반영한다. 에지 서버를 추가해도 캐시 키가 통째로 흔들리지 않으므로, 사용자 요청이 원본 서버로 새는 것을 최소화한다.
• 로드 밸런서의 확장: 상태를 가진 연결(스티키 세션 등)을 서버 집합에 고르게 분산하면서도, 서버가 늘어나도 기존 매핑을 최대한 보존한다. 노드가 빠지는 순간 전체 연결이 리셋되는 사고를 막아 준다.

여기서 짚고 넘어갈 점은 "언제 % N을 떠나야 하는가"다. 나머지 연산이 나쁜 것은 아니다. 서버 대수가 고정적이고 재배치 비용이 낮은 환경에서는 오히려 더 단순하고 효율적이다. 문제는 서버 증감이 잦거나 장애가 일상인 분산 환경이다. 그 경계에서 안정 해시로 전환하는 것이 설계자의 판단이다. 단순한 도입 이유 하나만으로 바꾸지 말고, "서버 증감 빈도와 그때의 데이터 이동 비용"을 견줘서 결정하라는 뜻이다.

구현할 때도 몇 가지를 함께 정해야 한다. 해시 함수로 무엇을 쓸지(해시 품질이 링 위 분포의 균등성에 직결된다), 링 위 노드 목록을 어떻게 유지할지(정렬된 링에서 "시계 방향으로 가장 가까운 노드"는 이분 탐색으로 찾는다), 그리고 서버 목록 변경을 노드 간에 어떻게 전파할지 등이다. 안정 해시는 아이디어 그 자체보다 "아이디어 + 운영 세부"로 완성되는 설계다.

면접 질문 "캐시 서버를 확장할 때 왜 안정 해시를 쓰는가"에는 세 가지를 한 꾸러미로 말하자. 첫째, % N은 서버 수가 바뀌면 대부분의 키가 매핑을 잃어 캐시 스탬피드가 터진다. 둘째, 안정 해시는 서버 증감 시 인접 구간의 데이터만 재배치해 N대 기준 약 1/N만 이동한다. 셋째, 서버 수가 적을 때 생기는 불균등 분포는 가상 노드로 균등화한다. 이 세 문장이 이 챕터의 전부다.

참고 자료

• Alex Xu, 『가상면접 사례로 배우는 대규모 시스템 설계 기초』(System Design Interview – An Insider's Guide), Design Gurus·ByteByteGo, 2021
• David Karger et al., "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web", STOC, 1997

5. 실무에서 자주 만나는 함정

안정 해시는 "데이터 이사가 작다"는 장점만 보면 놓치는 함정들이 있다.

함정	증상	회피법
가상 노드 수 결정의 오류	너무 적으면 분포가 들쭉날쭉 → 일부 서버 핫스팟, 너무 많으면 메모리·해시 계산 비용 폭증	보통 서버당 100~200개 가상 노드에서 시작, 실측 후 조정
키 편향(Skewed Key)	특정 키 prefix(예: 같은 사용자 ID prefix)에 트래픽이 몰림	키 솔팅(salting): 키 끝에 랜덤 접미사를 붙여 분산 후 결과 집계
노드 메타데이터 동기화	노드 추가/제거 시 다른 노드들이 링 구조를 모름 → 일부 키가 잘못된 노드로 라우팅	가십 프로토콜 또는 코디네이터(ZooKeeper/etcd)로 링 상태 전파
리밸런싱 중 일시적 실패	데이터 이관 중 해당 키 조회 실패 → 5xx 에러	점진적 이관(이중 쓰기 기간) + 조회는 새 노드 우선, 실패 시 기존 노드 fallback

6. 30초 면접 답변 예시

"안정 해시는 서버가 추가·제거돼도 데이터 재배치를 최소화하는 게 핵심입니다. hash(key) % N은 서버 1대 변동으로 대부분의 키 매핑이 바뀌지만, 안정 해시는 서버를 해시 링에 배치해 인접 구간만 재배치합니다. 노드 소수일 때 분포가 불균등한 문제는 가상 노드로 해결하고, 실제 적용은 키-값 저장소 파티셔닝·CDN 라우팅·로드 밸런서에 쓰입니다. 면접에서는 '왜 % N이 안 되는가'를 캐시 스탬피드로 설명하고, 가상 노드 수의 결정 기준을 짚으면 깊이를 보여줄 수 있습니다." (예: 재배치 비율 "약 1/N", 가상 노드 개수 100~200개)

다음 편 예고

다음 편은 키-값 저장소(Key-Value Store) 설계다. 안정 해시 링 위에 데이터를 분산하고 복제하는 방법이 실제로 쓰이는 곳이다. 이번 편에서 배운 해시 링과 가상 노드가, 분산 KV의 파티셔닝과 장애 감지·일관성 선택에서 어떻게 재사용되는지 이어서 본다.