External Sorting 外排序算法

Source: Jiuzhang's Tutorial: https://www.jiuzhang.com/tutorial/big-data-interview-questions/271

所谓的外排序算法(External Sorting),是指在内存不够的情况下,如何对存储在一个或者多个大文件中的数据进行排序的算法。

参考资料:

外排序算法通常是解决一些大数据处理问题的第一个步骤,或者是面试官所会考察的算法基本功。

外排序算法的基本步骤

外排序算法分为两个基本步骤:

  1. 将大文件切分为若干个个小文件,并分别使用内存排好序
  2. 使用K路归并算法将若干个排好序的小文件合并到一个大文件中

第一步:文件拆分

根据内存的大小,尽可能多的分批次的将数据 Load 到内存中,并使用系统自带的内存排序函数(或者自己写个快速排序算法),将其排好序,并输出到一个个小文件中。比如一个文件有1T,内存有1G,那么我们就这个大文件中的内容按照 1G 的大小,分批次的导入内存,排序之后输出得到 1024 个 1G 的小文件。

第二步:K路归并算法

K路归并算法使用的是数据结构堆(Heap)来完成的,使用 Java 或者 C++ 的同学可以直接用语言自带的 PriorityQueue(C++中叫priority_queue)来代替。

我们将 K 个文件中的第一个元素加入到堆里,假设数据是从小到大排序的话,那么这个堆是一个最小堆(Min Heap)。每次从堆中选出最小的元素,输出到目标结果文件中,然后如果这个元素来自第 x 个文件,则从第 x 个文件中继续读入一个新的数进来放到堆里,并重复上述操作,直到所有元素都被输出到目标结果文件中。

Follow up: 一个个从文件中读入数据,一个个输出到目标文件中操作很慢,如何优化?

如果我们每个文件只读入1个元素并放入堆里的话,总共只用到了 1024 个元素,这很小,没有充分的利用好内存。另外,单个读入和单个输出的方式也不是磁盘的高效使用方式。因此我们可以为输入和输出都分别加入一个缓冲(Buffer)。假如一个元素有10个字节大小的话,1024 个元素一共 10K,1G的内存可以支持约 100K 组这样的数据,那么我们就为每个文件设置一个 100K 大小的 Buffer,每次需要从某个文件中读数据,都将这个 Buffer 装满。当然 Buffer 中的数据都用完的时候,再批量的从文件中读入。输出同理,设置一个 Buffer 来避免单个输出带来的效率缓慢。

面试题

求两个超大文件中 URLs 的交集

问题描述

给定A、B两个文件,各存放50亿个URLs,每个 URL 各占 64 字节,内存限制是 4G,让你找出A、B文件共同的 URLs?

问题分析

首先需要跟面试官澄清一个问题:

这两个文件各自是否已经没有重复?

通常面试官会先让你假设没有重复,然后再来看有重复的情况怎么处理。那我们就先来看没有重复的情况。

A,B各自没有重复 URLs

方法1:文件拆分 Sharding(也可以叫 Partitioning)
50亿,每个 URLs 64 字节,也就是每个文件 320G 的大小。很显然我们不能直接全部 Load 到内存中去处理。这种内存不够的问题,通常我们的解决方法都可以是使用 hash function 来将大文件拆分为若干个小文件。比如按照hashfunc(url) % 200进行拆分的话,可以拆分成为,200 个小文件 —— 也就是如果 hashfunc(url) % 200 = 1 就把这个 url 放到 1 号文件里。每个小文件理想状况下,大小约是 1.6 G,完全可以 Load 到内存里。

这种方法的好处在于,因为我们的目标是要去重,那么那些A和B中重复的 URLs,会被hashfunc(url) % 200映射到同一个文件中。这样在这个小文件中,来自 A 和 B 的 URls 在理想状况下一共 3.2G,可以全部导入内存进入重复判断筛选出有重复的 URLs。

Q: 刚才一直在说理想情况下,那么不理想情况下是什么样的?该怎么处理?

A: 不理想的情况下,如果 hashfunc(url) % 200 的结果比较集中,那么有可能会造成不同的 URLs 在同一个文件中扎堆的情况。这种情况下,有一些文件的大小可能会超过 4G。对于这种情况,处理的办法是进行二次拆分,把这些仍然比较大的小文件,用一个新的 hashfunc 进行拆分:hashfunc'(url) % X。这里再拆成多少个文件,可以根据文件的实际大小来定。如果二次拆分之后还是存在很大的文件,就进行三次拆分。直到每个小文件都小于 4G。

方法2:BloomFilter
我们可以使用一个 4G 的 Bloom Filter,它大概包含 320 亿 个 bit。把 A 文件的 50亿 个 URLs 丢入 BF 中,然后查询 B 文件的 每个 URL 是否在 BF 里。这种方法的缺点在于,320 亿个 bit 的 BF 里存 50 亿个 URLs 实在是太满了(要考虑到BF可能会用4个哈希函数),错误率会很高。因此仍然还需需要方法1中的文件拆分来分批处理。

方法3:外排序算法

将A,B文件分别拆分为80个小文件,每个小文件4G。每个文件在拆分的时候,每4G的数据在内存中做快速排序并将有序的URLs输出到小文件中。

用多路归并算法,将这160个小文件进行归并,在归并的过程中,即可知道哪些是重复的 URLs。只需将重复的 URLs 记录下来即可。

Follow up: A,B各自有重复的 URLs

当 A, B 各自有重复的 URLs 的时候,比如最坏情况下,A里的50亿个URLs 全部一样。B里也是。这样采用方法1这种比较容易想到的 Sharding 方法,是不奏效的,因为所有 URLs 的 hashcode 都一样,就算换不同的 hashfunc 也一样。这种情况下,需要先对两个文件进行单独的去重,方法是每 4G 的数据,放到内存中用简单的哈希表进行去重。这样,在最坏情况下,总共 320G 的数据里,一个 URLs 最多重复 8次,则不会出现太严重的扎堆情况了。算法上唯一需要稍微改动的地方是,由于 A 存在多个重复的 URLs,所以当和 B 的 URLs 被sharding 到同一个文件里的时候,需要标记一下这个 URLs 来自哪个文件,这样才能知道是否在A和B中同时出现过。

另外,使用外排序的方法,是无需对两个文件进行单独去重的步骤的。

results matching ""

    No results matching ""