redis渐进式rehash(redis 深入)

本篇文章给大家谈谈redis渐进式rehash,以及redis 深入对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。

本文目录一览:

Redis底层数据结构

Redis中值的数据结构有String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合)五种,使用可参考 。

而底层数据结构一共有 6 种,分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示:

可以看到,String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。通常情况下,我们会把这四种类型称为集合类型,它们的特点是一个键对应了一个集合的数据。

为了实现从键到值的快速访问,Redis 使用了一个哈希表来保存所有键值对。一个哈希表,其实就是一个数组,数组的每个元素称为一个哈希桶。哈希桶中的元素保存的并不是值本身,而是指向具体值的指针。

这也就是说,不管值是 String,还是集合类型,哈希桶中的元素都是指向它们的指针。在下图中,可以看到,哈希桶中的歼明 entry 元素中保存了 key和 value指针,分别指向了实际的键和值。

哈希冲突,也就是指,两个 key 的哈希值和哈希桶计算对应关系时,正好落在了同一个哈希桶中。毕竟,哈希桶的个数通常要少于 key 的数量,这也就是说,难免会有一些 key 的哈希值对应到了同一个哈希桶中。Redis 解决哈希冲突的方式,就是 链式哈希 。链式哈希也很容易理解,就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。

如下图所示:entry1、entry2 和 entry3 都需要保存在哈希桶 3 中,导致了哈希冲突。此时,entry1 元素会通过一个 next指针指向 entry2,同样,entry2 也会通过 next指针指向 entry3。这样一来,即使哈希桶 3 中的元素有 100 个,我们也可以通过 entry 元素中的指针,把它们连起来。

其实,为了使 rehash 操作更高效,Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2。一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。随着数据逐步增多,Redis 开始执行 rehash,这个过程分为三步:

这个过程看似简单,但是第二步涉及大量的数据拷贝,如果一次性悔蔽把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求。此时,Redis 就无法快速访问数据了。为了避免这个问题,Redis 采用了 渐进式 rehash 。

简单来说就是在第二步拷贝数据时,Redis 仍然正常处理客户端请求,每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;等处理下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示:

对于 String 类型来说,找到哈希桶就能直接增删改查了碧改州,所以,哈希表的 O(1) 操作复杂度也就是它的复杂度了。

一个集合类型的值,第一步是通过全局哈希表找到对应的哈希桶位置,第二步是在集合中再增删改查。首先,操作复杂度与集合的底层数据结构有关。例如,使用哈希表实现的集合,要比使用链表实现的集合访问效率更高。其次,操作效率和这些操作本身的执行特点有关,比如读写一个元素的操作要比读写所有元素的效率高。

String类型对应的简单动态字符串到后面再说,集合类型的底层数据结构主要有 5 种:整数数组、双向链表、哈希表、压缩列表和跳表。

整数数组和双向链表也很常见,它们的操作特征都是顺序读写,也就是通过数组下标或者链表的指针逐个元素访问,操作复杂度基本是 O(N),操作效率比较低;压缩列表和跳表我们平时接触得可能不多,但它们也是 Redis 重要的数据结构。

压缩列表 实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。

跳表 在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图所示:

Redis 之所以能快速操作键值对,一方面是因为 O(1) 复杂度的哈希表被广泛使用,包括 String、Hash 和 Set,它们的操作复杂度基本由哈希表决定,另一方面,Sorted Set 也采用了 O(logN) 复杂度的跳表。不过,集合类型的范围操作,因为要遍历底层数据结构,复杂度通常是 O(N)。

不能忘了复杂度较高的 List 类型,它的两种底层实现结构:双向链表和压缩列表的操作复杂度都是 O(N)。因此,因地制宜地使用 List 类型。例如,既然它的 POP/PUSH 效率很高,那么就将它主要用于 FIFO 队列场景,而不是作为一个可以随机读写的集合。

Redis设计与实现3 哈希对象( ziplist /hashtable)

ziplist 编码的哈希对象使用压缩列表作为底层实现, 每当有新的键值对要加入到哈希对象时, 程序会先将保存了键的压缩列表节点推入到压缩列表表尾, 然后再将保存了值的压缩列表节点推入到压缩列表表尾, 因此:

保存了同一键值对的两个节点总是紧挨在一起, 保存键的节点在前, 保存值的节点在后;

先添加到哈希对象中的键值对会被放在压缩列表的表头方向, 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

举个例子, 如果我们执行以下 HSET 命令, 那么服务器将创建一个列表对象作明胡为 profile 键的值:

另一方面, hashtable 编码的哈希对象使用字典作为底层实现, 哈希对象中的每个键值对都使用一个字典键值对来保存:

Redis 的字典使用哈希表作为底层实现, 一个哈希表里面可以有多个哈希表节点, 而每个哈希表节点就保存了字典中的一个键值对。

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

table 属性是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针, 每个陆槐滚 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小, 也即是 table 数组的大小, 而 used 属性则记录了哈希表目前已有节点(键值对)的数量。

sizemask 属性的值总是等于 size - 1 , 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

图 4-1 展示了一个大小为 4 的空哈希表 (没有包含任何键值对)。

哈希表节点使用 dictEntry 结构表示, 每个 dictEntry 结构都保存着一个键值对:

key 属性保存着键值对中的键, 而 v 属性则保存着键值对中的值, 其中键值对的值可以是一个指针, 或者是一个 uint64_t 整数早余, 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题。

举个例子, 图 4-2 就展示了如何通过 next 指针, 将两个索引值相同的键 k1 和 k0 连接在一起。

Redis 中的字典由 dict.h/dict 结构表示:

type 属性和 privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的:

ht 属性是一个包含两个项的数组, 数组中的每个项都是一个 dictht 哈希表, 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外, 另一个和 rehash 有关的属性就是 rehashidx : 它记录了 rehash 目前的进度, 如果目前没有在进行 rehash , 那么它的值为 -1 。

图 4-3 展示了一个普通状态下(没有进行 rehash)的字典:

在Redis中,由于它对实时性要求更高,因此使用了渐进式rehash

当有新键值对添加到Redis字典时,有可能会触发rehash。Redis中处理哈希碰撞的方法与Java一样,都是采用链表法,整个哈希表的性能则依赖于它的大小size和它已经保存节点数量used的比率。

比率在1:1时,哈希表的性能最好,如果节点数量比哈希表大小大很多的话,则整个哈希表就退化成多个链表,其性能优势全无。

上图的哈希表,平均每次失败查找需要访问5个节点。为了保持高效性能,在不修改键值对情况下,

需要进行rehash,目标是将ratio比率维持在1:1左右。

Ratio = Used / Size

rehash触发条件:

rehash执行过程:

Redis哈希为了避免整个rehash过程中服务被阻塞,采用了渐进式的rehash,即rehash程序激活后,并不是

马上执行直到完成,而是分多次,渐进式(incremental)的完成。同时,为了保证并发安全,在执行rehash

中间执行添加时,新的节点会直接添加到ht[1]而不是ht[0], 这样保证了数据的完整性与安全性。

另一方面,哈希的Rehash在还提供了创新的(相对于Java HashMap)收缩(shrink)字典,当可用节点远远

大于已用节点的时候,rehash会自动进行收缩,具体过程与上面类似以保证比率始终高效使用。

当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码:

[img]

Redis字典的渐进式rehash

扩展或收缩哈希表需要将ht[0]中的所有键值对rehash到ht[1]中。不过,这个rehash的动作不一定是一次性、集中式完成的,而是分多次、渐进式完成的。

这样历氏做的原因在于,避免当ht[0]中保存了太多的键值对时,一次性集中式rehash让服务器在较长的时间内停止服务。rehash动作的过程中肯定是不能对外提供增删改查的操作的,如果ht[0]中只有四个键值对的话,那么一次性完成rehash也不会对服务器的运行造成太多延迟,但如果是四百万、四千万的话一次性完成rehash将会严重阻塞服务器运行。

以下是哈希表渐进式rehash的详细步骤:

渐进式 rehash 采用了 分治 的思想,将 rehash 键值对所需的工作分摊到了每次对字典的增删改查操作上,虽然降低了 redis 服务器的整体吞吐量,但提升了响应速度,不会出现在某次操作时特别慢的情况。

因为在渐进式 rehash 的过程中,字典会同时使用 ht[0] 和 ht[1] 两个哈希表,所以在这个过程中对字典的增删改查操作会在两个哈希表上进行。例如在字典上查找一伏亏个键时,程肢厅散序会先查询ht[0],如果没有查到就再查 ht[1]。

新添加到字典上的键值对只会保存在ht[1]上,而ht[0]上不再进行任何添加操作,这样就保证了ht[0]中包含的键值对的数量只减不增,并随着rehash的进行而逐渐变成空表。

关于redis渐进式rehash和redis 深入的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。

相关阅读

  • mssqlserver(mssqlserver怎么安装)

    mssqlserver(mssqlserver怎么安装)

    简介:MSSQL Server是由微软公司开发的一种关系型数据库管理系统,是在Windows操作系统上运行的数据库服务器。它旨在提供可靠性、高性能和安全性,被广泛应用于企业级应用程序和网站开发中。多级标题:一、MSSQL Server的特点...

    2024.04.22 22:38:00作者:intanet.cnTags:mssqlserver
  • js转json(js转json在线)

    js转json(js转json在线)

    **简介**在IT技术领域中,JavaScript(简称JS)是一种常用的脚本语言,用于网页开发和编程。JSON(JavaScript Object Notation)则是一种轻量级的数据交换格式,常用于存储和传输数据。本文将讨论如何将Ja...

    2024.04.22 22:23:30作者:intanet.cnTags:js转json
  • 数据库有那些(数据库有哪些索引)

    数据库有那些(数据库有哪些索引)

    一、简介数据库是计算机中用于存储和管理数据的系统,是信息系统中最重要的组成部分之一。数据库技术在信息化时代发挥着重要作用,广泛应用于各行各业。数据库的种类有很多,每种都有其特点和适用场景。下面将介绍一些常见的数据库类型。二、关系数据库1....

    2024.04.22 22:14:00作者:intanet.cnTags:数据库有那些
  • 关于sparksqlsplit的信息

    关于sparksqlsplit的信息

    简介:作为一种基于内存的分布式数据处理框架,Spark SQL使得数据分析更加高效和灵活。而在Spark SQL中,split函数是非常常用的函数,用于将字符串通过指定的分隔符进行拆分。本文将详细介绍sparksqlsplit函数的用法和示...

    2024.04.22 22:13:30作者:intanet.cnTags:sparksqlsplit
  • 数据的处理方法(实验数据的处理方法)

    数据的处理方法(实验数据的处理方法)

    在当今数字化时代,数据处理变得越发重要。从企业管理到科研领域,人们需要处理大量的数据以获取有价值的信息。本文将介绍一些常见的数据处理方法,帮助读者更好地理解和应用数据处理技术。# 传统数据处理方法传统数据处理方法主要包括数据录入、数据清洗、...

    2024.04.22 22:09:30作者:intanet.cnTags:数据的处理方法
  • mongodb和hbase(mongodb和hbase性能)

    mongodb和hbase(mongodb和hbase性能)

    MongoDB和HBase是两种流行的NoSQL数据库系统,它们在处理大规模数据和高并发访问方面都有很好的表现。本文将对MongoDB和HBase进行比较和分析,以帮助读者了解它们各自的优缺点和适用场景。# 一、MongoDB介绍Mongo...

    2024.04.22 22:00:00作者:intanet.cnTags:mongodb和hbase
  • mysql转sqlserver(MySQL转sqlserver数据库)

    mysql转sqlserver(MySQL转sqlserver数据库)

    **简介**将MySQL数据库转移到SQL Server数据库是常见的需求,因为有时候企业需要更稳定、更强大的数据库管理系统来满足数据需求。在本文中,我们将详细讨论如何将MySQL数据库成功转移到SQL Server数据库。**准备工作**...

    2024.04.22 21:45:30作者:intanet.cnTags:mysql转sqlserver
  • 数据库的建立(数据库的建立与维护实验心得)

    数据库的建立(数据库的建立与维护实验心得)

    标题:数据库的建立简介:数据库是指在计算机系统中,用于存储和管理数据的系统。在IT技术领域,数据库起着至关重要的作用,它可以帮助我们更好地组织和管理数据,提高数据的访问效率和安全性。下面将详细介绍数据库的建立过程和相关知识。一、数据库类型1...

    2024.04.22 21:30:00作者:intanet.cnTags:数据库的建立