Shulou(Shulou.com)06/01 Report--

This article mainly explains "what are the knowledge points of Redis dictionary". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what are the knowledge points of Redis dictionary".

Dictionary data structure

Speaking of dictionaries, we may be unfamiliar, but we all know how Redis itself provides KV queries, and this KV is actually saved through dictionaries through the underlying layer.

In addition, Redis supports multiple data types, one of which is the Hash key, which can also be used to store KV data.

When A Fan first learned about this data structure, he thought it was realized by using a dictionary. In fact, this is not the case, the initial creation of the Hash key, the default use of another data structure-"ZIPLIST" (compressed list), to save memory space.

However, once any of the following conditions are met, the data structure of the Hash key will become a dictionary, speeding up the query.

The length of a key or value in the hash table is greater than server.hash_max_ziplist_value (the default is 64). The number of nodes in the compressed list is greater than server.hash_max_ziplist_entries (default is 512).

When the Redis dictionary is created, an array of hash tables will be created by default, and two hash tables will be saved.

The ht [0] hash table allocates memory space when the key value is added to the dictionary for the first time, while another ht [1] will not allocate space until it is expanded / reduced below.

The hash table in the dictionary is actually equivalent to Java HashMap. We know that Java is implemented by array plus linked list / red-black tree. In fact, hash tables use similar data structures.

The hash table structure is as follows:

The table attribute is an array in which the array element holds a dictEntry structure that is exactly similar to the Entry type in HashMap, which stores a KV key-value pair.

At the same time, in order to solve the problem of hash collisions, dictEntry has a next pointer to the next dictEntry, which forms a linked list of dictEntry.

Now, when we look back at HashMap in Java, we can see that the data structures of the two are basically the same.

However, in order to solve the problem of too long linked list, HashMap uses the red-black tree data structure when there are too many linked list elements in JDK1.8.

Let's start adding new elements to understand how this works.

Element addition process

When we add elements to a new dictionary, the ht [0] hash table in the dictionary is allocated space by default, and by default the table array size of the hash table is 4 ("DICT_HT_INITIAL_SIZE").

The key value of the newly added element will go through the hash algorithm, determine the location of the hash table array, and then add it to the appropriate location, as shown in the figure:

Continue to add elements, and if two different keys pass through the hash algorithm to produce the same hash value, a hash collision occurs.

Suppose we now have three elements in our hash table:

We add a new element, and if the collision happens at the position of array 3, Redis will use a linked list to solve the hash collision.

"Note that the new element will be placed in the chain header node because the newly added element will most likely be accessed again and will be placed in the header node to increase access speed. "

Here we compare the element addition process, and we can see that the Redis process is actually similar to HashMap in JDK 1.7.

As we add more and more elements, hash collisions will become more and more frequent, which will lead to long linked lists and, in extreme cases, O (1) query efficiency will be reduced to O (N) query efficiency.

To do this, the dictionary must be expanded so that the dictionary rehash operation will be triggered.

Expand capacity

When Redis performs the Rehash expansion operation, it will first allocate more space for the unused ht [1] hash table of the dictionary.

❝

Voiceover: ht [1] Hash table size is the first greater than or equal to ht [0] .2 ^ 2 of used * 2 (2 to the power of n)

❞

Then all key-value pairs in ht [0] are migrated to ht [1].

For simplicity, ignore pointing to empty nodes

When all nodes are migrated, the ht [0] footprint will be freed and ht [1] will be set to ht [0].

In the expansion operation, all key-value pairs of ht [0] need to be Rehash to ht [1]. If there are too many key-value pairs, it is assumed that there are a billion key-value pairs. Such an one-time migration will inevitably cause the server to stop service within a period of time.

In addition, if each rehash blocks the current operation, it is very unfriendly to the client processing.

In order to avoid the impact of rehash on the server, Redis adopts a gradual migration method, slowly dispersing the data migration to multiple operating steps.

This operation relies on an attribute in the dictionary, rehashidx, which is an index position counter that records elements on the next hash table table array, with a default value of "- 1".

Suppose the dictionary before capacity expansion is shown in the figure:

When you start the rehash operation, rehashidx will be set to "0".

During this period, each time you receive add, delete, find, update commands, in addition to the commands that will be executed, the element of the ht [0] hash table in the rehashidx location will be rehash to ht [1].

Assuming that you receive a query operation with a "K3" key, Redis first performs the query operation, and then Redis will migrate all nodes on the rehashidx index of the table array on the ht [0] hash table to ht [1].

When the operation is complete, add 1 to the value of the rehashidx attribute.

Finally, when all key-value pairs are rehash into ht [1], rehashidx will be reset to-1.

Although the progressive rehash operation reduces the workload, it brings the complexity of key-value operation.

This is because during the progressive rehash operation, Redis cannot clearly know whether the key is in ht [0] or in ht [1], so Redis has to look up two hash tables at this time.

Take lookup as an example, Redis first queries ht [0], and if it does not find it, it will continue to search for ht [1]. In addition to the query, updates and deletions will also perform the same operation as above.

Adding operations is actually not so troublesome, because ht [0] will not be used, so it would be nice to add all of them to ht [1].

Finally, let's compare the Java HashMap expansion operation. It is an one-time operation, and all key-value pairs need to be migrated to a new array for each expansion, so if the amount of data is large, it will take a long time.

Thank you for your reading, these are the contents of "what are the knowledge points of Redis Dictionary". After the study of this article, I believe you have a deeper understanding of what are the knowledge points of Redis Dictionary, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.