Shulou(Shulou.com)05/31 Report--

This article shows you what the role of the internal data structure dict in Redis is, the content is concise and easy to understand, it can definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

Data structure definition of dict

To implement incremental double hashing (incremental rehashing), the data structure of dict contains two hash tables. During the heavy hash period, the data is migrated from the first hash table to the second hash table.

The C code for dict is defined as follows (from the Redis source dict.h):

Typedef struct dictEntry {void * key; union {void * val; uint64_t U64; int64_t S64; double d;} v; struct dictEntry * next;} dictEntry;typedef struct dictType {unsigned int (* hashFunction) (const void * key); void * (* keyDup) (void * privdata, const void * key); void * (* valDup) (void * privdata, const void * obj) Int (* keyCompare) (void * privdata, const void * key1, const void * key2); void (* keyDestructor) (void * privdata, void * key); void (* valDestructor) (void * privdata, void * obj);} dictType;/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. * / typedef struct dictht {dictEntry * * table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht;typedef struct dict {dictType * type; void * privdata; dictht ht [2]; long rehashidx; / * rehashing not in progress if rehashidx = =-1 * / int iterators; / * number of iterators currently running * /} dict

In order to show the data structure definition of dict more clearly, we use a structure diagram to represent it. As follows.

Combined with the above code and structure diagram, you can clearly see the structure of dict. A dict consists of the following items:

A pointer to the dictType structure (type). It enables dict's key and value to store any type of data in a custom way.

A private data pointer (privdata). Passed in by the caller when the dict is created.

Two hash tables (ht [2]). Both ht [0] and ht [1] are valid only during heavy hashing. Under normal circumstances, only ht [0] is valid, and there is no data in ht [1]. The figure above shows what happens when the heavy hash goes to a certain step in the middle.

Current heavy hash index (rehashidx). If rehashidx =-1, it means that the heavy hash is not currently in progress; otherwise, it indicates that the heavy hash is currently in progress, and its value records how far the current heavy hash has gone.

The number of iterator currently being traversed. This is not the focus of our discussion now, so we will ignore it for the time being.

The dictType structure contains several function pointers for callers of dict to customize various operations involving key and value. These actions include:

HashFunction, the hash algorithm that calculates the hash value of key.

KeyDup and valDup, which define copy functions for key and value, respectively, are used to make deep copies of key and value when needed, rather than just passing object pointers.

KeyCompare, which defines the comparison operation of two key, which is used when searching based on key.

KeyDestructor and valDestructor, which define destructors for key and value, respectively.

A private data pointer (privdata) is passed back to the caller when some operation of the dictType is invoked.

What needs to be examined in detail is the dictht structure. It defines the structure of a hash table, which consists of the following items:

An array of dictEntry pointers (table) The hash value of key is eventually mapped to a location in this array (corresponding to a bucket). If multiple key maps to the same location, a conflict occurs, and a dictEntry linked list is pulled out.

Size: identifies the length of the dictEntry pointer array. It's always an exponent of 2.

Sizemask: the location index used to map hash values to table. Its value is equal to (size-1), such as 7, 15, 31, 63, and so on, which is the number of all-one of each bit in binary. Each key is first calculated by hashFunction to get a hash value, and then calculated (hash value & sizemask) to get the position on the table. Equivalent to calculating the balance (hash value% size).

Used: record the number of data available in the dict. Its ratio to size is the loading factor (load factor). The higher the ratio, the higher the probability of hash conflict.

The dictEntry structure contains k, v, and a next pointer to the next item in the linked list. K is a void pointer, which means it can point to any type. V is a union, and when its value is of type uint64_t, int64_t, or double, no additional storage is required, which helps reduce memory fragmentation. Of course, v can also be a void pointer so that any type of data can be stored.

Creation of dict (dictCreate) dict * dictCreate (dictType * type, void * privDataPtr) {dict * d = zmalloc (sizeof (* d)); _ dictInit (dmaine type type privDataPtr); return d;} int _ dictInit (dict * d, dictType * type, void * privDataPtr) {_ dictReset (& d-> ht [0]); _ dictReset (& d-> ht [1]); d-> type = type; d-> privdata = privDataPtr; d-> rehashidx =-1 D-> iterators = 0; return DICT_OK;} static void _ dictReset (dictht * ht) {ht- > table = NULL; ht- > size = 0; ht- > sizemask = 0; ht- > used = 0;}

DictCreate allocates space for the data structure of dict and assigns initial values to each variable. Two of the hash tables ht [0] and ht [1] start with no space allocated, and the table pointer is assigned to NULL. This means that the space will not really be allocated until the first data is inserted.

Dict's search (dictFind) # define dictIsRehashing (d) ((d)-> rehashidx! =-1) dictEntry * dictFind (dict * d, const void * key) {dictEntry * he; unsigned int h, idx, table; if (d-> ht [0] .used + d-> ht [1] .used = 0) return NULL; / * dict is empty * / if (dictIsRehashing (d)) _ dictRehashStep (d); h = dictHashKey (d, key); for (table = 0) Table ht [table] .sizemask; he = d-> ht [table] .table [idx]; while (he) {if (key==he- > key | | dictCompareKeys (d, key, he- > key)) return he; he = he- > next;} if (! dictIsRehashing (d)) return NULL;} return NULL;}

The source code of the above dictFind does the following things in turn, depending on whether dict is currently re-hashing:

If re-hashing is currently in progress, the re-hashing process is pushed one step forward (that is, call _ dictRehashStep). In fact, in addition to finding, inserts and deletes also trigger this action. This distributes the heavy hashing process among the various find, insert, and delete operations, rather than focusing on one operation to do it all at once.

Calculate the hash value of the key (call dictHashKey, and the implementation in it invokes the previously mentioned hashFunction).

First look it up on the first hash table ht [0]. Locate the position corresponding to the hash value on the table array (bitwise and sizemask with the hash value as mentioned earlier), and then look it up on the corresponding dictEntry linked list. When looking up, you need to compare the key. Call dictCompareKeys at this time, and the implementation in it will call the keyCompare mentioned earlier. Return the item if it is found. Otherwise, proceed to the next step.

Determine whether a heavy hash is currently in progress, and if not, the search result on ht [0] is the final result (if not found, NULL is returned). Otherwise, make a search on ht [1] (the process is the same as the previous step).

Next we need to take a look at the implementation of _ dictRehashStep with incremental double hashing.

Static void _ dictRehashStep (dict * d) {if (d-> iterators = = 0) dictRehash (dMag1);} int dictRehash (dict * d, int n) {int empty_visits = nasty 10; / * Max number of empty buckets to visit. * / if (! dictIsRehashing (d)) return 0; while (while-& & d-> ht [0] .used! = 0) {dictEntry * de, * nextde; / * Note that rehashidx can't overflow as we are sure there are more * elements because ht [0] .used! = 0 * / assert (d-> ht [0] .size > (unsigned long) d-> rehashidx) While (d-> ht [0] .table [d-> rehashidx] = = NULL) {d-> rehashidx++; if (--empty_visits = = 0) return 1;} de = d-> ht [0] .table [d-> rehashidx]; / * Move all the keys in this bucket from the old to the new hash HT * / while (de) {unsigned int h Nextde = de- > next; / * Get the index in the new hash table * / h = dictHashKey (d, de- > key) & d-> ht [1] .sizemask; de- > next = d-> ht [1] .table [h]; d-> ht [1] .table [h] = de; d-> ht [0] .used -; d-> ht [1] .used + + De = nextde;} d-> ht [0] .table [d-> rehashidx] = NULL; d-> rehashidx++;} / * Check if we already rehashed the whole table... * / if (d-> ht [0] .used = 0) {zfree (d-> ht [0] .table); d-> ht [0] = d-> ht [1]; _ dictReset (& d-> ht [1]); d-> rehashidx =-1; return 0;} / * More to rehash... * / return 1;}

DictRehash pushes the heavy hash forward at least n steps at a time (unless the whole heavy hash ends in less than n steps), each step moves each dictEntry on a bucket (that is, a dictEntry linked list) on ht [0] to ht [1], and its new position on ht [1] is recalculated according to the sizemask of ht [1]. Rehashidx records the bucket location of ht [0] that has not yet been migrated (to be migrated).

If when dictRehash is called, there is no dictEntry in the bucket that rehashidx points to, then it has no data to be migrated. It then tries to iterate backwards through the ht [0] .table array until it finds the next bucket location where the data is stored. If you can't find it all the time, take a maximum of 10 steps, and this heavy hash is over for now.

Finally, if all the data on ht [0] is migrated to ht [1] (that is, d-> ht [0] .used = 0), then the whole heavy hash ends, ht [0] becomes the content of ht [1], and ht [1] is reset to null.

From the above analysis of the heavy hashing process, it is easy to see that what is shown in the previous dict structure diagram of this article is the case of rehashidx=2, and the first two bucket (ht [0] .table [0] and ht [0] .table [1]) have been migrated to ht [1].

Insertion of dict (dictAdd and dictReplace)

DictAdd inserts a new pair of key and value, or fails if key already exists.

DictReplace also inserts a pair of key and value, but it updates the value when key exists.

Int dictAdd (dict * d, void * key, void * val) {dictEntry * entry = dictAddRaw; if (! entry) return DICT_ERR; dictSetVal (d, entry, val); return DICT_OK;} dictEntry * dictAddRaw (dict * d, void * key) {int index; dictEntry * entry; dictht * ht; if (dictIsRehashing (d)) _ dictRehashStep (d); / * Get the index of the new element, or-1 if * the element already exists. * / if ((index = _ dictKeyIndex (d, key)) =-1) return NULL; / * Allocate the memory and store the new entry. * Insert the element in top, with the assumption that in a database * system it is more likely that recently added entries are accessed * more frequently. * / ht = dictIsRehashing (d)? & d-> ht [1]: & d-> ht [0]; entry = zmalloc (sizeof (* entry)); entry- > next = ht- > table [index]; ht- > table [index] = entry; ht- > used++; / * Set the hash entry fields. * / dictSetKey (d, entry, key); return entry;} static int _ dictKeyIndex (dict * d, const void * key) {unsigned int h, idx, table; dictEntry * he; / * Expand the hash table if needed * / if (_ dictExpandIfNeeded (d) = = DICT_ERR) return-1; / * Compute the key hash value * / h = dictHashKey (d, key); for (table = 0; table httable] .sizemask / * Search if this slot does not already contain the given key * / he = d-> ht [table] .table [idx]; while (he) {if (key==he- > key | | dictCompareKeys (d, key, he- > key) return-1; he = he- > next;} if (! dictIsRehashing (d)) break;} return idx;}

The above is the key implementation code of dictAdd. We mainly need to pay attention to the following points:

It also triggers the push of a heavy hash (_ dictRehashStep).

If you are in a heavy hash, it inserts the data into ht [1]; otherwise, it inserts into ht [0].

When inserting data in the corresponding bucket, it is always inserted into the head of the dictEntry. Because the probability of new data being accessed next may be higher, there will be fewer comparisons when looking for it again.

_ dictKeyIndex looks for the insertion location in the dict. If not in the heavy hashing process, it only looks for ht [0]; otherwise, it looks for ht [0] and ht [1].

_ dictKeyIndex may trigger dict memory expansion (_ dictExpandIfNeeded, which doubles the length of the hash table. For more information, please refer to the source code in dict.c).

DictReplace is implemented on the basis of dictAdd as follows:

Int dictReplace (dict * d, void * key, void * val) {dictEntry * entry, auxentry; / * Try to add the element. If the key * does not exists dictAdd will suceed. * / if (dictAdd (d, key, val) = = DICT_OK) return 1; / * It already exists, get the entry * / entry = dictFind (d, key); / * Set the new value and free the old one. Note that it is important * to do that in this order, as the value may just be exactly the same * as the previous one. In this context, think to reference counting, * you want to increment (set), and then decrement (free), and not the * reverse. * / auxentry = * entry; dictSetVal (d, entry, val); dictFreeVal (d, & auxentry); return 0;}

When key already exists, dictReplace calls dictAdd and dictFind at the same time, which is actually equivalent to two lookups. The Redis code here is not optimized enough.

Deletion of dict (dictDelete)

The source code of dictDelete is ignored here. For details, please refer to dict.c. What needs to be paid attention to is:

DictDelete will also trigger the push of a heavy hash (_ dictRehashStep)

If it is not currently in the re-hashing process, it only looks for the key; to be deleted in ht [0] otherwise it will look for both ht [0] and ht [1].

The destructors (keyDestructor and valDestructor) for key and value are called after a successful deletion.

The above is what is the function of the internal data structure dict in Redis. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.