- Published on
How redis expires keys? A dive into how TTL works internally in Redis. 🌊
Redis is one of the super-cool pieces of software that I've always admired. Recently, I got curious about the algorithm behind expiring keys in Redis. I've used the TTL feature in Redis, quite a lot but never dug deeper to understand the concept behind it.
Before I start, a quick heads-up for my awesome internet friends who are not quite aware of Redis and TTL.
Redis is an in-memory data structure store, used as a distributed, in-memory key–value database. And TTL stands for Time-to-Live. While setting a key in Redis, you can specify the time to live for key when the TTL elapses, the key is automatically destroyed.
So, to scratch my itch, I started my investigation and landed over this beautiful piece of code on Redis Github repo.
Well, It does not take a genius to figure this out. Redis has had different implementations over the years for it.
Sounds cool? Let's dip into it.
How Redis expire keys?
So, the problem statement is quite easy-peasy. Set a timeout on key. After the timeout has expired, the key will automatically be deleted.
Initially, Redis had a quite straight-forward implementation.
Redis expires keys in two ways - a passive way and an active way.
Well, please don't pull your hair. Let me clarify it.
A Passive way
In simple words, it's a semi-lazy mechanism.
God, again a new term? Don't worry.
Semi-lazy expiration means, it does not actually expire (delete) the key until we try to access it. Whenever we read a key, it checks if the key is already expired, if yes, it returns null and deletes the key silently.
Interesting. The beauty of this implementation is the simplicity.
But, it has a big problem.
If a key is never touched, it will be there, It will take space in the memory, for no reason. And of course Redis knows, we are not that rich to afford it.
An Active way
Redis needed a mechanism to ensure keys are eventually removed when expired, even if no access is performed on them. So, they added another beautiful layer on top of it.
Although, the actual implementation is quite tangled, the main idea was -
It periodically checks a few keys randomly and if any expired key is encountered, it goes ahead and removes the key.
More specifically, this is what Redis does 10 times per second :
- Test 20 random keys which has TTL attached
- Deletes all expired keys
- If more than 25% of keys were expired, repeat step 1
Simply, it's a trivial probabilistic algorithm. Redis runs an internal timer. It continues to expire keys until the total % of the keys, that are likely to be expired is under 25%.
This idea worked like a charm.
But still, there was a probability of taking up to 25% of memory. And my friends at Twitter were not quite happy with it.
TL;DR - They ran into an interesting performance issue in their Redis clusters. This super interesting concept became a culprit. In some of their clusters, expired keys ate up to 25% of the memory. So, whenever a new write request was coming to Redis, it stopped whatever it was doing, evicted a key, and then saved a new key because it didn't have enough memory to accept the write.
Redis 6.0 Release
The super-smart folks at Redis came up with a brilliant approach. They re-wrote the expiration cycle in Redis 6.0 to allow for a much faster expiration that more closely matches the TTL.
Redis 6.0 stable release expiration algorithm is no longer based on random sampling. Now, keys are sorted by expiration time in a radix tree and it's relatively easier and more efficient. And they claim, that all of these problems got vanished with this architectural change.
Now that I end my ramblings, I invite your comment on it. If you find any technical inaccuracies, let me know, please.