Let's Understand & Implement Consistent Hashing

27 February 2025 · 6 min read

Recently I’ve been learning about distributed systems and I came across a very interesting concept “Consistent Hashing”. It is one of the fundamental techniques used in distributed systems.

What Is Consistent Hashing?

Consistent hashing is a key distribution technique that ensures easy and smooth mapping of keys to servers to minimize data movement when nodes are added or removed. Unlike traditional hashing methods, where adding or removing a server changes the hash distribution significantly, consistent hashing reduces this impact.

It goes with mapping both servers (nodes) and keys to a circular hash space. When a request comes in, the system moves clockwise along the ring to find the closest node, which will be responsible for that key. It will store key and value data and can also be used while retrieving the same.

consistent-hashing

Use Cases

Consistent hashing is widely used in distributed systems.
Load Balancing: Can be used when requests should consistently map to the same backend, although virtual nodes and a suitable hash function are needed for good distribution.
Distributed Caching (e.g., Memcached-style caches): Helps map cache keys to stable nodes while minimizing remapping when nodes change. Redis Cluster uses hash slots rather than this classic ring algorithm.
Database Sharding: Efficiently distributes and saves database records across multiple database servers.

Why Is Consistent Hashing Important?

Imagine you have a set of servers handling API requests. A traditional hash function could distribute these requests among servers, but as soon as a server is added or removed, the entire mapping breaks, and most of the data needs to be rebalanced. This can cause cache misses, which increase latency and unnecessary load on the system.

Consistent hashing solves this by ensuring that only a small fraction of keys need to be remapped when a server is added or removed. This makes the system highly scalable and resilient.

Implementation

For simplicity, this implementation places physical nodes directly on the ring. Production systems often use virtual nodes (multiple positions per physical node) to improve key distribution and make node changes smoother.

Now, let’s talk about the implementation of consistent hashing in Go. My implementation involves a Consistent Hash Ring that maintains a sorted list of node hashes and efficiently assigns keys to nodes. Here’s how it works:

Base Structs:

 1type Node struct {
 2	ID   string
 3	Keys map[string]string
 4}
 5
 6type ConsistentHashRing struct {
 7	mu     sync.RWMutex
 8	nodes  map[uint32]*Node
 9	hashes []uint32
10}
11
12func NewConsistentHashRing() *ConsistentHashRing {
13	return &ConsistentHashRing{
14		nodes:  make(map[uint32]*Node),
15		hashes: []uint32{},
16	}
17}

1. Hashing Function

I used Murmur3 because it is a fast, non-cryptographic hash function that is suitable for this kind of ring lookup. I would benchmark different hashes for a production workload rather than assume one is always faster or better distributed.

1func hashFunction(key string) uint32 {
2  return murmur3.Sum32([]byte(key))
3}

2. Adding Nodes to the Ring

When a new server is added, it is assigned a hash value and placed on the ring.

 1func (chr *ConsistentHashRing) AddNode(id string) {
 2  chr.mu.Lock()
 3  defer chr.mu.Unlock()
 4
 5  hash := hashFunction(id)
 6  if _, exists := chr.nodes[hash]; exists {
 7    return // Hash collision or duplicate node ID.
 8  }
 9
10  newNode := &Node{
11    ID:   id,
12    Keys: make(map[string]string),
13  }
14
15  chr.nodes[hash] = newNode
16  chr.hashes = append(chr.hashes, hash)
17  slices.Sort(chr.hashes)
18
19  // Move keys that now belong to the new node from its successor.
20  if len(chr.hashes) > 1 {
21    newIndex := 0
22    for i, h := range chr.hashes {
23      if h == hash {
24        newIndex = i
25        break
26      }
27    }
28    successorIndex := (newIndex + 1) % len(chr.hashes)
29    successor := chr.nodes[chr.hashes[successorIndex]]
30
31    for key, val := range successor.Keys {
32      idx := chr.GetNextNodeIndex(hashFunction(key))
33      if chr.hashes[idx] == hash {
34        newNode.Keys[key] = val
35        delete(successor.Keys, key)
36      }
37    }
38  }
39}

3. Finding the Nearest Node

To locate the closest node for a given key, I move clockwise along the sorted list of hashes.

1func (chr *ConsistentHashRing) GetNextNodeIndex(hash uint32) int {
2  for i, h := range chr.hashes {
3    if h >= hash {
4      return i
5    }
6  }
7  return 0 // Wrap around to the first node
8}

4. Storing and Retrieving Data

Each node holds a set of keys. When a key-value pair is stored, it is mapped to the correct node.

 1func (chr *ConsistentHashRing) getNode(key string) *Node {
 2  if len(chr.hashes) == 0 {
 3    return nil
 4  }
 5
 6  hash := hashFunction(key)
 7  idx := chr.GetNextNodeIndex(hash)
 8  return chr.nodes[chr.hashes[idx]]
 9}
10
11func (chr *ConsistentHashRing) GetNode(key string) *Node {
12  chr.mu.RLock()
13  defer chr.mu.RUnlock()
14  return chr.getNode(key)
15}
16
17func (chr *ConsistentHashRing) StoreKey(key, val string) {
18  chr.mu.Lock()
19  defer chr.mu.Unlock()
20
21  node := chr.getNode(key)
22  if node != nil {
23    node.Keys[key] = val
24  }
25}

To Retrieve a Key:

 1func (chr *ConsistentHashRing) RetrieveKey(key string) (string, error) {
 2  chr.mu.RLock()
 3  defer chr.mu.RUnlock()
 4
 5  node := chr.getNode(key)
 6  if node == nil {
 7    return "", errors.New("no node found")
 8  }
 9  val, ok := node.Keys[key]
10  if !ok {
11    return "", errors.New("key not found")
12  }
13  return val, nil
14}

5. Handling Node Removal

When a server is removed, this toy implementation transfers its in-memory keys to the next available node. A production distributed system would normally perform controlled data migration and replication. The example is intentionally focused on ring lookup rather than implementing a complete distributed storage system.

 1func (chr *ConsistentHashRing) RemoveNode(id string) {
 2  chr.mu.Lock()
 3  defer chr.mu.Unlock()
 4
 5  hash := hashFunction(id)
 6  node, exists := chr.nodes[hash]
 7  if !exists {
 8    return
 9  }
10
11  if len(chr.hashes) == 1 {
12    delete(chr.nodes, hash)
13    chr.hashes = nil
14    return
15  }
16
17  nextNodeIndex := chr.GetNextNodeIndex(hash)
18  nextNode := chr.nodes[chr.hashes[nextNodeIndex]]
19  maps.Copy(nextNode.Keys, node.Keys)
20
21  delete(chr.nodes, hash)
22
23  for i, h := range chr.hashes {
24    if h == hash {
25      chr.hashes = slices.Delete(chr.hashes, i, i+1)
26      break
27    }
28  }
29}

6. Printing Node Data:

1func (chr *ConsistentHashRing) PrintRing() {
2	for _, h := range chr.hashes {
3		fmt.Printf("Node: %s \t\t Hash: %d \t\t Total Keys: %v\n", chr.nodes[h].ID, h, len(chr.nodes[h].Keys))
4	}
5}

Source Code : GitHub

Final Thoughts

Consistent hashing is a useful technique for keeping key-to-node mappings relatively stable when the membership of a distributed system changes. This implementation demonstrates the ring and lookup mechanics; it is intentionally a toy and does not implement replication or full production-grade data migration.

If you have suggestions to optimize this implementation, drop them in the comments. I am always looking to improve my code.