“This is my 40th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

The data structure

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

There are two implementations

1. The first ziplist node holds the element’s members, while the second node holds the element’s score. The collection elements in the compressed list are sorted by branch from smallest to largest, with the elements with the lowest score placed near the table head and the elements with the highest score placed near the table end.

Skiplist actually uses the Zset structure to encapsulate dictionaries and skip lists. The ZSL skip list branch in the Zset structure holds all elements from small to large. With this skip list, programs can perform range operations on ordered sets, such as Zrank, Zrange and other commands are based on the skip list to achieve.

Ziplist inserts data

/* Insert (element,score) pair in listpack. This function assumes the element is * not yet present in the list. */
unsigned char *zzlInsert(unsigned char *zl, sds ele, double score) {
    unsigned char *eptr = lpSeek(zl,0), *sptr;
    double s;
    
    // The sorting process
    while(eptr ! =NULL) { sptr = lpNext(zl,eptr); serverAssert(sptr ! =NULL);
        s = zzlGetScore(sptr);

        if (s > score) {
            /* First element with score larger than score for element to be * inserted. This means we should take its spot in the list to * maintain ordering. */
            // element, score
            zl = zzlInsertAt(zl,eptr,ele,score);
            break;
        } else if (s == score) {
            /* Ensure lexicographical ordering for elements. */
            if (zzlCompareElements(eptr,(unsigned char*)ele,sdslen(ele)) > 0) {
                zl = zzlInsertAt(zl,eptr,ele,score);
                break; }}/* Move to next element. */
        eptr = lpNext(zl,sptr);
    }

    /* Push on tail of list when it was not yet inserted. */
    if (eptr == NULL)
        zl = zzlInsertAt(zl,NULL,ele,score);
    return zl;
}
Copy the code

Ziplist compressed lists are switched to skip lists

/* Convert the sorted set object into a listpack if it is not already a listpack
 * and if the number of elements and the maximum element size and total elements size
 * are within the expected ranges. */
void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen, size_t totelelen) {
    if (zobj->encoding == OBJ_ENCODING_LISTPACK) return;
    zset *zset = zobj->ptr;

    if (zset->zsl->length <= server.zset_max_listpack_entries &&
        maxelelen <= server.zset_max_listpack_value &&
        lpSafeToAdd(NULL, totelelen))
    {
        zsetConvert(zobj,OBJ_ENCODING_LISTPACK);
    }
}
Copy the code

Pay attention to the point

On the basis of skiplist, dict needs to be created because when the score of an element needs to be obtained, the complexity of skiplist is O(logN), while the complexity of dict is O(1), see (zsetAdd). In particular, the main thing is that when the bottom layer is Ziplist, the operation time is O(n).

int zsetScore(robj *zobj, sds member, double *score) { if (! zobj || ! member) return C_ERR; if (zobj->encoding == OBJ_ENCODING_LISTPACK) { if (zzlFind(zobj->ptr, member, score) == NULL) return C_ERR; } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) { zset *zs = zobj->ptr; dictEntry *de = dictFind(zs->dict, member); if (de == NULL) return C_ERR; *score = *(double*)dictGetVal(de); } else { serverPanic("Unknown sorted set encoding"); } return C_OK; } unsigned char *zzlFind(unsigned char *lp, sds ele, double *score) { unsigned char *eptr, *sptr; if ((eptr = lpFirst(lp)) == NULL) return NULL; eptr = lpFind(lp, eptr, (unsigned char*)ele, sdslen(ele), 1); if (eptr) { sptr = lpNext(lp,eptr); serverAssert(sptr ! = NULL); /* Matching element, pull out score. */ if (score ! = NULL) *score = zzlGetScore(sptr); return eptr; } return NULL; }Copy the code

• Zkiplist and dict share elements and points (pointer copying).
• The conversion from Zkiplist to skiplist is irreversible
• The two parameters zset-max-ziplist-entries and zset-max-ziplist-value can be changed in the configuration file
• Zset also does not allow duplication

Usage scenarios

• Priority queue

• Leaderboard system: video websites mainly need to make leaderboards for videos uploaded by users. The dimensions of the leaderboard are in many aspects: ranking by time, by play amount and by likes obtained

  • Example Add a user’s likes

  zadd user:ranking:2022_02_20 3 mike
  Copy the code

  • Increase the thumb up

  zincrby user:ranking:2020_02_20 1 mike
  Copy the code

  • Cancel the thumb up

  zrem user:ranking:2020_02_20 mike
  Copy the code

  • Temporarily get the 10 users with the most likes

  zrevrang user:rangking:2020_02_20 0 9
  Copy the code

  • Displays user information as well as user scores and rankings

  hgetall user:info:tom
  zscore user:rangking:2020_02_20 mike
  zrank user:rangking:2020_02_20 mike
  Copy the code

Common operation

Redis object summary