Consistent Hashing

---

Definition

---

How It Works

// CONSISTENT HASHING IMPLEMENTATION

class ConsistentHash<T> {
    private final TreeMap<Long, T> ring = new TreeMap<>();
    private final int virtualNodes;  // Replicas per server
    private final HashFunction hashFunction;

    ConsistentHash(int virtualNodes) {
        this.virtualNodes = virtualNodes;
        this.hashFunction = Hashing.murmur3_128();
    }

    // Add a server to the ring
    void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    // Remove a server from the ring
    void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    // Find the server for a key
    T getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }

        long hash = hash(key);

        // Find next server clockwise
        Map.Entry<Long, T> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            // Wrap around to first server
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }

    private long hash(String key) {
        return hashFunction.hashString(key, StandardCharsets.UTF_8).asLong();
    }
}

---

Virtual Nodes

---

Adding/Removing Nodes

---

Use Cases

// USE CASES FOR CONSISTENT HASHING

// 1. DISTRIBUTED CACHING (Memcached, Redis Cluster)
class DistributedCache {
    private final ConsistentHash<CacheNode> ring;

    Object get(String key) {
        CacheNode node = ring.getNode(key);
        return node.get(key);
    }

    void put(String key, Object value) {
        CacheNode node = ring.getNode(key);
        node.put(key, value);
    }
}

// 2. LOAD BALANCING
class ConsistentLoadBalancer {
    private final ConsistentHash<Server> ring;

    // Route user to consistent server (sticky sessions)
    Server getServerForUser(String userId) {
        return ring.getNode(userId);
    }
}

// 3. DATABASE SHARDING
class ShardRouter {
    private final ConsistentHash<DatabaseShard> ring;

    DatabaseShard getShard(String entityId) {
        return ring.getNode(entityId);
    }
}

// 4. CONTENT DELIVERY NETWORKS (CDNs)
// Route requests to consistent edge servers

// 5. DISTRIBUTED STORAGE (Amazon Dynamo, Cassandra)
// Determine which nodes store each key

// Benefits in all cases:
// - Minimal data movement when scaling
// - Predictable key location
// - Easy horizontal scaling

---

Replication with Consistent Hashing

---

Tips & Tricks

---

• *