Let’s say you want to design caching system to your database. User journey is simple, User sends query to backend app that he needs to find a social media profile - app first check the cache, if profile is found you return the data from cache, otherwise you hit the database and then return the profile. So let’s build it, and I’ll show you where it breaks at every step.
Version 01 - Naive Approach
When a request needs a user’s profile named Alan_1, your code checks the cache first. If we find the data in cache, we call this cache-hit, then we return the data from cache to the app. If we don’t find the data we call it Cache-miss, and then you read the data from the database, and because that data was not in cache you write that result into the cache, then return it back to the app and then app will give profile to the user. Next time someone ask for same Alan’s profile, it comes straight from cache because cache has the data.
But you’ve a problem here… if Alan_1 user updates their profile from Alan_1 to Alan_4 and the new username is in the database, then the database has the new name, but the cache still holds the old username, which is Alan one, basically your cache don’t have updated data.
Version 02 - TTL and invalidation
To make sure your cache and database have same data, the simple fix is to add TTL to your cache, TTL stands for Time To Live - every entry in cache expires after specified period of time, let’s say five minutes, so after 5 mins cache will delete the old data and cache will be forced to get the data again from database. But this is not good enough, 5 minutes is too long for social media because in 5 minutes lot of queries can come in. So, what we can do is that if anything is updated in database, then we will delete that entry from cache. So if Alan is updated in database, his entry will be deleted from cache and then cache will be forced to get new data from database.
Version 03 - The cache miss storm
Let’s discuss the failure that takes down real systems. Let’s say you’ve got one hot key and it is access thousands of times per second from cache. If that key expires from cache. In the same instant, all hundred thousand requests miss the cache and slam the database at once. The database which was idle a second ago will see thousands of request and might break. The cache that was protecting your database just took it down.
To stop a hundred thousand requests from hitting the database the moment one hot key point expires? We add a few things on top of Version 3. First, single-flight, what we mean is that when the data point is missing from cache, only the first request goes to the database to load the value into cache. Any other request for the same data point does not hit the database; they wait. Second technique we use is called “Add jitter to TTLs”, instead of every key expiring at the exact same five-minute mark, we add a random few seconds to each key, so that different keys expires at different time.
And sometimes the problem is just raw volume, one hot key gets so much traffic that a single Redis node can’t keep up. The fix is to replicate that hot key across several Redis nodes and spread the reads, so no single node takes the full load.
We also break this down visually in a short video.
Discussion