📑 Table of Contents

  1. Problem Understanding
  2. Requirements & Scope
  3. Basic Consistent Hashing
  4. Virtual Nodes Solution
  5. Implementation Details
  6. Benefits & Real-world Applications
  7. Advanced Considerations

1. Problem Understanding

🧠 What is Consistent Hashing?

Consistent hashing is a special kind of hashing technique that minimizes the number of keys that need to be remapped when the hash table is resized. When a hash table is resized using consistent hashing, only k/n keys need to be remapped on average, where k is the number of keys and n is the number of slots.

Traditional vs Consistent Hashing:

❌ The Rehashing Problem

Traditional Hash Method:

serverIndex = hash(key) % N

where N is the size of the server pool.

Example with 4 servers:

Key Hash Value Server Index (hash % 4)
key0 18358617 1
key1 26143584 0
key2 18131146 2
key3 35863496 0

Problem When Server Fails:

When server 1 goes offline (N becomes 3), using hash % 3:

Key Hash Value New Server Index (hash % 3) Original Server
key0 18358617 2 1
key1 26143584 0 0
key2 18131146 1 2
key3 35863496 0 0

Result: Most keys are redistributed, causing a storm of cache misses.

✅ Why Use Consistent Hashing?

  1. Minimize redistribution: Only affected keys need to move when servers change
  2. Horizontal scaling: Easy to add/remove servers with minimal impact
  3. Load balancing: More even distribution of data across servers
  4. Hotspot mitigation: Prevents excessive load on specific servers

2. Requirements & Scope

🎯 Key Clarifying Questions

Scale Considerations:

Distribution Requirements:

Performance Requirements:

Data Characteristics:

Consistency & Replication:

Operational Requirements:

Business Constraints:

📋 Functional Requirements

📊 Non-Functional Requirements

3. Basic Consistent Hashing

🔄 Hash Space and Hash Ring

Hash Space:

Hash Ring Formation:

Hash Ring Figure: Hash space converted to ring structure

🖥️ Hash Servers

Server Mapping:

Example:

server0 → hash("192.168.1.1") → position on ring
server1 → hash("192.168.1.2") → position on ring
server2 → hash("192.168.1.3") → position on ring
server3 → hash("192.168.1.4") → position on ring

🔑 Hash Keys

Key Mapping:

🔍 Server Lookup Algorithm

Basic Rule: > To determine which server stores a key, go clockwise from the key’s position until the first server is found.

Example:

➕ Adding a Server

Minimal Impact: When server4 is added:

➖ Removing a Server

Graceful Redistribution: When server1 is removed:

4. Virtual Nodes Solution

⚠️ Problems with Basic Approach

Issue 1: Uneven Partitions

Issue 2: Non-uniform Key Distribution

🌐 Virtual Nodes Concept

Definition:

Example Configuration:

Physical Server 0 → virtual nodes: s0_0, s0_1, s0_2
Physical Server 1 → virtual nodes: s1_0, s1_1, s1_2

Lookup Process:

  1. Go clockwise from key position
  2. Find first virtual node
  3. Map virtual node to physical server

📊 Benefits of Virtual Nodes

Better Distribution:

Balanced Load:

Trade-offs:

🎯 Optimal Virtual Node Count

Guidelines:

Selection Criteria:

5. Implementation Details

🔍 Finding Affected Keys

When Adding a Server:

  1. Identify the newly added server position
  2. Move anticlockwise to find the previous server
  3. Keys between previous server and new server need redistribution

When Removing a Server:

  1. Identify the removed server position
  2. Move anticlockwise to find the previous server
  3. Keys between previous server and removed server move to next server clockwise

Example - Adding Server4:

Example - Removing Server1:

🛠️ Data Structures

Hash Ring Implementation:

class ConsistentHash:
    def __init__(self, virtual_nodes=150):
        self.virtual_nodes = virtual_nodes
        self.ring = {}  # position -> server mapping
        self.sorted_keys = []  # sorted positions on ring
        
    def add_server(self, server):
        for i in range(self.virtual_nodes):
            key = self.hash(f"{server}:{i}")
            self.ring[key] = server
            self.sorted_keys.append(key)
        self.sorted_keys.sort()
    
    def get_server(self, key):
        if not self.ring:
            return None
        
        hash_key = self.hash(key)
        # Binary search for first server clockwise
        idx = bisect.bisect_right(self.sorted_keys, hash_key)
        if idx == len(self.sorted_keys):
            idx = 0
        return self.ring[self.sorted_keys[idx]]

⚡ Performance Optimization

Efficient Lookup:

Memory Management:

6. Benefits & Real-world Applications

✅ Key Benefits

Minimized Redistribution:

Horizontal Scalability:

Load Balancing:

Fault Tolerance:

🏢 Real-world Applications

Amazon DynamoDB:

Apache Cassandra:

Discord Chat Application:

Akamai CDN:

Google Maglev Load Balancer:

7. Advanced Considerations

🧠 Design Trade-offs

Virtual Nodes Count:

Hash Function Selection:

Replication Strategy:

🎯 Advanced Interview Topics

1. Weighted Consistent Hashing

Challenge: > “How would you handle servers with different capacities using consistent hashing?”

Solution:

2. Consistent Hashing with Bounded Loads

Problem: > “What if consistent hashing causes some servers to become overloaded?”

Approach:

3. Handling Network Partitions

Question: > “How does consistent hashing behave during network partitions?”

Considerations:

4. Dynamic Rebalancing

Challenge: > “How do you minimize data movement during rebalancing?”

Strategies:

5. Multi-dimensional Hashing

Advanced Topic: > “How would you extend consistent hashing for multiple attributes (geographic location, data type, etc.)?”

Implementation:

🔧 Implementation Best Practices

Hash Function Choice:

Virtual Node Management:

Monitoring and Metrics:

Testing Strategies:

✅ Design Process Summary

Step-by-Step Approach

  1. Understand the problem

    • Identify redistribution challenges with traditional hashing
    • Define scale and performance requirements

  2. Choose hash function

    • Select cryptographic hash for good distribution
    • Consider performance requirements

  3. Implement basic consistent hashing

    • Create hash ring structure
    • Implement clockwise lookup algorithm

  4. Add virtual nodes

    • Determine optimal virtual node count
    • Implement virtual-to-physical server mapping

  5. Handle dynamic operations

    • Implement server addition/removal logic
    • Plan data redistribution strategy

  6. Optimize and monitor

    • Measure distribution quality
    • Monitor system performance

Key Takeaways

Interview Success Tips

  1. Start with the problem: Explain why traditional hashing fails
  2. Show progression: Basic consistent hashing → virtual nodes solution
  3. Discuss trade-offs: Memory vs. balance, simplicity vs. performance
  4. Mention real applications: DynamoDB, Cassandra, CDNs
  5. Consider edge cases: Server failures, network partitions, hotspots

📚 Reference Materials

The following resources provide additional depth and implementation details for consistent hashing:

Fundamental Research

Industry Implementations

Technical Deep Dives

Implementation Guides