Consistent Hashing

// Consistent hash ring
//
//         0 / 2^32
//          │
//    Node C ●──────── ● Node A
//          │         /
//          │  key1 ●   ← maps to Node A (first CW)
//          │       /
//    key3 ●──────●
//          │     Node B
//          │
//
// Adding Node D between B and C:
//   Only keys between B and D move to D
//   All other keys stay put
//
// Without consistent hashing:
//   hash(key) % 3 → hash(key) % 4 = ~75% of keys remapped!
// With consistent hashing:
//   Only ~1/N keys remapped (where N = number of nodes)

// Virtual nodes — even distribution
//
// Without vnodes: 3 nodes might get 60/25/15 split
// With 100 vnodes per node: ~33/33/33 split
//
// Implementation sketch
public class ConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int vnodes;

    public ConsistentHash(Collection<T> nodes, int vnodes) {
        this.vnodes = vnodes;
        for (T node : nodes) addNode(node);
    }

    public void addNode(T node) {
        for (int i = 0; i < vnodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    public void removeNode(T node) {
        for (int i = 0; i < vnodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    public T getNode(String key) {
        long hash = hash(key);
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        return (entry != null) ? entry.getValue() : ring.firstEntry().getValue();
    }
}

// Cassandra: partitioner uses consistent hashing (Murmur3)
// Each token range maps to a set of nodes
// vnodes = 256 (default) — each node owns 256 token ranges

// DynamoDB: consistent hashing for partition placement
// Partition key → hash → partition → storage node

// Redis Cluster: 16384 hash slots
// slot = CRC16(key) % 16384
// Each node owns a range of slots
// Resharding: migrate slots between nodes

// Envoy proxy: consistent hashing for session affinity
clusters:
  - name: api_service
    lb_policy: RING_HASH  # consistent hashing
    ring_hash_lb_config:
      minimum_ring_size: 1024