尧图网站建设 
在 第 1 篇的编码表里Hash 有两种形态字段少的时候是 listpack字段一多或者某个 value 一长就掉到 hashtable。掉下去之后底下就是 Redis 自己实现的一个哈希表代码里叫dict。dict表面上就是个普通的哈希表真正值得讲的是它怎么扩容。如果表里有几百万个节点一次性搬完会把 Redis 主线程卡住所以它把搬迁拆散了做这就是渐进式 Rehash。dict 的结构typedefstructdict{dictType*type;// 一组操作函数void*privdata;dictht ht[2];// 注意是两个哈希表longrehashidx;// 不在 rehash 时是 -1}dict;typedefstructdictht{dictEntry**table;// 桶数组每个元素是一条链表的头unsignedlongsize;// 桶的数量一定是 2 的幂unsignedlongsizemask;// size - 1unsignedlongused;// 已有的节点数}dictht;typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;doubled;}v;structdictEntry*next;// 拉链指向下一个冲突节点}dictEntry;三个东西要留意ht是长度 2 的数组ht[0]平时用ht[1]只在 rehash 的时候才分配。有第二个表就是为了 rehashsize一定是 2 的幂这样算下标可以用hash sizemask代替取模位运算快rehashidx是进度指针-1 表示没在 rehash哈希冲突两个 key 算出来的下标一样就叫冲突。Redis 用的是链地址法冲突的节点挂在同一个桶的链表上table[5] ──► entry(K1) ──► entry(K7) ──► entry(K3) ──► NULL新节点插在链表头部不是尾部。原因是dictEntry只有next没有prev也没有尾指针头插一步搞定是 O(1)尾插得先走到链表末尾是 O(n)。链表长了会退化。如果攻击者能构造出一堆哈希值相同的 key所有节点挤在一条链上查找就从 O(1) 变成 O(n)。所以 Redis 4.0 之后哈希函数换成了 SipHash它对这种碰撞攻击不敏感。拉链法的桶数够多、哈希函数够散链就不会长每次查找差不多就是算一次哈希、比一次 key。真正麻烦的不是冲突是冲突多到需要扩容。扩容和缩容负载因子load factor就是used / size用来衡量桶的拥挤程度。扩容的触发条件在_dictExpandIfNeeded里if(d-ht[0].usedd-ht[0].size(dict_can_resize||d-ht[0].used/d-ht[0].sizedict_force_resize_ratio))// 5{dictExpand(d,d-ht[0].used*2);}翻译一下只要用掉的节点数不小于桶数负载因子 ≥ 1正常情况下就扩容。但有个前提dict_can_resize它在有子进程跑BGSAVE或BGREWRITEAOF的时候是 0。为什么这时候要压住BGSAVE会fork一个子进程父子进程共享内存页父进程任何写操作都会触发写时复制。扩容要改table指针、搬大量数据会搅动很多内存页把共享的页复制成两份内存占用一下子涨上去。所以有子进程在跑的时候负载因子要涨到 5 才会强行扩容这就是dict_force_resize_ratio的作用。扩容到多大used * 2之后往上取最近的 2 的幂。比如used是 1000目标就是 2048 个桶。缩容的触发条件不一样是负载因子小于 0.1used / size 0.1 → 缩容缩容到第一个不小于used的 2 的幂。扩容在插入路径上顺手检查缩容则是靠serverCron定时任务里的tryResizeHashTables定期看一眼因为删除操作不像插入那么频繁。渐进式 Rehash问题出在搬迁的量上。假设ht[0]有 400 万个节点现在要扩到 800 万个桶把 400 万个节点一条条重新算哈希、挂到新表上这个操作可能要几百毫秒。Redis 是单线程处理命令的这几百毫秒里所有请求都得等线上就是一次明显的卡顿。Redis 的解法是把这次搬迁摊到后续的每一次操作里每次搬一点。整个过程分几步1. 给 ht[1] 分配空间大小是第一个 used*2 的 2 的幂 rehashidx 置 0 2. 每次对 dict 做增删改查干完正事顺手搬一个桶 把 ht[0].table[rehashidx] 这条链上的所有节点搬到 ht[1] 然后 rehashidx 3. 期间写入的新节点一律进 ht[1]ht[0] 只减不增 4. 查找时先在 ht[0] 找找不到再去 ht[1] 找 5. ht[0] 搬空了rehashidx -1 把 ht[1] 设成 ht[0]原来的 ht[1] 清零第 3 步是关键。rehash 期间如果有新节点往ht[0]写ht[0]就永远搬不完。所以规则定死了rehash 期间ht[0]只读不写所有新增都进ht[1]。第 4 步是查找要查两个表的代价。一个 key 可能在老表里还没搬走也可能已经在新表里了两边都得找一遍。不过这个代价是有界的最多查两次。光靠操作驱动不够如果某个 dict 建完之后长期没被访问就没人触发第 2 步rehash 停在半路ht[0]和ht[1]两个表同时占着内存等于内存翻倍还多。所以还有一条兜底路径。serverCron会周期性调用databasesCron里面有个incrementallyRehash它调用dictRehashMilliseconds(1)意思是主动搬 1 毫秒的活。这样即使没有请求rehash 也会往前走。搬运的最小单位是一个桶。dictRehash每次最多扫n * 10个空桶就停下避免连续碰到一大片空桶这在缩容后很常见时卡在原地太久。大 Hash 的代价回到 Hash 的编码选择。一个 Hash 字段少的时候是 listpack省内存一旦超过阈值变成 hashtable代价就上来了。两个地方会显内存hashtable 编码下每个字段都是一个独立的dictEntry加上 key、value 各自的 robj光指针和对象头就是几十字节。同样的数据listpack 里是挨着存的一大块没有这些开销rehash 期间ht[0]和ht[1]同时在两个桶数组一起占内存峰值能到平时的两倍所以别把一个 Hash 当成大集合用。字段到了几万、几十万HGET是快但内存和遇到扩容时的压力都不划算这种场景要拆 key或者换更合适的结构。存对象用 String 还是 Hash这个选择经常要做。同一个用户对象可以整体序列化成 JSON 存 String也可以拆成字段存 HashSET user:1{name:tom,age:18,city:sh}HSET user:1 name tom age18citysh维度StringHash读写粒度整个对象单个字段改一个字段读出来、改、整个写回一条HSET字段级过期做不到除了拆 key最近才支持见下字段多时内存拆成多 key 的话每字段都有 key 开销listpack 下字段挨着存省字段少时内存一个 key直接多一层 robj略多判断的逻辑对象整个读、整个写不怎么改单个字段用 String。缓存场景大部分是这种要频繁改某个字段或者要按字段读用 Hash。不然每次改一个字段都要把整个对象反序列化、改完再序列化写回白白浪费 CPU别用user:1:name、user:1:age这样把一个对象拆成一堆 String key。每个 key 都是一个dictEntry加一个 robj字段一多内存就上去了。这种情况应该用一个 Hash反过来字段只有两三个、又不需要字段级操作直接存一个 String 更省事字段级过期是个例外情况。Redis 7.4 之前Hash 不能给单个字段设 TTL只能整个 key 过期。7.4 加了HEXPIRE、HTTL这一组命令才支持。如果你用的是 7.4 之前的版本又需要对象里某个字段单独过期那就只能把它拆成独立的 String key。ZSet 也同时用了跳表和dict不过那里dict是为了按 member 查 score见ZSet 那篇。 Redis 哈希表如何边扩容边服务？讲透渐进式 Rehash
在 第 1 篇的编码表里Hash 有两种形态字段少的时候是 listpack字段一多或者某个 value 一长就掉到 hashtable。掉下去之后底下就是 Redis 自己实现的一个哈希表代码里叫dict。dict表面上就是个普通的哈希表真正值得讲的是它怎么扩容。如果表里有几百万个节点一次性搬完会把 Redis 主线程卡住所以它把搬迁拆散了做这就是渐进式 Rehash。dict 的结构typedefstructdict{dictType*type;// 一组操作函数void*privdata;dictht ht[2];// 注意是两个哈希表longrehashidx;// 不在 rehash 时是 -1}dict;typedefstructdictht{dictEntry**table;// 桶数组每个元素是一条链表的头unsignedlongsize;// 桶的数量一定是 2 的幂unsignedlongsizemask;// size - 1unsignedlongused;// 已有的节点数}dictht;typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;doubled;}v;structdictEntry*next;// 拉链指向下一个冲突节点}dictEntry;三个东西要留意ht是长度 2 的数组ht[0]平时用ht[1]只在 rehash 的时候才分配。有第二个表就是为了 rehashsize一定是 2 的幂这样算下标可以用hash sizemask代替取模位运算快rehashidx是进度指针-1 表示没在 rehash哈希冲突两个 key 算出来的下标一样就叫冲突。Redis 用的是链地址法冲突的节点挂在同一个桶的链表上table[5] ──► entry(K1) ──► entry(K7) ──► entry(K3) ──► NULL新节点插在链表头部不是尾部。原因是dictEntry只有next没有prev也没有尾指针头插一步搞定是 O(1)尾插得先走到链表末尾是 O(n)。链表长了会退化。如果攻击者能构造出一堆哈希值相同的 key所有节点挤在一条链上查找就从 O(1) 变成 O(n)。所以 Redis 4.0 之后哈希函数换成了 SipHash它对这种碰撞攻击不敏感。拉链法的桶数够多、哈希函数够散链就不会长每次查找差不多就是算一次哈希、比一次 key。真正麻烦的不是冲突是冲突多到需要扩容。扩容和缩容负载因子load factor就是used / size用来衡量桶的拥挤程度。扩容的触发条件在_dictExpandIfNeeded里if(d-ht[0].usedd-ht[0].size(dict_can_resize||d-ht[0].used/d-ht[0].sizedict_force_resize_ratio))// 5{dictExpand(d,d-ht[0].used*2);}翻译一下只要用掉的节点数不小于桶数负载因子 ≥ 1正常情况下就扩容。但有个前提dict_can_resize它在有子进程跑BGSAVE或BGREWRITEAOF的时候是 0。为什么这时候要压住BGSAVE会fork一个子进程父子进程共享内存页父进程任何写操作都会触发写时复制。扩容要改table指针、搬大量数据会搅动很多内存页把共享的页复制成两份内存占用一下子涨上去。所以有子进程在跑的时候负载因子要涨到 5 才会强行扩容这就是dict_force_resize_ratio的作用。扩容到多大used * 2之后往上取最近的 2 的幂。比如used是 1000目标就是 2048 个桶。缩容的触发条件不一样是负载因子小于 0.1used / size 0.1 → 缩容缩容到第一个不小于used的 2 的幂。扩容在插入路径上顺手检查缩容则是靠serverCron定时任务里的tryResizeHashTables定期看一眼因为删除操作不像插入那么频繁。渐进式 Rehash问题出在搬迁的量上。假设ht[0]有 400 万个节点现在要扩到 800 万个桶把 400 万个节点一条条重新算哈希、挂到新表上这个操作可能要几百毫秒。Redis 是单线程处理命令的这几百毫秒里所有请求都得等线上就是一次明显的卡顿。Redis 的解法是把这次搬迁摊到后续的每一次操作里每次搬一点。整个过程分几步1. 给 ht[1] 分配空间大小是第一个 used*2 的 2 的幂 rehashidx 置 0 2. 每次对 dict 做增删改查干完正事顺手搬一个桶 把 ht[0].table[rehashidx] 这条链上的所有节点搬到 ht[1] 然后 rehashidx 3. 期间写入的新节点一律进 ht[1]ht[0] 只减不增 4. 查找时先在 ht[0] 找找不到再去 ht[1] 找 5. ht[0] 搬空了rehashidx -1 把 ht[1] 设成 ht[0]原来的 ht[1] 清零第 3 步是关键。rehash 期间如果有新节点往ht[0]写ht[0]就永远搬不完。所以规则定死了rehash 期间ht[0]只读不写所有新增都进ht[1]。第 4 步是查找要查两个表的代价。一个 key 可能在老表里还没搬走也可能已经在新表里了两边都得找一遍。不过这个代价是有界的最多查两次。光靠操作驱动不够如果某个 dict 建完之后长期没被访问就没人触发第 2 步rehash 停在半路ht[0]和ht[1]两个表同时占着内存等于内存翻倍还多。所以还有一条兜底路径。serverCron会周期性调用databasesCron里面有个incrementallyRehash它调用dictRehashMilliseconds(1)意思是主动搬 1 毫秒的活。这样即使没有请求rehash 也会往前走。搬运的最小单位是一个桶。dictRehash每次最多扫n * 10个空桶就停下避免连续碰到一大片空桶这在缩容后很常见时卡在原地太久。大 Hash 的代价回到 Hash 的编码选择。一个 Hash 字段少的时候是 listpack省内存一旦超过阈值变成 hashtable代价就上来了。两个地方会显内存hashtable 编码下每个字段都是一个独立的dictEntry加上 key、value 各自的 robj光指针和对象头就是几十字节。同样的数据listpack 里是挨着存的一大块没有这些开销rehash 期间ht[0]和ht[1]同时在两个桶数组一起占内存峰值能到平时的两倍所以别把一个 Hash 当成大集合用。字段到了几万、几十万HGET是快但内存和遇到扩容时的压力都不划算这种场景要拆 key或者换更合适的结构。存对象用 String 还是 Hash这个选择经常要做。同一个用户对象可以整体序列化成 JSON 存 String也可以拆成字段存 HashSET user:1{name:tom,age:18,city:sh}HSET user:1 name tom age18citysh维度StringHash读写粒度整个对象单个字段改一个字段读出来、改、整个写回一条HSET字段级过期做不到除了拆 key最近才支持见下字段多时内存拆成多 key 的话每字段都有 key 开销listpack 下字段挨着存省字段少时内存一个 key直接多一层 robj略多判断的逻辑对象整个读、整个写不怎么改单个字段用 String。缓存场景大部分是这种要频繁改某个字段或者要按字段读用 Hash。不然每次改一个字段都要把整个对象反序列化、改完再序列化写回白白浪费 CPU别用user:1:name、user:1:age这样把一个对象拆成一堆 String key。每个 key 都是一个dictEntry加一个 robj字段一多内存就上去了。这种情况应该用一个 Hash反过来字段只有两三个、又不需要字段级操作直接存一个 String 更省事字段级过期是个例外情况。Redis 7.4 之前Hash 不能给单个字段设 TTL只能整个 key 过期。7.4 加了HEXPIRE、HTTL这一组命令才支持。如果你用的是 7.4 之前的版本又需要对象里某个字段单独过期那就只能把它拆成独立的 String key。ZSet 也同时用了跳表和dict不过那里dict是为了按 member 查 score见ZSet 那篇。