Redis ten Redis skip list structure implementation

One, foreword

Redis provides five data types: String, Hash, List, Set, and Zset. Understanding the characteristics of each data type is important for the development and operation of Redis.

The original resolution

Note: In accordance with the order of analysis, this section should say ordered collection object, but considering that the underlying implementation of ordered collection object uses skip list structure, so as to avoid the unexpected in the analysis of ordered collection, so this section first looks at the specific implementation of skip list structure in Redis.

Second, structure analysis

H /zskiplistNode and Redis. H /zskiplist. The zskiplistNode structure is used to represent the skip table node. The Zskiplist structure is used to store information about skip table nodes, such as the number of nodes, Pointers to the top and bottom of the table, and so on.

Figure 5-1 shows an example of a jump representation. The zskiplist structure at the far left of the image contains the following properties:

Header: Points to the table header node of the skip table. Tail: Refers to the end-of-table node of a skip table. Level: Records the level of the node with the largest level in the current skip table (the level of the top node is not counted). Length: Records the length of the skip table, that is, the number of nodes currently contained in the skip table (the head node is not counted).

To the right of the Zskiplist structure are the four zskiplistNode structures that contain the following properties:

Level: Each layer of a node is marked with words such as L1, L2, and L3. L1 represents the first layer, L2 represents the second layer, and so on. Each layer has two properties: a forward pointer and a 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 to which the forward pointer points and the current node. In the image above, the arrow with the number on the line represents the > forward pointer, and that number is the span. When the program traverses from the top of the table to the end of the table, access follows the forward pointer of the layer.

Backward Pointer (BACKWARD) : A node marks the backward pointer of the node with the word BW, which points to the previous node of the current node. The back pointer is used when the program traverses from the end of the table to the beginning of the table.

Score: 1.0, 2.0 and 3.0 in each node are the points saved by the node. In a skip list, the nodes are arranged in ascending order of the points they hold.

Member objects (OBJ) : O1, O2, and O3 in each node are the member objects held by the node.

Note that a header node is constructed the same as any other node: it also has a back pointer, a score, and a member object, but none of these attributes are used, so the figure omits these parts and shows only the layers of the header node.

1. Skip table node structure

The skiplist node implementation is defined by the redis. H /zskiplistNode structure:

typedef struct zskiplistNode {

    // Back up the pointer
    struct zskiplistNode *backward;

    / / score
    double score;

    // Member objects
    robj *obj;

    / / layer
    struct zskiplistLevel {

        // Forward pointer
        struct zskiplistNode *forward;

        / / span
        unsigned int span;

    } level[];

} zskiplistNode;
Copy the code

The definition of a layer

The level array of skip list nodes can contain multiple elements, each of which contains a pointer to another node. Programs can access other nodes faster through these layers. In general, the more layers, the faster the access to other nodes.

Each time a new skip list node is created, the program randomly generates a value between 1 and 32 as the size of the level array, which is the “height” of the layer, according to the power law (larger numbers are less likely to occur).

Figure 5-2 shows three nodes with the height of layer 1, layer 3 and layer 5 respectively. Because the array index of C language always starts from 0, the first layer of the node is level[0], and the second layer is Level [1], and so on.

Forward Pointers

Each layer has a forward pointer to the end of the table (the level[I].forward attribute) to access nodes from the head of the table to the end of the table.

Figure 5-3 shows the path of the program traversing all the nodes in the skip list from the head to the tail with dotted lines:

The iterator first accesses the first node of the skip list (the table header) and then moves from the forward pointer at the fourth level to the second node in the table. At the second node, the program moves to the third node in the table following the forward pointer at the second layer. At the third node, the program also moves to the fourth node in the table following the forward pointer of the second layer. When the program moves along the fourth node’s forward pointer again, it hits a NULL, and the program knows that it has reached the end of the skip list, so it finishes the walk.

The span of layer

The span of the layer (level[I].span property) is used to record the distance between two nodes:

The greater the span between two nodes, the farther apart they are. 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 and traversal operations, but in fact is not the case, traversal operations using only forward Pointers can be finished, the span is actually used to calculate the position (rank) : in the process of looking for a node, will visit along the span of all layers accumulated, the result is the target node position in the jump table.

For example, dotted lines are used in Figure 5-4 to mark the layers that the node with a score of 3.0 and a member object of O3 goes through in the skip list: The search process only goes through one layer, and the span of layers is 3, so the target node ranks 3 in the skip list.

For example, in Figure 5-5, dashed lines are used to mark the layers along the way when looking for a node with a score of 2.0 and a member object of O2 in the skip list: In the process of looking for a node, the program passes through two nodes of span 1, so it can be calculated that the rank of the target node in the skip list is 2.

The back pointer

A node’s backward pointer (a backward attribute) is used to access a node from the end of the table to the head: unlike a forward pointer, where you can skip multiple nodes at once, since there is only one backward pointer per node, you can only go back to the previous node at a time.

Points and members

The score attribute of a node is a floating-point number of type double, and all nodes in a skip list are sorted by score from smallest to largest.

The node’s member object (the obj property) is a pointer to a string object, which in turn holds an SDS (simple dynamic string, examined earlier) value.

In the same skip list, each node must hold unique member objects, but multiple nodes can hold the same points: Nodes with the same score are sorted by the size of their member objects in lexicographical order, with nodes with smaller member objects coming first (near the head of the table) and nodes with larger member objects coming second (near the bottom of the table).

For example, in the skip table shown in Figure 5-7, the three skip table nodes save the same score 10086.0, but the node saving member object O1 is ranked ahead of the node saving member object O2 and O3, and the node saving member object O2 is ranked ahead of the node saving member object O3. Therefore, the order of o1, O2, and O3 in the dictionary is o1 <= O2 <= O3.

2. Skip list structure

Although only multiple skip list nodes can form a skip list, as shown in Figure 5-8.

However, by using a Zskiplist structure to hold these nodes, the program can more easily process the entire skiplist, for example, quickly access the top and bottom nodes of the skiplist, or quickly obtain information such as the number of skiplist nodes (that is, the length of the skiplist), as shown in Figure 5-9.

The zskiplist structure is defined as follows:

typedef struct zskiplist {

    // Table header and table tail nodes
    struct zskiplistNode *header, *tail;

    // The number of nodes in the table
    unsigned long length;

    // The number of layers of the node with the largest middle level in the table
    int level;

} zskiplist;
Copy the code

As shown in figure:

The header and tail Pointers point to the head and tail nodes of the skip table, respectively. By using these two Pointers, the complexity of the program to locate the head and tail nodes is O(1).

By using the length attribute to record the number of nodes, the program can return the length of the skip list within O(1) complexity. The level attribute is used to obtain the number of layers of the node with the highest middle height in the skip table in O(1) complexity. Note that the height of the top node is not counted.

Skip list API operation

API operations for skip lists are listed in table form, along with the time complexity of the API.

function	role	Time complexity
zslCreate	Create a new skip list.	O(1)
zslFree	Releases the given skip list and all nodes contained in the table.	O(N), where N is the length of the skip list.
zslInsert	Adds a new node with the given member and score value to the skip list.	Average O(log N), worst O(N), N is the length of the skip list.
zslDelete	Deletes the node in the skip table that contains the given member and score.	Average O(log N), worst O(N), N is the length of the skip list.
zslGetRank	Returns the rank of the node in the skip list with the given member and score.	Average O(log N), worst O(N), N is the length of the skip list.
zslGetElementByRank	Returns the node of the skip list in the given rank.	Average O(log N), worst O(N), N is the length of the skip list.
zslIsInRange	Given a range of points, such as 0 to 15, 20 to 28, and so on, return 1 if the given range is included in the skip list, 0 otherwise.	This detection can be done with O(1) complexity with skip table head and tail nodes.
zslFirstInRange	Given a range of points, returns the first node in the skip list that matches this range.	Order log N on average, order N on worst. N is the length of the skip list.
zslLastInRange	Given a range of points, returns the last node in the skip list that matches this range.	Order log N on average, order N on worst. N is the length of the skip list.
zslDeleteRangeByScore	Given a range of points, delete all nodes in the skip list that fall within this range.	O(N), where N is the number of nodes to be deleted.
zslDeleteRangeByRank	Given a rank range, remove all nodes in the skip list that fall within this range.	O(N), where N is the number of nodes to be deleted.

4. Summary of key points

(1) Skip lists are one of the underlying implementations of ordered collections, and there are no other applications for them in Redis.

(2) The skiplist implementation of Redis is composed of zskiplist and zskiplistNode. Zskiplist is used to store skiplist information (such as head node, tail node and length), while zskiplistNode is used to represent skiplist nodes.

(3) The height of each skip list node is a random number between 1 and 32.

(4) In the same skip list, multiple nodes can contain the same score value, but the member object of each node must be unique.

(5) The nodes in the skip list are sorted according to the size of the score value. When the score value is the same, the nodes are sorted according to the size of the member objects.

over