“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

As an ordered set, Zset implements fast data lookup based on the internal hop table or index. It solves the pain point of low efficiency of linked list query

Review past

Redis redis prequel 】 【 rapid mapping dictionary + hash broken | progressive rehash of the single thread does not affect the background work

Redis eliminated + redis of being wild 】 【 expired two-way guarantee high availability | single-threaded how to achieve fast response

[redis prequel] redis list five top values basic data | how to growth from in to out further study

Handwritten redis prequel 】 【 a LRU strategy | catch the tail of the time

Redis based on distributed lock

preface

  • Immediately after that we learnedRedisHash structure in. In it we sort through the important internal structure of the dictionary and we analyze the hash structure and the process of rehash to explain whyredisSingle threading is still just as fast
  • In this chapter, we will push the perspective down and continue to learnRedisOne of the five heavenly KingszsetData structure;zsetIs an ordered non-repeating collection whose internal elements are unique and ordered. Its sorting criteria are sorted according to its internal Score dimension.

Zset structure

The basic unit

  • The zset structure is very simple. One is the dictionary structure we studied earlier (simple to think of as Hash structure), and the other is the skip list structure. The last chapter of the dictionary explained in detail its internal structure and how to perform data expansion and other operations! The rest of the course, which is in line with the theme of today’s study, is the familiar and the unfamiliarzskiplist.
  • We can also see from the above structure diagram of zSET that Zskiplist is actually a linked list.

zskiplist

  • Looking at the source code, it is easy to see that the internal structure is an abstract description of the list in zset. Zskiplist will first record the head node and tail node of this linked list to facilitate traversal operation through Zskiplist. The remaining length is, of course, a count of the number of lists inside. More abstract is the understanding of this level. Above we also see that the Zskiplist list will actually have the concept of hierarchy. The author here through different colors to express the concept of different levels.
  • The author here draws an internal data graph for the Zskiplist inside the skiplist described above

  • In the structural description and data description of Zskiplist, I separated them and understood them, thinking that it is easier to understand the structural relationship. Here is the entire diagram

  • Careful readers should be able to see that I missed an important part of the listzskiplistNodeThis important node explains. It’s actually the node in the list on our right. In other words, each point in the list is a zskiplistNode.

level

  • Skip list’s important feature types and tree structure can avoid the pain of traversal one by one. So how did he achieve this kind of leapfrog access? There’s another reason why Redis designed it the way he did. First, let’s answer the question of why. Inserting, deleting, and so on in a linked list can be done very quickly by simply changing the pointer. But for the query, it has to traverse the entire list to do it. In view of this disadvantage of the linked list, Redis designed the data structure of the jump table.
  • Here is how to implement a simple comb. We can also see that there is a level attribute in the above zskiplistNode object structure. Redis uses this property to implement the feature of jumping. This level is randomly generated for each node. It represents the scope of the layer in which the node is located.
  • Why is this level random? There is an internal idempotence algorithm involved. This algorithm ensures that larger numbers generate smaller profiles. The maximum level in Redis was 32.
  • For example, level randomly generates 5. Indicates that the current node is in levels level1 to Level5. The three nodes shown in the diagram above generate level values level3, Level2, and Level7. Note that in real storage level indexes start at 0.

forward

  • Two other properties in level are the forward pointer and the span length. A forward pointer is literally a pointer that advances toward the back end of the list. The span is the distance between the current node and the node at the forward pointer. This distance is referring to the distance at the bottom.

Double linked list

  • In Zskiplist each layer is a unidirectional linked list. Point to the end of our table through the forWAR pointer in level. So why do I say it’s a double linked list? The double-linked list here is not exactly a double-linked list. But we can use these levels of single linked lists to achieve our two-way free routing.

Random layer

  • We have explained the definition of level above. So why is it mentioned again? Because we briefly mentioned idempotent algorithms. Here we’ll explain in detail what idempotent is.

  • Firstly, according to the definition of level, we can summarize the following features about level.

  • If a node is at level[I], it must be at a level below level[I]

  • ② The higher the element, the larger the span, the span is uncertain. Depends on the random algorithm used to generate the nodes

  • ③, each layer is a linked list

  • This is the source part of Redis. It’s not that hard to understand this random level algorithm. The author will streamline the above code here

  • It’s a retry mechanism. Where p and maxLevel are both fixed values in the code. With this algorithm mechanism, we can ensure that the level will not be particularly high when the amount of data is small.
  • In other words, our level will not be too abrupt. If it is purely random, it is possible to have some nodes with very low level and some with very high level. This will result in an unnecessary waste of resources.

To find the

  • All right, so now that we’re here we’ve looked at the basic structure of the Zset. So just a quick review inside is a combination of dictionary and skip list. Let’s take a look at some of the common zset operations for these two data structures.
  • The first is our search. So much for the internal structure. We need to do it in practice.

Mark positioning

  • The above commands are basically located through the score and then do their own business processing.

  • The diagram illustrates our process. The first is to look at the top because the top is the thinnest. When higher-ups don’t see it, we push it down the hierarchy. At this point we come to node 1 in level. We then move forward through the forWAR pointer. Finally locate node 5.
  • One more caveat: In the node, the obj pointer points to the actual content, and the Score stores the branch; The author here demonstrates why it is convenient to mark scores directly in nodes. Other parts are not marked!!

Members of the positioning

  • When sorting out the relevant logic, the author also made the conclusion after browsing through Baidu, videos, books and other ways. Forgive my ability to read the source code directly! But in the process of looking up information. There is little explanation of how member location is performed. In addition to the commands related to the score, there are many member based locations in the Zset.

  • The above command is partially based on member location. The actual nodes in the ZSET structure are sorted based on score. There’s no order in OBj. We can’t do the layer-by-layer positioning of elements as we mentioned above by score! This brings us to our other important role: the hash.

  • Above is our description of the dictionary from the previous chapter. Through the member positioning when we are more than a step from the dictionary to locate the score, and then repeat the above steps to locate!

  • Knowing the structure naturally makes it easy to understand the operations involved. Standing on the shoulders of giants, we don’t have to reinvent the wheel. But we need to know how our predecessors built the wheel! Draft do not forget to dig the well!

Internal understanding of commands

  • If you understand the structure, you can quickly grasp the command. Otherwise, even if you memorize the command, you will forget it after a while. But by keeping the structure in mind we will know that there are commands that will implement our requirements and then we will be able to follow the manual with ease. Let’s take a look at how these four commands work.

zcard

  • Pass the length attribute in zskiplist

zcount

  • The boundary is located by the score, and then the bottom list is traversed to get the statistics

zlecount

  • Using the dictionary to locate the score, perform the Zcount operation

zrank

  • Returns the index of the specified member in the ordered collection. The member is located first, and the ranking can be determined by span

conclusion

  • A Zset is an ordered linked list. In order to solve the low query of linked list, Redis built the data structure of jump list. Greatly improved efficiency!
  • The data structure of the Zset we actually have a lot of cases that can be implemented through it; Latency queues, internal LRU, hotspot data, and so on

Like, follow don’t get lost oh