代码之家 › 专栏 › 技术社区 › Eric Z Beard

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

sharding distributed-computing sorting

Eric Z Beard · 技术社区 · 14 年前

我要解决的问题是:

我需要能够显示跨多个数据库碎片存储的分页、排序的数据表。

分页和排序是众所周知的问题,当数据来自同一个源时,我们中的大多数人可以用任何方式解决这些问题。但是,如果您将数据拆分为多个碎片,或者使用DHT或分布式文档数据库,或者任何您喜欢的NoSQL风格,那么事情就会变得更加复杂。

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

碎片数据
1μA
1μd
1μg
2磅
2埃
2小时
3℃
3μF
3μi

按页面排序(页面大小=3):

页面数据
1μA
1磅
1℃
2μd
2埃
2μF
3μg
3小时
3μi

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

D
e
f

如果所讨论的表的大小大约是1000万行或1亿行,则不能将所有数据下拉到Web/应用程序服务器上对其进行排序并返回正确的页面。很明显,您不能让每个单独的碎片对自己的数据切片进行排序和分页,因为这些碎片彼此不了解。

使事情复杂化的是,我需要呈现的数据不会太过时,因此提前预先计算一组有用的数据,并存储结果以便以后检索是不现实的。

1 回复 | 直到 14 年前

Gintautas Miliauskas 14 年前

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

按此值的输入范围进行切分(例如,切分1包含a-c、切分2 d-f等)。或者,使用另一个具有此表的外键的表作为索引,并使用此系统共享索引表。这样您就可以轻松地定位和获取指定的范围。如果您能做到的话,这个解决方案在性能方面可能是最好的(它假定碎片的数量是静态的,并且碎片是可靠的)。
通过二进制搜索标识页面项。例如,假设您想要项目100到110。对于每个碎片,按字典法计算“m”以下的值的数目。如果数字之和大于100,则减少轴点,否则增加轴点(使用二进制搜索)。确定第100个项目(页面上的第一个项目)后,从每个碎片中取出比该项目大的前9(10-1)个项目,取出它们,对整个列表进行排序,从列表中取出前9个项目,在第一个项目前加上前缀,这就是您的页面!这种方法更难实施,需要 O(log(n)) 查询,因此它比(1)慢,但如果负载不是很重,它仍然可以相当快。
用每个值存储页码。这会给你极快的读取速度,但写得非常慢,所以它只在写得很少的情况下工作(或者只在有序变量的基础上附加)。

推荐文章

Sanskriti · 在C中,为什么10/3给出3.000,而它应该给出3.333?(保持10和3的变量被声明为“双”)

1 年前

Abhijit Sarkar · 为什么sort忽略了类中定义的总排序方法?

1 年前

Cute dog · 如何将文本与重新排序的图像相匹配?

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Lakshya Kashyap · 如何先按数字降序排序,然后按字母升序排序

2 年前

Rohan Mittal · 按dict值对dict排序

2 年前

Pikachu620 · 可以对事件列表进行排序吗?

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

tryingmybest09 · 设置出生日期排序不正确

2 年前

Hariharan Ragothaman · python中多约束条件下按值排序字典

2 年前