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

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

sharding distributed-computing sorting

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

我要解决的问题是:

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

分页和排序是众所周知的问题,当数据来自同一个源时,我们中的大多数人可以用任何方式解决这些问题。但是,如果您将数据拆分为多个碎片,或者使用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 回复 | 直到 15 年前

Gintautas Miliauskas 15 年前

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

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

推荐文章

José Maia · 如何在CosmosDB实例中使用mongodb的切分

9 年前

ShS · Akka集群切分:切分实体共享日志吗?

9 年前

MANA624 · MongoDB分片没有响应

9 年前

Pablo Torrecilla · MongoDB分片:mongos和配置服务器在一起?

10 年前

Nilesh · hibernate OGM在分片环境中支持mongodb吗?

10 年前

VladislavLysov · SolrCloud索引复制

10 年前

rendybjunior · 更新MongoDB范围碎片上的标记范围

11 年前

codeHead · 在MongoDB上共享其他集合呢?

11 年前

Fish · PostgreSQL 9.3.5中Instragram的UUID创建失败,错误为“operator not exists:bigint%%integer”

12 年前

Martin · Apache Solr通过SSL进行分布式搜索

12 年前