[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_73":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",93,"title","Consistent Hashing","slug","dsa-cheatsheet-part-22-consistent-hashing","excerpt","Visual guide to Consistent Hashing: minimize key redistribution when servers change. See the hash ring with virtual nodes.","# Consistent Hashing\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Distributed hashing technique |\n| **Key Lookup** | O(log n) with binary search on ring |\n| **Add Server** | O(K/n) keys remapped (K=total keys, n=servers) |\n| **Remove Server** | O(K/n) keys remapped |\n| **Best For** | Distributed caches, load balancers, sharding |\n\n**One-liner**: *Hash ring that minimizes key redistribution when servers are added or removed.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how consistent hashing distributes keys and handles server changes:\n\n```visualizer-consistenthashing\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Add keys and see which server they map to\n2. Add a new server - observe only nearby keys move\n3. Remove a server - see keys redistribute to next server\n4. Compare with modulo hashing (all keys would move!)\n\n---\n\n## 🔧 How It Works\n\n### The Problem with Modulo Hashing\n\n```\nTraditional: server = hash(key) % num_servers\n\nWith 3 servers:\n key \"user:1\" → hash=7 → 7 % 3 = 1 → Server 1\n key \"user:2\" → hash=12 → 12 % 3 = 0 → Server 0\n\nAdd 4th server (now % 4):\n key \"user:1\" → 7 % 4 = 3 → Server 3 ← MOVED!\n key \"user:2\" → 12 % 4 = 0 → Server 0 ← stayed\n\nProblem: ~75% of keys move when adding 1 server!\n```\n\n### Consistent Hashing Solution\n\n```\nHash Ring (0 to 2^32):\n 0°\n |\n S1(30°)\n \\\n --- S2(120°)\n /\n S3(240°)\n\nKeys map to next server clockwise:\n hash(\"user:1\") = 50° → Server S2 (next after 50°)\n hash(\"user:2\") = 200° → Server S3 (next after 200°)\n\nAdd server S4 at 180°:\n Only keys between 120° and 180° move to S4\n Other keys stay where they are!\n```\n\n### Virtual Nodes\n\n```\nProblem: Uneven distribution with few servers\nSolution: Each server gets multiple positions (virtual nodes)\n\nServer A: positions at 30°, 150°, 270°\nServer B: positions at 90°, 210°, 330°\n\nBenefits:\n- More even key distribution\n- Smoother rebalancing when servers change\n- Can weight servers (more vnodes = more keys)\n```\n\n---\n\n## 📊 Key Redistribution Comparison\n\n| Scenario | Modulo Hash | Consistent Hash |\n|----------|-------------|-----------------|\n| Add 1 server (3→4) | ~75% keys move | ~25% keys move |\n| Add 1 server (10→11) | ~91% keys move | ~9% keys move |\n| Remove 1 server | Similar high % | Only affected keys |\n\n### Formula\n\n```\nKeys that move when adding server to n existing:\n- Modulo hashing: ~(n/(n+1)) × 100% of keys\n- Consistent hashing: ~(1/(n+1)) × 100% of keys\n```\n\n---\n\n## ✅ When to Use Consistent Hashing\n\n### Good Use Cases\n\n- **Distributed caches** - Memcached, Redis Cluster\n- **Load balancers** - sticky sessions\n- **Database sharding** - distribute data across nodes\n- **CDN routing** - route requests to nearest server\n- **P2P networks** - DHT (Distributed Hash Tables)\n\n### Avoid When\n\n- **Single server** - no distribution needed\n- **Perfect balance required** - may need other algorithms\n- **Data locality matters** - geographic sharding may be better\n- **Simple round-robin suffices** - adds unnecessary complexity\n\n---\n\n## 🔄 Consistent Hashing Variants\n\n| Variant | Feature | Used By |\n|---------|---------|---------|\n| **Basic Ring** | Simple clockwise lookup | Early Dynamo |\n| **Virtual Nodes** | Better distribution | Cassandra, Riak |\n| **Jump Hash** | No ring, O(1) memory | Google |\n| **Rendezvous Hash** | Highest random weight | Many systems |\n| **Maglev** | Minimal disruption, fast | Google LB |\n\n---\n\n## 🧩 Implementation Patterns\n\n### Java Implementation\n\n```java\npublic class ConsistentHash {\n private final TreeMap ring = new TreeMap<>();\n private final int virtualNodes;\n private final HashFunction hashFunction;\n\n public ConsistentHash(int virtualNodes) {\n this.virtualNodes = virtualNodes;\n this.hashFunction = Hashing.murmur3_128();\n }\n\n public void addServer(T server) {\n for (int i = 0; i < virtualNodes; i++) {\n long hash = hash(server.toString() + \"#\" + i);\n ring.put(hash, server);\n }\n }\n\n public void removeServer(T server) {\n for (int i = 0; i < virtualNodes; i++) {\n long hash = hash(server.toString() + \"#\" + i);\n ring.remove(hash);\n }\n }\n\n public T getServer(String key) {\n if (ring.isEmpty()) return null;\n\n long hash = hash(key);\n // Find first server with hash >= key hash\n Map.Entry entry = ring.ceilingEntry(hash);\n\n // Wrap around to first server if none found\n if (entry == null) {\n entry = ring.firstEntry();\n }\n return entry.getValue();\n }\n\n private long hash(String key) {\n return hashFunction.hashString(key, StandardCharsets.UTF_8).asLong();\n }\n}\n```\n\n### Usage Example\n\n```java\nConsistentHash ch = new ConsistentHash<>(150); // 150 vnodes\n\n// Add servers\nch.addServer(\"server-1\");\nch.addServer(\"server-2\");\nch.addServer(\"server-3\");\n\n// Route keys to servers\nString server = ch.getServer(\"user:12345\");\nSystem.out.println(\"Route to: \" + server);\n\n// Add new server - only ~1/4 of keys move\nch.addServer(\"server-4\");\n\n// Same key might now route differently\nString newServer = ch.getServer(\"user:12345\");\n```\n\n### Redis Cluster\n\n```\nRedis Cluster uses hash slots (not consistent hashing ring):\n- 16384 hash slots\n- Each key maps to a slot: CRC16(key) % 16384\n- Each node owns a range of slots\n\nResharding moves slots between nodes\nSimilar benefit: only affected slots' keys move\n```\n\n### Memcached Client\n\n```java\n// Ketama consistent hashing (built into many clients)\nMemcachedClient client = new MemcachedClient(\n new KetamaConnectionFactory(), // Uses consistent hashing\n AddrUtil.getAddresses(\"server1:11211 server2:11211\")\n);\n\n// Keys automatically routed via consistent hashing\nclient.set(\"user:123\", 3600, userData);\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Too Few Virtual Nodes\n\n```java\n// ❌ Few virtual nodes = uneven distribution\nConsistentHash ch = new ConsistentHash<>(1);\n\n// ✅ More virtual nodes = better balance (100-200 typical)\nConsistentHash ch = new ConsistentHash<>(150);\n```\n\n### 2. Poor Hash Function\n\n```java\n// ❌ Simple hash = clustering\nint hash = key.hashCode(); // Java's hashCode isn't uniform\n\n// ✅ Use cryptographic or high-quality hash\nlong hash = Hashing.murmur3_128()\n .hashString(key, StandardCharsets.UTF_8)\n .asLong();\n```\n\n### 3. Not Handling Server Failure\n\n```java\n// ❌ Assuming servers are always available\nString server = ch.getServer(key);\ncache.get(server, key); // What if server is down?\n\n// ✅ Build in replication or fallback\nList servers = ch.getServers(key, 3); // Get 3 replicas\nfor (String server : servers) {\n try {\n return cache.get(server, key);\n } catch (ServerException e) {\n continue; // Try next replica\n }\n}\n```\n\n### 4. Ignoring Hot Spots\n\n```java\n// Problem: Some keys accessed much more than others\n// One server may become overloaded\n\n// Solutions:\n// 1. Random suffix for hot keys\nString cacheKey = hotKey + \"#\" + random.nextInt(10);\n\n// 2. Replicate hot data to multiple servers\n// 3. Use weighted virtual nodes\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: What problem does consistent hashing solve?**\n\n> When servers are added/removed in a distributed system, modulo hashing remaps most keys. Consistent hashing minimizes this: only K/n keys move (K=total keys, n=servers) instead of nearly all keys.\n\n**Q: How does the hash ring work?**\n\n> Both servers and keys are hashed to positions on a ring (0 to 2^32). A key is assigned to the first server found clockwise from its position. Adding a server only affects keys between it and the previous server.\n\n**Q: What are virtual nodes and why use them?**\n\n> Virtual nodes are multiple positions on the ring for each physical server. They improve load distribution (a server with more vnodes handles more keys) and smoother rebalancing. Typically 100-200 vnodes per server.\n\n**Q: Name systems that use consistent hashing.**\n\n> Amazon DynamoDB, Apache Cassandra, Memcached (Ketama), Discord, Akamai CDN. Redis Cluster uses a similar concept with hash slots instead of a ring.\n\n**Q: How do you handle server failures?**\n\n> Replicate keys to multiple servers (next N servers on the ring). When one fails, requests go to the next replica. This is how DynamoDB and Cassandra achieve high availability.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 21: B-Tree](dsa-cheatsheet-part-21-btree)\n\n**Next**: [Part 23: Raft Consensus](dsa-cheatsheet-part-23-raft)\n\n---\n\n**Visualizer**: `ConsistentHashingVisualizer` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.781391Z","createdAt","2026-06-10T07:19:25.781649Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",5,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder",22,"author",{"_31":55,"_98":57,"_99":100,"_101":102,"_103":-5,"_104":-5,"_105":-5,"_106":-5,"_107":-5},"category",{"_31":94,"_73":59,"_35":95,"_76":96,"_97":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":92,"_73":34,"_35":93},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},309,"Sharding","sharding",308,"Hash Ring","hash-ring",307,"Distributed Systems","distributed-systems",306,"consistent-hashing",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]