100台機器上海量IP如何查找出現頻率 Top 100？

有 100 機器，每個機器的磁盤特别大，磁盤大小為 1T，但是記憶體大小隻有 4G，現在每台機器上都産生了很多 ip 日志檔案，每個檔案假設有50G，那麼如果計算出這 100 太機器上通路量最多的 100 ip 呢？也就是Top 100。

其實，一開始我有往布隆過濾器那邊考慮，但是布隆過濾器隻能大緻的判斷一個 ip 是否已經存在，而不能去統計數量，不符合該場景。

那麼一般這種大資料的問題，都是因為一次不能完全加載到記憶體，是以需要拆分，那怎麼拆呢？ip是32位的，也就是最多就 232 個， 常見的拆分方法都是 <code>哈希</code>：

把大檔案通過雜湊演算法配置設定到不同的機器

把大檔案通過雜湊演算法配置設定到不同的小檔案

上面所說，一台機器的記憶體肯定不能把所有的 ip 全部加載進去，必須在不同機器上先 hash 區分，先看每台機器上，50G 檔案，假設我們分成 100 個小檔案，那麼平均每個就500M，使用 Hash 函數将所有的 ip 分流到不同的檔案中。

這個時候相同的 ip 一定在相同的檔案中，當然不能排除資料全部傾斜于一個檔案的情況，也就是雖然 hash了，但是由于個别ip或者hash值相同的ip太多了，都分到了個别檔案上，那麼這個時候分流後的檔案依舊很大。這種情況我能想到的就是要是檔案還是很大，需要再hash，如果基本屬于同一個ip，那麼這個時候就可以分批次讀取，比如一次隻讀 1G 到記憶體。

在處理每個小檔案時，使用 HashMap 來統計每個 ip 出現的頻率，統計完成後，周遊，用最小根堆，擷取出現頻率最大的100個ip。這個時候，每個小檔案都擷取到了出現頻率最大的100個 ip，然後每個檔案的 Top 100 個ip 再進行排序即可（每個檔案的top100 都是不一樣的，因為前面進行 hash 之後保證相同的 ip 隻會落到同一個檔案裡）。這樣就可以得到每台機器上的 Top 100。

不同機器的 Top 100 再進行 <code>加和</code> 并 <code>排序</code>,就可以得到Top 100 的ip。

為什麼加和？ 因為不同機器上可能存在同樣的ip，前面的hash操作隻是確定同一個機器的不同檔案裡面的ip一定不一樣。

但是上面的操作有什麼瑕疵麼？當然有！

假設我們又兩台機器，有一台機器 <code>C1</code> 的top 100 的ip是 <code>192.128.1.1</code>，top 101 是 <code>192.128.1.2</code>,那麼就可能存在另一台機器 <code>C2</code> 上 <code>192.128.1.1</code> 可能從來沒有出現過，但是 <code>192.128.1.2</code> 卻也排在 top 101,其實總數上 <code>192.128.1.2</code> 是超過<code>192.128.1.1</code>，但是很不幸的是，我們每台機器隻儲存了 top100，是以它在計算過程中被淘汰了，導緻結果不準确。

解決方案：

先用 hash 算法，把 ip 按照 hash 值哈希到不同的機器上，保證相同的ip在相同的機器上，再對每個機器上的ip檔案再hash成小檔案，這個時候再分别統計小檔案的出現頻次，用最小根堆處理，不同檔案的結果排序，就可以得到每台機器的top 100，再進行不同機器之間的結果排序，就可以得到真正的 top 100。

一般而言，像這種海量資料，比如 <code>有一個包含100億個URL的大檔案,假設每個URL占用64B,請找出其中所有重複的URL.</code> ,記憶體一次性讀不下，隻能通過 分而治之。

hash 到不同的小檔案，一直這樣劃分，直到滿足資源的限制：

hash分流

hash表統計

最小堆/外部排序

如果允許一定的誤差存在，其實還可以考慮使用布隆過濾器（Bloom filter）,将URL挨個映射到每一個Bit，在此之前判斷該位置是否映射過，來證明它是否已經存在。（<code>有一定的機率出現誤判，因為其他的URL也可能會映射到同一位置</code>）

【作者簡介】：

秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。個人寫作方向：<code>Java源碼解析</code>，<code>JDBC</code>，<code>Mybatis</code>，<code>Spring</code>，<code>redis</code>，<code>分布式</code>，<code>劍指Offer</code>，<code>LeetCode</code>等，認真寫好每一篇文章，不喜歡标題黨，不喜歡花裡胡哨，大多寫系列文章，不能保證我寫的都完全正确，但是我保證所寫的均經過實踐或者查找資料。遺漏或者錯誤之處，還望指正。

劍指Offer全部題解PDF

2020年我寫了什麼？

開源程式設計筆記