Active expiry design clarifications and configuration

[Yoav]

Note, when I use "active expiry" below I'm referring to the process of periodically sampling keys and expiring them if needed in order to reduce memory used by dead keys (as performed in activeExpireCycle).

Recently I've been fighting quite a bit with various fragmentation and expiry issues in some huge databases. One of the things that could have helped is more aggressive active expiry.
Digging into the active expiry code I noticed at least 5 parameters that can affect how aggressive redis is when performing active expiry:

ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP - number of keys to sample and check for expiry before deciding if to continue expiring keys
ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4 - percentage of expired sampled keys indicating we should continue expiring stuff
ACTIVE_EXPIRE_CYCLE_FAST_DURATION - time limit in per cmd expiry cycle (fast cycle)
ACTIVE_EXPIRE_CYCLE_FAST_DURATION - min interval between fast cycles
ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC - time limit in periodic (slow cycle) expiry as percentage of HZ

The design here seems pretty complex and probably stems from the need to balance different use case a performance considerations. I'd really like to get some more insight into what are the general motivations behind this complex design? What's the purpose of the fast vs slow cycles?
Also the documentation mentions: "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." can you explain how this is achieved? In my specific scenario there are roughly 3K wops/sec but many millions of expired keys in memory (so this isn't working in my case).

Additionally because the above parameters are all constants there's no real way to tweak active expiry in runtime. For my case there seems some value in making this more configurable. The easy solution would be to make all 5 constants configurable. But before I go into this, I'd like some feedback about how to best make active expiry configurable. At a high level I want to be able to balance between CPU time spend on active expiry and memory used up by expired keys but given the complexity of the implementation I’m a bit lost at how this can be easily done.

[Thomas Love]

I can't answer your earlier/proximal questions because I am not familiar enough with Redis' design and source. But your ultimate goal is applying your own space/time trade-off to active expiry, and there are ways to do this without patching Redis.

Firstly I suppose that you have considered running a memory-limited process for this data according to http://redis.io/topics/lru-cache. This would be one way to get "more active" expiry, and you would in principle be able to tune the exact rate at runtime by changing maxmemory at runtime. 

An alternative would be to handle garbage collection yourself. For example and assuming you want an LRU-based approach, you could have something like Redis' probabilistic algorithm but with any parameters you like:

In your application, SADD new keys to a set rather than applying EXPIRES to them. And then, periodically in a background process:

1. Run SRANDMEMBER (or investigate SSCAN) to collect a subset to test (you can base the count on the SCARD of the set). 

2. Get OBJECT IDLETIME on each key referred to by the subset.

3. DEL the key and SREM the index if idle time is above your threshold. 

4. Repeat immediately if you deleted more than a certain number of keys. 

Over some desired "precision" for garbage collection, a zset-based index will probably be more efficient, at greater cost during key-creation. Having said all that, if you're not in fact doing a cache -- if your pattern looks like a FIFO buffer for example -- then a list would be all you need to track keys for deletion. 

Thomas

[Dvir Volk]

I think Yoav was aiming for more lower level issues, but a note on what you've suggested - 

the same can simply be implemented with RANDOMKEY http://redis.io/commands/randomkey

it might even trigger garbage collection automatically (that's what the "garbage collector" does internally IIRC)

--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+u...@googlegroups.com.
To post to this group, send email to redi...@googlegroups.com.
Visit this group at http://groups.google.com/group/redis-db.
For more options, visit https://groups.google.com/d/optout.

[Thomas Love]

It looks like RANDOMKEY does explicitly free expired keys, so I imagine it would work to "pump" collection by sending this command at some rate proportional to write ops/sec. 

And in the special case where the database is basically homogenous, this might be a better option than maintaining indexes, but then it might not be a better option than simply running Redis configured as an LRU cache. 

[Yoav Steinberg]

Yes, I was aiming for a lower level solution. There are two motivations here:

1) For my specific problem I'd like the ability to handle this without any client side modifications.
2) I feel it's worth opening some design talk about the motivations and design principle behind the active expiry implementation. From the code alone I was unable to understand this and It's probably worth having this documented (at least here in the list).

Anyway thanks for the ideas. I might actually test the RANDOMKEY approach. It seems it's fairly non obtrusive and might do the trick in some cases.

You received this message because you are subscribed to a topic in the Google Groups "Redis DB" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/redis-db/tF1cIg-bXS0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to redis-db+u...@googlegroups.com.

[Josiah Carlson]

See my replies inline.

On Mon, Jun 9, 2014 at 1:02 AM, Yoav <yo...@garantiadata.com> wrote:

Note, when I use "active expiry" below I'm referring to the process of periodically sampling keys and expiring them if needed in order to reduce memory used by dead keys (as performed in activeExpireCycle).

Recently I've been fighting quite a bit with various fragmentation and expiry issues in some huge databases. One of the things that could have helped is more aggressive active expiry.
Digging into the active expiry code I noticed at least 5 parameters that can affect how aggressive redis is when performing active expiry:

ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP - number of keys to sample and check for expiry before deciding if to continue expiring keys
ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4 - percentage of expired sampled keys indicating we should continue expiring stuff
ACTIVE_EXPIRE_CYCLE_FAST_DURATION - time limit in per cmd expiry cycle (fast cycle)
ACTIVE_EXPIRE_CYCLE_FAST_DURATION - min interval between fast cycles
ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC - time limit in periodic (slow cycle) expiry as percentage of HZ

The design here seems pretty complex and probably stems from the need to balance different use case a performance considerations. I'd really like to get some more insight into what are the general motivations behind this complex design?

The idea is that real LRU or sorted expiration times have memory overhead that is undesired. With this particular design, you can omit much of the space overhead by randomly sampling your keys, but the method does have some drawbacks.

Also, the design of this particular expiration method is not all that complicated. It *seems* complex because there is some non-intuitive behavior going on (fast vs. slow, multiple passes, etc.), but when you get right down to it, the algorithm is basically "sample some keys, expire as necessary, repeat if you got a lot of expired data". Everything else is tuning and optimization. And any other expiration system would necessarily be far more complicated (LRU actually doesn't buy you anything in the expiration side of things, and keeping a sorted sequence of expiration times can be a huge memory sink).

 

What's the purpose of the fast vs slow cycles?

Granularity and expectation. Looking into the source, the fast version is called prior to Redis waits for sockets to be available. The slow version is called a number of times/second based on what you have defined in the configuration as "hz". So if you have "hz" set as 10, Redis will call the slow version 10 times/second.

 

Also the documentation mentions: "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." can you explain how this is achieved? In my specific scenario there are roughly 3K wops/sec but many millions of expired keys in memory (so this isn't working in my case).

That bit of documentation is incorrect. A correct description is: "This means that at any given moment, the maximum number of keys already expired that are using memory is roughly equal to 1/4 of all keys with expiration times." That's because the method of randomly selecting keys for active expiration is to randomly choose a key from the hash that includes keys with an expiration time (db->expires), which it then expires as necessary. If there are more than 1/4 of those keys sampled that need to be expired, it takes another pass. If not, it checks another database. With the fast cycle times 

Additionally because the above parameters are all constants there's no real way to tweak active expiry in runtime. For my case there seems some value in making this more configurable. The easy solution would be to make all 5 constants configurable. But before I go into this, I'd like some feedback about how to best make active expiry configurable. At a high level I want to be able to balance between CPU time spend on active expiry and memory used up by expired keys but given the complexity of the implementation I’m a bit lost at how this can be easily done.

At present, only 25% of your keys with expiration might not be expired when they should. You can slightly reduce this number if you increase the 'hz' value, at the cost of more CPU time spent trying to expire data. Should the other parameters be adjustable? Hard to say. Each one of those values has a possible unintended performance and behavior consequence that makes describing the tradeoffs more difficult than "increase number of keys evicted, but also increases overhead".

If you are just looking to reduce the number of dead keys that are in memory, the simplest thing to do would be to make sure that all of your keys with expiration are in their own db and just make RANDOMKEY calls. Redis itself does the equivalent at least 200 times/second per db as part of the active expiration (20 probes, 10 times/second), but that doesn't mean that you can't do more.

 - Josiah

[Thomas Love]

On Wednesday, 11 June 2014 00:13:39 UTC+2, Josiah Carlson wrote:

At present, only 25% of your keys with expiration might not be expired when they should. You can slightly reduce this number if you increase the 'hz' value, at the cost of more CPU time spent trying to expire data. 

This may not be the case. The algorithm attempts to approach < 25% dead-weight keys, but it is also limited, by default, to 25ms in every 100ms cron interval. If it's hitting the time limit, it may not get anywhere near 25%, and increasing HZ alone will do no good -- if anything I'd expect that to *decrease* expiry performance slightly. Note also that fast cycles will not run in the case where normal cycles are hitting their time limit. 

So what to do depends on whether you are in fact seeing the expected 25% expired-but-not-deleted keys. 

If you are seeing significantly more than 25% dead-weight, try increasing ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC to 50, HZ to 20, and perhaps ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP to 100. 

If you're seeing 25% or so but want it lower, increase the denominator in ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4. 

If you want to see how much dead-weight Redis can eliminate given *only* a time limit, replace (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4) with (expired > 0). 

I agree it would be nice to be able to tweak this at runtime.

Thomas