Consistent Hashing

// Simple modulo hashing
int shard = hash(key) % N;

// Adding a server (N becomes N+1):
// hash(key) % 3 vs hash(key) % 4 — almost ALL keys remap!
// This causes a thundering herd on the new node

         0
        / \
   S_A /   \ S_B
      /     \
    2^32   2^10
      \     /
   S_C \   /
        \ /
        2^31

Key hash at 2^5 → next server clockwise = S_B

class ConsistentHash {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int virtualNodes;

    public ConsistentHash(List<String> servers, int virtualNodes) {
        this.virtualNodes = virtualNodes;
        for (String server : servers) addServer(server);
    }

    public void addServer(String server) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(server + "#" + i);
            ring.put(hash, server);
        }
    }

    public void removeServer(String server) {
        for (int i = 0; i < virtualNodes; i++)
            ring.remove(hash(server + "#" + i));
    }

    public String getServer(String key) {
        if (ring.isEmpty()) return null;
        long hash = hash(key);
        Map.Entry<Long, String> entry = ring.ceilingEntry(hash); // first server >= hash
        if (entry == null) entry = ring.firstEntry(); // wrap around
        return entry.getValue();
    }

    private long hash(String key) {
        // MurmurHash or similar 32/64-bit hash
        return Math.abs(key.hashCode()) % Long.MAX_VALUE;
    }
}

Without virtual nodes (3 servers):
  S_A: 0-30%, S_B: 30-80%, S_C: 80-100% ← very uneven!

With 100 virtual nodes per server (300 positions on ring):
  S_A: ~33%, S_B: ~33%, S_C: ~33% ← much more even

Before: S_A, S_B, S_C
Keys between S_A and S_B → served by S_B

Add S_D between S_A and S_B:
Keys between S_A and S_D → move from S_B to S_D
All other keys: unchanged!

Total keys moved = 1/(N+1) of total keys