I didn't initially think of this, but I think we also need a change in defrag. Here

@redis/core-team Probably worth pinging the group about this, as it's a rather intrusive change and I can see the argument the complexity is not worthwhile.

@zuiderkwast If you get a chance, I also would expect this to perform better as well. If you don't get a chance I can try running some benchmarks tomorrow.

Benchmarks

Cluster of 3 nodes, no replicas, running locally on laptop.

Latency

redis-benchmark -p 30001 --cluster -t set,get -n 1000000 --threads 8 -P 100 -q

Result: No significant difference compared to unstable.

[Edit] I forgot to use -r here, so only one key was created. :-/ See new benchmark below!

Memory

DEBUG POPULATE 1000000 on one of the cluster nodes. Then INFO MEMORY.

The keys generated by DEBUG POPULATE are on the form key:NNNNNN. With a longer common key prefix (10 bytes), the memory saving is around 18%. For long keys without a shared prefix, the saving is expected to be even higher but I haven't written any script for generating such data.

@yossigo @itamarhaber @soloestoy ?

Haven't done a CR, but this looks good as long as there's no regression in performance - the rax was put there to replace a skip list that didn't perform well (1409c54).

Regarding the performance regression concerns, I increased the numbers and ran some more benchmarks.

Benchmark: Set and get
Number of requests (-n): 10,000,000
Keyspace length (-r): 1G, 1M, 1K (see table)
Cluster: 3 masters, 0 replicas
Command: redis-benchmark -p 30001 --cluster -t set,get -n 10000000 --threads 8 -P 100 -q -r $r
The database was flushed on all nodes between each run.

Ooh, that is more like what I was expecting.

So it looks like we see about a ~40/50% speedup for writes (which is great) at the cost of about a 10% get performance regression. For the R=1000, almost everything is probably in L1/L2 CPU cache, so that likely explains why their wasn't much difference there.

I think that 10% regression is acceptable for the memory savings and the write speed improvement. @redis/core-team Going to ping everyone again since this is definitely something to discuss.

The read performance degradation is marginal and not a major concern IMO.

On the other hand, the current approach of using a RAX to store the slot to keys structure ensures that the keys in the slot are strictly ordered in lexicographic order. With this approach that property is foregone. There is no longer any ordering that can be done given a specific key which makes async iteration on the keys in a slot to be harder when we need to resume the operation later on after the slot is modified. Looked through db.c but can't seem to find a good place where redis is currently relying on that today though.

More specifically, I was thinking of a use-case when we are iterating the keys in the slot, and we do that in an incremental manner with an iterator. When the iterator is somewhere in the middle of the slot, is there an efficient way to determine if a given item comes "before" or "after" the iterator? With RAX when the keys are ordered, we can simply do a > comparator on the key name with the iterator key name, which I think is kind of nice. Also today, the raxIterator is able to store the current key name so that even if the underlying slot_to_keys changed across iterator runs, we can do a quick re-seek the next time around and resume iteration. I don't think we will have the same safe iteration mechanism available on the double linked list with this change.

Does anyone know why slot_to_keys is ordered today? There might be a reason for it that I am not aware of. I wonder if there can be future potential use-cases for keeping the keys in the slot ordered which will be harder to support after this change.

@madolson i agree that considering the memory improvement and the write speed improvement we can accept the read degradation, but maybe we should give it a quick optimization attempt to see if we can solve that too.
i.e. invest a small effort rather than give up without trying.
it could be an extra indirection that's unavoidable (although RAX had an abundance of these), but maybe there's something simple that can be done to make it more cache friendly, or do some function inlining tip / macro.
@zuiderkwast can you do some profiling to see if you happen to find something.

If you do look into performance degradation of the read operations, I would suggest finding out where the additional latency comes from. Looking at this CR there is nothing that changed directly in the lookupKeyRead code path apart from the additional metadata in the dictEntry so I am curious about it. It could potentially be coming from the way benchmark was set up but I am not sure assuming you are keeping all other factors the same in your test run besides the redis-server binary.

Thinking about this more, the key range of 1000 where everything fits into L1/L2 cache is a very small redis instance and quite unusual usage scenario nowadays especially given the increase in the memory capacity over time from various service offerings. It is very likely that people would store much larger number of keys in Redis in the range of millions, where they will see this 10% slow down in the read path.

meanwhile, can you please update the summary at the top (will be linked in the release notes), with a summary of what was done, what are the implications, and why we decided to accept them.

I've updated it. Does it clarify why you decided to accept them? If not, please update.

For the record, i just realized this this change also fixes an issue.
in the past, defrag.c wasn't defragging the slot-to-keys, so these allocations could have prevented the allocator from releasing pages and result in a defragger that's consuming a lot of CPU and sin't gaining anything, see #9773.
Now since they're part of the dictEntry, they'll get implicitly defragged with it, so problem solved!
i'll update the top comment for the sake of release notes.

Nice! Maybe that's why my colleagues didn't see any benefit of defrag and turned it off. (They also wanted to turn off the allocator statistics because of the costs to keep them updated at every alloc and free. I think I mentioned this once.)

That's awesome! We've also seen limited benefit in the past, good to know this might have been part of the problem.

Can someone have a look at the above mentioned ticket and confirm it makes sense that this is due the cluster slots mapping? IIRC it's redis 4, which used to use rax, and the fragmentation was mainly in the 24 byte bin.

Excuse me for being late...
Wasn't it simpler to have 16384 dicts (in worst case) - one dict for cluster slot? Empty slot could live without dict.

@funny-falcon Maybe it is simpler but now the other solution is already done. :-) Do you want to investigate the dicts idea and benchmark it?

I think 16384 dicts (or 5400 dicts, a 3rd of the slots) is a lot of memory allocations, especially if there is only one key in each slot.

Wasn't it simpler to have 16384 dicts (in worst case) - one dict for cluster slot? Empty slot could live without dict.

The question this solves is: "give me all the keys in slot X".

Mapping slot-to-key is only used rarely - for things like slot-migration. Normally, we look up keys without regard to slot.

Having 16k dictionaries (in place of the main dictionary) would increase lookup time as we'd need to find the correct dictionary first. It would also be fairly disruptive to the code base as there are a lot of operations which use the main dictionary which would have to be redesigned to hash to slot first and then lookup. Anything that iterates on the main dictionary would have to be redesigned to iterate over 16k dictionaries (or the portion of 16k which are on a given node).

Having 16k dicts in addition to the main dictionary is much more memory than the linked list solution and the direct item access isn't needed for the problem being solved.

IMO stringing a linked list through the existing dictionary is a good solution.

And, of course, this is FAR more efficient (both time & space) than the old RAX table implementation.

Sorry, I had deal with Redis instances with 6-10GB per instance - ~10M keys. And ~500 slots per instance (yes, 33 partitions).
Doubtfully linked list links (16*10M=160M) consumes less memory than per-slot dictionary.

If we replace the db dict with these 16K dicts, then I can agree it doesn't use more memory. I assumed you wanted to use separate dicts just as to reference the set of keys in each slot.

If we want a two-level hash table anyway to avoid huge allocations, this could be a possible way forward. It is similar to #9517. However, in the extreme case that a node has only one slot (16K shards) there will be only one dict again.

@funny-falcon I'm going to promote this to it's own issue, I think it's a good idea, #10589.

finally followed.
we could fundamentally consider the application scenario of slottokey, basically in the scenario of cluster rehash and this function is used infrequent(In our practical experience, 90% of the clusters do not use the rehash once a year.).
we can make a tradeoff and use the new migraite mechanism to completely remove the storage and performance overhead of the slottokey
This is a preliminary design:

1. fork a child
2. scan the keys in child process, find the slot key and write to dest node
3. Synchronize the incremental data of this slot

This solution will increase the CPU overhead of the child process in step 2, but considering the overall ROI, compared with the performance and storage that can be improved in the main process in most of the time, this overhead is worth it.

@judeng your idea is somewhat like what #10933 proposes, or the implementation in Tencent or Bytedance' internal forks, which regards migration as a special full-sync replication

@uvletter cool job! If convenient, can you tell me about the memory savings after slottokey be deleted? :-)

I don't know… migrating with full replication is mainly for mitigating the impact involved by original migration like blocking with big key, or resource contention between business and operations. Removing slottokey is not the main concern, but of course slottokey can be removed in that way depending on if you concern memory or CPU/time resumption more.

@uvletter I didn't see any comments from you on #10933, did you have any additional insights you wanted to provide?

@uvletter I didn't see any comments from you on #10933, did you have any additional insights you wanted to provide?

Yes, I only roughly viewed the raw proposal before as when I look at it the discussion list is quite long... I think the general direction and HLD is pretty well(silence is also an attitude I guess), looking forward the next moving. I will look into the whole discussions when I have some time.