@Axlgrep thanks for the detailed report.
I certainly agree that a user with such use case pattern would prefer the memory cost rather than the latency spikes, but i'm not comfortable with the config (one that's just preventing dicts from being shrinked).
I'd argue the same about a config that let's the user control HASHTABLE_MIN_FILL, it is too low level.
I would rather find some mechanism that can do that automatically in some way without users detecting the problem (which i assume most won't) and tuning their database.

looking at the code i see we use calloc in that case. and i suspect that the latency spike is due to the zeroing of the memory, and not the memory allocation itself.
the zeroing of memory brings latency due to two issues:

1. obviously it takes time to zero memory (memory bandwidth).
2. the kernel needs to allocate pages and assign them to the process (i think this makes the most damage).

so if we somehow do the zeroing gradually, we'll avoid the latency spike.

I would like to suggest to modify the code in a way that will not use calloc, instead it can use malloc, and only zero the entries when it writes to them for the first time.
obviously, the code will need to keep some variable that keeps track at the maximum index that was already written to, and avoid trying to read from ones that are still uninitialized.

while at this topic, i would like to raise another improvement idea i had, maybe we can combine these two and code them together:

Currently a reshash come with a big price of memory, which sometimes causes eviction and data loss.
this is because we allocate another hash table that's double in size, and keep the old one in parallel to the new one for a while.
my idea is that instead of allocating a new hash table, we'll re-alloc the existing one, and then start moving entries from the lower half to the upper half. or alternatively when shrinking, we can maybe concentrate the entries in the lower part, and then eventually realloc the hash table to be smaller.
obviously this poses some challenges in dictScan and other areas of dict.c, but i think they're all solvable.

@Axlgrep would you like to look into any of these?

@oranagra

For our guess is due to the zeroing of the memory caused by the latency spike, I can modify the source code(when use zalloc to allocate memory, also use zmalloc to allocate another memory of the same size), then over the next few days to compare the latency spike on ZCalloc() and ZMalloc().

However, it is to note that there is also a risk of latency spike when free large chunks of memory(zfree 536870912 bytes memory, cost 133389 us).

If we're at it: There are other implementations both faster and smaller in memory than the Redis dict. For example "SIMD-friendly bucketized cuckoo hash" (with more explanations found in this discussion) and HAMT. (The former can be re-hashed in place and can be 99% full and still be O(1). The latter doesn't need rehashing at all and doesn't use huge allocations.)

@zuiderkwast can these support our SCAN algorithm?
p.s. we have some long term plan to move away from dict and use rax instead, but this is still far ahead, for now i rather make small incremental changes.

@oranagra

can these support our SCAN algorithm?

I have to think about that. :-) I suppose it would have to be adapted. Does it work for rax?

p.s. we have some long term plan to move away from dict and use rax instead

Yeah, so I've read, but also that large random-like keys take up more space in rax, e.g. uuids. A HAMT is essentially a trie of the hash value of a key, with a high branching factor, so it's somewhere between a rax and a hash table. (If we don't need it to be ordered, I imagine HAMT is better.)

rax can't support SCAN, if / when we'll do that, we'll need to break compatibility with that command.

I think rax can support SCAN in this way: The key space is mapped to the cursor's integer range using the first 4 or 8 bytes of the key (treated as big endian) as the cursor value. The cursor 0 corresponds to keys starting with "\0\0\0\0"...

It implies that all keys with the same 4 or 8 bytes prefix have to be included in the same scan "chunk", so if all (or many) of the keys have the same prefix, SCAN has to return them all to be able to increment the cursor, and it falls back to KEYS behaviour in the worst case.

For the HAMT (which is a trie of the hash values of keys), the cursor can simply be the hash value of a key. The keys are traversed in the order of their hash values.

I'm not sure what you describe about common prefixes for the rax is acceptable.
For the two approaches, we have an issue with the special meaning of a cursor value of 0.

I'm not sure what you describe about common prefixes for the rax is acceptable.

Well, if there are a lot of keys like "user123456", they would all need to be returned together, so it becomes like KEYS, which is not acceptable. (Only perhaps in combination with deprecating SCAN.)

For the two approaches, we have an issue with the special meaning of a cursor value of 0.

Well, 0 (as input) means start from the first key. The cursor has to always increment so we'll never return 0 again until all keys are scanned, so that's not an issue.

@Axlgrep Sorry for kidnapping this PR! I suppose this side-track is done.

Hi @Axlgrep, I have a great interest on memory allocation of dict rehash and also did some research. I'd like to confirm if you use jemalloc when you encountered the issue mentioned?
Thanks in advance!

Idea: Would it be possible to do the large ht malloc and free asynchronously in another thread, so that the main thread can continue serving clients? If I understand it right, there is a special arena shared among threads for large allocations (opt.oversize_threshold, 8MiB by default). The main thread would not start incremental rehashing until the allocation thread is done allocating.

[Edit] @oranagra, OK, I've moved this comment to the "perfect implementation of hashtable" issue where this thread has been running lately. (Hard to decide where it best fits. That issue is mainly about the nested has table idea. This PR is about the slow malloc and free, so I thought here might be a good place for the comment. The other place is where the "thread" is now though.)

@zuiderkwast did you mean to comment in the other issue? If you did, maybe move your comment and I'll respond there.

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}