海量数据处理 - noonecare/spark GitHub Wiki

不论是 spark 还是 mapreduce， 都是为了解决处理海量数据。 它们所用到的算法，不论是不是使用集群，都可以提高处理大数据的效率。之前我太注重识记 spark/mapreduce 的 API, 却没有理解其中的算法。所以本文实际解决一些处理大数据的问题，不用 spark/mapreduce 的 API, 重在去揭示算法。

• 海量日志数据，提取出某日访问百度次数最多的那个IP。（比方说日志是个 10T 大小的文件（为了简单），有 10 亿条记录。）

• 做 hash 取模， 分成每份大约 4G 数据的大小（大约是 10T/4G = 2500， 应该是 几千份的数据）。
• 对于分拆后的每一份数据，找出出现次数最多的 IP, 并且给出这个词以及这个词出现的次数。
• 对于这几千份的数据，比较每个词出现的次数，给出出现次数最多的词。

• 寻找热门查询，300万个查询字符串中统计最热门的10个查询。

• 和上一题的解法几乎一致，不过对于每一份数据，不是给出出现次数最多的词和这个词出现的次数。而是给出出现次数前十多的词（以及这些词的出现次数）。
• 汇总结果时，由于每一份给出的是有序的数据，所以可以用 merge sort 算法在 nlogn 的时间复杂度内给出出现次数最多的十个词。

• 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

• 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

• 跟上上题一模一样。
• 有了 100 台机器，就可以同时处理 100 份分拆后的数据。

• 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

• hash 做 shuffle， 把数据分成多份儿
• 在每份儿中统计 query 出现的次数，并且排序
• merge sort 给出总的排序

• 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

• 和之前的问题重复了

• 怎么在海量数据中找出重复次数最多的一个？

• 和之前的问题重复了

• 上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。

• 和之前的问题重复了

• 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

• 和之前重复了

这里分析一下时间复杂度：

• 理想情况下： hash 实现均分，均分成 K 份， S_1, S_2 ... S_k

• 对于 S_i 给出出现最频繁的十个词，最少耗时为 |S_i| 做多耗时为 |S_i| * (|S_i| - 1) / 2, 期望耗时 |S_i| * (|S_i| - 1) / 4.

• 归并算法的耗时 K log(K)

• 总耗时 \sum |S_i| *(|S_i| - 1) + K log(K)

• 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

• hash 分成多份
• 在每一份中，删除又重复的数据
• 把数据合并起来

• 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

• 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

海量处理时用到的数据结构和算法：

• heapsort
• hashtable
• bitmap
• Bloom filter

Basic 问题：

• 有海量的记录，记录中可能有重复，统计独特的记录数，以及每个记录出现的次数(Hash Table)
• 有海量的记录，去重给出不重复的记录数（bitmap）
• 有海量的数据，找出其中最大的 K 的数(heapsort)

困难问题：

• 如何解决数据不平衡