Chapter 5 Flashcards - Consistent Hashing
flashcards volume1 consistent-hashing
Core Concepts
What is the rehashing problem with traditional modulo hashing?
?
When using hash(key) % N for distribution, changing N (adding/removing servers) causes most keys (~75-90%) to be redistributed to different servers. This leads to cache stampede (all moved keys miss cache and hit database), massive data movement, service degradation, and potential cascading failures.
What is consistent hashing and how does it solve the rehashing problem?
?
Consistent hashing maps both keys and servers to positions on a hash ring (0 to 2^32-1). Each key is assigned to the next server clockwise on the ring. When a server is added or removed, only keys near that server move (~1/N keys on average), not all keys. This minimizes redistribution.
How does the consistent hashing ring work?
?
Step 1: Create a hash ring from 0 to 2^32-1 that wraps around. Step 2: Hash servers onto the ring at specific positions. Step 3: Hash keys onto the ring. Step 4: Each key goes to the next server clockwise from its position on the ring.
What happens when you add a server to a consistent hash ring?
?
The new server takes a position on the ring. Only keys that fall between the new server and the previous server (counterclockwise) get moved to the new server. All other keys remain on their current servers. Approximately 1/N keys move (where N is new number of servers).
What happens when you remove a server from a consistent hash ring?
?
All keys on the removed server move to the next server clockwise on the ring. All other keys remain unchanged. Only keys from the failed server are affected, not the entire keyspace.
Virtual Nodes
What are virtual nodes (vnodes) in consistent hashing and why are they needed?
?
Virtual nodes give each physical server multiple positions on the hash ring instead of just one. They solve the load imbalance problem where servers might get unlucky with ring positions and end up with very large or very small ranges. More vnodes = more even distribution of load.
How many virtual nodes per server do real systems use?
?
Cassandra: 128-256 vnodes per node. DynamoDB: 100-200 vnodes. Riak: 64 vnodes (default). Interview answer: Use 150 vnodes as a reasonable default for good load balancing.
How do virtual nodes work?
?
For server A with 150 vnodes: Create vnodes “A-0”, “A-1”, “A-2”, … “A-149”. Hash each vnode name to get ring position. All vnodes map back to physical server A. Result: Server A has 150 positions on ring instead of 1, providing much better load distribution.
What is the memory overhead of virtual nodes?
?
For 100 servers × 150 vnodes = 15,000 entries. Each entry needs ~40 bytes (32-byte hash + 8-byte pointer). Total: 600 KB. This is negligible compared to benefits, making vnodes essentially free in terms of memory cost.
How can you implement weighted consistent hashing with virtual nodes?
?
Assign different numbers of vnodes based on server capacity. Powerful server (2x capacity) gets 300 vnodes. Normal server gets 150 vnodes. Weak server (0.5x capacity) gets 75 vnodes. This naturally distributes more load to powerful servers.
Implementation
What data structure should you use to implement consistent hashing?
?
Use a sorted list/array of (hash_value, server_id) tuples. Keep it sorted to enable binary search for O(log N) lookups. When adding server, insert vnodes and re-sort. When looking up key, binary search for first position >= key hash.
What is the time complexity of consistent hashing operations?
?
add_server: O(V log N) where V = vnodes per server, N = total vnodes. remove_server: O(N) where N = total vnodes (need to filter out all vnodes). get_server: O(log N) using binary search on sorted ring.
What is the space complexity of consistent hashing?
?
O(S × V) where S = number of servers and V = vnodes per server. For 100 servers with 150 vnodes each = 15,000 entries. With each entry ~40 bytes = ~600 KB total.
What hash functions are good for consistent hashing?
?
MD5 (128-bit, good distribution, widely used), MurmurHash (faster than MD5, non-cryptographic), SHA-1 (160-bit, more secure but slower), xxHash (extremely fast, modern choice). Interview answer: “I’d use MD5 or MurmurHash for speed and uniform distribution.”
How do you handle the wrap-around case in consistent hashing?
?
If key’s hash is greater than all server positions on the ring, wrap around to the first server (position 0). This maintains the circular nature of the ring. In code: if idx >= len(ring): idx = 0.
Real-World Usage
Which major systems use consistent hashing?
?
Amazon DynamoDB (data partitioning), Apache Cassandra (token ring distribution), Memcached (with ketama algorithm), Redis Cluster (hash slots), Akamai CDN (content distribution), Discord (server sharding), Riak (distributed database).
How does DynamoDB use consistent hashing?
?
Each node owns a range of hash values on the ring (100-200 vnodes per node). For replication, uses preference list: key K goes to primary (first server clockwise), replica 1 (next server), replica 2 (next server). If server fails, replicas take over seamlessly with automatic rebalancing.
How does Cassandra use consistent hashing?
?
Uses token ring with 256 vnodes per node by default. Each node owns multiple non-contiguous ranges on the ring. Read/write requests routed to correct node(s) based on key hash. With replication factor 3, each key stored on 3 consecutive nodes clockwise.
How is consistent hashing used for load balancing?
?
Hash requests based on user_id, session_id, or IP address. Route to server using consistent hash. Benefits: Same user always goes to same server (sticky sessions without state), minimal disruption when servers added/removed, better than round-robin for session affinity.
Trade-offs and Comparisons
What are the advantages of consistent hashing?
?
- Minimal redistribution (only 1/N keys move vs all keys). 2. Easy horizontal scalability (add/remove nodes gracefully). 3. Even load distribution (with virtual nodes). 4. Fault tolerance (graceful degradation). 5. No coordination needed (clients compute independently).
What are the disadvantages of consistent hashing?
?
- More complex than simple modulo hashing. 2. Memory overhead for ring structure. 3. No efficient range queries (keys randomly distributed). 4. Hotspot keys still create hotspots on single server. 5. Cascading failure possible (failed server’s keys go to next server).
When should you use consistent hashing?
?
Use when: Distributing data across multiple servers, servers frequently added/removed (elastic scaling), want to minimize data movement during changes, need fault tolerance, building distributed cache or database.
When should you NOT use consistent hashing?
?
Don’t use when: Single server (not distributed), need range queries (use range-based sharding instead), cluster is completely stable (simple modulo is simpler), have strong ordering requirements, all servers always available.
How does consistent hashing compare to modulo hashing?
?
Modulo (hash % N): Very simple, but ~100% keys move when N changes, perfect distribution if hash is good, no memory overhead. Consistent hashing: More complex, only ~1/N keys move, good distribution with vnodes, O(S×V) memory. Use modulo for stable clusters, consistent hashing for dynamic clusters.
How does consistent hashing compare to range-based sharding?
?
Range sharding: Efficient range queries, requires manual rebalancing, common hotspots on popular ranges, simple implementation. Consistent hashing: Inefficient range queries, automatic rebalancing, fewer hotspots, moderate complexity. Use range sharding for ordered data (timestamps), consistent hashing for random access patterns.
What is Jump Hash and how does it compare to consistent hashing?
?
Jump Hash (Google): Simpler algorithm, zero memory overhead, cannot choose which server to add/remove (only supports adding at end), good for controlled scaling. Consistent hashing: More memory, can add/remove any server, better for handling failures. Use Jump Hash when you control additions, consistent hashing when handling dynamic failures.
Interview Scenarios
How would you explain consistent hashing in a system design interview?
?
“Consistent hashing minimizes key redistribution when servers change. We hash both keys and servers onto a ring (0 to 2^32-1). Each key goes to the next server clockwise. When a server is added or removed, only keys near that server move—about 1/N of total keys—instead of nearly all keys like in modulo hashing. We use virtual nodes (150 per server) for even load distribution.”
If asked to implement consistent hashing, what would you outline?
?
“I’d use a sorted array of (hash, server_id) tuples for the ring. For add_server, hash V vnodes and insert into sorted array (O(V log N)). For get_server, hash the key and binary search for next position clockwise (O(log N)). Handle wrap-around when key hash exceeds all servers. Use MD5 or MurmurHash for uniform distribution.”
Calculate: 10 servers, 1M keys. Server fails. How many keys move with modulo vs consistent hashing?
?
Modulo hashing (hash % N): Going from 10→9 servers changes hash % 10 to hash % 9 for nearly all keys. Approximately 900,000 keys move (~90%). Consistent hashing: Only keys from failed server move to next server. Each server has ~100,000 keys, so only 100,000 keys move (10x fewer than modulo).
How would you design a distributed cache using consistent hashing?
?
Use consistent hashing with 150 vnodes per cache server. Client-side hashing: client computes which server owns each key. Replication factor 3: store on 3 consecutive servers for fault tolerance. When cache server fails, clients automatically route to next server (may have replica). Monitor key distribution to detect hotspots. Cache aside pattern: check cache, miss→query DB→populate cache.
Advanced Topics
How do you handle hotspot keys in consistent hashing?
?
Hotspot keys still go to one server. Solutions: 1. Cache hotspot keys more aggressively (in-memory cache before consistent hash). 2. Replicate hot keys across multiple servers. 3. Add jitter to hot key lookups (distribute across replicas). 4. Use application-level sharding for known celebrities/popular items. 5. Rate limiting on hot keys.
What is a preference list in consistent hashing?
?
Used in DynamoDB and Riak for replication. For key K with hash H: Preference list is ordered list of servers responsible for the key. Primary = first server clockwise, Replica 1 = next server, Replica 2 = next server. If primary fails, read/write goes to replicas. Provides fault tolerance and eventual consistency.
How would you implement consistent hashing with replication?
?
For replication factor N, assign each key to N consecutive servers clockwise on ring. Example with RF=3: key at position 150 goes to servers at positions 200 (primary), 300 (replica 1), 400 (replica 2). Writes go to all replicas. Reads can go to any replica (eventual consistency) or require quorum (stronger consistency).
What happens during cascading failures with consistent hashing?
?
If server A fails, its keys move to server B (next clockwise). If B gets overloaded and fails, its keys plus A’s keys move to server C. This can cascade. Solutions: 1. Sufficient capacity headroom (each server can handle 2x normal load). 2. Rate limiting. 3. Circuit breakers. 4. Auto-scaling to add servers quickly. 5. Replication (distribute load across replicas).
Total Cards: 35
Review Time: 25-30 minutes
Priority: HIGH - Core distributed systems concept, frequently asked in interviews
Last Updated: 2026-04-09