浅记redis数据类型底层结构

Redis 数据类型底层结构一、总览不是简单的数据结构而是会变的Redis 的每个数据类型都有一个默认实现和一个阈值切换的轻量实现。数据少时省内存数据多时换高性能结构。Redis 类型 → 底层实现Redis 7.0 String → SDSSimple Dynamic String List → QuickListLinkedList ListPack 混合 Hash → ListPack小数据→ Dict大数据 Set → ListPack小数据→ Dict大数据 ZSet → ListPack小数据→ SkipList Dict大数据 Stream → RadixTreeRax Bitmap → SDS位操作 HyperLogLog→ Sparse → Dense Geo → ZSetSkipList Dict二、SDSSimple Dynamic String— 所有字符串的根基2.1 C 语言字符串的四大问题// C 原生字符串 char[]以 \0 结尾charstr[]hello;问题一O(N)取长度 — 必须遍历到 \0才知道多长 问题二缓冲区溢出 — strcat 不管目标够不够大 问题三二进制不安全 — 遇到 \0就认为结束了 问题四频繁修改 → 频繁 malloc/free → 内存碎片2.2 SDS 的结构Redis 3.2 分五档struct__attribute__((__packed__))sdshdr8{uint8_tlen;// 已用长度O(1) 获取uint8_talloc;// 总分配空间不包括 header 和 \0unsignedcharflags;// 低 3 位表示 SDS 类型charbuf[];// 实际数据 隐含 \0};// 五种 SDS 类型按长度自动选择// sdshdr5 (len 32B) — 不存 alloc省内存// sdshdr8 (len 256B) — 8 位 len/alloc// sdshdr16 (len 64KB)// sdshdr32 (len 4GB)// sdshdr64 (len 4GB)2.3 SDS 的四个核心优势优势一O(1) 取长度 — 读 len 字段不用遍历 优势二杜绝缓冲区溢出 修改前先检查 alloc → 不够自动扩容 → 永远不会溢出 优势三内存预分配减少 malloc 次数 len 1MB → 新 alloc len × 2 len ≥ 1MB → 新 alloc len 1MB 下次 append 如果还在 alloc 范围内 → 不需要重新分配 优势四惰性释放减少 free 次数 trim 操作不释放内存只改 len 等下次真的需要空间时再看要不要回收直观对比 操作append(s, world) 100 次每次加 5 字节 C 字符串 每次都要 realloc → 100 次系统调用 SDS 第一次 alloc 10第二次 20第四次 40... 100 次 append 可能只触发了 10 次 realloc 减少 90% 的内存分配三、Dict字典— Redis 的核心中的核心Redis 数据库本身就是一个大 Dictkey → valueHash 类型底层也是 Dict。3.1 结构typedefstructdict{dictType*type;// 类型特定函数hash 函数、key/value 复制等dictEntry**ht_table[2];// 两个 hash 表渐进式 rehash 的关键unsignedlonght_used[2];// 每个表的使用量longrehashidx;// -1 表示不在 rehash0 表示正在 rehashint16_tpauserehash;// rehash 暂停计数}dict;typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;doubled;}v;// union 省内存structdictEntry*next;// 拉链法解决哈希冲突头插快}dictEntry;3.2 渐进式 rehash — 核心亮点普通 hash 表的 rehash ht[0]1GB→ ht[1]2GB→ 一次性 copy 全部数据 → 阻塞主线程几百毫秒 Redis 是单线程阻塞几百毫秒 服务不可用 Redis 的渐进式 rehash 1. 创建 ht[1]大小是 ht[0] 的 2 倍 2. 设置 rehashidx 0 3. 每次读/写操作顺带把 ht[0][rehashidx] 迁移到 ht[1] 4. rehashidx直到所有桶迁移完 5. 把 ht[1] 设为 ht[0]释放旧的 ht[0] 这期间 - 读先查 ht[0]没找到再查 ht[1] - 写直接写 ht[1] - 删先删 ht[0]再删 ht[1] 迁移平摊到每次操作 → 每次操作多几微秒 → 不会卡住渐进式 rehash 的触发条件 扩容used / size 1 且没有执行 BGSAVE/BGREWRITEAOF used / size dict_force_resize_ratio (默认 5) 缩容used / size 0.1四、List — QuickList4.1 演进历史Redis 3.2 之前 List → ziplist数据少 或 linkedlist数据多 问题linkedlist 每个节点都要 malloc → 内存碎片严重 Redis 3.2 之后 List → QuickList QuickList 双向链表但每个节点是一个 ziplist/listpack4.2 QuickList 结构QuickList head ─→ [listpack 1] ←→ [listpack 2] ←→ [listpack 3] ←─ tail │ │ │ a,b,c d,e,f g,h,i 为什么这样设计 纯链表 每个元素一个节点 → 100 个元素 100 次 malloc 指针开销大 → 但插入/删除快 纯 ziplist 所有元素挤在连续内存 → 100 个元素 1 次 malloc → 但插入/删除要移动大量数据 QuickList 折中 — 每个 listpack 存 N 个元素 → malloc 次数 100/N比纯链表少 N 倍 → 插入删除只影响 1 个 listpack比纯 ziplist 快 → N 可调redis.conf 里的 list-max-listpack-size4.3 ListPackRedis 7.0 替代 ZiplistListPack 相比 Ziplist 的关键改进 Ziplist 的问题 每个元素存 prevlen前一个元素的长度 前一个元素变大 → prevlen 也需要扩容 → 连锁更新 → O(N²) ListPack 不存 prevlen 改在元素结尾存当前元素的总长度 逆序遍历时从末尾往前读 → 彻底消灭连锁更新 列表的中间插入从 Ziplist 的 O(N²) 降到 O(N)五、Hash — ListPack → Dict数据少时用 ListPack1 次 malloc紧凑存储 key1→val1→key2→val2→key3→val3 交替排列 数据多时换成 Dict 触发阈值 hash-max-listpack-entries 512 超过 512 个 field hash-max-listpack-value 64 任一 value 超过 64 字节 为什么切换 ListPack O(N) 查找 → 100 个 field 还行10000 个就慢了 Dict O(1) 查找 → 10000 个 field 也差不多快六、Set — ListPack → Dict小 SetListPack去重靠遍历元素少成本低 大 SetDictkey 存元素值value 为 NULL天然去重 切换阈值 set-max-listpack-entries 128 set-max-listpack-value 64七、ZSetSorted Set— 双结构协同ZSet 最特殊同时用 SkipList Dict 两个结构。7.1 为什么要两个结构需求一按分数查排名 → SkipList 天然有序 需求二按成员查分数 → Dict O(1) 直接查 只用 SkipList 按分数查排名 → 快 按成员查分数 → 要遍历O(N) ❌ 只用 Dict 按成员查分数 → O(1) 快 按分数查排名 → Dict 无序没法查 ❌ 所以两个都要 Dict 存成员 → 分数 SkipList 存分数 → 成员按分数排序 两个结构共享同一个对象指针 → 不占双倍内存7.2 SkipList跳表普通链表查找1→2→3→4→5→6→7→8 O(N) 跳表查找 第3层 1 ──────────→ 5 ──────────→ 8 第2层 1 ───→ 3 ───→ 5 ───→ 7 ───→ 8 第1层 1→2→3→4→5→6→7→8 查找 7 第3层从 1→5 跳过去5→8 过头了下降 第2层从 5→7找到了 一共访问了 3 个节点 vs 链表要访问 7 个节点 O(logN) ✓ 跳表 vs 红黑树 跳表实现简单不到 200 行代码 跳表支持范围查询找到起点后顺着链表走 跳表的层高是随机的插入时掷硬币决定7.3 ZSet 在数据少时的优化小 ZSetListPack 数据少时跳表字典的开销不值得 阈值zset-max-listpack-entries 128 zset-max-listpack-value 64八、Stream — RadixTreeRaxStream 的消息 ID 是 时间戳-序号例如 1680000000000-0 RadixTree 是什么 压缩前缀树 — 合并只有一个子节点的路径 不压缩的 trie 1→6→8→0→0→0→0→0→0→0→0→0→0 RadixTree 1680000000000 整个路径压缩成一个节点 内存省了 N 倍性能不变九、底层切换策略汇总类型少量数据大量数据切换阈值配置StringSDS(8/16/32/64)同无自动选 SDS 类型ListQuickList同list-max-listpack-sizeHashListPackDicthash-max-listpack-entries/valuesSetListPackDictset-max-listpack-entries/valuesZSetListPackSkipListDictzset-max-listpack-entries/valuesStreamRadixTree同无十、设计的核心思想Redis 底层设计的三个核心思想 思想一小数据用紧凑结构大数据换高性能结构 → 你只有 10 个 hash field 时不需要 Dict → 超过阈值自动切换 思想二用空间换时间但控制成本 → ZSet 双结构SkipList Dict多占一点内存换两种操作都是 O(logN) → SDS 预分配用多 50% 内存换 append 减少 90% 的 malloc 思想三避免主线程被阻塞 → 渐进式 rehash 不卡主线程 → ListPack 替代 Ziplist 避免连锁更新 → 所有操作 O(N) 时都有N 太大就切成多个小操作的保护十一、总结String → SDS → O(1) 长度 预分配 惰性释放 List → QuickList → 链表 紧凑列表的折中 Hash → Dict → 渐进式 rehash永不卡顿 Set → Dict → key 存元素value 为 NULL ZSet → SkipListDict → 双结构互补排名查找都是 O(logN) Stream → RadixTree → 压缩前缀树省内存 Geo → ZSet → 坐标用 Geohash 编码成 score 核心心法 小数据 省内存 大数据 高性能 单线程 不能卡