Distributed Systems - 10. 일관적 해싱

일관적 해싱 — 노드 추가/제거 시 최소 이동

2014년 한 시스템이 4개 노드로 운영되다가 트래픽이 늘어 5개로 확장했다. 해시 파티셔닝(05편)을 썼기 때문에, 노드가 4→5로 바뀌자 전체 데이터의 80%가 다른 노드로 이동해야 했다. 클러스터가 몇 시간 동안 비정상적으로 동작했고, 확장은 실패로 끝났다. 노드 하나를 추가했을 뿐인데 데이터 대부분이 움직이는 현상 — 이건 해시 분할의 근본적 한계다. 이 한계를 해결하는 기법이 일관적 해싱(consistent hashing)이다. 1997년 David Karger 등이 발표한 이 기법은 — 노드가 추가·제거될 때 데이터 이동을 최소화한다. 오늘날 Dynamo, Cassandra, Memcached, CDN이 쓰는 핵심 기법이다.

비유로 감 잡기 — 원형 테이블의 자리 배정

원형 테이블에 사람들이 앉아 있다고 상상하자. 새 사람이 들어와 자리가 필요하다. 직사각형 테이블이었다면 — 빈 자리를 만들려고 모든 사람이 한 자리씩 옆으로 이동해야 할 수 있다. 원형 테이블이면 — 한 사람이 두 사람 사이에 끼어들면, 그 두 사람만 살짝 벌리면 된다. 나머지 사람들은 그대로.

일관적 해싱이 이 원형 테이블과 비슷하다. 노드와 데이터(키)를 모두 원형(해시 링) 위의 점으로 대응시킨다. 각 키는 "원형 위에서 시계 방향으로 만나는 첫 번째 노드"가 담당한다. 새 노드가 추가되면 — 원형 위의 한 점에 배치되고, 그 점 다음의 기존 노드가 담당하던 일부 키만 새 노드로 옮겨온다. 전체 데이터의 1/N만 움직이면 된다 (N은 노드 수).

flowchart TD
    subgraph Hash["해시 링 (원형 공간)"]
        N1[Node A]
        N2[Node B]
        N3[Node C]
        K1[Key 1]
        K2[Key 2]
        K3[Key 3]
        K4[Key 4]
    end

원형이라서 어디가 "처음"인지 정하기 위해 — 시계 방향으로 "각 노드 다음의 첫 키"를 그 노드가 담당한다고 정한다. Node A가 담당하는 키는 Node A 위치에서 시계 방향으로 Node B 위치 직전까지의 키들이다.

비유의 한계 — 원형 테이블 비유는 '균등 배치'를 가정하지만, 실제 일관적 해싱은 노드의 해시 위치가 불균등할 수 있다 (한 노드가 원형의 넓은 영역을 차지). 가상 노드(virtual nodes) 기법으로 이를 보정한다. 비유는 '균등 배치 가정'에서 무너진다.

일관적 해싱의 핵심 — 노드 추가/제거 시 이동 최소화

해시 분할(05편)의 hash(key) % N 방식은 — N이 바뀌면 (노드 추가·제거) 거의 모든 키의 담당 노드가 바뀐다. 데이터의 대부분이 이동해야 한다.

// 해시 분할 — 노드 수 변경 시 대규모 이동
class HashModPartitioner {
    private int nodeCount;

    int nodeForKey(String key) {
        return Math.abs(key.hashCode()) % nodeCount;
    }
    // nodeCount가 4에서 5로 바뀌면:
    // key=1: 1%4=1 → 1%5=1 (유지)
    // key=2: 2%4=2 → 2%5=2 (유지)
    // key=4: 4%4=0 → 4%5=4 (이동)
    // key=5: 5%4=1 → 5%5=0 (이동)
    // 약 80% 키가 이동
}

일관적 해싱은 이 문제를 노드와 키를 같은 해시 공간에 배치해서 해결한다.

// 일관적 해싱 — 노드 수 변경 시 최소 이동
class ConsistentHashPartitioner {
    private final SortedMap<Integer, Node> ring = new TreeMap<>();
    private final HashFunction hash;

    void addNode(Node node) {
        int position = hash.hash(node.id());
        ring.put(position, node);
        // 기존 노드가 담당하던 일부 키만 이 노드로 이동
    }

    void removeNode(Node node) {
        int position = hash.hash(node.id());
        Node nextNode = ring.higherEntry(position).getValue();
        ring.remove(position);
        // 이 노드가 담당하던 키만 nextNode로 이동
    }

    Node nodeForKey(String key) {
        int position = hash.hash(key);
        // 시계 방향으로 첫 번째 노드 찾기
        SortedMap<Integer, Node> tail = ring.tailMap(position);
        if (tail.isEmpty()) {
            return ring.get(ring.firstKey());  // 원형이므로 처음으로
        }
        return tail.get(tail.firstKey());
    }
}

이 구조에서 — 노드 하나가 추가되면 그 노드의 해시 위치 다음 영역을 담당하던 기존 노드의 일부 키만 새 노드로 옮겨온다. 전체 키의 약 1/N만 이동 (N은 노드 수). 5번 노드가 4개에서 5개로 갈 때, 약 20%만 이동.

가상 노드 (Virtual Nodes) — 균등 분산의 핵심

단순한 일관적 해싱의 문제 — 노드의 해시 위치가 불균등하다. 한 노드가 원형의 넓은 영역을 차지하고, 다른 노드는 좁은 영역을 차지할 수 있다. 그러면 부하가 균등하지 않다.

해결책 — 각 물리 노드를 원형 위의 여러 점에 배치하는 것. 이를 가상 노드(virtual node) 또는 vnode라 부른다.

class ConsistentHashWithVNodes {
    private final SortedMap<Integer, Node> ring = new TreeMap<>();
    private final int vnodesPerNode = 150;  // 물리 노드당 150개 가상 노드

    void addNode(Node node) {
        for (int i = 0; i < vnodesPerNode; i++) {
            int position = hash.hash(node.id() + "-" + i);
            ring.put(position, node);
        }
    }

    void removeNode(Node node) {
        // 이 노드의 모든 가상 노드 제거
        ring.entrySet().removeIf(e -> e.getValue().equals(node));
    }

    Node nodeForKey(String key) {
        int position = hash.hash(key);
        SortedMap<Integer, Node> tail = ring.tailMap(position);
        return tail.isEmpty() ? ring.get(ring.firstKey()) : tail.get(tail.firstKey());
    }
}

가상 노드 수는 — 많을수록 균등 분산이 좋아지지만, 라우팅 비용(메모리·검색)이 증가한다. Cassandra는 기본 256개, Riak은 기본 64개. 실제로 100~300 사이가 흔한 설정.

가상 노드의 추가 이점 — 이질적 하드웨어

가상 노드는 또 다른 이점을 준다 — 물리 노드의 용량이 다를 때, 가상 노드 수를 다르게 해서 부하를 용량에 비례하게 배분.

// 용량에 비례한 가상 노드 수
void addNode(Node node) {
    int vnodes = (int) (baseVNodes * node.capacityRatio());
    // 강력한 노드는 더 많은 가상 노드 → 더 많은 부하
    // 약한 노드는 더 적은 가상 노드 → 더 적은 부하
    for (int i = 0; i < vnodes; i++) {
        ring.put(hash.hash(node.id() + "-" + i), node);
    }
}

예: 2배 강력한 노드는 2배 많은 가상 노드 → 2배 많은 키를 담당. 클러스터에 이질적 하드웨어가 섞여 있을 때 유용하다.

설계 사례 — Dynamo 스타일 키-값 저장소

Dynamo(DeCandia et al. 2007)가 정립한 패턴을 간소화해 본다. 일관적 해싱 + 복제 + 쿼럼의 조합.

class DynamoStyleStore {
    private final ConsistentHashRing ring;
    private final int replicationFactor = 3;  // 각 키 3개 노드에 복제

    Set<Node> nodesForKey(String key) {
        // 시계 방향으로 N개 노드 선택
        return ring.nextNNodes(hash(key), replicationFactor);
    }

    void put(String key, String value) {
        Set<Node> nodes = nodesForKey(key);
        // 코디네이터 (첫 번째 노드)가 다른 노드에 전파
        Node coordinator = nodes.iterator().next();
        coordinator.putLocal(key, value);
        coordinator.replicateTo(key, value, nodes);  // 비동기 전파
    }

    String get(String key) {
        Set<Node> nodes = nodesForKey(key);
        // 여러 노드에서 읽어 최신 선택 (vector clock으로 버전 비교)
        List<VersionedValue> values = new ArrayList<>();
        for (Node n : nodes) {
            values.add(n.getLocal(key));
        }
        return reconcile(values);  // 충돌 해결
    }
}

이 패턴에서 — 각 키는 원형 위에서 시계 방향으로 연속한 3개 노드에 복제된다. 한 노드가 죽어도 나머지 2개가 서비스. 새 노드가 추가되면, 원형 위의 그 영역을 담당하던 기존 노드 1개가 일부 키를 새 노드에 넘겨주고, 새 노드는 그 키를 자기 다음 노드 2개에 복제한다. 노드 추가가 거의 영향을 안 미치는 이유가 여기에.

일관적 해싱 위반/오용 감지

신호	의미
노드 추가 시 데이터의 50% 이상 이동	일관적 해싱 미사용 또는 가상 노드 부족
한 노드의 부하가 다른 노드의 3배	가상 노드 수 부족 — 균등 분산 실패
노드 제거 시 그 노드의 데이터 유실	다음 노드로 승계 안 됨
키 조회가 O(N) (N=노드 수)	라우팅 자료구조 미흡 — TreeMap 사용 안 함
가상 노드 수가 물리 노드에 따라 안 변함	이질적 하드웨어에서 부하 불균등
노드 추가 직후 일시적 일관성 위반	복제 동기화 전에 읽기 허용

일관적 해싱이 쓰이는 시스템

일관적 해싱은 특정 라이브러리가 아니라 — 분산 시스템의 기본 패턴이다. 거의 모든 수평 확장 시스템이 변형해서 쓴다.

• DynamoDB — Dynamo 논문의 직계 후손. 일관적 해싱 + 복제 + 쿼럼.
• Cassandra — Dynamo 모델 + 컬럼 패밀리. 가상 노드(vnode) 256개 기본.
• Memcached — 클라이언트사이드 일관적 해싱 (Ketama 알고리즘).
• CDN (Akamai 등) — 사용자를 가장 가까운 에지 서버로 라우팅.
• Riak — 일관적 해싱 + vector clock + CRDT.
• Redis Cluster — 16384개 슬롯을 해시 슬롯으로 분할. 일관적 해싱의 단순화된 변형.

각각의 구현은 세부에서 다르지만 — "노드 추가/제거 시 최소 이동"이라는 핵심 아이디어는 같다.

다른 패턴과의 관계

일관적 해싱은 다른 분산 패턴과 자주 짝한다.

• 파티셔닝(05편) — 일관적 해싱은 파티셔닝의 한 형태. 노드 추가 시 재밸런싱 비용 최소화.
• 복제(06편) — 각 키를 담당하는 N개 노드를 일관적 해싱으로 선택. Dynamo의 패턴.
• 일관성 모델(03편) — 일관적 해싱은 어디로 보낼까를 다루고, 일관성 모델은 보낸 뒤 어떻게 일치시킬까를 다룸. 직교하는 관심사.
• 합의(04편) — 일관적 해싱 자체는 합의 없이 동작 (각 클라이언트가 독립적으로 계산). 합의는 "링 구성원 변화"를 합의할 때 쓰임.

일관적 해싱의 한계

일관적 해싱이 만능은 아니다. 한계가 뚜렷하다.

• 핫스팟을 완전히 없애지 못함 — 키의 해시 분포가 안 좋으면, 한 노드가 우연히 인기 키를 많이 담당할 수 있다. 가상 노드는 완화하지만 제거하진 못한다.
• 복잡한 쿼리에 부적합 — 범위 쿼리(05편 참조)가 어렵다. 인접 키가 서로 다른 노드에 있을 수 있어, 범위 조회가 모든 노드에 가야 할 수 있다.
• 운영 복잡성 — 링 구성원 관리, 가상 노드 조정, 복제본 동기화가 복잡하다. 단순한 시스템엔 오버엔지니어링.

그래서 — 데이터가 단일 노드에 들어가거나, 범위 쿼리가 주된 패턴이면, 단순한 범위 분할이 더 나을 수 있다. 일관적 해싱은 — 데이터가 크고, 노드 추가/제거가 빈번하고, 키 단위 조회가 주된 패턴일 때 빛을 발한다.

다음으로 — 시간과 순서

일관적 해싱은 "어디로 보낼까"를 다뤘다면, 다음 편들(합의·시간·분산 트랜잭션)은 "보낸 뒤 어떻게 일치시킬까"를 다룬다. 특히 09편(시간·순서)은 — 분산 시스템에서 "어떤 일이 먼저 일어났나"를 어떻게 정할까를 다룬다. 일관적 해싱이 각 클라이언트의 독립적 계산으로 동작할 수 있는 건, "어디로"가 시간과 무관하기 때문. 하지만 "어떤 쓰기가 최신인가"는 시간에 의존한다 — 그래서 일관성 모델의 강한 쪽(linearizability)은 합의·시계·버전 벡터 같은 도구를 필요로 한다.

일관적 해싱의 핵심 통찰 — 데이터를 어디에 둘까라는 문제를 "원형 위의 점"이라는 우아한 추상화로 풀었다는 점이다. 노드와 키를 같은 공간에 배치하면, 추가/제거의 영향이 자연스럽게 최소화된다. 이 단순한 아이디어가 오늘날 분산 데이터 인프라의 근간이다.

---

참고

• Karger et al. — "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" (ACM STOC 1997), 일관적 해싱 원 논문 — 접근 2026-07-20
• DeCandia et al. — "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007), 가상 노드·복제·쿼럼 결합 — 접근 2026-07-20
• Lakshman, Malik — "Cassandra: A Decentralized Structured Storage System" (ACM SIGOPS Operating Systems Review, 2010) — 접근 2026-07-20
• Nishtala et al. — "Scaling Memcache at Facebook" (NSDI 2013), Ketama 알고리즘 — 접근 2026-07-20
• Kleppmann — (O'Reilly, 2017), Ch.6 (파티셔닝 — 일관적 해싱 절)