有序集

REDIS_ZSET (有序集)是 ZADDZCOUNT 等命令的操作对象, 它使用 REDIS_ENCODING_ZIPLISTREDIS_ENCODING_SKIPLIST 两种方式编码:

digraph redis_zset {
    
    node [shape=plaintext, style = filled];

    edge [style = bold];

    // type

    REDIS_ZSET [label="有序集合\nREDIS_ZSET", fillcolor = "#95BBE3"];

    // encoding

    REDIS_ENCODING_ZIPLIST [label="ziplist\nREDIS_ENCODING_ZIPLIST", fillcolor = "#FADCAD"];
    REDIS_ENCODING_SKIPLIST [label="跳跃表\nREDIS_ENCODING_SKIPLIST", fillcolor = "#FADCAD"];

    // edge

    REDIS_ZSET -> REDIS_ENCODING_ZIPLIST;
    REDIS_ZSET -> REDIS_ENCODING_SKIPLIST;

    // datastruct 1

    ziplist [label="ziplist"];

    REDIS_ENCODING_ZIPLIST -> ziplist;

    // datastruct 2

    zset [label="redis.h/zset"];

    dict [label="dict.h/dict"];
    zskiplist [label="redis.h/zskiplist"];

    REDIS_ENCODING_SKIPLIST -> zset;

    zset -> dict;
    zset -> zskiplist;
}

编码的选择

在通过 ZADD 命令添加第一个元素到空 key 时, 程序通过检查输入的第一个元素来决定该创建什么编码的有序集。

如果第一个元素符合以下条件的话, 就创建一个 REDIS_ENCODING_ZIPLIST 编码的有序集:

  • 服务器属性 server.zset_max_ziplist_entries 的值大于 0 (默认为 128 )。
  • 元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值(默认为 64 )。

否则,程序就创建一个 REDIS_ENCODING_SKIPLIST 编码的有序集。

编码的转换

对于一个 REDIS_ENCODING_ZIPLIST 编码的有序集, 只要满足以下任一条件, 就将它转换为 REDIS_ENCODING_SKIPLIST 编码:

  • ziplist 所保存的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值(默认值为 128
  • 新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值(默认值为 64

ZIPLIST 编码的有序集

当使用 REDIS_ENCODING_ZIPLIST 编码时, 有序集将元素保存到 ziplist 数据结构里面。

其中,每个有序集元素以两个相邻的 ziplist 节点表示, 第一个节点保存元素的 member 域, 第二个元素保存元素的 score 域。

多个元素之间按 score 值从小到大排序, 如果两个元素的 score 相同, 那么按字典序对 member 进行对比, 决定那个元素排在前面, 那个元素排在后面。

          |<--  element 1 -->|<--  element 2 -->|<--   .......   -->|

+---------+---------+--------+---------+--------+---------+---------+---------+
| ZIPLIST |         |        |         |        |         |         | ZIPLIST |
| ENTRY   | member1 | score1 | member2 | score2 |   ...   |   ...   | ENTRY   |
| HEAD    |         |        |         |        |         |         | END     |
+---------+---------+--------+---------+--------+---------+---------+---------+

score1 <= score2 <= ...

虽然元素是按 score 域有序排序的, 但对 ziplist 的节点指针只能线性地移动, 所以在 REDIS_ENCODING_ZIPLIST 编码的有序集中, 查找某个给定元素的复杂度为 \(O(N)\)

每次执行添加/删除/更新操作都需要执行一次查找元素的操作, 因此这些函数的复杂度都不低于 \(O(N)\) , 至于这些操作的实际复杂度, 取决于它们底层所执行的 ziplist 操作。

SKIPLIST 编码的有序集

当使用 REDIS_ENCODING_SKIPLIST 编码时, 有序集元素由 redis.h/zset 结构来保存:

/*
 * 有序集
 */
typedef struct zset {

    // 字典
    dict *dict;

    // 跳跃表
    zskiplist *zsl;

} zset;

zset 同时使用字典和跳跃表两个数据结构来保存有序集元素。

其中, 元素的成员由一个 redisObject 结构表示, 而元素的 score 则是一个 double 类型的浮点数, 字典和跳跃表两个结构通过将指针共同指向这两个值来节约空间 (不用每个元素都复制两份)。

下图展示了一个 REDIS_ENCODING_SKIPLIST 编码的有序集:

digraph zset {

    rankdir = LR;

    node [shape = record, style = filled];

    edge [style = bold];

    label = "在实际中,字典和跳跃表通过指针来共享元素的 member 和 score\n图中对每个元素都重复显示了一遍,只是为了展示的方便";

    zset [label = "<head>zset |<dict>dict |<zskiplist> zskiplist"];

    // skiplist

    skiplist [label ="<head>zskipNode |<3> |<2> |<1> |<score>score\n NULL |<robj>robj\n NULL", fillcolor = "#FADCAD"];
    six [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 6 |<robj>robj\n x", fillcolor = "#FADCAD"];
    ten [label = "<head>zskipNode | <1> |<score>score\n 10 |<robj>robj\n y", fillcolor = "#FADCAD"];
    fiften [label = "<head>zskipNode |<3> |<2> |<1> |<score>score\n 15 |<robj>robj\n z", fillcolor = "#FADCAD"];

    zset:dict -> dict:head;
    zset:zskiplist -> skiplist:head;
    skiplist:3 -> six:3; 
    skiplist:2 -> six:2;
    skiplist:1 -> six:1;
    six:1 -> ten:1;
    six:2 -> fiften:2;
    six:3 -> fiften:3;
    ten:1 -> fiften:1;


    // dict

    dict [label = "<head>dictht | ... |<table> table | ...", fillcolor = "#A8E270"];
    bucket [label = "<head>dictEntry**\n(bucket) |<0> 0 |<1> 1 |<2> 2", fillcolor = "#95BBE3"];
    entry_x [label = "<head>dictEntry |{<key>key\n x |<value>value\n 6}", fillcolor = "#F2F2F2"];
    entry_y [label = "<head>dictEntry |{<key>key\n y |<value>value\n 10}", fillcolor = "#F2F2F2"];
    entry_z [label = "<head>dictEntry |{<key>key\n z |<value>value\n 15}", fillcolor = "#F2F2F2"];

    dict:table -> bucket:head;

    bucket:0 -> entry_x:head;
    bucket:1 -> entry_y:head;
    bucket:2 -> entry_z:head;

}

通过使用字典结构, 并将 member 作为键, score 作为值, 有序集可以在 \(O(1)\) 复杂度内:

  • 检查给定 member 是否存在于有序集(被很多底层函数使用);
  • 取出 member 对应的 score 值(实现 ZSCORE 命令)。

另一方面, 通过使用跳跃表, 可以让有序集支持以下两种操作:

  • \(O(\log N)\) 期望时间、 \(O(N)\) 最坏时间内根据 scoremember 进行定位(被很多底层函数使用);
  • 范围性查找和处理操作,这是(高效地)实现 ZRANGEZRANKZINTERSTORE 等命令的关键。

通过同时使用字典和跳跃表, 有序集可以高效地实现按成员查找和按顺序查找两种操作。

讨论

comments powered by Disqus