• What is Sorted Set
• Sorted Set command and implementation method
• Sorted Set data structure
• Skiplist
  • The structure definition of the hop table node
  • Definition of a hop table
  • Query the hop table node
  • The layer number of Settings
  • The hop table inserts the zslInsert node
  • The hop table deletes the zslDelete node
• Sorted Set basic operations
  • zsetAdd
    • Ziplist coding
    • Skiplist coding
    • ZsetAdd overall code
  • zsetDel
• Refer to the link
• Redis source code concise analysis series

What is Sorted Set

Sorted Set (Sorted Set) is an important data type in Redis. It is a Set type itself, and also supports the elements in the Set with weights and Sorted according to the weights.

• ZRANGEBYSCORE: Returns a range of elements by element weight
• ZSCORE: Returns the weight of an element

Sorted Set command and implementation method

Sorted Set data structure

• Structure definition:server.h
• Implementation:t_zset.c

The structure definition is zset, which contains dict hash table and ZSL hop table. Zset makes full use of:

• Efficient Single Point Query feature of Hash Table (ZSCORE)
• Efficient range query for skip tables (ZRANGEBYSCORE)

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;
Copy the code

Skiplist

A multi-level ordered linked list. Level0 to Level2; level0 to Level2; level0 to Level2; level0 to Level2

The structure definition of the hop table node

typedef struct zskiplistNode {
    // Sorted set elements
    sds ele;
    // Element weight
    double score;
    // back pointer (for easy lookup from the tail of the hop table)
    struct zskiplistNode *backward;
    // The level array of the node
    struct zskiplistLevel {
        // Forward pointer on each layer
        struct zskiplistNode *forward;
        // span, which records the node at a level *forward pointer and the node, spanning several nodes at Level0
        unsigned long span;
    } level[];
} zskiplistNode;
Copy the code

Definition of a hop table

typedef struct zskiplist {
    // Head and tail nodes
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
Copy the code

Query the hop table node

When querying a node, the hop table looks for the next node, starting at the top of the first node:

• Access the next node
  • The element weight of the current node < the weight to look for
  • The element weight of the current node = the weight to be found, and the node data < the data to be found
• Accesses the next-level pointer to the level array of the current node
  • Element weight of the current node > the weight to look for

// Get the header of the hop table
x = zsl->header;
// Start with the maximum number of layers
for (i = zsl->level- 1; i >= 0; i--) {
   ...
   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))) {... x = x->level[i].forward; }... }Copy the code

The layer number of Settings

Several methods:

1. The number of nodes in each layer is about half the number of nodes in the next layer.
   • Benefits: Similar to binary search, search complexity can be reduced to O(logN)
   • Disadvantages: Each time a node is inserted/deleted, the number of subsequent node layers must be adjusted, resulting in additional overhead
2. Randomly generate the number of layers for each node. Redis hops take this approach.

In Redis, the number of hops is determined by the zslRandomLevel function.

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

The probability of increasing each layer is 0.25, and the maximum number of layers is 32.

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
Copy the code

The hop table inserts the zslInsert node

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    inti, level; serverAssert(! isnan(score)); x = zsl->header;// Start with the highest level
    for (i = zsl->level- 1; i >= 0; i--) {
        // Position of each layer to be inserted
        rank[i] = i == (zsl->level- 1)?0 : rank[i+1];
        / / forward. Score < to be inserted into the score | | (forward) score < to insert the score && forward. Ele < ele)
        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))) {
            // Find the next node at the same level
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    // The number of random layers
    level = zslRandomLevel();

    // If the number of random layers of the node to be inserted is greater than the current number of layers of the hop table
    if (level > zsl->level) {
        // Increase the number of corresponding layers
        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 a node
    x = zslCreateNode(level, score, ele);
    // Set the level array for the new node
    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;
    }

    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}
Copy the code

The hop table deletes the zslDelete node

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    // Find the node to delete
    for (i = zsl->level- 1; i >= 0; i--) {
        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)))
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    x = x->level[0].forward;
    // Check whether score and ele of nodes meet the criteria
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        // Delete the node
        zslDeleteNode(zsl, x, update);
        if(! node)// Free memory
            zslFreeNode(x);
        else
            *node = x;
        return 1;
    }
    return 0; /* not found */
}
Copy the code

Sorted Set basic operations

In object. C, it can be seen that the dictCreate function will be called to create a hash table, and then the zslCreate function will be called to create a jump table.

robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;

    zs->dict = dictCreate(&zsetDictType,NULL);
    zs->zsl = zslCreate();
    o = createObject(OBJ_ZSET,zs);
    o->encoding = OBJ_ENCODING_SKIPLIST;
    return o;
}
Copy the code

Hash table and hop table data must be consistent. Let’s explore this with the zsetAdd function.

zsetAdd

Nothing. It’s all in the flow chart.

First determine whether the code is ziplist or skiplist.

Ziplist coding

If you want to convert the code, you need to call zsetConvert to convert to Ziplist code, which is not described here.

// The ziplist process logic
if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
    unsigned char *eptr;

    // zset has an element to insert
    if((eptr = zzlFind(zobj->ptr, ele, &curscore)) ! =NULL) {
        // Update at not exist when storing elements to be inserted
        if (nx) {
            *out_flags |= ZADD_OUT_NOP;
            return 1; }...if (newscore) *newscore = score;

        // The original score is different from the score to be inserted
        if(score ! = curscore) {// Delete the original element first
            zobj->ptr = zzlDelete(zobj->ptr, eptr);
            // Insert a new element
            zobj->ptr = zzlInsert(zobj->ptr, ele, score);
            *out_flags |= ZADD_OUT_UPDATED;
        }
        return 1;
    }
    // There is no element to insert in zset
    else if(! xx) {Too much / / to test whether ele | | ziplist is too large
        if (zzlLength(zobj->ptr) + 1> server.zset_max_ziplist_entries || sdslen(ele) > server.zset_max_ziplist_value || ! ziplistSafeToAdd(zobj->ptr, sdslen(ele))) {// Convert to skiplist encoding
            zsetConvert(zobj, OBJ_ENCODING_SKIPLIST);
        } else {
            // Insert (Element,score) pair in ziplist
            zobj->ptr = zzlInsert(zobj->ptr, ele, score);
            if (newscore) *newscore = score;
            *out_flags |= ZADD_OUT_ADDED;
            return 1; }}else {
        *out_flags |= ZADD_OUT_NOP;
        return 1; }}Copy the code

Skiplist coding

// Skiplist code processing logic
if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
    zset *zs = zobj->ptr;
    zskiplistNode *znode;
    dictEntry *de;

    // Query the new element from the hash table
    de = dictFind(zs->dict, ele);

    // The element was found
    if(de ! =NULL) {
        /* NX? Return, same element already exists. */
        if (nx) {
            *out_flags |= ZADD_OUT_NOP;
            return 1; }...if (newscore) *newscore = score;

        // The weight changes
        if(score ! = curscore) {// Update the hop table node
            znode = zslUpdateScore(zs->zsl, curscore, ele, score);
            // Set the hash element's value to the weight of the hop node
            dictGetVal(de) = &znode->score; /* Update score ptr. */
            *out_flags |= ZADD_OUT_UPDATED;
        }
        return 1;
    }
        // If the new element does not exist
    else if(! xx) { ele = sdsdup(ele);// Insert new elements into the hop table
        znode = zslInsert(zs->zsl, score, ele);
        // Insert a new element into the hash table
        serverAssert(dictAdd(zs->dict, ele, &znode->score) == DICT_OK);
        *out_flags |= ZADD_OUT_ADDED;
        if (newscore) *newscore = score;
        return 1;
    } else {
        *out_flags |= ZADD_OUT_NOP;
        return 1; }}Copy the code

ZsetAdd overall code

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
    /* Turn options into simple to check vars. */
    intincr = (in_flags & ZADD_IN_INCR) ! =0;
    intnx = (in_flags & ZADD_IN_NX) ! =0;
    intxx = (in_flags & ZADD_IN_XX) ! =0;
    intgt = (in_flags & ZADD_IN_GT) ! =0;
    intlt = (in_flags & ZADD_IN_LT) ! =0;
    *out_flags = 0; /* We'll return our response flags. */
    double curscore;

    /* NaN as input is an error regardless of all the other parameters. */
    // Check whether score is valid or not
    if (isnan(score)) {
        *out_flags = ZADD_OUT_NAN;
        return 0;
    }

    /* Update the sorted set according to its encoding. */

    // The ziplist process logic
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *eptr;

        // zset has an element to insert
        if((eptr = zzlFind(zobj->ptr, ele, &curscore)) ! =NULL) {
            // Update at not exist when storing elements to be inserted
            if (nx) {
                *out_flags |= ZADD_OUT_NOP;
                return 1;
            }

            /* Prepare the score for the increment if needed. */
            if (incr) {
                score += curscore;
                if (isnan(score)) {
                    *out_flags |= ZADD_OUT_NAN;
                    return 0; }}/* GT/LT? Only update if score is greater/less than current. */
            if ((lt && score >= curscore) || (gt && score <= curscore)) {
                *out_flags |= ZADD_OUT_NOP;
                return 1;
            }

            if (newscore) *newscore = score;

            // The original score is different from the score to be inserted
            if(score ! = curscore) {// Delete the original element first
                zobj->ptr = zzlDelete(zobj->ptr, eptr);
                // Insert a new element
                zobj->ptr = zzlInsert(zobj->ptr, ele, score);
                *out_flags |= ZADD_OUT_UPDATED;
            }
            return 1;
        }
            // There is no element to insert in zset
        else if(! xx) {Too much / / to test whether ele | | ziplist is too large
            if (zzlLength(zobj->ptr) + 1> server.zset_max_ziplist_entries || sdslen(ele) > server.zset_max_ziplist_value || ! ziplistSafeToAdd(zobj->ptr, sdslen(ele))) {// Convert to skiplist encoding
                zsetConvert(zobj, OBJ_ENCODING_SKIPLIST);
            } else {
                // Insert (Element,score) pair in ziplist
                zobj->ptr = zzlInsert(zobj->ptr, ele, score);
                if (newscore) *newscore = score;
                *out_flags |= ZADD_OUT_ADDED;
                return 1; }}else {
            *out_flags |= ZADD_OUT_NOP;
            return 1; }}/* Note that the above block handling ziplist would have either returned or * converted the key to skiplist. */

    // Skiplist code processing logic
    if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplistNode *znode;
        dictEntry *de;

        // Query the new element from the hash table
        de = dictFind(zs->dict, ele);

        // The element was found
        if(de ! =NULL) {
            /* NX? Return, same element already exists. */
            if (nx) {
                *out_flags |= ZADD_OUT_NOP;
                return 1;
            }

            // Query the weights of elements from the hash table
            curscore = *(double *) dictGetVal(de);

            // To update the element weight value
            if (incr) {
                score += curscore;
                if (isnan(score)) {
                    *out_flags |= ZADD_OUT_NAN;
                    return 0; }}/* GT/LT? Only update if score is greater/less than current. */
            if ((lt && score >= curscore) || (gt && score <= curscore)) {
                *out_flags |= ZADD_OUT_NOP;
                return 1;
            }

            if (newscore) *newscore = score;

            // The weight changes
            if(score ! = curscore) {// Update the hop table node
                znode = zslUpdateScore(zs->zsl, curscore, ele, score);
                // Set the hash element's value to the weight of the hop node
                dictGetVal(de) = &znode->score; /* Update score ptr. */
                *out_flags |= ZADD_OUT_UPDATED;
            }
            return 1;
        }
            // If the new element does not exist
        else if(! xx) { ele = sdsdup(ele);// Insert new elements into the hop table
            znode = zslInsert(zs->zsl, score, ele);
            // Insert a new element into the hash table
            serverAssert(dictAdd(zs->dict, ele, &znode->score) == DICT_OK);
            *out_flags |= ZADD_OUT_ADDED;
            if (newscore) *newscore = score;
            return 1;
        } else {
            *out_flags |= ZADD_OUT_NOP;
            return 1; }}else {
        serverPanic("Unknown sorted set encoding");
    }
    return 0; /* Never reached. */
}
Copy the code

zsetDel

int zsetDel(robj *zobj, sds ele) {
    / / ziplist encoding
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *eptr;

        // Find the corresponding node
        if ((eptr = zzlFind(zobj->ptr, ele, NULL)) != NULL) {
            // Delete from ziplist
            zobj->ptr = zzlDelete(zobj->ptr, eptr);
            return 1; }}/ / skiplist encoding
    else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        // Delete from skiplist
        if (zsetRemoveFromSkiplist(zs, ele)) {
            if (htNeedsResize(zs->dict)) dictResize(zs->dict);
            return 1; }}else {
        serverPanic("Unknown sorted set encoding");
    }
    return 0; /* No such element found. */
}
Copy the code

The zsetRemoveFromSkiplist function looks like this:

static int zsetRemoveFromSkiplist(zset *zs, sds ele) {
    dictEntry *de;
    double score;

    de = dictUnlink(zs->dict,ele);
    if(de ! =NULL) {
        score = *(double*)dictGetVal(de);

        // Unlink the element from the hash table
        dictFreeUnlinkedEntry(zs->dict,de);

        // Remove the element from the hop table and free up memory
        int retval = zslDelete(zs->zsl,score,ele,NULL);
        serverAssert(retval);

        return 1;
    }

    return 0;
}
Copy the code

The zslDelete function in the code is analyzed in the hop table section of the article.

Refer to the link

• Redis Design and Implementation – Ordered collection objects
• Geek time Redis source code analysis and actual combat – 05 | ordered set why can support both queries and range queries?

Redis source code concise analysis series

The most concise Redis source code analysis series of articles

Java programming ideas – the most complete mind map -GitHub download link, need partners can take ~

Original is not easy, I hope you reprint when please contact me, and mark the original link.