记一种分布式超大规模数据的实时快速排序算法
引言
对数据进行处理的同学,经常会遇到排序需求,无论是内存数据还是磁盘数据。
对于单点的数据,我们的处理比较简单,比如:
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




