Theory · Redis · Internals

对象系统与底层数据结构

redisObject 壳 + SDS / dict / skiplist / listpack / quicklist 芯 —— type 定行为，encoding 定实现，阈值定切换

对象系统

五大类型只是"壳"：redisObject 用 type/encoding 双字段解耦逻辑类型与底层实现，OBJECT ENCODING 直接可查

核心结构

SDS O(1) 长度、dict 渐进式 rehash、skiplist 概率平衡、listpack 消灭连锁更新——全部对照 redis 源码讲

编码切换

紧凑编码 ↔ 常规编码的阈值配置（7.x vs 8.0 变化）、只升不降原则，是面试的追问主战场

面试复习 · 结论对照 Redis 7.x/8.x 源码（src/server.h、src/sds.h、src/dict.c、src/t_zset.c）与 redis.io 官方文档
这是 Redis 领域的第一张 deck，讲对象系统和底层数据结构。主线逻辑：先建立"一个 key 一个 redisObject"的世界观，再逐个拆五大底层数据结构——SDS、dict、skiplist、listpack、quicklist，最后落到编码切换的阈值配置表。所有结构体名都对应 redis 源码里的真实定义，面试时报得出 sdshdr8、zskiplistNode、rehashidx 这些名字，说服力完全不同。

Why Encodings Matter

先看现象：命令一模一样，内存差了 4 倍

// 存用户画像：一个用户一个 hash，每个 5 个字段
> HSET u:1 name alice age 30 city bj vip 1 lv 7
> OBJECT ENCODING u:1
"listpack"        // 紧凑编码：整块连续内存
> MEMORY USAGE u:1
120               // 约 120 字节，每字段 ≈24B

// 换一个大 hash：塞进 600 个字段（超过默认阈值 512）
> OBJECT ENCODING u:big
"hashtable"       // 自动换成常规哈希表
> MEMORY USAGE u:big
// 每字段 ≈100B 起：多出 dictEntry(24B)
// + 两个 sds 头 + 桶数组 + 空槽预留

// 而对业务代码来说，HGET / HSET 的用法、
// 返回值、复杂度承诺，全都没变过一个字。
把它放大到生产规模：1000 万个 5 字段小 hash，走 listpack 约 1.2GB，走 hashtable 约 5GB——同样的数据、同样的命令，账单差 4 倍。Redis 之所以给每种类型准备多套底层实现，就是为了自动替你挑便宜的那套。

如果只用一套通用实现会怎样

假设 hash 永远是标准哈希表：存 5 个字段也要为每对键值分配一个 dictEntry（键指针 + 值指针 + next 指针 ≈24B）、两个独立的字符串对象头，再加上桶数组必须留空槽（负载因子要 <1）。元数据比数据本身还大——小对象场景，"通用"等于"浪费"。

Redis 的做法：一个壳 + 可换的芯

每个 key 的值都套一个统一外壳 redisObject，壳上写着两件事：我是什么类型（type，给用户看）和我现在用哪种底层实现（encoding，内部优化）。数据小的时候用省内存的紧凑实现，大到一定程度自动换成快的常规实现，而上层命令完全不知情。

所以这份 deck 值得细读的三个理由

① 它直接是钱：编码选择决定内存账单，是缓存集群最大的成本项；
② 它解释怪现象："删了一半数据内存却不降"、"同样 10 万条数据这个 key 特别大"，答案都在编码；
③ 它是面试的深水区：从"五大类型"追问到 sdshdr8、rehashidx、连锁更新，报得出结构体名字和常量的人一眼可辨。

本 deck 的路线

先认识壳（redisObject）与类型×编码的全局地图 → 再逐个拆五种芯（SDS / dict / skiplist / listpack / quicklist·intset）→ 最后收到"什么时候换芯"的阈值表、速查页与 16 道 QA。

Theory · Redis · 对象系统与底层结构
动机页：用"同一条 HSET、同一份数据，内存差 4 倍"这个可现场复现的对比开场，把编码体系的价值先量化成钱。再解释若只用一套通用哈希表，元数据会比数据还大，从而引出"一个壳 + 可换的芯"这个全 deck 的心智模型。禁止一上来贴 redisObject 结构体——那是下一页的事。

Prerequisites & Glossary

先把词认全：后面每一页都会用到它们

术语一句话理解（细节后面展开）
对象 / robj
（redisObject）		每个 key 的值都被套上的统一外壳，记着类型、编码、访问时钟等元信息
type / encodingtype = 用户看到的类型（string/hash/…）；encoding = 内部真正用的数据结构。同一个 type 可以有多种 encoding
紧凑编码把所有元素塞进一整块连续内存的实现（listpack、intset）：省内存、但改动要挪字节，只适合小数据
SDSRedis 自己写的字符串（Simple Dynamic String）：字节数组 + 一个记录长度的头部
dict / 桶 / 负载因子哈希表；桶（bucket）是数组的一格，冲突的键挂成链表；负载因子 = 元素数 ÷ 桶数，越大冲突越多
rehash桶数组换大（或换小）后，把所有键按新桶数重新分配位置的过程
跳表（skiplist）多层链表：上层稀疏用来"跨大步"、底层完整且有序，查找像跳台阶，期望 O(log N)
quicklistlist 的实现：一条双向链表，但每个节点内部塞一块紧凑内存（而不是只放一个元素）
写时复制（COW）fork 出子进程后父子共享内存页，谁写谁才复制一份——父进程改得越多，额外内存越多
jemalloc 分配类内存分配器只按固定档位给内存（16/32/64/128B…）：申请 45B 实际拿到 64B，多出来的是浪费

不在本 deck 内的前置，按需回看

哈希表 →　桶、冲突、链地址法、负载因子的通用原理
跳表 →　层高、概率平衡、与平衡树的完整对比
数组 vs 链表 →　"连续内存 vs 指针跳转"的取舍（紧凑编码的理论基础）
往后看：过期与淘汰 →（robj 里 lru:24 字段的用途）、缓存问题 →（大 key 治理）

本 deck 怎么用这些词

结构体名与常量一律用源码里的原文（sdshdr8、rehashidx、ZSKIPLIST_P），因为面试报得出名字才算真读过；配置项一律用 7.0 之后的新名（*-max-listpack-*），旧名只在讲版本变迁时出现。

最小心智模型（后面每页都挂在它上面）

一个 key = 一个壳（robj）+ 一个芯（底层结构）。
· 壳上写着"我是什么类型"和"我现在用哪种芯"；
· 芯有两类：紧凑芯（连续内存、省钱、慢改）与常规芯（哈希表/跳表、费内存、快）；
· 数据小用紧凑芯，超过阈值自动换常规芯，而且只换一次、永不换回。
后面 11 页只回答两个问题：有哪些芯（结构原理）、什么时候换芯（阈值与转换规则）。

Theory · Redis · 对象系统与底层结构
前置页：十个术语先定义再使用，重点是"紧凑编码""负载因子""写时复制""jemalloc 分配类"——这四个词后面分别支撑 listpack、rehash 触发、BGSAVE 期间阈值提高、embstr 的 44 字节。三条前置链接指向数据结构系列的通用原理，本 deck 只讲 Redis 的特化取舍。最小心智模型把全 deck 压成"壳 + 可换的芯 + 只升不降"。

Object System · src/server.h

redisObject：类型与实现解耦的"壳"

开场那两条 OBJECT ENCODING 的输出差异，就写在这个壳的两个 4bit 字段里：type 决定命令能不能用，encoding 决定这份数据实际长什么样。

// github.com/redis/redis · src/server.h
// Redis 7.x / 8.x · robj（redisObject）
typedef struct redisObject {
    unsigned type:4;       // 逻辑类型
    unsigned encoding:4;   // 底层编码
    unsigned lru:LRU_BITS; // 24bit：LRU 时钟或 LFU
    int refcount;          // 引用计数 / 内存回收
    void *ptr;             // 指向底层结构
} robj;

// type：OBJ_STRING / OBJ_LIST / OBJ_SET
//      OBJ_ZSET / OBJ_HASH（4bit 够用）
// encoding：同 type 的不同底层实现
// LRU_BITS = 24（第 16 页展开 LFU 拆分）
字段要点
type:4面向用户的五大类型：STRING / LIST / SET / ZSET / HASH；由命令名决定校验（LPUSH 只认 LIST）
encoding:4同一 type 的多种底层实现，如 hash 的 listpack / hashtable——行为对外一致，内存与复杂度内敛优化
lru:24复用同一 24bit：LRU 模式存最后访问时钟，LFU 模式拆成 16bit 分钟时间戳 + 8bit 计数器
refcount引用计数回收 + 对象共享：0–9999 整数共享（OBJ_SHARED_INTEGERS = 10000），LRU/LFU 模式下共享对象时钟不更新
查看命令：TYPE 看 type；OBJECT ENCODING key 看编码（int/embstr/raw/listpack/hashtable/intset/skiplist/quicklist）；OBJECT REFCOUNT 验证整数共享。
为什么这么设计：小数据自动换省内存的紧凑编码，代码上层不感知——"编码"是 Redis 内存优化的总开关
redisObject 是所有 key 值的统一外壳，只有 16 字节：type 和 encoding 各占 4 个 bit，lru 占 24 个 bit，加一个 int 引用计数和指针。核心思想是解耦：type 是给用户看的逻辑类型，encoding 是底层真实实现，两者可以自由组合。refcount 有个高频细节：0 到 9999 的整数对象是全局共享的，创建时直接复用，这能省大量小整数内存；但共享对象的 lru 时钟不会随访问更新，这是它和普通对象的一个差异。查编码用 OBJECT ENCODING，这是调试大 key 优化效果的日常工具。

Type × Encoding Map

五大类型 × 底层编码：一张表建立全局地图

type可能 encoding（OBJECT ENCODING 输出）切换条件（默认配置）
stringint → embstr → raw值是 ≤ 20 位整数（long 范围）→ int；字符串 ≤ 44 字节 → embstr；超过 → raw（浮点数按字符串存）
listquicklist（节点内是 listpack）始终 quicklist；节点大小由 list-max-listpack-size 控制（默认 -2 = 8KB/节点）
hashlistpack → hashtable键值对数 ≤ hash-max-listpack-entries 且 value ≤ hash-max-listpack-value（64B）→ listpack；超出转 hashtable。7.x 阈值 128，8.0 起默认 512
setintset / listpack / hashtable全为整数且个数 ≤ set-max-intset-entries（512）→ intset；7.2 起小集合（≤128 个且元素 ≤64B）→ listpack；否则 hashtable
zsetlistpack → skiplist元素数 ≤ zset-max-listpack-entries（128）且 member ≤ zset-max-listpack-value（64B）→ listpack；超出转 skiplist
答题框架：先说"type 不变、encoding 变"，再报两三个关键阈值（128/64/512），最后补一句"7.0 起 listpack 全面取代 ziplist、7.2 起小集合也用 listpack"——版本演进意识立即和背旧八股的人区分开。
出处：redis.io/docs/latest/commands/object-encoding/ · redis.conf（8.2）默认值
这张映射表是全 deck 的地图。记忆抓手：三种编码切换模式。string 是"按值大小"三选一；hash 和 zset 是"紧凑编码超阈值升级"，共同阈值是 128 个、64 字节；set 最特殊，整数优先 intset，7.2 以后小集合还多了 listpack 这一层。注意 8.0 把 hash 的 listpack 阈值从 128 提到 512，这是官方为了省内存做的默认值调整，面试提这个版本差异是加分项。list 从 3.2 起就固定是 quicklist 了。

Simple Dynamic Strings · src/sds.h

SDS：C 字符串的"加固版"

维度C 字符串SDS
取长度O(N)：遍历到 \0O(1)：头部 len 字段直接读（STRLEN 常量时间）
二进制安全不安全：内容含 \0 即被截断，只能存文本二进制安全：以 len 判边界，\0 只是结尾标记；可存图片序列化字节流等任意字节
拼接溢出忘记 realloc 直接缓冲区溢出（安全漏洞之源）拼接前检查 alloc-len，不足先 sdsMakeRoomFor 扩容，杜绝溢出
修改内存分配每次改长必然 realloc空间预分配：扩容后新分配空间 = min(翻倍, +1MB)（SDS_MAX_PREALLOC = 1MB，即 <1MB 翻倍、≥1MB 每次多给 1MB），减少连续增长的 realloc 次数
缩短内存无法安全缩短惰性释放：缩短只减 len 不释放 alloc，字节留在原地，等下次写入直接复用；必要时 API 可显式释放
C 兼容—buf 仍以 \0 结尾，多数 <string.h> 函数可直接复用，避免重复造轮子
面试一句话："SDS = 长度头 + 二进制安全的字节数组。O(1) 取长度、拼接前检查扩容防溢出、预分配 + 惰性释放摊平修改成本，同时保留 C 字符串的结尾 \0 兼容部分 C API。"
出处：src/sds.h / src/sds.c · SDS_MAX_PREALLOC = 1024*1024（1MB）
SDS 是所有字符串值的底层，也是 RESP 之外 Redis 自己最基础的结构。对比 C 字符串抓四点：O(1) 取长度，因为头部记了 len；二进制安全，靠 len 判边界而不是 \0；拼接前检查空间不够就扩容，杜绝溢出漏洞；预分配加惰性释放，把增长的 realloc 和缩短的 free 都摊平了。预分配的阈值要记准：小于 1MB 翻倍，大于等于 1MB 每次多加 1MB，这个 1MB 就是源码里的 SDS_MAX_PREALLOC。

sdshdr5/8/16/32/64

按长度选头部：短字符串的内存精细化

结构体len/alloc 宽度头部总开销
sdshdr5无 len/alloc 字段1B flags（3bit type + 5bit len）
sdshdr81B / 1B3B（len+alloc+flags）
sdshdr162B / 2B5B
sdshdr324B / 4B9B
sdshdr648B / 8B17B
设计收益：旧版统一用 5B 头部；Redis 3.2 起按实际字符串长度选最小头——百万级短 key 场景下，每个值省 2B 也能累积出可观内存。
// src/sds.h · sdshdr8（长 ≤255 的字符串）
struct __attribute__((packed)) sdshdr8 {
    uint8_t len;    // 已用长度
    uint8_t alloc;  // 分配总长（不含头与\0）
    unsigned char flags; // 低 3bit 存 type
    char buf[];
};
// packed：禁止结构体对齐填充，
// 3B 头部是"真实" 3 字节

// len 与 alloc 分开维护：
// 空闲空间 = alloc - len
//   → 惰性释放的实现基础
embstr（string 编码之一）说明
≤ 44 字节 → embstr一次分配：redisObject 头 + sdshdr8 + 44 字符 + \0 恰好装进 jemalloc 64B 分配类；连续内存对 CPU 缓存友好
embstr 是只读的任何修改（APPEND 等）先转 raw 再改——没有就地修改的余地（分配粒度固定）
44 = 64B（jemalloc 分配类）− sizeof(robj) 16B − sdshdr8 头 3B − \0 1B
SDS 头部是分级设计，按字符串长度选 sdshdr5、8、16、32、64，短字符串用最小头部。关键细节：结构体加了 packed 属性禁止对齐填充，sdshdr8 的 3 字节头是真 3 字节。len 和 alloc 分开记，两者的差就是惰性释放留下的空闲空间。embstr 那个 44 是高频计算题：jemalloc 的 64 字节分配类，减 16 字节 redisObject、3 字节 sdshdr8 头、1 字节结尾符，正好 44。embstr 一次分配一次释放、缓存友好，但只读，修改就转 raw。

dict · src/dict.c

两张 ht + rehashidx：把一次大搬家摊成 N 次小搬家

dict 渐进式 rehash：ht[0] 向 ht[1] 逐桶迁移 dict 持有 ht[0] 与 ht[1] 两张哈希表与 rehashidx；rehash 期间 ht[0] 中 rehashidx 之前的桶已迁空，数据出现在 ht[1]，读操作双查两表，新增只写 ht[1]。 下一个迁移目标 已迁移完成 dict（src/dict.h） dictType *type 类型特定函数 void *privdata dictht ht[2] 两张哈希表 long rehashidx = 2 unsigned long iterators -1 = 未在 rehash ≥0 = rehash 进行中 ht[0] · 原表（size=8） bucket 0 · 空 bucket 1 · 空 bucket 2 → k1 → k3（链表） rehashidx 指向此桶 bucket 3 → k7 bucket 4..7 空 迁移完成的桶被置空： rehashidx 之前的桶不再有数据 每次增删改查顺带迁一个非空桶 ht[1] · 新表（size=16） bucket 0 → k1 bucket 1 → k3 bucket 2 → k7 bucket 3..15 空 扩容 size = 第一个 ≥ used×2 的 2 的幂（used=4 → 16） rehash 期间的新增键 一律只写 ht[1]，保证 ht[0] 只减不增、终会迁空 读：双查 查找先 ht[0]，没有再 ht[1]； 更新/删除同样在两表都可能命中 → 语义与单表完全一致 写：分家 新增只进 ht[1]（保证收敛）； 删除/更新先 ht[0] 后 ht[1]； 每次操作附带 _dictRehashStep 定时兜底 serverCron 周期调 dictRehashMilliseconds(d, 1)： 1ms 预算内批量迁移，防停滞
单次 rehash 是 O(N)：百万 key 一次搬完 = 数百毫秒阻塞；渐进式把它摊到每次操作 O(1)
dict 是 Redis 的心跳结构，db 的 keyspace 本身就是个 dict。渐进式 rehash 的全景：扩容时同时持有 ht[0] 和 ht[1]，rehashidx 标记迁移进度，之前的桶已迁空。三张卡片是全部规则：读操作双查两表，保证语义不变；新增只进 ht[1]，让 ht[0] 只减不增保证收敛；增删改查每次顺带迁移一个非空桶。还有个兜底：定时任务给 1 毫秒预算批量迁移，防止只有读操作时迁移停滞。整套设计的动机就一句话：一次搬完是 O(N) 会阻塞，摊到每次操作就是 O(1)。

Load Factor · dict.c

什么时候扩、什么时候缩、BGSAVE 为什么插手

动作触发条件（负载因子 = ht[0].used / ht[0].size）新 size 的取法
扩容 expand无 BGSAVE / BGREWRITEAOF 在跑：负载因子 ≥ 1
有 BGSAVE / BGREWRITEAOF 在跑：负载因子 ≥ 5（dict_force_resize_ratio）		第一个 ≥ used×2 的 2 的幂
缩容 shrink负载因子 < 0.1第一个 ≥ used 的 2 的幂（多为对半缩）
迁移节奏每次增删改查附带迁移一个非空桶（连续跳过空桶计数 empty_visits 有限，防止纯扫空桶）—
完成ht[0] 迁空 → 释放 ht[0]，ht[1] 变为新的 ht[0]，rehashidx 置回 −1，新 ht[1] 清空待用—

为什么 BGSAVE 期间阈值从 1 提到 5

fork 出的子进程靠写时复制共享父进程内存页。此时激进 rehash 会大量改写 ht[0] 所在页，触发更多 COW 页复制、内存翻倍放大。提高阈值 = rehash 期间尽量不动老表，为 fork 省内存。

为什么必须 2 的幂

哈希取模优化为按位与：hash & sizemask（sizemask = size−1）。扩缩容取 2 的幂才能保证 sizemask 全 1，一次位运算完成取模——dictType 里还要求哈希函数带种子（防哈希碰撞注入攻击）。

答题口径："触发看负载因子：平时 1 扩 0.1 缩；有 RDB/AOF 重写子进程在跑时，扩容阈值升到 5，为了少动老表、减少写时复制的内存放大。"
出处：src/dict.c · dict_can_resize / dict_force_resize_ratio 逻辑 · SipHash 种子（redis 5.0+）
rehash 什么时候触发：负载因子超过 1 就扩、低于 0.1 就缩，这是平时状态。关键变体是 BGSAVE 或 AOF 重写期间，扩容阈值提到 5，原因是 fork 子进程靠写时复制共享内存，这时大规模 rehash 会疯狂改写老表的内存页，COW 放大内存占用，所以故意不迁。新表大小必须是 2 的幂，因为取模优化成了位运算 hash 与 sizemask。另外哈希函数带随机种子，防的是有人恶意构造碰撞 key 打挂链表，这也是个安全向的加分细节。

t_zset.c · zset = dict + zskiplist

zset 为什么"养两套结构"：各付各的钱，各赚各的快

zset 双结构：dict 负责 O(1) 分数查询，skiplist 负责有序范围操作 zset 结构体持有 dict 和 zskiplist 两个指针：dict 把 member 映射到 score，支撑 ZSCORE O(1)；skiplist 按 score 有序，多层链表支撑 ZRANGE 等范围操作，两结构共享 member 的 sds。 zset（server.h） dict *dict · zskiplist *zsl member 的 sds 两结构共享指针，不复制 dict：member → score（O(1)） "alice" ──→ 92.5 "bob" ──→ 87.0 "carol" ──→ 99.0 ZSCORE O(1) ZSCORE alice → 92.5 ZADD 已存在 member 时靠它找到旧 score 判断更新 value 与 skiplist 节点共用同一个 score/ele 对象 没有它：每次查分数都要 O(logN) 扫有序结构 zskiplist：按 score 有序（O(logN) 范围） L2 L1 L0 head carol head bob alice carol head dave bob alice carol ZRANGE / ZRANGEBYSCORE / ZRANK 从最高层向右跨步逼近目标，再逐层下降； 命中后沿 L0 顺序遍历即是天然有序输出 score 相同比 member 字典序——排序全序保证 写路径：ZADD 同时更新两结构 → 内存 ×2 的代价，换来"点查 O(1) + 范围 O(logN)"两全
面试句式："dict 管 O(1) 点查，skiplist 管 O(logN) 范围，member 字符串两结构共享不复制"
zset 是唯一"双结构"的类型，这是必考设计题。dict 负责 member 到 score 的映射，ZSCORE 直接 O(1)；skiplist 按 score 有序，ZRANGE、ZRANGEBYSCORE、ZRANK 这些范围和排名操作靠它，而且命中后沿最底层遍历天然有序。两者共享 member 的字符串和 score 值，不会复制两份。为什么非要两套：只有 skiplist 的话查分数要 O(logN)，只有 dict 的话做不了范围查询，花两倍内存买两种复杂度，这是典型的以空间换时间的自觉选择。

zskiplistNode · server.h

跳表 vs 红黑树/平衡树：Redis 的概率平衡选择

// src/server.h · Redis 7.x/8.x
typedef struct zskiplistNode {
    sds ele;            // member（共享 sds）
    double score;       // 排序分数
    struct zskiplistNode *backward;
                        // 后退指针（仅 L0）
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span; // 跨度
    } level[];          // 柔性数组：层高随机
} zskiplistNode;

// ZSKIPLIST_MAXLEVEL = 32（8.0 恒定）
// ZSKIPLIST_P = 0.25：每层晋升概率 1/4
// 期望层高 1/(1-p)×… 平均指针 ≈1.33
// 期望查找 O(log₄N)——常数比红黑树大
// 但绝对值依然对数级
为什么不选红黑树/AVL理由
范围查询是主战场ZRANGE 类操作命中后沿 L0 链表顺序遍历即天然有序输出；树做范围要中序回溯、实现繁琐
实现与调试简单无旋转、无变色；插入/删除只处理前后指针——antirez 自述选择理由
概率平衡层高由随机数决定（p=0.25），期望对数高度，无需维护严格平衡
span 免费送 ZRANK每层记录跨度，查找路径累加 span 直接得排名，ZRANK O(logN)
backward 只在 L0反向遍历（ZREVRANGE）够用；上层不需要双向，省指针
对比收尾："红黑树查单个元素更快些，但 zset 的高频操作是范围查询；跳表以略高的查找常数换实现简单 + 顺序遍历 + rank 免费，这笔账 Redis 算得过来。"
出处：src/t_zset.c · zslRandomLevel()（p=0.25）· antirez《Redis 内部数据结构详解》系列访谈
跳表的结构要点：每个节点的层高随机，level 是柔性数组，每层有 forward 和 span；backward 只在最底层有，满足反向遍历就行。P 值 0.25 意味着每层晋升概率四分之一，平均下来每个节点只有约 1.33 个指针，比 p=0.5 的版本省内存。为什么不用红黑树，答三层：范围查询命中后沿底层链表顺序走就是有序输出，树要复杂的中序处理；实现无旋转无变色，代码好写好调；span 累加直接算出排名，ZRANK 免费得到。这是概率平衡换工程简单性的经典取舍。

7.0 的全面替换 · src/listpack.c

ziplist 的"连锁更新"顽疾，listpack 怎么根治

ziplist prevlen 连锁更新 vs listpack 自包含条目 ziplist 每个 entry 开头记录前一节点长度 prevlen，占 1 或 5 字节；中间节点长度变化导致后续节点 prevlen 溢出扩容，可能连锁传播。listpack 的 entry 只记录自身 encoding、data 和结尾 backlen，不再引用前驱，彻底消除连锁更新。 ziplist（≤6.2 · 已于 7.0 退役） zlbytes zltail zllen entry1 prevlen=1B entry2 变大 → entry3.prevlen 1B→5B entry3 被迫扩容 → entry4.prevlen 又溢出 连锁更新：一次插入/修改可能级联重分配整串节点 entry 结构：prevlen(1B 或 252→5B) + encoding + data prevlen ≤252 用 1B；≥253 需 5B——跨过 252 就是悬崖边 最坏 O(N²)；为兜底极端情况 redis 7.0 直接移除该实现 （quicklist 节点、hash/zset 紧凑编码全部换 listpack） listpack（7.0 起全面接棒） total entry1 enc + data + backlen entry2 变大 只影响自己 entry3 纹丝不动 ✓ entry 只记录"自己"：encoding + data + 自身长度 backlen（放尾部） 不再引用前驱长度 → 无连锁更新，最坏改动 O(N) 单次 遍历：从尾部 backlen 反推 entry 长度 → 向前走； 向后走按 enc/data 长度前进。天然支持双向遍历 仍是一块连续内存、整数与字符串变长编码， 内存布局与 ziplist 同级紧凑，去掉了唯一隐患 连锁更新是什么：前驱节点的长度写在后继节点的头上；前驱从 252 以下涨到 252 以上，后继头上的 1 字节装不下， 必须扩成 5 字节、自身整体后移，于是后继的后继又要跟着变——雪崩式逐节点重分配
Redis 7.0 release notes：list type 等全部改用 listpack，ziplist 编码退出历史舞台（对应源码 src/listpack.c）
ziplist 是紧凑连续内存，但每个 entry 头上记着前驱的长度 prevlen，小于 252 用 1 字节，超了要 5 字节。坑就在这：往中间插入一个大元素，后继节点头上的 prevlen 从 1 字节变 5 字节，整个 entry 变长，再后面的 prevlen 又装不下了，可能一串节点连锁重分配，最坏 O(N²)。listpack 的根治方案很优雅：entry 只记自己的 encoding、data 和放尾部的自身长度 backlen，谁也不引用谁，改动影响范围只限自己。7.0 起 hash、zset、list 的紧凑编码全部换成 listpack。

quicklist.c · intset.c

quicklist：链表 + 紧凑块的折中；intset：整数专属

quicklist（list 的唯一编码）

双向链表串起多个 listpack 节点（7.0 前是 ziplist）。纯链表指针开销大（prev/next 24B 对 8B 数据）、纯 ziplist 大块内存连锁更新 + realloc 代价高——quicklist 取中：每节点一块 ≤8KB 的紧凑内存，链表负责 O(1) 两端。

关键配置：list-max-listpack-size 负数按字节数（-1=4KB / -2=8KB 默认 / -3=16KB / -4=32KB / -5=64KB）；正数 = 每节点最多 entry 数。list-compress-depth 0：两端各保留 N 个节点不压缩，中间节点 LZF 压缩——"头尾热、中间冷"的列表（如时间线）可省一半以上内存。

intset（set 的整数特化）

有序整数数组 + 二分查找。三个成员：encoding（int16/int32/int64）、length、contents。新元素比现有类型宽 → 整表升级（upgrade）：重新按新宽度分配并搬移；查找 O(logN)，插入保持有序。

两个边界：只升不降——删掉大整数后 encoding 不回落；只要混入一个字符串元素，整个集合升级为 hashtable，且不再转回 intset。默认上限 set-max-intset-entries 512，超过直接 hashtable。

追问答案
为什么 list 不直接用双向链表？adlist 每节点 2 指针 + 独立分配，小元素场景指针开销超过数据本身；quicklist 把 8KB 内的数据"打包"，指针均摊近乎为零
quicklist 节点还会连锁更新吗？7.0 前节点内是 ziplist，会；7.0 起节点内是 listpack，不会——这就是 7.0 换血的意义
intset 二分查找为什么够快？上限 512 个元素，log₂512 ≈ 9 次比较；且全是整数、缓存局部性极好，紧凑数组常快过哈希
出处：src/quicklist.h（quicklistNode/quicklistLZF）· src/intset.h
quicklist 解决的是链表和紧凑块的矛盾：纯双向链表指针开销大，纯 ziplist 大了以后操作代价高还可能连锁更新，所以折中成链表挂多个 8KB 的紧凑块，两端操作 O(1)，中间块保持紧凑。compress-depth 是隐藏加分点：两端留几个节点不压缩，中间用 LZF 压，适合头尾热中间冷的列表。intset 是集合的整数特化，有序数组加二分查找，记住两点：类型宽度只能升不能降；混进一个字符串就整体转 hashtable 不回头。7.0 后 quicklist 节点内换成 listpack，连锁更新问题彻底消失。

Config Defaults · redis.conf

编码切换阈值速查：默认值与版本变化

配置（7.0+ 命名）默认值控制对象
hash-max-listpack-entries7.x：128 → 8.0 起：512hash 转 hashtable 的键值对数上限
hash-max-listpack-value64hash 单个 value 字节数上限
set-max-intset-entries512纯整数集合保持 intset 的元素数上限
set-max-listpack-entries / value128 / 64小集合 listpack 编码（7.2 引入）的元素数 / 单元素字节上限
zset-max-listpack-entries128zset 转 skiplist 的成员数上限
zset-max-listpack-value64zset 单个 member 字节数上限
list-max-listpack-size-2（8KB/节点）quicklist 单节点 listpack 的大小或条目数
list-compress-depth0两端不压缩的节点数，中间 LZF 压缩

铁律：编码只升不降

一旦升级（hash → hashtable、zset → skiplist、set → hashtable、intset 升宽），即使之后删除元素缩回阈值以下，也不会自动降回紧凑编码。想要降回去只能新 key 重建——排查"明明数据变小了内存却不降"就是这个原因。

命名的版本变迁（防背错）

7.0 前叫 hash-max-ziplist-entries 等（含"ziplist"字样）；7.0 起 config 改名为 *-max-listpack-*，旧名在 7.x 兼容别名。8.0 把 hash 的 entries 默认从 128 提到 512——用更大紧凑区间换更低内存。

出处：redis.conf（8.2）默认值实测核对 · Redis 8.0 release notes（hash 阈值调整）
这张阈值表建议整页背下来，面试报得出默认值就赢了大多数人。核心数字：128 和 64 是 hash、set、zset 共同的紧凑编码门槛；intset 上限 512；list 节点默认负二就是 8KB。两个必考原则：第一，编码只升不降，升级后删数据不会降回来，这是内存排查的经典坑；第二，配置命名在 7.0 从 ziplist 改成 listpack，旧名兼容。版本差异点：8.0 把 hash 的 listpack entries 阈值从 128 提到 512，说明官方在持续扩大紧凑编码的适用范围。

Edge Cases

高频边界四连：细节决定追问能不能接住

边界展开
embstr 的 44 从哪来jemalloc 64B 分配类 − robj 16B − sdshdr8 头 3B − \0 1B = 44。embstr 一次分配、缓存友好、但只读：APPEND/INCR 等修改先转 raw——"44"比"embstr 更省"更值钱
整数对象共享0–9999（OBJ_SHARED_INTEGERS=10000）的整数字符串全局共享一份；refcount 计数。注意：LRU/LFU 模式下共享对象不更新访问时钟（淘汰统计失真为可接受的代价）
字符串能存整数吗能且优先：值为 long 范围整数时编码直接 int，STRLEN/OBJECT ENCODING 验证；INCR 系列只对 int 编码生效，非整数报错——这就是"计数器要用 INCR 而非 GET+SET"的底层原因之一（原子 + 编码保证）
大 key 与编码的关系大 key 常见成因之一是越过紧凑编码阈值（10 万元素的 hash 直接 hashtable）。治理思路：分桶（hash tag + 分片 key）让每个 hash 回到 listpack 区间，内存可省数倍
答题串联："编码体系 → 内存优化 → 大 key 治理"是一条完整的追问链：OBJECT ENCODING 定位编码 → 阈值判断是否可优化 → 分桶/拆 key 回到紧凑编码 → 内存收益量化（listpack 每元素约省 50–70%）。下一份 deck（memory-policy）会接上淘汰侧的 lru 字段。
出处：src/server.h（OBJ_ENCODING_EMBSTR_SIZE_LIMIT=44、OBJ_SHARED_INTEGERS=10000）
四个高频边界。embstr 的 44 要能现场算：64 字节分配类减 16 字节 robj、3 字节头、1 字节结尾。整数共享区间是 0 到 9999，源码常量 OBJ_SHARED_INTEGERS 等于 10000，注意共享对象不更新 LRU 时钟。字符串存整数时编码是 int，这也是计数器必须用 INCR 的底层理由之一。最后一个是大 key 治理：超大 hash 越过了紧凑编码阈值直接 hashtable，每个元素要付出哈希表加指针的开销，分桶回到 listpack 区间能省一半以上内存，这条链路在真实生产里非常实用。

Cheat Sheet

一页带走：五种芯、必背常量、换芯规则

① 五种芯，各一句话

SDS长度头 + 字节数组：O(1) 取长度、二进制安全、预分配 + 惰性释放
dict两张表 + rehashidx：渐进式 rehash 把一次 O(N) 搬家摊成每次 O(1)
skiplist多层链表 + span：范围/排名 O(log N)，实现比平衡树简单，ZRANK 免费
listpack连续内存、entry 自包含（不记前驱长度）→ 无连锁更新，7.0 起取代 ziplist
quicklist
/ intset		quicklist = 链表节点内挂 listpack（默认 8KB/节点）；intset = 有序整数数组 + 二分

② 猜编码：按这个顺序判

string整数（long 内）→ int；≤44B → embstr；否则 raw
hash / zset元素数 ≤ 阈值 且 每个值 ≤64B → listpack；否则 hashtable / skiplist
set全整数且 ≤512 → intset；小集合（7.2+）→ listpack；否则 hashtable
list恒为 quicklist（节点内是 listpack）

③ 必背常量

44 字节embstr 上限 = 64B 分配类 − robj 16B − sdshdr8 头 3B − \0 1B
16 字节robj 大小（type:4 + encoding:4 + lru:24 + refcount + ptr）
0–9999共享整数对象区间（OBJ_SHARED_INTEGERS=10000），共享对象不更新时钟
1MBSDS 预分配分界：<1MB 翻倍、≥1MB 每次 +1MB
128 / 64zset·set 紧凑编码的元素数 / 单元素字节阈值；hash 7.x 也是 128
512intset 元素上限；8.0 起 hash-max-listpack-entries 默认值
1 / 0.1 / 5负载因子：≥1 扩容、<0.1 缩容；有 BGSAVE/AOF 重写子进程时扩容阈值 ≥5
p=0.25 / 32跳表晋升概率与最大层高（平均约 1.33 个指针/节点）
252ziplist 的 prevlen 由 1B 变 5B 的临界值——连锁更新的悬崖边

④ 三条铁律 + 内存排查三步

铁律：① 编码只升不降（删数据不会降回紧凑编码，要降只能重建 key）；② 桶数恒为 2 的幂（取模退化成 hash & sizemask）；③ intset 宽度只升不降，混入一个字符串就整体转 hashtable。
排查三步：OBJECT ENCODING key 看现状 → 与阈值比对判断"是否本可以更省" → 分桶 / 拆 key 让每份回到紧凑区间后重建（元素级内存常省 50–70%）。
Theory · Redis · 对象系统与底层结构
速查页把全 deck 压成四块：五种结构一句话、猜编码的判定顺序、九组必背常量、三条铁律加排查动作。回看与考前只看这一页；完整配置项清单在上一页的阈值表。

Interview QA · 1/2

结构与原理 8 连问

先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。

1 · redisObject 占多少字节？各字段什么作用？

16Btype:4 encoding:4 lru:24

16B：4bit type（五大类型）、4bit encoding（底层实现）、24bit lru（LRU 时钟或 LFU 数据）、int refcount（引用计数/共享）、void* ptr。type 定行为、encoding 定实现，二者解耦是编码优化的基础。

2 · SDS 相比 C 字符串好在哪？

O(1) len二进制安全预分配/惰性释放

头部记 len 取长度 O(1)；按 len 判边界所以二进制安全；拼接前检查 alloc 扩容防溢出；预分配（<1MB 翻倍、≥1MB +1MB）摊平增长成本，缩短只减 len 惰性释放；末尾仍保留 \0 兼容 C API。

3 · 什么是渐进式 rehash？为什么需要？

ht[0]+ht[1]rehashidx摊还 O(1)

扩容时持有两张表，rehashidx 记进度；每次增删改查顺带迁移一个非空桶，读双查两表、新增只进 ht[1]、定时任务 1ms 兜底。一次迁完是 O(N) 会阻塞主线程，渐进式把它摊成每次操作 O(1)。

4 · rehash 的触发条件？BGSAVE 时有何不同？

≥1 扩 <0.1 缩BGSAVE 时 ≥5

负载因子（used/size）≥1 扩容、<0.1 缩容；有 BGSAVE/BGREWRITEAOF 时扩容阈值升到 5——子进程靠 COW 共享内存，少动老表可减少页复制放大。新 size 取 2 的幂以支持 hash & sizemask 位运算取模。

5 · zset 为什么同时用 dict 和 skiplist？

O(1) 点查O(logN) 范围

dict 负责 member→score 的 O(1) 点查（ZSCORE，ZADD 更新前定位旧分）；skiplist 按 score 有序支撑 ZRANGE/ZRANK 等范围与排名操作。member 的 sds 两结构共享不复制——用双倍内存换两种复杂度各取最优。

6 · 为什么用跳表而不用红黑树？

范围查询实现简单span 送 ZRANK

①范围查询命中后沿最底层链表顺序遍历天然有序，树要繁琐中序处理；②无旋转无变色，实现调试简单（antirez 自述）；③概率平衡 p=0.25 期望对数高度且省内存；④每层 span 累加直接算排名，ZRANK 免费。

7 · ziplist 的连锁更新是什么？listpack 怎么解决？

prevlen 1B/5B自包含 entry

ziplist 每个 entry 头记前驱长度（≤252 占 1B，否则 5B）：中间元素变大迫使后继扩容后移，可级联全表、最坏 O(N²)。listpack 的 entry 只记自身，不引用前驱——无连锁。

8 · embstr 的 44 字节怎么算的？

64B 分配类只读

64（jemalloc 分配类）− 16（robj）− 3（sdshdr8 头）− 1（\0）= 44。一次分配装下对象头+字符串，缓存友好；但没有就地修改空间，任何修改先转 raw，这就是 embstr "只读"的原因。

答题节奏：结论 → 结构体/常量名 → 复杂度或数值证据
QA 第一组覆盖结构主干。第三题答渐进式要三件套说全：双查、新增只进新表、定时兜底。第六题跳表对比红黑树按三层答：范围查询、实现简单、ZRANK 免费，能提 span 字段就是懂源码。第七题连锁更新要能说出 252 这个分界数和 1 字节变 5 字节的机制。第八题现场推 44 的算式，比背结论更能证明水平。

Interview QA · 2/2

编码与边界 8 连问

同样先自答。这一组的答案都要落到具体数值或版本——只说"会自动转换"是不及格的。

9 · OBJECT ENCODING 常见返回值有哪些？

int/embstr/rawlistpack/hashtableintset/skiplist/quicklist

string：int、embstr、raw；hash/zset 小数据：listpack（≤6.2 是 ziplist）；hash/set 大数据：hashtable；set 整数：intset；zset 大数据：skiplist；list：quicklist。排查编码是内存优化的第一步。

10 · 编码转换是双向的吗？

只升不降

不是。超阈值升级后（hash→hashtable、zset→skiplist、set→hashtable、intset 升宽），即使删除元素缩回阈值以下也不自动降级。要回收只能重建 key。"数据变少内存不降"的经典原因。

11 · hash 的 listpack 阈值默认是多少？有版本差异吗？

7.x=1288.0 起=512

7.x 默认 128 个键值对、value 上限 64B；Redis 8.0 起把 entries 默认提到 512，扩大紧凑编码适用面。同时 7.0 起配置名从 *-max-ziplist-* 改为 *-max-listpack-*，背旧名会露馅。

12 · quicklist 是什么？list-max-listpack-size 负数什么意思？

链表挂 listpack-2=8KB

双向链表串多个 listpack 节点（7.0 前 ziplist），兼顾 O(1) 两端与紧凑内存。负数按字节：-1=4KB、-2=8KB（默认）、-3=16KB、-4=32KB、-5=64KB；正数是每节点最多条目数。list-compress-depth 可 LZF 压缩中段。

13 · intset 支持降级吗？混入字符串会怎样？

只升不降整体转 hashtable

不支持降级：存过 int64 后删掉大数 encoding 仍是 int64。混入任意非整数元素，整个集合升级为 hashtable 且不再转回。上限默认 512 个（set-max-intset-entries），超过直接 hashtable。

14 · 渐进式 rehash 期间扩容触发/新键写哪张表？

不二次扩容只进 ht[1]

rehash 进行中不再次触发扩容（等本次完成）；所有新增键一律写 ht[1]，保证 ht[0] 只减不增最终迁空；读和删要双表；rehashidx 之前的桶必为空，定位时可跳过。

15 · skiplist 的 span 和 backward 各干什么用？

span→ZRANKbackward 仅 L0

span 是本层 forward 指针跨过的节点数，查找路径上累加 span 即为排名，ZRANK 因此 O(logN)；backward 只存在于最底层，供 ZREVRANGE 反向遍历，上层不设反向指针以省内存。

16 · 为什么大 hash 要分桶？和编码什么关系？

回到 listpack 区间省 50–70%

超大 hash 越过阈值变 hashtable：每对键值付出 dictEntry+指针+重哈希开销。按业务键分桶（hash tag 或取模拆 key），让每个 hash 保持小规模走 listpack 编码，元素级内存省一半以上，还能配合 expire 整桶过期。

进阶题密度：只升不降 / 8.0 阈值 / span / 分桶治理——拉开差距的四件套
第二组偏编码和工程边界。第十题的只升不降和第十六题的分桶治理是生产向重点，能连起来讲最有说服力：先说升级不降级导致内存虚高，再给分桶方案和量化收益。第十一题的版本差异（8.0 的 512）是新鲜的考点，多数旧资料还写 128。第十四题注意 rehash 进行中不会二次扩容。第十五题 span 和 backward 的分工能体现读源码的深度。

Related & References

相关知识点与参考

Redis 领域 · 同批 deck

过期删除与内存淘汰 →　robj 的 lru:24 字段在此展开
单线程模型 →　高效数据结构是"快"的四要素之一
RDB / AOF 持久化 →　编码紧凑度决定 RDB 体积与恢复速度
主从与集群 →　大 key 对同步与迁移的影响

跨领域 · 答题串联

跳表 →　zset 结构原理与"为什么不选平衡树"
哈希表 →　dict 的通用原理与渐进 rehash 家族
GMP 调度器 →　同样"把全局操作摊到每次事件"
通用线索：摊还分析、概率平衡、紧凑编码三招在多个系统反复出现

参考来源（★ = 最值得原文精读的一篇）

★ redis 源码 src/dict.c + src/dict.h渐进式 rehash 全流程可通读：dictht/rehashidx、dict_force_resize_ratio、_dictRehashStep、dictRehashMilliseconds——本 deck 最值得逐行看的一份
src/server.hrobj 字段、zskiplistNode（level/span/backward）、ZSKIPLIST_P=0.25、MAXLEVEL=32、EMBSTR 上限 44
src/sds.h / sds.csdshdr5/8/16/32/64 分级头部、SDS_MAX_PREALLOC=1MB、sdsMakeRoomFor
src/t_zset.c · listpack.c · quicklist.c · intset.czset 双结构、listpack entry 布局、quicklistNode 与 LZF、intset 升级
redis.io/commands/object-encoding + 数据类型文档各类型合法编码输出与阈值行为的官方口径
redis.conf（8.0 / 8.2）+ 7.0 RELEASENOTES阈值默认值核对（hash 8.0 起 512）；listpack 全面替代 ziplist
Theory · Redis · 对象系统与底层数据结构
收尾页给串联线索：对象系统的 lru 字段直接通向淘汰策略那本 deck，数据结构的高效是单线程模型快的前提，紧凑编码影响 RDB 体积。跨领域的三条线值得反复体味：摊还分析、概率平衡、紧凑编码，Redis 的 dict 和 MySQL 的版本链、Kafka 的稀疏索引本质上是同一类工程思想。所有阈值和常量都能在上表列出的源码路径里找到，复习时按图索骥。