redis Why use the data structure of jump table in ？

reids Of zset The realization of ordered sets , It needs to be convenient to find , Insert and delete , If you use a linked list , Find efficiency bit O(N), This is right redis Unacceptable , Use red black trees , The implementation is more troublesome , therefore redis A new structure is used , Jump watch .

The picture above is an ideal jump table

If you want to find now 21, You just need to start from the highest 2 Layer start , find 18, Jump to the first 1 layer , find 24, Jump to the first 0 layer , find 21, If you have a lot of data , This will achieve the effect of binary search .

Jump from the ideal table above , We can think about how to define a data structure of jump table , What should it have ？

If it is a jump table node ： such as 1 This node

Rough data structure of jump table

struct MySkipListLevel
{
    TMySkipListNode* m_pNext;   //  Next node 
    int m_nSpan;                //  The interval between the current layer and the next node 
};
struct TMySkipListNode
{
    void* m_pData;                //  data 
    MySkipListLevel m_L[];        //  Each layer 
    TMySkipListNode* m_pPrev;     //  Find the 24, Go back 
};

struct TMySkipList
{
    TMySkipListNode* m_pHeadNode;
    int m_nLeves;
};

reids Jump watch

typedef struct zskiplistNode {
    sds ele;
    double score;
	struct zskiplistNode* backward;     //  Back pointer ,  It can only point to the previous node at the bottom of the current node ,
    struct zskiplistLevel { 
        struct zskiplistNode *forward;  //  Point to the next node 
        unsigned long span;             // forward The number of elements between the pointed node and this node 
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

among , More tail pointers tail,length, See what's the use later , The difference in the data part is ignored .

redis Realized jump table

1、 Create a jump table node

zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

2、 Create a jump table and create a header node

  What is the default floor height of the new jump table ?

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

As you can see from the code , Let's say it's less than (ZSKIPLIST_P * 0xFFFF) The probability of is p

Greater than (ZSKIPLIST_P * 0xFFFF) The probability of is 1-p

Then the number of layers is n, Corresponding （p^(n-1)) * (1-p)

Its mathematical expectation is ：E=1/(1-p), When p by 0.25 when , Corresponding E = 1.33

Create a jump table , The head node does not store information , The layer number 64, No data .

zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

3、 Insert node

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;

    //  Visit from the top to the bottom 
    // rank[i] It's No i The passing of the previous node that can be inserted into the new node corresponding to the layer span（ That is, the interval from the head node to the previous node of the inserted node ）, The highest floor is 0
    // update[i]  It's No i The layer can be inserted into the previous node of the node 
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    //  It is assumed that the insertion will not be repeated , Create a new one with a height of level The node of , If it is higher than the height of the original meter , Need to update the corresponding rank and update
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    //  Create nodes , Update the forward node and backward node information of the node 
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    //  After inserting a new node , The corresponding higher layers need to be updated span
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    //  Set the value on the backward node 
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    //  Update the skip table length 
    zsl->length++;
    return x;
}

Insert the node of the jump table ,1、 The key is if it is lower than the number of layers , Then the data of the corresponding layer to be assigned higher than the current number of skip layers .2、 Maintain the front and back nodes of the inserted nodes .3、 Maintain other nodes of the entire hop table after inserting nodes , length , The influence of floor height .

4、 Delete node ：

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    //  The next node is the deleted node , Then add the spacing of the deleted nodes -1, Not the deleted node , direct -1
    //  It is assumed that , The deleted node must exist in the jump table 
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            update[i]->level[i].span -= 1;
        }
    }
    //  If the deleted node has a next node , Then assign the forward pointer of the next node to the previous node of the deleted node 
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward; //  Update tail node 
    }
    //  The height of the jump table is greater than 1, There is no next node at the top , Number of layers minus 1, Adjust the height 
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    //  Update length 
    zsl->length--;
}

5、 Delete jump table ：

void zslFree(zskiplist *zsl) {
    zskiplistNode *node = zsl->header->level[0].forward, *next;

    zfree(zsl->header);
    while(node) {
        next = node->level[0].forward;
        zslFreeNode(node);
        node = next;
    }
    zfree(zsl);
}

Traverse from the bottom , Then go back , Release all his nodes .

Jump watch redis Application ：

redis in ,zset There are two realizations , Jump tables and compressed lists

When the number of elements is less than 128 when , Use compressed lists

The number of elements is greater than 128 when , Use a skip watch

therefore zset When the conditions are met , Will be converted to a skip table implementation , And it won't turn back .