Redis底层数据结构全解析：SDS到跳表与编码机制

1. String 绕不开的 SDS从“字符数组”说起很多人一看到“Redis String”脑子里就浮现出一个 byte 数组甚至觉得它和 Java 的 String、C 语言的 char[] 没什么区别。这个理解在业务层面没错可真要聊底层数据结构Redis 压根没有直接用 C 字符串来保存键值而是维护了一套自己的动态字符串实现叫 SDS全称 Simple Dynamic String。这个“简单动态字符串”才是 String 类型真正的地基。Redis 底层为什么非得自己再造一个轮子C 语言的字符串以\0结尾获取长度得从头遍历复杂度 O(n)修改字符串要手动管理内存稍不注意就缓冲区溢出而且因为\0是终止符字符串中间一旦出现空字符后面内容就丢了。这在缓存二进制内容、图片数据、序列化后的对象时非常致命。Redis 是单线程处理命令的内存数据库任何不必要的遍历和内存拷贝都会被无限放大所以它必须用更可控的结构。SDS 的设计思路其实很像 Java 里的 ArrayList不直接暴露字符内容给外部而是带上一堆“元信息”。当前长度是多少、已经分配了多少容量、用哪种类型的头部、数据区在哪这些字段都被组织在头部里。操作字符串时先看头部能避免就避免重新计算长度需要扩容时直接按策略预分配减少内存重分配次数。SDS 的具体结构经历过一次比较大的版本调整。在 Redis 3.2 之前SDS 头部长得比较“死板”就是两个 int 字段加一个字符数组int len记录字符串长度int free记录剩余空间。不管存储 1 个字节还是 1MB 的数据每个字符串都要付出 16 字节的头部代价。对于大字符串这不算什么但对于几千万个小 key 的实例浪费就很明显了。Redis 3.2 之后把 SDS 改成了按长度分级的紧凑方案sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。数字代表 len 字段用多少位来存储。比如字符串长度不超过 255就只需要一个 uint8_t 长度的字段内存占用大幅下降。为了进一步榨干空间Redis 甚至在这些结构体上加了__attribute__((__packed__))避免编译器因为字节对齐塞入空洞。这里必须提一个新手非常容易踩坑的点C 语言结构体在内存里默认会对齐比如两个 uint8_t 和一个 char 理论上占 3 字节但编译器为了让后续四字节类型对齐可能塞成 8 字节。Redis 用 packed 强制按实际字段紧密排列然后通过SDS_HDR这类宏从字符串指针反推出头部起始位置。这样能做到“指针指到哪头部就在前边”代价是在某些平台访问未对齐内存时需要特别小心Redis 源码里也做了相应适配。SDS 还保证了二进制安全。它以 len 字段作为字符串边界而不是以空字符作为结束标志。因此内部存储任意二进制内容都不会失真。这一点对 String 类型来说极其重要你用 Redis 存一张图片、一个 protobuf 对象、一段加密后的内容底层其实都是 SDS 在默默兜底。既然 SDS 头部分了这么多种底层到底怎么识别当前字符串属于哪种类型答案就在 flags 字段里。flags 的低 3 位保存了 SDS 类型编号sdshdr5是 0sdshdr8是 1依次类推。sdslen、sdssetlen 这些函数先读 flags再决定按哪个头部去解析 len 字段。这层动态判断让 Redis 在处理不同长度的字符串时都能找到合适的头部而不是一刀切。2. String 的三种内部编码本质是“空间换性能”的三套方案搞清楚了 SDS再看 String 类型的编码就顺了。Redis 中对 String 对象并不只用一种办法存储它会根据值的形态和长度选择 int、embstr、raw 三种编码之一。你执行OBJECT ENCODING key看到的结果几乎都是这三种编码的组合。先看最简单的情况如果一个字符串能被解析成 long 型整数Redis 就不会真的分配字符串存储而是直接把整数值塞进 redisObject 的 ptr 字段里。redisObject 是所有 Redis 对象共用的头里面记录了 type、encoding、lru、refcount 指针等信息。在 64 位系统上这个对象一般是 16 字节ptr 字段本身就能装下一个 8 字节整型。把整数变成指针放进去虽然看起来有点“野”但 Redis 源码里确实就是这么干的因为这样整型计数器的内存开销极低。这种编码下 String 的最大优势是可以做原子自增操作。INCR、DECR、INCRBY命令直接操作整数值不需要先 GET 出来、再在客户端算好、最后 SET 回去天然避免并发覆盖问题。这也是很多人把 Redis 当分布式计数器用的底层基础。如果你存储的内容是10086实际底层编码就是 int你把它读回来后 Redis 协议层又会转成字符串返回从这个角度说编码形式对业务完全透明。再说embstr。当字符串长度在较短范围内时Redis 会把 redisObject 和 SDS以及字符串内容放在同一块连续内存里。具体来说在 64 位系统、新版 SDS 结构下创建对象时一次 malloc 就能申请一块足够大的内存redisObject 在最前面紧接着是 sdshdr8 头然后是字符串内容。如果用一句话概括embstr 是“一次分配三者连体”。这个连续布局对缓存非常友好。普通对象访问时redisObject 在内存这一边SDS 的 header 在另一边数据可能在第三块区域CPU 要跳好几次 cache line。embstr 则把整块数据紧凑放在一起读取时能够一次加载内存碎片也更少。这里有个关键限制当字符串长度超过一定阈值后Redis 就不愿意再做这种连续分配了。常见说法是 44 字节其实这个数值不是凭空拍出来的而是来自对 jemalloc 分配策略和 Redis 对象头的综合考量。jemalloc 对尺寸的处理类似“按档切分”64 字节以内是一档。embstr 想要一次分配成功就要让整体占用刚好控制在某个标准档位内。64 位系统下 redisObject 占 16 字节新版 sdshdr8 头占 3 字节数据后面还要留 1 字节给\0。16 3 内容 1 64算下来内容最多 44 字节。一旦超过这个长度Redis 更倾向于把对象的数据部分独立分配那就是 raw 编码。需要注意的是在 Redis 3.2 之前头部比较肥大当时 embstr 能支持的长度阈值是 39 字节左右很多老文章里的结论都是从旧版本推出来的容易误导人。raw 编码的逻辑也简单redisObject 和 SDS 分开存SDS 内部按字符串长度选择合适的 sdshdr 类型。刚创建的长字符串就直接走 raw另外 embstr 一旦被修改比如执行 APPEND也会立马转成 raw。原因很直接embstr 是连续内存的只读对象如果修改后长度变大得先把原来的整块内存重新分配再复制数据这个操作比直接换成一个独立的 raw 对象要昂贵得多。Redis 选择了一种更干脆的策略修改就降级。这一点引出了很多人在观察底层编码时的困惑为什么同一个前缀的 key有的值是 embstr有的却是 raw其实答案绕不开 Redis 的“预分配”策略。当你对一个 raw 编码的字符串执行 APPEND 时SDS 会预留额外空间一般不会只扩到刚好放得下而是会预分配一部分未来增长的空间。你可以用DEBUG SDSLOG之类的手段深入查看不过日常生产环境我不会建议你用 DEBUG 命令通过STRLEN和MEMORY USAGE也可以间接推断。3. ZSet 的复杂底色跳表与字典的组合拳String 聊完再来啃硬骨头 ZSet。ZSet 这个数据结构在业务里神出鬼没排行榜、延迟队列、滑动窗口限流、商品热度排序处处都有它的影子。可它的内部结构并不像 String 那么统一Redis 会根据数据规模在 listpack 和 skiplist 之间动态切换。当数据量小到一定程度时用一段紧凑的列表内存保存所有 member 和 score数据量上来后就切换成“字典 跳跃表”的组合结构。先来看主力形态skiplist 跳表加上 dict 字典。为什么 ZSet 需要两个结构因为外部需求是“既要按 member 快速查 score又要能按 score 范围遍历数据”。一个结构很难同时把这两件事做到高效。字典擅长精确查找你给我一个 member我 O(1) 级别返回它的 score但字典里的数据是无序的没办法做ZRANGEBYSCORE这种范围查询。跳跃表则擅长有序遍历能在 O(log N) 级别按分数找到起点然后沿着链表向后扫但要通过 member 去倒推 score 就非常慢。所以 Redis 干脆搞了“组合拳”dict 里存的是 member 到 score 的映射跳表里存的是按 score 排好序的完整节点。两个结构共享同一个 member 字符串和 score 数值不额外复制一份数据。插入一个元素时先往 dict 里加映射然后在跳表里定位合适位置插入节点删除时两个结构同时清理。这也是 ZSet 的写操作相比 List、Hash 要重一些的原因因为它每改一次两套索引都得同步维护。跳表到底是什么你可以把它想象成“多层的有序链表”。普通有序链表查找一个元素只能从头到尾走效率 O(n)。跳表在每个节点上额外抽出一些“索引节点”高层节点每次能跳过好几个数据节点查找时从最高层开始向下寻找层数越多一次能跨过的节点就越多。理想情况下跳表查询复杂度能做到 O(log N)最坏情况是 O(N)但通过随机层数策略几乎可以避免极端情况。Redis 里的每个跳表节点用 zskiplistNode 表示。里面有一个sds ele存储 member一个 double 类型的 score一个 backward 指针指向后一个节点还有一个 flexible array 指向 levels。每个 level 里包含两个部分前向指针 forward以及跨度 span。span 记录当前这一层能跨多少个节点别小看这个跨度ZRANK 命令之所以能算出成员排名靠的就是它自顶向下累加跨度。跳表层数的生成方式是纯概率的。每个新插入的节点等级从 1 开始每次有 1/4 的概率升一层直到达到最高层级限制。Redis 源码里定义的最大层级是 32概率因子 0.25。你可以把 1/4 理解成“每隔四个节点抽一个索引”。为什么不用 1/2概率越小高层节点越少索引文件占比也就更低内存更节省只是理论上高层搜索路径会稍微长一点。1/4 是工程实践里比较均衡的选择。说完跳表再说说“为什么用跳表而不是红黑树、AVL 树”。这个问题在 Redis 社区被讨论过很多次。红黑树和 AVL 树同样能保证有序范围查找也能做到 O(log N M)但实现复杂度和调试难度明显高得多。跳表的逻辑可以用几层循环写清楚插入删除时的局部调整非常直观而且对并发友好虽然 Redis 单线程模型不太需要利用这一点。再从内存角度看红黑树的节点颜色、父子指针会消耗额外空间跳表通过概率控制层级整体的内存消耗是可以预估的。还有一点容易被忽略Redis 的跳表在按 score 排序时并不只是比较 score 数值。如果两个 member 的 score 完全相同它还会按 member 的字典序二次排序。这个细节直接决定了你写入两个相同分数的元素时它们的相对位置并不一定是“谁先写谁在前”而是按字典序排列。所以自己在客户端做“同分时按时间排序”的逻辑时不能天真地依赖插入顺序。当 ZSet 里的数据量少到什么程度会启用紧凑结构默认情况下如果集合元素数量少于 128 个且每个 member 的长度不大于 64 字节Redis 会用 listpack 来编码整个 ZSet。listpack 是一种非常紧凑的线性结构把所有 member 和 score 首尾相接存成一条内存块。member 和 score 在 listpack 里成对出现比如 member1、score1、member2、score2依次排列。查询时就从这个列表里一个个找。很多人会问用 listpack 是否意味着 ZSet 操作是 O(n)确实listpack 编码下查找一个 member 只能线性扫描但因为数据量少128 个以内的元素线性扫描的开销几乎可以忽略不计。Redis 的目标是让每个底层数据结构在小数据规模下足够轻量所以它宁可用 O(n) 换来极高的内存紧凑度也不愿意为一个只有几个元素的集合就建一套完整跳表。listpack 替代的旧方案是 ziplist也就是压缩列表。老版本 Redis 的 ZSet、Hash、List 小体积场景都靠 ziplist 来压缩。ziplist 的设计本身就存在一个著名痛点级联更新。每个 ziplist 节点会记录前一个节点的长度如果前一个节点的长度发生变化后面的节点可能要不断调整极端情况下会引发连锁的扩容和数据搬移。listpack 改变了记录方式它不再记录前一个节点的长度而是给每个节点加了一个本地长度尾部标记这样某个节点变化时不会影响后续节点的存储布局从根上解除了级联更新问题。Redis 7.0 以后新版本默认用 listpack 替代了 ZSet 中的 ziplist。4. 用 OBJECT ENCODING 和 MEMORY USAGE 验证底层编码理解了这一堆理论不动手看一次总觉得不踏实。好在 Redis 给了我们一把非常直接的“透视镜”OBJECT ENCODING 命令。对任意现存 key 执行它就能看到当前对象的实际编码方式。举个最直观的例子在 Redis 里先塞一个整数再塞一小段字符串再塞一个超长字符串你会发现三种编码依次出现。127.0.0.1:6379 SET myint 9527 OK 127.0.0.1:6379 OBJECT ENCODING myint int 127.0.0.1:6379 SET myshort hello redis OK 127.0.0.1:6379 OBJECT ENCODING myshort embstr 127.0.0.1:6379 SET mylong aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa OK 127.0.0.1:6379 OBJECT ENCODING mylong raw我用几十个 a 组成的字符串来演示 raw 编码是因为它的长度已经超出了 embstr 的 44 字节阈值。实际项目中你可能会看到长度只有 50 左右的值就变成了 raw这是预期行为不用怀疑 Redis 出了问题。真正重要的是观察第一次创建后的编码只要你没对 key 做过修改操作编码基本能保持初始形态。再来看 ZSet 的编码切换。第一次把一个 ZSet 做成只有 3 个元素的集合时默认通常能看到 listpack如果你用ZADD快速灌入几千个元素再去查编码它已经变成了 skiplist。127.0.0.1:6379 ZADD myrank 100 a 200 b 300 c (integer) 3 127.0.0.1:6379 OBJECT ENCODING myrank listpack 127.0.0.1:6379 ZADD myrank 1 m1 2 m2 3 m3 4 m4 …此处省略大量添加命令 127.0.0.1:6379 OBJECT ENCODING myrank skiplist这里要提醒一句如果你的 Redis 版本是 7.0 以下看到的可能是 ziplist 而不是 listpack这完全正常。Redis 在小数据编码上经历了从 ziplist 到 listpack 的演进旧版本客户端和资料里说的 ziplist在今天的新版本里基本被 listpack 覆盖了。还要注意一个容易误导人的现象如果同一个 key 先设置成一个小整数后来又改变了内容编码类型也可能跟着变。比如127.0.0.1:6379 SET tmp 1 OK 127.0.0.1:6379 OBJECT ENCODING tmp int 127.0.0.1:6379 SET tmp 1a OK 127.0.0.1:6379 OBJECT ENCODING tmp embstr第一次能转成 int是因为字符串内容可以被解析成整数第二次内容里带了字母Redis 无法把它当作整型只能退回字符串存储。这种“动态降级”与版本无关属于编码选择机制务必理解。内存占用方面可以用 MEMORY USAGE 命令看看一个 key 总共占了多少字节。比如在 64 位实例上127.0.0.1:6379 SET num 1000000 OK 127.0.0.1:6379 MEMORY USAGE num (integer) 16 127.0.0.1:6379 SET text hello OK 127.0.0.1:6379 MEMORY USAGE text (integer) 56整型编码的 1000000 只占了 16 字节而一个 5 字节的嵌入式字符串却占了 56 字节。看到这个数字别惊讶因为 MEMORY USAGE 统计的是整个 redisObject 加上实际 SDS 和可能存在的缓存对齐一个小字符串还包含对象头所以并不像你想象的那么“小”。这把很多业务上的“节省内存”直觉打破了你不应该过分追求短 key短 key 的对象头开销反而更突出。内存分析对生产环境排查至关重要。如果某个缓存实例内存偏高你可以循环执行scan拿到 key 列表然后对每个 key 调用MEMORY USAGE把结果汇总成一张占用排行表。不过千万别在高峰期对几十万 key 做这操作MEMORY USAGE 本身有额外计算开销建议放到低峰期或者抽样执行。5. 常见问题与实战避坑记录我在实际排查和性能优化过程中把与 String、ZSet 底层结构有关的问题整理成了一份“避坑清单”。很多问题在网上聊得云里雾里但落到底层代码上答案其实很清晰。一个高频问题是为什么我的 member 不多、value 不长ZSet 编码却变成了 skiplist这种现象大概率是你改过 Redis 的配置。Redis 对 ZSet 使用紧凑结构的控制参数有两个维度一是最大元素数默认 128二是 member 的最大长度默认 64 字节。只要有一个条件不满足Redis 就会转为 skiplist。比如你向一个 ZSet 里塞入了一个 100 字节的 member哪怕整个集合只有 1 个元素它也会用跳表结构。第二个问题关于 String为什么我用 SET 存了一段非常短的文本但 OBJECT ENCODING 返回 raw这往往是因为 key 之前被 SET 过一个大字符串后来又把值改短。Redis 要不要把 raw 降级回 embstr答案是不会。raw 对象虽然可以复用原来的 SDS 空间但一旦使用过后续 set 新值可能并不会重新创建一个嵌入式对象而是继续沿用 raw 路径。即使业务上看起来只是简单覆盖底层编码也不会回到 embstr。想观察这个现象可以先设一个 1000 字节的字符串再 SET 成“hi”再查编码多半就是 raw。第三个问题比较隐蔽ZSet 的 score 是 double 类型有没有精度问题有。double 精度有限尤其是在超过 2^53 后连续的整数无法被精确表示。你插入 score 为 9007199254740993 的元素时底层的 double 存储可能变成 9007199254740992读出来的数值和你期望的不一样。做排行榜时如果 id 比较大且直接用 id 当 score极容易出现“分值错乱”。我的做法一般是把 score 限制在安全整数范围或者使用哈希映射后的小整数作为分数避免大整数直接进来。另一个高频问题来自版本差异。很多人搜到旧文章照着配置zset-max-ziplist-entries在 Redis 7.x 上却报“未知参数”于是怀疑配置写错了。实际上新版本引入了 listpack 编码后配置项已经改名比如zset-max-listpack-entries。如果你用的是 Redis 6.2 以上的版本尽量使用新的 listpack 配置参数。为了兼容旧脚本有些参数名会保留一个别名过渡期但新项目一定按新版本来写。在真实项目中我还遇到过“一个 String 类型 key 占用了异常大的内存”的案例。排查时发现某个业务不断对同一个 key 执行 APPENDSDS 扩容后空间没有及时释放。SDS 设计里有“惰性空间释放”机制字符串缩短时并不会立刻把多余的容量归还给内存分配器而是更新 len 字段把剩余空间留着后续再用。好处是减少了内存重新分配次数坏处是如果业务只缩短不重新填充内存里会残留大量空闲空间。生产上可以通过定期重写这个 key或者换一种数据结构缓存来把冗余内存释放掉。最后再给一个关于性能测试的建议判断 String 值和 ZSet 是否该换结构时不要只看命令耗时。单个命令在小数据量下都快得惊人真正要关注的是内存增长趋势。建议在压测环境用 debug 级的监控把mem_fragmentation_ratio、used_memory和key 数量拉出来做趋势分析。你会发现底层编码对内存碎片率影响非常大在小 value 场景下embstr 的连续分配优势会让碎片率更稳定而大 value 场景则更依赖分配器的表现。我用这套方法排查和优化过不少 Redis 集群。总体感受是Redis 的底层数据结构设计不是炫技每一项都有非常具体的收益考量。你在阅读源码时最好带着“如果我来实现会怎么处理”的问题去看比如 SDS 为什么要分级头部跳表为什么保留跨度。看懂了这些大部分面试题都能变成“从设计意图反推答案”而不是死记硬背。