In-depth understanding of Redis - Dict dictionary

Written in the book before

This series of articles has been included in the Redis column, so if you are interested, you can read more about Redis

Introduction to the

Redis dictionary is realized by Hash function, which is familiar to most readers. The most typical one in Java is HashMap, so I will not introduce its basic principle too much. However, in Redis, since Redis is single-threaded, special processing will be done in the case of expansion, reduction, iteration, etc., which is different from our Java HashMap.

The data structure

The dictionary in Redis is divided into several sections

1. A Hash table

/* 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;
Copy the code

The Hash table looks like this:

**size: ** Specifies the length of the hash table to store. The initial value is 4#define DICT_HT_INITIAL_SIZE 4Control.
**table: ** pointer array, where Redis does not insert the entry array into the Hash table, but stores the address of the entry array.
**sizemask: ** Used to map hash values to the table’s positional index, with each key passing firsthashFunctionCompute a hash value, and then computehashcode & sizemaskGet a position on the table. It’s the same thing as calculating modhashcode % size. (Redis has optimized this calculation for high performance, and bit operations are much faster than remainder operations)
** Used: ** Stores how many elements are in the entry array.

2. Hash table nodes

The concrete implementation is dictEntry, and the related structures are as follows:

typedef struct dictEntry {
    void *key;	/* Store key */
    union {
        void *val;		// Can store any type
        uint64_t u64;
        int64_t s64;	
        double d;
    } v;		
    struct dictEntry *next;		// Zip to resolve hash conflicts
} dictEntry;
Copy the code

**v: ** is a consortium, expressed in sectors, int64, and double, such as when we store the expiration date of a key in the dictionarys64, can be used if it is to store some complex types*val
** Next: ** Uses zip to resolve hash conflicts, and inserts are head-insertions
**key: ** address of the storage key

3. The dictionary

Redis encapsulates the Hash table, which can be used during expansion and iteration:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
Copy the code

**type: ** a pointerdictTypePointers to structures. It enables dict keys and values to store any type of data.
** privData: ** A private data pointer passed in by the caller when creating a dict and used in conjunction with the function pointed to by the type field.
** HT [2] : ** Stores two hash tables in a dictionaryht[0]The top one is only used for scaling up or scaling down
**rehashidx: ** As the comment states, a value of -1 indicates that no rehash has been performed; otherwise, the value is used to represent the Hash tableht[0]Which element is rehash to, and record the array subscript value for that element.
Iterators: ** is used to record the number of safe iterators currently running. A value that is not zero indicates that a safe iterator is running, which suspends the rehash operation.

The type field is used to distinguish the use of Redis dictionaries. The type field is used to distinguish the use of Redis dictionaries.

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key); // The Hash function corresponding to the dictionary
    void *(*keyDup)(void *privdata, const void *key); // The copy function corresponding to the key
    void *(*valDup)(void *privdata, const void *obj); // The copy function corresponding to the value
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // Key alignment
    void (*keyDestructor)(void *privdata, void *key); // The key destruction function
    void (*valDestructor)(void *privdata, void *obj); // The destruction function of the value
} dictType;
Copy the code

These methods operate on keys and values. The Redis dictionary plays an important role in the entire Redis architecture. For example, in the Redis Sentinel mode, the dictionary is used to store and manage all the Master nodes and Slaver nodes. The function of the dictionary is different in each scenario, so this type is extracted and let them implement their respective operations. It’s kind of like abstract functions.

The above is the complete dictionary structure, you can taste the details of the structure.

Initialize the

After data structure, let’s look at dictionary initialization, which is actually very simple, nothing more than allocating memory, initialize an empty dictionary.

/* Create a new dictionary */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

/* Initialize the dictionary */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]); // Initialize the hash table
    _dictReset(&d->ht[1]); // Initialize the hash table
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = - 1;
    d->iterators = 0;
    return DICT_OK;
}

/* Reset a hash table already initialized with ht_init().
 * NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}
Copy the code

The only thing to notice is that dictht is empty after the successful creation of the dictionary.

Add and Expand

The operation of adding a Redis dictionary is similar to that of adding a Hashmap. We are here to talk about his expansion mechanism.

Rehash

Load_factor = used/ht[0].size

The difference with hashmap is that redis load_factor == 1 can expand.

The capacity reduction condition is load_factor == 0.1, that is, when used is 10% of HT [0]. Size.

The corresponding code for capacity expansion is:

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    /* the size is invalid if it is smaller than the number of * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);  // Recalculate the expanded value, which must be 2 to the power of N, for the same reason as hashmap

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize- 1;
    n.table = zcalloc(realsize*sizeof(dictEntry*)); // For non-initial application, the Hash table capacity is twice that of the current Hash table
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;	// Put the expanded array in HT [1]
    d->rehashidx = 0;	// Set the current dictionary state to capacity expansion. -1 means no capacity expansion
    return DICT_OK;
}
Copy the code

After capacity expansion, data migration is required. This process is to put the hashcode of the original element and the new sizemask into the new table.

Progressive Rehash

Redis is known to be a single-threaded execution pattern. When key pairs in the database reach millions or tens of millions, the normal rehash process will be slow to use, especially blocking the entire service. Redis has proposed the concept of progressive Rehash to solve this problem.

Simple process for capacity expansion:

When we perform add, delete, alter, and search operations, we will first determine whether the current dictionary state is rehash, and then call the dictRehashStep method to rehash the current element only once. In addition to this, Redis also automatically performs batch Rehash when the Redis server is idle, processing 100 elements at a time. After the Rehash is complete, switch the ht[0] and HT [1] values and change rehashidx to -1. The expansion is complete.

We can see that if there are 1000W data to rehash, we will only operate on one element at a time, which will spread the total time of rehash to each operation and greatly reduce the loss caused by expansion.

Delete and shrink

The operation of deletion is also relatively simple, and the general process is as follows

Find if the key exists in the dictionary
If it exists, remove the node from the list and free memory
The used field of the hashTable is -1
Determine whether the capacity needs to be reduced

Shrinkage capacity

If a node is deleted and the hash table usage is less than 10% of its size, the hash table will be shrunk to the lowest quadratic power to accommodate the current element. For example, size = 12, used = 6 size = 8

The corresponding code is:

void tryResizeHashTables(int dbid) {
    if (htNeedsResize(server.db[dbid].dict)) // Determine whether to reduce capacity: used/size<10%
    	dictResize(server.db[dbid].dict); // Perform capacity reduction
}
int dictResize (dict *d){ // The scaling function
    int minimal;
    minimal = d->ht[0].used;
    if (minimal < DICT_HT_INITIAL_SIZE) // The minimum capacity is 4
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand (d, minimal); // call the capacity expansion function
}
Copy the code

The dictionary traversal

Dictionary traversal is also important for dictionary structure, and dictionary traversal also involves traversal in various situations.

There are two types of traversal under Redis:

Full traversal: keys, read out all at once
Intermittent traversal: Scan: reads only part at a time and traverses several times

In the case of dictionaries, the developers designed an iterator traversal, and as anyone familiar with Java knows, the iterator traversal of a HashMap will result in an error if changes are made to elements in the container. The same problem occurs in Redis, where an element is iterated multiple times, or data is underiterated.

Iterator structure

Iterators for dictionaries in Redis:

/* If safe is set to 1 this is a safe iterator, that means, you can call * dictAdd, dictFind, and other functions against the dictionary even while * iterating. Otherwise it is a non safe iterator, and only dictNext() * should be called while iterating. */
typedef struct dictIterator {
    dict *d; // The iterated dictionary
    int index; // Which index value in the Hash table is currently iterated to
    int table, safe; // Table is used to indicate the current iterating Hash table, ht[0] and HT [1]. Safe is used to indicate whether the currently created Hash table is a safe iterator
    dictEntry *entry, *nextEntry;// Current node, next node
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;// The fingerprint of the dictionary. This value does not change when the dictionary is not changed, and changes when the dictionary is changed
} dictIterator;

Copy the code

**d: ** points to the iterated dictionary
**index: ** represents what index is currently read into the HashTable
**table: ** points to the hashTable currently being iterated over
**safe: indicates the ** flag to enable security iteration
Entry, nextEntry:The node pointing to the current iteration and its next node, isTo prevent the loss of the next node after the current node is deleted
**fingerprint: ** represents the state of the dictionary at a given time. This is called the dictionary fingerprint here because the value of this field is dictionary (dictThe Hash value generated by combining all the field values in the dictionary, so that any changes to the data in the dictionary will have different values. (method isdict.cUnder thedictFingerprintFunction)

All traversal

Iterators in Redis fall into two categories: plain iterators and security iterators.

Plain iterator

Iterators that only iterate over data

When a common iterator iterates data in the dictionary, it checks the fingerprint field value to ensure that the dictionary structure does not change during iteration and that the read data does not duplicate.

The main steps are as follows:

Safety iterator

You can modify data while traversing it

This type of iterator is simple in principle. If the current dictionary has a safe iterator running, no progressive rehash is performed, the rehash operation is paused and the dictionary data is not iterated repeatedly, thus ensuring the accuracy of the read data.

The main steps are as follows:

Create an iterator, setsafe=1
Loop over the Hash table node, first accessdictNextFunction is going to Hash the tableiderator++To ensure that the rehash is broken during iteration
After walking through, letiterator--To make sure rehash works properly

Intermittent traverse

Because full traversal will cause Redis to be unavailable for a certain period of time, Redis has added intermittent traversal operations, such as Scan, in later versions.

The idea of intermittent traversal is to set a cursor, traverse a part of the data each time, and return a new cursor value. The whole traversal process is carried out around the change of the cursor value to ensure that all the data can be traversed.

Obviously, cursor traversal can be affected by the following situations of rehash:

The entire process of intermittent traversal has no rehash, meaning only traversal is requiredht[0]Each element of.
From the beginning to the end of the iteration, the hash is expanded or shrunk, and the rehash is done exactly between iterations.
From the beginning to the end of an iteration, the hash table is being rehashed for one or more iterations.

For the second and third cases, Redis uses a reverse binary algorithm to ensure that cursor traversal is neither repeated nor omitted. This algorithm mainly takes advantage of the principle that rehash increases or decreases exactly by integer multiples. For specific implementation, check ~ in dictScan function under dict.c

Write in the last

This concludes this chapter’s exploration of dictionaries

I am a passer-by Xiao Zhang, a back end engineer lying on the road

If you are interested in my article, please support me and follow me to prevent getting lost

The resources

Redis 5.0 source
Redis 5 Design and Source Code Analysis
Redis’ progressive Rehash principle
Redis internal data structure details -dict

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

In-depth understanding of Redis – Dict dictionary

Written in the book before

Introduction to the

The data structure

Initialize the

Add and Expand

Rehash

Progressive Rehash

Delete and shrink

The dictionary traversal

Iterator structure

All traversal

Plain iterator

Safety iterator

Intermittent traverse

The resources

In-depth understanding of Redis – Dict dictionary

Written in the book before

Introduction to the

The data structure

Initialize the

Add and Expand

Rehash

Progressive Rehash

Delete and shrink

The dictionary traversal

Iterator structure

All traversal

Plain iterator

Safety iterator

Intermittent traverse

The resources

Related Posts

Python has three ways of traversing directories to help you find hidden files easily

Springboot interception in three ways and asynchronous implementation of the thinking

Gitlab CI instance Django