Mastering Consistent Hashing in Go: From Simple Modulo to Virtual Nodes

Why Simple Modulo Sharding Breaks When Nodes Change

In a single‑machine setup, a map can handle caching, task distribution, and data routing, but once a Go project scales to multiple nodes, the question "Which node should a request be routed to?" becomes critical. Node count can increase, decrease, or be dynamic, and a wrong routing rule can invalidate large amounts of data or even crash the system.

1. The Most Obvious Solution: Modulo Sharding

Many early systems use a simple formula: nodeIndex := hash(key) % nodeCount Advantages: extremely easy to implement, low overhead, sufficient for single‑machine scenarios.

Implementation is trivial

Performance cost is minimal

Works fine when the node count is fixed

The fatal flaw appears when the node count changes: almost every key’s mapping shifts, causing massive cache invalidation, full data migration, and sudden system jitter.

2. Consistent Hashing Aims for Stability, Not Uniformity

When nodes change, affect as few existing keys as possible.

Consistent hashing introduces a hash ring where both nodes and keys are placed. A key is assigned to the first node encountered when moving clockwise on the ring.

Only keys that fall into the departing node’s segment are affected.

3. Basic Consistent‑Hash Implementation (No Virtual Nodes)

Data Structure

type ConsistentHash struct {
    hashFunc func(data []byte) uint32
    nodes    []uint32          // Sorted hash ring nodes
    nodeMap  map[uint32]string // Hash value → node name
    mu       sync.RWMutex
}

Initialization

func NewConsistentHash() *ConsistentHash {
    return &ConsistentHash{
        hashFunc: crc32.ChecksumIEEE,
        nodeMap:  make(map[uint32]string),
    }
}

Adding a Node

func (c *ConsistentHash) AddNode(node string) {
    c.mu.Lock()
    defer c.mu.Unlock()

    hash := c.hashFunc([]byte(node))
    c.nodes = append(c.nodes, hash)
    c.nodeMap[hash] = node
    sort.Slice(c.nodes, func(i, j int) bool { return c.nodes[i] < c.nodes[j] })
}

Getting the Node for a Key

func (c *ConsistentHash) GetNode(key string) string {
    c.mu.RLock()
    defer c.mu.RUnlock()
    if len(c.nodes) == 0 {
        return ""
    }
    hash := c.hashFunc([]byte(key))
    idx := sort.Search(len(c.nodes), func(i int) bool { return c.nodes[i] >= hash })
    if idx == len(c.nodes) {
        idx = 0
    }
    return c.nodeMap[c.nodes[idx]]
}

This version already guarantees that node changes only affect a limited range of keys.

4. Why Virtual Nodes Are Almost Always Needed

With few real nodes, data distribution becomes uneven—some nodes hold many keys while others stay idle. The remedy is to introduce virtual nodes , each real node mapping to multiple points on the ring.

5. Consistent Hashing with Virtual Nodes

Core Idea

Map each real node to several virtual nodes.

Distribute virtual nodes uniformly on the hash ring.

Map the selected virtual node back to its real node.

Adjusted Data Structure

type ConsistentHash struct {
    hashFunc func(data []byte) uint32
    replicas int               // Number of virtual nodes per real node
    nodes    []uint32          // Hash ring
    nodeMap  map[uint32]string // Virtual node hash → real node name
    mu       sync.RWMutex
}

Initialization with Replicas

func NewConsistentHash(replicas int) *ConsistentHash {
    return &ConsistentHash{
        hashFunc: crc32.ChecksumIEEE,
        replicas: replicas,
        nodeMap:  make(map[uint32]string),
    }
}

Adding a Node (Including Virtual Nodes)

func (c *ConsistentHash) AddNode(node string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    for i := 0; i < c.replicas; i++ {
        virtualKey := node + "#" + strconv.Itoa(i)
        hash := c.hashFunc([]byte(virtualKey))
        c.nodes = append(c.nodes, hash)
        c.nodeMap[hash] = node
    }
    sort.Slice(c.nodes, func(i, j int) bool { return c.nodes[i] < c.nodes[j] })
}

Getting the Node (Logic Unchanged)

func (c *ConsistentHash) GetNode(key string) string {
    c.mu.RLock()
    defer c.mu.RUnlock()
    if len(c.nodes) == 0 {
        return ""
    }
    hash := c.hashFunc([]byte(key))
    idx := sort.Search(len(c.nodes), func(i int) bool { return c.nodes[i] >= hash })
    if idx == len(c.nodes) {
        idx = 0
    }
    return c.nodeMap[c.nodes[idx]]
}

Virtual nodes make the data distribution much more balanced, which is why most production systems adopt this pattern.

6. Typical Go Use Cases for Consistent Hashing

Distributed cache routing : local caches, Redis clusters, multi‑level cache hierarchies.

Task dispatch : assign workers to specific key ranges to avoid frequent state migration.

Session affinity : keep the same user’s requests on the same node, reducing synchronization overhead.

7. Common Pitfalls Engineers Overlook

1️⃣ Choosing the Hash Function

The hash function determines distribution quality.

Different business scenarios may replace the implementation.

2️⃣ Too Many or Too Few Virtual Nodes

Too few leads to uneven distribution.

Too many increases maintenance cost.

3️⃣ Consistent Hashing Is Not a Silver Bullet

Node performance variance, hot keys, and data skew still need additional strategies.

These issues often require combined business‑level policies to resolve.

Conclusion

Consistent hashing is not a complex algorithm, but it solves a highly practical problem: maintaining overall system stability amid node changes. When you adopt it in a Go project, it usually signals that the system has entered a more mature, distributed stage.