Redis这个项目我前前后后读过不少次源码也给团队做过好几轮分享。每次面试技术候选人大家都能熟练背出五种数据类型但一追问OBJECT ENCODING返回什么、rehash为什么是渐进的、ziplist为什么被listpack替代往往就答不上来了。标题里的“Redis、底层数据结构、实现原理”这几个词其实就是理解Redis真正价值的三把钥匙。Redis快并不只因为“内存”两个字而在于它用一套极其克制的结构设计把内存、速度和并发安全平衡到了极致。这篇文章适合刚入门想进阶的人也适合准备面试或者正准备读源码的开发者。1. 为什么我认为先看底层结构比背命令更有用1.1 内存和速度的账一个对象到底占多大Redis里的每个键值对并不是简单地存一个字符串。在server.h头文件里redisObject结构占用了type、encoding、lru、refcount和ptr这些字段。一个普通的redisObject在64位机器上就要占16字节即使你存的是一个纯粹的数字这个对象头的成本也逃不掉。很多人就没有意识到这一点以为存10万个数字1就是10万个字节实际上正常情况下至少还要多出160万字节的对象头开销还不算SDS本身和内存分配对齐带来的浪费。之所以要把type和encoding拆成两个维度是为了“逻辑类型稳定、物理编码可变”。type永远是用户看到的String、List、Hash、Set、ZSet而encoding可以根据数据特征在int、embstr、raw、quicklist、listpack、hashtable、intset、skiplist之间随意切换。这其实很像操作系统里“接口与实现分离”的思路。你执行SET k 1时Redis底层存的并不是字符1而是一个long类型的整数内存占用比相同长度字符串小得多。这种设计带来的直接好处是命令层接口不用变底层实现却可以针对数据特征做最优选择。内存分配上也能看到Redis的用心。Redis默认使用jemalloc分配器它会按照2的幂次分桶管理小内存块。embstr编码的阈值为什么定在44字节而不是40或者50因为jemalloc常见的64字节桶减去redisObject的16字节再算上SDS头部和各种对齐开销剩余的数据区正好能放下44字节。一旦字符串超过这个长度还用一次性分配的方式就会造成内存碎片率上升所以必须改成对象头和数据分开分配的raw编码。这些阈值不是拍脑袋得来的而是每一处都由分配器行为倒推出来。排查线上内存问题时我经常用MEMORY USAGE key查看某个键真实占用的内存然后再用OBJECT ENCODING key确认编码类型。看到底层编码后很多内存突增的疑问基本都能解开。1.2 从C字符串到SDSRedis的第一个底层选择C语言原生字符串以\0结尾获取长度要O(n)而且遇到二进制数据里的\0就会截断。Redis要存序列化对象、图片二进制、消息内容这些数据完全可能包含\0。所以Redis自己实现了SDS也就是Simple Dynamic String。3.2版本以后SDS分成了sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64多种变体按数据长度选择不同宽度的len和alloc字段。SDS的buf依然以\0结尾但这不是它判断结束的方式真正记录长度的是前面的len字段因此它既是二进制安全的又能兼容部分C字符串函数。SDS带来的第一个优势就是O(1)获取字符串长度这是API层速度的来源之一。另外它做了空间预分配追加后长度低于1MB时SDS会额外分配与当前长度相同的剩余空间超过1MB后每次追加只额外分配1MB。举个例子当前len是10追加5字节后SDS实际拿到的可用容量可能是30字节以上。这种用空间换时间的策略是为了尽量减少malloc的调用次数。如果每次都执行系统级内存分配高并发下系统调用开销会非常惊人。SDS的另一个细节是惰性释放。像sdstrim这类操作会修改len和buf位置但不会立刻把内存还给系统等后续追加时再复用。这种“不急着还内存”的做法在高并发且字符串频繁变更的场景下能显著降低内存分配次数。我在实践里也碰到过类似问题把Redis当消息队列用消息体很小但量非常大如果不理解SDS的空间复用内存参数调来调去都找不到方向。理解了底层结构之后你自然就明白为什么STRLEN返回的长度和MEMORY USAGE显示的内存不一定成正比。2. 全局哈希表与渐进式rehash2.1 用哈希表解决快速查找但哈希冲突怎么办Redis所有键值对的顶层结构是一个全局dict。dict的定义在dict.h和dict.c里核心结构由两个hashtable组成。真正查询key时Redis会先计算哈希值再定位到哈希桶。这里使用的哈希算法是MurmurHash这类非加密散列算法特点是分布均匀、计算开销低。哈希冲突不可避免Redis用链地址法解决每个哈希桶后面拉一条dictEntry链表冲突的元素依次挂在链表上。dictEntry里除了保存key和value之外还有一个next指针。这里容易被忽略的是value的类型是void*指向一个redisObject而key直接用SDS保存没有再用redisObject包装。为什么因为key本身不需要像value那样支持多种类型去掉一层对象头可以省不少内存。看expires过期字典也是同样的dict结构key也是SDSvalue则存过期时间戳mstime_t。当你执行SET key value EX 100时数据进了主dict过期时间进了expires dict。两个字典共享同一个SDS key不会重复保存key字符串。哈希表实现里还有一个容易被忽视的细节桶数量永远是2的幂次。这样要计算桶下标时可以用hash (size-1)来代替取模运算位运算比除法快不少。代价是扩容和缩容的触发阈值要设计得比较保守不然桶数量容易暴涨。Redis在负载因子大于1时触发扩展当后台有RDB或AOF子进程时阈值提高到5负载因子低于0.1时触发缩容。理解了这一点你就会明白为什么大量写入时Redis内存会阶段性上涨那往往不是数据本身变多而是扩容换桶带来的额外数组空间。2.2 rehash分步走避免阻塞事件循环传统哈希表rehash是一次性把旧桶数据全部迁移到新桶。Redis是单线程事件循环如果一次性rehash一个几GB的dict主线程会被卡住几百毫秒甚至更久业务方看到的症状就是“Redis卡了一下”。因此Redis实现了渐进式rehashdict里增加了一个rehashidx字段初始值为-1。触发rehash时rehashidx被置为0之后每执行一次增删改查操作就顺带迁移一个非空桶。rehashidx不断往前推进直到旧表所有桶迁移完成再释放旧表把rehashidx重新置为-1。渐进式rehash期间有四个关键行为。第一新写入的键一律进ht[1]避免后续再迁移一次。第二查找时先查ht[0]找不到再查ht[1]。第三更新操作同样先查旧表再查新表。第四删除操作需要先通过dictFind确认键存在于哪张表然后在该表中删除。很多人以为rehash期间两个表只是“备份”关系其实它们是分工关系旧表继续服务存量数据新表承接增量数据。这样设计既保证数据不丢失也保证每次请求只做少量搬迁不会阻塞主线程。还有一个容易被忽略的机制1ms空转。当rehash过程中没有请求进入时serverCron会在周期任务里主动执行rehash并限制每次执行时长保证大字典能慢慢迁移完而不是永远停在半路。由于rehash期间两个哈希表同时存在内存峰值会暂时上升。我在生产环境里遇到过一个大Hash导致rehash迟迟不结束的情况解决思路不是干等而是分批用HSCAN把大Key拆小避免触发一次性的大迁移操作。很多Redis内存报警实际都和数据结构的rehash状态有关光看内存数字看不出端倪必须配合底层结构和慢日志来分析。3. 五种数据类型的编码选择这里先用一张表把整体结构列清楚后面再逐个展开。数据类型底层编码适用条件Stringint可转为long long的整数Stringembstr长度不超过44字节的短字符串Stringraw长字符串或二进制内容Listquicklist默认使用节点内部存listpackHashlistpack默认阈值128个field且value不超过64字节Hashhashtable超过listpack阈值Setintset全整数且成员数不超过512Sethashtable存在非整数成员或数量超阈值ZSetlistpack默认阈值128个member且member/score不超过64字节ZSetskiplist dict超过listpack阈值3.1 String的int、embstr、raw怎么切换String是Redis里最基础也最容易被人误解的类型。当你执行SET k 1时Redis会先尝试把字符串转成long long能转且没超范围就使用OBJ_ENCODING_INT编码直接把整数值存在redisObject的ptr字段里不再额外分配SDS。这里存的是8字节的long long加上16字节的redisObject就能表示一个整数。像INCR这类自增命令底层就是对这个long直接做加减所以性能极高。embstr是嵌入式短字符串。创建embstr时Redis会把redisObject和SDS头在内存里一次性分配两者放在同一块连续内存中。好处是只需要一次malloc也避免了对象头和数据分开导致的内存碎片。缺点是这种结构不支持原地修改一旦对embstr执行追加或替换操作Redis会先将它转换成raw然后再处理。为什么阈值正好是44字节这个数字和jemalloc的64字节内存桶、redisObject的大小、SDS头部的开销都有关系实质就是在“尽量减少内存占用”和“尽量避免碎片”之间找到一个平衡点。不同版本阈值可能有差异但设计思路没变。raw编码适合长字符串和二进制数据。raw的创建过程需要两次分配先分配redisObject再分配SDS。比起embstr多一次内存分配但也换来了SDS自由扩容的能力。如果你往Redis里塞一个几百KB的HTML页面raw编码会更稳定。这里有个实际性能误区有些人喜欢用APPEND命令不断追加长字符串看起来每次操作很快但SDS在扩容和内存拷贝上的开销是持续产生的。更好的做法是客户端拼好完整字符串再一次性SET。踩过几次坑之后我养成了一个习惯先用STRLEN看长度再用OBJECT ENCODING看编码很多“为什么内存这么大”的疑问其实就是编码没选对导致的。3.2 Listquicklist的诞生和listpack替代ziplist早期Redis List在元素少时使用ziplist元素多时使用双向链表。ziplist是一块紧凑的字节数组内存占用低、缓存局部性好但它有一个非常伤性能的问题级联更新。ziplist每个节点会记录前一个节点的长度也就是previous_entry_length字段。当前面节点长度变化后后续节点的prevlen可能要从1字节扩展成5字节这会引发连锁反应最坏情况下后续所有节点都要移动复杂度退化到O(n²)。为了解决ziplist的级联更新问题Redis在3.2版本引入了quicklist。quicklist宏观上是一个双向链表但每个链表节点内部嵌了一个ziplist或listpack。这样既保留了双向链表头尾插入删除的O(1)复杂度又用紧凑数组提升内存密度。Redis 7.0之后quicklist节点内部的ziplist被listpack取代。listpack不再记录前一个节点的长度只记录当前节点自身的长度从结构上彻底规避了级联更新。listpack和ziplist一样追求内存紧凑但读写稳定性大幅提升。quicklist有两个重要配置值得关注list-max-listpack-size和list-compress-depth。前者控制单个listpack节点最多放多少元素或多少字节后者控制首尾两端各有多少个节点不参与压缩中间的节点可以被压缩。为什么只压缩中间节点因为List最典型的操作是LPUSH和RPOP比如消息队列、日志流两端节点被访问频率极高对两端做压缩会导致每次操作都要解压反而更慢。我维护过一个延迟队列把list-compress-depth设为2后list整体内存下降了约60%但读写延迟几乎没变化。数据结构的选型和调优从来不是越大越好而是要根据访问模式来。3.3 Hashlistpack条件与hashtable的升级阈值Hash类型在业务中非常常用用户画像、商品属性、会话数据都适合放Hash。Redis 7.0之前小Hash默认使用ziplist7.0之后改用listpack。默认的判定条件是field数量不超过hash-max-listpack-entries也就是128个同时每个field和value长度都不超过hash-max-listpack-value也就是64字节。当条件全部满足时Hash用listpack顺序存储字段和值一旦任何一个条件被打破整个Hash会整体转成hashtable编码。listpack编码下的Hashfield和value交替排列在一段连续内存里。查找字段时走线性扫描但因为默认阈值只有128个entry每个value又都很短线性扫描的代价非常低换来的是极高的内存密度。hashtable编码则是真正的dict字段作为key值作为value支持O(1)查找但每个entry要多出dictEntry节点、哈希数组和指针等开销。这里有个特别重要的认知升级是全局的不是某个字段单独升级。一个原本100个field都小于64字节的Hash某天其中一个field变成了几百字节Redis会立刻把整个Hash转成hashtable所有字段的内存都会跟着升高。我见过不少线上事故就是因为把大Hash当成无限容器使用。比如往一个Hash里持续写入订单数据超过128个field后内存突然上涨查来查去发现业务数据量并没有明显增加实际就是编码切换带来的结构开销。经验做法是默认阈值以上的大Hash要么拆成多个小Hash要么换用其他结构。拆分时建议用HSCAN分批迭代避免直接HGETALL把网络和大对象内存都打爆。另外Redis的Hash不支持字段级过期过期字典的粒度是整个key给某个field单独设置过期时间需要业务层额外维护这也是底层实现决定的上层能力边界。3.4 Setintset的升级机制与哈希化Set的实现只有两种底层编码intset和hashtable。当集合中所有成员都是整数并且元素数量不超过set-max-intset-entries默认512时Set使用intset编码。intset本质上是一个升序排列的整型数组查找时用二分查找插入时要移动后续元素。所以intset特别适合点赞用户ID、在线状态这种“数量少、全整数”的场景。intset有一个很有特色的升级机制。初始时所有元素都在int16范围内数组按2字节一个元素存储一旦插入一个超出int16范围的整数intset会原地把整个数组升级成int32。如果再有大整数插入又会升级成int64。升级过程会重新分配内存并迁移所有元素复杂度是O(n)。面试里最容易被问到的点就是intset会不会降级答案是不会。比如一个大集合里删掉了大整数剩余元素都很小它依然保持int64编码。Redis不会为了省几个字节来回搬家那样只会带来无谓的性能抖动。所以排查时会看到某个Set的成员明明很少但编码是hashtable很大概率是曾经插入过字符串或者大整数结构已经回不去了。当Set不再满足整数条件或者元素数量超过512时编码会转为hashtable。这里的hashtable和全局dict共用同一套实现只是每个dictEntry的value指针都指向NULL。所以Set做去重的时候内存开销主要集中在哈希桶数组和dictEntry上不会为每个元素额外保存value对象。这也是为什么用Set做去重通常比List去重省内存List会把重复的元素都存下来Set只保存一份而且value是NULL。3.5 ZSet为什么既要跳表又要哈希表ZSet底层根据数据量有两条路径小数据用listpack大数据用skiplist加dict的组合。先聊跳表。普通有序链表查找需要从头一个个遍历跳表会增加多层索引每一层跳过一部分节点查找时从高层索引开始逐步下沉复杂度能到O(log n)。它和平衡树都能解决有序查询问题但跳表实现更简单插入删除只需要调整相邻节点指针不需要像红黑树那样做复杂的旋转操作。Redis是内存数据库不用考虑磁盘页和节点局部性跳表这种结构在内存里非常合适。另一个优势是范围查询友好ZRANGEBYSCORE从定位到起点后沿着链表走就能拿到区间数据红黑树反而需要维护parent指针去找后继节点。那为什么还要额外维护一个dict因为按member查score跳表是O(log n)而dict能做到O(1)。ZSet里member作为dict的keyscore作为value同时member和score又作为跳表节点存在。于是ZSCORE key member走dict直接命中ZRANGEBYSCORE走跳表有序遍历。两个结构中的member通过指针共享同一份数据不存在重复复制。这个设计看起来繁琐实际上是为了让“按成员查分数”和“按分数取范围”两个操作各自都有最优复杂度。小数据为什么不用这套组合因为跳表每个节点都带有可变高度的指针数组指针开销非常大。默认条件zset-max-listpack-entries为128且member和score不超过64字节时ZSet用listpack顺序保存member和score对读取时做线性扫描或二分搜索。一旦超过阈值整个ZSet转成skiplist加dict。这个升级同样是全局的不可逆。我在做排行榜之前通常会预估数据量如果确定会超过128人就直接按大ZSet设计不让它反复升级。4. 深入源码前必须知道的实现细节4.1 过期、淘汰和惰性删除背后的数据结构Redis的过期机制不是定时扫全库而是“惰性删除加定期删除”的组合。惰性删除依赖expires字典每当GET一个keyRedis会先查expires dict如果发现当前时间已经超过过期时间就删除这个key并且返回nil。定期删除则由serverCron每100ms执行一次每次随机从expires字典中抽一批key检查过期状态默认抽20个如果过期key比例超过25%就继续循环。这个策略决定了过期key不会立刻从内存消失这也是为什么你执行完DEL或等到过期后used_memory不会立刻下降。底层数据结构对过期策略的影响很直接。过期字典和主数据字典中的key通过指针共享不会复制两份SDS字符串。当内存淘汰策略启用了allkeys-lru或者volatile-lru时Redis是在dict的桶数组里随机抽样若干key再按照近似LRU策略淘汰。这里的“随机抽样”很关键它并不是对全库做精确LRU排序而是牺牲一定准确性来避免全量扫描。所以如果你设置了volatile-ttlRedis会优先淘汰接近过期的抽样结果但不保证全库最接近过期的key被第一个淘汰。很多人在配置过期策略时误以为它是全局精准淘汰理解了底层的抽样机制后就不会对这个行为产生误判。4.2 分布式锁与Lua脚本的原子性依赖Redis分布式锁想要可靠依赖的是底层命令的原子性。SET key value NX PX 10000在服务端是一条命令Redis单线程事件循环不会在命令执行过程中插入其他请求所以NX和PX的组合天然原子。但如果你分两步操作先SETNX再EXPIRE这两条命令之间就存在时间窗口进程一旦崩溃锁就可能永远不释放。最稳妥的办法就是使用一条SET命令或者把“校验owner、删除锁”的逻辑放进Lua脚本里。Lua脚本在Redis执行期间不会被其他命令打断整个脚本天然原子。从底层数据结构角度看锁本质上就是一个普通的String键底层编码可能是int、embstr或raw。为什么释放锁时需要校验value是不是自己的唯一随机数因为如果不校验线程A可能把线程B后来持有的锁给删掉。这个校验逻辑通常用Lua脚本实现先GET比对value一致再DEL两步操作合成一步原子动作。还有一个容易忽略的点是Redlock这类分布式锁方案对系统时钟有假设要求各节点时间偏差有界如果发生GC停顿或时钟跳跃锁的安全性会被削弱。以我自己的项目经验来看绝大多数业务场景用SET NX PX加Lua释放锁就足够了没必要为了追求高端方案而引入额外的时钟风险和复杂度。5. 面试和实战里的底层原理高频题5.1 容易被问懵的细节清单我整理了一份自己面试常考的细节清单很多人在这些点上翻过车。OBJECT ENCODING key返回的编码名是什么直接回答当前底层结构比如int、embstr、raw、listpack、hashtable、intset、skiplist。ziplist和listpack的区别是什么ziplist记录前一个节点的长度可能引发级联更新listpack记录当前节点自身长度不依赖前一个节点从结构上避免级联更新。Hash默认为什么超过128个field就切换因为listpack在线性扫描场景下只适合小规模数据超过阈值后哈希表的O(1)查找收益才明显。rehash期间怎么保证不丢数据查找先查旧表再查新表新写入只进新表rehashidx逐步推进。SDS为什么二进制安全因为通过len字段记录长度而不是依赖\0判断字符串结束。intset为什么不降级为了避免频繁升级和降级造成的内存拷贝抖动并保持实现简单。跳表和红黑树相比优势在哪实现简单、范围查询友好、不需要旋转调整作为内存结构不依赖磁盘页局部性。quicklist为什么保留链表结构链表负责头尾操作O(1)节点内部用listpack提升内存密度。dict为什么需要两个哈希表为了渐进式rehash时新旧表交替服务保证主线程不被阻塞。Redis单线程为什么还能快内存访问、非阻塞I/O、O(1)数据结构和无锁设计是主要原因但最怕遇到KEYS、大Key这类阻塞命令。5.2 用工具验证底层编码从安装到排查的实操想真正理解底层数据结构最好自己动手跑一遍验证流程。先准备一个可用的Redis环境Linux下可以直接编译安装执行make make installmacOS上执行brew install redisWindows环境建议用WSL或者官方Docker镜像比如docker run -d -p 6379:6379 redis:7。安装完成后用redis-cli连上去做几个小实验。先SET k 1再用OBJECT ENCODING k查看大概率返回int再SET k shortstring返回embstr塞一个超过44字节的字符串返回raw。给Hash写入100个字段观察编码还是listpack再加到129个字段观察编码变成hashtable。这一套操作比死记硬背文档直观得多。可视化工具方面Redis Desktop Manager和Another Redis Desktop Manager可以满足日常查看需求但生产环境我建议以命令行工具为准。命令行更容易看到编码、内存等底层信息。排查性能问题的时候先用INFO memory看used_memory_rss和mem_fragmentation_ratio。碎片率长期偏高通常意味着大量key过期或rehash频繁。再用redis-cli --bigkeys扫描大key对大Hash用HSCAN分批迭代不要一次性把整个大key取出来。如果发现某个命令导致延迟抖动检查INFO commandstats里的慢命令统计再结合底层编码变化判断是不是发生了结构升级或者大key连锁反应。最后分享一个我自己的习惯每次上线新模型之前先在一台测试机跑半小时压测同时用INFO和OBJECT ENCODING记录数据结构变化。踩过几次“小Hash变大Hash内存暴涨”的坑之后我养成了看底层编码的习惯。数据结构是Redis的骨架命令只是骨架上的肌肉你越懂骨架线上出问题时就越有底气。