antirez/redis — pull request #1790 by yoav-steinberg (2014-06-01 14:29:24+00:00)
Title: Prefer evicting expired keys when low on memory.

There are some cases where you have lots of expired objects in memory but for various reasons your eviction policy (maxmemory-policy) is tuned in such a way that other non expired keys get evicted first. I didn't want to rewrite the entire eviction logic as this would be a huge challenge and probably would disturb the delicate balance between eviction and expiry which exists in Redis.
What I did think totally possible (and was quite surprised to see it missing in the code) is to evict expired objects if we "accidentally" come across them when performing the random key sampling for eviction on low memory conditions.
My initial concern was that this added logic might affect performance, mainly by adding lookups into the expires dictionary in `freeMemoryIfNeeded`. To avoid this I made sure to only implement the logic for the `volatile-lru` and `volatile-ttl` settings.
* In case of `volatile-ttl` if we come across an expired key during the random sampling we simply halt the random sampling and use the key we found. This mainly improves performance and doesn't really change redis in any way.
* In case of `volatile-lru` if we come across an expired key during the random sampling we simply select it for eviction and skip the whole eviction pool logic. Here too there's a performance benefit, but additionally we can free memory without evicting cold keys which can also be a significant memory optimization.

Some more notes:
* I removed the (I hope you agree) ugly code related to local vs heap memory for the temporary random keys. Instead I simply use **dynamic stack allocation** which has been part of the c standard (via VLA's or alloca for over 15 years now).
* If you don't think performing additional translations between the `db->expires` and `db->dict` is a significant performance issue, then this should be amended to be include in `allkeys-ttl` and `allkeys-lru`.
* When checking if a key is expired I used the `server.mstime` instead of calling `mstime()` in place. This is also because of performance concerns which might be unbased. Feel free to fix that if you think there isn't a performance issue here.
* What prompted this patch are some very annoying real life scenarios where we're evicting lots of live keys while we have lots of memory consuming expired keys (In case you were wondering).