老实说，这更像是一个思想实验或算法挑战。
我很好奇我在Redis中创建的排行榜系统是否可以扩展到超过1个服务器节点的容量。
排行榜条目是存储在订单集（ZSET）中的key、score对。
条目被添加到从key的hashcode中选择的随机集合中，有效地对数据进行分片。
排行榜支持许多类型的查询，我能够在分片变体中有效地实现所有这些查询（可能不会在生产中使用），除了一个。
我想实现迭代，在给定skip和limit参数的情况下，返回有序的条目。首先，比如说，10个元素很容易：我从每个分片中请求最大的10个条目，并在排序时聚合集合，然后保留聚合集合中的前10个元素。然而，这变得非常低效，因为我们想要使用skip进入排行榜。
问题：
1.有没有办法在对数时间内满足这个查询？
1.在插入过程中是否可以创建元数据来帮助满足这样的查询？希望将插入时间从O（1）增加到O（log n）max？
1条答案
按热度按时间tjvv9vkg1#
首先，你需要一个新的命令，它不是直接在https://redis.io/commands/?group=sorted-set中，它是一个给定的元素的排名，如果它在集合中（它可能是）。
你可以通过检查元素是否有这个分数来做到这一点。如果有，那么返回它的排名。如果没有，那么插入它，找到它的排名，然后删除它。如果它有错误的分数，删除它，插入新的分数，找到它的排名，删除它，插入正确的分数。
所有这些都可以捆绑在LUA命令中，这将是快速和原子的。
如果你只返回最后一个元素是什么，以及它在集合中的位置，那么问题就简单多了。因为你可以发现它的排名，然后获取接下来的10个元素，合并，并返回它们。
如果你坚持只显示页面，你可以做一个二进制搜索，如下所示。从一个排序集中选择一个排名的元素。然后找到它在所有分片中的整体排名。然后决定下一步做什么。使用直接的二进制搜索，你需要在集群中发出
O(log(n))请求。如果你聪明地询问接近你认为答案的元素，您可以将其减少到平均O(log(log(n)))请求，但有时需要许多额外的请求。（提示，跟踪每个分片的排名范围，并始终从具有最大范围的分片中按排名请求元素。任何范围降至0个元素的分片都不再是您范围的一部分。）