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

This article is from the Internet.

This series of articles will be sorted out in my Java interview Guide warehouse on GitHub. Please check out more wonderful content in my warehouse.

Https://github.com/h3pl/Java-Tutorial

Have some trouble with Star if you like.

The article was first posted on my personal blog:

Www.how2playlife.com

This article is one of "exploring the Design and implementation of Java" on the official account of Wechat [Redis Technology]. Part of the content of this article comes from the network. In order to explain the topic of this article clearly and thoroughly, and integrate a lot of technical blog content that I think is good, quote some good blog articles, if there is any infringement, please contact the author.

This series of blog posts will show you how to start to advanced, the basic usage of Redis, the basic data structure of Redis, and some advanced usage. At the same time, you also need to further understand the underlying data structure of Redis. Then, it will also bring Redis master-slave replication, clustering, distributed locks and other related content, as well as some usage and precautions as a cache. So that you can have a more complete understanding of the whole Redis-related technology system and form your own knowledge framework.

If you have any suggestions or questions about this series of articles, you can also follow the official account [Java Technology jianghu] to contact the author. You are welcome to participate in the creation and revision of this series of blog posts.

This article is the sixth in a series of "detailed explanation of Redis internal data structures". In this article, we discuss skiplist, an internal data structure of Redis.

Skiplist is used in Redis to implement the external data structure of sorted set. Sorted set provides a wide range of operations to meet a wide range of application scenarios. This also means that the implementation of sorted set is relatively complex. At the same time, the data structure of skiplist is unfamiliar to many people, because most of the algorithm courses in schools have not introduced this data structure in detail. Therefore, in order to introduce clearly enough, this article will take more space than the other articles in this series.

We will roughly divide it into three parts:

The classical skiplist data structure is introduced, and the simple algorithm is analyzed. The introduction of this part is not directly related to Redis. I will try to describe it in easy-to-understand language as much as possible. Discuss the concrete implementation of skiplist in Redis. In order to support some of the requirements of sorted set itself, several changes have been made to the corresponding implementation in Redis based on the classic skiplist. Discuss how sorted set is built on skiplist, dict and ziplist.

We will also cover two Redis configurations (in the ADVANCED CONFIG section of redis.conf) in our discussion:

Zset-max-ziplist-entries 128zset-max-ziplist-value 64

We will explain the meaning of these two configurations in detail during the discussion.

Note: the code implementation discussed in this article is based on the 3.2branch of the Redis source code.

Brief introduction of skiplist data structure

Skiplist is essentially a search structure, which is used to solve the search problem (Searching) in the algorithm, that is, to quickly find its location (or corresponding value) according to a given key.

When we introduced dict in the first article of the series "detailed explanation of Redis Internal data structures", we discussed that the solutions to general search problems can be divided into two categories: one is based on various balanced trees, and the other is based on hash tables. But skiplist is so special that it doesn't belong to these two categories.

This data structure was invented by William Pugh and first appeared in his paper "Skip Lists: A Probabilistic Alternative to Balanced Trees" published in 1990. Students who are interested in details can download the original paper and read it.

Skiplist, as its name implies, is first of all a list. In fact, it is developed on the basis of ordered linked lists.

Let's start with an ordered linked list, as shown in the following figure (the leftmost gray node represents an empty header node):

In such a linked list, if we want to find some data, we need to compare one by one from scratch until we find the node that contains the data, or until we find the first node that is larger than the given data (not found). In other words, the time complexity is O (n). Similarly, when we want to insert new data, we have to go through the same search process to determine the insertion location.

If we add a pointer to every two adjacent nodes, let the pointer point to the next node, as shown in the following figure:

In this way, all the newly added pointers are connected to a new linked list, but it contains only half the number of nodes (7, 19, 26 in the figure above). Now when we want to find the data, we can look it up along this new linked list. When you encounter a node larger than the data to be checked, go back to the original linked list and look for it. For example, we want to look for 23, and the path is in the direction pointed by the pointer marked red in the following image:

23 first compare with 7, then compare with 19, bigger than them, continue to compare backwards. But when compared with 26, 23 is smaller than 26, so go back to the linked list below (the original linked list) and compare with 22. 23 is larger than 22, continue to compare backwards with 26 along the pointer below. 23 is smaller than 26, indicating that data 23 does not exist in the original linked list, and its insertion position should be between 22 and 26.

During this lookup process, we no longer need to compare each node in the linked list one by one because of the newly added pointers. The number of nodes that need to be compared is only about half of the original.

In the same way, we can continue to add a pointer to each two adjacent nodes on the newly generated linked list at the upper level, thus generating a third layer linked list. As shown below:

In this new three-tier linked list structure, if we still look for 23, then the first thing to compare along the top linked list is 19, and it is found that 23 is larger than 19, and then we know that we only need to go to the back of 19 to continue to look, thus skipping all the nodes in front of 19 at once. As you can imagine, when the linked list is long enough, this multi-layer linked list search method allows us to skip many lower-level nodes, greatly speeding up the search speed.

Skiplist is inspired by the idea of a multi-layer linked list. In fact, according to the way the linked list is generated above, the number of nodes in each layer of the linked list is half the number of nodes in the lower layer, so the search process is very similar to a binary search, so that the time complexity of the search can be reduced to O (log n). However, this method has a big problem when inserting data. After a new node is inserted, the correspondence of 2:1 with a strict number of nodes on the upper and lower adjacent linked list will be disturbed. If this correspondence is to be maintained, all nodes behind the newly inserted node (including the newly inserted node) must be readjusted, which will degenerate the time complexity back to O (n). Deleting data has the same problem.

In order to avoid this problem, skiplist does not require a strict correspondence between the number of nodes between the upper and lower adjacent linked lists, but randomly gives a layer number (level) for each node. For example, if the random number of layers from a node is 3, then link it to the three-layer linked list from layer 1 to layer 3. To be clear, the following figure shows how to form a skiplist through a step-by-step insert operation:

From the above skiplist creation and insertion process, we can see that the number of layers of each node (level) is random, and inserting a new node will not affect the number of layers of other nodes. Therefore, the insert operation only needs to modify the pointer before and after the node is inserted, and does not need to adjust many nodes. This reduces the complexity of the insert operation. In fact, this is a very important feature of skiplist, which makes it significantly better than the balanced tree scheme in insertion performance. We'll talk about that later.

According to the skiplist structure in the figure above, it is easy to understand the origin of the name of this data structure. Skiplist, translated into Chinese, can be translated into "jump list" or "jump list", which means that in addition to the lowest layer 1 linked list, it will generate several layers of sparse linked lists, in which pointers deliberately skip some nodes (and the higher the list, the more nodes are skipped). This enables us to look up the data in the high-level linked list, then reduce it layer by layer, and finally down to the first layer linked list to accurately determine the location of the data. In the process, we skipped some nodes, thus speeding up the search.

The skiplist you just created contains a total of 4 layers of linked lists. Now suppose we still look for 23 in it. The following figure shows the search path:

It should be noted that the insertion process of each node demonstrated above actually goes through a similar search process before insertion, and then completes the insertion operation after determining the insertion location.

At this point, we are very clear about the find and insert operations of skiplist. The delete operation is similar to the insert operation, which is easy to imagine. We should also be able to easily implement these operations in code.

Of course, each node of skiplist in practical application should contain two parts: key and value. There is no specific distinction between key and value in the previous description, but the list is actually sorted by key, and the search process is compared according to key.

However, if you are exposed to skiplist for the first time, there must be a question: when a node is inserted, a random number of layers is selected, and the multi-layer linked list structure constructed only by such a simple random number operation can guarantee a good lookup performance. To answer this question, we need to analyze the statistical performance of skiplist.

Before the analysis, we also need to emphasize that the process of calculating random numbers when performing the insert operation is a very critical process, which has a very important impact on the statistical characteristics of skiplist. This is not an ordinary random number with uniform distribution, and its calculation process is as follows:

First of all, each node must have a layer 1 pointer (each node is in the layer 1 linked list). If a node has a layer I (I > = 1) pointer (that is, the node is already in the layer 1 to layer I linked list), the probability that it has a layer 1 pointer is p. The maximum number of layers of a node is not allowed to exceed a maximum value, recorded as MaxLevel.

The pseudo code for calculating the number of random layers is as follows:

RandomLevel () level: = 1 / / random () returns a random number while random () < p and level < MaxLevel do level: = level + 1 return level

The pseudo code of randomLevel () contains two parameters, one is p and the other is MaxLevel. In the skiplist implementation of Redis, the values of these two parameters are:

Performance Analysis of p = 1/4MaxLevel = 32skiplist algorithm

In this section, we will briefly analyze the time complexity and space complexity of skiplist in order to have an intuitive understanding of the performance of skiplist. If you are not particularly obsessed with the performance analysis of the algorithm, you can skip this section for a while.

Let's first calculate the average number of pointers contained in each node (probability expectation). The number of pointers contained in the node is equivalent to the extra space overhead (overhead) of the algorithm and can be used to measure space complexity.

From the pseudo code of the previous randomLevel (), it is easy to see that the higher the number of node layers, the lower the probability. The quantitative analysis is as follows:

The number of node layers is at least 1. The number of node layers greater than 1 satisfies a probability distribution. The probability that the number of node layers is exactly equal to 1 is 1murp. The probability that the number of node layers is greater than or equal to 2 is p, and the probability that the number of node layers is exactly equal to 2 is p (1murp). The probability that the number of node layers is greater than or equal to 3 is p 2, and the probability that the number of node layers is exactly equal to 3 is p 2 (1murp). The probability that the number of node layers is greater than or equal to 4 is p 3, while the probability that the number of node layers is exactly equal to 4 is p 3 (1murp).

Therefore, the average number of layers (that is, the average number of pointers included) of a node is calculated as follows:

It is now easy to calculate:

The average number of pointers contained in each node is 2 when pumped 1max 2, and 1.33 per node when pumped 1max 4 is used. This is also the space overhead of the skiplist implementation in Redis.

Next, to analyze the time complexity, let's calculate the average search length of skiplist. The search length refers to the number of hops spanned on the search path, and the number of comparisons in the search process is equal to the search length plus 1. Take the search path of search 23 marked in the previous figure as an example, starting from the head node in the upper left corner to node 22, with a search length of 6.

In order to calculate the search length, we need to use a few tricks here. We notice that when each node is inserted, its number of layers is calculated by the random function randomLevel (), and the random calculation does not depend on other nodes, and each insertion process is completely independent. Therefore, statistically speaking, the formation of a skiplist structure has nothing to do with the insertion order of nodes.

In this way, in order to calculate the search length, we can look at the search process backwards, starting from the last node on the first floor on the lower right, and going back left and up along the search path, similar to the process of climbing stairs. We assume that it is inserted only when it is traced back to a node, which is equivalent to changing the insertion order of the nodes, but does not statistically affect the formation structure of the whole skiplist.

Now suppose we start from a node x with a number of layers I, and we need to climb the k layer to the left. We have two possibilities at this time:

If node x has a layer 1 pointer, then we need to go up. The probability of this situation is p. If node x does not have a layer 1 pointer, then we need to go left. The probability of this situation is (1MRP).

These two scenarios are shown in the following figure:

Use C (k) to denote the average search path length (probability expectation) to climb k levels, then:

C (0) = 0C (k) = (1murp) × (the search length of case b in the figure above) + p × (the search length of case c in the figure above)

Replace it, get a difference equation and simplify it:

C (k) = (1Mui p) (C (k) + 1) + p (C (k) 1) + 1) C (k) = 1/p+C (k Muir 1) C (k) = k max p

What this result means is that for every level we climb, we need to take one step on the search path. And the total number of levels we need to climb is equal to the total number of layers of the whole skiplist-1.

Then we need to analyze what is the probability mean of the total number of layers when there are n nodes in the skiplist. This question is easier to understand intuitively. According to the random algorithm of the number of layers of nodes, it is easy to obtain:

The first layer linked list has fixed n nodes, the second layer linked list has an average of n nodes, and the third layer list has an average of 2 nodes.

Therefore, from the first layer to the highest level, the average number of nodes in the linked list of each layer is an exponentially decreasing proportional series. It is easy to calculate that the average number of total layers is log 1/pn, while the average number of nodes in the highest layer is 1 × p.

To sum up, by rough calculation, the average search length is approximately equal to:

C (log 1/pn-1) = (log 1/pn-1) / p

That is, the average time complexity is O (log n).

Of course, the time complexity analysis here is still relatively rough. For example, when backtracking to the left and up along the search path, you may first reach the left head node, and then go all the way up along the head node, or you may reach the highest node first, and then go all the way to the left along the highest linked list. However, these details do not affect the final result of the average time complexity. In addition, the time complexity given here is only a probability average, but in fact it is possible to calculate a fine probability distribution. For more information, please see William Pugh's paper "Skip Lists: A Probabilistic Alternative to Balanced Trees".

Comparison of skiplist with balance tree and hash table the elements of skiplist and various balance trees (such as AVL, red-black tree, etc.) are arranged in order, while the hash table is not. Therefore, you can only do a single key search on the hash table, not the range search. The so-called range lookup refers to finding all nodes whose size is between two specified values. When doing range lookups, balanced trees are more complex than skiplist operations. On the balanced tree, after we find the small value of the specified range, we need to continue to look for other nodes that do not exceed the large value in the order of traversing in the middle order. If the balanced tree is not modified, the mid-order traversal here is not easy to achieve. Range lookup on skiplist is very simple, as long as you find a small value and traverse the layer 1 linked list in several steps. The insertion and deletion of the balanced tree may lead to the adjustment of the subtree, which is logically complex, while the insertion and deletion of the skiplist only need to modify the pointers of the adjacent nodes, which is simple and fast. In terms of memory footprint, skiplist is more flexible than balanced trees. Generally speaking, each node of the balanced tree contains two pointers (pointing to the left and right subtrees respectively), while the average number of pointers per node of the skiplist is 1 / (1murp), depending on the size of the parameter p. If, as in the implementation in Redis, we take pendant 1Universe 4, then on average each node contains 1.33 pointers, which is more advantageous than the balanced tree. The time complexity of searching a single key,skiplist and a balanced tree is O (log n), which is about the same, while the hash table has a lower hash value conflict probability, the search time complexity is close to O (1), and the performance is higher. So most of the Map or dictionary structures we use are based on hash tables. In terms of the difficulty of implementing the algorithm, skiplist is much simpler than balanced tree. Skiplist implementation in Redis

In this section, we discuss the skiplist implementation in Redis.

In Redis, skiplist is used to implement a data structure that is exposed to the outside: sorted set. To be exact, the underlying sorted set uses not only skiplist, but also ziplist and dict. The relationship between these data structures will be discussed in the next chapter. Now, let's take a moment to take a look at the key commands of sorted set. These commands have an important impact on the implementation of skiplist in Redis.

Examples of sorted set commands

Sorted set is an ordered collection of data, especially suitable for application scenarios such as rankings.

Now let's look at an example of using sorted set to store the grade table of algebra (algebra). The original data are as follows:

Alice 87.5Bob 89.0Charles 65.5David 78.0Emily 93.5Fred 87.5

This data gives the name and score of each student. Let's store this data in sorted set:

For the above commands, the points we need to pay attention to include:

The previous six zadd commands input the names and scores (score) of six students into a sorted set with a key value of algebra. Notice that Alice and Fred have the same score, both 87.5. The zrevrank command queries the ranking of Alice (the rev in the command indicates that it is sorted in reverse order, that is, from largest to smallest), and returns 3. At the top of the Alice list are Emily, Bob, and Fred, respectively, while the ranking (rank) counts from 0, so Alice ranks 3. Note that Alice and Fred actually have the same score, in which case sorted set will arrange the elements with the same score in dictionary order. In reverse order, Fred comes before Alice. The zscore command queries the corresponding score for Charles. The zrevrange command queried four students with a ranking of 03from big to small. The zrevrangebyscore command queries all students with scores between 80.0 and 90.0, and sorts them according to their scores.

To sum up, each element in sorted set has three main attributes:

The data itself (we saved the name as data in the previous example). Each data corresponds to a score (score). According to the size of the score and the dictionary order of the data itself, each data produces a ranking (rank). It can be in positive or reverse order. The particularity of skiplist implementation in Redis

Let's take a brief analysis of the previous query commands:

Zrevrank queries its corresponding rankings by data, which is not supported in the skiplist described earlier. Zscore queries its corresponding score by data, which is not supported by skiplist. According to a ranking range, zrevrange queries the data ranked within that range. This is also not supported in the skiplist described earlier. Zrevrangebyscore queries the data set according to the score interval, which is a typical range search supported by skiplist (score is equivalent to key).

In fact, the implementation of sorted set in Redis looks like this:

When there is little data, sorted set is implemented by a ziplist. When there is a lot of data, sorted set is implemented by a dict + a skiplist. To put it simply, dict is used to query the correspondence of data to scores, while skiplist is used to query data based on scores (possibly range lookups).

The composition of sorted set here will be discussed in more detail in the next chapter. Now let's focus on the relationship between sorted set and skiplist:

The query for zscore is not provided by skiplist, but by that dict. In order to support ranking (rank), skiplist has been extended in Redis so that data can be quickly found according to rankings, or easily obtained after finding data based on scores. Moreover, according to the search of the ranking, the time complexity is O (log n). The query of zrevrange is based on ranking data and is provided by the expanded skiplist. Zrevrank is first in the dict from the data to find the score, and then take the score to the skiplist to find, after the search also got the ranking.

The above query process also implies the time complexity of each operation:

Zscore only needs to query one dict, so the time complexity is O (1) zrevrank, zrevrange, zrevrangebyscore. Because of querying skiplist, the time complexity of zrevrank is O (log n), while that of zrevrange and zrevrangebyscore is O (log (n) + M), where M is the number of elements returned by the current query.

To sum up, the skiplist in Redis is different from the classic skiplist introduced earlier, as follows:

The score (score) allows repetition, that is, the key of skiplist allows repetition. This is not allowed in the classic skiplist introduced at the beginning. When comparing, compare not only the score (equivalent to the key of skiplist), but also the data itself. In the skiplist implementation of Redis, the contents of the data itself uniquely identify the data, not by the key. In addition, when multiple elements have the same score, they need to be sorted in the dictionary according to the content of the data. The layer 1 linked list is not an one-way linked list, but a two-way linked list. This is to facilitate the acquisition of elements in a range in reverse order. The ranking of each element (rank) can be easily calculated in skiplist. Data structure definition of skiplist # define ZSKIPLIST_MAXLEVEL 32#define ZSKIPLIST_P 0.25typedef struct zskiplistNode {robj * obj; double score; struct zskiplistNode * backward; struct zskiplistLevel {struct zskiplistNode * forward; unsigned int span;} level [];} zskiplistNode;typedef struct zskiplist {struct zskiplistNode * header, * tail; unsigned long length; int level;} zskiplist

This code is from server.h, so let's take a brief analysis:

At the beginning, we define two constants, ZSKIPLIST_MAXLEVEL and ZSKIPLIST_P, which correspond to the two parameters of skiplist we mentioned earlier: one is MaxLevel and the other is p. ZskiplistNode defines the node structure of skiplist. The obj field holds the node data, and its type is a string robj. Originally, a string robj may store a long rather than a sds, but the zadd command decodes the data before inserting it into the skiplist, so the obj field here must be a sds. For more information about robj, see the third article in the series, "detailed explanation of Redis's internal data structures (3)-- robj." The purpose of this should be to facilitate lexicographic comparison of the data when looking up, and it is less likely that the data part of the skiplist is numeric. The score field is the score corresponding to the data. The backward field is a pointer (forward pointer) to the previous node of the linked list. The node has only 1 forward pointer, so only the layer 1 linked list is a two-way linked list. Level [] stores a pointer (backward pointer) to a node behind each layer's linked list. Each layer corresponds to a backward pointer, which is represented by the forward field. In addition, each backward pointer corresponds to a span value, which indicates how many nodes the current pointer spans. Span is used to calculate element rankings (rank), which is an extension of skiplist by Redis that we mentioned earlier. It is important to note that level [] is a flexible array (flexible array member), so the memory it occupies is not in the zskiplistNode structure, but is allocated separately when nodes need to be inserted. It is also because of this that the number of pointers per node in skiplist is not fixed, and the conclusion we analyzed earlier-that the average number of pointers per node in skiplist is 1 / (1MIP)-makes sense. Zskiplist defines the true skiplist structure, which consists of a header pointer header and a tail pointer tail. The linked list length length, that is, the total number of nodes contained in the linked list. Note that the newly created skiplist contains an empty header pointer, which is not included in the length count. Level represents the total number of layers of skiplist, that is, the maximum number of layers of all nodes.

The following figure shows the possible structure of a skiplist in Redis, using the algebra score sheet inserted earlier as an example:

Note: the number in parentheses above the forward pointer in the figure indicates the corresponding span value. That is, how many nodes the current pointer spans. This count does not include the start node of the pointer, but includes the end node of the pointer.

Suppose we look for the elements of score=89.0 (that is, the performance data of Bob) in this skiplist, and in the search path, we will cross-domain graph red pointers, and the span values on these pointers add up to get the ranking of Bob (2-2-1)-1-4 (minus 1 because the rank starts with 0). It should be noted that the ranking is calculated from small to large, but if you want to calculate the ranking from large to small, you only need to use the skiplist length minus the span cumulative value on the lookup path, that is, 6-(2-2-1) = 1.

It can be seen that in the process of finding skiplist, we can easily calculate the ranking by accumulating the sp value. On the contrary, if you specify a ranking to find data (like zrange and zrevrange), you can also accumulate span and keep the cumulative value no more than the specified ranking at all times. In this way, you can get an O (log n) search path.

Sorted set in Redis

As we mentioned earlier, sorted set in Redis is built on skiplist, dict, and ziplist:

When there is little data, sorted set is implemented by a ziplist. When there is a lot of data, sorted set is implemented by a data structure called zset, which zset contains a dict + a skiplist. Dict is used to query the correspondence between data and scores (score), while skiplist is used to query data based on scores (possibly range lookups).

Here let's first discuss the former case-- sorted set based on ziplist implementation. In the previous article on ziplist in this series, we introduced that ziplist is a large chunk of contiguous memory made up of many data items. Because each element of sorted set consists of data and score, when you insert a (data, score) pair using the zadd command, the underlying layer inserts two data items on the corresponding ziplist: the data comes first and the score comes last.

The main advantage of ziplist is that it saves memory, but the lookup operations above can only be found sequentially (either in positive or reverse order). Therefore, each query operation of sorted set is to look up front-to-back (or back-to-forward) on ziplist step by step, with two data items in each step and a cross-domain (data, score) pair.

As the data is inserted, the underlying ziplist of sorted set may be transformed into an implementation of zset (see t_zset.c 's zsetConvert for details of the conversion process). So how much is inserted before it will turn?

Remember the two Redis configurations mentioned at the beginning of this article?

Zset-max-ziplist-entries 128zset-max-ziplist-value 64

This configuration means that ziplist will be converted to zset when one of the following two conditions is met (for specific trigger conditions, see the zaddGenericCommand related code in t_zset.c):

When the number of elements in sorted set, that is, the number of (data, score) pairs exceeds 128, that is, when the ziplist data item exceeds 256, When the length of any data inserted in the sorted set exceeds 64.

Finally, the code definition for the zset structure is as follows:

Why does typedef struct zset {dict * dict; zskiplist * zsl;} zset;Redis use skiplist instead of a balanced tree?

In the previous comparison of skiplist with balanced tree and hash table, it is not difficult to see why skiplist is used in Redis instead of balanced tree. Now let's see what the author of Redis @ antirez says about this problem:

There are a few reasons:

1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.

2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.

3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O (log (N)). It required little changes to the code.

The original source of this passage is:

Https://news.ycombinator.com/item?id=1171423

Here, we have also covered the reasons from three aspects: memory footprint, support for range lookup, and ease of implementation.

In the next article in the series, we will introduce intset and its relationship to Redis's exposed data type set.

(end)

The original article, reproduced, please indicate the source, and include the following QR code! Or refuse to reprint!

Link to this article: http://zhangtielei.com/posts/blog-redis-skiplist.html

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.