Redis Skip List principle implementation

Introduction: Why does Redis choose to jump table?

In the implementation of ordered sets (ZSET), Redis developers face a key choice:How to find a balance between high-performance read and write and code simplicity? Although traditional balanced trees (such as red and black trees) can ensure O(logN) time complexity, they are complex and difficult to support range query.Skip ListIt has become the core data structure of Redis ZSET with its performance comparable to balanced trees, minimalist implementation (about 200 lines of code) and natural support for range query. This article will conduct in-depth analysis of the implementation details of the skip table and the engineering optimization of Redis.

1. Core idea of ​​jumping tables: Probable multi-layer index

1.1 Evolution from linked list to jump table

• Ordinary link list: Insert/delete O(1), but the query requires O(N)
• Jump table innovation: Achieve logarithmic query efficiency by randomizing multi-layer indexes

1.2 Visualization of table jump structure

Level 3: Head -> 37 --------------------------> 99 -> NULL  
Level 2: Head -> 37 -------> 71 -------> 99 -> NULL  
Level 1: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  
Level 0: Head -> 37 -> 55 -> 71 -> 85 -> 99 -> NULL  

Key Features：

Randomly generates layers per node (Redis maximum number of layers 64)

High-level indexes span more nodes to speed up search

The underlying linked list stores complete data

2. Redis table jump to achieve deep anatomy

2.1 Data structure definition ()

// Jump table nodetypedef struct zskiplistNode {
    sds ele;                          // Member object (SDS string)    double score;                     // Sort scores    struct zskiplistNode *backward;   // Backward pointer (bidirectional linked list)    struct zskiplistLevel {
        struct zskiplistNode *forward; // Forward pointer        unsigned long span;            // Span (for ranking calculation)    } level[];                        // Flexible array, hierarchical random generation} zskiplistNode;

// Table jump structuretypedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;             // Total number of nodes    int level;                        // Current maximum number of layers} zskiplist;

Design Highlights：

• span field: Record the span of a node at a certain layer, supporting O(1) time complexity calculation element ranking (ZRANK）
• backward pointer: Constituting a two-way linked list, supporting reverse traversal
• Flexible array (level[]): Compact memory, avoid redundant pointers

2.2 Source code analysis of key operations

2.2.1 Node layer generation algorithm

// Excerpt from source codeint zslRandomLevel(void) {
    int level = 1;
    // 0xFFFF corresponds to 1/4 probability improvement level (based on bit operation optimization)    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Principles of mathematics：

• usePower Law, high-level nodes are reduced exponentially
• Each node has a 50% chance of entering L1, 25% entering L2, 12.5% ​​entering L3...
• Redis practical use1/4 probability factor(Optimize memory and performance balance)

2.2.2 Insert node process (zslInsert)

• Search path record: Starting from the highest level, record the front-drive nodes and spans of each layer
• Generate random layers: Call zslRandomLevel
• Create a new node: Assign hierarchies and connect front and back pointers
• Update span: Adjust the span value of adjacent nodes
• Maintain back pointer: Set the backward pointer for the new node

2.2.3 Scope Query (ZRANGEBYSCORE)

• Quickly locate the starting point from a high-level index
• Use the underlying linked list to traverse the scope
• Complexity:O(logN + M) (M is the number of returned elements)

3. Performance analysis and optimization strategies

3.1 Time complexity comparison

Note: The worst case of jumping table (all nodes have the same height) is extremely low (for example, the probability of 100 million nodes is 1/(2^50))

3.2 Memory usage analysis

• Theoretical space complexity：O(NlogN)
• Redis optimization practices: Through the 1/4 probability factor, the actual space occupies about O(1.33N) (the actual measured memory of 1 million nodes is about 64MB)

3.3 Tuning parameters

• ZSKIPLIST_MAXLEVEL: Control the maximum number of layers (default 64, memory and performance balance can be adjusted)
• ZSKIPLIST_P: Adjust the probability of layer generation (default 0.25)

4. Application scenarios of table jump in Redis

4.1 Ordered Sets (ZSET)

Number of elements > 128orElement length > 64 bytesWhen ZSET uses skip table internally

Support operation：

• ZADD/ZREM: Insert and delete
• ZRANK/ZSCORE: Ranking query
• ZRANGE:Scope query

4.2 Cluster metadata management

Used to maintain the mapping relationship between slots and nodes

5. Jump table vs balanced tree: selection of engineering angle

Reviews by Redis Author Antirez: "The table jump is not as elegant as the balance tree in theory, but it is simpler and faster in actual engineering, especially suitable for scenarios where range query is required."

Summarize:

The exquisite thing about jumping tables isExchange probability for structure, avoid complex rebalancing operations by randomizing hierarchical distribution. This design philosophy of "for time" + "for probability to simplicity" is of great reference significance in the development of distributed systems. Understanding table skipping not only helps to master Redis source code, but also inspires us to think about how to find a balance between high performance and maintainability.

This is the end of this article about the implementation of the Redis Skip List principle. For more related content on Redis Skip List, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!