Lazy expiring algorithm enhanced
Salvatore Sanfilippo
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
"Once you have something that grows faster than education grows,
you’re always going to get a pop culture.", Alan Kay
Simone Carletti
I found it to be extremely simple to read and understand especially
for those, like me, who are following the project to leverage their
coding skills.
Thanks you,
- Simone
Salvatore Sanfilippo
>
> Great write up Salvatore,
>
> I found it to be extremely simple to read and understand especially
> for those, like me, who are following the project to leverage their
> coding skills.
Hello Luca,
you are welcome, I'll try to write similar messages for the next
important changes.
Guo Du
> Great write up Salvatore,
>
> I found it to be extremely simple to read and understand especially
> for those, like me, who are following the project to leverage their
> coding skills.
Great design information. We probably should put those usefully
information on wiki or somewhere as redis knowledge base.
Just a suggestion. I understand it take effort to do it by volunteer.
-Guo
Aníbal Rojas
Yesterday I started to build a RoadMap (DRAFT) page in the wiki
with the reference to Salavatore's entry in the group. There is a lot
of information scattered in the group that yes should be in the wiki.
--
Aníbal Rojas
Ruby on Rails Web Developer
http://www.google.com/profiles/anibalrojas
Guo Du
> Yesterday I started to build a RoadMap (DRAFT) page in the wiki
> with the reference to Salavatore's entry in the group. There is a lot
> of information scattered in the group that yes should be in the wiki.
Hi Aníbal,
Thank you very much to put all together.
RoadMap is another exciting point to see which direction redis is
heading. Looking forward to see it.
-Guo