In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-21 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >
Share
Shulou(Shulou.com)06/02 Report--
This article mainly explains the "Redis jump table structure implementation method", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "Redis jump table structure implementation method"!
I. Preface
Redis provides five data types: String (string), Hash (hash), List (list), Set (set), and Zset (ordered set). Understanding the characteristics of each data type is very important for the development and operation of redis.
Original text analysis: http://www.yund.tech/zdetail.html?type=1&id=e4802958843feef901c7d7b7932f8be0"
Note: according to the order of analysis, this section should talk about ordered collection objects, but considering that the jump table structure is used in the underlying implementation of ordered collection objects to avoid being abrupt when analyzing ordered collections, this section first looks at the specific implementation of the jump table structure in redis.
Second, structural analysis
The jump table of Redis is defined by two structures, redis.h/zskiplistNode and redis.h/zskiplist, in which zskiplistNode structure is used to represent jump table nodes, while zskiplist structure is used to store relevant information about jump table nodes, such as the number of nodes and pointers to header nodes and footer nodes.
Figure 5-1 of shows an example of a jump. On the far left of the picture is the zskiplist structure, which contains the following properties:
Header: points to the header node of the jump table. Tail: points to the footer node of the jump table. Level: record the number of layers of the node with the largest number of layers in the current jump table (the number of layers of the header node is not counted). Length: records the length of the jump table, that is, the number of nodes currently contained in the jump table (header nodes are not counted).
To the right of the zskiplist structure are four zskiplistNode structures that contain the following attributes:
Layer (level): each layer of the node is marked with the words L1, L2, L3, etc., L1 for the first layer, L2 for the second layer, and so on. Each layer has two properties: forward pointer and span. The forward pointer is used to access other nodes at the end of the table, while the span records the distance between the node the forward pointer points to and the current node. In the picture above, the arrow with a number on the line represents the > forward pointer, and that number is the span. As the program traverses from the header to the footer, the access occurs along the forward pointer of the layer.
Backward pointer: a backward pointer in a node marked with the word BW, which points to the previous node at the current node. The back pointer is used when the program traverses from the footer to the header.
Scores (score): 1.0,2.0 and 3.0 in each node are the scores saved by the node. In the jump table, the nodes are arranged from small to large according to their saved scores.
Member objects (obj): o1, o2, and o3 in each node are the member objects saved by the node. Note that the header node is constructed the same as other nodes: the header node also has fallback pointers, scores, and member objects, but these attributes of the header node are not used, so these parts are omitted in the figure. Only the layers of the header node are shown.
1. Jump table node structure
The jump table node implementation is defined by the redis.h/zskiplistNode structure:
Typedef struct zskiplistNode {/ / backward pointer struct zskiplistNode * backward; / / score double score; / / member object robj * obj; / / layer struct zskiplistLevel {/ / forward pointer struct zskiplistNode * forward; / / Span unsigned int span;} level [];} definition of zskiplistNode; layer
The level array of jump table nodes can contain multiple elements, each containing a pointer to other nodes. Programs can use these layers to speed up access to other nodes. In general, the more layers, the faster access to other nodes.
Each time a new jump table node is created, the program randomly generates a value between 1 and 32 as the size of the level array according to the power law (power law, the larger the number, the smaller the probability of occurrence). This size is the "height" of the layer.
Figure 5-2 shows three nodes with a height of layer 1, layer 3, and layer 5, respectively. Because the array index of the C language always starts at 0, the first layer of the node is level [0], the second layer is level [1], and so on.
Forward pointer
Each layer has a forward pointer to the footer (level [I]. Forward attribute) that accesses the node from the header to the footer.
Figure 5-3 shows the path of the program traversing all the nodes in the jump table from header to footer with dotted lines:
The iterator first accesses the first node (header) of the jump table and then moves from the forward pointer of the fourth layer to the second node in the table. At the second node, the program moves along the forward pointer of the second layer to the third node in the table. At the third node, the program also moves along the forward pointer of the second layer to the fourth node in the table. When the program moves along the forward pointer of the fourth node again, it encounters a NULL, and the program knows that it has reached the end of the jump table, so it ends the traversal.
Span of layer
The span of the layer (level [I] .span attribute) is used to record the distance between two nodes:
The greater the span between the two nodes, the farther apart they will be. All forward pointers to NULL have a span of 0 because they are not connected to any node. At first glance, it is easy to think that the span is related to the traversal operation, but in fact this is not the case. The traversal operation can only be done with a forward pointer, and the span is actually used to calculate the rank: in the process of finding a node, add up the spans of all the layers visited along the way, and the result is the ranking of the target node in the jump table.
For example, figure 5-4 marks the layer experienced along the way when looking for a node with a score of 3.0 and a member object of o3 in the jump table: the search process goes through only one layer, and the span of the layer is 3, so the target node ranks 3 in the jump table.
For example, figure 5-5 marks the layer along the way when looking for a node with a score of 2.0 and a member object of O2 in the jump table: in the process of finding the node, the program passes through two nodes with a span of 1, so it can be calculated that the target node ranks 2 in the jump table.
Backward pointer
The backward pointer of a node is used to access the node from the end of the table to the header: unlike the forward pointer, which can skip more than one node at a time, each node has only one backward pointer, so it can only go back to the previous node at a time. Figure 5-6 shows if you traverse all the nodes in the jump table from the footer to the header: the program first accesses the footer node through the tail pointer of the jump table, then accesses the penultimate node through the backward pointer, then accesses the penultimate node along the backward pointer, and then encounters a backward pointer to NULL, so the access ends.
Scores and members
The score (score attribute) of a node is a floating-point number of type double, and all nodes in the jump table are sorted by score from smallest to largest.
The node's member object (the obj attribute) is a pointer to a string object, which holds a SDS (simple dynamic string, analyzed previously) value.
In the same jump table, the member objects saved by each node must be unique, but the scores saved by multiple nodes can be the same: nodes with the same scores are sorted according to the size of the member objects in lexicographical order. the smaller nodes of the member objects are ranked first (near the header), while the larger nodes of the member objects are arranged behind (near the end of the table).
For example, in the jump table shown in figure 5-7, the three jump table nodes all keep the same score of 10086.0, but the nodes that save member objects o1 are ranked before the nodes that save member objects O2 and o3, and the nodes that save member objects o2 are ranked before the nodes that save member objects o3, so it can be seen that the ranking of o1, o2 and o3 member objects in the dictionary is o1.
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.
Views: 257
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.