1. 从对象到编码：Redis 的两层抽象

Redis 并不是"一种类型对应一种数据结构"，而是设计了两层抽象：

• 对外的类型（type）：string、list、hash、set、zset —— 用户看到的语义；
• 对内的编码（encoding）：SDS、listpack、quicklist、hashtable、intset、skiplist —— 实际的内存布局。

同一个类型在不同数据规模下会用不同编码，Redis 自动转换。这个设计的目的是：小数据用紧凑结构省内存 + CPU 缓存友好，大数据用高级结构保证时间复杂度。

用 OBJECT ENCODING 可以随时看到当前编码：

127.0.0.1:6379> SET k 123
127.0.0.1:6379> OBJECT ENCODING k
"int"
127.0.0.1:6379> SET k "hello"
127.0.0.1:6379> OBJECT ENCODING k
"embstr"
127.0.0.1:6379> SET k "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
127.0.0.1:6379> OBJECT ENCODING k
"raw"

1.1 redisObject 结构

所有 value 在 Redis 内部都被包在一个 redisObject（简称 robj）里：

typedef struct redisObject {
    unsigned type:4;        // 类型：OBJ_STRING/OBJ_LIST/OBJ_HASH/OBJ_SET/OBJ_ZSET/OBJ_STREAM
    unsigned encoding:4;    // 编码：OBJ_ENCODING_INT/EMBSTR/RAW/LISTPACK/HT/SKIPLIST/INTSET/QUICKLIST
    unsigned lru:24;        // LRU 时钟（LRU 模式）或 LFU 的计数+时间（LFU 模式）
    int refcount;           // 引用计数，共享对象靠它
    void *ptr;              // 指向实际的数据结构
} robj;

这个结构本身占 16 字节（4+4+24 位 = 4 字节 + 4 字节 refcount + 8 字节指针）。所以每个 value 至少有 16 字节的固定开销，这是"key 数量越多越浪费内存"的原因之一。

几个关键字段：

• lru 字段的双重用途：maxmemory-policy 是 LRU 系列时，它存最后访问的时间戳（秒级精度的 24 位时钟）；是 LFU 系列时，高 16 位存"上次递减时间"，低 8 位存"对数访问计数"。详见第 6 篇；
• refcount 与共享对象：Redis 启动时会预创建 0~9999 的整数对象（shared.integers），所有用到这些小整数的地方共享同一个 robj，refcount 累加。所以：

127.0.0.1:6379> SET a 100
127.0.0.1:6379> OBJECT REFCOUNT a
(integer) 2147483647    # INT_MAX，表示共享对象（永不释放）
127.0.0.1:6379> SET b 99999
127.0.0.1:6379> OBJECT REFCOUNT b
(integer) 1             # 超出 0~9999，独立对象

注意：开启 maxmemory 且策略是 LRU/LFU 时，共享整数对象会被禁用，因为共享对象没法记录独立的访问时间。

1.2 编码总表

先给出完整对应关系，后面逐个展开：

对应的配置项：

hash-max-listpack-entries 128
hash-max-listpack-value 64
list-max-listpack-size 128
set-max-intset-entries 512
set-max-listpack-entries 128
set-max-listpack-value 64
zset-max-listpack-entries 128
zset-max-listpack-value 64

核心规则：编码转换是单向的、不可逆的。 一旦因为超过阈值升级成了 hashtable/skiplist，即使后来元素删回到阈值以下，也不会退回 listpack。原因是频繁来回转换的开销远大于省下的那点内存，而且转换需要 O(N) 重建整个结构。

127.0.0.1:6379> RPUSH mylist a b c
127.0.0.1:6379> OBJECT ENCODING mylist
"listpack"
127.0.0.1:6379> RPUSH mylist <插入 200 个元素>
127.0.0.1:6379> OBJECT ENCODING mylist
"quicklist"
127.0.0.1:6379> DEL ... # 删回 3 个元素
127.0.0.1:6379> OBJECT ENCODING mylist
"quicklist"             # 不会退回 listpack

2. SDS 简单动态字符串

Redis 用 C 写的，但没有直接用 C 的字符串（char * + \0 结尾），而是自己实现了 SDS（Simple Dynamic String）。

2.1 结构定义

Redis 3.2 之后 SDS 有 5 种变体，按字符串长度选最省的那个：

struct sdshdr8 {
    uint8_t len;          // 已使用长度（不含结尾的 \0）
    uint8_t alloc;        // 分配的容量（不含 header 和结尾 \0）
    unsigned char flags;  // 低 3 位表示类型：SDS_TYPE_5/8/16/32/64
    char buf[];           // 实际字节数组，柔性数组
};

3.2 之前只有一种 header（len 和 free 都是 unsigned int，固定 8 字节），存一个 3 字节的短字符串要浪费 8 字节头。改成 5 种变体后短字符串的头只要 3 字节，这是 3.2 版本一次很显著的内存优化。

2.2 SDS 相比 C 字符串的五大优势

（1）O(1) 获取长度

C 字符串要 strlen 遍历到 \0，O(N)。SDS 直接读 len 字段，O(1)。所以 Redis 的 STRLEN 是 O(1)，而如果用 C 字符串，一个 100MB 的 value 每次 STRLEN 都要扫 100MB。

（2）杜绝缓冲区溢出

C 的 strcat 不检查目标空间是否足够，溢出就覆盖相邻内存。SDS 的 sdscat 会先检查 alloc - len 是否够，不够就自动扩容，从 API 层面消除了溢出。

（3）减少内存重分配次数

C 字符串每次修改长度都必须 realloc。SDS 用两个策略避免：

• 空间预分配：扩容时不只分配刚好够的空间。如果扩容后 len < 1MB，就多分配同样大小的空闲空间（alloc = 2 * len）；如果 len >= 1MB，则多分配 1MB。这让连续 APPEND 的分配次数从 N 次降到 O(logN) 级别；
• 惰性空间释放：缩短字符串时只改 len，不立即 realloc 释放，保留 alloc 供后续增长复用。真要释放可以调 sdsRemoveFreeSpace。

127.0.0.1:6379> SET k "hello"        # len=5
127.0.0.1:6379> APPEND k " world"    # len=11, alloc 扩到 22（预分配）
(integer) 11
127.0.0.1:6379> APPEND k "!"         # len=12, 直接用预留空间，无需 realloc

（4）二进制安全

C 字符串以 \0 判断结尾，所以不能存包含 \0 的数据（比如图片、protobuf 序列化结果）。SDS 用 len 界定长度，buf 里可以有任何字节，因此 Redis 能存任意二进制数据。

（5）兼容部分 C 字符串函数

SDS 依然在 buf 末尾放一个 \0（不计入 len），所以可以直接把 buf 传给 printf、strcmp 这类只读的 C 函数，复用现成的库。

2.3 string 的三种编码

int 编码：值能被解析成 long（64 位有符号整数）时，robj.ptr 直接存这个整数（指针位置当整数用），完全不用 SDS，省掉一次分配。

SET k 12345
OBJECT ENCODING k    # int

注意：SET k "12345678901234567890123"（超过 long 范围）会退化成 embstr。另外 SET k 007 也是 embstr，因为 007 转成 long 再转回字符串会变成 7，不能无损还原。

embstr 编码（embedded string，长度 <= 44）：robj 和 SDS 在一次 malloc 中连续分配，robj.ptr 指向紧跟在 robj 后面的 SDS。

好处：

1. 内存分配/释放各只要 1 次（raw 需要 2 次）；
2. robj 和字符串数据在同一段连续内存里，CPU 缓存局部性好。

raw 编码（长度 > 44）：robj 和 SDS 分开两次分配，robj.ptr 指向独立的 SDS。

2.4 为什么 embstr 的阈值是 44 字节

这是一道经典面试题。推导过程：

jemalloc 的内存分配是分档的（8/16/32/48/64/...字节），
Redis 希望 embstr 对象能装进一个 64 字节的分配单元：

64 字节 = robj (16 字节) + sdshdr8 (3 字节) + buf 内容 + 结尾 \0 (1 字节)
       = 16 + 3 + N + 1
=> N = 64 - 20 = 44

所以 44 字节是"能让 robj + SDS 头 + 内容 + 结尾符正好塞进 64 字节内存块"的最大长度。

历史小知识：Redis 3.2 之前这个阈值是 39，因为那时 SDS 只有一种 header，占 8 字节：64 - 16 - 8 - 1 = 39。3.2 引入 sdshdr8（3 字节）后变成 44。面试时能说出这个演变是加分项。

2.5 embstr 是"只读"的

embstr 一旦被修改就会转成 raw，且不可逆：

127.0.0.1:6379> SET k "hello"
127.0.0.1:6379> OBJECT ENCODING k
"embstr"
127.0.0.1:6379> APPEND k "!"
127.0.0.1:6379> OBJECT ENCODING k
"raw"                      # 变成 raw 了，虽然只有 6 个字节

127.0.0.1:6379> SET n 100
127.0.0.1:6379> OBJECT ENCODING n
"int"
127.0.0.1:6379> APPEND n "1"
127.0.0.1:6379> OBJECT ENCODING n
"raw"                      # int 被修改后也变 raw

原因：Redis 没有为 embstr 实现原地修改的函数（因为 embstr 是连续分配的，扩容要重新分配整块，还得更新所有指向它的指针，不如直接转 raw 简单）。所以只要碰到 APPEND、SETRANGE、GETSET 这类修改操作，一律先转 raw。

实践含义：如果一个短 string 会被频繁 APPEND，它其实是 raw 编码，内存比你想的多（多一次分配 + 预分配的空闲空间）。

3. intset 整数集合

当 set 里**全是整数且元素个数不超过 set-max-intset-entries（默认 512）**时，用 intset 编码。

3.1 结构

typedef struct intset {
    uint32_t encoding;   // INTSET_ENC_INT16 / INT32 / INT64
    uint32_t length;     // 元素个数
    int8_t contents[];   // 实际是 int16_t/int32_t/int64_t 数组，按 encoding 解释
} intset;

三个关键设计：

1. 元素在 contents 里从小到大有序排列，所以查找用二分查找，SISMEMBER 是 O(logN)（不是 O(1)！）；
2. 连续内存、无指针、无 robj 包装，一个 int16 元素只占 2 字节，比 hashtable 里每个元素要 robj + dictEntry 几十字节省得多；
3. encoding 是整个集合共用的，按当前最大元素所需的宽度决定。

3.2 升级

当插入一个超出当前 encoding 范围的整数时，intset 会升级：

127.0.0.1:6379> SADD s 1 2 3          # 都在 int16 范围
# encoding = INTSET_ENC_INT16, contents 是 int16_t[3]，占 6 字节

127.0.0.1:6379> SADD s 65536          # 超出 int16 范围（-32768~32767）
# 升级为 INTSET_ENC_INT32：
# 1. 按新编码重新分配空间（4 字节 × 4 = 16 字节）
# 2. 从后往前逐个搬移旧元素（从后往前是为了避免覆盖未搬的数据）
# 3. 把新元素放到头部或尾部（因为触发升级的元素必然是当前最大或最小）

升级的复杂度是 O(N)。intset 只升级不降级——即使把那个大整数删掉，编码仍是 INT32。

3.3 转换为其他编码

两种情况会让 set 离开 intset：

1. 插入了非整数元素：立即转成 listpack（7.2+，如果元素数和长度还在小阈值内）或 hashtable；
2. 元素数超过 set-max-intset-entries（512）：7.2 之前直接转 hashtable；7.2+ 会先看是否满足 listpack 阈值。

127.0.0.1:6379> SADD s 1 2 3
127.0.0.1:6379> OBJECT ENCODING s
"intset"
127.0.0.1:6379> SADD s "abc"
127.0.0.1:6379> OBJECT ENCODING s
"listpack"                          # 7.2+；旧版本会直接是 hashtable
127.0.0.1:6379> SADD s <加到 200 个元素>
127.0.0.1:6379> OBJECT ENCODING s
"hashtable"

注意一个反直觉的点：set-max-intset-entries 是 512，而 set-max-listpack-entries 是 128。所以一个有 300 个整数的 set 是 intset（省内存），但如果里面有一个非整数，就会因为超过 128 而直接变成 hashtable（内存暴涨）。

4. ziplist 压缩列表

ziplist 是 Redis 早期为"小集合"设计的紧凑结构，7.0 后逐步被 listpack 取代，但理解它对理解 listpack 的动机很关键。

4.1 内存布局

ziplist 是一整块连续内存，没有任何指针：

+---------+--------+---------+--------+--------+-----+--------+-------+
| zlbytes | zltail | zllen   | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+---------+--------+--------+-----+--------+-------+
   4字节     4字节     2字节                                    1字节(0xFF)

• zlbytes：整个 ziplist 占用的字节数（用于 realloc）；
• zltail：最后一个 entry 距起始位置的偏移量 —— 这让尾部操作 O(1)（RPUSH/RPOP 不用遍历）；
• zllen：entry 数量。只有 2 字节，最大表示 65535；超过时这个字段固定为 65535，真实数量必须遍历才知道（所以超过 65535 个元素时 LLEN 会变成 O(N)）；
• zlend：固定的 0xFF 结束标记。

每个 entry 的结构：

+------------------+----------+---------+
| prevlen          | encoding | content |
+------------------+----------+---------+
  前一个entry的长度   本entry的
  (1或5字节)         编码与长度

• prevlen：前一个 entry 的字节长度。这是 ziplist 能从后往前遍历的关键（ZREVRANGE、RPOP 靠它）。前一个 entry 长度 < 254 时用 1 字节，>= 254 时用 5 字节（第 1 字节固定 0xFE，后 4 字节存长度）；
• encoding：标识 content 是整数还是字符串，以及具体长度。整数有 6 种编码（int16/int32/int64/24bit/8bit/4bit 立即数），字符串按长度分 1/2/5 字节的编码头。

ziplist 极致省内存的原因：没有指针、没有 robj、按需选择最小的整数编码。一个存 1 的 entry 只要 2 字节（1 字节 prevlen + 1 字节 encoding 兼 content）。

4.2 连锁更新（cascade update）—— ziplist 的致命缺陷

这是 ziplist 最经典的问题，也是面试高频题。

设想一个 ziplist，里面每个 entry 的长度都在 250~253 字节之间（都小于 254，所以每个 entry 的 prevlen 都只用 1 字节）：

[e1: 253字节] [e2: prevlen=1字节, 253字节] [e3: prevlen=1字节, 253字节] ...

现在在头部插入一个 长度 >= 254 字节的新 entry：

1. e1 的 prevlen 必须从 1 字节扩展到 5 字节 → e1 自己的总长度增加了 4 字节；
2. e1 原来是 253 字节，现在变成 257 字节，超过了 254 → e2 的 prevlen 也必须从 1 字节扩到 5 字节；
3. e2 变长 4 字节又超过 254 → e3 也要扩容……
4. 连锁反应一直传递下去，整个 ziplist 都要重新分配和搬移内存。

结果：本该是 O(1) 的头部插入变成了 O(N²)（每次扩容都要 realloc + memmove）。删除操作同理也可能触发连锁更新（删掉一个大 entry 后，后面 entry 的 prevlen 可能需要缩小）。

发生概率极低（需要连续多个 entry 长度精确落在 250~253 这个窄区间），所以 Redis 长期容忍了它。但它是个不可预测的延迟毛刺来源——一旦触发，单线程会被卡住，且完全没法预警。

除此之外 ziplist 还有：

• zllen 只有 2 字节，超过 65535 个元素后 LLEN 退化为 O(N)；
• prevlen 设计本身就是复杂度来源，每个 entry 都要维护前驱长度。

4.3 listpack —— ziplist 的替代品

listpack 在 5.0 为 Stream 引入，7.0 全面替换 ziplist 成为 hash/zset/list 的小编码。

核心改动：彻底去掉 prevlen，改为在每个 entry 的末尾存"本 entry 的总长度"。

+---------+---------+--------+--------+-----+--------+-------+
| totbytes| numele  | entry1 | entry2 | ... | entryN | lpend |
+---------+---------+--------+--------+-----+--------+-------+
   4字节     2字节                                    1字节(0xFF)

每个 entry:
+----------------+---------+------------------+
| encoding+len   | content | backlen          |
+----------------+---------+------------------+
                            本entry总长度(1~5字节)

关键点：

• backlen 存的是"自己的长度"而不是"前一个的长度"。要向前遍历时，从当前 entry 起始位置往前读 backlen（backlen 用一种特殊的变长编码，从后往前读也能正确解析），就知道前一个 entry 有多长，从而定位到它的起点；
• 修改某个 entry 只影响它自己，绝不会影响其他 entry 的元数据 → 彻底消除连锁更新；
• numele 依然是 2 字节（超过 65535 时同样需要遍历），但因为 listpack 只用于小集合（阈值 128），实际不会触及。

7.0 的改名：配置项从 hash-max-ziplist-entries 改成 hash-max-listpack-entries，但旧名字仍然兼容（Redis 会自动映射）。OBJECT ENCODING 的返回值从 ziplist 变成 listpack，升级时如果有监控/代码依赖这个字符串要注意改。

5. quicklist 快速列表

5.1 为什么需要 quicklist

3.2 之前，list 的编码是：小的用 ziplist，大的用 linkedlist（标准双向链表）。两者各有致命缺点：

• ziplist：连续内存，插入删除要 memmove 甚至 realloc 整块，元素多了性能急剧下降，还有连锁更新风险；
• linkedlist：每个节点是独立的 listNode（prev 8 字节 + next 8 字节 + value 指针 8 字节 = 24 字节），加上 value 自己的 robj（16 字节）和 SDS 头，存一个 3 字节的字符串要花掉 50+ 字节。而且节点内存分散，CPU 缓存命中率极差，还容易产生内存碎片。

3.2 引入的 quicklist 是两者的折中：一个双向链表，但每个节点内部是一个 ziplist（7.0+ 是 listpack）。

   quicklist
+--------+--------+-------+--------+
| head   | tail   | count | len    |
+--------+--------+-------+--------+
     |
     v
+------------+       +------------+       +------------+
| quicklist  | <---> | quicklist  | <---> | quicklist  |
| Node       |       | Node       |       | Node       |
| [listpack] |       | [listpack] |       | [listpack] |
|  a,b,c,d   |       |  e,f,g,h   |       |  i,j,k     |
+------------+       +------------+       +------------+

这样既保留了链表两端 O(1) 操作的优势，又通过"节点内紧凑存储"大幅减少了指针开销和内存碎片。

5.2 结构

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        // 所有节点里的元素总数（LLEN 靠它，O(1)）
    unsigned long len;          // 节点个数
    signed int fill : 16;       // 每个节点的填充上限（list-max-listpack-size）
    unsigned int compress : 16; // 两端各有多少个节点不压缩
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;       // 指向 listpack（或压缩后的 lzf 数据）
    size_t sz;                  // listpack 的字节数
    unsigned int count : 16;    // 该节点内的元素数
    unsigned int encoding : 2;  // RAW=1（未压缩） / LZF=2（已压缩）
    unsigned int container : 2; // PLAIN=1（单个大元素直接存） / PACKED=2（listpack）
    unsigned int recompress : 1;// 是否是临时解压的（访问后要重新压缩）
    ...
} quicklistNode;

5.3 关键配置：list-max-listpack-size

这个配置（旧名 list-max-ziplist-size）控制单个节点的大小，有两种语义：

• 正数：表示每个节点最多放多少个元素。如 128 表示每节点最多 128 个元素；
• 负数：表示每个节点的字节上限，有 5 档：

默认 -2（8KB）是官方推荐值：单节点太小则节点数多、指针开销大；太大则节点内 listpack 的插入删除 memmove 成本高，还容易超过 CPU 缓存。

特殊情况：PLAIN 节点。如果单个元素本身就超过节点上限（比如 RPUSH k <一个 1MB 的字符串>），Redis 会创建一个 container = PLAIN 的节点，直接把这个大元素单独存，不套 listpack。

5.4 中间节点压缩（compress）

list-compress-depth 配置（对应 quicklist.compress）控制用 LZF 算法压缩中间节点：

设计动机：list 最常见的访问模式是在两端操作（LPUSH/RPUSH/LPOP/RPOP、LRANGE 0 N 取最新几条），中间的数据很少被访问。把中间节点压缩起来能省大量内存（LZF 对文本类数据通常能压到 30%~50%）。

代价是：访问中间节点时要先解压（recompress 标志用于标记"临时解压过，用完要压回去"），所以 LINDEX 到中间位置、LINSERT 等操作会变慢。

生产建议：如果 list 是纯队列用途（只在两端操作）且数据量大，可以设 list-compress-depth 1 省内存；如果有随机访问需求就保持 0。

5.5 7.0+ 的变化

7.0 之后 list 的编码判定变成两层：

1. 元素数 <= 128 且每个元素 <= 64 字节 → 直接用 listpack（不套 quicklist，连链表头都省了）；
2. 超过阈值 → 转成 quicklist，且节点内部用 listpack 而不是 ziplist。

127.0.0.1:6379> RPUSH l a b c
127.0.0.1:6379> OBJECT ENCODING l
"listpack"
127.0.0.1:6379> RPUSH l <加到 200 个>
127.0.0.1:6379> OBJECT ENCODING l
"quicklist"

7.2 进一步优化了 quicklist 与 listpack 之间的转换逻辑，元素删减后在某些条件下可以合并节点。

6. dict 字典（哈希表）

dict 是 Redis 最核心的结构：整个数据库本身就是一个 dict（key → value 的映射），hash 和 set 的大编码也是 dict，zset 内部也有一个 dict。

6.1 结构

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                       // 用 union 省内存
    struct dictEntry *next;    // 链地址法解决冲突
} dictEntry;

typedef struct dict {
    dictType *type;            // 类型特定函数（hash函数、key比较、销毁等）
    dictEntry **ht_table[2];   // 两个哈希表！rehash 时用
    unsigned long ht_used[2];  // 各表已有的元素数
    long rehashidx;            // rehash 进度：-1 表示没在 rehash
    int16_t pauserehash;       // >0 表示 rehash 被暂停（有迭代器在遍历时）
} dict;

最关键的设计是 ht_table[2]——两个哈希表。平时只用 ht_table[0]，rehash 时才启用 ht_table[1]。

• 冲突解决用链地址法（拉链）：冲突的 entry 挂成单链表。新元素插入链表头部（O(1)，不用遍历到尾）；
• 哈希函数用 SipHash（4.0+，之前是 MurmurHash2）。换成 SipHash 是为了防御哈希碰撞攻击（Hash-DoS）：攻击者精心构造大量哈希到同一个桶的 key，让查找退化成 O(N)。SipHash 带随机密钥（每次启动随机生成的 hash0/seed），攻击者无法预测哈希值。

6.2 渐进式 rehash（核心考点）

哈希表元素变多后必须扩容（否则链表越来越长、查找退化）。但 Redis 是单线程的，如果一次性把几千万个 key 从旧表搬到新表，会阻塞几秒钟——完全不可接受。

所以 Redis 用渐进式 rehash（incremental rehashing），把搬迁摊到后续的每次操作里。

触发条件

先定义负载因子：load_factor = ht_used[0] / size(ht_table[0])

扩容（_dictExpandIfNeeded）：

1. load_factor >= 1 且当前没有子进程在做 RDB/AOF 重写 → 扩容到"第一个 >= used*2 的 2 的幂"；
2. load_factor >= dict_force_resize_ratio（默认 5）→ 无论是否有子进程都强制扩容（因为链表太长了，性能损失比 COW 代价更严重）。

为什么要看"是否有子进程"？因为 rehash 要分配新的大数组并写入，会触发大量写时复制（COW），让 fork 出来的子进程内存暴涨。所以有子进程时，Redis 会尽量推迟扩容（把阈值从 1 提到 5）。

缩容（htNeedsResize，由 serverCron 定期检查）：

load_factor < 0.1（使用率低于 10%）时缩容到"第一个 >= used 的 2 的幂"。缩容避免了"曾经存了 1 亿 key、删到只剩 100 个，但哈希表数组还占着 1 亿个指针（800MB）“的浪费。

7.0+ 还增加了 dict-resizing 配置（可用 DEBUG SET-ACTIVE-EXPIRE 等调试命令控制），在特殊场景可以临时禁止 resize。

rehash 的过程

1. 为 ht_table[1] 分配新空间（大小是目标容量）
2. 把 rehashidx 设为 0，标志"开始 rehash"
3. 之后每次对 dict 的增删改查操作，除了完成本职工作，还会顺带
   把 ht_table[0] 的第 rehashidx 个桶上的所有 entry 重新哈希到 ht_table[1]，
   然后 rehashidx++
4. 同时 serverCron 每 100ms 会调用 dictRehashMilliseconds，
   用最多 1ms 的时间批量搬迁（后台推进）
5. 全部搬完后：释放 ht_table[0]，把 ht_table[1] 变成 ht_table[0]，
   rehashidx 置为 -1

关键细节（面试爱追问）：

• _dictRehashStep 每次只搬一个桶，但如果连续遇到空桶，最多访问 10 * n 个空桶就退出，避免大量空桶导致单次操作耗时不可控；
• rehash 期间的读操作要查两张表：先在 ht_table[0] 找，没找到再去 ht_table[1] 找；
• rehash 期间的新增操作只写 ht_table[1]，保证 ht_table[0] 的元素只减不增，rehash 一定能结束；
• 删除、修改也要两张表都处理；
• 有迭代器时暂停 rehash（pauserehash）：安全迭代器存在期间不能 rehash，否则遍历会重复或漏掉元素。这也是为什么 HSCAN/SCAN 用的是特殊的反向二进制迭代算法，能在 rehash 过程中保证"始终存在的元素一定被返回”。

SCAN 为什么能容忍 rehash

补充一个高阶知识点：SCAN 的游标不是简单的"第几个桶"，而是用了 reverse binary iteration（高位进位加法）。

游标的二进制位从高位开始递增（如 000 → 100 → 010 → 110 → 001 → …），这样设计的性质是：

• 表扩容时，原来在桶 i 的元素会分散到新表的 i 和 i + oldsize，而这两个桶在反向二进制序里是相邻访问的，不会漏；
• 表缩容时，原来两个桶合并成一个，可能导致重复返回（这就是 SCAN 不保证不重复的根本原因）。

所以 SCAN 的保证是"完整性有、唯一性无"。

6.3 hash 的 hashtable 编码内存开销

理解了 dict 结构就明白为什么"大 hash 比小 hash 费内存得多"：

一个 hashtable 编码的 hash，每个字段要花：

• dictEntry：24 字节（key 指针 8 + union 8 + next 指针 8），jemalloc 实际分配 32 字节；
• field 的 SDS：header 3 字节 + 内容 + \0；
• value 的 robj：16 字节；
• value 的 SDS：header + 内容 + \0；
• 哈希表数组里的指针：8 字节（还要摊上负载因子导致的空槽）。

合计每个字段固定开销约 60~90 字节。而 listpack 编码下，一个字段只要"encoding + 内容 + backlen"，短字符串大概 5~10 字节。

这就是为什么第 2 篇提到的分桶技巧能省 5~10 倍内存：把 100 万个字段的大 hash 拆成 1 万个各含 100 字段的小 hash，让每个都保持 listpack 编码。

7. skiplist 跳跃表

zset 元素多时用 skiplist + dict 的组合编码。

7.1 结构

typedef struct zskiplistNode {
    sds ele;                              // 成员
    double score;                         // 分数
    struct zskiplistNode *backward;        // 后退指针（只有一个，用于倒序遍历）
    struct zskiplistLevel {
        struct zskiplistNode *forward;     // 前进指针
        unsigned long span;                // 跨度：到下个节点跳过了多少个节点
    } level[];                             // 柔性数组，层数随机
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;      // 节点数（不含 header）
    int level;                 // 当前最大层数
} zskiplist;

typedef struct zset {
    dict *dict;          // member -> score 的映射，用于 O(1) 查 score
    zskiplist *zsl;      // 按 score 排序，用于范围查询
} zset;

为什么需要 dict 和 skiplist 两个结构？

• ZSCORE member 要 O(1) → 靠 dict；
• ZRANGE/ZRANGEBYSCORE/ZRANK 要按 score 有序访问 → 靠 skiplist。

两个结构通过指针共享同一份 member 的 SDS 和 score（不是各存一份），所以不会双倍浪费内存。

7.2 跳表原理

跳表本质是"给有序链表加多级索引"：

level 3:  header ------------------------------------> tail
level 2:  header --------> [c] ---------------------> tail
level 1:  header --> [b]-> [c] --------> [e] -------> tail
level 0:  header --> [b]-> [c] -> [d] -> [e] -> [f] -> tail

查找 [e]：从最高层开始，forward 指针指向的节点 score 小于目标就往右走，否则下降一层。这样跳过了大量节点，平均复杂度 O(logN)。

层数是随机决定的（zslRandomLevel）：

#define ZSKIPLIST_P 0.25          // 每层上升的概率
#define ZSKIPLIST_MAXLEVEL 32     // 最大层数

int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

即：每个新节点至少 1 层，有 25% 概率加一层，再有 25% 概率再加一层……所以：

• 层数为 1 的概率 75%，为 2 的概率 18.75%，为 3 的概率约 4.7%……
• 平均层数 = 1/(1-p) = 1/0.75 ≈ 1.33 层，所以平均每个节点只有 1.33 个 forward 指针，内存很省；
• 最大 32 层，理论上能支撑 4^32 个元素（远超实际需要）。

用随机层数而不是严格维护"每 2 个节点提升一个"，是跳表实现简单的关键——插入删除只要改几个指针，不需要任何再平衡操作。

7.3 span 与 ZRANK

span（跨度）字段是 Redis 对标准跳表的重要增强：它记录"这个 forward 指针跳过了多少个节点"。

有了 span，ZRANK（求排名）就能在 O(logN) 完成：查找目标节点的路径上，把经过的所有 span 累加，就是它的排名。

level 1:  header --span=2--> [c] --span=2--> [e]
                                          排名 = 2 + 2 = 4

没有 span 的话，求排名只能从头遍历数节点，O(N)。同理 ZRANGE key 0 9（按排名取区间）也靠 span 快速定位起点。

7.4 为什么用跳表不用红黑树 / B+ 树 / 平衡二叉树

这是最高频的数据结构面试题之一。antirez 本人在邮件列表里给过三点理由：

（1）范围查询更自然、更高效

跳表最底层就是一个有序双向链表。ZRANGEBYSCORE 60 100 只需：O(logN) 定位到起点，然后顺着 level[0] 的 forward 指针一路走到 100 为止。代码就是个 while 循环。

红黑树做范围查询要中序遍历，需要维护栈或者用线索化，实现复杂、缓存局部性也更差。

（2）实现和维护复杂度低得多

跳表插入：随机个层数，改几个指针，完事。删除：改几个指针。没有任何再平衡逻辑。

红黑树插入删除要处理旋转（左旋/右旋）和重新着色，有十几种 case，代码量是跳表的好几倍，出 bug 的概率也高得多。对于一个要长期维护的开源项目，这个理由的权重非常高。

（3）内存可调、缓存友好

跳表可以通过调整 ZSKIPLIST_P 参数在"内存占用"和"查询速度"之间自由权衡。Redis 选 p=0.25（而不是教科书常见的 0.5），让平均指针数从 2 降到 1.33，为了省内存牺牲了一点查询速度——这正是内存数据库该做的取舍。

红黑树每个节点固定要 2 个子指针 + 1 个父指针 + 颜色位，没有调节空间。

（4）为什么不用 B+ 树？

B+ 树是为磁盘设计的：一个节点的大小对齐磁盘页（4KB/16KB），目的是让一次磁盘 IO 读到尽可能多的索引信息，把树高压到 3~4 层，从而把 IO 次数降到最少。

Redis 是纯内存数据库，没有磁盘 IO 这个瓶颈，用 B+ 树白白增加了节点分裂/合并的复杂度，收益为零。（对比：MySQL InnoDB 用 B+ 树是因为数据在磁盘上。）

（5）为什么不用普通平衡二叉树（AVL）？

AVL 对平衡要求更严格（左右子树高度差 <= 1），插入删除时旋转次数比红黑树还多，写性能更差。而 zset 的写操作（ZADD/ZINCRBY）非常频繁（想想排行榜每次加分）。

7.5 skiplist 与 listpack 的转换

127.0.0.1:6379> ZADD z 1 a 2 b
127.0.0.1:6379> OBJECT ENCODING z
"listpack"                          # 元素少
127.0.0.1:6379> ZADD z <加到 200 个成员>
127.0.0.1:6379> OBJECT ENCODING z
"skiplist"

在 listpack 编码下，zset 的 member 和 score 成对连续存放（member1, score1, member2, score2, ...），按 score 从小到大排列。此时所有操作都是 O(N) 遍历，但因为 N <= 128 且内存连续（CPU 缓存友好），实际比 skiplist 更快，同时内存少几倍。

8. 编码转换实践与内存优化

8.1 亲手验证所有编码转换

# ---------- string ----------
SET s1 10086          ; OBJECT ENCODING s1    # int
SET s2 "hello redis"  ; OBJECT ENCODING s2    # embstr（11 字节 <= 44）
SET s3 "<45个字符>"    ; OBJECT ENCODING s3    # raw
APPEND s2 "!"         ; OBJECT ENCODING s2    # raw（修改后必转）
SET s4 "007"          ; OBJECT ENCODING s4    # embstr（不能无损转 long）

# ---------- list ----------
RPUSH l1 a b c                    ; OBJECT ENCODING l1   # listpack
RPUSH l2 "<65个字符的长串>"          ; OBJECT ENCODING l2   # quicklist（单元素超 64）
for i in {1..200}: RPUSH l3 $i    ; OBJECT ENCODING l3   # quicklist（超 128 个）

# ---------- hash ----------
HSET h1 f v                       ; OBJECT ENCODING h1   # listpack
HSET h2 f "<65个字符>"              ; OBJECT ENCODING h2   # hashtable
for i in {1..200}: HSET h3 f$i v  ; OBJECT ENCODING h3   # hashtable

# ---------- set ----------
SADD st1 1 2 3                    ; OBJECT ENCODING st1  # intset
SADD st1 abc                      ; OBJECT ENCODING st1  # listpack（7.2+）
SADD st2 a b c                    ; OBJECT ENCODING st2  # listpack
for i in {1..600}: SADD st3 $i    ; OBJECT ENCODING st3  # hashtable（整数超 512）
SADD st4 "<65个字符>"               ; OBJECT ENCODING st4  # hashtable

# ---------- zset ----------
ZADD z1 1 a                       ; OBJECT ENCODING z1   # listpack
ZADD z2 1 "<65个字符>"              ; OBJECT ENCODING z2   # skiplist
for i in {1..200}: ZADD z3 $i m$i ; OBJECT ENCODING z3   # skiplist

8.2 实测内存差异

# 1000 个字段的 hash，两种编码的内存对比

# 情况 A：保持 listpack（先把阈值调大）
CONFIG SET hash-max-listpack-entries 1000
for i in {1..1000}: HSET h_lp f$i v$i
MEMORY USAGE h_lp          # 约 20~25 KB

# 情况 B：强制 hashtable
CONFIG SET hash-max-listpack-entries 0
for i in {1..1000}: HSET h_ht f$i v$i
MEMORY USAGE h_ht          # 约 90~110 KB

# 差 4~5 倍

但注意：listpack 的增删改是 O(N)（要 memmove），字段多了以后 CPU 开销急剧上升。所以不能无脑把阈值调到很大。

8.3 阈值调优的权衡

经验建议：

1. 默认值（128/64）适用于大多数场景，不要随便改；
2. 如果你的 hash/zset 通常在 200~500 之间，且读多写少，可以把阈值调到 512，能显著省内存；
3. 绝不要调到 1000 以上——O(N) 的常数会让操作耗时进入毫秒级，单线程被拖死；
4. 更好的做法是从数据模型上分桶（把大 hash 拆成多个小 hash），而不是调阈值。

8.4 内存优化清单

# 1. 用 hash 代替多个 string key（省掉每个 key 的 robj + dictEntry + SDS 开销）
# 差：SET user:1001:name tom / SET user:1001:age 20
# 好：HSET user:1001 name tom age 20

# 2. 大 hash 分桶，保持 listpack 编码
HSET bucket:$(id/1000) $(id%1000) value

# 3. key 名尽量短（但要可读）—— key 也是 SDS，也占内存
# 差：user:information:detail:1001
# 好：u:1001

# 4. 整数尽量用整数存（走 int 编码 + 共享对象）
SET count 100        # int 编码，且 0~9999 是共享对象

# 5. 布尔状态用 Bitmap
SETBIT active:20260729 1001 1

# 6. 海量基数统计用 HyperLogLog

# 7. 用 Bitfield 打包小整数

# 8. 开启压缩（对大 list）
CONFIG SET list-compress-depth 1

# 9. 检查工具
MEMORY USAGE key           # 单个 key 的内存
MEMORY DOCTOR              # 内存诊断建议
DEBUG OBJECT key           # 查看 serializedlength、编码、ql_nodes 等
redis-cli --bigkeys        # 扫描大 key
redis-cli --memkeys        # 按内存排序扫描

DEBUG OBJECT 的输出能看到 quicklist 的内部细节：

127.0.0.1:6379> DEBUG OBJECT mylist
Value at:0x7f... refcount:1 encoding:quicklist serializedlength:1234
ql_nodes:5 ql_avg_node:40.00 ql_ziplist_max:8192 ql_compressed:0 ql_uncompressed_size:2048

9. 高频面试题

Q1：Redis 的 string 为什么不用 C 语言原生字符串？SDS 有什么优势？

五个优势：

1. O(1) 获取长度：SDS 有 len 字段，C 字符串要 strlen 遍历（O(N)）。这让 STRLEN 和内部的长度判断都是常数时间；
2. 杜绝缓冲区溢出：SDS 的 API 会先检查剩余空间并自动扩容，C 的 strcat 不检查直接写；
3. 减少内存重分配次数：空间预分配（扩容后 <1MB 时多分配一倍，>=1MB 时多分配 1MB）+ 惰性空间释放（缩短只改 len 不释放），把 N 次修改的 realloc 次数从 N 降到 O(logN) 甚至更少；
4. 二进制安全：靠 len 界定长度而不是 \0，可以存图片、序列化数据等含 \0 的二进制内容；
5. 兼容部分 C 函数：buf 末尾仍放 \0（不计入 len），可直接用 printf 等只读函数。

加分点：3.2 后 SDS 分成 sdshdr5/8/16/32/64 五种，按长度选最小的 header（短字符串只要 3 字节头，之前统一 8 字节），是一次重要的内存优化。

Q2：embstr 和 raw 的区别？为什么阈值是 44 字节？

区别：

• embstr：robj 和 SDS 在一次 malloc 中连续分配，ptr 指向紧跟其后的 SDS。分配/释放各只 1 次，内存连续、缓存友好，但不支持原地修改；
• raw：robj 和 SDS 分两次分配，ptr 指向独立的 SDS。支持修改。

44 的推导：Redis 希望一个 embstr 对象正好装进 jemalloc 的 64 字节分配档：

64 = robj(16) + sdshdr8(3) + 内容(N) + '\0'(1)   →   N = 44

补充历史：3.2 之前阈值是 39，因为当时 SDS header 固定 8 字节（64-16-8-1=39）；3.2 引入 3 字节的 sdshdr8 后变成 44。

再补充：embstr 一旦被修改（APPEND/SETRANGE）就永久变成 raw，即使长度还很短。因为 Redis 没实现 embstr 的原地修改函数。

Q3：ziplist 的连锁更新是什么？listpack 如何解决？

连锁更新：ziplist 的每个 entry 都存了 prevlen（前一个 entry 的长度），前驱长度 < 254 时用 1 字节，>= 254 时用 5 字节。

如果一个 ziplist 里连续多个 entry 的长度都在 250~253 之间，此时在头部插入一个 >= 254 字节的元素：

1. 第一个 entry 的 prevlen 从 1 字节扩到 5 字节 → 它自己变长 4 字节 → 253+4 = 257 >= 254；
2. 于是第二个 entry 的 prevlen 也要扩容 → 又变长 4 字节 → 继续超阈值；
3. 连锁传递下去，整个 ziplist 反复 realloc + memmove，复杂度退化为 O(N²)。

删除操作也可能触发（删掉大 entry 后后续 prevlen 需要缩小）。发生概率极低但不可预测，是单线程的延迟毛刺来源。

listpack 的解法：彻底去掉 prevlen，改为在每个 entry 末尾存"本 entry 的总长度" backlen。要向前遍历时，从当前位置往前读 backlen（用了支持反向解析的变长编码）即可定位前一个 entry。这样修改一个 entry 只影响它自己，绝不波及邻居，连锁更新从根本上消失了。

listpack 5.0 为 Stream 引入，7.0 全面替换 ziplist 成为 hash/zset/list 的小编码。

Q4：quicklist 是什么？解决了什么问题？

3.2 之前 list 的两种编码各有致命缺陷：

• ziplist：连续内存，插入删除要 memmove/realloc 整块，元素多了性能崩塌，且有连锁更新风险；
• linkedlist：每个节点 listNode 要 24 字节指针 + value 的 robj 16 字节 + SDS 头，存 3 字节内容要花 50+ 字节；内存分散、缓存命中率差、碎片多。

quicklist 是两者的折中：一个双向链表，每个节点内部是一个 ziplist（7.0+ 是 listpack）。

• 保留链表的两端 O(1) 操作；
• 节点内紧凑存储，大幅减少指针开销和碎片；
• 用 list-max-listpack-size（默认 -2 = 8KB）控制单节点大小，在"节点数过多"和"节点内 memmove 过重"之间取平衡；
• list-compress-depth 可以用 LZF 压缩中间节点（首尾各留 n 个不压缩），因为 list 通常只在两端访问；
• count 字段让 LLEN 保持 O(1)；
• 单个超大元素会用 container=PLAIN 的节点直接存，不套 listpack。

7.0 后小 list 直接用 listpack（连 quicklist 外壳都省了），超阈值才转 quicklist。

Q5：什么是渐进式 rehash？为什么需要它？

Redis 的 dict 有 ht_table[0] 和 ht_table[1] 两个哈希表。当负载因子超标需要扩容时：

为什么不能一次性搬完：Redis 单线程，如果一个有 5000 万 key 的字典一次性 rehash，要遍历并重新哈希 5000 万个 entry，会阻塞数秒，期间所有请求超时，等于服务挂了。

渐进式过程：

1. 给 ht_table[1] 分配新空间（目标是第一个 >= used*2 的 2 的幂）；
2. rehashidx = 0，标记 rehash 开始；
3. 之后每次对该 dict 的增删改查操作，都顺带把 ht_table[0] 第 rehashidx 个桶上的所有 entry 迁到 ht_table[1]，然后 rehashidx++；
4. 同时 serverCron 每 100ms 调用 dictRehashMilliseconds，用最多 1ms 批量推进（防止 dict 一直没人访问导致 rehash 卡住）；
5. 全部搬完：释放 ht_table[0]，把 ht_table[1] 变成 ht_table[0]，rehashidx = -1。

期间的读写规则：

• 查找/删除/修改要依次查两张表；
• 新增只写 ht_table[1]，保证旧表元素只减不增，rehash 必然收敛；
• 有安全迭代器时用 pauserehash 暂停 rehash，避免遍历重复/漏元素。

触发条件补充：负载因子 >= 1 且无子进程时扩容；负载因子 >= 5 时强制扩容（不管有没有子进程）。之所以要看子进程，是因为 rehash 会造成大量 COW，让 RDB/AOF 重写的子进程内存暴涨。使用率 < 10% 时缩容。

Q6：dict 的哈希冲突怎么解决？为什么用 SipHash？

冲突用链地址法（拉链）：哈希到同一个桶的 entry 挂成单链表，新元素插入链表头部（O(1)，避免遍历到尾部）。

哈希函数从 MurmurHash2 换成 SipHash（4.0+） 是为了防御 Hash-DoS 攻击：MurmurHash2 是确定性的且可被逆向分析，攻击者能构造出成千上万个哈希到同一桶的 key，让哈希表退化成一条长链表，所有查找变成 O(N)，用少量请求就能打死实例。

SipHash 是带密钥的伪随机函数，Redis 启动时生成随机 seed，攻击者不知道密钥就无法预测哈希值、无法构造碰撞。代价是 SipHash 比 MurmurHash 略慢，但安全性收益远大于此。

Q7：zset 为什么同时用 skiplist 和 dict？

因为 zset 有两类完全不同的访问需求：

• 按 member 查 score（ZSCORE、ZINCRBY 需要先读旧值）要 O(1) → 只有哈希表能做到，所以用 dict 存 member → score；
• 按 score 排序访问（ZRANGE、ZRANGEBYSCORE、ZRANK、ZCOUNT）要 O(logN) 定位 + 顺序遍历 → 用 skiplist。

如果只有 skiplist，ZSCORE 就要 O(logN)（还得先按 score 找，但我们只知道 member，实际是 O(N)）；如果只有 dict，所有排序和范围查询都要 O(NlogN) 现场排序。

重要细节：两个结构共享同一份 member 的 SDS 和 score（dict 的 key 指针和 skiplist 节点的 ele 指向同一块内存），所以不是双倍内存，只是多了一份哈希表的指针开销。

Q8：跳表的层数是怎么决定的？为什么概率取 0.25？

随机决定：zslRandomLevel() 从 1 层开始，每次以 ZSKIPLIST_P = 0.25 的概率再加一层，直到失败或达到 ZSKIPLIST_MAXLEVEL = 32。

为什么用随机：标准的"每 2 个节点提升 1 个"需要在插入删除时重建索引层（维护成本高）。随机层数在概率意义上能达到同样的 O(logN)，但插入删除只需改几个指针，完全不需要再平衡——这是跳表实现简单的根本原因。

为什么 p 取 0.25 而不是教科书的 0.5：

• 平均层数 = 1/(1-p)。p=0.5 时平均 2 层，p=0.25 时平均 1.33 层；
• 层数越少，每个节点的 forward 指针数越少，内存越省（每个指针 8 字节 + span 8 字节）；
• 代价是查找时要多做一些同层比较，速度略降。

Redis 作为内存数据库，主动用一点查询速度换内存，这个取舍非常典型。最大 32 层配合 p=0.25，理论上支持 4^32 个元素。

Q9：跳表节点的 span 字段是干什么的？

span 记录"这个 forward 指针跨过了多少个节点"，是 Redis 对标准跳表的增强。

它让 ZRANK（求排名）从 O(N) 变成 O(logN)：查找目标节点的过程中，把路径上经过的所有 span 累加，就得到了它的排名（前面有多少个节点）。

同理，ZRANGE key 5 15（按排名取区间）也靠 span 快速跳到第 5 个节点，而不必从头数。没有 span 的话这两类操作都只能顺序遍历。

Q10：Redis 的编码会从 hashtable 退回 listpack 吗？

不会。编码转换是单向的、不可逆的。

比如一个 hash 因为字段数超过 128 升级成了 hashtable，后来删到只剩 3 个字段，编码仍然是 hashtable。

原因：

1. 转换成本高：降级要 O(N) 重建整个结构（遍历所有元素重新写进 listpack）；
2. 可能反复抖动：如果元素数在阈值附近来回波动（127 ↔ 129），双向转换会导致持续的 O(N) 重建，性能远比省下的内存更值钱；
3. 省内存的收益有限：能升级说明它曾经很大，业务上很可能还会再变大。

实践影响：如果一个 hash/zset 曾经短暂地超过阈值（比如批量导入时一次性塞了 200 个字段，然后删到 10 个），它会永久占着 hashtable 的高内存。想恢复只能删除后重建这个 key（或者 DUMP+RESTORE，因为 RESTORE 时会按当前大小重新选编码）。

Q11：为什么大 hash 比同样数据量的多个小 hash 费内存？

因为编码不同。

• 小 hash（<=128 字段）用 listpack：一整块连续内存，每个字段只占「encoding + 内容 + backlen」，短字符串约 5~10 字节，没有任何指针；
• 大 hash 用 hashtable（dict）：每个字段要 dictEntry（32 字节，含 jemalloc 对齐）+ field 的 SDS（3 字节头 + 内容）+ value 的 robj（16 字节） + value 的 SDS + 哈希数组里的指针（8 字节，还要摊上空槽），合计 60~90 字节。

所以差 5~10 倍。这就是分桶优化的理论依据：把 100 万字段的大 hash 按 id/1000 拆成 1000 个各含 1000 字段的小 hash（配合调大 hash-max-listpack-entries），内存能降一个数量级。这是 Instagram 那篇著名的 Redis 内存优化文章的核心方法。

Q12：intset 的 SISMEMBER 是 O(1) 吗？

不是，是 O(logN)。

intset 的 contents 是一个从小到大有序排列的整数数组，查找用二分查找，所以 SISMEMBER 是 O(logN)。只有 hashtable 编码下才是 O(1)。

但实际上完全不用担心：intset 最多 512 个元素（set-max-intset-entries），log2(512) = 9 次比较，而且数组是连续内存、CPU 缓存全命中，实测比 hashtable 的一次哈希计算 + 指针跳转还快。这也是为什么小集合用紧凑结构反而更快。

补充：intset 有 INT16/INT32/INT64 三种 encoding，插入超范围的整数会触发升级（O(N)，从后往前搬移避免覆盖），且只升不降。

Q13：Redis 的共享整数对象是什么？什么时候不生效？

Redis 启动时预先创建了 0~9999 共 10000 个整数的 robj（shared.integers）。任何地方用到这些小整数时，直接复用同一个对象并增加 refcount，不再分配新的 robj（省 16 字节/个）。

SET a 100 ; OBJECT REFCOUNT a    # 2147483647 (INT_MAX)，表示共享对象
SET b 99999 ; OBJECT REFCOUNT b  # 1，独立对象

两种情况不生效：

1. 值超出 0~9999；
2. 配置了 maxmemory 且淘汰策略是 LRU/LFU 系列时，共享对象被禁用。因为 robj 的 lru 字段要记录每个 key 独立的访问时间/频率，共享同一个对象就没法区分谁被访问了。（noeviction 和 random 策略不需要 lru 信息，所以共享仍生效。）

这是个很少人知道的细节，答出来是明显加分项。

小结

• Redis 有类型（type）和编码（encoding）两层抽象：小数据用紧凑结构省内存 + 缓存友好，大数据用高级结构保时间复杂度；用 OBJECT ENCODING 查看。
• 每个 value 都被 robj 包裹（16 字节固定开销），lru 字段兼做 LRU 时钟/LFU 计数，refcount 支撑 0~9999 的共享整数（LRU/LFU 策略下失效）。
• SDS 的五大优势：O(1) 长度、防溢出、预分配+惰性释放、二进制安全、兼容部分 C 函数；3.2 后分 5 种 header 进一步省内存。
• string 三编码：int（long 范围整数）、embstr（<=44 字节，robj+SDS 一次分配）、raw；44 = 64 - 16(robj) - 3(sdshdr8) - 1(\0)；embstr 被修改后永久变 raw。
• intset：有序整数数组 + 二分查找（O(logN)），只升级不降级；上限 512 个。
• ziplist 的连锁更新（prevlen 的 1/5 字节切换引发 O(N²)）是它被淘汰的核心原因；listpack 用"自身长度 backlen"取代"前驱长度 prevlen"，彻底消除连锁更新。
• quicklist = 双向链表 + 每节点一个 listpack，兼顾两端 O(1) 和内存紧凑；list-max-listpack-size 默认 -2（8KB）；list-compress-depth 可 LZF 压缩中间节点。
• dict 的渐进式 rehash：两张表 ht_table[0/1]，每次操作搬一个桶 + serverCron 每 100ms 最多 1ms 推进；期间查两表、只写新表；负载因子 >=1 扩容（有子进程时提到 >=5 才强制，为了减少 COW），<0.1 缩容。
• 哈希函数用 SipHash（带随机密钥）防 Hash-DoS；冲突用链地址法且头插。
• zset = dict（member→score，O(1)）+ skiplist（排序范围，O(logN)），两者共享同一份 member 和 score。
• 跳表选型理由：范围查询天然高效、实现比红黑树简单太多、p=0.25 让平均层数 1.33 更省内存；B+ 树是为磁盘设计的，纯内存场景无意义。span 字段让 ZRANK 达到 O(logN)。
• 编码转换不可逆：升级后不会降回来，短暂超阈值会永久占用高内存，只能删除重建。
• 内存优化主线：用 hash 代替多 key、大 hash 分桶保持 listpack、短 key 名、整数走 int 编码、布尔用 Bitmap、基数用 HLL；阈值可适度调到 512，但绝不要超过 1000。