sorting - 您如何实现对分布式数据的排序和分页？

Question

这是我要解决的问题：

我需要能够显示存储在多个数据库分片中的分页，排序的数据表。

分页和排序是众所周知的问题，当数据来自单一来源时，我们大多数人可以通过多种方式解决。但是，如果您要在各个分片之间拆分数据，或者使用DHT或分布式文档数据库或您喜欢的任何NoSQL风格，事情都会变得更加复杂。

这是一个非常小的数据集的简单图片：

碎片|数据
1 |一个
1 | d
1 | G
2 |乙
2 | Ë
2 | H
3 | C
3 | F
3 |一世

分为页面（页面大小= 3）：

页面数据
1 |一个
1 |乙
1 | C
2 | d
2 | Ë
2 | F
3 | G
3 | H
3 |一世

如果我们想显示用户页面2，我们将返回：

d
Ë
F

如果所讨论的表的大小大约为1000万行或1亿行，则不能仅将所有数据下拉到Web /应用程序服务器上以对其进行排序并返回正确的页面。而且您显然不能让每个单独的分片排序并分页其自己的数据片段，因为分片彼此之间并不了解。

使事情复杂化的是，我需要提供的数据不会太过时，因此提前预先计算一组有用的排序并将结果存储以供以后检索是不切实际的。

Answer 1

有几种解决方案，其中一些可能对您不可行，但也许其中一种会坚持下去：


通过此值的输入范围进行分片（例如，分片1包含A-C，分片2 D-F等）。或者，使用具有该表外键的另一个表作为索引，并使用此系统将索引表分片。这样，您可以轻松找到并获取指定范围。如果可以的话，此解决方案可能是性能最好的解决方案（它假定分片的数量是静态的，并且分片是可靠的）。
通过二进制搜索识别页面项。例如，假设您希望项目100到110。对于每个分片，按字典顺序计算“ M”以下的值数。如果数字总和大于100，则减小枢轴点，否则增大枢轴点（使用二进制搜索）。确定第100个项目（页面上的第一个项目）后，从每个分片中取出比该项目大的前9个（10-1）个项目，进行提取，对整个列表进行排序，从列表中获得前9个，第一项，有您的页面！这种方法更难以实施，并且需要O(log(n))查询，因此它比（1）慢，但是如果负载不是很重的话，仍然可能相当快。
将页码与每个值一起存储。这将使您的读取速度非常快，但是写入速度却非常慢，因此它仅在写入很少（或者仅在有序变量方面追加）的情况下才起作用。