Redis数据结构之Sorted Sets

redis 版本7.x

有序性与唯一性

Sorted sets与Sets类似，是一种集合类型，这种集合中不会出现重复的member(数据)。Sorted seats中的元素由两部分组成，分别是member和score(分数)。

member会关联一个double类型的score，Sorted sets默认会根据这个score对member从小到大排序。如果member关联的score相同，则按照字符串的字典顺序排列。

常见使用场景：

排行榜：游戏中根据分数排名top10。
速率限流器：滑动窗口速率限制器。
延迟队列：使用score存储过期时间，从小到大排序，最靠前的就是最先到期的数据。

skiplist + dict 和 listpack

Sorted sets底层通过两种方式存储数据：

listpack（7.0版本之前是ziplist）：使用条件是集合元素小于或等于128，且member占用字节数小于64。将member和score紧凑排列作为listpack的一个元素存储。
skiplist + dict：当不满足上述条件时，将数据分别存储在skiplist（跳表）和dict中，是一种空间换时间的思想。散列表key存储的是member，value存储的是关联的score。

listpack适用于元素个数不多且占用空间不大的场景，使用listpack就是为了节省内存。Sorted Sets能支持高效的范围查询，正是因为采用了skiplist。

而使用dict的目的是以O(1)的时间复杂度查询单个元素。总之，Sorted Sets在插入或者更新时，会同时向skiplist和dict中插入或更新对应的数据，以保证两者数据的一致性。

skiplist + dict

skiplist本质是一种可以进行二分查找的有序链表。skiplist在原有的基础上增加了多级索引来实现快速查找。

skiplist节点查找

通常数据查找是从顶层开始，如果节点保存的值比待查数据的值小，skipllist就继续访问该层的下一个节点。

如果比待查数据的值大，就跳到当前节点的下一层的链表继续查找。如下图所示查找节点17：

从level1开始，17大于6，继续与下一个节点比较
17<26，回到原节点，跳到当前节点的level0层链表，与下一个节点比较，找到目标17

skiplist也是受到这种多层链表的启发设计出来的。根据上面的生成链表，上层节点个数是下层节点个数的一半，查找过程类似二分查找，时间复杂度是O(n)。

但是，这种设计方式有个问题，就是每次新增一个节点，就会打乱相邻的两层链表节点个数2：1的关系，就需要调整链表结构。

为了避免这个问题，skiplist不要求上下相邻两层链表之间节点个数有严格的比例关系，而是为每个节点随机出一个层数，这样插入节点时只需要修改前后指针。

Sorted Sets相关数据结构源码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


typedef struct zskiplist {

    // 头尾指针便于双向遍历
    struct zskiplistNode *header, *tail;
    // 当前skiplist包含的元素个数
    unsigned long length;
    // 表内节点的最大层级
    int level;
    size_t alloc_size;
} zskiplist;

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

skiplist中的每个节点，由zskiplistNode结构体表示：

1
2
3
4
5
6
7
8
9


typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

ele和score属性：使用sds类型的ele存储实际数据，score存储分数。
*backward：后退指针，指向该节点的上一个节点，便于倒序查找。每个节点只有一个后退指针，只有level0层的节点是双向链表。
level[]：
- *forward：前进指针。
- span：跨度，记录该层的forward指针指向的下一个节点之间的跨越了level0层的节点数

listpack

listpack的优势的节省内存，但只能按顺序查找元素，时间复杂度是O(n)。正因如此，才能在少量数据的情况下，节省内存同时又不影响性能。