前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Redis中Rehash浅析

Redis中Rehash浅析

作者头像
码农编程进阶笔记
发布2023-03-23 12:59:16
5930
发布2023-03-23 12:59:16
举报
文章被收录于专栏:码农编程进阶笔记

Redis 键值对结构

HashTable:Redis中有一个「全局哈希表」,该哈希表中保存所有的键值对。对于Hash表的查找操作时间复杂度为O(1)

Bucket:哈希表中的每一个元素称为哈希桶(Bucket),哈希桶中保存了键值对数据

Entry:保存键值对数据,如上图:其实Entry中保存的是Key,Value的指针值,通过对应的指针能够对Key,Value进行查找

举个例子:假设你现在要往Redis中写入一个String类型的数据,其中Key=username_1 ,Value=小明,那么Redis将调用Hash函数计算Key的哈希值,根据哈希值选择哈希表中对应的哈希桶,然后将Key,Value进行存储。并将Key,Value的指针存入哈希桶的Enrty中。

Rehash

哈希冲突

哈希表中桶的数量是有限的,当Key的数量较大时自然避免不了哈希冲突(多个Key落在了同一个哈希桶中)。当哈希桶中存在哈希冲突时那么多个Entry就形成了链表,每个链表中有一个Next指针指向了下一个元素。当哈希桶中的链表过长时,那么查询性能会显著降低(链表的查找时间复杂度为O(N)),Redis为了避免类似的问题从而会进行Rehash操作。

Rehash

为了能够减少哈希冲突,其实最直接的做法是增加哈希桶数量从而让元素能够更加均匀的分布在哈希表中。而Redis中的Rehash操作的原理其实也是如此,只不过他的设计更加巧妙。

  1. Redis中其实有两个「全局哈希表」,一开始时默认使用的Hash Table1来存储数据,而Hash Table2并没有分配内存空间。
  2. 随着Hash Table1中的元素越来越多时,Redis会进行Rehash操作。
  3. 首先会给Hash Table2分配一定的内存空间(肯定比哈希表一大),然后将Hash Table1中的元素重新映射至Hash Table2中,最后会释放Hash Table1。
  4. 这样来看的话,Redis的Rehash操作的确能减少哈希冲突,但是你有没有想过如果Hash Table1中的元素特别多时,如果这么粗暴的将数据往Hash Table2中搬,那势必会阻塞Redis的主线程进而影响Redis的性能。

其实Redis也考虑到了这个问题,那么接下来我们看看Redis是如何解决这种问题的

渐进式Rehash

如上图所示,渐进式Rehash采用的做法是:

  1. 在将数据拷贝至Hash Table2时,Hash Table1仍然对客户端提供服务。
  2. 当客户端访问Hash Table1时,Hash Table1 将索引位置为1的Bucket1中的Entery全部拷贝至Hash Table2。
  3. 同理当客户端再一次访问Hash Table1时,Hash Table1 将索引位置为2的Bucket2中的Entery全部拷贝至Hash Table2。
  4. 再拷贝数据进Hash Table2的同时会对数据做重新的Bucket分配,从而减少Hash冲突
  5. 如此往复下去,当Hash Table1的元素都拷贝Hash Table2时,Hash Table2会顶替Hash Table1 与客户端进行交互,此时Hash Table1会被释放,等待下一次Rehash使用。

总结

上文中我们描述了Redis是通过Hash Table的方式来组织所有的键值对,Hash Table中的元素为Bucket(哈希桶)。Bucket中存储着键值对的指针。

当Hash Table中的元素逐渐增多时,会在Bucket中形成链表,一旦链表过长则会严重影响Redis的查询性能,这对以速度著称的Redis是不能接受的。所以Redis采用了增加Hash Table的容量来解决这个问题,也就是所谓的Rehash机制,而Redis为了减轻Rehash时数据大量拷贝锁带来的压力,从而采用了渐进式Rehash来分批次的进行数据拷贝。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2023-02-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码农编程进阶笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档