Consistent Hashing, cache sharding에서 key 이동을 줄이는 방법

서비스가 커지면 하나의 cache node나 storage node에 모든 key를 넣기 어렵습니다.

그래서 여러 node로 key를 나누는 sharding을 사용합니다.

가장 단순한 방식은 hash(key) % node_count이지만, node가 추가되거나 제거되는 순간 많은 key가 한꺼번에 이동하는 문제가 생깁니다.

Consistent hashing은 이 문제를 줄이기 위해 hash space를 ring처럼 보고, key가 이동해야 하는 범위를 제한하는 방법입니다.

 

Consistent hashing의 핵심은 node 수가 바뀌어도 전체 key를 다시 나누지 않고, 바뀐 node 주변의 key만 이동시키는 것입니다.

 

Consistent hashing은 cache sharding, distributed storage, load distribution에서 node 변화에 따른 key 이동을 줄이기 위해 사용됩니다.

 

---

1. 들어가며

Sharding은 데이터를 여러 node에 나눠 담는 방법입니다.

예를 들어 user session cache를 Redis 여러 대에 나눠 저장하거나, image metadata를 여러 storage partition에 나눠 저장할 수 있습니다.

문제는 node 수가 고정되어 있지 않다는 점입니다.

트래픽이 늘면 node를 추가하고, 장애가 나면 node를 제거해야 합니다.

이때 key 이동이 너무 많으면 cache miss가 폭증하거나 storage migration 비용이 커집니다.

 

방식	아이디어	node 변화 시 문제
Modulo sharding	hash(key) % node_count	node_count가 바뀌면 대부분 key의 위치가 바뀜
Range sharding	key range를 node별로 나눔	hot range가 생기면 특정 node에 부하 집중
Consistent hashing	hash ring에서 key가 시계 방향으로 만나는 node에 배치	ring 설계와 virtual node 수를 잘 잡아야 함

Consistent hashing은 모든 문제를 해결하는 magic은 아니지만, node 증감이 잦은 distributed system에서 중요한 기본기입니다.

 

---

2. 왜 중요한가?

분산 시스템에서 key를 어디에 둘지 정하는 방식은 성능과 장애 복구에 직접 영향을 줍니다.

잘못된 sharding 방식은 평소에는 문제가 없어 보이다가 scale-out이나 failover 순간에 큰 비용을 만듭니다.

1. node를 추가할 때 이동해야 하는 key 수를 줄일 수 있습니다.
2. cache cluster에서 대규모 cache miss를 줄이는 데 도움이 됩니다.
3. storage나 queue partition을 늘릴 때 migration 범위를 제한할 수 있습니다.
4. 장애 node가 빠졌을 때 영향을 받는 key range를 이해하기 쉽습니다.
5. 면접에서 sharding, hash table, distributed cache를 함께 설명하기 좋은 주제입니다.

특히 cache에서는 key 이동이 곧 cache miss로 이어질 수 있습니다.

node를 3대에서 4대로 늘렸는데 대부분 key가 다른 node로 이동하면, scale-out 직후 backend DB에 부하가 몰릴 수 있습니다.

 

---

3. 핵심 개념

Consistent hashing은 hash value를 일직선이 아니라 원형 ring으로 생각합니다.

Node와 key를 같은 hash space 위에 올려두고, key는 시계 방향으로 가장 먼저 만나는 node에 배치합니다.

ring의 끝까지 갔는데 node가 없으면 처음 위치로 돌아갑니다.

 

개념	의미	실무에서 보는 지점
Hash space	key와 node가 배치되는 전체 범위	hash function의 분포가 고르게 나와야 함
Ring	hash space의 끝과 시작을 연결한 구조	마지막 range는 첫 node로 wrap around됨
Successor node	key 위치에서 시계 방향으로 처음 만나는 node	key의 담당 node가 됨
Virtual node	하나의 물리 node를 ring 위 여러 지점에 배치	부하 분산을 더 고르게 만들기 위해 사용

Node가 추가되면 새 node 바로 이전 range의 key만 새 node로 이동합니다.

Node가 제거되면 그 node가 담당하던 key만 다음 successor node로 이동합니다.

이 특성이 consistent hashing의 핵심입니다.

 

---

4. 그림으로 이해하기

Consistent hashing에서는 새 node가 추가되어도 전체 key가 다시 섞이지 않고, 새 node 앞쪽의 일부 key range만 이동합니다.

 

그림에서 중요한 점은 key가 node 개수로 나눠지는 것이 아니라 ring 위의 위치로 배치된다는 점입니다.

따라서 node_count가 3에서 4로 바뀌어도 모든 key의 modulo 결과를 다시 계산하는 방식과 다르게 동작합니다.

영향 범위가 새 node 주변으로 제한되기 때문에 cache warm-up과 migration 비용을 예측하기 쉬워집니다.

 

상태 변화

기존 ring
node A, node B, node C가 hash ring 위에 배치됨
key는 자기 위치에서 시계 방향으로 처음 만나는 node에 저장됨

node D 추가
node D가 ring 위 특정 위치에 들어옴
node D 바로 앞 range의 key만 node D로 이동
나머지 key는 기존 담당 node를 유지

 

면접에서는 이 상태 변화를 말로 설명할 수 있어야 합니다.

“node가 추가되면 일부 key만 이동한다”에서 멈추지 말고, “새 node가 ring에서 차지하는 위치 이전 range만 이동한다”까지 설명하면 더 좋습니다.

 

---

5. 실무 예시

가장 흔한 예시는 distributed cache입니다.

Application server가 user_id나 session_id를 key로 hash하고, consistent hashing ring에서 담당 cache node를 찾습니다.

이 구조에서는 cache node를 하나 추가해도 전체 session key가 이동하지 않습니다.

 

상황	Modulo sharding	Consistent hashing
cache node 1대 추가	node_count가 바뀌어 많은 key 재배치	새 node 주변 key range만 이동
cache node 1대 장애	전체 modulo 기준이 흔들릴 수 있음	장애 node 담당 key가 다음 node로 이동
부하가 고르지 않음	hash 분포와 key 특성에 의존	virtual node로 분산 균형 조정 가능
운영 복잡도	구현은 단순하지만 scale 변화에 약함	ring 관리가 필요하지만 변화 비용이 작음

실무에서는 consistent hashing만으로 충분하지 않은 경우도 많습니다.

Virtual node 수, replication factor, hot key 대응, node weight, health check, rebalancing 속도까지 함께 봐야 합니다.

 

---

6. C++와 연결해보기

아래 C++17 예제는 단순화된 hash ring을 보여줍니다.

실제 시스템에서는 더 좋은 hash function과 virtual node가 필요하지만, key가 successor node로 배치된다는 핵심은 이 코드로 확인할 수 있습니다.

#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

class HashRing {
public:
    void add_node(int position, std::string name)
    {
        ring_[position] = std::move(name);
    }

    std::string route(int key_hash) const
    {
        auto it = ring_.lower_bound(key_hash);
        if (it == ring_.end()) {
            it = ring_.begin();
        }
        return it->second;
    }

private:
    std::map<int, std::string> ring_;
};

int toy_hash(const std::string& key)
{
    int value = 0;
    for (unsigned char ch : key) {
        value = (value * 31 + ch) % 600;
    }
    return value;
}

void print_routes(const HashRing& ring,
                  const std::vector<std::string>& keys)
{
    for (const auto& key : keys) {
        const int hash = toy_hash(key);
        std::cout << key << " hash=" << hash
                  << " node=" << ring.route(hash) << '\n';
    }
}

int main()
{
    const std::vector<std::string> keys = {
        "user:12", "session:88", "product:7", "cart:45"
    };

    HashRing ring;
    ring.add_node(100, "A");
    ring.add_node(300, "B");
    ring.add_node(500, "C");

    std::cout << "before adding D\n";
    print_routes(ring, keys);

    ring.add_node(150, "D");

    std::cout << "\nafter adding D\n";
    print_routes(ring, keys);
}

 

실행 결과

before adding D
user:12 hash=544 node=A
session:88 hash=12 node=A
product:7 hash=132 node=B
cart:45 hash=19 node=A

after adding D
user:12 hash=544 node=A
session:88 hash=12 node=A
product:7 hash=132 node=D
cart:45 hash=19 node=A

 

새 node D는 ring position 150에 추가되었습니다.

hash 값이 100보다 크고 150 이하인 key는 D로 이동하고, 다른 key는 기존 node를 유지합니다.

예제에서는 product:7만 B에서 D로 이동하고, user:12, session:88, cart:45는 기존 node를 유지합니다.

 

---

7. 면접 질문 예시

1. hash(key) % node_count 방식은 node를 추가할 때 왜 문제가 되나요?
   node_count가 바뀌면 modulo 결과가 바뀌어 많은 key가 다른 node로 이동합니다. Cache에서는 대량 cache miss로 이어질 수 있습니다.
2. Consistent hashing에서 node가 추가되면 어떤 key가 이동하나요?
   새 node가 ring 위에 들어간 위치를 기준으로, 그 node 바로 앞 range에 있던 key만 새 node로 이동합니다.
3. Virtual node는 왜 필요한가요?
   물리 node를 ring 위 여러 위치에 배치해 key 분포를 더 고르게 만들고, node별 capacity 차이를 weight로 반영하기 위해 사용합니다.

답변할 때는 “key 이동이 적다”는 장점만 말하기보다, ring 구조, successor node, virtual node, hot key 한계까지 함께 언급하는 편이 좋습니다.

 

---

8. 실무에서는 어떻게 볼까?

Consistent hashing을 도입할 때는 algorithm 자체보다 운영 조건이 더 중요합니다.

Hash ring이 잘 설계되어도 특정 key에 요청이 몰리는 hot key 문제는 별도로 해결해야 합니다.

또 cache node가 서로 다른 성능을 갖는다면 virtual node 개수나 weight를 조절해야 합니다.

운영 질문	확인할 내용	대응 방향
Key 분포가 고른가?	특정 node에 key나 traffic이 몰리는지 확인	virtual node 수와 hash function 점검
Hot key가 있는가?	일부 key에 요청이 집중되는지 확인	replication, local cache, request coalescing 검토
Node weight가 다른가?	node별 CPU, memory, network capacity 차이 확인	weighted virtual node 적용
장애 복구가 빠른가?	node 제거 후 traffic이 어느 node로 몰리는지 확인	replication factor와 health check 조정
Migration 속도를 제어하는가?	새 node 추가 시 backend 부하가 증가하는지 확인	gradual rollout과 rate limit 적용

Consistent hashing은 “key 이동을 줄이는 배치 전략”이지 “부하 문제를 자동으로 해결하는 시스템”은 아닙니다.

실무에서는 monitoring, replication, health check와 함께 설계해야 합니다.

 

---

9. 정리

Consistent hashing은 node 변화가 있을 때 key 이동 범위를 줄이는 sharding 기법입니다.

Key와 node를 같은 hash ring 위에 두고, key는 시계 방향 successor node에 배치됩니다.

Node 추가 시 새 node 주변 range의 key만 이동하므로 cache miss와 migration 비용을 줄일 수 있습니다.

Virtual node는 key 분포를 고르게 만들고 node weight를 반영하는 데 사용됩니다.

실무에서는 hot key, replication, health check, gradual migration까지 함께 봐야 합니다.

 

---