Capacity expansion mechanism of Dict Of redis (rehash)

redis Supported by data structure Yes ：

1. string character string （ It can be used for plastic surgery 、 floating-point And string , Collectively referred to as element ）,String Type is binary safe , intend redis Of string Can contain any data .
2. List  Linked list （redis Use Double ended linked list Realized List）, Is ordered ,value Can be repeated , You can get the corresponding by subscript value value , You can insert and delete data on both sides .
3. dict Dictionaries ( Hash value ),hash map Of key Must be unique .
4. set Collection of elements that hold multiple strings , But unlike the linked list, in the set   1. Duplicate elements are not allowed ,2. Elements in a collection are unordered , Elements cannot be retrieved by index index ,3. Support operations between sets , You can take more than one set and take the intersection 、 Combine 、 Difference set .
5. zset Ordered set , It preserves the feature that the collection cannot have duplicate members , The difference is that , Elements in an ordered set can be ordered , It sets a score for each element , Sort by .

among dict It is used quite frequently , It is also a very practical structure , Use hash table as the underlying implementation , There can be multiple hash table nodes in a hash table , Each hash table node holds a key value pair in the dictionary , The key value pairs in the hash table increase or decrease as operations continue , In order to set the hash table's Load factor Maintain within a reasonable range , The program needs to expand or shrink the size of the hash table . stay redis In the implementation of , Used a kind called ** Progressive hash (rehashing)** To improve dict Zoom efficiency .

Source code explanation

dict Data structure definition of ：

/*  Hash table node  */



typedef struct dictEntry {

    //  key 
    void *key;

    //  value 
    union {

        void *val;

        uint64_t u64;

        int64_t s64;

    } v;

    //  Point to next hash table node , Form a linked list 
    struct dictEntry *next;

} dictEntry;


/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */

/*  Hashtable 
 *  Each dictionary uses two hash tables , To achieve progressive  rehash .
 */
typedef struct dictht {

    //  Hash table array 
    //  It can be seen as ： A hash table array , Each item of the array is entry The head node of the list （ The chain address method solves the hash conflict ）
    dictEntry **table;

    //  Hash table size 
    unsigned long size;

    //  Hash table size mask , Used to calculate index values 
    //  Always equal to  size - 1
    unsigned long sizemask;

    //  The number of existing nodes in the hash table 
    unsigned long used;

} dictht;



/*  Dictionaries  */
typedef struct dict {

    //  Type specific function 
    dictType *type;

    //  Private data 
    void *privdata;

    //  Hashtable 
    dictht ht[2];

    // rehash  Indexes 
    //  When  rehash  When not in progress , The value is  -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    //  Number of security iterators currently running 
    int iterators; /* number of iterators currently running */

} dict;

dict The structure of is roughly as above , Next, let's analyze some of the most important data members ：

1. dictht::table： Inside the hash table table Structure used Chain address To resolve hash conflicts , At first I was very strange , How can this be a two-dimensional array ？ This is actually a pointer to an array , Every item in the array is entry The head node of the list .
2. dictht ht[2]： stay dict Internal , Maintained two hash tables , The effect is equivalent to a pair of scrolling arrays , A watch is Old table , A watch is New table , When hashtable When the size of needs to change dynamically , The elements in the old table are migrated to the new table , Next change in size , The current new table becomes the old table , So as to achieve the reuse of resources and the improvement of efficiency .
3. rehashidx： the reason being that Progressive hashing , Data migration is not a one-step process , So you need an index to Indicates the current rehash speed of progress . When rehashidx by -1 when , No hash operation .

rehash The main part of ：

/* Performs N steps of incremental rehashing. Returns 1 if there are still

 * keys to move from the old to the new hash table, otherwise 0 is returned.
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
   
    if (!dictIsRehashing(d)) return 0;

    while(n-- && 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) {

            uint64_t 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;

}

The best way to understand the function of a function is its comments . We can get a general idea ：

rehash In order to bucket( bucket ) Incremental data migration for basic units , Complete one step at a time bucket Migration , Until all data is migrated . One bucket Corresponding to one in the hash table array entry Linked list . The new version of the dictRehash() A maximum number of empty buckets accessed is also added (empty_visits) To further reduce the time that may cause blocking .

Go deep into the specific implementation of this function .

1. Judge dict Is it rehashing, Only yes , To continue , Otherwise, the hash process has ended , Go straight back to .
2. Then there are points n Step progressive hash body part （n Passed in by function parameters ）, stay while Add right to the condition of .used Observation of the number of remaining elements in the old table , Increase security .
3. One runtime The assertion of ensures that the index of the progressive hash does not cross the bounds .
4. Next a little while To skip over empty barrels , At the same time, update the number of empty buckets that can be accessed , Maximum number of empty buckets accessed empty_visits The function of this variable has been mentioned before .
5. Now we come to the present bucket, The next while(de) To migrate all of its elements to ht[1] in , The index value is calculated by the size mask of the hash table , You can guarantee that you won't cross the line . The current number of elements in both tables is updated .
6. Each step rehash end , Increase the index value , And the old tables that have been migrated bucket Set to null pointer .
7. Finally, judge whether all the old tables have been migrated , if , Then recycle space , Reset old table , Reset the index of progressive hash , Otherwise, the return value is used to tell the caller ,dict There are still data not migrated .

The essence of progressive hashing ： Data migration is not completed at one time , But through dictRehash() This function is planned step by step , And the caller can know in time whether to continue the progressive hash operation . If dict A large amount of data is stored in the data structure , Then one-time migration is bound to bring redis Performance degradation , Don't forget redis It is a single-threaded model , This can be fatal in real-time scenarios . Progressive hashing allocates this cost controllably , The caller can be in dict Insert , Delete , Execute when updating dictRehash(), Minimize the cost of data migration .
In the process of migration , Whether the data is in the new table or the old table is not a very urgent requirement , The migration process does not lose data , If you can't find it in the old table, just look in the new table .

rehash

Trigger rehash The mechanism of ：

1. The server is not currently executing BGSAVE Order or BGREWRITEAOF command , And the load factor of hash table is greater than or equal to 1 , Perform extended operations ;
2. The server is currently executing BGSAVE Order or BGREWRITEAOF command , And the load factor of hash table is greater than or equal to 5, Perform extended operations ;
3. When the load factor of the hash table is less than 0.1 when , The program automatically starts to shrink the hash table .

The load factor of hash table can be calculated by formula ： Load factor = Number of nodes saved in hash table / Hash table size load_factor = ht[0].used / ht[0].size calculated .
    for instance , For a size of 4 , contain 4 For hash table of key value pairs , The load factor of this hash table is ：load_factor = 4 / 4 = 1
    Again for instance , For a size of 512 , contain 256 For hash table of key value pairs , The load factor of this hash table is ：load_factor = 256 / 512 = 0.5

according to BGSAVE Order or BGREWRITEAOF Whether the order is being executed , The load factor required by the server to perform the expansion operation is not the same , This is because of the implementation BGSAVE Order or BGREWRITEAOF In the course of the order , Redis You need to create a child of the current server process . Most operating systems use copy on write （copy-on-write） Technology to optimize the efficiency of sub processes , So during the existence of the child process , The server increases the load factor required to perform the expansion operation , So as to avoid the expansion of hash table during the existence of child process , This avoids unnecessary memory writes , Maximize memory savings .

rehash The process ：

1. ht[1] Allocate space , Let the dictionary hold ht[0] and ht[1] Two hash tables .
2. Maintain an index counter variable in the dictionary rehashidx , And set its value to 0 , Express rehash Work officially begins .
3. stay rehash During the process , Every time the dictionary is added 、 Delete 、 When searching or updating operations , In addition to performing the specified operations , By the way ht[0] The hash table is in rehashidx All key value pairs on the index rehash To ht[1] , When rehash When the work is done , Program will rehashidx The value of the property is increased by one .
4. With the continuous execution of dictionary operation , At some point in time , ht[0] All key value pairs of will be rehash to ht[1] , At this point the program will rehashidx Property is set to -1 , Express rehash Operation completed .

About rehash In the process ht Array changes ：

For the dictionary ht[1] Hash table allocation space , The size of the hash table depends on the operation to be performed , as well as ht[0] The number of key value pairs currently contained （ That is to say ht[0].used The value of the property ）：

• If you are performing an extension operation , that ht[1] The size of the first is greater than or equal to ht[0].used * 2 Of 2^n （2 Of n Power of power ）;
• If you are performing a shrink operation , that ht[1] The size of the first is greater than or equal to ht[0].used Of 2^n.

Will be saved in ht[0] All key value pairs in rehash To ht[1] above ：rehash It refers to recalculating the hash value and index value of the key , Then place the key value pair in ht[1] On the specified location of the hash table .

When ht[0] All key value pairs contained are migrated to ht[1] after （ht[0] Becomes an empty table ）, Release ht[0] , take ht[1] Set to ht[0] , And in ht[1] Create a new blank hash table , For the next time rehash To prepare for .

Reference resources 《Redis Design and implementation 》 The illustration  ：

• Get ready to start rehash​

• rehash Indexes 0 Key value pairs on ​

• rehash Indexes 1 Key value pairs on ​

• ehash Indexes 2 Key value pairs on ​

• rehash Indexes 3 Key value pairs on ​

• rehash completion of enforcement

​

Progressive type rehash Hash table operations during execution

Because it's progressive rehash In the process of , The dictionary will use ht[0] and ht[1] Two hash tables , So in progressive rehash During the process , The deletion of the dictionary （delete）、 lookup （find）、 to update （update） The operation will be performed on two hash tables . for example , To find a key in a dictionary , The program will start with ht[0] Search inside , If you don't find it , It will continue until ht[1] Search inside , And so on .

in addition , In a progressive way rehash During execution , All new key value pairs added to the dictionary will be saved to ht[1] Inside , and ht[0] No more add operations , This measure guarantees ht[0] The number of key value pairs contained will only decrease but not increase , And with rehash The execution of the operation turns into an empty table .​

Reference resources ：

《Redis Design and implementation 》

Talking about Redis Medium Rehash Mechanism _CodingQK The blog of -CSDN Blog _redis rehash