海量資料處理常用思路和方法

大資料量的問題是很多面試筆試中經常出現的問題，比如 google、淘寶、百度、 騰訊 這樣的一些涉及到海量資料的公司經常會問到。

下面的方法是我對海量資料的處理方法進行了一個一般性的總結，當然這些方法可能并不能完全覆寫所有的問題，但是這樣的一些方法也基本可以處理絕大多數遇到的問題。下面的一些問題基本直接來源于公司的面試筆試題目，方法不一定最優，如果你有更好的處理方法，歡迎與我讨論。

1.Bloom filter

适用範圍：可以用來實作資料字典，進行資料的判重，或者集合求交集

基本原理及要點：

對于原理來說很簡單，位數組+k個獨立hash函數。将hash函數對應的值的位數組置1，查找時如果發現所有hash函 數對應位都是1說明存在，很明顯這個過程并不保證查找的結果是100%正确的。同時也不支援删除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他 的關鍵字。是以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支援删除了。

還有一個比較重要的問題，如何根據輸入元素個數n，确定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率 最小。在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組裡至少一半為 0，則m應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。

舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

注意這裡m與n的機關不同，m是bit為機關，而n則是以元素個數為機關(準确的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。是以使用bloom filter記憶體上通常都是節省的。

擴充：

Bloom filter将集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）将位數組中的每一位擴充為一個counter，進而支援了元素的删除操作。Spectral Bloom Filter（SBF）将其與集合元素的出現次數關聯。SBF采用counter中的最小值來近似表示元素的出現頻率。

問題執行個體：給你A,B兩個檔案，各存放50億條URL，每條URL占用64位元組，記憶體限制是4G，讓你找出A,B檔案共同的URL。如果是三個乃至n個檔案呢？

根據這個問題我們來計算下記憶體的占用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個 bit。現在可用的是340億，相差并不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。

2.Hashing

适用範圍：快速查找，删除的基本資料結構，通常需要總資料量可以放入記憶體

hash函數選擇，針對字元串，整數，排列，具體相應的hash方法。

碰撞處理，一種是open hashing，也稱為拉鍊法；另一種就是closed hashing，也稱開位址法，opened addressing。

d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是将一個哈希表分成長度相等的兩半，分别叫做T1和T2，給T1和T2分别配備一個哈希函數，h1和h2。在存儲一個新的key時，同 時用兩個哈希函數進行計算，得出兩個位址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個 位置已經存儲的（有碰撞的）key比較多，然後将新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。

問題執行個體：

1).海量日志資料，提取出某日通路百度次數最多的那個IP。

IP的數目還是有限的，最多2^32個，是以可以考慮使用hash将ip直接存入記憶體，然後進行統計。

3.bit-map

适用範圍：可進行資料的快速查找，判重，删除，一般來說資料範圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話号碼

擴充：bloom filter可以看做是對bit-map的擴充

1)已知某個檔案内包含一些電話号碼，每個号碼為8位數字，統計不同号碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m位元組的記憶體即可。

2)2.5億個整數中找出不重複的整數的個數，記憶體空間不足以容納這2.5億個整數。

将bit-map擴充一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模拟實作這個2bit-map。

4.堆

适用範圍：海量資料前n大，并且n比較小，堆可以放入記憶體

基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較目前元素與最大堆裡的最大元素，如果它小于最大元素，則應該替換那 個最大元素。這樣最後得到的n個元素就是最小的n個。适合大資料量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很 高。

擴充：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

1)100w個數中找最大的前100個數。

用一個100個元素大小的最小堆即可。

5.雙層桶劃分 —-其實本質上就是【分而治之】的思想，重在“分”的技巧上！

适用範圍：第k大，中位數，不重複或重複的數字

基本原理及要點：因為元素範圍很大，不能利用直接尋址表，是以通過多次劃分，逐漸确定範圍，然後最後在一個可以接受的範圍内進行。可以通過多次縮小，雙層隻是一個例子。

1).2.5億個整數中找出不重複的整數的個數，記憶體空間不足以容納這2.5億個整數。

有點像鴿巢原理，整數個數為2^32,也就是，我們可以将這2^32個數，劃分為2^8個區域(比如用單個檔案代表一個區域)，然後将資料分離到不同的區域，然後不同的區域在利用bitmap就可以直接解決了。也就是說隻要有足夠的磁盤空間，就可以很友善的解決。

2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們将int劃分為2^16個區域，然後讀取資料統計落到各個區域裡的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們隻統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先将int64分成2^24個區域，然後确定區 域的第幾大數，在将該區域分成2^20個子區域，然後确定是子區域的第幾大數，然後子區域裡的數的個數隻有2^20，就可以直接利用direct addr table進行統計了。

6.資料庫索引

适用範圍：大資料量的增删改查

基本原理及要點：利用資料的設計實作方法，對海量資料的增删改查進行處理。

7.反向索引(Inverted index)

适用範圍：搜尋引擎，關鍵字查詢

基本原理及要點：為何叫反向索引？一種索引方法，被用來存儲在全文搜尋下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

以英文為例，下面是要被索引的文本：

T0 = “it is what it is”

T1 = “what is it”

T2 = “it is a banana”

我們就能得到下面的反向檔案索引：

“a”:      {2}

“banana”: {2}

“is”:     {0, 1, 2}

“it”:     {0, 1, 2}

“what”:   {0, 1}

檢索的條件”what”, “is” 和 “it” 将對應集合的交集。

正向索引開發出來用來存儲每個文檔的單詞的清單。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正 向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文 檔，很容易看到這個反向的關系。

問題執行個體：文檔檢索系統，查詢那些檔案包含了某單詞，比如常見的學術論文的關鍵字搜尋。

8.外排序

适用範圍：大資料的排序，去重

基本原理及要點：外排序的歸并方法，置換選擇 敗者樹原理，最優歸并樹

1).有一個1G大小的一個檔案，裡面每一行是一個詞，詞的大小不超過16個位元組，記憶體限制大小是1M。傳回頻數最高的100個詞。

這個資料具有很明顯的特點，詞的大小為16個位元組，但是記憶體隻有1m做hash有些不夠，是以可以用來排序。記憶體可以當輸入緩沖區使用。

9.trie樹

适用範圍：資料量大，重複多，但是資料種類小可以放入記憶體

基本原理及要點：實作方式，節點孩子的表示方式

擴充：壓縮實作。

1).有10個檔案，每個檔案1G， 每個檔案的每一行都存放的是使用者的query，每個檔案的query都可能重複。要你按照query的頻度排序 。

2).1000萬字元串，其中有些是相同的(重複),需要把重複的全部去掉，保留沒有重複的字元串。請問怎麼設計和實作？

3).尋找熱門查詢：查詢串的重複度比較高，雖然總數是1千萬，但如果除去重複後，不超過3百萬個，每個不超過255位元組。

10.分布式處理 mapreduce

适用範圍：資料量大，但是資料種類小可以放入記憶體

基本原理及要點：将資料交給不同的機器去處理，資料劃分，結果歸約。

1).The canonical example application of MapReduce is a process to count the appearances of

each different word in a set of documents:

void map(String name, String document):

// name: document name

// document: document contents

for each word w in document:

EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):

// key: a word

// values: a list of aggregated partial counts

int result = 0;

for each v in partialCounts:

result += ParseInt(v);

Emit(result);

Here, each document is split in words, and each word is counted initially with a “1″ value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Reduce, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量資料分布在100台電腦中，想個辦法高效統計出這批資料的TOP10。

3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數并對它們操作。如何找到N^2個數的中數(median)？

經典問題分析

上千萬or億資料（有重複），統計其中出現次數最多的前N個資料,分兩種情況：可一次讀入記憶體，不可一次讀入。

可用思路：trie樹+堆，資料庫索引，劃分子集分别統計，hash，分布式計算，近似統計，外排序

所謂的是否能一次讀入記憶體，實際上應該指去除重複後的資料量。如果去重後資料可以放入記憶體，我們可以為資料建立字典，比如通過 map，hashmap，trie，然後直接進行統計即可。當然在更新每條資料的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個資料，當 然這樣導緻維護次數增加，不如完全統計後在求前N大效率高。

如果資料無法放入記憶體。一方面我們可以考慮上面的字典方法能否被改進以适應這種情形，可以做的改變就是将字典存放到硬碟上，而不是記憶體，這可以參考資料庫的存儲方法。

當然還有更好的方法，就是可以采用分布式計算，基本上就是map-reduce過程，首先可以根據資料值或者把資料hash(md5)後的值，将數 據按照範圍劃分到不同的機子，最好可以讓資料劃分後可以一次讀入記憶體，這樣不同的機子負責處理各種的數值範圍，實際上就是map。得到結果後，各個機子隻 需拿出各自的出現次數最多的前N個資料，然後彙總，選出所有的資料中出現次數最多的前N個資料，這實際上就是reduce過程。

實際上可能想直接将資料均分到不同的機子上進行處理，這樣是無法得到正确的解的。因為一個資料可能被均分到不同的機子上，而另一個則可能完全聚集到 一個機子上，同時還可能存在具有相同數目的資料。比如我們要找出現次數最多的前100個，我們将1000萬的資料分布到10台機器上，找到每台出現次數最 多的前 100個，歸并之後這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10台機子，這樣在每台上隻有1千 個，假設這些機子排名在1000個之前的那些都是單獨分布在一台機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每台機子選 出出現次數最多的1000個再歸并，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。是以不能将資料随便均分到不同機子上，而是要根據hash 後的值将它們映射到不同的機子上處理，讓不同的機器處理一個數值範圍。

而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用于單機版本，也就是将總的資料根據值的範圍，劃分成多個不同的子檔案，然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行一個歸并。實際上就可以利用一個外排序的歸并過程。

另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，隻将那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入記憶體。

轉載請注明出處：http://bbs.xjtu.edu.cn

作者phylips@bmy

參考文獻：

http://blog.csdn.net/jiaomeng/archive/2007/03/08/1523940.aspx       d-Left Hashing

http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx

http://en.wikipedia.org/wiki/Bloom_filter

http://hi.baidu.com/xdzhang_china/blog/item/2847777e83fb020229388a15.html 應用Bloom Filter的幾個小技巧

http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95