Redis五种数据类型底层

String底层数据结构是SDS简单动态字符串SDS可以保存文本数据以及二进制数据C语言字符串不行SDS有变量监测字符串长度因此获取长度为O(1)SDS拼接字符串会自动扩容且会检查空间要求因此API安全不会造成缓冲区溢出ListRedis 的List结构为了平衡内存利用率和操作性能其底层实现经历了几次重大的架构演进。目前Redis 7.0List的核心底层结构是quicklist而 quicklist 的每个节点内部使用的是listpack。1. 早期ziplist linkedlist早期的 Redis 根据数据量大小在两种结构之间切换ziplist (压缩列表)当元素少且小时使用。它是一块连续内存非常省内存但由于是连续存储修改时可能触发“连锁更新”Cascade Update性能不稳定。linkedlist (双向链表)当数据量大时切换。每个节点独立虽然插入删除快但内存碎片严重且每个节点都要存prev和next指针额外空间开销巨大。为了结合两者的优点Redis 引入了quicklist。2. Redis7前quicklist ziplistRedis7前quicklist实际上是一个以ziplist为节点的双向链表。宏观上它是一个双向链表所以两端的LPUSH、RPUSH等操作复杂度是O(1)O(1)O(1)。微观上每个链表节点并不是只存一个元素而是存一个包含多个元素的“压缩块”。设计意图通过链表结构解决大块内存申请的困难。通过压缩块ziplist/listpack减少指针开销提高 CPU 缓存命中率。3. Redis7后quicklist listpack在 Redis 7.0 之后quicklist 内部的压缩块由ziplist全面升级为listpack。为什么 ziplist 被抛弃了ziplist 有一个致命缺陷连锁更新 (Cascade Update)。ziplist是压缩链表顺序表但每个元素长度不固定需要记录每个entry的长度在 ziplist 中每个 entryziplist中的一个元素 都会记录上一个 entry 的长度。如果上一个 entry 的长度稍微增加导致长度字段从 1 字节变成 5 字节那么当前 entry 的总长度就会变进而可能导致下一个 entry 也要变……这会导致O(N2)O(N^2)O(N2)的写性能崩溃。listpack 是如何解决的listpack同样是连续内存但它不再记录“上一个元素的长度”而是记录**“当前元素的长度”**。读取时通过当前元素的结尾标识可以反向计算出当前元素的起始位置。解耦一个元素的长度变化完全不会影响其他元素的长度字段从物理上彻底消除了连锁更新。4. 关键参数配置你可以通过配置来微调List的存储密度从而在内存和 CPU 之间寻找平衡点list-max-listpack-size控制每个 quicklist 节点即 listpack的大小。配置为负数如 -2表示限制字节数如 8KB。配置为正数表示限制元素个数。list-compress-depth压缩深度。如果 List 非常长中间的数据很少访问Redis 可以对 quicklist 中间的节点进行LZF 算法压缩进一步节省空间只保留两端节点不压缩。Hash目前Redis 7.0Hash 的底层主要由listpack和hashtable (dict)组成。1. 结构一listpack当你的 Hash 中字段Field较少且每个字段的 Value 都不大时Redis 会使用listpack。物理形式一整块连续的内存空间。存储逻辑每一个 Hash 的键值对在 listpack 中表现为相邻的两个 Entry前一个是 Field后一个是 Value。优势极致省内存由于内存连续且没有多余的指针开销它比传统的哈希表要省得多。缓存友好数据紧凑CPU 预取效率高。缺陷查询复杂度是O(N)O(N)O(N)。因为是连续内存寻找特定 Field 需要从头开始遍历扫描。2. 结构二hashtable (dict)一旦 Hash 的规模超过了预设阈值它就会“进化”为hashtable在源码中称为dict。物理形式由数组Buckets 链表解决哈希冲突组成。存储逻辑通过哈希函数计算Hash(Field)(modSize)Hash(Field) \pmod{Size}Hash(Field)(modSize)将数据映射到对应的桶位。优势真正的O(1)O(1)O(1)查找性能。无论你有 100 个还是 100 万个字段定位速度几乎一样。核心特性渐进式 rehash为了避免在扩容时一次性搬运海量数据导致 Redis “假死”dict内部会维护两个哈希表ht[0]和ht[1]。数据迁移不是瞬间完成的。每执行一次增删改查Redis 就顺手搬运几个桶的数据到新表。直到ht[0]搬空再彻底切换到ht[1]。3. 转换的“分水岭”Redis 默认通过两个配置参数来控制什么时候从 listpack 切换到 hashtable数量阈值hash-max-listpack-entries默认512个。大小阈值hash-max-listpack-value任一字段或值的字节数超过64。注意这种转换是单向的。一旦从 listpack 升级为 hashtable即便你删除了大量数据它通常也不会自动退化回 listpack除非通过reconstruct或重启加载 RDB。Set目前尤其是 Redis 7.2 版本之后Set 的底层实现由三种结构支撑intset、listpack和hashtable (dict)。1. 结构一intset整数集合——极致的内存压缩当你往 Set 里丢的数据全是整数且数量不多时Redis 会动用intset。物理形式一块连续的内存内部是一个有序的数组。核心特性自动升级Promotion它会根据存入整数的大小自动选择int16_t、int32_t或int64_t来存储。如果你存的是小数字它就用 2 字节存一旦混入一个大的它会瞬间把整个数组“升级”到 4 或 8 字节。注意不支持降级。性能查找采用二分查找复杂度为O(log⁡N)O(\log N)O(logN)。因为内存连续即使是O(log⁡N)O(\log N)O(logN)在小规模下也飞快。2. 结构二listpackRedis 7.2 引入的新宠在 Redis 7.2 之前只要 Set 里出现一个字符串或者整数多了就会直接跳到哈希表。现在的版本更细腻了如果数据量还不够大它会先用listpack顶一阵子。设计初衷替换掉在这种“尴尬规模”下过于臃肿的哈希表。存储逻辑和 List/Hash 里的 listpack 一样连续内存存储。触发条件当元素包含字符串或者整数数量超过intset限制但还没达到hashtable阈值时使用。3. 结构三hashtable (dict)当集合变得很大默认超过 512 个元素时Set 会演化为hashtable。物理形式标准的哈希表。巧妙之处Set 的哈希表其实就是把 Hash 类型的Value 置为 NULL。性能真正的O(1)O(1)O(1)查找。无论集合里有一万个还是十万个元素判断SISMEMBER的速度都是恒定的。ZSetRedis 的ZSet有序集合是 Redis 中最复杂、也最精妙的数据结构。它既要支持根据成员Member查找分数Score又要支持按照分数范围进行快速检索。1. 结构一listpack当 ZSet 的元素数量较少且每个元素的体积较小时Redis 使用listpack。物理形式一整块连续内存。排列逻辑元素和分数交替出现且按分数从小到大紧凑排列。[member1, score1, member2, score2, ...]性能查找和插入的复杂度为O(N)O(N)O(N)。但在数据量极小时默认 128 个以内其 CPU 缓存命中率极高实际表现非常出色。2. 结构二Skiplist Dict当 ZSet 变大时它会同时启用两个数据结构跳表Skiplist和哈希表Dict。A. 跳表 (Skiplist)负责“有序”跳表是 ZSet 的灵魂。你可以把它看作是一个支持二分查找的有序链表。实现原理在普通有序链表的基础上建立多层“索引”。查找过程先在高层“大步跳”迅速锁定范围再在底层“小步走”。性能平均查找、插入、删除复杂度均为O(log⁡N)O(\log N)O(logN)。为什么不用平衡树红黑树实现更简单跳表代码量更少。范围查询更强跳表底层是链表找到起点后直接向后遍历即可平衡树做范围查询需要复杂的跨分支搜索。B. 哈希表 (Dict)负责“查询”虽然跳表很快但如果你只想知道user:100的分数是多少ZSCORE命令在跳表里找依然需要O(log⁡N)O(\log N)O(logN)。实现原理维护一个member - score的映射。性能O(1)O(1)O(1)即可拿到分数。协作模式两者共同指向同一份成员和分数的内存对象。Dict 负责O(1)O(1)O(1)查分Skiplist 负责O(log⁡N)O(\log N)O(logN)范围检索。