第一篇：Redis数据结构底层——String、List、Hash、Set、ZSet各自用什么实现的？

第一篇Redis数据结构底层——String、List、Hash、Set、ZSet各自用什么实现的第二篇Redis的过期删除与内存淘汰——数据过期了怎么删内存满了怎么办前言你可能每天都在用Redis的String、List、Hash、Set、ZSet但面试官追问到底层时很多人就答不上来了“Redis的String和Java的String是一回事吗”“List底层是链表还是数组”“ZSet怎么实现O(log n)排序的”“为什么Redis不直接复用C语言的原生数据结构”这些问题考察的不是会用而是理解设计意图。本文从底层实现的角度逐个拆解Redis五大基本数据结构的内部原理。本文核心问题Redis的String底层是什么SDS和C字符串有什么区别List的底层经历了怎样的演进ziplist、linkedlist、quicklist分别是什么Hash的底层有两种实现什么时候用ziplist什么时候用hashtableSet和ZSet各自的底层结构是什么为什么ZSet能排序为什么Redis要自己实现一套数据结构而不是复用C语言自带的读完本文你将对Redis数据结构拥有从使用到实现的完整理解。一、Redis为什么自建数据结构疑问C语言有原生的字符串和数组Redis为什么不直接用回答C语言的原生数据结构有两个致命缺陷——字符串操作不安全、内存管理不灵活。Redis自己实现的数据结构第一优先级是快第二优先级是省内存。C语言的字符串本质是一个char[]数组以空字符\0结尾。获取长度需要遍历整个数组这是一个O(n)操作——Redis每次获取键长都要遍历一遍不可接受。C字符串存二进制数据时遇到\0就会被截断——Redis的网络协议传输的是二进制安全的批量数据不能依赖C字符串。C的数组不记录实际元素数量每次检查长度又是O(n)。更重要的是C结构体的内存布局是对齐的Redis需要紧凑的存储结构来节省内存——数百万个小Key如果用标准结构体内存碎片和对齐开销会让实际内存占用是实际数据的数倍。Redis的解决思路为每种数据结构设计专门的底层实现所有结构都额外记录一个当前长度字段——获取长度变O(1)二进制安全也能保证。这就是SDS、ziplist、skiplist等专用数据结构的来源。二、String——SDSSimple Dynamic String疑问Redis的String到底存了什么和Java的String有什么不同回答Redis的String底层是SDS——一个自描述的动态字符串结构它在C字符串的基础上增加了长度记录、缓冲区预分配、二进制安全三个关键能力。SDS的结构如下structsdshdr{intlen;// 已使用的字节数intfree;// 未使用的字节数预分配空间charbuf[];// 实际的字节数组};SDS和C字符串的核心区别能力C字符串SDS获取长度O(n)遍历O(1)直接读len字段缓冲区溢出可能发生不检查边界自动扩容不会溢出内存分配每次修改都要重新分配预分配空间减少分配次数二进制安全不安全遇到\0截断二进制安全使用len字段确定长度为什么需要二进制安全Redis存储的不仅仅是文本。一个序列化后的Java对象可能包含多个内部\0字节。C字符串读到第一个\0就停了——后面的数据全部丢失。SDS用len字段指明数据的实际长度不依赖空字符终止符所以能够存储包括图片、序列化对象在内的任意二进制数据。预分配空间——减少内存分配次数Append操作在C字符串中是灾难。每次追加world到hello后面都要重新分配内存新长度1。如果反复追加100次就要分配100次内存。SDS的预分配策略当增后长度小于1MB时分配2倍的空间free len 1下次追加大概率不需要再分配。当增后长度大于等于1MB时每次分配多预留1MB。这是用有限的内存换取更少的分配次数——Redis是内存数据库省掉分配带来的时间收益远超多用的少量内存。三、List——从linkedlist到quicklist的演进疑问List底层是链表还是数组为什么Redis的List可以两端插入回答Redis的List底层经历了三次演进——早期用linkedlist或ziplist互斥选择后来用quicklist统一两者优势。linkedlist版本早期标准的双向链表每个节点独立分配内存。两端插入和删除的时间复杂度是O(1)但每个节点都需要前驱和后继指针内存开销大——一个只存10字节数据的节点两个指针占16字节内存使用率还不到40%。此外链表的节点在内存中不连续存储CPU缓存在顺序遍历时大量miss性能不支持日常中大规模的顺序读取。ziplist版本省内存ziplist是一种连续内存块的压缩结构——把所有元素紧凑排列在一整块连续内存中没有任何额外的指针。它依赖当前元素长度字段自动步进到下一个元素。内存利用率大幅高于链表适合小数据量场景但中间插入或删除一个元素后面的所有元素都要整体往后移动——这个特质决定了它只适合元素较少且操作仅在两端的场景。quicklist版本Redis 3.2quicklist将linkedlist和ziplist结合——它是一个双端链表但每个节点内部不再是一个元素而是一段ziplist。两端操作快速定位到head或tail节点中间操作可在这段ziplist内完成。元素较多时一段ziplist被限制在一定大小内中间插入的影响只局限于这段子列表不会波及整个列表。quicklist结构 [head] ←→ [Node(ziplist)] ←→ [Node(ziplist)] ←→ [tail] ↓ ↓ 连续内存存3-4个元素 连续内存存3-4个元素选择逻辑少量元素 → ziplist节点省内存两端操作也快大量元素或中间插入频繁 → quicklist兼顾内存和效率四、Hash——两种底层实现疑问Hash底层是什么结构和Java的HashMap一样吗回答Redis的Hash有两种底层实现——字段较少时用小而紧凑的ziplist字段较多时转为标准的hashtable。这个阈值可以通过配置文件调整。小Hash用ziplist当Hash中的字段数 512且每个字段的值长度 64字节时Hash用ziplist存储。使用方式和List类似键和值被压缩排列在连续内存中没有任何指针开销。ziplist存Hash [field1][value1][field2][value2][field3][value3]...大Hash用hashtable当字段数量或值的长度超过阈值时Hash自动升级为hashtable——类似Java的HashMap是一个数组链表的拉链结构。但Redis的hashtable使用了渐进式rehash——一次性rehash大数据量时可能阻塞其他命令所以Redis会把rehash过程分散到后续的多次操作中每次处理一部分逐渐完成迁移同时不影响正常命令的响应时间。为什么需要两种实现一个用户对象可能只有3个字段name、age、email用标准hashtable存储时数组和指针的开销比数据本身还大。ziplist把三个字段紧凑排在一块内存中省掉所有指针和元数据。一个购物车Hash可能有几千个商品ID和数量ziplist的线性查找和插入性能在元素过多时变差降级为hashtable保证操作性能。这是Redis用空间换时间或用时间换空间选择的具体体现。小数据量时内存优先ziplist大数据量时性能优先hashtable。阈值的选择是两者成本和受益的平衡点——512个字段×64字节≈32KB这是现代CPU缓存的舒适区。五、Set——有序还是无序疑问Set的底层是什么为什么Set能快速判断元素是否存在回答Set有两种底层实现——当所有元素都是整数时用intset有序整数集否则用hashtable存键不存值。intset当Set中全部元素都是整数且数量不超过512时用intset存储。intset是一个有序的、不重复的整数数组——查找可以用二分查找O(log n)不需要hashtable的完整桶结构。hashtable当Set中包含非整数元素或整数数量超过阈值时升级为hashtable。每个Set元素是hashtable中的一个键值全为NULL——只使用hashtable的键结构不存储实际值。键去重的特性天然满足Set元素不重复的约束。六、ZSet——有序集合的排序秘密疑问ZSet是怎么做到O(log n)排序的为什么能同时按score排序和按member查找回答ZSet同时使用两种数据结构——skiplist跳表按score排序hashtable按member快速查找。两种结构各自解决一个问题ZSet把两者组合使用。skiplist——概率型数据结构level 3: 1 ──────────────────→ 9 level 2: 1 ──────→ 5 ──────→ 9 ──→ 12 level 1: 1 → 3 → 5 → 7 → 9 → 10 → 12 ↑ 高层指针跨越多级低层精确步进skiplist是一个多层链表底层是完整的所有元素的链表每往上一层只保留部分元素但跨越的元素更多。查找时从高层开始粗略定位逐步下到低层精确命中——平均时间复杂度O(log n)与平衡树相同但代码比平衡树简单得多。这是概率型数据结构——每层保留哪些元素在插入时用随机数决定。不需要平衡树那么多的旋转和再平衡操作也不需要递归遍历或栈来定位前驱后继。为什么不用红黑树红黑树的O(log n)同样高效。但在Redis中ZSet需要频繁的范围查询ZRANGE score1 score2——skiplist的链表结构天生适合找到起点顺序遍历红黑树遍历一段区间需要反复访问父指针回到上层。范围查询是ZSet的核心功能skiplist的遍历模式比红黑树更适合这个操作模式。七、底层选择速查表数据类型小数据量大数据量选择逻辑String—SDS动态扩容预分配空间二进制安全Listziplistquicklist内存优先→性能优先Hashziplisthashtable字段512且值64B→ziplistSetintsethashtable全部整数→intset否则→hashtableZSetziplistskiplisthashtable元素128且长度64B→ziplist否则→跳表总结Redis自己实现数据结构是为了O(1)获取长度、二进制安全、灵活的内存管理——这些C语言原生结构做不到SDS用len记录实际长度、用free做预分配获取长度O(1)追加时减少内存分配次数List从linkedlistziplist互斥演化到quicklist统一两者的优势——链表级快速定位到某一节点ziplist级在该节点内紧凑存储元素Hash和ZSet都有小数据用ziplist、大数据用专用结构的双实现——这是空间和时间的动态平衡ZSet的核心是skiplist——概率型数据结构实现比红黑树简单范围查询比红黑树的父指针回溯遍历模式更高效所有底层选择背后都是同一个权衡数据量小时优先内存效率数据量变大时优先操作速度下一篇预告Redis原理二——过期删除与内存淘汰数据过期了怎么删、内存满了怎么办。拆解惰性删除定期删除的组合策略以及8种内存淘汰策略的适用场景和选择逻辑。