记一种分布式超大规模数据的实时快速排序算法

引言

对数据进行处理的同学，经常会遇到排序需求，无论是内存数据还是磁盘数据。

对于单点的数据，我们的处理比较简单，比如：

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);

存储服务的处理流程一般可抽象如下：

信息爆炸的时代，数据早已不是单点所能承载的了，数据一般分布在大量节点上，假设某库中的数据均匀地分布在以下的所有节点上。

这时sort, limit的一般方法是选择一个中间节点或者中间件来做合并处理：

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

我们将过程抽象，流程简化如下：

注意第三步在数据节点中的查询结果范围为[0，skip+limit]。当我们想查询[skip=1000000, limit=200]的数据，意味着需要在各节点

上先查询[skip=0, limit=1000000+200]的数据，再由归并服务对结果进行[skip=1000000, limit=200]的排序， 对存储IO与网络IO的处理量级与skip成正比，

对于T级以上规模所数据处理，无法做到实时处理。

下面来讨论另一种方式

理论基础

在一般对数据的处理方法中，我们基于一个共同的假设：各数据存储节点只具备简单的对外查询功能，相互之间的连接功能是很弱的，主要有主从，选举，更一步的功能就少了。

现在我们要改变这一假设。

理论描述

假设各存储节点具备相互对话的能力。比如，"hey,你那里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，则目标数据以[b, b]开头， 以[e,e,e]结尾。

技术使用

某节点想知道数据m前面有多少个数， 则直接向其他数据节点发送对话，所有节点（包含自身）只需要返回本节点中在m前面的数据个数, 假设各节点上的查询结果个数为n1,n2,n3,...n10,

则全量数据中数据m前面的数据个数n=(n1+n2+n3+.....+n10)。

以数据m做为递度对象， n做为结果向skip, skip+limit逼近，在全量数据中获取最终的b,e。

架构设计请求处理流程

如图所示，对于一次请求我们会分成三个部分

节点确认阶段

此阶段确认哪些节点参与发现。

结果同步阶段

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

这一步是处理的核心步骤，通过相互确认，最终逼近索引在[100,120]之间的数是哪些。

结果合并

各数据节点将数据结果同步出去，如果skip=100万， limit=20,最多也就同步20条数据，

不再于skip正成比。

模型假设

假设存在m个节点，各节点上的数据都是各自排好序的，各节点间平均来回时间为t1，

单次查询确认程序执行时间为t2,

每次确认的数据个数为p，假设结果确认阶段平均某节点的对外请求次数不在于s。

节点确认时间为 t1

结果确认阶段时间=100， 因此结果为空，直接跳到数据合并阶段）

存在2个数n3, n4满足 i(n3max/100=s3) + c(s3)=120.(如果不存在n4, 则表明不存在这个数，其全局索引>=120, 假设存在n2, 则数据大于等于n2*max/100的数都是目标数据。）

则有 s1

（编辑：海南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!