Redis从入门到放弃系列(五) ZSet

本文例子基于：5.0.4 ZSet是Redis中一种比较复杂的数据结构,当存储大小在128之内且member得长度在64以下,其实现为zipList,超过为SkipList

忽然发现,到现在第五篇文章,还没有讲到zipList,然而前面例如Hash,List的篇章都涉及到了zipList的,后面会单独写一篇zipList的实现的~立Flag 请期待【Redis从入门到放弃系列(外传) ZipList】

言归正传，首先让我们来看一下该如何在redis里面使用ZSet类型

1//将一个或多个元素及其分数加入到有序集合里面
2ZADD key [NX|XX] [CH] [INCR] score member [score member ...]
3
4
5
6
7

代码示例：

1//添加元素
2>zadd store 1000 xiaoming 2000 xiaoqiang 3000 xiaoyue
3(integer) 3
4//返回指定区间内的有序集合列表                        
5> zrange store 0 -1 withscores    
61) "xiaoming"                                   
72) "1000"                                       
83) "xiaoqiang"                                  
94) "2000"                                       
105) "xiaoyue"                                    
116) "3000"                  
12//返回有序集合的数量
13>zcard store
14(integer) 3  
15//查看处于1000到2000的存款的人数
16>zcount store 1000 2000 
17(integer) 2  
18//查询处于1000到2000的存款的人群
19> ZRANGEBYSCORE store 1000 2000
201) "xiaoming"
212) "xiaoqiang"
22//根据member查看当前排名
23>zrank store xiaoming
24(integer) 0 
25
26
27
28
29

至此,redis zset的用法先告一段落.

源码解析

按照惯例,先来一波zset的数据结构

1/* ZSETs use a specialized version of Skiplists */
2typedef struct zskiplistNode {
3    sds ele;
4    double score;
5    struct zskiplistNode *backward;
6    struct zskiplistLevel {
7        struct zskiplistNode *forward;
8        unsigned long span;
9    } level[];
10} zskiplistNode;
11
12typedef struct zskiplist {
13    struct zskiplistNode *header, *tail;
14    unsigned long length;
15    int level;
16} zskiplist;
17
18typedef struct zset {
19    dict *dict;
20    zskiplist *zsl;
21} zset;
22
23
24
25
26

SkipList编码的有序集合底层是使用一个命为zset的结构体构成的,该结构体拥有两种数据类型,dict跟zskiplist。zskiplist按照score从小到大保存所有集合元素,dict则保存着member到score的映射关系,两个数据结构共用着相同元素的ele和score的内存。 zskiplist是一个双向链表,这是为了方便倒序方式获取一个范围内的元素。关于跳跃链表的讲解请参考漫画算法：什么是跳跃表？

当我们在使用zadd key member的时候，redis是如何实现的呢？让我们来看一下源码:

1/* Insert a new node in the skiplist. Assumes the element does not already
2 * exist (up to the caller to enforce that). The skiplist takes ownership
3 * of the passed SDS string 'ele'. */
4zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
5    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
6    unsigned int rank[ZSKIPLIST_MAXLEVEL];
7    int i, level;
8
9    serverAssert(!isnan(score));
10    x = zsl->header;
11    for (i = zsl->level-1; i >= 0; i--) {
12        /* store rank that is crossed to reach the insert position */
13        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
14        while (x->level[i].forward &&
15                (x->level[i].forward->score < score ||
16                    (x->level[i].forward->score == score &&
17                    sdscmp(x->level[i].forward->ele,ele) < 0)))
18        {
19            rank[i] += x->level[i].span;
20            x = x->level[i].forward;
21        }
22        update[i] = x;
23    }
24    /* we assume the element is not already inside, since we allow duplicated
25     * scores, reinserting the same element should never happen since the
26     * caller of zslInsert() should test in the hash table if the element is
27     * already inside or not. */
28    level = zslRandomLevel();
29    if (level > zsl->level) {
30        for (i = zsl->level; i < level; i++) {
31            rank[i] = 0;
32            update[i] = zsl->header;
33            update[i]->level[i].span = zsl->length;
34        }
35        zsl->level = level;
36    }
37    x = zslCreateNode(level,score,ele);
38    for (i = 0; i < level; i++) {
39        x->level[i].forward = update[i]->level[i].forward;
40        update[i]->level[i].forward = x;
41
42        /* update span covered by update[i] as x is inserted here */
43        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
44        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
45    }
46
47    /* increment span for untouched levels */
48    for (i = level; i < zsl->level; i++) {
49        update[i]->level[i].span++;
50    }
51
52    x->backward = (update[0] == zsl->header) ? NULL : update[0];
53    if (x->level[0].forward)
54        x->level[0].forward->backward = x;
55    else
56        zsl->tail = x;
57    zsl->length++;
58    return x;
59}
60
61
62
63
64

上面的流程我们用一张图来表示,如下所示:

当我们在使用zrank key member的时候,zset是怎么实现的呢？让我们一起来看一下源码

1long zsetRank(robj *zobj, sds ele, int reverse) {
2    unsigned long llen;
3    unsigned long rank;
4
5    llen = zsetLength(zobj);
6
7    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
8        //忽略掉 zipList查找过程
9    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
10        zset *zs = zobj->ptr;
11        zskiplist *zsl = zs->zsl;
12        dictEntry *de;
13        double score;
14
15        de = dictFind(zs->dict,ele);
16        if (de != NULL) {
17            score = *(double*)dictGetVal(de);
18            rank = zslGetRank(zsl,score,ele);
19            /* Existing elements always have a rank. */
20            serverAssert(rank != 0);
21            if (reverse)
22                return llen-rank;
23            else
24                return rank-1;
25        } else {
26            return -1;
27        }
28    } else {
29        serverPanic("Unknown sorted set encoding");
30    }
31}
32/* Find the rank for an element by both score and key.
33 * Returns 0 when the element cannot be found, rank otherwise.
34 * Note that the rank is 1-based due to the span of zsl->header to the
35 * first element. */
36unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
37    zskiplistNode *x;
38    unsigned long rank = 0;
39    int i;
40
41    x = zsl->header;
42    for (i = zsl->level-1; i >= 0; i--) {
43        while (x->level[i].forward &&
44            (x->level[i].forward->score < score ||
45                (x->level[i].forward->score == score &&
46                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
47            rank += x->level[i].span;
48            x = x->level[i].forward;
49        }
50
51        /* x might be equal to zsl->header, so test if obj is non-NULL */
52        if (x->ele && sdscmp(x->ele,ele) == 0) {
53            return rank;
54        }
55    }
56    return 0;
57}
58
59
60
61
62

其实查找的时候跟上面插入流程是有很多地方享受的,获取用户的排名是通过累加的span。

应用场景

1.排行榜

2.存储社交关系

3.滑动窗口应用

Redis从入门到放弃系列(五) ZSet