Appearance
数据类型与底层编码
看在前面
这是 Redis 板块的「数据结构篇」。系列姊妹篇：缓存穿透-击穿-雪崩、持久化-RDB与AOF、过期删除与内存淘汰、高可用与部署选型-主从哨兵与集群。
面试官问「Redis 有哪些数据类型」，从来不是想听你背九个名词。他想听的是三层东西。命令语义（这个类型干什么用）→ 底层编码（数据结构功底）→ 编码何时转换（内存与性能的权衡意识）。能把 SDS、跳表、listpack 讲出「为什么这么设计」，这轮才算过关。
开场先把一个认知立住：类型是命令语义层的抽象，编码才是真正的底层结构。Bitmap 底层是 String，GEO 底层是 ZSet——第一分钟就把这句说出来，面试官会立刻坐直。每个 key 当前的编码用 OBJECT ENCODING key 查看，编码由写入的数据形态自动决定，不能手动指定。
一张总图：九大类型与编码全景
| 类型 | 底层编码 | 转换条件（默认阈值） | 典型场景 |
|---|---|---|---|
| String | int / embstr / raw | 整数值 → int；≤44 字节 → embstr；更长 → raw | 缓存 JSON、计数器、分布式锁 |
| List | quicklist（节点为 listpack） | list-max-listpack-size 控制每节点大小 | 时间线、消息列表、安全队列 |
| Hash | listpack → hashtable | 元素 ≤128 且 value ≤64 B 用 listpack | 对象属性缓存、购物车 |
| Set | intset → listpack → hashtable | 全整数且 ≤512 用 intset；7.2+ 小集合用 listpack | 去重、标签、共同关注 |
| ZSet | listpack → skiplist + dict | 元素 ≤128 且 member ≤64 B 用 listpack | 排行榜、延迟队列、范围检索 |
| Bitmap | 就是 String（SDS 按位使用） | —— | 签到、活跃位图、布隆过滤器 |
| HyperLogLog | 稀疏/稠密编码，上限固定 12 KB | 元素极少时稀疏编码 | 亿级 UV 基数统计 |
| GEO | 就是 ZSet（geohash 52 bit 作 score） | 同 ZSet | 附近的店、附近的人 |
| Stream | 基数树（radix tree）挂 listpack 节点 | —— | 消费组语义的轻量 MQ |
两个版本分水岭要主动讲。3.2 引入 quicklist 统一 List 的两种旧编码；7.0 用 listpack 全面替换 ziplist（List/Hash/ZSet 换血，ziplist 从源码删除）。7.2 起 Set 的小集合也走 listpack。分得清「哪个版本发生了什么」，面试官会默认你读过源码。
String 与 SDS：一个结构体答四个考点
面试官：Redis 的字符串为什么不用 C 的 char[]，SDS 好在哪？
SDS（Simple Dynamic String）核心字段以 sdshdr8 为例。头部长度按内容规模分 sdshdr5/8/16/32/64 五档，小字符串配小头部，本身就是省内存的设计：
c
struct sdshdr8 {
uint8_t len; // 已使用字节数
uint8_t alloc; // 分配的总字节数（不含头部和结尾 \0）
unsigned char flags; // 低 3 位标记头部类型
char buf[]; // 内容，末尾仍补 '\0' → 可复用一部分 C 字符串函数
};对比 C 字符串，四个考点逐条对答：
- O(1) 取长度：
STRLEN直接读 len，C 字符串要 O(N) 扫到\0； - 二进制安全：以 len 判定结尾而不是
\0，可以存图片字节、序列化对象。SDS 是「字节数组」而非「字符串」； - 杜绝溢出 + 减少重分配：拼接前 API 自动检查剩余空间。扩容策略是小于 1 MB 翻倍、达到 1 MB 后每次加 1 MB。缩短时不立即归还内存（惰性释放），留待复用；
- 均摊 O(1) 追加：预分配让连续 APPEND 的重分配次数按指数衰减。这是对「写多」场景的定向优化。
String 的三种编码与 44 的由来
- int：值是 long 装得下的整数（不超过 19 位），直接把整数存进 redisObject 的 ptr，连 SDS 都省了——
INCR计数器快就快在这； - embstr：≤44 字节。redisObject（16 B）+ sdshdr8 头（3 B）+ 内容 + 结尾
\0恰好塞进一次 64 B 分配（对 jemalloc 尺寸友好），只读。一旦修改（APPEND/SETRANGE）无法局部扩容，直接降级为 raw； - raw：>44 字节，redisObject 和 SDS 分两次分配。
场景与坑：计数器/限流（int 原子 INCR）、分布式锁（SET NX EX，见缓存穿透-击穿-雪崩的互斥重建）、对象 JSON 整存整取。坑：把一个 500 字段的大对象整体 JSON 塞进 String，就是典型 BigKey——应转 Hash 按字段存，或按业务拆 key。
List：quicklist —— 两种旧结构的合体
3.2 之前 List 有两种编码。元素少用 ziplist（紧凑省内存，但追加触发整块 realloc 搬移）。大了用 linkedlist（两端 O(1)，但每节点两个指针 + 碎片）。quicklist = 以 ziplist/listpack 为节点的双向链表，两头的好处都占：
quicklist（双向链表）
head ⇄ [ listpack 节点1: e1|e2|e3 ] ⇄ [ 节点2: e4|e5 ] ⇄ [ 节点3: e6 ] ⇄ tail
↑ 中间插入只影响单个节点，节点内部连续紧凑存储list-max-listpack-size：正数 = 每节点最多元素个数；负数 = 每节点字节上限（-1=4 KB，-2=8 KB 默认，最大 -5=64 KB）。节点越小链表指针越多、越不省内存；节点越大单次操作越接近整块搬移的成本——参数化的折中。
为什么 7.0 用 listpack 替换 ziplist（高频追问）
ziplist 每个 entry 记录前一项长度 prevlen。前一项从 253 字节涨到 254 时，prevlen 从 1 字节膨胀为 5 字节。这迫使后一项跟着改写，极端情况逐项传导到块尾（级联更新）。listpack 每项只存「自己的长度 + 结束标记」，改任何项都不影响邻居——级联更新从结构上根除。这也是为什么 7.0 敢把 Hash/ZSet/List 的紧凑编码全部切到 listpack。
场景：最新动态时间线（LPUSH + LRANGE）、简单队列（LPUSH + BRPOP；要可靠消费用 6.2+ 的 LMOVE src dst LEFT RIGHT 双队列备份）。
Hash 与 Set：紧凑编码与渐进式 rehash
Hash：小 Hash 用 listpack（hash-max-listpack-entries 128、hash-max-listpack-value 64），field/value 紧挨着存；超限转 dict（hashtable）。dict 的考点是渐进式 rehash。扩容要建 2 倍桶并全量搬移，一次性做会卡顿主线程。于是 dict 同时持有 ht[0]/ht[1] 两张表加 rehashidx 游标：
扩容触发（元素数 ≥ 桶数）后：
查找：先查 ht[0]，miss 再查 ht[1] ← 两张表都要看
新增：只写 ht[1] ← ht[0] 只减不增
搬移：每次增删改顺手搬一小批桶，rehashidx 前移，搬完释放 ht[0]细节加分：bgsave / AOF 重写子进程存在期间，Redis 暂停 rehash。搬移会改写内存页，而 fork 的 COW 下每页改动都意味着物理页复制（见持久化-RDB与AOF的 COW 一节）。
Set：全整数且元素 ≤512（set-max-intset-entries）用 intset——升序整数数组、二分查找。按最大整数自动升级 int16→int32→int64 编码（只升不降）。7.2 起小规模非整数集合先走 listpack 省内存，大了转 hashtable（值存 NULL 的 dict，只存 key）。
场景：Hash 存购物车（HINCRBY cart:uid skuId 1）可单字段读写、省掉整对象反序列化；Set 做共同关注（SINTER）、抽奖（SPOP）、标签去重。
ZSet：跳表 + dict 双结构，为什么不用红黑树
面试官：ZSet 底层是什么？为什么用跳表不用红黑树？
小 ZSet 用 listpack（member/score 依次紧排，≤128 项且 member ≤64 B）。大了以后转的不是单一结构，是双结构：
c
typedef struct zset {
dict *dict; // member → score：ZSCORE 这类点查 O(1)
zskiplist *zsl; // score 有序的跳表：ZRANGE/ZRANK 这类范围/排名 O(logN)
} zset;单独的 dict 没法按 score 范围查，单独的跳表点查是 O(logN)。两者组合、元素（sds）共享，用可接受的内存增量换来「点查 O(1) + 范围 O(logN)」全都要。这是「按命令访问模式选结构」的教科书案例，面试时要主动点破。
跳表本身（多层有序链表，高层是低层的快速通道）：
level 3: head ───────────────────────────────► 50 ──────────► NIL
level 2: head ─────────► 20 ─────────────────► 50 ──────────► NIL
level 1: head ─► 10 ───► 20 ───► 30 ─────────► 50 ─► 70 ───► NIL
level 0: head ─► 10 ───► 20 ───► 30 ───► 40 ─► 50 ─► 70 ───► NIL ← 双向，可反向遍历
查找 40：L3 走到 50 超了退回 → L2 到 20 → L1 到 30 → L0 命中 40实现细节说两个就够。每层晋升概率 ZSKIPLIST_P = 0.25、最高 ZSKIPLIST_MAXLEVEL = 32，平均每节点 1/(1-0.25) ≈ 1.33 个指针。每个前向指针带 span（跨度），沿途 span 累加即排名——ZRANK/ZREVRANK 因此是 O(logN)。
为什么不是红黑树，按这四条答：
| 维度 | 跳表 | 红黑树 |
|---|---|---|
| 范围查询 | 定位起点后沿 level-0 链表直接遍历，天然契合 ZRANGE | 要中序回溯（栈/父指针），实现别扭 |
| 实现复杂度 | 插删只改前后指针，无旋转无变色 | 旋转 + 变色，边界条件多 |
| 内存 | 平均 1.33 指针/节点（P=0.25 刻意压低） | 2 指针/节点 + 父指针 + 颜色位 |
| 排名功能 | span 天然支持 rank | 需额外维护子树大小 |
结论句：ZSet 的核心操作是按 score 的范围与排名，跳表在这两件事上更简单、内存更省。红黑树的优势（严格平衡、最坏 O(logN) 保证）对 ZSet 场景没有增量价值。antirez 还补过一般性理由：跳表更细的锁粒度对并发实现友好。Redis 单线程用不上，但说明你理解一般性权衡。
Bitmap / HyperLogLog / GEO / Stream：四个「复用已有编码的类型」
- Bitmap：底层就是 String，
SETBIT直接改 SDS 某字节位。1 亿用户日签到100_000_000 / 8 ≈ 12MB。SETBIT/GETBIT/BITCOUNT/BITOP 组合能做签到、连续活跃，以及缓存穿透-击穿-雪崩里的布隆过滤器（SETBIT + 多哈希）； - HyperLogLog：固定 12 KB、标准误差 0.81%——16384 个桶、每桶 6 bit 记最大前导零，调和平均出基数。
PFADD/PFCOUNT/PFMERGE。统计 UV 这类「允许近似、量级巨大」的场景是绝配；要精确就得用 Set，内存翻几个数量级； - GEO：底层就是 ZSet，经纬度编码成 geohash 52 bit 整数当 score，
GEOSEARCH实质是按 score 区间检索再换算距离； - Stream（5.0+）：基数树挂 listpack 消息块，支持消费组、ACK、pending 重投。这是「想要 Kafka 语义又不想引入 Kafka」时的轻量选择；但它的可靠性受持久化机制约束（见持久化-RDB与AOF）。
BigKey：每种类型都会踩的雷
BigKey 不是 String 专属——集合元素过多同样是 BigKey。常用判定线（阿里规范口径）：String value > 10 KB，集合元素 > 5000，就值得治理。
五宗罪（每条都有事故画面）：
- 阻塞主线程：DEL 一个百万元素的集合是 O(N)，主线程卡几百毫秒到秒级。所有请求排队。要用
UNLINK异步删除（见过期删除与内存淘汰）； - 打爆网卡：1 MB 的 value × 1000 QPS ≈ 1 GB/s 出口流量，单分片被打满，其他 key 陪着抖；
- 集群倾斜：一个 key 只能落在一个槽、一个节点。槽位原理见高可用与部署选型-主从哨兵与集群。热 + 大叠一起就是单节点内存/带宽双杀；
- 内存不均：槽迁移、扩容时该节点成为长尾；
- 过期/淘汰被拖累：大 key 到期一次性释放同样卡顿。
发现与治理四件套 + 三板斧
bash
# 1. 在线抽样发现（低峰跑，输出每个类型的 TOP N）
redis-cli --bigkeys
# 2. 精确测量单个 key（含内嵌结构开销）
MEMORY USAGE product:1001
# 3. 离线全量：对 RDB 快照做离线扫描（rdb-tools / redis-rdb-cli），不影响线上
# 4. 在线遍历一律 SCAN 游标分批，永远不要 KEYS *治理三板斧。拆：大 String 转 Hash 分桶、大集合按 id 取模拆 N 个子 key。压：value 先 snappy/kryo 压缩再存。限：必配 TTL + 写入口约束字段数。删除与迁移用 UNLINK / MIGRATE 并安排低峰。
追问链
面试官：embstr 为什么一改就变 raw，不还原？
embstr 是一次内存分配的整体（robj 与 SDS 连续存放），无法局部 realloc，修改必然整体重分配。它本来就是为「小而只读」优化的，回不去符合设计预期——「embstr 只读」本身就是考点。
面试官：渐进式 rehash 期间 key 分散在两张表，遍历怎么办？
SCAN 的游标做「反向二进制迭代」，按桶号倒序跳跃，配合 rehash 的搬移方向保证不重不漏。期间可能返回重复 key，客户端需去重。把 SCAN 和 rehash 连起来答，是隐藏加分点。
面试官：跳表层数怎么定？为什么 P=0.25 不是 0.5？
插入时随机掷点，每层以 0.25 概率继续晋升。P 越小平均层数越低、指针越省、查询常数项越大——0.25 是「内存 vs 查询代价」的折中（1.33 指针 vs 0.5 时的 2 指针）。
面试官：这几个类型在你们项目里怎么用的？
提前备一张自己的映射表。String=token/计数器、Hash=购物车/商品属性、ZSet=排行榜/延迟队列、Set=共同关注/去重、Bitmap=签到、HLL=UV。有真实场景的答案比背书强 10 倍。
面试官视角小结
- 总起：类型是语义、编码是底层，
OBJECT ENCODING现场看。主动交代 3.2 quicklist、7.0 listpack 替换 ziplist 两个版本点； - SDS 四考点：O(1) len、二进制安全、预分配/惰性释放、五档小头部。int / embstr(44 B，只读) / raw 三编码与 44 的由来；
- List/Hash/Set：quicklist = listpack 节点的双向链表。listpack 靠「只记自己长度」根除 ziplist 级联更新。渐进式 rehash 两表协作、持久化子进程期间暂停。intset 只升不降；
- ZSet：dict + skiplist 双结构（点查 O(1)、范围 O(logN)）。不用红黑树四条：范围查询、实现简单、1.33 指针省内存、span 天然支持排名；
- BigKey：五宗罪 + 发现四件套（--bigkeys / MEMORY USAGE / RDB 离线分析 / SCAN）+ 治理三板斧（拆/压/限）。
2026-10 新增（P0 补全）。