Redis Skiplist Internals: Nodes, Levels, and Ordering

Redis implements its skiplist through two structures defined in server.h: zskiplistNode represents an individual node, while zskiplist holds list-level metadata such as the node count and pointers to the head and tail nodes.

The zskiplist structure contains:

• header: points to the skiplist head node.
• tail: points to the skiplist tail node.
• level: records the highest level among nodes in the skiplist, excluding the head node.
• length: records the number of nodes in the skiplist, excluding the head node.

A zskiplistNode contains:

• Levels: nodes label their levels as L1, L2, L3, and so on. Each level has two properties: a forward pointer and a span. The forward pointer accesses nodes toward the tail, and the span records the distance between the current node and the node reached by the forward pointer. When traversing from head to tail, the program follows forward pointers along the levels.
• Backward pointer: marked BW in diagrams, it points to the previous node and is used when traversing from tail to head.
• Score: the 1.0, 2.0, and 3.0 values stored by nodes. Nodes are ordered from smallest score to largest score.
• Member object: the o1, o2, and o3 values stored by nodes.

The head node is built like any other node. It also has a backward pointer, score, and member object, but those fields are not used; diagrams often omit them and show only its levels.

The skiplist node

The node implementation is defined by server.h/zskiplistNode:

typedef struct zskiplistNode {
    // Member object, using Redis's internal string type
    sds ele;
    // Score
    double score;
    // Backward pointer
    struct zskiplistNode *backward;
    // Levels
    struct zskiplistLevel {
        // Forward pointer
        struct zskiplistNode *forward;
        // Span
        unsigned long span;
    } level[];
} zskiplistNode;

Levels

A node's level array can contain multiple elements, and each element includes a pointer to another node. These levels let the program skip ahead, and generally more levels mean faster access to other nodes.

When a new skiplist node is created, the program uses a power law to generate a random value between 1 and 32 as the size of the level array. That size becomes the node's height. Because C array indexes start at 0, a node's first level is level[0], its second level is level[1], and so on.

Forward pointers

Each level has a forward pointer toward the tail, stored in level[i].forward, and it is used to move from head to tail.

A traversal can work like this: start at the head, move through a high-level forward pointer to the second node, follow a lower-level pointer to the third node, continue through another level to the fourth node, and eventually reach NULL, which marks the end of the skiplist.

Spans

The span stored in level[i].span records the distance between two nodes. A larger span means the nodes are farther apart. Every forward pointer that points to NULL has a span of 0 because it does not connect to another node.

At first glance, spans might seem related to traversal, but traversal only needs forward pointers. Spans are used to calculate rank: while searching for a node, add up the spans of the levels that are crossed, and the total is the target node's rank in the skiplist.

For example, searching for the node with score 3.0 and member object o3 may cross only one level with a span of 3, so the target node has rank 3.

Searching for the node with score 2.0 and member object o2 may cross two nodes with a span of 1 each, giving the target node rank 2.

Backward pointers

The backward pointer is used to move from tail toward head. Unlike a forward pointer, which can skip several nodes, each node has only one backward pointer, so it can move back only one node at a time.

To traverse from tail to head, the program starts at the tail node through the skiplist's tail pointer, then follows backward pointers through the previous nodes. When it reaches a backward pointer that is NULL, the traversal ends.

Scores and member objects

A node's score is a double, and all nodes in the skiplist are sorted from smallest score to largest score.

A node's member object is a pointer to a string object that holds an SDS value. Within one skiplist, member objects must be unique, but multiple nodes may have the same score. Nodes with equal scores are ordered by the lexicographic order of their member objects: the smaller member object comes first, closer to the head, and the larger member object comes later, closer to the tail.

For example, three nodes may all store the score 10086.0, but the node with member object o1 comes before o2 and o3, while o2 comes before o3. This reflects the ordering o1 <= o2 <= o3.

The zskiplist wrapper

Multiple skiplist nodes can form a skiplist by themselves, but wrapping them in a zskiplist structure makes whole-list operations easier. It allows quick access to the head and tail nodes and quick retrieval of information such as the node count.

The zskiplist structure is defined as:

typedef struct zskiplist {
    // Head and tail nodes
    struct zskiplistNode *header, *tail;
    // Number of nodes in the skiplist
    unsigned long length;
    // Maximum level among nodes in the skiplist
    int level;
} zskiplist;

The header and tail pointers point to the head and tail nodes, so the program can locate either end in O(1) time. The length field stores the node count and allows the skiplist length to be returned in O(1) time. The level field provides the highest level among nodes in O(1) time, not counting the head node's level.