Nimendra's Notes 🪴

Consistent Hashing

5 min read

distributedsystem systemdesign

The Simple Magic of Consistent Hashing | Mathias Meyer
[!video]- What is CONSISTENT HASHING and Where is it used?


[!video]- Consistent Hashing: Easy Explanation


[!video]- Consistent Hashing | The Backend Engineering Show


Consistent Hashing | System Design
DS02.6 - DHT (Distributed Hash Table)

The Problem in traditional Approach

👉 Hash Table

we use a hash function to hash our partition keys (i.e. request ID or IP). Then if we use the modulo against the total number of nodes (server or databases). This will give us the node where we want to route our request.

hash_function(key1) --> Hash mod N = Node

N = Total No. of Nodes

The problem with this is if we add or remove a node, it will cause N to change, meaning our mapping strategy will break as the same requests will now map to a different server. As a consequence, the majority of requests will need to be redistributed which is very inefficient.

Consistent Hashing

Consistent hashing is technique used in distributed systems to distribute data evenly across multiple nodes while minimizing the number of data migrations when nodes are added or removed. It is commonly used in distributed caching and load balancing.

How it Works ?

1. Hashing Nodes

We need to way to determine where data should be stored in a distributed system.
Instead of assigning nodes sequentially (Node 1, Node 2, etc.), we use a hash function to map them evenly and randomly to a circular space (called the hash ring).

  • We apply hash function(MD5, SHA-1, MurmurHash) to the node identifier(IP, hostnme or Unique id).
  • The output is mapped to a fixed range, forming a circular space(hash ring)

Example:
Assume we have three nodes: Node A, Node B, and Node C.

hash(Node A) = 12   → Place Node A at position 12
hash(Node B) = 37   → Place Node B at position 37
hash(Node C) = 82   → Place Node C at position 82

Visualizing the Hash Ring (0 - 99 Scale)

0---A(12)------B(37)----------------C(82)---(99)

Nodes are placed randomly on the ring based on their hash values.

2. Hashing Keys

Each data item (key-value pair) also needs a placement rule.
Instead of assigning keys to nodes manually, we use the same hash function to distribute them evenly across the ring.

  • Hash each key using the same hash function as nodes.
  • The key is assigned to the first node in the clockwise direction.

Example:

hash(Key1) = 20  → Assigned to Node B (37)
hash(Key2) = 50  → Assigned to Node C (82)
hash(Key3) = 90  → Assigned to Node A (wrap-around)

Updated Hash Ring with Keys

 0---A(12)------B(37)------C(82)---(99)
         |       |         |
      (Key1)  (Key2)    (Key3)

**One of the biggest advantages of consistent hashing is that when nodes are added or removed, only a few keys need to be reassigned.**

Adding a Node

Adding a new node D at position 55:

hash(Node D) = 55  → Insert Node D into the ring

Updated hash ring:

 0---A(12)------B(37)------D(55)------C(82)---(99)
         |       |          |         |
      (Key1)  (Key2*)    (Key2)    (Key3)

Caution

A problem with basic consistent hashing is uneven data distribution when nodes are placed unevenly on the ring.
In theory, consistent hashing should distribute the load evenly however it doesn’t happen in practice. Usually, the load distribution is uneven and one server may end up handling the majority of the request becoming a hotspot, essentially a bottleneck for the system. We can fix this by adding extra nodes but that can be expensive.
To fix this problem Use Virtual Nodes(VNodes)

Virtual Nodes

Instead of one position per node, we create multiple virtual nodes (VNodes) per node.

  1. Each physical node is assigned multiple virtual nodes.
  2. Virtual nodes evenly distribute data across multiple positions.
  3. When a node fails, only some virtual nodes are reassigned.

Consistent Hashing And DHT

Consistent Hashing and Distributed Hash Tables (DHTs) are closely related because DHTs rely on consistent hashing to efficiently distribute and locate data across a distributed network of nodes.

DHT Uses Consistent Hashing for Data Placement

  • In a DHT, keys (data items) are distributed among nodes in a decentralized way.
  • Consistent hashing determines which node is responsible for storing a given key.
  • This allows the system to dynamically add or remove nodes without major disruptions.

How a DHT Uses Consistent Hashing (Example: Chord DHT)

Nodes and Data Items Are Hashed

  • Each node is assigned a unique ID (hash(node_id)).
  • Each key (data item) is also hashed (hash(key)).
  • The key is stored on the first node clockwise that has an ID greater than or equal to the key’s hash.

Node Lookup Using Finger Tables

  • Instead of searching sequentially, DHTs like Chord use a finger table to jump across the ring efficiently (O(log N) lookups).

Handling Node Joins/Failures Efficiently

  • When a node joins, it only takes responsibility for some keys from its successor instead of rehashing all data.
  • When a node fails, its data is redistributed among nearby nodes without impacting the whole system.

DHT Implementations Using Consistent Hashing

  • Chord → A structured P2P network with finger tables for fast lookups.
  • Kademlia (Used in BitTorrent, Ethereum, IPFS) → Uses XOR-based routing.
  • Pastry → A prefix-based lookup approach for decentralized applications.
  • Amazon DynamoDB → Uses a DHT-like architecture for highly available key-value storage.

Backlinks

Graph View