Redis maxmemory-policy: performances of volatile-lru vs allkeys-lru

Question

assuming all keys in a redis instance have an expire set, volatile-lru and allkeys-lru are similar. But is there a significative performance difference between the 2 when a key is removed?

Bonus question:

between 2 distinct instances configured with the allkeys-lru policy, having the same content and same configuration, except:

• Instance A has all its keys with an expire set (different values of expire)
• Instance B has none key with an expire set

Aside the overhead of memory in instance A due to the expires bits, is there a performance difference between the 2 when a key is removed by the allkeys-lru algorithm?

In both cases, I'm talking about instances of redis 2.4.x on linux 64 bits with maxmemory = 3Gb with 4-5000 keys when the maxmemory is reached (most of the keys are hashes).

Thanks

Mauretta

Answer 1

redis.c, line 2311, unstable branch:

/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
    server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
    for (k = 0; k < server.maxmemory_samples; k++) {
        sds thiskey;
        long thisval;
        robj *o;

        de = dictGetRandomKey(dict);
        thiskey = dictGetKey(de);
        /* When policy is volatile-lru we need an additonal lookup
         * to locate the real key, as dict is set to db->expires. */
        if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            de = dictFind(db->dict, thiskey);
        o = dictGetVal(de);
        thisval = estimateObjectIdleTime(o);

        /* Higher idle time is better candidate for deletion */
        if (bestkey == NULL || thisval > bestval) {
            bestkey = thiskey;
            bestval = thisval;
        }
    }
}

It seems like all things being equal allkeys-lru would be strictly speaking faster, but not by a significant magnitude. Chances are we are talking about not much more than a fraction of a microsecond faster.

The second question got pretty much already answered, but just in case: it looks like it makes no difference to allkeys-lru how many keys are set to expire, or if any are. Both Instance A and B in your example would see the same performance when a key is purged by the lru algorithm.

Video

@antirez getting a comment from the one who wrote it is even cooler :) – Video