Hash底层存储原理及优化Redis中big Hash的一些建议

By | 2021年3月15日

Hash底层存储原理及优化Redis中big Hash的一些建议

Hash 是 Redis 中出现最为频繁的复合型数据结构,除了 dict 结构的数据会用到Hash外,整个 Redis 数据库的所有 key 和 value 也组成了一个全局Hash,还有带过期时间的 key 集合也是一个Hash。set集合相当于一个value为null的Hash,zset 集合中存储 value 和 score 值的映射关系也是通过 hash 结构实现的。

由于业务上考虑不周,使得生产环境中有一个hash结构存储的数据量达到40w,导致redis的内存使用量不断增大,而这个key的查询效率也越来越低,失去了刚开始想用缓存来加快查询速度的初衷。为什么不能出现big hash,这里先分析hash的实现原理与存储过程中的扩容机制。

Hash原理

Hash内部实现结构上同 Java 的 HashMap 大致相同,都是采用数组 + 链表二维结构。第一维 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来,链表长度过长时,查询时间复杂度会降低到O(n)。

image-20210315091020144

Java8中当链表长度大于8时会自动转换为红黑树,提高查询效率,redis对链表采用zipList和hashtable两种结构存储。

底层结构

zipList

ziplist是为了节省内存而开发的一种压缩列表数据结构,ziplist是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个ziplist可以包含任意多个entry,而每一个entry又可以保存一个字节数组或者一个整数值,ziplist不存储指向上一个节点和下一个节点的指针,存储的是上一个节点的长度和当前节点的长度,牺牲了部分读写性能来换取高效的内存利用率,是一种时间换空间的思想,ziplist适用于字段个数少和字段值少的场景。

ziplist的组成结构为:

image-20210315092243393

hashtable

Hashtable是通过dictEntry对象来实现的,将dictEntry对象进行再次包装得到对象dictht:

字典的内部嵌套了哈希表dictht对象,下面是字典的定义:

所以当创建一个哈希对象时,整体类结构如下

image-20210315092210011

ziplist与hashtable转换机制

当一个哈希对象可以满足以下两个条件中的任意一个,哈希对象会选择使用ziplist来进行存储:

  1. 哈希对象中的所有键值对总长度(包括键和值)小于64字节(这个阈值可以通过参数hash-max-ziplist-value 来进行控制)。
  2. 哈希对象中的键值对数量小于512个(这个阈值可以通过参数hash-max-ziplist-entries 来进行控制)。

一旦不满足这两个条件中的任意一个,哈希对象就会选择使用hashtable来存储。

扩容流程

大字典的扩容是非常耗时间的,需要重新申请新的数组,正常情况下,当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个 O(n)级别的操作,Redis 使用渐进式 rehash 扩容,分多次来慢慢的将旧数组中的键值对rehash到新数组的操作就称之为渐进式rehash。渐进式rehash可以避免了集中式rehash带来的庞大计算量,在渐进式rehash过程中,因为还可能会有新的键值对存进来,此时Redis的做法是新添加的键值对统一放入ht[1]中,这样就确保了ht[0]键值对的数量只会减少,当执行rehash操作时需要执行查询操作,此时会先查询ht[0],查找不到结果再到ht[1]中查询。

问题分析

1.存储问题

当key值到达40w左右,底层存储必然会转换为hashtable,相比hashtable,ziplist结构少了指针,大大的减少了内存的使用,而内存对于redis来说弥足珍贵,ziplist存储时内存分配是连续的,查询更快。

2.扩容问题

每次扩容需要先申请2倍于当前数组大小的新数组,旧数组越大,新数组的内存占用也会翻倍,当扩容过程中,由于redis是单线程,在将旧数据搬迁的的过程中还要支持其他操作的进行,如果此时数据还在不断增加,可能会出现redis迁移很久终于迁到新数组后,又达到扩容条件,需要继续扩容迁移。整个redis服务器的性能都会被拖累。

3.查询问题

当key值数量倍增,发生hash冲突的概率也会增加,redis底层只有链表来存储,没有使用查询树等高效的数据结构,会让查询速度从O(1)退化到O(n),影响业务查询效率和用户体验。

优化建议

  1. 旧数据的需求是怎样的,是否可以通过更换数据结构来实现,如果只是简单的判断该数据是否存在,可以使用布隆过滤器,布隆过滤器适用位数组实现,内存占用特别小,虽然可能出现一定的偏差,但不会造成大规模缓存穿透的问题,小部分数据错误可以通过数据库层面处理,不影响正常请求的流程。
  2. 将key根据关键字段来划分,key名称一般为xxx:xxx:xxx,:的使用类似于一种树形结构,我们可以用不同类型区分不同的hash,或者还可以用时间来划分,时间划分区间可以稍大些,如每个月或每周作为命名区间,这样在查询的时候可以用类型字段时间字段进行不同的分流,还可以省去判断机制,尽量将每个hash的key数量保持在1w左右。
  3. 合理的删除机制,因为只能设置hash整体的过期时间,而不能细化到每一个key,所以需要在代码里去定时判断,及时删除很少被使用的key值,只留下热点数据。
  4. 使用str来代替hash,这样的好处是可以灵活的对每个str设置过期时间,每次访问的时候再不断更新过期时间,保证热点数据不会超时,冷数据能自动失效,但这样也存在一些问题,redis中对过期数据的清理是采用随机策略和惰性策略,这样能防止大规模数据失效进行清除时占用主线程,然而也会导致很多数据即使过期了也不会真的被清理掉,redis的内存占用还是会不断增加。
  5. 优化key或value的内容大小,例如user可以替换为u,order使用o,数据的命名上保持简洁明了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注