雲計算用1.5KB內存為十億對象計數方法

　　為了更好地理解已經明確基數的大數據集的挑戰，我們假設你的日志文件包含16個字符的ID,並且你想統計不同ID的數量.例如:

　　4f67bfc603106cb2

　　這16個字符需要用128位來表示。6萬5千個ID將需要1MB的空間。我們每天收到30多億條事件記錄，每條記錄都有一個ID。這些ID需要3840億位或45GB的存儲。而這僅僅是ID字段需要的空間。我們采取一種簡單的方法獲取日常事件記錄中以ID為基數的數據。最簡單的辦法就是使用哈希集合且存放到內存中，其中哈希集包含唯一ID的列表(即輸入文件中可能會有多條記錄的id是相同，但在哈希集中只存放一條)。即使我們假設只有1/3的條記錄ID是唯一的(即2/3的記錄ID是重復的)，哈希集仍需要119GB的RAM，這其中不包括Java需要在內存中存儲對象的開銷。你需要一台配備幾百GB內存的機器來計算不同的元素，並且這只是計算一天內日志事件記錄的唯一ID的內存消耗。如果我們想要統計數周或數月的數據，這問題只會變得更加困難。我們身邊當然不會有一台配備幾百GB內存的空閒機器，所以我們需要一個更好的解決方案。

　　解決這一問題的常見辦法是使用位圖(博客：海量數據處理算法—Bit-Map)。位圖可以快速、准確地獲取一個給定輸入的基數。位圖的基本思想是使用哈希函數把數據集映射到一個bit位，每個輸入元素與bit位是一一對應。這樣Hash將沒有產生碰撞沖突，並減少需要計算每個元素映射到1個bit的空間。雖然Bit-map大大節省了存儲空間，但當統計很高的基數或非常大的不同的數據集，它們仍然有問題。例如，如果我們想要使用Bit-map計數十億，你將需要Bit-map位，或需要每個約120 MB的計數器。稀疏的位圖可以被壓縮，以獲得更多的空間效率，但也並不總是有幫助的。

　　幸運的是，基數估計是一個熱門的研究領域。我們已經利用這項研究提供了一個開源實現的基數估計、集合元素檢測和top-k算法。

　　基數估計算法就是使用准確性換取空間。為了說明這一點，我們用三種不同的計算方法統計所有莎士比亞作品中不同單詞的數量。請注意，我們的輸入數據集增加了額外的數據以致比問題的參考基數更高。這三種技術是：Java HashSet、Linear Probabilistic Counter以及一個Hyper LogLog Counter。結果如下：

　　該表顯示，我們統計這些單詞只用了512 bytes，而誤差在3%以內。相比之下，HashMap的計數准確度最高，但需要近10MB的空間，你可以很容易地看到為什麼基數估計是有用的。在實際應用中准確性並不是很重要的，這是事實，在大多數網絡規模和網絡計算的情況下，用概率計數器會節省巨大的空間。

　　線性概率計數器

　　線性概率計數器是高效的使用空間，並且允許實現者指定所需的精度水平。該算法在注重空間效率時是很有用的，但你需要能夠控制結果的誤差。該算法分兩步運行：第一步，首先在內存中分配一個初始化為都為0的Bit-map，然後使用哈希函數對輸入數據中的每個條目進行hash計算，哈希函數運算的結果是將每條記錄(或者是元素)映射到Bit-map的一個Bit位上，該Bit位被置為1;第二步，算法計算空的bit位數量，並使用這個數輸入到下面的公式來進行估算：

　　n=-m ln Vn

　　在公式中，m是 Bit-map的大小，Vn是空bit位和map的大小的比率。需要重點注意的是原始Bit-map的大小，可以遠小於預期的最大基數。到底小多少取決於你可以承受誤差的大小。因為Bit-map的大小m小於不同元素的總數將會產生碰撞。雖然碰撞可以節省空間，但同時也造成了估算結果出現誤差。所以通過控制原始map的大小，我們可以估算碰撞的次數，以致我們將在最終結果中看到誤差有多大。

　　Hyper LogLog

　　顧名思義，Hyper LogLog計數器就是估算Nmax為基數的數據集僅需使用loglog(Nmax)+O(1) bits就可以。如線性計數器的Hyper LogLog計數器允許設計人員指定所需的精度值，在Hyper LogLog的情況下，這是通過定義所需的相對標准差和預期要計數的最大基數。大部分計數器通過一個輸入數據流M，並應用一個哈希函數設置h(M)來工作。這將產生一個S = h(M) of {0,1}^∞字符串的可觀測結果。通過分割哈希輸入流成m個子字符串，並對每個子輸入流保持m的值可觀測 ，這就是相當一個新Hyper LogLog(一個子m就是一個新的Hyper LogLog)。利用額外的觀測值的平均值，產生一個計數器，其精度隨著m的增長而提高，這只需要對輸入集合中的每個元素執行幾步操作就可以完成。其結果是，這個計數器可以僅使用1.5 kb的空間計算精度為2%的十億個不同的數據元素。與執行 HashSet所需的120 兆字節進行比較，這種算法的效率很明顯。

　　合並分布式計數器

　　我們已經證明了使用上面描述的計數器我們可以估算大集合的基數。但是，如果你的原始輸入數據集不適合於單台機器，將怎麼做呢?這正是我們在Clearspring所面臨的問題。我們的數據分散在數百台服務器上，並且每個服務器只包含整個數據集子集的一部分。這事實上我們能合並一組分布式計數器的內容是至關重要的。這個想法有點令人費解，但如果你花費一些時間去思考這個問題，就會發現其與基本的基數估計值相比並沒有太大的不同。因為這個計數器表示映射中的位作為基數，我們可以采取兩個兼容計數器並將他們bit位合並到單一的map上。這個算法已經處理碰撞，所以我們可以得到一個基數估計所需的精密，即使我們從來沒有把所有的輸入數據到一台機器。這是非常有用的，節省了我們在網絡中移動數據的大量時間和精力。

　　Next Steps

　　希望這篇文章能幫助你更好地理解這個概念和概率計數器的應用。如果估算大集合的基數是一個問題，而你又碰巧使用一個基於JVM的語言，那麼你應該使用stream-lib項目——它提供了其他幾個流處理工具以及上文所述的算法的實現。