In dictionaries, a key and a value are associated, and by such a relationship, they are called key-value pairs. The internal data structure of a dictionary is basically composed of multiple key-value pairs. Redsi uses C as its implementation, but UNLIKE most other languages, C does not have dictionary data structures built in, so Redis implements its own dictionary structures.

Dictionary Application Scenarios

The dictionary is basically the most widely used in Redis. For example, the database of Redis uses the dictionary as its underlying implementation. The addition, deletion, modification and check of the database are all based on the operation of the dictionary. There are also data types that Redis often uses: Hash, and Zset also use dictionaries as one of their underlying data structure implementations. And the key set with expiration time in Redis also uses dictionaries as an implementation of the underlying data structure.

Dictionary structured content

A dictionary structure with no normal state being rehash:

Specific structure code:

typedef struct dict {    

    // Type specific functions
    dictType *type;   
    
    // Private data
    void *privdata;   
    
    / / a hash table
    dictht ht[2];   
    
    / / rehash index
    // When rehash is not in progress, the value is -1
    int rehashidx; 
    
    // The number of security iterators currently running
    int iterators; 
    
} dict;
Copy the code

The left-hand side of the diagram represents the dict dictionary structure. The Type and privData properties are designed to be stored in dictionaries for different types of key-value pairs, creating dictionary polymorphisms.

The Type attribute is a pointer to the dictType structure. Each dictType structure contains multiple functions that operate key value pairs of a specific type, so that different type-specific functions can be set for different dictionaries.

The privadate attribute holds the optional arguments that need to be passed to the above specific type of function.

DictType Structure specific code:

typedef struct dictType {    

    // The function that calculates the hash value
    unsigned int (*hashFunction)(const void *key);   

    // Copy the key function
    void *(*keyDup)(void *privdata, const void *key);    

    // Copy the value of the function
    void *(*valDup)(void *privdata, const void *obj);    

    // Compare key functions
    int (*keyCompare)(void *privdata, const void *key1, 
    const void *key2);    

    // The function that destroys the key
    void (*keyDestructor)(void *privdata, void *key);        

    // A function that destroys values
    void (*valDestructor)(void *privdata, void *obj);
    
} dictType;
Copy the code

The HT attribute is a two-length array, each of which is a Dictht hash table. Normally, the dictionary only uses the HT [0] hash table without rehash. The HT [1] hash table will rehash the HT [0] hash table only when rehash is performed. Use both tables at the same time.

Of course, rehashidx is only used for rehash purposes, and it keeps track of the progress of the rehash. If no rehash has occurred, the value of rehashidx is -1.

Hash table structure content

The ht attribute mentioned above contains two hash tables. The structure of each hash table is as follows:

The table property in a hash table is an array, and each element in the array is a pointer to a dictEntry structure that holds a key-value pair.

The size property holds the size of the hash table array, which is also the size of the hash table. For example, the table attribute in the picture points to four dictEntry structures, so the size value is 4.

The used property holds the number of existing key-value pairs in the hash table. There are two key-value pairs in the image, so the used value is 2.

The sizemask attribute always equals size-1. This attribute, along with the hash value, calculates which index a key should be placed on in the table array.

Hash table structure concrete code:

typedef struct dictht {     

    // Hash table array
    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 key-value pairs in the hash table
    unsigned long used;

} dictht;

Copy the code

Hash table node structure content

The dictEntry nodes mentioned above are hash table nodes, and each hash table node stores a key-value pair.

DictEntry structure specific code:

typedef struct dictEntry {      

    / / key
    void *key;   

    / / value
    union {        
        void *val;        
        uint64_t u64;       
        int64_t s64;    
    } v;   

    // Point to the next hash table node to form a linked list
    struct dictEntry *next;

} dictEntry;
Copy the code

The key attribute in dictEntry structure stores the keys in the key-value pair, while the V attribute stores the values in the key-value pair. According to the code, the V attribute can be a pointer, a Uint64_t integer, or an INT64_T integer.

The next property is a pointer to another hash table node that joins key-value pairs of the same hash value together to form a linked list that can be used to resolve key collisions.

For example, in the figure below, the hash values of key1 and key2 calculated by the hash algorithm and sizemask are both equal to 2 after bitwise and operation, which will put them into slot 2 of the array. At this time, a conflict occurs, so the next pointer is used to connect the two to solve the hash conflict.

The hash algorithm

When a new key-value pair is about to be added to the hash table array or the corresponding value is to be found by the key, the program needs to perform the hash algorithm, obtain the corresponding cable of the key, and then perform related operations.

Specific hashing algorithm steps:

1. Use the hash function in the dictionary’s type attribute to get the hash value of the key

hash = dict->type->hashFunction(key);
Copy the code

2. According to the sizemask attribute and hash value of the hash table, bitwise and calculation are performed to calculate the index ht[x], which can be HT [0] or HT [1].

idnex = hash & dict->hx[x].sizemask;
Copy the code

Resolve hash conflicts

When the two keys pass the above hash algorithm and the index values of the two keys are the same, hash conflict occurs at this time. In order to solve hash conflict, Redis adopts the form of linked list and sets a next pointer on each hash table node. The next pointer connects the conflicting keys to form a one-way linked list. Each index on the hash table array can hold multiple hash table nodes.

Multiple hash table, singly linked list of nodes because there is no pointer to the tail chain table, add Redis such high performance architectural thought, directly to the next time we need to new added to the list of the hash table node directly added to the list of header position, directly in the list first, so that the time complexity is O (1), greatly improve the performance of the data structure.

rehash

In the actual production process of a dictionary structure, the hash table in the dictionary may store more or less key-value pairs as the business develops. In order to keep the load factor within a reasonable range, that is, when the hash table stores too many key-value pairs or too few key-value pairs, The program needs to rehash to expand or shrink the hash table size.

Load factor meaning: Used to indicate a program in which elements are filled in a hash conflict. The greater the chance of hash conflicts, the higher the cost of lookups. Conversely, the lower the cost of the search, the less time the search takes.

Here a load factor is equal to the number of nodes currently in use divided by the size of the hash table:

load_factor = ht[0].used / ht[0].size
Copy the code
Rehash steps

1. Allocate memory for the HT [1] hash table of the dictionary. The amount of memory allocated is determined by the operation to be performed and the number of key-value pairs ht [0] currently holds (the value of ht [0].

When the load factor of the hash table is greater than or equal to 5 and the server is running BGSAVE or BGREWRITEAOF or

When the load factor of the hash table is greater than or equal to 1, the server does not run the BGSAVE or BGREWRITEAOF command

The size of ht [1] is the first one greater than or equal to (ht [0]. Used * 2) to the power of 2 to the n

When the load factor of the hash table is less than 0.1

Perform the shrink operation: the size of HT [1] is the first one greater than or equal to (HT [0].used) to the power of 2 n

2. All key/value pairs saved on HT [0] are then rehash to HT [1]. Rehash means to recalculate the key hash and index and reinsert the key/value pairs into the corresponding index of HT [1].

3. When all key-value pairs on HT [0] are migrated to HT [1], the memory of HT [0] is released, and HT [1] is changed to HT [0] to create an empty HT [1] hash table for the next rehash operation.

That’s the end of the process

Note:

Depending on whether the server executes BGSAVE or BGREWRITEAOF, the load factor required for the extension operation varies.

This is because Redis creates a child of the current server process when executing the BGSAVE or BGREWRITEAOF command, and most operating systems use copy-on-write techniques to optimize the use of the child process. If rehash is performed while the child process is in existence and the load factor is low during the extension operation, memory will be consumed even more in cases where the original child process is already occupied. So you need to increase the value of the load factor to save as much memory as possible.

Progressive rehash

If all key pairs in the HT [0] hash table are rehashed to the HT [1] hash table at once, then in the production process, if multiple dictionaries, a large number of key pairs need to rehash, the server performance will be a fatal blow, and may be down. So you have to be progressive when you rehash.

Progressive Rehash execution steps:
  1. First, space is allocated for the HT [1] hash table so that the dictionary holds both HT [0] and HT [1]
  2. Setting the value of the rehashidx property in the dictionary to 0 indicates the beginning of rehash
  3. In addition to performing the specified operation, the program rehashes all key/value pairs in the HT [0] rehashidx index into the HT [1] hash table every time the dictionary is added, deleted, changed, or checked during rehash. The program increments the value of the rehashidx property by one
  4. As the operation increases, the program sets the rehashidx property to -1 to indicate that the rehash is complete when all key-value pairs on HT [0] are rehashed into the HT [1] hash table.

conclusion

Through the internal structure content of the dictionary and the related operation of the hash table content, realize that redis in order to achieve high performance indicators, through the design of data structure, the optimization of operation steps and other means, to make redis dictionary structure better be applied.

Reference: Redis Design and Implementation

For more Java backend development related technologies, you can follow the public account “Red Orange ah”.