很多人在面试或者日常排查性能问题的时候都会被问到一个问题Redis为什么这么快标准答案无非是内存操作、单线程避免竞争、IO多路复用。这些说法都没错但都属于宏观层面的“场面话”。真正决定一次get、一次set具体耗时的是Redis底层那套极其朴素又极其讲究的数据结构。这里头戏份最多、也最容易被一笔带过的就是字典dict。你可以把Redis想象成一座巨大的寄存柜每一个redisDb就是其中一个柜区柜区里每一个格子登记在哪儿、什么时候过期、遇到碰撞怎么处理全由字典说了算。这篇文章我打算从redisDb出发把字典的struct、哈希函数、hash冲突、渐进式rehash整个链路拆开讲一遍顺便把键空间、过期键、大key这些实操场景串起来。不管你是刚开始读Redis源码的新手还是准备面试的老兵这篇文章应该都能让你对“Redis为什么快”有一个更踏实的答案。1. redisDb与字典键空间的真相1.1 redisDb里到底装了什么先把目光放到一个Redis实例上。你在配置文件里看到的databases 16指的就是这个实例最多可以创建16个redisDb。每个redisDb不是简单的一堆键值对堆在一起它内部维护了若干张字典其中最关键也最庞大的一张就是保存所有业务键值对的键空间字典。在Redis源码server.h里redisDb结构体大致长这样typedef struct redisDb { dict *dict; // 键空间保存所有键值对 dict *expires; // 过期字典保存键的过期时间 dict *blocking_keys; // 正在被阻塞命令等待的键 dict *ready_keys; // 可以解除阻塞的键 dict *watched_keys; // 被WATCH监视的键事务会用 int id; // 数据库编号 long long avg_ttl; // 用于统计平均TTL } redisDb;也就是说哪怕你在Redis里只set了一个字符串也会同时出现在两个字典里dict里存的是“键 - 值对象”expires里存的是“键 - 过期时间”。平时我们说的键空间keyspace指的就是dict这张大表。SELECT切换数据库本质上就是把当前操作的redisDb指针切到另一个编号的redisDb上命令里后续的键操作全部落到那个redisDb的dict上。1.2 为什么键空间非字典不可选型背后的逻辑很直接。键空间需要支持的操作是增删改查、判断存在、随机拿一个key、遍历全库。这些操作如果放到普通的链表里查找复杂度是O(N)数据量一上来就完蛋如果放到有序数组里虽然可以用二分查但插入删除又面临元素移动。字典这种基于哈希表的实现正常场景下查找、插入、删除都是O(1)配合Memcached多年的实践几乎就是键值对存储的默认答案。另外还有一个容易被忽略的原因Redis的键是二进制安全的。什么意思键可以是任意字节序列不一定非得是合法的UTF-8字符串甚至可以是带着\0的裸字节。哈希表天然不关心键内部长什么样只把键看成一串字节算出哈希值存到对应桶里就行。这种“不挑食”的特征让字典成为键空间最省心的容器。换作B树或者跳表还得定义键的排序规则二进制键的排序本身就很麻烦。1.3 先别混淆hash类型与字典结构是两码事很多人一看到“Redis字典”会条件反射想到HSET、HGET那套哈希类型API。严格说这两者是不同层次的东西字典是Redis内部的基础数据结构而哈希类型是面向用户的一种对象类型它的底层编码可以是listpack小数据量或hashtable大数据量。后者一旦转化为hashtable编码底层其实就复用了一套字典但用户感知的“哈希类型”并不等于字典本身。这个区分很重要。面试里经常有人被问到“Redis的哈希类型底层是什么”脑子里第一反应就是dict结果漏掉listpack这个更常见的小体积编码。记住一个原则Redis内部很多地方都用字典但用户空间看到的hash类型只是字典的一个使用场景不要画等号。2. 字典的三层结构dict、dictht与dictEntry2.1 dict结构整个字典的“门面”经典的Redis字典设计来自C语言的开源哈希表库作者是Redis之父antirez在早期项目里沉淀下来的。它在dict.h里的核心结构如下typedef struct dict { dictType *type; // 类型特定函数哈希、比较、键值内存释放 void *privdata; // 私有数据给类型函数用 dictht ht[2]; // 两张哈希表rehash时交替使用 long rehashidx; // rehash进度-1表示没有进行 unsigned long iterators; // 正在迭代的迭代器数量 } dict;type是一组函数指针负责告诉哈希表“这个字典的键怎么算哈希、怎么比较、怎么释放”。比如键空间字典和过期字典都用dict结构但它们的键比较方式和释放逻辑完全不同靠dictType分开。ht[2]是理解字典的核心。绝大多数时候只有ht[0]在工作ht[1]是空的。但一旦触发rehashht[1]就会被分配成一张更大的新表数据逐渐从ht[0]搬过去。rehashidx记录搬移进度等于-1表示没在搬等于0或更大的值表示搬到了第几个桶。2.2 dictht结构真正的哈希表本体dictht是真正存数据的哈希表它长这样typedef struct dictht { dictEntry **table; // 桶数组每个元素是一个指向dictEntry链表的指针 unsigned long size; // 桶的数量必须是2的整数次幂 unsigned long sizemask; // 等于 size - 1用来做位运算取模 unsigned long used; // 已使用的节点数量 } dictht;这个结构信息量很大。size强制要求是2的整数次幂这直接决定了索引计算可以用hash sizemask代替hash % size。按位与比取模快得多在每一条命令都要计算索引的Redis里这种微小的性能差异会被放大到肉眼可见。table是指向指针数组的指针数组里每个槽位叫桶bucket。如果两个键算出来的索引相同就会在这个桶底下拉出一条链表后续会专门讲这个。used则代表当前一共存了多少个dictEntry节点它和size的比值就是负载因子是判断要不要扩容缩容的关键指标。2.3 dictEntry结构键值对的最小载体单个键值对在字典里用dictEntry表示typedef struct dictEntry { void *key; // 键指针 union { void *val; // 值指针 uint64_t u64; // 无符号整数直接内联 int64_t s64; // 有符号整数直接内联 double d; // 浮点数直接内联 } v; struct dictEntry *next; // 指向下一个冲突节点拉链法用 } dictEntry;这里的union很巧妙。如果值是普通的Redis对象指针走val但有些内部场景要存的只是计数、时间戳这类整数就不需要额外分配Redis对象直接塞进u64或s64里省了一次内存分配。过期字典就是这么干的它的value存的就是毫秒级过期时间戳直接放进u64省对象开销。next指针是理解hash冲突的关键后面单独开一节讲。现在先记住这个“链表节点”形态它意味着Redis的哈希表解决冲突的方式是链地址法而不是开放寻址法。3. 哈希算法与索引计算O(1)查询的根基3.1 Redis用什么哈希函数从MurmurHash到SipHash哈希函数直接决定了键能不能均匀散列到各个桶里。早期Redis使用MurmurHash2系列这个算法以“分布均匀、速度快”著称在数据库界用得很多。但后来Redis逐步换掉了它改用SipHash。为什么要换因为哈希碰撞攻击。如果一个攻击者能精确构造一批哈希值相同的键让它们全部落到同一个桶里哈希表就会退化成链表插入和查找复杂度从O(1)变成O(N)直接拖垮服务。SipHash是一种带密钥的伪随机函数每次进程启动时生成随机种子哈希结果严重依赖种子攻击者不知道种子就无法稳定构造碰撞键。这有点类似给哈希过程加了一把随机盐你说它慢吧确实比MurmurHash稍慢但换来的是抗碰撞能力这个安全投入对缓存服务来说非常值。需要区分的是Redis在不同用途上用了不同的哈希函数。键空间字典默认用的就是SipHash而命令表查找这类需要大小写不敏感的哈希场景则用djb2的变体。不要看源码的时候发现两个哈希函数就对不上号它们各有分工。3.2 索引计算hash sizemask是怎么来的一个键存到哈希表的哪个桶里索引是这样算的index hash dict-ht[x].sizemask;因为size是2的整数次幂sizemask size - 1的二进制全是低位1。比如size 8sizemask 7二进制就是0111任何哈希值跟它做按位与结果只能在0到7之间也就等价于对8取模。位运算比取模快这是哈希表设计里的经典优化C语言层面能省则省。但这里有一个不得不提的点按位与会丢弃哈希值的高位信息只用低位决定桶的位置。如果哈希函数分布不太均匀而哈希值低位恰好又有规律就容易产生不均衡。好在SipHash和MurmurHash这类算法本来就是为“雪崩效应”设计的——输入变化一点点输出整体翻天覆地因此低位信息足够分散实际使用中没毛病。3.3 键空间查询的全链路走读一条GET name命令到达服务端后在字典层面大致走这些步骤根据redisDb找到键空间字典db-dict调用dictType里注册的哈希函数对键“name”计算SipHash哈希值用hash sizemask算出桶索引取出table[索引]指向的链表头逐个比较key命中后拿到dictEntry返回里面的value指针。这个链路每一步都是常数级操作唯一可能有波动的是第4步如果链表很长比较次数就会增多。所以哈希表的健康度核心指标就是“桶够不够多、链表够不够短”这正好引出负载因子和rehash。4. hash冲突与链地址法冲突链里的生存法则4.1 哈希冲突的本质生日悖论下的必然哈希表容量有限无论哈希函数设计得多好总会出现两个不同键算出的索引相同的情况这就是哈希冲突。你不要指望“让函数好一点冲突就没有了”因为按抽屉原理只要键的数量超过桶的数量冲突一定出现更反直觉的是即便键数量远小于桶数量由于生日悖论冲突概率也会很快逼近百分百。所以冲突不是bug是要被正视的设计前提。Redis的选择是链地址法同一个桶下面挂一个链表冲突的就往链表尾巴上接。插入时头插还是尾插Redis源码里是头插法新节点直接插在链表头部这样插入复杂度O(1)不用遍历链表找尾巴。4.2 next指针链地址法的具体形态回看dictEntry里的next指针它就是串起冲突键的那根线。当两个键index相同第二个键插入时会让它的next指向第一个键自身成为桶里的链表头。这样桶数组里的每个元素实际上不是单个键值对而是一个链表的头指针。查找的时候先找到桶再在链表里逐个比较key。链表短查找就快链表长查找就慢最坏情况所有键都冲突退化成一条大链表复杂度回到O(N)。这也是为什么Redis非常在意哈希表的负载因子负载因子越高链表越长的概率越大所以要在合适时机让桶变多。这里有一个实操层面的认知对一个大规模哈希表如果used / size已经接近1说明平均每个桶都快有1个键了看起来还行但极端情况下某个热门桶可能挂了成百上千个键。排查时不能只看平均负载还要关注单个桶的链表长度只是Redis没有直接暴露“每个桶链表长度”这个指标更多时候只能靠命令耗时异常去反推。4.3 冲突链变长之后性能退化和哈希攻击防御冲突链变长的根源有两种一是数据量太大但没及时扩容负载因子过高二是恶意构造碰撞键哈希函数的输出被针对。针对第一种靠rehash机制自动解决针对第二种Redis在SipHash之外还加了随机种子。每次启动Redis都会用随机数生成器初始化一份哈希种子存进dict_hash_function_seed。同一个键这次启动算出的哈希值和下次启动算出的哈希值完全不同。攻击者在没有种子之前无法预判哪些键会落进同一个桶碰撞攻击就很难实施。顺带提一点Redis持久化后重启哈希种子会重新生成所以RDB里相同的键在重启后可能散落到完全不同的桶里。这对用户毫无感知但对攻击者来说意味着预先构造的碰撞键表完全失效。5. rehash全解析扩容、缩容与渐进式搬移5.1 负载因子什么时候该扩容缩容哈希表不是无限长的数据越积越多桶不够用时就得扩容。Redis用负载因子来判断负载因子 used / size触发扩容的决定因素有两个如果没有子进程在执行BGSAVE或BGREWRITEAOF负载因子超过1就扩容如果有子进程在执行上述操作负载因子要超过5才强制扩容。为什么BGSAVE会影响阈值因为fork出来的子进程要写RDB文件Redis在fork时为了写时复制会复制父进程的页表。如果父进程这时候频繁扩容意味着要分配大块新内存并搬移数据每一页的内存写入都会触发COW复制内存和CPU压力都会暴涨。为了照顾持久化子进程Redis把扩容阈值临时调高到5能拖就拖避免扩容和持久化互相踩踏。缩容的条件就一条负载因子低于0.1。也就是数据删掉很多桶太稀疏了哈希表空占内存需要缩小table数组。5.2 扩容和缩容的动作先建新表再搬数据触发扩容时Redis会计算新表大小对used * 2做向上取整到最近的2的整数次幂。比如当前used 100used * 2 200最近的2的幂是256新表size就是256。为什么这么算因为要维持size % 2 0这个约束索引位运算才成立。缩容时新表大小取第一个大于等于used的2的整数次幂。比如used 80新表size就是128。具体动作是先给ht[1]分配内存容量是新size然后把ht[0]里的所有键值对重新计算索引搬到ht[1]搬完后释放ht[0]的table把ht[1]赋值给ht[0]ht[1]的table置空。5.3 渐进式rehash一次只搬一点点如果说扩容是目标那么渐进式rehash就是实现目标的方式。为什么不能一次性把数据全搬完因为Redis是单线程的一次搬几百GB的哈希表服务就直接卡死几秒到几十秒。这违背了Redis“低延迟”的立身之本。渐进式rehash的核心思想是“把搬移动作分摊到后续的每一次CRUD操作里”。具体执行时rehashidx从0开始表示从桶0开始搬每次增删改查触发_dictRehashStep时只搬一小步默认步长是1个桶与此同时后台的serverCron定时任务也会调用dictRehashMilliseconds要求每次执行至少搬移1毫秒把空闲CPU时间花在搬移上。也就是说即使业务空转没有任何命令进来定时任务也会一点点搬一旦有命令进来每条命令都会“顺手”搬一点。整个过程对客户端完全透明Redis不会因为rehash而停机。5.4 rehash期间的读写规则与最终收尾渐进式rehash期间ht[0]和ht[1]同时存在读写必须兼容两张表。Redis的处理原则非常清晰新增键一律只往ht[1]插入因为最终所有数据都要落到新表里再往旧表插等于白搬查找键先查ht[0]查不到再去ht[1]查删除键两张表都查查到哪张就在哪张删更新键两张表都查找到节点后更新值搬移进度每搬完一个桶就把ht[0]里那个桶的指针置空避免重复搬。搬完最后一个桶时ht[0].used应该为0这时把ht[1]整张表赋给ht[0]ht[1].table置空rehashidx设回-1。整个rehash周期就此结束。5.5 单线程为什么不卡时间预算与serverCron很多人担心“rehash会阻塞服务”其实渐进式设计已经把这个风险压得很低了。单条命令触发的搬移步长只有1偶发情况是多访问几个空桶——源码里限制了最多连续访问的空桶数量防止某些桶空洞太多导致一次搬移拖太久。而serverCron里的耗时预算也只是1到2毫秒默认每100ms执行一次搬不完就等下一轮。这套设计的效果是一个5000万键的字典rehash通常只需要几百个命令周期和定时任务周期就能平滑搬完。最坏情况下如果负载因子长期高企且持续有新写入rehash可能一直持续但此时ht[1]已经在服务读请求旧表一点点清空性能曲线没有尖刺。6. redisDb里与字典相关的几个实操场景6.1 expires字典过期键有自己的“花名册”回到redisDb结构expires字典才是键空间之外最值得注意的一张表。它的key指向键空间里同一个键对象value则存储该键的过期时间戳毫秒。因为key是共享指针所以内存开销比再存一份字符串小得多。当你执行EXPIRE key 100Redis不是去键空间里改动键值对而是向expires字典里插入或更新一条记录执行PERSIST key则是从expires字典里删掉这条记录而执行TTL key时Redis会先从expires字典查过期时间再用当前时间相减得出剩余秒数。理解这一点之后你会明白为什么“判断键是否存在”和“判断键是否过期”是两回事——前者查dict后者查expires。6.2 过期键删除惰性删除与主动删除的配合既然存在专门的过期字典删除自然有配套策略。Redis用了两个层面惰性删除每次读取键时先查expires发现已过期就直接删除并返回空。这种策略省CPU但可能导致过期键“赖着不走”占内存主动删除后台定时任务从expires字典里随机抽一批键默认20个检查并删除其中过期的如果这次抽样里过期键占比超过四分之一就再抽一轮反复多次。这个机制保证了过期键不会一直霸占内存。有意思的是主动删除在rehash期间也会执行但要注意过期键可能分散在两个哈希表里抽样逻辑得兼容两张表。好在dict的迭代器和rehash机制是配套设计的不会因为搬移而重复抽到或漏掉。6.3 dictScan反向迭代大规模遍历不漏不重我们平时用SCAN命令遍历Redis键表面上是游标迭代底层就是dictScan。如果在遍历过程中字典发生了rehash普通顺序迭代很容易漏掉某些桶——因为键搬到了新表的不同索引位置。Redis解决这个问题的办法是“反向二进制迭代”游标不是简单递增而是每次反转最高位之类的操作让新旧表之间的桶映射被完整覆盖。这听起来有点绕但最终效果很明确即使迭代过程中rehash正在进行SCAN也能保证返回所有仍然存在的键不重复、不遗漏。如果你有过线上用KEYS命令导致卡顿的惨痛教训就知道SCAN这个特性有多重要。6.4 大哈希表与fork阻塞隐蔽的性能杀手字典太大还有一个隐蔽问题fork()的耗时与进程内存大小有关尤其是页表规模。当redisDb的键空间字典动辄几千万键时执行BGSAVE触发fork可能带来一次数百毫秒乃至数秒的停顿。很多运维把锅甩给磁盘其实根子在于哈希表太大了页表复制太慢。应对办法通常是对大实例做分片或者拆分数据让单个实例的key数量降下来给Redis配置足够大的maxmemory逐步淘汰旧数据避免让键空间长期处于超高负载因子状态。说实话字典本身已经做了渐进式rehash真正让人头疼的往往不是rehash而是大字典背后的fork成本。7. 面试与实战避坑关于字典的那些高频问题7.1 一个表就能解决为什么要搞出两个表这是理解Redis字典设计的第一个坎。单表哈希表当然简单但一旦要扩容你就得让服务停下来搬完数据再继续这在生产环境不可接受。两张表配合rehashidx本质上是把“全量迁移”变成了“增量迁移”。所以看到ht[2]不要慌它不是两个数据库而是“正在用的哈希表”和“未来目标哈希表”。7.2 大hash对象的读写要小心用户空间的大哈希类型底层一旦是hashtable编码字段再多一点每次HGETALL都要遍历整棵哈希表。如果你在redis-cli --bigkeys里看到有一个几十万字段的hash key这其实意味着redisDb里的某些键值对绑定了巨大的字典实例。正确的做法是用HSCAN分批次取字段或者考虑换成多个字符串键分散压力。很多“Redis变慢”案例最后定位到的问题不是配置不对而是把一个字典当成了无底洞往里堆。7.3 集群模式下字典与slot的关系Redis Cluster把16384个slot分布在多个节点上每个节点上的键由本地redisDb的键空间字典管理。也就是说字典依然是本地的数据结构slot决定的是“这个键应该由哪个节点负责”而不影响节点内部的组织方式。面试里容易把这两者混在一起字典管的是键到值的映射slot管的是键到节点的映射层次完全不同。7.4 常见FAQ速查表问题答案要点Redis用哪种方法解决哈希冲突链地址法即每个桶挂链表新冲突节点头插哈希表为什么不直接用取模算索引size为2的整数次幂用hash sizemask代替位运算更快负载因子超过多少扩容无子进程时超过1有BGSAVE时超过5负载因子低于多少缩容低于0.1rehash期间新增键放哪张表只放ht[1]避免白搬rehash会阻塞服务吗渐进式rehash每次只搬少量桶不会长时间阻塞为什么用SipHash抗哈希碰撞攻击带随机种子攻击者无法构造碰撞键过期键存在哪独立的expires字典键是数据键值是毫秒过期时间戳我个人的体会是读源码看到dict.c时会发现很多细节其实都是为了“在单线程模型下优雅地完成有状态操作”。字典结构本身并不复杂复杂的是它要和过期机制、持久化fork、迭代器、集群迁移同时共存。如果你以后看到某个Redis线上问题找不到头绪不妨先打印一下INFO里的键数量再想想此刻字典的负载因子大概在什么水平。很多玄学问题落到哈希冲突与rehash上一下就通了。最后再分享一个小技巧排查的时候可以用redis-cli --stat观察keyspace_hits和keyspace_misses的比值如果命中率突然下滑同时命令延迟上升很可能是某些大字典触发了rehash先把问题往哈希表方向带往往比瞎调内核参数管用。