V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
SlipStupig
V2EX  ›  程序员

如何实现一个分布式排序

  •  
  •   SlipStupig · 2018-04-21 23:35:18 +08:00 · 4984 次点击
    这是一个创建于 2167 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    20 条回复    2018-04-23 11:48:02 +08:00
    verrickt
        1
    verrickt  
       2018-04-21 23:38:44 +08:00 via Android
    归并排序?
    axknightroad
        2
    axknightroad  
       2018-04-21 23:39:00 +08:00
    归并排序了解一下
    WildCat
        3
    WildCat  
       2018-04-21 23:40:19 +08:00 via iPhone
    merge sort
    geelaw
        4
    geelaw  
       2018-04-21 23:41:58 +08:00   ❤️ 1
    看起来这个问题并不是很 trivial,你需要更清楚地描述数据是怎么存起来的。

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

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

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

    最后把有序列表归并一下就好了(归并排序的归并)。不过每台服务器可以根据自身的情况用混合式排序法,比如:每个服务器先尝试归并切分,大小适合 in-memory 排序之后改用快排,但限制深度,超过深度用堆排,并且当切到足够小用插入排序等。当然这是一个比较 trivial 的细节了。
    wweir
        5
    wweir  
       2018-04-21 23:50:45 +08:00 via Android
    我在考虑直接使用任务队列来实现分布式任务分配
    或者找找专门的分布式排序算法
    常规的算法,都是至少需要单机过一次完整的数据
    lsylsy2
        6
    lsylsy2  
       2018-04-21 23:56:22 +08:00
    SlipStupig
        7
    SlipStupig  
    OP
       2018-04-21 23:56:38 +08:00
    @geelaw 非常感谢,5tb 数据在一个文件里面,我说的切割方法是按照文件中的 json 文档(一个文件里面有多个 json )总个数,算数平均是:sum ( json 个数)/服务器数量,我看大家都推荐 merge sort,我还是不知道具体咋操作
    MiffyLiye
        8
    MiffyLiye  
       2018-04-22 00:27:06 +08:00
    搜索 external merge sort,然后 copy & paste。
    vegito2002
        9
    vegito2002  
       2018-04-22 01:13:31 +08:00 via iPad
    随机分配到服务器上, 每个服务器上完成自己的排序, 然后 google k-merge
    sivacohan
        10
    sivacohan  
       2018-04-22 01:27:39 +08:00 via iPhone
    map reduce ?
    catror
        11
    catror  
       2018-04-22 02:16:11 +08:00
    上学的时候写过类似的,当时应该是用 OpenMPI 写的,记得 API 挺易用的,可以了解下。
    msg7086
        12
    msg7086  
       2018-04-22 03:03:19 +08:00
    @SlipStupig Merge sort 是算法,你要是自己实现呢,就自己写个程序做,要是自己不会写呢,就找找看有没有现成的包咯。
    swulling
        13
    swulling  
       2018-04-22 03:33:28 +08:00
    别自己造轮子了,一个文件多个 JSON 那就好办的很。直接用 Spark 吧
    billlee
        14
    billlee  
       2018-04-22 04:09:38 +08:00
    terasort
    laxenade
        15
    laxenade  
       2018-04-22 04:29:37 +08:00 via Android
    不要自己瞎造轮子+1 spark, es 什么的先试试
    luban
        16
    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
        17
    swulling  
       2018-04-22 10:31:21 +08:00
    @luban 10T 排序 100 台 128g 机器 3 天有点太慢了吧。
    owenliang
        18
    owenliang  
       2018-04-22 11:30:34 +08:00 via Android
    hive 写 sql 了解一下
    param
        19
    param  
       2018-04-23 02:06:44 +08:00 via Android
    首先想到归并排序。。。
    jameslan
        20
    jameslan  
       2018-04-23 11:48:02 +08:00 via Android
    5t 数据还需要排序的场景很少见啊,楼主三思
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5439 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 08:44 · PVG 16:44 · LAX 01:44 · JFK 04:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.