Redis（三）存储原理与数据模型（hash冲突、渐进式rehash）_渐进式rehash解决hash冲突

Redis系列文章

Redis（一）原理及基本命令（柔性数组）
Redis（二）网络协议和异步方式（乐观锁&悲观锁）
Redis（三）存储原理与数据模型（hash冲突、渐进式rehash）
Redis跳表

---

一、redis 存储结构

Redis是key-value的结构，其中value包含：字典，双向链表，压缩列表，跳表，整数数组，动态字符串。

存储转换

其中redis中各value的数据结构根据不同的情况有不同的自动存储转换。

键值存储实现

redis 中 K-V 组织是通过字典来实现的，也就是hash表。key字符串经过 hash 函数运算得到 64 位整数；

hash冲突

redis采用hash表存储key-value就会遇到hash冲突的情况。常见的hash冲突解决方式有：

• 开链法：将hash冲突的value值用链表连接，每个hash结果的key值下面都连接一个链表。如果链表过长还可以将链表转化为红黑树来优化。
• rehash：即增加hash桶的大小。redis有两个hash表，当hash表1冲突了，就会采用hash表2，而hash表2的hash桶大小通常是hash表1的2倍。

但是rehash时，将hash表1的数据复制到hash表2是一个庞大的工程，可能会造成redis线程阻塞，影响redis性能。因此redis有渐进式rehash的机制来解决这个问题。

渐进式rehash

渐进式rehash和rehash一样，同样需要将hash表1的数据复制到hash表2，但是这个复制过程不是一次性的，而是一步一步分块转移。

redis的渐进式有两种规则：

1. 分治的思想，将 rehash 分到之后的每步增删改查的操作当中，即每次处理redis时，复制一个key；
2. 在定时器中，最大执行一毫秒 rehash ；每次复制100 个数组key槽位；

rehash 过程中如果入到增删查改时会怎么做？

• 查：查找数据时，会先在hash表1中查找数据，如果没找到就会在hash表2中去找。
• 增：新增数据时，只会增加到hash表2中，不会在hash表1做任何操作。
• 删&改：在两个表上都会操作。

redis除了扩容会有渐进式rehash，其实缩容时也会采用rehash。
但是在rehash阶段，不会再发生扩容和缩容。必须等rehash结束。

大KEY

在 redis 实例中假如形成了很大的对象，比如一个很大的 hash 或很大的 zset，这样的对象在扩容的时候，会一次性申请更大的一块内存，这会导致卡顿；如果这个大 key 被删除，内存会一次性回收，卡顿现象会再次产生；如果观察到 redis 的内存大起大落，极有可能因为大 key 导致的；

解决方法：

• 拆分value
• 压缩value
• 删除非热点大key（可使用redis异步机制删除）

跳表

Redis 中的有序集合(Sorted Set)是用跳表（Skip list）来实现的。跳表就是解决链表在有序节点场景下的查询时间复杂度高问题。时间复杂度能达到O(logn)。
详细内容参考Redis跳表