Redis Caching & Pooling
Podcast · Redis Caching & Pooling

Thundering Herds and Redis Eviction Mechanics

by ZumiLabs · 17m
0:00 17m

Transcript

Made automatically from the audio, so it may contain mistakes. Click a line to play from there.

Host 1

You have this highly successful web service, right? The architecture's just humming along beautifully.

Host 2

Right.

Host 1

And then out of nowhere, a single viral event hits. Like a massive celebrity tweets a link to a specific product on your platform, or maybe a huge jackpot drops in your game.

Host 2

Oh yeah. The classic spike.

Host 1

Exactly. Suddenly you are just slammed with an unprecedented hotkey spike.

Host 2

And initially, you know, your infrastructure absorbs the blow. The system is serving that one cached item perfectly from memory.

Host 1

Right. If you're looking at your monitoring dashboards, everything seems green.

Host 2

Completely green. The CPU load on the database is negligible at this point.

Host 1

But time is ticking because, well, every cached item has a time to live, TTL. Yep. And eventually that single viral key expires.

Host 2

And the very next millisecond, you experience what the AWS architecture docs refer to as a thundering herd.

Host 1

A thundering herd.

Host 2

Yeah. Because that item is no longer in the cache. Every single application server in your fleet simultaneously experiences a cache miss. Wow. So thousands of threads pivot, like all at the exact same moment and fire a request directly to your backend database for that exact same piece of data.

Host 1

So within milliseconds, your database connection cues just fill up. Your HTTP connections max out.

Host 2

It's instant.

Host 1

Yeah. And CPU threads across your entire stack saturate as they just wait for the database to respond. Your health checks start failing because the servers can't even process ping requests anymore. And well, the entire cluster basically enters a death spiral.

Host 2

And if you're thinking, you know, I'll just add more cache servers, that doesn't save you. Right. Because that specific hotkey is mathematically hashed and pinned to one single slot on one single cache node.

Host 1

So adding a hundred extra nodes does absolutely nothing to distribute the load of a single viral key.

Host 2

Exactly. Right. And meanwhile, your database is already melting down. It is a textbook cascading failure, and it happens to some of the biggest tech companies in the world.

Host 1

Well, welcome to this deep dive into our sources on internal web architecture and infrastructure components.

Host 2

Glad to be here.

Host 1

This is episode seven of the series. And explicitly, because we already covered HTTP and CDN edge caching back in episode two, and we did service resilience in episode six. Today's deep dive is strictly focused on the internal layers.

Host 2

Right. So we are looking exclusively at application to data store caching, Redis eviction internals, and the underlying physics of database connections.

Host 1

Exactly. The goal here is to decode these architectural sources, like the AWS Builder Center, Google's SRE practices, Envoy documentation, and Redis internals. We want to really understand why these crashes happen and how to engineer your caching and connection layers to prevent them.

Host 2

Yeah, to really get into the mechanics of it.

Host 1

Okay. Let's unpack this. To understand why that cold open ended in the system crash, we first have to look at where our data actually lives and the gap between the application and the database.

Host 2

Right.

Host 1

So we have two main layers, L1 and L2 caches. Let's contrast those. L1 is your local on-box cache. You build it right into the application's process memory, like a an in-memory hash table in Java or say Node.js.

Host 2

And it is blindingly fast.

Host 1

Super fast. Zero network offs.

Host 2

But L1 comes with this severe structural flaw when it comes to cache coherence, right? Imagine a user refreshing their browser. Request one hits server A, which has an L1 cache showing a product price of $10. Okay. But request two hits server B, which hasn't updated its L1 cache yet, and it shows $12.

Host 1

So the user just sees the price jumping around.

Host 2

Exactly. And furthermore, when you deploy new application code, those servers restart. They wake up with completely empty L1 caches.

Host 1

Which is what we call a cold start. And a cold start instantly stirps away your defense, just bombarding your database with raw traffic.

Host 2

Yep.

Host 1

That is why the architecture almost always shifts to an L2, the external cache. We're talking about a central Redis or Memcache cluster.

Host 2

Right. Because all your application servers check the same shared external cache, so the coherence problem vanishes.

Host 1

Everyone sees the $10 price.

Host 2

Exactly. And it survives application deployments because the cache lives on completely separate hardware.

Host 1

But the compromise is network overhead.

Host 2

Always. You're introducing a network hop for every single cache check, plus, you know, serious operational complexity according to the AWS docs.

Host 1

I always visualize this like an office. An L1 cache is like having a sticky note slapped right under your own computer monitor.

Host 2

I like that.

Host 1

It's instantly accessible to you, but no one else in the building can see it. And if you get a new monitor, like a server restart, the note is just gone.

Host 2

Right.

Host 1

The L2 cache is like the locked filing cabinet in the center of the office. It's consistent for everyone, but you have to physically get up, walk over, and unlock it.

Host 2

Right. But if we connect this to the bigger picture, this really highlights the ecstasy and agony of caches. Like what happens if that shared filing cabinet is temporarily unavailable?

Host 1

Do we just go directly to the source?

Host 2

Well, the AWS architecture docs warn heavily against that. It's called the cache aside trap.

Host 1

Right. The standard pattern.

Host 2

Yeah. Normally your code checks the cache. On a miss, it falls back to the database, reads the data, and then updates the cache.

Host 1

But if your L2 cache goes down completely and your code automatically falls back to the database for every single request, you've accidentally turned your cache into a hard dependency.

Host 2

That is the crux of the trap. You take this helpful accelerator and turn it into a catastrophic single point of failure that just browns out the database.

Host 1

Because it was never provisioned for that much direct traffic.

Host 2

Exactly.

Host 1

Which brings us back to the thundering herd from the cold open. Even if the cache is perfectly healthy, a single expired key still triggers that massive stampede.

Host 2

Yeah.

Host 1

So how do we mitigate that?

Host 2

The mechanism is called request coalescing.

Host 1

Okay.

Host 2

When a cache miss occurs for a viral hotkey, a thousand threads might try to fetch it at the exact same time. But with coalescing, the application framework recognizes they are all asking for the exact same resource.

Host 1

Oh, I see.

Host 2

So it allows only one, literally the very first pending request, to go out and query the database.

Host 1

And the other 999 threads just wait.

Host 2

Basically, yeah. They wait on a local lock. Once that single database call returns and populates the cache, the framework wakes up all those waiting threads and hands them the data.

Host 1

Wow. So you've shielded the database from 999 redundant queries. That is amazing.

Host 2

It's highly effective.

Host 1

But assuming we've successfully shielded our database using coalescing, our Redis cluster is now catching all that traffic.

Host 2

Right.

Host 1

And RAM is finite. How does Redis internally decide what data lives and what dies when the memory is full?

Host 2

Well, looking at the Redis internals, their eviction mechanics are wildly clever. Most people just assume Redis uses a strict LRU, you know, least recently used.

Host 1

Right. Just kick out the oldest stuff.

Host 2

Right. But tracking the exact millisecond access time of a hundred million keys requires massive pointer overhead. You would burn gigabytes of precious RAM just tracking the metadata for the cache.

Host 1

So what do they do instead?

Host 2

They use an approximated LRU. It doesn't scan the whole data set. It randomly samples a tiny fraction of keys. The default is literally just five keys.

Host 1

Wait, really? Just five keys? That feels impossibly small for a data set of millions.

Host 2

It sounds totally counterintuitive. But mathematically, a small sample size combined with a running pool of the best candidates yields a highly efficient approximation.

Host 1

So it gets near perfect LRU behavior without the memory blow.

Host 2

Exactly. But LRU isn't always the best strategy. The sources also detail LFU, which is least frequently used.

Host 1

Okay. And how do they track frequency without wasting memory?

Host 2

Redis employs this probabilistic data structure called a Morris counter.

Host 1

A Morris counter.

Host 2

Yeah, it is fascinating. Instead of storing the exact number of times an item was accessed, which would take a large integer, it uses just eight bits.

Host 1

Only eight bits.

Host 2

Yeah. It increments probabilistically. If the counter is at five, the chance of it incrementing to six might be one in five. If it's at a hundred, the chance is one in a hundred.

Host 1

Oh wow. So it stores a magnitude, not an exact count.

Host 2

Exactly. And it pairs that with a decay period.

Host 1

Right, because if someone was super active yesterday but hasn't logged in today, you don't want their data hogging the cache forever.

Host 2

Exactly.

Host 1

It's kind of like a bouncer at a club using a clicker to track VIPs. Like buy a lot of drinks, you stay in the VIP section. But periodically the bouncer randomly rolls the clicker backwards. That's the decay.

Host 2

That's a great way to picture it.

Host 1

So people who were popular hours ago can still get kicked out to make room for new VIPs.

Host 2

Right. And what's fascinating here is why this matters architecturally. Choosing the wrong eviction policy directly degrades your cache hit ratio, which throws unnecessary load back onto your connection pools.

Host 1

Makes sense.

Host 2

For example, there's a newer policy called LRM, least recently modified. It only updates the timestamp on write operations.

Host 1

Oh, perfect for read-heavy workloads.

Host 2

Exactly. You only want to evict stale data that hasn't been updated recently, regardless of how often it's being read.

Host 1

Okay, here's where it gets really interesting. Evicting old data manages state, but what about complex multi-step mutations? Like we can't afford race conditions between our application and the cache.

Host 2

Right, like checking inventory and deducting a balance.

Host 1

Exactly. So to handle atomic mutations, Redis actually embeds a full Lua 5.1 interpreter. You write your logic in a Lua script, and Redis executes it atomically.

Host 2

But keep in mind, Redis is single-threaded. Right. So by atomic, that means it blocks absolutely every other operation on the server while the script runs.

Host 1

Everything else just cues up.

Host 2

Yep. Now to save network bandwidth, you don't send the whole script every time. You load it once, get an SHA1 digest, and then use the evalShaw command to execute it from the cache.

Host 1

Wait, if Lua scripts block the entire Redis server to guarantee atomicity, doesn't a slow script defeat the entire purpose of a lightning fast cache? Like what if a developer writes an infinite loop?

Host 2

That is a very real danger. That is. And it's why the documentation is so strict about keeping caching logic extremely lightweight.

Host 1

Do they have a failsafe?

Host 2

They do. There's a maximum execution time threshold. If a script exceeds it, Redis stops accepting normal commands and only accepts a script kill command.

Host 1

So you can terminate it before it ruins everything.

Host 2

Assuming it hasn't modified data yet. Yeah. And there's also a major shift in how these scripts replicate to read replicas.

Host 1

Right. Verbatim versus effects replication.

Host 2

Yeah. Previously, Redis used verbatim replication. The primary node sent the raw script down to the replicas to execute.

Host 1

But what about non-deterministic scripts?

Host 2

Like if it uses a random number generator or the time command.

Host 1

That was the danger.

Host 2

A random number on the primary would yield a completely different result on the replica. Your data is suddenly corrupted.

Host 1

So how do they fix it?

Host 2

Since Redis 5.0, effects replication is the default. The primary calculates the final state and only replicates the actual write commands down to the replicas.

Host 1

Oh, so the replicas don't run the script at all.

Host 2

Exactly. They just apply the safe deterministic data changes.

Host 1

That is brilliant. Okay, so we've optimized the cache and eviction policies, but what happens to the actual network pipes connecting our services when things slow down?

Host 2

Resource exhaustion.

Host 1

Right. The Envoy proxy documentation gives us great insight into connection pooling here.

Host 2

Yeah. If you look at HTTP 1.1, it requires acquiring a dedicated connection per request. If you have a thousand users, you need a massive pool of a thousand open connections.

Host 1

Which means your servers are just burning CPU cycles, fighting over thread locks.

Host 2

Right. But upgrading to HTTP2 or HTTP3 changes the game. They multiplex multiple requests over a single connection up to a concurrent stream limit.

Host 1

So you drastically shrink your connection pools.

Host 2

Exactly. Envoy also supports features like Happy Eyeballs for failover.

Host 1

I just love that name.

Host 2

Happy eyeballs.

Host 1

It basically tries IPv6 and IPv4 simultaneously, right?

Host 2

Yeah, but with a slight 300 millisecond delay for IPv4. It beautifully mitigates network level connection blocking.

Host 1

But even with multiplexing, the Google SRE handbook highlights this terrifying mathematical reality called bimodal latency and threat exhaustion.

Host 2

This is a huge one.

Host 1

Right. Like if you're wondering why your microservices randomly drop perfectly healthy traffic during a minor back end blip, this math is why. Let's walk through it.

Host 2

Okay.

Host 1

So your front end has a pool of a thousand threads. Normally requests take a hundred milliseconds.

Host 2

Nice and fast.

Host 1

Right. But suddenly a downstream dependency slows down and just five percent of your requests hit a say hundred-second timeout deadline.

Host 2

Well, let's do the math on that. If you're processing a thousand queries a second, five percent is fifty requests. Okay. So in the first second of that slowdown, 50 threads lock up, waiting for that hundred-second timeout. In the second second, another 50 threads lock up.

Host 1

Oh man.

Host 2

Yeah. Within just 20 seconds, all 1,000 of your front-end threads are completely locked.

Host 1

So you instantly run out of capacity. You get 100% thread exhaustion.

Host 2

Exactly. And because those 5% of stuck requests are hogging the pool, the other 95% of healthy traffic just gets rejected with errors.

Host 1

So if waiting for a slow back end kills our front-end threads, why don't we just set incredibly short timeouts for everything?

Host 2

Well, that introduces deadline propagation and cancellation propagation.

Host 1

How does that work?

Host 2

If server A gives server B a 10-second deadline and B takes eight seconds just processing before it calls server C.

Host 1

B has to propagate a two-second deadline to C.

Host 2

Exactly. Otherwise, server C does useless work for a client that has already given up.

Host 1

Right. And those connection limits and timeout physics are exactly the ingredients that turn a simple cash miss into a global cascading failure.

Host 2

Definitely. Let's look at how the system actually breaks under pressure.

Host 1

Yeah, let's talk about retries. Because the biggest meltdown trigger is usually retries.

Host 2

Oh, absolutely. Retries are often implemented naively. Like if your back end is rejecting traffic due to overload and your front end aggressively retries, you amplify the load exponentially.

Host 1

It's like pressing the crosswalk button 50 times because the light is broken. You aren't helping, you're just short-surticking the button.

Host 2

Exactly. What's fascinating here is the absolute necessity of randomized exponential back off, what we call jitter.

Host 1

Right, staggering the retries so they don't all hit in a synchronized way.

Host 2

Yeah. And you also need strict server-wide retry budgets. Cap the amplification at the source.

Host 1

Another system killer from the source is cache penetration.

Host 2

Oh yeah. Bombarding the downstream database with requests for keys that literally don't exist.

Host 1

Because if the key doesn't exist, it never gets cached. So every request pierces straight through the database.

Host 2

Right. And the mitigation for that is negative caching. You actually cache the error responses with a distinct TTL so the database isn't hit repeatedly for the same missing item.

Host 1

That makes total sense. But even if your networking is flawless, Redis itself has a hidden landmine regarding background saves, right?

Host 2

Yes. The Linux fork copy on write memory spike.

Host 1

Right.

Host 2

When Redis takes a snapshot, it forks its process. If a massive number of writes happen during that save, Linux has to copy those memory pages.

Host 1

Your memory usage basically doubles.

Host 2

Exactly. And if your overcommit memory setting isn't set to one, the node just crashes.

Host 1

Wow. Speaking of data issues, why might a read replica show a different key count than the primary? I know that confuses a lot of engineers.

Host 2

Yeah. Expired keys aren't pushed to the replica until they're explicitly deleted on the primary. So the replica temporarily holds ghost data.

Host 1

Got it. So pulling this all together, how do we establish clear decision boundaries for our architecture?

Host 2

The sources offer a great architectural checklist. First, combine your L1 and L2 caches. But if L2 goes down, strongly consider load shedding instead of failing over to the DB.

Host 1

Deliberately dropping traffic is better than a total collapse.

Host 2

Right. Second, use graceful degradation. When approaching overload, drop non-critical features to save CPU.

Host 1

Save the core transactions.

Host 2

Exactly. And third, use soft versus hard TTLs. Try to refresh the cache at the soft TTL, but if the back end is down, keep serving the stale data up until the hard TTL.

Host 1

Stale data is better than an error page.

Host 2

Always.

Host 1

Well, thank you for taking this deep dive with us. We've seen how all this math and architecture acts as a shock absorber. But I want to leave you, the listener, with a final provocative thought.

Host 2

Go for it.

Host 1

If we are engineering systems with probabilistic Morris counters to guess what data matters, and employing automated load shedding that decides which traffic is unimportant during an outage, at what point does our infrastructure stop being purely technical and start making subjective business level product decisions on our behalf? Something to think about.

Save to playlist

Manage playlists →

Share