redis的zset跳表-Toy模板网

这篇具有很好参考价值的文章主要介绍了redis的zset跳表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基础

redis用了哪些算法来实现他的数据结构？

1 跳表

读懂才会用：带你见识 Redis 的 zset

读懂才会用：Redis ZSet 的几种使用场景

1.1 在实践中，通常采用的策略是每一层的节点数是其下一层的一半（或者固定的比例），这样可以确保每一层都能有效地减少查找的节点数。为什么，这可以证明吗？

跳表中每一层节点数是其下一层的一半（或其他固定比例），是为了在保证查找效率的同时，尽可能地减少额外的空间消耗。当我们在跳表中查找一个元素时，我们首先在最高层的链表中进行查找，如果当前节点的下一个节点的值比要查找的值大，那么我们就到下一层继续查找，直到找到目标元素或者确定元素不存在。

由于每一层节点数是其下一层的一半，我们在每一层都可以跳过大量的节点，从而大大提高查找效率。具体来说，如果跳表的层数为 h，且每层节点数是其下一层的 1/2，那么在最坏情况下，我们需要查找的节点数为 O(h)。由于 h 通常取 log(n)，其中 n 是跳表中元素的数量，所以跳表的查找效率为 O(log(n))。

这个查找效率是基于假设每一层节点数是其下一层的一半得出的。如果每一层的节点数不是其下一层的一半，比如说每一层的节点数都一样，那么跳表的查找效率就会变为 O(n)，这是因为在最高层的链表中，我们无法跳过任何节点，只能一个一个地查找。

至于为什么选择每一层节点数是其下一层的一半，而不是其他比例，这是因为这个比例在保证查找效率的同时，可以尽可能地减少额外的空间消耗。如果比例过大，比如说每一层节点数是其下一层的 3/4，查找效率不一定会提高，但是额外的空间消耗会增大，；反之，如果比例过小，比如说每一层节点数是其下一层的 1/4，虽然可以减少额外的空间消耗，但查找效率也会降低。

因此，每一层节点数是其下一层的一半这个比例是一种折中的选择，它在查找效率和空间消耗之间找到了一个平衡。

1.2 跳表每一层的跳数

跳表是一个可以进行快速查找的数据结构，它是通过在普通有序链表上增加多级索引来实现的。每一层的索引节点数是其下一层的一半（或者固定的比例），因此查找时可以在上层索引快速跳过不必要的节点，然后再在下一层进行查找，以此类推，直到找到目标节点或者确定目标节点不存在。

每一层跳跃的节点数并没有固定的规定，一般会根据实际的数据量和查询效率的要求来动态调整。但在实践中，通常采用的策略是每一层的节点数是其下一层的一半（或者固定的比例），这样可以确保每一层都能有效地减少查找的节点数。

可以举一个例子，假设数组大小为10，则第0层为最底层10个节点，第一层有5个，第二层为3个，第四层为2个，第五层为1个。

那么第i层的跳数均值为O(10/(2^i)/2);

1.3 跳表插入时的操作

插入的时候，首先要进行查询，然后从最底层开始，插入被插入的元素。然后看看从下而上，是否需要逐层插入。可是到底要不要插入上一层呢？我们要想每层的跳跃都非常高效，那就越是平衡越好（第一层1级跳，第二层2级跳，第3层4级跳，第4层8级跳）。但是用算法实现起来，确实非常地复杂的，并且要严格地按照2地指数次幂，我们还要对原有地结构进行调整。所以跳表的思路是抛硬币，听天由命，产生一个随机数。Redis 中 25%概率再向上扩展。这样子，每一个元素能够有X层的概率为0.25^(X-1)次方。在 Redis 中level初始化时就定义好了，为 32 层。那么，第32层有多少个元素的概率大家可以算一下。

1.4 跳表的删除操作相对于插入和查找来说稍微复杂一些，但其基本步骤如下：

查找要删除的节点：从跳表的最高层开始，沿着每一层进行查找，直到找到要删除的节点。这个过程和跳表的查找操作类似。
删除节点：找到要删除的节点后，将该节点从每一层的链表中删除。这个过程从最低层开始，将要删除的节点的前后节点连接起来，使其跳过要删除的节点。然后逐层向上，重复此过程，直到最高层。
调整跳表的层数：如果删除的节点是跳表中最高层的唯一节点，那么需要将跳表的总层数减一。

通过以上步骤，我们可以从跳表中删除任意节点，并且保证跳表的查找效率。虽然这个过程看起来有点复杂，但实际上，由于跳表的结构，每一步操作的时间复杂度都是O(1)，所以总的时间复杂度仍然是O(log n)。

2 ZSET

2.1 redis的zset由hash+zskiplist组成，讲讲hash表的作用，key和value分别存什么，那zskiplist的一个节点存什么呢？

Redis zset 组成和存储：在 Redis 中，zset（有序集合）是由哈希表和跳表共同组成的。哈希表用于存储元素和其对应的分数，即 key 是元素，value 是分数，这样可以保证了 zset 的元素唯一性，并且可以快速查找元素及其对应的分数。跳表则用于根据分数对元素进行排序，跳表的一个节点包含元素和其对应的分数。

3 应用场景

3.1 实现固定时间段内 “1小时最热门” 榜单：

这个实现方案的关键在于利用 zset 的排序功能和 Redis 的过期删除功能。我们以当前小时的时间戳作为 zset 的 key，贴子ID作为 member，点击数评论数等作为 score。这样，在每个小时内，所有发生的点击和评论都会被记录在对应的 zset 中，并按照 score 进行排序。**在新的一小时开始时，会创建一个新的 zset，**并设置其过期时间为一小时，旧的 zset 会在过期后被自动删除。

以上方案只能实现固定时间段（如每小时、每天等）的“最热门”榜单。这是因为我们是通过创建一个新的 zset 并设置过期时间的方式，来切换到新的时间段。这样做的结果就是，在两个时间段之间，我们无法获取到连续的数据。

3.1.1 如果我们想要实现连续时间段内的“最热门”榜单（比如过去一小时内的榜单），我们就需要采取不同的策略。其中一种可能的策略是：

对于每一个帖子，我们都维护一个 zset，key 为帖子的 ID，member 为时间戳，score 为点击数或评论数。每次用户对帖子进行点击或评论，我们就将当前时间戳和对应的 score 添加到这个 zset 中。

在获取过去一小时内的“最热门”榜单时，我们首先获取当前时间戳一小时前的时间戳。然后，我们遍历每一个帖子的 zset，使用 ZRANGEBYSCORE 命令，获取 score 在这一小时内的所有 member，并计算其总分。然后，我们按照总分进行排序，得到过去一小时内的“最热门”榜单。

3.1.2 缺点

这种策略能够实现连续时间段内的“最热门”榜单，但是需要注意，如果帖子的数量非常大，那么在获取榜单时，我们可能需要遍历大量的 zset，这可能会导致性能问题。所以，在选择具体的实现方案时，我们需要根据实际的业务需求和性能需求进行权衡。

3.2 zset实现限流

滑动窗口是限流常见的一种策略。如果我们把一个用户的 ID 作为 key 来定义一个 zset ，member 或者 score 都为访问时的时间戳。我们只需统计某个 key 下在指定时间戳区间内的个数，就能得到这个用户滑动窗口内访问频次，与最大通过次数比较，来决定是否允许通过。

思路是每一个请求到来时，将时间窗口外的记录全部清理掉，只保留窗口内的记录。zset 中只有 score 值非常重要，value 值没有特别的意义，只需要保证它是唯一的就可以了

3.2.1 优缺点

使用 Redis 的 zset 实现滑动窗口限流算法是一个简洁高效的方法。这种方法基于 Redis 的有序集合，使得你能在一个滑动时间窗口内对请求进行计数，并且可以精确地对请求在时间轴上进行排序和清除。

优点：

简洁有效：使用 zset 可以非常方便的实现滑动窗口限流。你只需要在每次请求时将时间戳添加到 zset，然后移除时间窗口之前的记录，再检查剩余的记录数是否超过限流值即可。
高性能：Redis 是内存数据库，读写速度非常快，可以支持高并发环境下的限流。
精确控制：由于 zset 中的每个元素都有一个与之关联的分数（这里是时间戳），因此你可以精确地对请求在时间轴上进行排序和清除。

缺点：

存储消耗：对于访问量巨大的系统，zset 中可能需要存储大量的记录，如果滑动窗口的时间段设置较长，可能会占用大量的内存。
无法跨节点共享：如果你的系统是分布式的，这种基于 Redis 的限流方式无法在多个节点之间共享限流状态。每个服务节点的 Redis 都会维护一个独立的限流计数，这可能会导致实际的请求次数超过你的限流值。
Redis单点故障：如果Redis出现故障，可能会导致限流功能无法使用，对系统造成影响。
清理过期数据的操作可能消耗较大的CPU资源：如果清理过期数据的操作过于频繁或者需要清理的数据量过大，可能会占用较大的CPU资源。

3.3 延时队列

3.3.1 实现

zset 会按 score 进行排序，如果 score 代表想要执行时间的时间戳。在某个时间将它插入zset集合中，它变会按照时间戳大小进行排序，也就是对执行时间前后进行排序。

起一个死循环线程不断地进行取第一个key值，如果当前时间戳大于等于该key值的score就将它取出来进行消费删除，可以达到延时执行的目的。

3.3.2 没有 ack 机制，当消费失败的情况下队列如何处理？

Redis 本身并没有提供消息队列中常见的 ack 机制（确认机制），所以在使用 Redis 实现队列时需要自行解决这个问题。一种可能的解决方案是，当一个消费者从队列中取出一个消息后，先将它存入一个“处理中”队列，然后开始处理。如果处理成功，就从“处理中”队列中删除该消息；如果处理失败，就可以根据“处理中”队列重新进行处理或者进行其他的错误处理。

3.3.3 这是 topic 模式，广播模式如何搞

在 Redis 中，可以使用 Pub/Sub（发布/订阅）模式来实现广播。在这个模式中，生产者（发布者）可以向一个频道（channel）发送消息，所有订阅了该频道的消费者（订阅者）都可以接收到这个消息。这就是一种广播模式，因为消息被发送到了所有的订阅者。

3.3.4 示例代码是demo，简单应用，投入生产中还需要考虑各种细节问题

将 Redis 用于生产环境中的消息队列，确实需要考虑许多额外的问题。例如：

持久化：Redis 的数据是保存在内存中的，如果 Redis 服务器宕机，未处理的消息可能会丢失。因此，你可能需要配置 Redis 的-
持久化策略，或者使用其他的持久化消息队列系统，如 RabbitMQ 或 Kafka。
并发处理：如果有大量的消息需要处理，可能需要在多个消费者之间进行负载均衡。
错误处理：如果一个消息处理失败，需要有策略来处理这种情况，例如重试、记录错误信息等。
消息顺序：Redis 的 List 和 Pub/Sub 都不能保证在高并发下消息的顺序，如果业务上需要严格的顺序，这需要额外的设计来保证。

以上只是一些常见的问题，具体的实现可能还需要考虑更多的细节和业务需求。

4 压缩列表及其变体

4.1 listpack也是紧凑型布局，所有节点的数据都是物理上挨在一起的吧

对的，listpack也是一个紧凑型的布局，其中的条目（或称为节点）在物理上是紧密排列的。这种设计是为了确保空间效率和高速访问。

但与ziplist不同的是，listpack在设计时已经考虑了避免连锁更新的问题。正如之前提到的，listpack使用了一些策略，如标记已删除的条目、允许条目的内容在原地修改（只要它们不超过原始大小）等来减轻或消除连锁更新的影响。

所以，尽管listpack和ziplist都是紧凑型布局，但listpack的设计策略使其在面对修改时更为稳健，避免了连锁更新的性能问题。

4.2 允许条目的内容在原地修改（只要它们不超过原始大小），无论是listpack还是ziplist，只要超过了原始大小，都会引起连锁更新吧

你是对的。不论是ziplist还是listpack，如果你尝试将一个条目替换为一个更大的条目（超过原始大小），并且没有足够的空间来容纳它，那么这确实会引起连锁更新。但是，两者在如何处理这种情况上存在差异。

在ziplist中，由于其连续性和内存紧凑型设计，当某个条目的大小发生改变时（例如从一个5字节的字符串扩展到一个10字节的字符串），可能需要移动后面的所有条目来为新数据腾出空间，这可能导致连锁更新。

而listpack采取了一些策略来降低连锁更新的可能性和影响，如标记已删除的条目等。但这并不意味着listpack完全避免了连锁更新。确实，如果一个条目的新值大小超出了原始条目的空间，并且其后没有足够的空闲空间来容纳它，那么它仍然需要进行重新分配和数据移动。但由于listpack的其他策略，连锁更新的发生频率和影响范围都得到了限制。

总的来说，listpack的设计是在ziplist的经验基础上进行的，它试图通过一些策略来减轻或避免连锁更新带来的性能问题。但这并不意味着它完全解决了这个问题。

4.3 ziplist引起的连锁更新和listpack引起的连锁更新问题有什么不同，我想关注的是ziplist因为prevLen字段字节数不够时引起的连锁更新问题

好的，我明白你的意思了。我们来深入讨论这个问题。

在 Redis 的 ziplist 结构中，每一个条目都有一个 prevlen 字段，该字段表示前一个条目的长度。这个设计在大多数情况下工作得很好，因为它允许我们在 O(1) 的时间内从列表的任何位置删除条目。但是，prevlen 的长度是变动的，根据前一个条目的长度，它可能是 1 字节、2 字节、5 字节等。因此，当我们插入或删除一个特定长度的条目时，可能会导致后续条目的 prevlen 字段长度不足，从而需要连锁更新来调整整个 ziplist。

这种连锁更新的情况主要发生在以下场景：

当我们向 ziplist 中插入一个新的条目，且该条目的长度超过了某个阈值，从而导致其后面的条目的 prevlen 字段不够用。
当我们从 ziplist 中删除一个条目，且该条目的长度处于某个范围，可能导致后面的条目的 prevlen 字段长度过长，从而需要调整。

为了避免这种连锁更新，Redis 6.2 版本引入了 listpack 数据结构作为 ziplist 的替代方案。在 listpack 中，每个条目的头部只包含条目的总长度（即包括数据的长度和头部本身的长度），而不是前一个条目的长度。这意味着，无论我们如何插入或删除条目，都不会影响到后续条目的头部结构，从而避免了因 prevlen 字段引起的连锁更新问题。

总结：文章来源地址https://www.toymoban.com/news/detail-626691.html