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的渐进式有两种规则:
- 分治的思想,将 rehash 分到之后的每步增删改查的操作当中,即每次处理redis时,复制一个key;
- 在定时器中,最大执行一毫秒 rehash ;每次复制100 个数组key槽位;
rehash 过程中如果入到增删查改时会怎么做?
- 查:查找数据时,会先在hash表1中查找数据,如果没找到就会在hash表2中去找。
- 增:新增数据时,只会增加到hash表2中,不会在hash表1做任何操作。
- 删&改:在两个表上都会操作。
redis除了扩容会有渐进式rehash,其实缩容时也会采用rehash。
但是在rehash阶段,不会再发生扩容和缩容。必须等rehash结束。
大KEY
在 redis 实例中假如形成了很大的对象,比如一个很大的 hash 或很大的 zset,这样的对象在扩容的时候,会一次性申请更大的一块内存,这会导致卡顿;如果这个大 key 被删除,内存会一次性回收,卡顿现象会再次产生;如果观察到 redis 的内存大起大落,极有可能因为大 key 导致的;
解决方法:文章来源:https://www.toymoban.com/news/detail-573392.html
- 拆分value
- 压缩value
- 删除非热点大key(可使用redis异步机制删除)
跳表
Redis 中的有序集合(Sorted Set)是用跳表(Skip list)来实现的。跳表就是解决链表在有序节点场景下的查询时间复杂度高问题。时间复杂度能达到O(logn)。
详细内容参考Redis跳表文章来源地址https://www.toymoban.com/news/detail-573392.html
到了这里,关于Redis(三)存储原理与数据模型(hash冲突、渐进式rehash)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!