侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Redis 常见数据结构的底层实现系列(一):全局哈希表

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 101 阅读 / 2,025 字

Redis 之所以能够成为高性能键值对数据库,除了基于内存操作和非阻塞 IO 多路复用的单线程 IO 模型外,还得益于这些数据结构底层的高性能设计。

全局哈希表

首先,从 Redis 全局来看,不管是字符串(String)、列表(List)、集合(Set)、有序集合(Sorted Set)还是字典(Hash)类型,都是一个键值对结构,这些上层可见的数据类型其实都是针对键值类型而言的:对于字符串而言,键值是简单的数字或者字符串类型,对于其他类型而言,键值是列表、集合、字典等复合类型。

所以从全局而言,对于单个 Redis 数据库实例而言,底层的数据结构就是一张巨大的哈希表(或者叫散列表,哈希和散列二者是等价的),所有的字符串、列表、集合、有序集合、字典都是通过键值对挂载在这张哈希表上,哈希表的键就是经过哈希运算后的 Redis 键名字符串指针,哈希表的值则是 Redis 键值对应的指针。

既然是哈希表,就会存在哈希冲突,为了解决哈希冲突,业界现在通用的做法是通过链地址法将冲突的键名通过链表串起来,对于这样的哈希表实现,又被称为哈希桶(就像一个个桶一样,每个桶中存放的是键值对链表,如果对应键名有哈希冲突,则链表会变长),Redis 底层也是这么做的:

1.jpeg

哈希表的查询性能和存放数据量的多少并没有关系,不管哈希表中存放的是100万条记录还是1亿条记录,哈希表的查询时间复杂度是 O(1),性能是最佳的,得益于此,Redis 可以通过键名快速定位到键值指针的位置,再通过指针操作获取对应的键值返回给客户端,非常高效。

哈希冲突和 rehash

但这是理想情况,实际业务中,随着 Redis 存放数据越来越多,哈希表越来越大,会导致哈希冲突的概率越来越高,而 Redis 处理哈希冲突的方式是链地址法,如果某个键上哈希冲突非常严重,会导致对应的链表越来越长。

而我们知道,链表这种数据结构查询的时间复杂度是 O(n),查询性能不高,为了避免长链表造成查询性能下降,Redis 底层会通过 rehash 操作将现有哈希表进行扩容从而分散单个桶中的元素,具体做法是 Redis 默认会维护两个哈希表,当需要做 rehash 时,为备用哈希表分配两倍于现有哈希表的空间,然后将现有哈希表中的元素复制到新的哈希表,最后释放老的哈希表。

由于新的哈希表空间是老的哈希表的两倍,就可以将老哈希表的键值对分散到更多桶里,解决哈希冲突导致的链表过长问题。

不管是哈希冲突,还是 rehash,都会降低 Redis 的查询性能,尤其是 rehash,如果 Redis 数据库实例非常大的话,这个操作是非常耗时的,而 Redis 又是单线程 IO 模型,任何阻塞操作都会导致后续指令无法执行,进而导致 Redis 服务出现卡顿现象。

为了优化这个问题,Redis 采用了渐进式 rehash:在复制元素到新哈希表的过程中,仍然正常处理客户端请求,只不过每处理一个请求时,都会从现有哈希表中的第一个桶开始,将该桶中的所有元素复制到新哈希表中,然后处理下一个请求时,再复制现有哈希表下一个桶中的所有元素,依次类推,直到现有哈希表所有元素都被复制到新哈希表,再将其释放,作为新哈希表需要 rehash 时的备用哈希表。

这样一来,本来需要停下来一次性 rehash 的操作就被分散成多次粒度更小的操作,避免了单次 rehash 耗时过长导致 Redis 服务卡顿甚至不可用的问题,而在此过程中,Redis 查询会同时查询两张哈希表,时间复杂度仍然是 O(1),不会带来大的影响。

设置多个数据库和 scan 指令

基于以上介绍,你应该能解答为什么线上 Redis 实例存放数据非常多,要设置多个数据库实例了吧,这也是为了分散元素,降低哈希冲突和 rehash 的概率。

由此,还引入了另一个问题,那就是执行 keys 指令对键名进行查询和匹配时,会涉及到对 Redis 哈希表的进行遍历,如果哈希表非常大,这个指令也是非常耗时的,也会导致 Redis 服务阻塞,要优化这个问题,可以使用 scan 指令替代 keys 来匹配键名,该指令可以设置起始游标和返回的查询结果数量,就像 MySQL 的分页查询一样,避免对哈希表进行扫描:

scan 0 match *name* count 10

上述指令的含义是从 0 开始,返回 10 个包含 name 字符串的键名,在生产环境,建议使用这个指令查询键名,关于该指令的使用细节,请参考官方文档介绍。

0

评论区