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