Redis 的 Key 是如何寻址的?

JAVA herman 249浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

大家都知道 Redis 很快,用的公司也非常多。因此,面试中遇到 Redis 几乎是 100%。这两天,有网友给我留言,面试中被问到“Redis 的 Key 是如何寻址的?”关于这个问题,今天我们来简单的解答一下!

Redis 服务器在初始化时,默认的会预先分配 16 个数据库。这其中的每一个数据库,都由一个 redisDb 的结构存储。redisDb 的结构中有两个重要的部分:

  • redisDb.id:存储着 redis 数据库以整数表示的号码。
  • redisDb.dict:存储着该库所有的键值对数据。
  • redisDb.expires:保存着每一个键的过期时间。

针对 Redis 中的众多数据库,当我们使用 select number 选择数据库时,程序可以直接通过 redisServer.db[number] 来切换数据库。有时候当程序需要知道自己是在哪个数据库时,也可以直接通过读取 redisDb.id 即可。

Redis 的字典使用哈希表作为其底层实现。dict 类型使用的两个指向哈希表的指针,其中 0 号哈希表(ht[0])主要用于存储数据库的所有键值,而 1 号哈希表主要用于程序对 0 号哈希表进行 rehash 时使用,rehash 一般是在添加新值时会触发,这里不做过多的赘述。所以 redis 中查找一个 key,其实就是对进行该 dict 结构中的 ht[0] 进行查找操作。

既然是哈希,那么我们知道就会有哈希碰撞,那么当多个键哈希之后为同一个值怎么办呢?redis 采取链表的方式来存储多个哈希碰撞的键。也就是说,当根据 key 的哈希值找到该列表后,如果列表的长度大于 1,那么我们需要遍历该链表来找到我们所查找的 key。当然,一般情况下链表长度都为是 1,所以时间复杂度可看作 o(1)。

根据上面的解释,以及官方文档和源码解毒。我们可以得出,Redis 的 Key 寻址包含一下步骤:

  1. 当拿到一个 key 后,redis 先判断当前库的 0 号哈希表是否为空,即:if (dict->ht[0].size == 0)。如果为 true 直接返回 NULL。
  2. 判断该 0 号哈希表是否需要 rehash,因为如果在进行 rehash,那么两个表中都有可能存储该 key。如果正在进行 rehash,将调用一次_dictRehashStep 方法,_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash。
  3. 计算哈希表,根据当前字典与 key 进行哈希值的计算。
  4. 根据哈希值与当前字典计算哈希表的索引值。
  5. 根据索引值在哈希表中取出链表,遍历该链表找到 key 的位置。一般情况,该链表长度为 1。
  6. 当 ht[0] 查找完了之后,再进行了次 rehash 判断,如果未在 rehashing,则直接结束,否则对 ht[1]重复 345 步骤。

如果是 Redis 集群模式,则需要先判断 key 在哪一个节点上。

Redis 的 key 寻址

以上,只是我个人的片面理解,如有错误,请大家帮我指正。另外,懂 C 的,可以跑一遍 Redis 的源码。分享出相关的寻址步骤,我们一起精进!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:codedq(5000人已满),微信号3:xttblog(超2800)。备注:“xttblog”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Redis 的 Key 是如何寻址的?