关于redis:Redis-Sorted-Set-实现与应用

前言

在没有真正意识 Redis 之前，你可能都低估了它

一开始对于 Redis 咱们的意识都是一个 key:value 的缓存，当然用的最多的也就是这个作用。但随着 Redis 的一直倒退，缓缓的我就发现它有的性能越来越多，它可能在肯定水平上帮咱们疾速简化一些高并发场景下的开发。我感觉它其中最重要的设计是它的 <mark style=”background: #FFB86CA6;”> 数据结构 </mark>。通过几个根底的数据结构的组合，就能实现一些高性能的构造。比方咱们明天要探讨的 Sorted Set 就是这样一个构造。因为 Redis 中称为 zset 所以后文中为了简化间接也叫 zset。

什么是 Sorted Set

我感觉可能很多同学还没有用过，其实非常容易了解，就是一个有序的汇合，无论你以什么程序增加元素，最终都会依据分数排成一个有序的汇合。通过它咱们能够疾速取得一个组数据的最高的几个值。

猜想实现

堆？没错，我的第一反馈也是这个，要实现一个这样的构造最先想到的就是堆或者说是优先队列的实现，完满匹配。

但，不对，咱们晓得，对于堆，咱们只能疾速失去最大或最小值。而对于 zset 其中有一个办法是 ZRANGE key start stop 也就是能够获取一个范畴，比方获取排序后的第 3 位开始后的 5 个元素。而且它能够疾速获取到一个某个元素的地位 ZRANK key，也就是疾速查问到某个元素的排名。

所以，这显然不能简略的用“堆”搞定了。

前置常识

• ziplist 压缩列表 redis 中为了压缩数据大小来实现的一种数据结构，通过数据长度来定位下一个数据和前一个数据
• skiplist 跳表 一种“重叠”（这个概念是我脑补的）的数据结构，通过不同层级的的标记能疾速进行元素地位的定位，思路上有点相似二分

这两个构造我在这里不具体开展了，不然篇幅太长。如有须要，请查看参考链接：

• redis-ziplist
• redis-skiplist

具体实现

废话不多说，间接开代码最间接。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

所以 zset 的构造就是一个字典（hash 表）+ 一个 skiplist（跳表）就完事了呗？简略，走了走了。别急~ 其实并不是这样。

数据结构的变动

我来看一下元素的 add 办法就明确了外面的玄机

int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
    // 重点 1
    if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
        unsigned char *eptr;

        if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) {...................} else if (!xx) {
            /* check if the element is too large or the list
             * becomes too long *before* executing zzlInsert. */
            if (zzlLength(zobj->ptr)+1 > server.zset_max_listpack_entries ||
                sdslen(ele) > server.zset_max_listpack_value ||
                !lpSafeToAdd(zobj->ptr, sdslen(ele)))
            {
                // 重点 2
                zsetConvertAndExpand(zobj, OBJ_ENCODING_SKIPLIST, zsetLength(zobj) + 1);
            } else {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 listpack would have either returned or
     * converted the key to skiplist. */
    // 重点 3
    if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {...............} else {serverPanic("Unknown sorted set encoding");
    }
    return 0; /* Never reached. */
}

1. 依据以后 encoding 不同，有两种不同的实现，别离是：ziplist 和咱们下面提到的 `dict + skiplist
2. 触发数据结构变动的条件是元素数量超过 zset_max_listpack_entries 默认 128，还有一个条件是，有序汇合保留的所有元素成员的长度都小于 zset_max_listpack_value(64) 字节
3. 咱们能够通过 OBJECT ENCODING key 命令查看对象的编码方式（数据结构）

127.0.0.1:6379> OBJECT ENCODING linkinstar
"listpack"

127.0.0.1:6379> OBJECT ENCODING linkinstars
"skiplist"

为什么须要 dict

这是十分常见的一种查问优化策略，就是用空间换工夫，为了实现疾速用 key 查问该元素的分数和地位就能用到 dict（ZRANK）

long zsetRank(robj *zobj, sds ele, int reverse, double *output_score) {
    // ......
    if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
        // 这里只能遍历了
        // ....
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        // 这里查字典就好了
        de = dictFind(zs->dict,ele);
        if (de != NULL) {score = *(double*)dictGetVal(de);
            rank = zslGetRank(zsl,score,ele);
            /* Existing elements always have a rank. */
            serverAssert(rank != 0);
            if (output_score)
                *output_score = score;
            if (reverse)
                return llen-rank;
            else
                return rank-1;
        } else {return -1;}
    } else {serverPanic("Unknown sorted set encoding");
    }
}

能够看到，如果是 SKIPLIST 的 encoding 也就是有 dict 的数据结构的时候，就间接 dictFind 了，十分快。而且作为一个 dict 十分好保护，增加和删除元素的时候，同时操作一次 dict 就能够了。

留神点

Most sorted set operations are O(log(n)), where _n_ is the number of members.
Exercise some caution when running the ZRANGE command with large returns values (e.g., in the tens of thousands or more). This command’s time complexity is O(log(n) + m), where _m_ is the number of results returned.

绝大多数 zset 的操作都是 O(log(n)) 但 ZRANGE 须要留神。当实现为跳表的时候，须要进行 ZRANGE 查问的时候，须要查问一个范畴值，查问第一个指标必定是 O(log(n)) 而后向后找 m 个，所以显然 m 太大会影响性能。

利用场景

排行榜

第一个能想到的利用场景必定是这个，毕竟它的个性太像了，将须要排序的人和分数扔进去，一下就能搞定一个高性能的排行榜。就不多说了。

限流

这个是我一开始也没想到的。对于限流咱们罕用的必定是 token 或漏桶什么的，当然也有窗口，因为固定窗口有边界问题。滑动窗口就能够解决很大一部分问题，而如何滑动就很要害了。此时 zset 就能帮忙咱们来实现这个滑动窗口，咱们能够通过将用户拜访的工夫戳作为分数扔进去，每次拜访的时候能够抛弃掉过期的分数，而在 zset 的中的数量就是限流的大小了，超过数量就回绝了。

具体能够参考：https://engineering.classdojo.com/blog/2015/02/06/rolling-rat…

所有其余利用堆的场景

因为 zset 它实质就是个堆，那其实这个个性还能够被用在例如：撮合交易、抽奖等等须要堆的场景。

总结

Redis Sorted Set 给咱们带来的思考可能有上面这些：

1. 在不同数据量的时候应用不同的数据结构能优化存储和性能
2. 通过不同数据结构的组合来优化不同场景下的性能以提供更多的操作
3. 只有底层数据结构实现的好，下面能扩大的性能也会很简略