How does redis expire keys?
RedisRedis Problem Overview
How does Redis implement the expiration of keys? From here I learnt that Redis stores the time at which the key will expire, but how exactly is this implemented?
Redis Solutions
Solution 1 - Redis
In short - for each redis object, there is an expiration time. Unless you set the object to expire, that time is "never".
Now, the expiration mechanism itself is semi-lazy. Lazy expiration means that you don't actually expire the objects until they are read. When reading an object, we check its expiration timestamp, and if it's in the past, we return nothing, and delete the object while we're at it. But the problem is that if a key is never touched, it just takes up memory for no reason.
So Redis adds a second layer of random active expiration. It just reads random keys all the time, and when an expired key is touched it is deleted based on the lazy mechanism. This does not affect the expire behavior, it just adds "garbage collection" of expired keys.
Of course the actual implementation is more complicated than this, but this is the main idea.
You can read more about it here: http://redis.io/commands/expire
And the source code for the active expiration cycle can be found here: https://github.com/antirez/redis/blob/a92921da135e38eedd89138e15fe9fd1ffdd9b48/src/expire.c#L98
Solution 2 - Redis
For the Redis 6, from the release notes:
> The expiration cycle has been rewritten in Redis 6.0 to allow for much
> faster expirations that more closely match the time-to-live (TTL)
> property. Redis 6 expiration will no longer be based on random
> sampling but will take keys sorted by expire time in a radix tree
>
— Redis 6 release notes
For full release notes here.
Solution 3 - Redis
From reference:
> Redis keys are expired in two ways: a passive way, and an active > way. > > A key is passively expired simply when some client tries to access it, > and the key is found to be timed out. > > Of course this is not enough as there are expired keys that will never > be accessed again. These keys should be expired anyway, so > periodically Redis tests a few keys at random among keys with an > expire set. All the keys that are already expired are deleted from the > keyspace. > > Specifically this is what Redis does 10 times per second: > > Test 20 random keys from the set of keys with an associated expire. > Delete all the keys found expired. If more than 25% of keys were > expired, start again from step 1. This is a trivial probabilistic > algorithm, basically the assumption is that our sample is > representative of the whole key space, and we continue to expire until > the percentage of keys that are likely to be expired is under 25% > > This means that at any given moment the maximum amount of keys already > expired that are using memory is at max equal to max amount of write > operations per second divided by 4.