Big eviction loop by dictExpand & rehashing

[itugs]

Problem

• Faced big performance drop when eviction began in LRU mode testing.

# Redis version
Redis server v=3.0.3 sha=5acd0104:1 malloc=jemalloc-3.6.0 bits=64 build=9bcbb4fa9b65d878

# Memory configration
maxmemory 16g
maxmemory-policy allkeys-lru

# Key/Value
Each of key and value : 20 bytes

Investigation

• After adding some logs, found a loop inside of freeMemoryIfNeeded took tens of seconds.

73494:M 06 Aug 12:53:52.666 # dict expanded. latency: 5, used: 67108864
73494:M 06 Aug 12:53:52.666 #    - before - ht.size: 67108864, mem 8056638424
73494:M 06 Aug 12:53:52.666 #    - after - ht.size: 134217728, mem 9130380248
73494:M 06 Aug 12:55:34.761 # rehashing done. latency: 24971, memory freed: 536870912
73494:M 06 Aug 13:01:34.344 # dict expanded. latency: 6, used: 134217728
73494:M 06 Aug 13:01:34.344 #    - before - ht.size: 134217728, mem 16109702296
73494:M 06 Aug 13:01:34.344 #    - after - ht.size: 268435456, mem 18257185944
73494:M 06 Aug 13:02:29.176 # Eviction loop done. loop_count: 9618901, latency: 54832518, mem_freed: 1077316912
73494:M 06 Aug 13:02:29.179 # Eviction loop done. loop_count: 225, latency: 1238, mem_freed: 25200
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 330, latency: 1826, mem_freed: 36960
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 1, latency: 6, mem_freed: 112
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 1, latency: 8, mem_freed: 112
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 1, latency: 6, mem_freed: 112
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 1, latency: 5, mem_freed: 112
73494:M 06 Aug 13:02:29.181 # Eviction loop done. loop_count: 1, latency: 7, mem_freed: 112
....
73494:M 06 Aug 13:03:23.040 # rehashing done. latency: 57560, memory freed: 1073741824

This is a timing issue occurring when eviction and rehashing is overlapped.

1. Dict expand. In my case it's 1GB.
2. By this expansion, used memory exceed maxmemory with huge gap.
3. freeMemoryIfNeeded try to free this entire gap.

Beside this zfree take long time when memory is large. So this cause another latency problem.

• About 25ms at 512MB
• About 50ms at 1GB

Here is my code for logging.

int freeMemoryIfNeeded(void) {
...
    long long latency_u = ustime();
    int loop_count = 0;
    while (mem_freed < mem_tofree) {
...
            /* Finally remove the selected key. */
            if (bestkey) {
...
            }

            eviction_loop--;
    }
...
    redisLog(REDIS_WARNING, "Eviction loop done. loop_count: %d, latency: %lld, mem_freed: %zu", loop_count, ustime()-latency_u, mem_freed);
    return REDIS_OK;
}

int dictRehash(dict *d, int n) {
...

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        long long mem_before = zmalloc_used_memory();
        long long latency_u = ustime();
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        redisLog(REDIS_WARNING, "rehashing done. latency: %lld, memory freed: %lld", ustime()-latency_u, mem_before-zmalloc_used_memory());
        return 0;
    }

...
}

Suggestions of modification

1. Restrict eviction loop count.
2. Preallocate db's hashtable size to large enough to avoid rehashing.

When I tested max 3 loops, eviction loop consume 10~40 us. And my current workaroud is second one because we only put fixed size KV so we can choose good number.
To apply second solution, we should disable resize down.

void tryResizeHashTables(int dbid) {
    if (0 == server.hashtable_minfill)
        return;
...
}