如何实现一个分布式排序

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2400 天前的主题，其中的信息可能已经有所发展或是发生改变。

假设我有 5TB 大小的json数据，需要排序.
我想实现一个分布式排序，我想到的是把数据先切割然后按 算数平均 大小分成分若干份，分配到 n 台服务器上，然后合并在一起。

但问题是在多台服务排序完成后，如何合并能保证 n 台服务器的结果合并，合并顺序保证有序的呢？

排序

合并

分布式

JSON

20 条回复 • 2018-04-23 11:48:02 +08:00

verrickt

2018-04-21 23:38:44 +08:00 via Android

归并排序？

axknightroad

2018-04-21 23:39:00 +08:00

归并排序了解一下

WildCat

2018-04-21 23:40:19 +08:00 via iPhone

merge sort

geelaw

2018-04-21 23:41:58 +08:00

看起来这个问题并不是很 trivial，你需要更清楚地描述数据是怎么存起来的。

比如 5TB 的 JSON 数据是已经切割好的，还是一个单体是 5TB ？后者的话，需要根据数据的情况设计一个 on-the-fly 切割器比较好。

然后没有理解你说的“切割后按照算术平均分成若干份”，切两次？怎么“按照算术平均数”切分？

对于这个问题，似乎没有看到什么 speculative 的地方需要用什么特别的切分方式，随便切成好几份就行了。

最后把有序列表归并一下就好了（归并排序的归并）。不过每台服务器可以根据自身的情况用混合式排序法，比如：每个服务器先尝试归并切分，大小适合 in-memory 排序之后改用快排，但限制深度，超过深度用堆排，并且当切到足够小用插入排序等。当然这是一个比较 trivial 的细节了。

wweir

2018-04-21 23:50:45 +08:00 via Android

我在考虑直接使用任务队列来实现分布式任务分配
或者找找专门的分布式排序算法
常规的算法，都是至少需要单机过一次完整的数据

lsylsy2

2018-04-21 23:56:22 +08:00

http://sortbenchmark.org/
了解一下

SlipStupig

2018-04-21 23:56:38 +08:00

@geelaw 非常感谢，5tb 数据在一个文件里面，我说的切割方法是按照文件中的 json 文档（一个文件里面有多个 json ）总个数，算数平均是：sum （ json 个数）/服务器数量，我看大家都推荐 merge sort，我还是不知道具体咋操作

MiffyLiye

2018-04-22 00:27:06 +08:00

搜索 external merge sort，然后 copy & paste。

vegito2002

2018-04-22 01:13:31 +08:00 via iPad

随机分配到服务器上，每个服务器上完成自己的排序，然后 google k-merge

sivacohan

2018-04-22 01:27:39 +08:00 via iPhone

map reduce ？

catror

2018-04-22 02:16:11 +08:00

上学的时候写过类似的，当时应该是用 OpenMPI 写的，记得 API 挺易用的，可以了解下。

msg7086

2018-04-22 03:03:19 +08:00

@SlipStupig Merge sort 是算法，你要是自己实现呢，就自己写个程序做，要是自己不会写呢，就找找看有没有现成的包咯。

swulling

2018-04-22 03:33:28 +08:00

别自己造轮子了，一个文件多个 JSON 那就好办的很。直接用 Spark 吧

billlee

2018-04-22 04:09:38 +08:00

terasort

laxenade

2018-04-22 04:29:37 +08:00 via Android

不要自己瞎造轮子+1 spark, es 什么的先试试

luban

2018-04-22 05:05:16 +08:00

我们用 map-reduce 做过，数据量大小 10T 左右，key 的量级 2000 亿，排序好后写入 hbase，供后续查询
5T 的数据，看 json 大小和 key 的数量，还是很需要计算资源的
我们当时是 100 台的 Hadoop 集群跑了 3 天左右，集群的单机配置大概是 128G 内存+10 核 20 线程 /20 核 40 线程，当然我们这个还包括了生成 key/value，排序及写入 hbase 的时间，主要耗时还是在排序这块

swulling

2018-04-22 10:31:21 +08:00

@luban 10T 排序 100 台 128g 机器 3 天有点太慢了吧。