如何在分布式数据上实现排序和分页？

Question

这是我试图解决的问题:

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

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

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

碎片| 数据
1 | A
1 | D
1 | G
2 | B
2 | E
2 | H
3 | C
3 | F
3 | 一世

分页到页面(页面大小= 3):

页面| 数据
1 | A
1 | B
1 | C
2 | D
2 | E
2 | F
3 | G
3 | H
3 | 一世

如果我们想要显示用户页面2,我们将返回:

D
E
F.

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

更复杂的是,我需要呈现的数据不能太过时,因此提前预先计算一组有用的排序并存储结果以供以后检索是不切实际的.

Answer 1

有几个解决方案,其中一些可能对您不可行,但可能其中一个会坚持:

1. 按此值的输入范围进行分片(例如,分片1包含AC,分片2 DF等).或者,使用另一个具有此表的外键的表作为索引,并使用此系统对索引表进行分片.这样您就可以轻松找到并获取指定的范围.如果你能做到这一点,这个解决方案在性能方面可能是最好的(它假设分片的数量是静态的,而且碎片是可靠的).
2. 通过二进制搜索识别页面项.例如,假设您需要项目100到110.对于每个分片,按字典顺序计算"M"以下的值的数量.如果数字的总和大于100,则减小轴心点,否则增加它(使用二进制搜索).确定第100个项目(页面上的第一个项目)后,从每个分片中取出大于该项目的前9(10 - 1)个项目,获取它们,对整个列表进行排序,从列表中取出前9项,前置第一项,那是你的页面!这种方法更难以实现,并且需要O(log(n))查询,因此它比(1)慢,但如果负载不是很重,仍然可能相当快.
3. 存储每个值的页码.这会给你极快的读取速度,但写入速度非常慢,所以它只适用于写入次数非常少的情况(或者只根据有序变量附加).