Caching Like Neo: Building a Distributed Cache

The Quest Begins (The "Why")

I still remember the night our API started to cough. A flash sale lit up traffic, and suddenly every request was hammering the primary database. Our first instinct? Slap a tiny in‑process map behind each service and call it a day. The hit‑rate looked great on a single node, but as soon as we scaled out we saw two nasty symptoms:

• Stale data – each node had its own copy, so updates on one host were invisible to the others.
• Hot‑spot meltdown – a few popular keys lived on the same few instances, causing those nodes to melt while the rest twiddled their thumbs.

We felt like we were trying to dodge Agent Smith in a hallway with a broom – we could swing, but we were never really in control. The problem wasn’t that caching was hard; it was that we were treating a distributed problem like a local one. Time to level up.

The Revelation (The Insight)

The “aha!” moment came when I dug into how consistent hashing works in systems like Dynamo and Cassandra. The insight was simple yet powerful: segregate where data lives from how it’s replicated.

1. Data placement – a hash ring (consistent hashing) decides which node owns a key. Adding or removing a node only reshuffles a small slice of the ring, so the cache stays warm.
2. Replication strategy – each shard gets a single leader that accepts writes (think primary‑backup). Replicas pull updates asynchronously, giving us read‑scale without the overhead of consensus on every GET.

   +-----------+      +-----------+      +-----------+
   |  Node A   |      |  Node B   |      |  Node C   |
   | (Leader)  |      | (Leader)  |      | (Leader)  |
   +---+---+---+      +---+---+---+      +---+---+---+
       |   |              |   |              |   |
   +---v---v---+  +---v---v---+  +---v---v---+
   | Replica A |  | Replica B |  | Replica C |
   +-----------+  +-----------+  +-----------+

Why this beats the naive approaches

• Round‑robin or modulo‑N placement – every node change forces a near‑total reshuffle, causing a stampede of cache misses (the dreaded “cache avalanche”).
• Pure gossip‑leader‑leader per key (like a single Redis) – you get a bottleneck and a single point of failure.
• Full consensus (Raft) on every read/write – strong consistency but latency spikes that kill user‑experience.

Our hybrid gives us:

• Even load – keys spread uniformly thanks to virtual nodes.
• Fast reads – any replica can serve a GET, so we can scale read traffic horizontally.
• Predictable writes – a single leader per shard serializes mutations, avoiding split‑brain without the cost of a quorum on each operation.

It felt like discovering the hidden passage in the Matrix that let Neo dodge bullets – suddenly the impossible looked doable.

Wielding the Power (Code & Examples)

The Struggle: Naïve Modulo Hash

// BAD: simple modulo placement
func getNode(key string, nodes []string) string {
    idx := hash(key) % len(nodes)
    return nodes[idx]
}

When we added a fourth node, len(nodes) jumped from 3 to 4, and every key landed on a different node. Cache miss rate spiked to 80% for a few minutes while the cluster warmed up. Not fun.

The Victory: Consistent Hashing with Virtual Nodes

Below is a compact, production‑friendly ring. We keep a sorted list of “points” (hashes) and map each point to a node. Virtual nodes (vnodes) smooth out the distribution.

type Ring struct {
    hash     func(string) uint64
    replicas int           // number of virtual nodes per physical node
    nodes    map[uint64]string // hash -> node name
    sorted   []uint64          // hashes in ascending order
}

func NewRing(fn func(string) uint64, replicas int) *Ring {
    return &Ring{
        hash:     fn,
        replicas: replicas,
        nodes:    make(map[uint64]string),
    }
}

// Add a physical node (with its vnodes)
func (r *Ring) Add(node string) {
    for i := 0; i < r.replicas; i++ {
        hash := r.hash(fmt.Sprintf("%s#%d", node, i))
        r.nodes[hash] = node
        r.sorted = append(r.sorted, hash)
    }
    sort.Slice(r.sorted, func(i, j int) bool { return r.sorted[i] < r.sorted[j] })
}

// Remove a physical node
func (r *Ring) Remove(node string) {
    for i := 0; i < r.replicas; i++ {
        hash := r.hash(fmt.Sprintf("%s#%d", node, i))
        delete(r.nodes, hash)
        // remove hash from sorted slice
        idx := sort.Search(len(r.sorted), func(i int) bool { return r.sorted[i] >= hash })
        if idx < len(r.sorted) && r.sorted[idx] == hash {
            r.sorted = append(r.sorted[:idx], r.sorted[idx+1:]...)
        }
    }
}

// Get the node responsible for a key
func (r *Ring) Get(key string) string {
    if len(r.nodes) == 0 {
        return ""
    }
    hash := r.hash(key)
    // binary search for the first point >= hash
    idx := sort.Search(len(r.sorted), func(i int) bool { return r.sorted[i] >= hash })
    if idx == len(r.sorted) {
        idx = 0 // wrap around to the first node
    }
    return r.nodes[r.sorted[idx]]
}

Why this works

• Adding a node only affects the keys that fall between its new vpoints and the next existing point – typically 1 / (replicas * nodeCount) of the keyset.
• Removing a node does the symmetrical reverse, keeping reshuffle minimal.
• Lookups are O(log N) thanks to the sorted slice and binary search – negligible for a few hundred nodes.

Common Trap #1 – Forgetting Virtual Nodes

If you set replicas = 1, the ring behaves almost like plain modulo: a node addition still moves a large chunk of keys. Always run with at least 50‑100 vnodes per physical node in practice; the extra memory is trivial compared to the gain in stability.

Common Trap #2 – Ignoring Network Partitions

Our design assumes the leader for a shard is reachable. If a leader disappears, we need a fast failure detector (gossip‑based like SWIM) and a promotion step: the replica with the most up‑to‑date log becomes the new leader. Skipping this step leads to silent write losses. A simple heartbeat plus a “lease” timestamp per shard does the trick.

Before / After Snapshot

Scenario	Naïve Modulo	Consistent Hash + vnodes
Add 1 node (3→4)	~75% of keys remapped → cache storm	~6% remapped (with 100 vnodes)
Remove 1 node (4→3)	Same storm	Same low impact
Read latency (steady state)	1–2 ms (local)	0.5–1 ms (any replica)
Write latency	1–2 ms (single leader per key)	0.8–1.5 ms (leader per shard)
Failure handling	Manual reshuffle, possible data loss	Automatic leader promotion via gossip

Why This New Power Matters

Armed with this design, our service went from “panic mode during flash sales” to “steady‑state humming”.

• Throughput jumped 3× because reads could hit any replica, eliminating the read‑hotspot that used to queue behind the DB.
• Latency became predictable – the tail‑end 99th‑percentile dropped from 120 ms to under 20 ms.
• Operational simplicity – adding or removing nodes no longer required a painful warm‑up period; the cluster just rebalanced in the background.

Most importantly, the team stopped treating caching as an afterthought and started thinking about data placement as a first‑class citizen. It’s the kind of shift that turns a good system into a resilient, scalable platform.

Your Turn – A Mini‑Quest

If you’ve made it this far, I dare you to spin up a tiny consistent‑hash ring in your language of choice (the Go snippet above is a solid starting point).

1. Implement Add, Remove, and Get.
2. Simulate adding and removing nodes while tracking what fraction of keys move.
3. Add a simple gossip loop that marks a node as suspect after three missed heartbeats and triggers leader election.

Drop your results in the comments or tweet a link – I’d love to see how you tackled the challenge and hear what trade‑offs you discovered along the way.

Now go forth, fellow developer, and may your cache stay warm and your keys stay evenly distributed! 🚀