海量資料處理方法整理記錄
隨著現在資料量的不斷增加，很多大數量的問題隨之而來，就得需要我們想辦法解決，我找了一些問題並首先思考，然後找到方法，在這裡記錄一下，未來有需要的同學可以拿走去用。
1. 在海量日誌資料裡，提取某天訪問量最多的IP。
一般處理海量的思路都是分治處理，就是現將資料進行拆分，然後進行處理，排序等。這個例子也不例外，IPV4的地址一共32位，最大值為2^32也就是總數大約4G左右，如果放到記憶體裡邊，以目前的記憶體容量也是可以處理的，但是咱們可以為自己設定一些條件，比如目前沒有那麼多記憶體。
a) 首先分治，將這個檔案按照IP的HASH分成1024份（如果想要均勻的分的演算法需要使用一致性Hash演算法），這樣每個檔案大約4M左右並且存放到磁碟上去。
b) 構建一個需要以IP為Key，出現次數為Value的TreeMap。讀取每個檔案，將IP和出現次數放入有序的TreeMap。
c) 這樣就可以得到出現次數最多的IP，前N個出現次數多的IP都可以獲取到了。
這種問題一般是TOP K的問題，思路都可以按照這樣的思路去解決。當然這種場景比較合適的就是Map Reduce莫屬了。另外，關於TOP K的這種排序的話可以採用最小堆排序（即根節點是最小的），它的時間複雜度為n*mlogm，n即為一共多少資料，m為取出前m個數據。關於這種結構不知道的同學可以進行谷歌搜尋。分治的作用就是為了減少使用系統的資源，比如系統內容。
2. 上個問題是統計重複出現的個數，那麼如何統計不重複的個數。比如：有個電話本，裡邊記錄的電話號碼都是8位數字，統計電話本里邊有多少電話號碼？這個裡邊肯定也是有一些侷限的，比如記憶體限制。再比如再2.5億整數中找到不重複的整數的個數，當然，記憶體中不能夠儲存著2.5億資料。這種解決的思路一般是點陣圖演算法（bitMap)解決。
以電話號碼為例：
a)電話號碼是8位數字，也就是出現的數字應該為11111111-99999999，總數為99999999，咱們採用點陣圖法（因為最省記憶體）。
b)一個bit位代表一個數字，那麼這些數字共需要99999999個bit，佔用記憶體為 99999999/8/1024/1024約等於11.92M，即如果這個數字所在的位有資料，那麼這個bit位就設定為1，否則設定為0。
這樣只需要12M的記憶體就可以統計這些資料了。當然2.5億整數同理，在記憶體中所有整數的個數為2^32，一個數對應一個bit，大概需要512M記憶體就可以了，如果給的記憶體還不夠的話，則需要再次進行拆分。
3. 還有一些與上邊類似的，但是不太相同的，因為有重複的數（1、2、2、3、3、4，排好序的數並且偶數個的話，中位數是[2+3]/2=2.5 奇數個的話正好是中間的），比如在5億int數中找到中位數。這個問題的解決思路其實採用雙層桶劃分思路。注意一個int佔4個Byte，整數的最大位數為32位，那麼我們將每個數轉換為二進位制，然後擷取前多少位，要看記憶體大小。解決思路：
a) 把整數轉為二進位制數，然後擷取前5位，那麼總共分出2^5=32個區間，如果分出檔案來共分出32個檔案，如果記憶體不夠的話，那麼再繼續擷取（比如16位，這裡舉例）。比如：file_00000, file_00001等。
b) 如果擷取完了，所有檔案一共32個檔案，因為都是二進位制，所以檔案是按照有序排好的。統計每個檔案的個數，然後計算中位數所在的檔案裡。
c) 如果檔案還是比較大，假設檔案在最後一個檔案，即前邊2.5億，最後一個檔案2.5億，檔名字為file_11111，那麼再繼續按照上邊的方法繼續拆分（比如再5位 檔名：file_11111_00000 等)，知道記憶體中可以裝下整個檔案。
d) 可以裝下整個檔案下的話再進行排序，排好序之後，找到中間的數就是中位數。
4. 兩個檔案，各存放50億條URL，每個URL佔64位元組。記憶體限制是4G，找出兩個檔案中相同的URL。這個問題有一個記憶體限制，那麼肯定需要分治法。
方法一（分治+hash+hashset)：
a) 50億個64Byte= 5G*64Byte = 320G，記憶體4個G，肯定是不可以的。那麼咱們將每個URL進行hash，然後放到1024個檔案中，也就是每個檔案為320G/1024=320M左右。以hash值作為檔名，第一個檔案hash出來的檔案命名為(hash[URL]%1024)a1.....a1024，第二個檔案hash出來的檔案命名為b1.....b1024。
b）1024個檔案生成了，那麼相同的URL肯定在hash命名檔案的字尾中，比如a1 vs b1，這樣依次讀取檔案的內容放入到hashset中，如果存在的話記錄並且追加放到檔案中。
c) 最後檔案中就是所有URL即為相同的URL。
方法二（Bloom Filter布隆過濾器)
a) 先說一下布隆過濾器，主要將需要內容進行hash，然後對應到相應的bit上，即Bit Map點陣圖法，但是這個裡邊有一個問題就是hash會碰撞，即不同的結果可能會hash成相同的值，這樣就會出錯。如果可以接受錯誤率，當然錯誤率較低，那麼可以採用這種方式。4G記憶體=2^32 * 8 約等於 40億Byte * 8 大約等於340億。先遍歷第一個檔案，然後再遍歷第二個，這樣會錯誤率。
5. 有40億個不重複的unsigned int的整數，沒排過序，現在給一個數，如何快速判斷這個數是否在這40億個數當中。這個如果直接放到記憶體裡邊的話得需要2^32*4Byte（int 4Byte) = 4G *4 = 16G. 顯然記憶體比較大了。
a) 這個也採用點陣圖法，所需要的記憶體為 2*32Byte / 8 = 500M 記憶體，所以僅僅需要500M記憶體就可以放下這些數字了，然後查詢就可以了。
6. 給定一個檔案，裡面最多含有n個不重複的正整數（也就是說可能含有少於n個不重複正整數），且其中每個數都小於等於n，n=10^7。輸出：得到按從小到大升序排列的包含所有輸入的整數的列表。條件：最多有大約1MB的記憶體空間可用，但磁碟空間足夠。且要求執行時間在5分鐘以下，10秒為最佳結果。
如果採用點陣圖法的話需要為10^7 / 8 /1024/1024 大約等於1.19M，大於題目的1M，顯然點陣圖法不太合適，那麼咱們考慮一下多路歸併排序。
a) 首先將這個檔案分批次讀取拆分，比如一次讀取256K，然後進行memory sort 在記憶體排序，寫到檔案中。假如檔案大小是10M的大小，則需要迴圈40次，寫入40個檔案當中。
b) 然後將檔案進行merge sort合併排序，建立一個數組40個長度，依次讀取最小的檔案，然後找到陣列中最小的寫入到檔案當中，然後繼續讀取檔案並且繼續排序，將最小的再次寫入檔案即可。
6. 有10個檔案，每個檔案1G，每個檔案的每一行都存放的是使用者的搜尋的關鍵字，每個檔案的搜尋的關鍵字都可能重複。找出熱度高的前1000個搜尋關鍵字。（提示分治+hash+trie樹+最小堆）
看到這種問題的話，首先得考慮是否機器資源足夠使用，如果足夠使用的話，就直接加入記憶體，但是如果不夠的話需要考慮分治。解決思路。
a) 將每個檔案按關鍵字進行hash，然後拆分成100個檔案，然後每個檔案大概100M左右。（分治+hash)。
b) 讀取每個小檔案，並且將讀取的關鍵字形成Trie樹字典樹，這樣會達到去重的效果。Trie樹的插入和查詢複雜度是O(k), k為最長字串的長度。然後建立長度為1000的小根堆，將遍歷每個關鍵字的出現的次數放到小根堆裡。
c) 以上一遍就可以得出第一個1G檔案的結果，然後按照相同的原理繼續以上步驟。
總結一下：
如果是大量資料不重複的，而且需要記憶體佔用比較少的需要找出出現的內容的話，適合使用BitMap點陣圖法進行處理。
還有就是一般的TOP K問題，就是找出前多少位的這種，一般記憶體容量都不是很大，採用的方式是 分治+hash+最小（大）堆排序。當然分散式的適合處理方式為MapReduce處理。
排序可以有很多種，按照不同的方式進行不同的排序，比如快排，最小堆排序，歸併排序。如果大檔案需要排序，並且嚴格要求記憶體的話，分治成小檔案，然後採用歸併排序很合適。
如果涉及到單詞的型別處理的話，需要使用Trie樹進行，因為這個非常合適處理，並且複雜度為O(k）。
如果有不對的地方，歡迎指正。