The problem/use-case that the feature addresses

Redis is a remote dictionary server, which is essentially a hash table. When there is a hash conflict, we are going to put the data in a singly linked list, and the head node of the slot points to the singly linked list. In reality, we often run into the problem of hot keys. If the hot key is at the end of the singly linked list, we have to go through the whole singly linked list every time to get the hot key, which will waste a lot of performance in unnecessary queries.

Description of the feature

By turning a singly linked list into a ring, the head node can automatically select the next key based on access frequency or other rules. This can save the time you need to go through a singly linked list every time.

Additional information

Specific implementation, please refer to HotRing article. https://www.usenix.org/system/files/fast20-chen_jiqiang.pdf

Comment From: itamarhaber

Hello @Acm77

Thanks for thinking of Redis and coming up with this suggestion.

The HotRing is very interesting indeed. Redis, however, takes another approach to reducing collisions via rehashing, which is designed to keep the linked list at a "constant" size. Do you think it needs to be augmented with HotRing?

Comment From: Jeremy-Run

Hello @itamarhaber

Yes, I just want to strengthen it. I know that Redis uses progressive rehash to ensure that the list length doesn't get that long, and that the load factor is usually 1 for Redis rehash (5 for BGSAVE or BGREWRITEAOF command).

I propose to apply HotRing to Redis for two reasons:

  1. When using Redis, we do have the situation of hotspot tilts. Some keys are very popular and some keys are barely accessed. It would be unfortunate if the hot key falls at the end of the singly linked list. Why don't we figure out a way to solve this problem Instead of giving this problem to God?

  2. Since the working thread of Redis is single-threaded, we don't need to consider concurrent reads and writes in HotRing, which makes it much easier to implement HotRing in Redis than mentioned in the previous paper. A low-cost improvement that might give Redis some performance boost in actual use, which is clearly worth doing. Of course, the ultimate performance improvement depends on the results of benchmark test.