Load Balancing: The Matrix of Traffic

The Quest Begins (The "Why")

I still remember the first time our service started to choke under a sudden spike. It was a Friday night, the kind where you’re hoping to push a small feature and head out for pizza, but instead you’re staring at a Grafana dashboard that looks like a heart monitor gone wild. Requests were piling up, some instances were getting hammered while others twiddled their thumbs, and our users were seeing those dreaded 502s. Honestly, it felt like we were trying to fill a bucket with a hose that kept kinking.

We had a naïve round‑robin load balancer sitting in front of a fleet of stateless API nodes. It worked fine when the cluster size was static, but every time we added or removed a node—say, during a deploy or an autoscaling event—the whole mapping got shuffled. Almost every request landed on a different backend, destroying any benefit of local caches or warm connections. The cost? Extra latency, more cache misses, and a frantic on‑call pager that refused to quit.

That night I asked myself: Is there a way to spread load evenly without reshuffling the whole table every time the cluster changes? The answer turned out to be hiding in a concept I’d only seen in distributed systems papers: consistent hashing.

The Revelation (The Insight)

Consistent hashing is like giving each server a spot on a giant circular ring and then mapping each request to the first point clockwise from its hash. The magic is that when you add or remove a node, only the requests that land between the old node’s position and the new node’s position need to move. Everything else stays put. In practice, that means the fraction of reshuffled requests is roughly 1/N where N is the number of nodes—far better than the near‑100% shuffle you get with simple mod‑N or round‑robin.

Here’s the insight that made my eyes light up: You don’t need perfect uniformity to get huge wins; you just need to bound the amount of disruption when the topology changes. A little imbalance is acceptable if it saves you from thrashing caches and rewarming connections on every scaling event.

Let me draw it out so you can see the ring in action.

          0°
        ↑
   [Node A]---[Node B]---[Node C]---[Node D]--- (wrap around)
        ↓                                 ↑
      hash(key1)                     hash(key2)

• Each node gets one or more points on the circle (we often add “virtual nodes” to smooth out hotspots).
• A request’s hash lands somewhere on the ring; we walk clockwise until we hit a node.
• Add a new node? Only the segment between its predecessor and itself changes ownership.

The trade‑off? You need a hash ring data structure and you must decide how many virtual nodes per physical node to keep the distribution even. Too few, and you still get hotspots; too many, and you increase memory and lookup cost. In practice, 100–200 virtual nodes per host gives a sweet spot for most workloads.

Wielding the Power (Code & Examples)

The Struggle: Naïve Round‑Robin

# Simple round‑robin balancer (the “before”)
class RoundRobinLB:
    def __init__(self, backends):
        self.backends = backends
        self.idx = 0

    def pick(self):
        backend = self.backends[self.idx]
        self.idx = (self.idx + 1) % len(self.backends)
        return backend

When backends changes (say we autoscale from 3 to 4 nodes), self.idx keeps counting, but the mapping of which request goes to which node changes for every request after the change. Cache hit rates plummet.

The Victory: Consistent Hashing with Virtual Nodes

import hashlib
import bisect

class ConsistentHashLB:
    def __init__(self, backends, virtual_nodes=100):
        """
        backends: list of strings like "host:port"
        virtual_nodes: how many points per backend on the ring
        """
        self.virtual_nodes = virtual_nodes
        self.ring = dict()          # hash -> backend
        self.sorted_hashes = []     # sorted list of hashes for bisect

        for backend in backends:
            self._add_backend(backend)

    def _hash(self, key):
        # Use a good hash; MD5 is fine for load‑balancing purposes
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def _add_backend(self, backend):
        for i in range(self.virtual_nodes):
            hash_val = self._hash(f"{backend}#{i}")
            self.ring[hash_val] = backend
            bisect.insort(self.sorted_hashes, hash_val)

    def _remove_backend(self, backend):
        for i in range(self.virtual_nodes):
            hash_val = self._hash(f"{backend}#{i}")
            del self.ring[hash_val]
            idx = bisect.bisect_left(self.sorted_hashes, hash_val)
            del self.sorted_hashes[idx]

    def pick(self, key):
        if not self.ring:
            raise RuntimeError("No backends available")
        hash_val = self._hash(key)
        # Find first node clockwise from hash
        idx = bisect.bisect(self.sorted_hashes, hash_val)
        if idx == len(self.sorted_hashes):   # wrap around
            idx = 0
        return self.ring[self.sorted_hashes[idx]]

    # Helper methods to scale up/down
    def add(self, backend):
        self._add_backend(backend)

    def remove(self, backend):
        self._remove_backend(backend)

Why this works better:

• Adding a node only requires hashing its virtual nodes and inserting them into the ring—no need to rebuild the whole table.
• Lookup is O(log V) where V = backends * virtual_nodes (a simple bisect over a sorted list).
• The fraction of keys that move when you add/remove a backend is roughly 1 / N, where N is the number of physical nodes. With 10 nodes, only about 10% of the traffic gets remapped—far less than the 100% shuffle of round‑robin.

Common Pitfalls (the “traps”)

1. Too few virtual nodes – you’ll still see hotspots because the ring is too coarse.
   
   Fix: Start with 100–200 vnodes per host and monitor key distribution.

2. Hash collisions causing duplicate entries – extremely unlikely with a 128‑bit MD5, but if you use a weaker hash you could silently overwrite a node.
   
   Fix: Stick with a strong, well‑distributed hash (MD5, SHA‑1, or xxhash) and treat the ring as a set.

3. Forgetting to rebalance when nodes are removed – if you only call add but never remove, stale entries linger and requests may be sent to dead hosts.
   
   Fix: Wrap scaling events in both remove(old) and add(new) calls.

Why This New Power Matters

With consistent hashing in place, our Friday night incidents turned into a thing of the past. Autoscaling events now cause only a tiny blip in latency, and our local caches stay warm across deploys. The system feels stable, not fragile.

You can now:

• Scale confidently – add or remove instances without fear of a thundering herd of cache misses.
• Build smarter backends – keep per‑node state (like in‑memory caches or warm DB connections) knowing it won’t be invalidated on every scaling step.
• Explain the design – the ring diagram is intuitive enough to draw on a whiteboard during an incident review, making post‑mortems faster.

In short, consistent hashing gave us a predictable, low‑overhead way to spread load while respecting the reality that clusters are never truly static.

---

Your Turn

Grab a language of choice, implement a tiny consistent‑hash ring (the code above is a solid starting point), and throw it in front of a mock service. Watch how the request distribution changes as you add and remove backends. Then, try tweaking the number of virtual nodes and see the effect on hotspots.

What’s the biggest surprise you notice when the ring reshapes itself? Drop a comment or tweet your findings—I’d love to hear how your own quest went! 🚀