Redis设计与实现-数据结构

1. 基本数据结构

1. SDS

C 语言里面的字符串都是静态的，Redis 自己实现了一个动态字符串，我们称为 SDS（简单动态字符串）：

\0 既没有算入 len 也没有算入 free。

SDS 的优点：

• 传统 C 字符串想要获取长度需要 $O(n)$ 遍历，而 SDS 把长度存到了 len 中，可以 $O(1)$ 获取长度。

• 由于存在 free，所以在字符串后面追加的时候可以进行判断，防止缓冲区溢出。如果 buf 不够了可以扩容。SDS 相关的 API 都会检查 SDS 的空间是否满足要求。

• 高效的扩容，SDS 有如下的扩容机制：

  • 如果对 SDS 修改后，len 小于 1MB，那么额外分配和 len 同样大小的空间，即扩容后 len 和 free 相同。（二倍扩容）
  • 如果对 SDS 修改后，len 大于等于 1MB，那么只会分配 1MB 的额外空间。（对额外空间有上界限制）

  除非使用专门的 API 进行缩容，否则 buf 的空间只增不减。

• 二进制安全：由于 C 语言使用 \0 来表示字符串结尾，所以 C 语言字符串本身不能存储含有 \0 的字符串。而 SDS 使用 len 来表示字符串长度，就没有这个限制了。

• 兼容 C 字符串函数：SDS 遵循 C 字符串以 \0 结尾的惯例。这使得 SDS 可以直接重用 C 字符串函数库里面的函数。

注意上面的定义，buf 不是指针，而是柔性数组。也就是说 SDS 的头部后面紧跟着就是字符串数据。

2. 链表

Redis 链表有这个特点：

• 是一个双向的链表，并且带有 prev 和 next 指针，维护了 len，这使得可以高效地使用链表

• 实现了泛型，value 为 void*，并且链表上还有个 dup，free 和 match 函数来配合泛型使用。

3. 字典

3.1 结构

Redis 的字典基于哈希表：

Redis 的字典的键和值都是泛型的，dictType 存储了一些用于辅助泛型的函数。字典存储了两个哈希表，用于重哈希。

table 为一个数组，数组内的每个元素都是一个 dictEntry 指针。

dictEntry 的值要么是 u64 要么是 i64 要么是指针。next 指针用来处理哈希冲突。

3.2 哈希算法

这里 index 不是 hash % size 是因为，Redis 里面哈希表的 size 都是二的幂次，于是 sizemask = size - 1 的低位全为 1，那么 hash & sizemask 等价于 hash % size ，并且位操作更快

Redis 使用 MurmurHash2 算法来计算哈希值。该哈希算法的有点是即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度非常快。

当发生哈希冲突的时候，Redis 使用链地址法来解决。

由于 dictEntry 节点组成的链表是单链表，因此新节点是 $O(1)$ 插到链表头部位置。

3.3 重哈希

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的 装填因子 维持在一个合理的范围内，需要对哈希表的大小进行相应的扩展或者收缩，这个行为被称为重哈希。

重哈希的步骤：

• 为字典的 ht[1] 哈希表分配空间，哈希表的大小取决于要执行的操作和 ht[0] 当前包含的键值对数量
  • 如果执行扩展操作，那么 ht[1] 大小为第一个大于等于 ht[0].used * 2 的 2 的幂次
  • 如果执行收缩操作，那么 ht[1] 大小为第一个大于等于 ht[0].used 的 2 的幂次
• 将保存在 ht[0] 中的所有键值对重新计算键的哈希值和索引值，然后放到 ht[1] 里面
• 当 ht[0] 包含的所有键值对都迁移到 ht[1] 之后，释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 创建一个空白哈希表，为下一次重哈希做准备。

其中的第二个步骤并不是一次性完成的，而是分多次完成：

• 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表
• 将字典的 rehashidx 置为 0，表示重哈希工作正式开始
• 每次进行删除/查找/更新之类的操作后，还会把 ht[0] 哈希表在 rehashidx 索引上的所有键值对重哈希到 ht[1]，然后将 rehashidx 增一，直到将 ht[0] 全部重哈希完，此时将 rehashidx 置为 -1
• 进行查找操作时，会在两个哈希表中分别查找。进行添加操作时，把键值对加到 ht[1] 上面。确保 ht[0] 不再有所增加。

这种渐进式重哈希使得整个哈希过程均摊到每次操作中。

当如下任意条件之一满足时，程序会进行哈希表扩展操作：

• 服务器目前没有在执行 BGSAVE 命令或者是 BGREWRITEAOF 命令，且哈希表的装填因子大于等于 $1$
• 服务器目前没有在执行 BGSAVE 命令或者是 BGREWRITEAOF 命令，且哈希表的装填因子大于等于 $5$

Redis 在进行 BGSAVE 命令或者是 BGREWRITEAOF 命令时，会启动一个子进程。操作系统会使用 copy on write 技术来优化子进程的内存占用。如果此时进行重哈希的话就会带来内存的复制，所以 Redis 对装填因子有不同的要求。

当如下任意条件之一满足时，程序会进行哈希表收缩操作：

• 装填因子小于 $0.1$

4. 跳表

4.1 初始化跳表

c
1
2
3
4
5
6
7
// src/server.h
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
    size_t alloc_size;
} zskiplist;

其中 level 表示这个链表目前有多少层。

c
1
2
3
4
5
6
7
8
9
10
11
12
// src/server.h
typedef struct zskiplistNode {
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        /* Span is the number of elements between this node and the next node at this level.
         * At level 0, span is repurposed to store zskiplistNodeInfo for regular nodes, */
        unsigned long span;
    } level[];
    /* sds ele is embedded after level[] array (assist zslGetNodeElement(node) to access it) */
} zskiplistNode;

zskiplistNode 的内存结构比较有意思。C 语言规定 zskiplistNode 的最后一个成员如果是不带大小的数组的话，那么这个数组就被称为“柔性数组”。sizeof(zskiplistNode) 的时候，只会计算结构体前面的成员占用的内存大小，而不会计算后面柔性数组的大小。

同时，zskiplistNode 在内存中，后面紧跟着的内存空间会被用来存储 SDS。这种和关联的数据紧密放置的手法可以增加内存分配效率，减少内存碎片，增大缓存命中率。

创建跳表：

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// src/t_zset.c
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    zskiplist *zsl;
    size_t zsl_size;

    zsl = zmalloc_usable(sizeof(*zsl), &zsl_size);
    zsl->level = 1;
    zsl->length = 0;
    zsl->alloc_size = zsl_size;
    zsl->header = zslCreateHeaderNode(zsl);
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

跳表的 header 指向的是一个头节点，这个头节点是一个虚拟节点，不实际存储数据。

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// src/t_zset.c
/* Create a skiplist header node with ZSKIPLIST_MAXLEVEL levels */
static zskiplistNode *zslCreateHeaderNode(zskiplist *zsl) {
    size_t usable;
    zskiplistNode *zn = zmalloc_usable(sizeof(*zn) + ZSKIPLIST_MAXLEVEL * sizeof(struct zskiplistLevel), &usable);

    /* Initialize all fields */
    zn->score = 0;
    zn->backward = NULL;

    /* Initialize all level pointers and spans */
    for (int j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zn->level[j].forward = NULL;
        zn->level[j].span = 0;  /* Will be overwritten for level[0] below */
    }

    /* Use ZSL_OFFSET_NO_ELE as sentinel to indicate no embedded sds (header node) */
    zslSetNodeInfo(zn, ZSKIPLIST_MAXLEVEL, ZSL_OFFSET_NO_ELE);

    /* Track allocation size */
    zsl->alloc_size += usable;

    return zn;
}

其中的 ZSKIPLIST_MAXLEVEL 被定义为 32，Redis 的跳表最大支持 32 层。sizeof(*zn) 是 C 语言的一个特性，可以在定义某个变量的同时就引用这个变量做 sizeof，这里等价于 sizeof(zskiplistNode)。后面不再为 SDS 分配空间了，因为头节点是虚拟节点，不存储实际数据。

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// src/server.h
typedef struct zskiplistNodeInfo {
    uint16_t sdsoffset;  /* Offset from node start to sds data (after sds header) */
    uint8_t levels;      /* Number of levels in this node (1-32) */
    uint8_t reserved;
} zskiplistNodeInfo;

// src/t_zset.c
static inline void zslSetNodeInfo(zskiplistNode *node, uint8_t levels, uint16_t sdsoffset) {
    union {
        zskiplistNodeInfo info;
        unsigned long span;
    } u = { .info = { .levels = levels, .sdsoffset = sdsoffset } };
    node->level[0].span = u.span;
}

zslSetNodeInfo 这里使用 union 做到了把 zskiplistNodeInfo 压成了一个 32 位数。zskiplistNode 里面，level[0] 存储的 span 比较特别，为 zskiplistNodeInfo。

4.2 插入节点

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// src/t_zset.c
/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The element 'ele' is COPIED
 * into the new node, so the caller retains ownership and can free it. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    int level;

    serverAssert(!isnan(score));

    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    level = zslRandomLevel();
    zskiplistNode *node = zslCreateNode(zsl, level, score, ele);
    zslInsertNode(zsl, node);
    return node;
}

c
1
2
3
4
5
6
7
8
9
10
11
12
// sec/t_zset.c
/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
static int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

这里的 ZSKIPLIST_P 被设为 0.25。每次有 0.25 的概率让层数加一。

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// src/t_zset.c
/* Insert an already-created node, with its score, element set into the skiplist
 * at the correct position. Updates all forward/backward pointers and spans.
 * The node's level must already be set via zslSetNodeInfo(). */
static void zslInsertNode(zskiplist *zsl, zskiplistNode *node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];  /* Nodes that will point to the new node at each level */
    unsigned long rank[ZSKIPLIST_MAXLEVEL];     /* Rank (0-based) at each level during traversal */

    ....

    // 先处理当前跳表已经有的层级
    /* Find the position where this node should be inserted */
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (zslCompareWithNode(score, ele, x->level[i].forward) > 0) {
            rank[i] += zslGetNodeSpanAtLevel(x, i);
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    // 再处理没有的层级
    /* Update skiplist level if needed */
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            zslSetNodeSpanAtLevel(update[i], i, zsl->length);
        }
        zsl->level = level;
        zslGetNodeInfo(zsl->header)->levels = level;
    }

    /* Insert the node at the found position */
    for (i = 0; i < level; i++) {
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;

        /* update span covered by update[i] as node is inserted here */
        zslSetNodeSpanAtLevel(node, i, zslGetNodeSpanAtLevel(update[i], i) - (rank[0] - rank[i]));
        zslSetNodeSpanAtLevel(update[i], i, (rank[0] - rank[i]) + 1);
    }

    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        zslIncrNodeSpanAtLevel(update[i], i, 1);
    }

    /* Update backward pointers */
    node->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (node->level[0].forward)
        node->level[0].forward->backward = node;
    else
        zsl->tail = node;

    zsl->length++;
}

4.3 其他

其他的操作应该也差不多，这里就不多贴代码了。

总的来说跳表分成若干层，层数越低节点越多，并且上一层的节点一定是下一层节点的子集。遍历跳表的时候先从高层遍历，再逐步往下层走，类似于一个二分的过程。

Redis 中跳表节点对应的 SDS 必须是不同的。然后每个跳表节点还对应了一个分数 score。score 可以是相同的。比较两个节点时，score 相同则继续比较 SDS 字典序。

Redis 的跳表节点维护了一个 span，表示两个节点之间的距离（两个节点的下标之差）。span 用于快速进行 kth 操作，使得链表可以随机读写。

5. 整数集合

contents 中保存集合的各个元素，元素有序排列。

encoding 决定了如何解释 contents：

• encoding 为 INTSET_ENC_INT16：contents 为一个 int16_t 类型的数组
• encoding 为 INTSET_ENC_INT32：contents 为一个 int32_t 类型的数组
• encoding 为 INTSET_ENC_INT64：contents 为一个 int64_t 类型的数组

当要往这个整数集合里面添加一个新元素时，如果新元素的类型比集合当前元素类型要长时，整数集合会进行一个升级操作：

• 根据新元素的类型，扩展整数集合数组的空间大小
• 将集合中原来的元素进行类型转换，然后放到正确的位置上
• 将新元素放到数组中

由于引发升级的新元素类型的长度大于当前集合类型的长度，所以新加入的元素的值要么大于所有现有元素，要么小于所有现有元素，所以升级操作新元素的位置比较好确定。

整数集合不支持降级操作，一旦升级了就降不回来了。

6. 压缩列表

压缩列表主要的目的在于节省存储空间。Redis 一般会用压缩列表存少量且占用空间比较小的元素。

• zlbytes：4 字节，记录整个压缩列表占用的内存字节数
• zltail：4 字节，压缩列表的表尾节点距离压缩列表的起始地址有多少字节。通过这个可以快速得到列表中最后一个节点
• zllen：2 字节，u16。当这个属性小于 u16::MAX （65535）时，这个属性的值就是列表中包含节点的数量。当这个属性等于 u16::MAX 时，列表中节点的真实数量需要遍历整个压缩列表才能得到
• entryX：占用的大小不固定
• zlend：1 字节，一个特殊值 0xFF，用于标记压缩列表的末端

压缩列表的每个节点的结构如下：

• previous_entry_length：

  • 如果前一个节点的长度小于 254 字节，那么该属性占用 1 字节，表示前一节点的长度。
  • 如果前一节点的长度大于等于 254 字节，那么该属性长度为 5 字节，该属性的第一字节会被设置为 0xFE（254），之后四个字节用于保存前一节点的长度。

  通过这个属性可以得到前一个节点的地址，因此可以从后往前遍历列表。通过 zltail 可以从后往前遍历整个列表。

• encoding 属性记录了节点 content 属性保存的数据的类型和长度。首先看该属性的最高两位：

  • 00：encoding 为一字节，content 是一个字节数组，数组长度由 encoding 去掉前两位之后的位来编码。

  • 01：encoding 为两字节，content 是一个字节数组，数组长度由 encoding 去掉前两位之后的位来编码。

  • 10：encoding 为五字节，content 是一个字节数组，数组长度由 encoding 去掉前两位之后的位来编码。

  • 11：encoding 为一字节，content 表示一个整数，整数的类型和长度由 encoding 去掉前两位之后的位来编码：

其中的字节数组往往表示的是一个字符串（不含末尾 \0）：

在压缩列表中进行插入和删除数据时都要重新分配内存。

于是会存在一种叫做连锁更新的现象：

• （情况一）压缩链表中现有节点 e1 到 eN 大小介于 250 字节到 253 字节之间，每一个节点的 previous_entry_length 属性都是一个字节长的。

  此时如果将一个长度大于等于 254 字节的新节点 new 插入到压缩列表头部，那么 e1 的 previous_entry_length 就会占用 5 字节了，从而使得 e1 大小增加，变得大于等于 254 字节了，于是 e2 大小又增加。。。就这样出现了连锁更新。

• （情况二）big 节点大小大于等于 254 字节，而其他节点的大小均小于 254 字节，此时如果将 small 删去，e1 的 previous_entry_length 就变为 5 字节长，从而使得 e1 大于等于 254 字节，然后以此类推，又会导致连锁更新。

压缩列表再每次需要扩展时都会进行重新分配内存，最坏情况下进行 $O(n)$ 次重分配，每次分配 $O(n)$ 内存，总时间复杂度为 $O(n^2)$。

不过 Redis 只用压缩列表存比较少的元素，元素多了就换数据结构了。同时一般情况下连锁更新的情况不常见，即使出现了可能也就有三四个元素连锁更新。所以连锁更新的影响不大。

我有个想法是，在加入/删除元素的时候，先扫一遍列表中的元素，计算出最终需要的内存大小，然后再分配，这样的话就可以避免掉连锁更新的问题。

不过貌似是这样实现起来比较复杂，容易出锅，并且这样的话每次添加/删除都要额外扫描一次，反而给常见情况增加了时间，所以 Redis 没这么做。

Redis 现在使用 listpack 来替代压缩列表。listpack 的大致思想是，改为每个节点的末尾去记录当前节点的大小，相当于把当前节点的大小从下一个节点的开头移到了当前节点的末尾，这样就解决了连锁更新的问题。

2. 对象

Redis 中的键就是 SDS，但是值可能有不同的类型。Redis 的值不直接使用上述提到的数据结构来实现，而是基于这些数据结构创建了一个对象系统，用对象表示值。

2.1 类型与编码

对象的结构如下：

每个对象都有一个类型。我们称呼一个数据库键为“字符串键”的时候，指的是这个数据库键所对应的值为字符串类型的对象。

可以使用 TYPE 指令来查看一个键的值的对象类型：

Unknown
1
2
3
4
5
6
7
8
9
10
11
redis> SET msg "hello world"
OK

redis> TYPE msg
string

redis> RPUSH numbers 1 3 5
(integer) 6

redis> TYPE numbers
list

每种类型的对象都至少有两种不同的编码：

可以使用 OBJECT ENCODING 命令来查看一个数据库键的值对象的编码：

Unknown
1
2
3
4
5
6
7
8
9
10
11
redis> msg "hello world"
OK

redis> OBJECT ENCODING msg
"embstr"

redis> SET story "long long long long ... long"
OK

redis> OBJECT ENCODING story
"raw"

2.1.1 字符串对象

Redis 中，数字和一般的字符串（单个的这种字面量）都是用字符串对象存储的。123 和 "123" 没啥区别。

字符串对象的编码可以是 int、raw 或者 embstr。

如果一个值可以用 long 类型来表示，那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面（直接把 void* 视为 long），编码设置为 int。

反之，则将其视为字符串。如果这个字符串长度大于 32 字节，那么字符串对象将使用 SDS 来保存，编码设置为 raw。

如果长度小于等于 32 字节，那么使用 embstr 编码。

字符串对象使用 raw 编码时，需要先给对象分配一个空间，再给 SDS 分配一个空间，有两次内存分配。而 embstr 编码只需要分配一次内存，直接让 SDS 紧跟着对象的后面。

embstr 相比于 raw 带来如下的好处：

• 内存分配次数减少。同时这也意味着释放内存时也只需要释放一次
• 对象和 SDS 紧挨着，提高了缓存的利用率

注意，对于浮点数，其底层肯定是用 raw 或者 embstr 编码的，但是在有需要的时候，Redis 还是会把这些字符串转为浮点数：

Unknown
1
2
3
4
5
6
7
8
9
10
11
redis> SET pi 3.14
OK

redis> OBJECT ENCODING pi
"embstr"

redis> INCRBYFLOAT pi 2.0
"5.14"

redis> OBJECT ENCODING pi
"embstr"

编码转换

如果我们对 int 编码的对象进行了一些操作，使得其不能再被 int 编码，那么这个对象会直接变为 raw 编码：

Unknown
1
2
3
4
5
6
7
8
9
10
11
12
13
14
redis> SET number 10086
OK

redis> OBJECT ENCODING number
"int"

redis> APPEND number " is a good number!"
(integer) 23

redis> GET number
"10086 is a good number!"

redis> OBJECT ENCODING number
"raw"

Redis 并没有为 embstr 编码的字符串对象编写任何的修改程序，所以 embstr 编码的字符串对象实际上是只读的。当我们对其进行任何修改命令的时候，这个对象都会从 embstr 编码转为 raw 编码。

Unknown
1
2
3
4
5
6
7
8
9
10
11
redis> SET msg "hello world"
OK

redis> OBJECT ENCODING msg
"embstr"

redis> APPEND msg " again!"
(integer) 18

redis> OBJECT ENCODING msg
"raw"

2.1.2 列表对象

列表对象相当于是一个 Vector，不过里面的元素类型可以不一致：

Unknown
1
2
redis> RPUSH numbers 1 "three" 5
(integer) 3

列表对象有两种编码方式：ziplist 或者 linkedlist

当列表对象同时满足以下两个条件时，列表对象使用 ziplist 编码：

• 列表对象保存的所有字符串元素的长度都小于 64 字节
• 列表对象保存的元素数量小于 512 个

上面两个条件有一个不满足时就用 linkedlist 编码，比如上面的例子，假如使用了 linkedlist 编码：

同时，如果原来时 ziplist 编码，但是对列表修改使得列表不再满足上面两个条件，此时会发生转换。并且转换是单向的，不能再逆着转换了。

2.1.3 哈希对象

哈希对象相当于是一个维护了键值对的对象：

Unknown
1
2
redis> HSET profile name "Tom"
(integer) 1

哈希对象的编码可以是 ziplist 或是 hashtable。

同时满足下面条件时，哈希对象使用 ziplist 编码：

• 哈希对象保存的所有键值对的键和值的字符串长度均小于 64 字节
• 哈希对象保存的键值对数量小于 512 个

在压缩列表中，键和值紧挨着放，先插入的键值对放在前面：

不满足上述条件的时候，使用 hashtable 来编码，使用字典。比如上面的例子，假如使用了 hashtable 编码：

同时，如果原来时 ziplist 编码，但是对列表修改使得列表不再满足上面两个条件，此时会发生转换。并且转换是单向的，不能再逆着转换了。

2.1.4 集合对象

Unknown
1
2
redis> SADD numbers 1 3 5
(integer) 3

集合对象有 intset 和 hashtable 两种编码方式。

同时满足下面条件时，集合对象使用 intset 编码：

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过 512 个

不满足上述条件的时候，使用 hashtable 来编码。集合元素作为键，值为 NULL：

同时，如果原来时 intset 编码，但是对列表修改使得列表不再满足上面两个条件，此时会发生转换。并且转换是单向的，不能再逆着转换了。

2.1.5 有序集合对象

Redis 的有序集合相较于集合，每一个元素还额外带了一个分数值。有序集合可以做到集合的所有（或者说几乎所有）功能，同时还拥有下面的功能：

• 统计分数值在某个范围内的元素数量
• 返回排名在某个范围内的元素
• 返回某个元素的排名

集合对象有 ziplist 和 skiplist 两种编码方式。

同时满足下面条件时，集合对象使用 ziplist 编码：

• 有序集合保存的元素数量小于 128 个

• 有序集合保存的所有元素成员的长度均小于 64 字节

使用 ziplist 编码时，元素和其对应的分值紧挨在一块放，并且按分数值递增的顺序排列：

压缩列表本身不能存小数，所以分数值如果是小数的话会按字符串形式存。

不满足上述条件的时候，使用 skiplist 来编码。

使用 skiplist 编码时，有序集合需要同时维护一个跳表和一个字典。跳表是有序的，所以维护跳表可以让我们快速地做范围型的操作。但是仅靠跳表无法做到 $O(1)$ 查找元素的分数值。而字典可以做到这点，但字典是无序的，又无法独自做范围型的操作。

同时，如果原来是 ziplist 编码，但是对列表修改使得列表不再满足上面两个条件，此时会发生转换。并且转换是单向的，不能再逆着转换了。

2.2 引用计数

C 语言并不具备垃圾回收的功能。Redis 对象可能会同时被多个地方引用，此时为了使得对象能够被正确释放，Redis 就自己搓了个引用计数，在 redisObject 的 refcount 字段上面。

有了引用计数之后还能带来一个额外的特性：对象共享。Redis 在初始化服务器时，会创建一些表示小范围整数的字符串对象，比如创建从 0 到 9999 这个范围的所有整数值。当有键的值位于这个范围中时，Redis 会直接共享这些已经有的对象。这些小范围整数值会经常被用作键的值，因此共享他们是一个优化。

Redis 应该还有个类似 copy on write 的机制，使得被共享的对象在被修改时复制一份再修改。

2.3 空转时长

redisObject 中包含 lru 字段，该字段记录了对象最后一次被命令程序访问的时间。

OBJECT IDLETIME 命令可以打印出给定键的空转时长，这个空转时长就是将当前时间减去键的值对象的 lru 得到的。特别地，OBJECT IDLETIME 本身不会更新对象的 lru。