在网站上做漂浮,嘉定企业网站建设,网站建设公司长春,做电影网站模板教学redis 为什么要这莫快#xff1f;一个就是他是基于内存的#xff0c;另外一个就是他是他的数据结构 说到这儿#xff0c;你肯定会说#xff1a;“这个我知道#xff0c;不就是 String#xff08;字符串#xff09;、List#xff08;列表#xff09;、 Hash#xff08… redis 为什么要这莫快一个就是他是基于内存的另外一个就是他是他的数据结构 说到这儿你肯定会说“这个我知道不就是 String字符串、List列表、 Hash哈希、Set集合和 Sorted Set有序集合吗”其实这些只是 Redis 键 值对中值的数据类型也就是数据的保存形式。而这里我们说的数据结构是要去看看 它们的底层实现。
简单来说底层数据结构一共有 6 种分别是简单动态字符串、双向链表、压缩列表、哈 希表、跳表和整数数组。它们和数据类型的对应关系如下图所示 可以看到String 类型的底层实现只有一种数据结构也就是简单动态字符串。而 List、 Hash、Set 和 Sorted Set 这四种数据类型都有两种底层实现结构。通常情况下我们会 把这四种类型称为集合类型它们的特点是一个键对应了一个集合的数据
以上 底层的数据结构我单写一篇文章
看到这里其实有些问题已经值得我们去考虑了 这些数据结构都是值的底层实现键和值本身之间用什么结构组织 为什么集合类型有那么多的底层结构它们都是怎么组织数据的都很快吗 什么是简单动态字符串和常用的字符串是一回事吗 接下来我就和你聊聊前两个问题。这样你不仅可以知道 Redis“快”的基本原理还 可以借此理解 Redis 中有哪些潜在的“慢操作”最大化 Redis 的性能优势。
键和值用什么结构组织
了实现从键到值的快速访问Redis 使用了一个哈希表来保存所有键值对。
一个哈希表其实就是一个数组数组的每个元素称为一个哈希桶。所以我们常说一 个哈希表是由多个哈希桶组成的每个哈希桶中保存了键值对数据。
看到这里你可能会问了“如果值是集合类型的话作为数组元素的哈希桶怎么来保存 呢”其实哈希桶中的元素保存的并不是值本身而是指向具体值的指针。这也就是 说不管值是 String还是集合类型哈希桶中的元素都是指向它们的指针。
在下图中可以看到哈希桶中的 entry 元素中保存了*key和*value指针分别指向了 实际的键和值这样一来即使值是一个集合也可以通过*value指针被查找到。 因为这个哈希表保存了所有的键值对所以我也把它称为全局哈希表。哈希表的最大好 处很明显就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算 键的哈希值就可以知道它所对应的哈希桶位置然后就可以访问相应的 entry 元素。
你看这个查找过程主要依赖于哈希计算和数据量的多少并没有直接关系。也就是说 不管哈希表里有 10 万个键还是 100 万个键我们只需要一次计算就能找到相应的键
但是如果你只是了解了哈希表的 O(1) 复杂度和快速查找特性那么当你往 Redis 中 写入大量数据后就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在 的风险点那就是哈希表的冲突问题和 rehash 可能带来的操作阻塞。
为什么哈希表操作变慢了
当你往哈希表中写入更多数据时哈希冲突是不可避免的问题。这里的哈希冲突也就是 指两个 key 的哈希值和哈希桶计算对应关系时正好落在了同一个哈希桶中。
毕竟哈希桶的个数通常要少于 key 的数量这也就是说难免会有一些 key 的哈希值对 应到了同一个哈希桶中
Redis 解决哈希冲突的方式就是链式哈希。链式哈希也很容易理解就是指同一个哈希 桶中的多个元素用一个链表来保存它们之间依次用指针连接。
如下图所示entry1、entry2 和 entry3 都需要保存在哈希桶 3 中导致了哈希冲突。此 时entry1 元素会通过一个*next指针指向 entry2同样entry2 也会通过*next指针 指向 entry3。这样一来即使哈希桶 3 中的元素有 100 个我们也可以通过 entry 元素 中的指针把它们连起来。这就形成了一个链表也叫作哈希冲突链。 但是这里依然存在一个问题哈希冲突链上的元素只能通过指针逐一查找再操作。如果 哈希表里写入的数据越来越多哈希冲突可能也会越来越多这就会导致某些哈希冲突链 过长进而导致这个链上的元素查找耗时长效率降低。对于追求“快”的 Redis 来说 这是不太能接受的。
所以Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量让逐渐 增多的 entry 元素能在更多的桶之间分散保存减少单个桶中的元素数量从而减少单个 桶中的冲突。那具体怎么做呢
其实为了使 rehash 操作更高效Redis 默认使用了两个全局哈希表哈希表 1 和哈希 表 2。一开始当你刚插入数据时默认使用哈希表 1此时的哈希表 2 并没有被分配空 间。随着数据逐步增多Redis 开始执行 rehash这个过程分为三步
给哈希表 2 分配更大的空间例如是当前哈希表 1 大小的两倍、把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中释放哈希表 1 的空间
到此我们就可以从哈希表 1 切换到哈希表 2用增大的哈希表 2 保存更多数据而原来 的哈希表 1 留作下一次 rehash 扩容备用.
这个过程看似简单但是第二步涉及大量的数据拷贝如果一次性把哈希表 1 中的数据都 迁移完会造成 Redis 线程阻塞无法服务其他请求。此时Redis 就无法快速访问数据 了.
为了避免这个问题Redis 采用了渐进式 rehash
简单来说就是在第二步拷贝数据时Redis 仍然正常处理客户端请求每处理一个请求 时从哈希表 1 中的第一个索引位置开始顺带着将这个索引位置上的所有 entries 拷贝 到哈希表 2 中等处理下一个请求时再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示 这样就巧妙地把一次性大量拷贝的开销分摊到了多次处理请求的过程中避免了耗时操 作保证了数据的快速访问。 好了到这里你应该就能理解Redis 的键和值是怎么通过哈希表组织的了。对于 String 类型来说找到哈希桶就能直接增删改查了所以哈希表的 O(1) 操作复杂度也就 是它的复杂度了。 但是对于集合类型来说即使找到哈希桶了还要在集合中再进一步操作。接下来我 们来看集合类型的操作效率又是怎样的
有哪些底层数据结构
集合类型的底层数据结构主要有 5 种整数数组、双向链表、哈 希表、压缩列表和跳表
其中哈希表的操作特点我们刚刚已经学过了整数数组和双向链表也很常见它们的操 作特征都是顺序读写也就是通过数组下标或者链表的指针逐个元素访问操作复杂度基 本是 O(N)操作效率比较低压缩列表和跳表我们平时接触得可能不多但它们也是 Redis 重要的数据结构所以我来重点解释一下。 压缩列表实际上类似于一个数组数组中的每一个元素都对应保存一个数据。和数组不同 的是压缩列表在表头有三个字段 zlbytes、zltail 和 zllen分别表示列表长度、列表尾的 偏移量和列表中的 entry 个数压缩列表在表尾还有一个 zlend表示列表结束。 在压缩列表中如果我们要查找定位第一个元素和最后一个元素可以通过表头三个字段 的长度直接定位复杂度是 O(1)。而查找其他元素时就没有这么高效了只能逐个查 找此时的复杂度就是 O(N) 了。
我们再来看下跳表。
有序链表只能逐一查找元素导致操作起来非常缓慢于是就出现了跳表。具体来说跳 表在链表的基础上增加了多级索引通过索引位置的几个跳转实现数据的快速定位 如下图所示 可以看到这个查找过程就是在多级索引上跳来跳去最后定位到元素。这也正好符 合“跳”表的叫法。当数据量很大时跳表的查找复杂度就是 O(logN)。 不同操作的复杂度 集合类型的操作类型很多有读写单个集合元素的例如 HGET、HSET也有操作多个元 素的例如 SADD还有对整个集合进行遍历操作的例如 SMEMBERS。这么多操作 它们的复杂度也各不相同。而复杂度的高低又是我们选择集合类型的重要依据。我总结了一个“四句口诀”希望能帮助你快速记住集合常见操作的复杂度。这样你在使用过程中就可以提前规避高复杂度操作了
单元素操作是基础 范围操作非常耗时 统计操作通常高效 例外情况只有几个。 第一单元素操作是指每一种集合类型对单个数据实现的增删改查操作。例如Hash 类 型的 HGET、HSET 和 HDELSet 类型的 SADD、SREM、SRANDMEMBER 等。这些操 作的复杂度由集合采用的数据结构决定例如HGET、HSET 和 HDEL 是对哈希表做操 作所以它们的复杂度都是 O(1)Set 类型用哈希表作为底层数据结构时它的 SADD、 SREM、SRANDMEMBER 复杂度也是 O(1)。 这里有个地方你需要注意一下集合类型支持同时对多个元素进行增删改查例如 Hash 类型的 HMGET 和 HMSETSet 类型的 SADD 也支持同时增加多个元素。此时这些操 作的复杂度就是由单个元素操作复杂度和元素个数决定的。例如HMSET 增加 M 个元 素时复杂度就从 O(1) 变成 O(M) 了。
第二范围操作是指集合类型中的遍历操作可以返回集合中的所有数据比如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS或者返回一个范围内的部分数据比如 List 类型的 LRANGE 和 ZSet 类型的 ZRANGE。这类操作的复杂度一般是 O(N)比较耗时 我们应该尽量避免。 不过Redis 从 2.8 版本开始提供了 SCAN 系列操作包括 HSCANSSCAN 和 ZSCAN这类操作实现了渐进式遍历每次只返回有限数量的数据。这样一来相比于 HGETALL、SMEMBERS 这类操作来说就避免了一次性返回所有元素而导致的 Redis 阻 塞。
第三统计操作是指集合类型对集合中所有元素个数的记录例如 LLEN 和 SCARD。这 类操作复杂度只有 O(1)这是因为当集合类型采用压缩列表、双向链表、整数数组这些数 据结构时这些结构中专门记录了元素的个数统计因此可以高效地完成相关操作。
第四例外情况是指某些数据结构的特殊记录例如压缩列表和双向链表都会记录表头 和表尾的偏移量。这样一来对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操 作来说它们是在列表的头尾增删元素这就可以通过偏移量直接定位所以它们的复杂 度也只有 O(1)可以实现快速操作。 edis 之所以能快速操作键值对一方面是因为 O(1) 复杂度的哈希表被广泛使用包括 String、Hash 和 Set它们的操作复杂度基本由哈希表决定另一方面Sorted Set 也采 用了 O(logN) 复杂度的跳表。不过集合类型的范围操作因为要遍历底层数据结构复 杂度通常是 O(N)。这里我的建议是用其他命令来替代例如可以用 SCAN 来代替 避免在 Redis 内部产生费时的全集合遍历操作。 当然我们不能忘了复杂度较高的 List 类型它的两种底层实现结构双向链表和压缩列 表的操作复杂度都是 O(N)。因此我的建议是因地制宜地使用 List 类型。例如既然 它的 POP/PUSH 效率很高那么就将它主要用于 FIFO 队列场景而不是作为一个可以随 机读写的集合
