一. 基礎(chǔ)知識
1. 哈希函數(shù)
經(jīng)典的哈希函數(shù)有MD5, SHA1等, 不是必須掌握, 可以適當了解.
2. map-reduce
原理展現(xiàn): 使用word-count案例
1) 預(yù)處理
2) map階段
3) reduce階段
#scala代碼
sc.textFile("hdfs://cloud01:9000/user/hduser/wordcount.txt")
.flatMap(_.split(" "))
.map((_,1))
.reduceByKey(_+_)
.saveAsTextFile("hdfs://cloud01:9000/user/hduser/output01")
二. 套路
三. ?？途W(wǎng)給出的經(jīng)典例題
1. bitmap運用
- 對10億個IPv4的地址進行排序, 已知每個IP地址只會出現(xiàn)一次.
已知, IPv4 = 32 bit表示一個整數(shù), 即4byte unsigned int.
這個第一反應(yīng)要想到bitmap. 2^32大概是4Gbit, 假設(shè)每個取值對應(yīng)的是一個bit, 那么用一個bitmap, 長度4Gbit剛好.
2. count sort運用
- 給定10億個整數(shù), 每個整數(shù)代表一個人的年齡, 請將這10億個數(shù)進行排序
準備一個長度為128(range: 0~127)的數(shù)組, 然后進行"計數(shù)排序"(時間O(n), n: number of elements)即可. 可見基礎(chǔ)的算法知識仍然是挑戰(zhàn)大數(shù)據(jù)問題的工具.
計數(shù)排序: 用C數(shù)據(jù), 數(shù)0~127每個取值下的count數(shù), 然后, c[1] = c[0]+c[1], c[2]=c[1]+c[2], 這樣c[val]變成值<=val的count數(shù). 最后輸出到B數(shù)組中, 采用
B[c[A[j]]] = A[j]; c[ A[j] ]--;的辦法輸出;
3. 哈希分流運用
- 有一個包含20億個全是32位整數(shù)的大文件, 在其中找到出現(xiàn)次數(shù)最多的數(shù), 內(nèi)存限制只有2GB.
這里劃重點: 一定要記得哈希函數(shù)的四個特點(輸入無限域, 輸出均勻分布有限域, 同key必同桶, 同桶可不同key, ).
這樣放到16個文件中后, 對每個文件求出count值最高的那個key, 然后把16個key-value再對比對比, 找出count值最大的key.
4. TOP k問題: 哈希分流+小根堆+外排序
- 某搜索公司一天的搜索關(guān)鍵詞是百億級別的, 請設(shè)計出一種求出每天最熱100詞的可行辦法
還是那三板斧, 哈希分流, bitmap, mapreduce, 但是這次要加上一個數(shù)據(jù)結(jié)構(gòu) -- 小根堆, 再加一種排序算法 -- 外排序.
此處小根堆的細節(jié): 先把小文件中的所有keyword分詞后, map成(keyword, 1)形式, 再對所有key-value進行一次wordcount(Scala: reduceByKey). 然后, 使用堆排序算法, 先建一個大小只是m = 100的小根堆(時間花費O(mlgm)), 然后, 遍歷所有小文件中的數(shù), 凡是比小根堆的根節(jié)點元素大的, 就頂替掉根節(jié)點, 并且重新調(diào)整堆, 這樣遍歷掉所有小文件中的元素, 花費時間O(nlogm). 當進行外排序合并的時候, 先把每個小文件的這100個元素進行排序, 然后再作歸并排序. 選出前100個keyword, 就是我們要的top100.
此處合并選擇使用外排序的話, 參考外排序的整理文章http://blog.sina.com.cn/s/blog_4485748101019qnk.html
這里正確性的保證(局部的top100, 經(jīng)過多輪reduce能保證是全局的top100而不會錯誤遺漏掉真正的top100)在于: 把搜索詞匯進行分流的時候, 由于哈希函數(shù)同key必同桶, 因此, 只要是同一個關(guān)鍵詞, 一定會被哈希到同一個機器上, 在分小文件的時候, 一定也會是在一個小文件上, 甚至對某些高頻詞會出現(xiàn)一個小文件只有兩三個詞.
5. 一致性哈希算法
- 問題
一旦機器數(shù)目發(fā)生變化, 增加或者減少, 那么N值發(fā)生變化, 那么所有數(shù)據(jù)的哈希值也發(fā)生變化, 需要整體重新計算, 進行大規(guī)模數(shù)據(jù)遷移, 時間成本和潛在的風(fēng)險是比較大的.
解決方法: 一致性哈希算法
要點: data和machine都hash到2^32bit的環(huán)形數(shù)值空間, data和machine通過順時針查找來映射; 增加結(jié)點, 把插入位置之前的data重新映射到新結(jié)點; 刪除結(jié)點, 把自己之前的data都映射到下一個順位繼承人身上.
可以參考http://blog.csdn.net/caigen1988/article/details/7708806
四. 六道海量數(shù)據(jù)處理練習(xí)題
1. 給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url？
10billion * 64byte = 640 billion byte = 640GB, 遠大于內(nèi)存限制.
方法1(通用方法): 分而治之. 使用哈希函數(shù)分流, 即hash(url) %1000, 320GB文件分到1000個小文件后, 每個平均是320MB.
這里運用兩個哈希的性質(zhì):
- 優(yōu)秀的哈希函數(shù)能保證映射的均勻, 因此每個小文件的大小應(yīng)該都是320MB左右.
- 同key必同桶, 同桶不一定同key. 因此a, b倆文件中相同的url一定在同一個小文件中.
接下來, 對a, b映射的小文件pair-by-pair地進行比對, 具體可以使用java中的hashset, 來看是否有重復(fù). 有重復(fù)的就輸出寫入到一個輸出txt文件中.
方法2: bloomFilter, 建立bitmap, 把每個url映射到k個bit上, 先把a的放進去, 再把b的url逐一映射進行檢查, 如果重復(fù), 就寫出到文本文件上.
相同的判斷有一定的錯誤率, 這是bloomFilter不完美的地方.
2. 有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求你按照query的頻度排序。
這題是百度TopK問題的變種.
方法1(通用方法): 分而治之. 當前10個文件的query是散亂分布的, 需要先重新對10個文件再做一次hash分流, 生成新的10個文件, 這樣才能保證"同key同桶". 接下來可以對每個文件使用hashmap來進行wordcount, 然后再做排序. 之后對全部10個文件進行排序.
值得一提的是, 重新hash分流以后再對每個文件進行wordcount其實就是在做mapreduce, 因此完全可以使用hadoop mapreduce, spark來進行計算.
3. 有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。
方法1(通用方法): 分而治之. 把1GB文件hash成5000個小文件, 這樣保證了同key同桶. 然后, 我們對每個小文件建立m=100的小根堆, 得到每個小文件的top100. 最后對5000個小文件產(chǎn)生的top100先各自排序, 然后總體進行一次歸并排序.
4. 海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)前100個IP
方法1(通用方法): 分而治之. 把海量日志數(shù)據(jù)寫入到大的文本文件, 然后map到1000個小文件中, 再對每個小文件使用hashmap進行wordcount, 然后再把count值當做key進行排序(或者使用m=100的小根堆), 找出每個小文件的top100, 然后再對所有小文件的top100進行內(nèi)外結(jié)合排序(可以內(nèi)部使用quicksort, 每個花費O(nlgn), 然后外部使用多路歸并算法, O(N)時間).
5. 在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，內(nèi)存不足以容納這2.5億個整數(shù)。
方法1: 使用bloomFilter, bloomFilter判斷不重復(fù)是100%準確的. 因此時間, 空間效率都很可靠.
方法2: 使用2bitmap. 00表示無, 01表示出現(xiàn)一次, 10無意義. 2.5億個整數(shù), 2 ? 2^32 bit = 1GB(java, C中都是int占據(jù)4個字節(jié)), 對普通PC可以接受.
6. 1000萬字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串。請怎么設(shè)計和實現(xiàn)？
方法1(通用): 分而治之, 先哈希到1000個小文件, 由于同key必同桶. 再對每個小文件使用hashset/hashmap找出不重復(fù)的, 輸出到對應(yīng)的一個小文件上. 最后合并這1000個小文件.
方法2: 也可以使用字典樹(trie樹), 這樣查找效率會很高. 不過, 凡是trie樹能做的, 用hashmap都能做, 因此并非一定要掌握字典樹.
