Designing a Distributed Cache Inspired by The Lord of the Rings: One Insight to Rule Them All

The Quest Begins (The "Why")

Ever felt like your application is constantly begging the database for the same piece of data over and over? I remember a late‑night debugging session where our API latency spiked every time a new feature launched. The culprit? A naïve in‑process cache that lived inside each service instance. When we scaled out, each node kept its own copy, leading to stale reads, wasted memory, and a frantic chase to keep everything in sync.

We needed a shared cache that could survive node restarts, handle network partitions, and still give us sub‑millisecond look‑ups. The obvious answer was to reach for Redis, but simply slapping a Redis client onto our code didn’t solve the underlying distribution problem: how do we decide which node owns which key, and what happens when we add or remove nodes?

That’s when I realized the real dragon we had to slay wasn’t latency—it was consistent data placement across a changing cluster.

The Revelation (The Insight)

The breakthrough came from a simple idea borrowed from distributed hash tables: consistent hashing with virtual nodes. Instead of assigning each physical server a single point on a hash ring, we give it many lightweight “virtual” points (or tokens). When a key arrives, we hash it to a position on the ring and walk clockwise until we hit the first virtual node; the physical server that owns that virtual node becomes the key’s home.

Why does this matter?

• Uniform load – By spreading many tokens per server, the probability of any one server getting a hotspot drops dramatically.
• Minimal reshuffle – Adding or removing a server only affects the keys that map to its tokens, which is a fraction of the total keyspace.
• Straight‑forward implementation – The ring can be represented as a sorted list of hash values; lookups are a binary search.

I still recall the moment the numbers clicked: with 100 virtual nodes per physical host and a 5‑node cluster, adding a sixth node moved only about 2% of the keys. That’s tiny compared to the 20% reshuffle you’d see with a naive modulo‑node-count scheme.

Wielding the Power (Code & Examples)

Below is a compact Go implementation that shows the before‑and‑after. The first snippet is what many teams start with—a simple hash‑mod approach that causes massive reshuffle. The second snippet is the consistent‑hash ring with virtual nodes that puts our insight to work.

The Struggle: Hash‑Mod (the “before”)

type SimpleCache struct {
    nodes []string // e.g. ["redis-01:6379", "redis-02:6379"]
}

func (c *SimpleCache) nodeForKey(key string) string {
    h := fnv.New32a()
    h.Write([]byte(key))
    return c.nodes[int(h.Sum32())%len(c.nodes)]
}

Problem: If we go from 5 nodes to 6, every key’s modulus changes → ~80% of keys get remapped. Cache miss rate spikes, and Redis gets hammered.

The Victory: Consistent Hash Ring (the “after”)

import (
    "hash/fnv"
    "sort"
)

type ring struct {
    // sorted list of hash values
    hashedKeys []uint32
    // map hash -> node name
    hashMap    map[uint32]string
    // number of virtual tokens per physical node
    vnodes int
}

func NewRing(nodes []string, vnodes int) *ring {
    r := &ring{
        hashMap:  make(map[uint32]string),
        vnodes:   vnodes,
    }
    for _, n := range nodes {
        for i := 0; i < vnodes; i++ {
            // hash(node + i) gives a unique token
            h := fnv.New32a()
            h.Write([]byte(fmt.Sprintf("%s:%d", n, i)))
            r.hashedKeys = append(r.hashedKeys, h.Sum32())
            r.hashMap[h.Sum32()] = n
        }
    }
    sort.Slice(r.hashedKeys, func(i, j int) bool {
        return r.hashedKeys[i] < r.hashedKeys[j]
    })
    return r
}

func (r *ring) nodeForKey(key string) string {
    h := fnv.New32a()
    h.Write([]byte(key))
    keyHash := h.Sum32()

    // binary search for the first token >= keyHash
    idx := sort.Search(len(r.hashedKeys), func(i int) bool {
        return r.hashedKeys[i] >= keyHash
    })
    if idx == len(r.hashedKeys) {
        idx = 0 // wrap around
    }
    return r.hashMap[r.hashedKeys[idx]]
}

What changed?

• Each physical node now owns vnodes tokens (we used 100 in production).
• The ring is a sorted list; lookup is O(log N) with a tiny constant.
• Adding a node only remaps the keys that fall into its token ranges—roughly 1 / (nodes * vnodes) of the total.

Common Traps to Avoid

1. Skipping virtual nodes – If you set vnodes = 1, you’re back to the old hotspot problem. Always pick a number that gives you enough granularity (50‑200 works well for most clusters).
2. Forgetting to re‑hash on node removal – When a node leaves, you must delete its tokens from the ring; otherwise look‑ups will point to a dead host.
3. Using a non‑deterministic hash function – Stick to something like FNV or MurmurHash; otherwise the ring will drift between language runtimes.

A quick ASCII diagram helps visualize the ring with virtual nodes:

   hash space (0 → 2^32-1)
   0                                      2^32-1
   |                                      |
   V                                      V
 +----+   +----+   +----+   +----+   +----+
 | v1 |   | v5 |   | v9 |  | v13|  | ...|
 +----+   +----+   +----+   +----+   +----+
   |A|     |B|     |C|      |A|      |
   |   token for node A   token for node B ...

Each vX is a virtual token; the letters show which physical node (A, B, C…) owns it. A key hashes to a spot, we walk clockwise, and the first token we hit tells us the owner.

Why This New Power Matters

With this design in place, our service went from dreading scaling events to welcoming them. Adding a new Redis replica during peak traffic caused only a blip in miss rate—well under 1%—while memory usage stayed balanced across hosts. The system now gracefully handles node failures: when a pod crashes, the keys it owned are seamlessly taken over by the next token holder, and our read‑through logic fills the gap without a cascade of database queries.

Most importantly, the insight is portable. Whether you’re building a rate‑limiter cache, a session store, or a lookup table for feature flags, consistent hashing with virtual nodes gives you a predictable, low‑overhead way to spread load and adapt to change. It’s the kind of tool that makes you feel like you’ve unlocked a secret level in a game—except the reward is real uptime and happier users.

Your Turn

Grab a language of your choice, implement a simple ring with 50 virtual nodes per host, and run a quick experiment: add a node, remove a node, watch how many keys move. Share your results or any tweaks you discover in the comments—let’s see who can push the idea even further!

Happy hashing, and may your cache stay ever warm. 🚀