일관된 해싱 — 서버가 추가되어도 데이터가 안 깨지는 이유

서버 3대: hash("user:1001") % 3 = 2 → 서버2
서버 4대: hash("user:1001") % 4 = 1 → 서버1 (이동!)

서버 1대 추가했을 뿐인데, 약 75%의 키가 다른 서버로 이동
→ 캐시 미스 폭증 → DB 부하 급증 (cache stampede)

      0
   ┌──┬──┐
   │  S1  │
 S3│      │
   │      │
   │  S2  │
   └──┴──┘
     2^32

키 K가 S2와 S3 사이에 있으면 → S3가 담당

S3 제거 전: K → S3가 담당
S3 제거 후: K → S3 다음 서버인 S1이 담당
           (K와 S3 사이의 키만 S1으로 이동)

public class ConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int virtualNodes; // 가상 노드 수
    private final MessageDigest md;

    public ConsistentHash(int virtualNodes) {
        this.virtualNodes = virtualNodes;
        try {
            this.md = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }

    // 서버 추가
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    // 서버 제거
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    // 키가 어느 서버에 속하는지 결정
    public T getNode(String key) {
        if (ring.isEmpty()) return null;
        long hash = hash(key);

        // 시계 방향으로 가장 가까운 서버 찾기
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry(); // 링의 끝을 넘으면 처음으로
        }
        return entry.getValue();
    }

    private long hash(String key) {
        md.reset();
        byte[] digest = md.digest(key.getBytes());
        // MD5의 처음 8바이트를 long으로 변환
        long hash = 0;
        for (int i = 0; i < 8; i++) {
            hash = (hash << 8) | (digest[i] & 0xFF);
        }
        return hash;
    }
}

물리 서버 S1 → 가상 노드: S1#0, S1#1, S1#2, ..., S1#149
물리 서버 S2 → 가상 노드: S2#0, S2#1, S2#2, ..., S2#149
물리 서버 S3 → 가상 노드: S3#0, S3#1, S3#2, ..., S3#149

총 450개 점이 링에 분포 → 훨씬 균등한 분배

// 고성능 서버는 가상 노드를 더 많이
addNodeWithWeight("server-large", 300);  // 가상 노드 300개
addNodeWithWeight("server-small", 100);  // 가상 노드 100개
// → 고성능 서버가 약 3배의 키를 담당

총 16384개의 슬롯
키의 슬롯 = CRC16(key) % 16384

노드 A: 슬롯 0-5460
노드 B: 슬롯 5461-10922
노드 C: 슬롯 10923-16383

upstream backend {
    hash $request_uri consistent;
    server backend1.example.com;
    server backend2.example.com;
    server backend3.example.com;
}