A little internal on Redis hash table implementation

Redis needs no introduction. It’s a very popular key value store providing a variety of in-memory storage ( Data can be persisted on disk also — there are background saving & Append Only File options to achieve the same ) like List, Set, Sorted Set, String, HyperLogLog, Geospatial structures etc. Redis trades off memory to achieve speed, it performs all operations in a single thread, though AOF operations run in a separate background thread.

This post intends to explain how internally redis hash table is designed & how they are resized. The post does not explain how hash value or bucket index for a key is calculated.

Each redis database instance ( databases are indexed from 0 to max configured ) has a key space associated with it which is nothing but a wrapper on hash table implementation. Whatever data redis stores be it string, redis set or redis hash, everything is saved inside the hash tables. The following code snippet, taken from redis github repository shows how the dict datatype is defined. The struct dict contains an array of 2 dictht instances. We will come back after a short while why there are 2 instances in the array. dictht ,the hash table implementation which in turn contains an array ( named as table in the code ) of dictEntry . dictEntry is a representation of linked list node that contains key, value & a pointer to the next node. dictht has other members like — size: total number of buckets in the hash table, the size is provided while creating or expanding the hash table, sizemask is used along with hash value of key to identify the correct index for the key, typically sizemask ≤ size, and the member used actually keeps track of how many total elements currently exists in the hash table.

The initial size of hash table dictht is 4. As more & more keys enter into the system, the hash table size also grows. When does redis resize hash table? Redis can resize hash tables or simply rehash in following 2 scenarios:

1. total_elements / total_buckets = 1 and dict resize is enabled. Enabling or disabling dict resize is handled by redis internally. Redis tries to avoid rehashing when some background process runs to do some sort of heavy operation like saving the database to disk as rehashing involves movement of memory pages in heavy amount. So simply stating, when background process runs, dict resize is usually disabled otherwise enabled.
2. total_elements / total_buckets > 5 ( force resize ratio, forcefully resizing is done)

Now here comes the interesting part. As I already mentioned, redis is single threaded. So it has to execute operations like hash table resizing & rehashing in such a way that it does not get blocked. Because rehashing a big hash table can always block redis which is unacceptable.

To achieve that redis performs rehash operation in incremental fashion. With every operation like GET, SET etc redis checks if it needs to rehash. If rehash is necessary, redis checks if it needs to expand the hash table first. Expand is simply resizing the hash table. As I mentioned struct dict in the above code snippet contains an array ht of 2 dictht instances, here they come into picture. Redis usually stores data in the first dictht instance ( ht[0] ). While rehashing, it creates an expanded hash table of size power of 2 just greater than or equal to the current hash table ( ht[0] ) size and the new hash table is actually stored in ht[1] instance. So during incremental rehashing, redis keeps moving buckets ( a linked list actually as redis uses separate chaining in case of collision) from ht[0] to ht[1] in steps, not moving everything at once. Which bucket ( chained nodes ) to move is identified by calculating the position of the key in the current hash table. The member rehashindex of struct dict will be ≥ 0 during rehashing. rehashindex is just a variable that is used to iterate over a hash table in order to identify if that index position contains buckets to move or not. It starts with 0, goes till all index in the hash table is covered. Reading value of this member, redis knows if a rehash is going on. So to serve a GET request during rehasing, redis has to read both the hash tables to find out the data. That’s a bit disadvantage in terms of speed. When rehashing is complete, rehashindex is set to -1 and the new hash table that resides in ht[1] instance is assigned back to ht[0].

You can refer to the following code snippets which shows redis table expanding & rehashing: