学生在处理数据时经常会遇到排序的需求，无论是内存数据还是磁盘数据。

单点数据处理比较简单，例如：

select field_a from table_b order by field_a limit 100, 10;
db.collection_b.find().sort({"field_a ":1}).skip(100).limit(10);

存储服务的处理流程通常可以抽象为：

在信息爆炸的时代，数据已经无法承载任何数据观点。 ，数据通常分布在大量节点上，假设给定数据库中的数据均匀分布在所有后续节点上。

目前常见的排序限制方法是选择中间节点或中间件进行合并：

一般处理流程的动态表示如下：

我们将流程和简单流程抽象为如下：

注意，第三步中数据节点中的查询结果范围为[0,skip+limit]。当我们要查询[skip=1000000, limit=200]数据时，首先需要查询每个节点的[skip=0, limit=1000000+200]数据，然后聚合服务执行[skip=1000000, limit=200] ]、存储IO：n与网络IO的处理水平bypass成正比。

对于T级及以上的数据处理，无法实现实时处理。

让我们考虑另一种方式

理论基础

在一般的数据处理方法中，我们基于一个共同的假设：每个数据存储节点只有简单的外部查询功能，并且它们之间没有交互。连接功能很弱，主要是主从、选择等高级功能。

现在我们想改变这个假设。

理论描述

假设每个存储节点都具有相互通信的能力。例如，“嘿，skip 为 100 的数据是什么？”，“好吧，skip 为 100 的数字，这里是 m。”

对话分为几种不同的类型。第一个是扩散请求。当一个节点收到请求后，该节点迅速将该请求传播到所有其他连接的节点。

第二种对话是回应式，简单的问答式。

假设有整个网络的排序请求。一旦节点收到请求，该请求就会传播到必须处理该请求的网络。每个节点在n次对话后产生最终结果。

概念定义

如果数据栈中数据m前面有n-1个数字，则m的排序索引为n。我们需要做的就是在每个节点上添加该节点之前的数字。

领导力

这很简单。如果我们要查询skip=100、limit=20个数据批次中的数据，我们的目标是从全网的数据中得到b,e.

b。索引是100。索引

e是120。

那么[b,e]之前的所有数字都是我们的目标数据。

其实必须要考虑到数据的重复，即b的索引为98，b的个数为4，e的索引为118，e的个数为5，那么目标data 以 [ b, b] 开头，以 [e, e, 到 e] 结尾。

该技术使用

如果一个节点想知道数据m前面有多少个数字，它会直接向其他数据节点发送对话。所有节点（包括自己）只需要返回该节点m前面的数据量即可。假设每个节点的查询结果条数为n1,n2,n3,...n10，

总数据中数据m之前的数据条数为n=(n1+n2+n3+....+n10 ）。

使用数据m作为梯度对象，n作为结果来接近skip、skip+constraint并从完整数据集中得到最终的b、e。

架构设计

请求处理流程

如图所示，我们将请求分为三个部分

节点确认阶段

该阶段确认哪些节点参与搜索。

结果同步阶段

同步过程是相互的，互相猜测，查询对应数据的索引。

该阶段是处理的核心阶段。通过相互增强，最终的近似指数在[100,120]范围内。

合并结果

各数据节点同步数据结果。如果skip = 100万，limit = 20，则最多同步20条数据。
不再与通过成正比。

模型假设

假设有m个节点，每个节点的数据都是排序的，每个节点之间的平均循环时间为t1，
一次查询的执行时间为t2确认

的数量每次确认的数据为p，假设结果确认阶段节点平均外部请求次数不等于s，

节点确认时间为t1

结果确认阶段时间