一. 基础知识

1. 哈希函数

哈希函数 使用哈希来分流

经典的哈希函数有MD5, SHA1等, 不是必须掌握, 可以适当了解.

2. map-reduce

原理展现: 使用word-count案例

1) 预处理

预处理

2) map阶段

map

3) reduce阶段

reduce

#scala代码
sc.textFile("hdfs://cloud01:9000/user/hduser/wordcount.txt")
.flatMap(_.split(" "))
.map((_,1))
.reduceByKey(_+_)
.saveAsTextFile("hdfs://cloud01:9000/user/hduser/output01")

二. 套路

海量数据处理题通用解法

三. 牛客网给出的经典例题

1. bitmap运用

• 对10亿个IPv4的地址进行排序, 已知每个IP地址只会出现一次.

已知, IPv4 = 32 bit表示一个整数, 即4byte unsigned int.

这个第一反应要想到bitmap. 2^32大概是4Gbit, 假设每个取值对应的是一个bit, 那么用一个bitmap, 长度4Gbit刚好.

bitmap

2. count sort运用

• 给定10亿个整数, 每个整数代表一个人的年龄, 请将这10亿个数进行排序
  准备一个长度为128(range: 0~127)的数组, 然后进行"计数排序"(时间O(n), n: number of elements)即可. 可见基础的算法知识仍然是挑战大数据问题的工具.

计数排序: 用C数据, 数0~127每个取值下的count数, 然后, c[1] = c[0]+c[1], c[2]=c[1]+c[2], 这样c[val]变成值<=val的count数. 最后输出到B数组中, 采用B[c[A[j]]] = A[j]; c[ A[j] ]--;的办法输出;

3. 哈希分流运用

• 有一个包含20亿个全是32位整数的大文件, 在其中找到出现次数最多的数, 内存限制只有2GB.

估算 map分流 reduce合并结果

这里划重点: 一定要记得哈希函数的四个特点(输入无限域, 输出均匀分布有限域, 同key必同桶, 同桶可不同key, ).
这样放到16个文件中后, 对每个文件求出count值最高的那个key, 然后把16个key-value再对比对比, 找出count值最大的key.

4. TOP k问题: 哈希分流+小根堆+外排序

• 某搜索公司一天的搜索关键词是百亿级别的, 请设计出一种求出每天最热100词的可行办法

还是那三板斧, 哈希分流, bitmap, mapreduce, 但是这次要加上一个数据结构 -- 小根堆, 再加一种排序算法 -- 外排序.

TopK

此处小根堆的细节: 先把小文件中的所有keyword分词后, map成(keyword, 1)形式, 再对所有key-value进行一次wordcount(Scala: reduceByKey). 然后, 使用堆排序算法, 先建一个大小只是m = 100的小根堆(时间花费O(mlgm)), 然后, 遍历所有小文件中的数, 凡是比小根堆的根节点元素大的, 就顶替掉根节点, 并且重新调整堆, 这样遍历掉所有小文件中的元素, 花费时间O(nlogm). 当进行外排序合并的时候, 先把每个小文件的这100个元素进行排序, 然后再作归并排序. 选出前100个keyword, 就是我们要的top100.

此处合并选择使用外排序的话, 参考外排序的整理文章http://blog.sina.com.cn/s/blog_4485748101019qnk.html

这里正确性的保证(局部的top100, 经过多轮reduce能保证是全局的top100而不会错误遗漏掉真正的top100)在于: 把搜索词汇进行分流的时候, 由于哈希函数同key必同桶, 因此, 只要是同一个关键词, 一定会被哈希到同一个机器上, 在分小文件的时候, 一定也会是在一个小文件上, 甚至对某些高频词会出现一个小文件只有两三个词.

5. 一致性哈希算法

• 问题

cache问题

一旦机器数目发生变化, 增加或者减少, 那么N值发生变化, 那么所有数据的哈希值也发生变化, 需要整体重新计算, 进行大规模数据迁移, 时间成本和潜在的风险是比较大的.
解决方法: 一致性哈希算法

一致性保持哈希算法

要点: data和machine都hash到2^32bit的环形数值空间, data和machine通过顺时针查找来映射; 增加结点, 把插入位置之前的data重新映射到新结点; 删除结点, 把自己之前的data都映射到下一个顺位继承人身上.

可以参考http://blog.csdn.net/caigen1988/article/details/7708806

四. 六道海量数据处理练习题

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

10billion * 64byte = 640 billion byte = 640GB, 远大于内存限制.

方法1(通用方法): 分而治之. 使用哈希函数分流, 即hash(url) %1000, 320GB文件分到1000个小文件后, 每个平均是320MB.
这里运用两个哈希的性质:

1. 优秀的哈希函数能保证映射的均匀, 因此每个小文件的大小应该都是320MB左右.
2. 同key必同桶, 同桶不一定同key. 因此a, b俩文件中相同的url一定在同一个小文件中.

接下来, 对a, b映射的小文件pair-by-pair地进行比对, 具体可以使用java中的hashset, 来看是否有重复. 有重复的就输出写入到一个输出txt文件中.

方法2: bloomFilter, 建立bitmap, 把每个url映射到k个bit上, 先把a的放进去, 再把b的url逐一映射进行检查, 如果重复, 就写出到文本文件上.
相同的判断有一定的错误率, 这是bloomFilter不完美的地方.

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

这题是百度TopK问题的变种.

方法1(通用方法): 分而治之. 当前10个文件的query是散乱分布的, 需要先重新对10个文件再做一次hash分流, 生成新的10个文件, 这样才能保证"同key同桶". 接下来可以对每个文件使用hashmap来进行wordcount, 然后再做排序. 之后对全部10个文件进行排序.

值得一提的是, 重新hash分流以后再对每个文件进行wordcount其实就是在做mapreduce, 因此完全可以使用hadoop mapreduce, spark来进行计算.

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

方法1(通用方法): 分而治之. 把1GB文件hash成5000个小文件, 这样保证了同key同桶. 然后, 我们对每个小文件建立m=100的小根堆, 得到每个小文件的top100. 最后对5000个小文件产生的top100先各自排序, 然后总体进行一次归并排序.

4. 海量日志数据，提取出某日访问百度次数前100个IP

方法1(通用方法): 分而治之. 把海量日志数据写入到大的文本文件, 然后map到1000个小文件中, 再对每个小文件使用hashmap进行wordcount, 然后再把count值当做key进行排序(或者使用m=100的小根堆), 找出每个小文件的top100, 然后再对所有小文件的top100进行内外结合排序(可以内部使用quicksort, 每个花费O(nlgn), 然后外部使用多路归并算法, O(N)时间).

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

方法1: 使用bloomFilter, bloomFilter判断不重复是100%准确的. 因此时间, 空间效率都很可靠.
方法2: 使用2bitmap. 00表示无, 01表示出现一次, 10无意义. 2.5亿个整数, 2 • 2^32 bit = 1GB(java, C中都是int占据4个字节), 对普通PC可以接受.

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

方法1(通用): 分而治之, 先哈希到1000个小文件, 由于同key必同桶. 再对每个小文件使用hashset/hashmap找出不重复的, 输出到对应的一个小文件上. 最后合并这1000个小文件.
方法2: 也可以使用字典树(trie树), 这样查找效率会很高. 不过, 凡是trie树能做的, 用hashmap都能做, 因此并非一定要掌握字典树.