just pushed on git a small change with big effects. As some of you
probably already know EXPIRE uses a lazy expire algorithm, that is,
Redis does not constantly monitor keys that are going to be expired.
Keys are expired simply when some client tries to access a key, 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. This keys should be expired anyway, so Redis once
every second test a few keys at random among keys with an expire set.
All the keys that are already expired are deleted from the keyspace.

And after this background let's explain what changed. In the past
every second just a fixed number of keys where tested (100 by
default). So if you had a client setting keys with a very short expire
faster than 100 for second the memory continued to grow. When you
stopped to insert new keys the memory started to be freed, 100 keys
every second in the best conditions. This sucks... under a peak Redis
continues to use more and more RAM even if most keys are expired.

The new algorithm instead does the following, every second.

a) Test 100 random keys for expired keys.
c) Delete all the keys found expired.
d) If more than 25 keys were expired, start again from "a"

This is a trivial probabilistic algorithm, basically the assumption is
that our sample is more or less representative of the whole key space,
and we continue to expire until the percentage of keys that are likely
to be expired is < 25%.

This means that into a given moment the maximum amount of keys already
expired that are using memory is at max:

max_expired_keys_still_in_RAM = max_SET_operations_per_second / 4

That is absolutely acceptable.

So if you experienced problems with memory usage using Redis as a
cache with many keys with short expires 1.1 should fix this problems.

Cheers,
Salvatore

--
Salvatore 'antirez' Sanfilippo
http://invece.org