TECH OTAKUS SAVE THE WORLD

4.1 为什么不用 C 字符串？#

C 字符串以 \0 作为结尾，这会带来几个问题：

第一，获取字符串长度需要遍历，时间复杂度是 O(N)。

第二，字符串中间不能安全地存储 \0，否则会被误认为字符串结束。

第三，拼接字符串时容易出现缓冲区溢出，需要开发者自己处理内存分配。

Redis 作为数据库，需要频繁处理字符串、网络协议、命令参数和 key/value 数据，因此需要一个更安全、更高效的字符串结构。

4.2 SDS 的核心思想#

SDS 可以简单理解为：

1
struct sdshdr {
2
    int len;    // 已使用长度
3
    int free;   // 剩余可用空间
4
    char buf[]; // 实际数据
5
};

实际 Redis 中 SDS 会根据字符串长度使用不同 header 类型，以减少内存浪费，但核心思想差不多：在真正的数据 buf 前面记录长度、容量等元信息。

SDS 的优势主要有：

1. 获取长度是 O(1)

因为 SDS 直接保存了 len，不需要像 C 字符串那样遍历到 \0。

2. 二进制安全

SDS 根据 len 判断字符串长度，而不是依赖 \0，所以中间可以存任意字节。

3. 减少频繁内存分配

SDS 扩容时会预留一部分空间，后续追加内容时不一定每次都重新分配内存。

4. 兼容部分 C 字符串函数

SDS 的 buf 末尾仍然会保留 \0，所以在一些场景下可以兼容 C 字符串函数。

4.3 String 的三种常见编码#

Redis String 常见编码有：

• int
• embstr
• raw

如果字符串可以表示为整数，并且在 64 位有符号整数范围内，Redis 可能使用 int 编码，节省空间。

如果是比较短的字符串，Redis 可能使用 embstr 编码。embstr 会把 Redis 对象头和 SDS 连续分配在一块内存中，减少一次内存分配，也提升缓存局部性。

如果字符串比较长，Redis 会使用 raw 编码。此时 Redis 对象和 SDS 通常是分开分配的，更适合后续修改和扩容。

可以通过下面命令观察：

1
SET a 100
2
OBJECT ENCODING a
3

4
SET b hello
5
OBJECT ENCODING b
6

7
SET c "一个比较长的字符串..."
8
OBJECT ENCODING c

5.1 普通链表的问题#

普通双向链表的优点是头尾插入删除很快，时间复杂度是 O(1)。但它也有明显缺点：

• 每个节点都需要额外保存前驱、后继指针；
• 每个元素单独分配内存，内存碎片较多；
• 缓存局部性较差，遍历时可能频繁跳转到不同内存位置。

Redis 是内存数据库，内存占用非常关键。如果 List 中每个元素都用一个独立链表节点，会有不少额外开销。

5.2 listpack 是什么？#

listpack 是一种紧凑的连续内存结构，可以在一块连续内存中存储多个元素。

它和数组有点像，都是连续内存，但 listpack 的每个 entry 是变长编码的，可以存整数，也可以存字符串。它主要追求节省内存。

listpack 的优点：

• 元素紧凑存储，指针开销小；
• 缓存局部性较好；
• 适合小集合、小列表、小哈希、小有序集合。

缺点也很明显：

• 中间插入或删除可能需要移动内存；
• 查找某个位置通常需要顺序遍历；
• 数据太大时不适合作为唯一结构。

所以 listpack 适合“小而紧凑”的场景。

5.3 quicklist 是什么？#

quicklist 可以理解成“双向链表 + listpack”的组合。

它整体是一个双向链表，每个链表节点内部不是只存一个元素，而是存一个 listpack。也就是说：

1
quicklist
2
  |
3
  +-- node1 -> listpack[e1, e2, e3, ...]
4
  +-- node2 -> listpack[e4, e5, e6, ...]
5
  +-- node3 -> listpack[e7, e8, e9, ...]

这样做相当于在普通链表和连续内存之间做了折中：

• 和普通链表相比，quicklist 减少了节点数量，降低了指针开销；
• 和单个巨大 listpack 相比，quicklist 避免了大范围内存移动；
• 头尾操作仍然比较快；
• 遍历时也能利用 listpack 的连续内存优势。

所以 List 的底层结构可以概括为：小数据尽量紧凑，大数据用 quicklist 分块管理。

5.4 List 的使用建议#

List 适合：

• 简单队列：LPUSH + RPOP；
• 简单栈：LPUSH + LPOP；
• 最新消息列表：LPUSH + LTRIM；
• 阻塞队列：BLPOP、BRPOP。

但 List 不适合频繁按下标随机访问。比如 LINDEX key 100000 这类操作可能需要遍历，性能不如数组型结构。

6.1 小 Hash：listpack#

当 Hash 中字段数量较少，并且 field 和 value 都比较短时，Redis 会使用 listpack 编码。

listpack 中会按顺序存储 field 和 value：

1
[field1, value1, field2, value2, field3, value3]

这种方式非常节省内存，因为它不需要为每个 field-value 都维护哈希表节点和指针。

但问题是，查找某个 field 时需要顺序扫描。听起来似乎不快，但由于小 Hash 数据量很小，而且 listpack 连续内存的缓存局部性好，所以实际开销可以接受。

6.2 大 Hash：hashtable#

当 Hash 字段数量超过阈值，或者某个 field/value 太大时，Redis 会把它转换成 hashtable 编码。

hashtable 的优点是查询、插入、删除平均时间复杂度接近 O(1)，适合字段较多的 Hash。

可以简单理解为：

1
dict:
2
  field1 -> value1
3
  field2 -> value2
4
  field3 -> value3

Redis 的哈希表使用链式哈希解决冲突，并支持渐进式 rehash。所谓渐进式 rehash，就是在扩容时不一次性把所有数据迁移完，而是把迁移工作拆散到后续多次操作中逐步完成，避免一次性阻塞太久。

6.3 Hash 的使用建议#

Hash 很适合存储对象型数据，比如：

1
HSET product:1001 name keyboard price 199 stock 50

相比于把每个字段拆成多个 key：

1
SET product:1001:name keyboard
2
SET product:1001:price 199
3
SET product:1001:stock 50

使用 Hash 通常能减少 key 的数量，降低 Redis key 元数据开销，也更便于整体管理。

不过需要注意：如果一个 Hash 特别大，HGETALL 可能一次返回大量数据，影响 Redis 单线程执行时间。大 Hash 更推荐使用 HSCAN 分批遍历。

7.1 intset：整数集合的紧凑表示#

如果一个 Set 中的元素全都是整数，并且数量不大，Redis 可能使用 intset 编码。

intset 可以理解为一个有序整数数组。它会根据元素大小选择合适的整数宽度，比如 16 位、32 位、64 位。

当插入更大的整数时，intset 可能会升级编码。例如原本所有元素都能用 16 位表示，后来插入一个需要 32 位表示的整数，那么整个 intset 会升级到 32 位。

intset 的优点是非常省内存，适合小规模整数集合。

缺点是插入、删除、查找通常需要在数组中操作，数据大了以后不如 hashtable。

7.2 listpack：小规模普通集合#

在较新的 Redis 版本中，小规模 Set 也可以使用 listpack 编码。它适合元素数量少、元素长度较短的场景。

listpack 的目标依旧是节省内存。

7.3 hashtable：通用 Set 编码#

当集合规模变大，或者元素类型不适合紧凑编码时，Redis 会使用 hashtable。

Set 的 hashtable 可以简单理解为：

1
dict:
2
  member1 -> null
3
  member2 -> null
4
  member3 -> null

value 不重要，重要的是 key 是否存在。这样 SISMEMBER、SADD、SREM 等操作平均可以接近 O(1)。

7.4 Set 的使用建议#

Set 适合：

• 用户标签；
• 点赞用户集合；
• 抽奖去重；
• 共同关注、共同好友；
• 黑名单、白名单；
• UV 去重。

但要注意集合运算的成本。比如 SINTER、SUNION、SDIFF 在大集合上可能比较重，如果集合非常大，要注意慢查询和阻塞问题。

8.1 小 ZSet：listpack#

当 ZSet 元素数量较少，并且 member 较短时，Redis 可能使用 listpack 编码。

listpack 中通常会连续存储 member 和 score：

1
[member1, score1, member2, score2, member3, score3]

这种编码节省内存，但查找和插入需要顺序处理，适合小数据量。

8.2 大 ZSet：skiplist + dict#

当 ZSet 规模变大后，Redis 通常会使用 skiplist + dict 的组合。

为什么需要两个结构？

因为 ZSet 既需要根据 member 快速查 score，也需要根据 score 做排序和范围查询。

dict 负责：

1
member -> score

这样 ZSCORE member 可以快速查到分数。

skiplist 负责按照 score 维护有序结构，这样可以支持：

• 按排名查询；
• 按 score 范围查询；
• 获取前 N 名；
• 删除某个 score 范围内的元素。

8.3 skiplist 是什么？#

skiplist，跳表，是一种多层有序链表。

最底层包含所有元素，上层是部分元素的索引。查找时从最高层开始，如果当前节点的下一个节点还没超过目标，就继续向前；否则下降一层。通过这种多层索引，可以把查找复杂度降低到平均 O(log N)。

可以简单理解为：

1
Level 3:  1 -------------------- 9
2
Level 2:  1 -------- 5 --------- 9
3
Level 1:  1 --- 3 --- 5 --- 7 --- 9
4
Level 0:  1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9

相比平衡树，跳表实现更简单，范围遍历也比较自然。Redis 的 ZSet 需要大量范围查询，所以 skiplist 很适合这个场景。

8.4 为什么 ZSet 不只用 dict？#

如果只用 dict，可以很快通过 member 找到 score，但无法高效按 score 排序和范围查询。

8.5 为什么 ZSet 不只用 skiplist？#

如果只用 skiplist，按 score 范围查询很方便，但通过 member 查 score 不够直接。加上 dict 后，可以兼顾 member 查找和 score 排序。

所以 ZSet 的核心思路是：dict 管查找，skiplist 管有序。

14.1 Redis List 就是普通链表吗？#

不是。现代 Redis List 主要与 listpack、quicklist 有关。quicklist 是双向链表和 listpack 的组合，每个链表节点中存多个元素。

14.2 Hash 一定是哈希表吗？#

不一定。小 Hash 可能是 listpack。只有当数据量或元素大小超过阈值后，才会转成 hashtable。

14.3 ZSet 只用跳表实现吗？#

不准确。大 ZSet 通常是 skiplist 和 dict 的组合。skiplist 负责有序范围查询，dict 负责通过 member 快速查 score。

14.4 Bitmap 是单独的数据类型吗？#

从使用角度看可以把它当成一种数据结构，但底层本质上是 String 的位操作。

14.5 ziplist 现在还常用吗？#

在 Redis 早期版本中，ziplist 用得比较多，比如小 List、小 Hash、小 ZSet 都可能使用 ziplist。但 Redis 7 之后，很多地方已经使用 listpack 替代 ziplist。