AddThis（前身為Clearspring）的數據分析副總監Matt Abrams在High Scalability上發表了一篇文章，介紹了他們公司如何應對大數據。在這篇文章中，AddThis僅僅用了1.5KB內存的內存就計算了十億個不同的對象，Matt Abrams主要向我們詳解了他們公司在處理過程中使用的方法。
以下為文章全文：
在AddThis，我們喜歡統計數據。對一組中不同元素（也稱為“基數”）的數量進行計數，當其數量很大時，這是一個挑戰。
為了更好地理解確定的大型成套基數的挑戰，讓我們想象一下，在你的日志中有一個16個字符的ID，并且你想計算不同ID的數量。這里有一個例子：
4f67bfc603106cb2
16個字符需要用128位來表示。6萬5千個ID將需要1MB的空間。我們每天收到30多億個事件，每個事件都有一個ID。這些ID需要3840億位或45GB的存儲。而這僅僅是ID字段需要的空間！為了得到我們日常活動中的ID基數，我們可以采取一個簡單的方法。最簡單的想法是使用內存中的哈希集合，其中包含在輸入文件中看到的獨特的ID列表。即使我們假設3條記錄中有1個是唯一的，哈希集合仍需要119GB的RAM，不包括Java需要在內存中存儲對象的開銷。你需要一臺配備幾百GB內存的機器來計算不同的元素，并且這只是計算一天的獨特ID的成本。如果我們想要數周或數月的數據，這個問題只會變得更加困難。我們身邊當然不會有一臺配備幾百GB內存的空閑機器，所以我們需要一個更好的解決方案。
解決這一問題的常見辦法是使用位圖。位圖可以用來快速、準確地獲取一個給定的輸入的基數。位圖的基本思路是使用哈希函數映射數據集到一個位字段，在位字段里輸入的獨特元素映射到該字段中的一個位。這產生零碰撞，并減少需要計算每個獨特元素到1位的空間。雖然位圖大大減少了對空間的要求，但當基數是非常高或你對非常多的不同的組進行計數時，它們仍然有問題。例如，如果我們想要使用位圖計數十億，你將需要十億位，或需要每個約120 MB的計數器。稀疏的位圖可以被壓縮，以獲得更多的空間效率，但也并不總是有幫助的。
幸運的是，基數估計是一個熱門的研究領域。我們已經利用這項研究提供了一個開源實現的基數估計、集員資格檢測和top-k算法。
為了了解算法占用的空間與精確度之間的關系，我們用三種不同的計算方法在所有莎士比亞的作品計數了不同單詞的數量（90萬）。請注意，我們的輸入數據集有額外的數據，所以基數高于這個問題答案的標準參考。我們使用的三種技術是：Java HashSet、Linear Probabilistic Counter以及一個Hyper LogLog Counter。這里是結果：
該表顯示，我們只使用512字節的空間就可以進行計數，并且誤差在3%以內。相比之下，HashMap的計數準確度最高，但需要近10MB的空間，你可以很容易地看到為什么基數估計量是有用的。在實際應用中精度并不是很重要的，這是事實，在大多數網絡規模和網絡計算的情況下，用概率計數器可能會節省巨大的空間，這是真的。
線性概率計數器
線性概率計數器是高效的空間，并且允許實現者指定所需的精度水平。該算法在注重空間效率時是很有用的，但你需要能夠控制你結果里的誤差。該算法運行需要兩步：第一步，在內存中分配一個初始化為都為0的位圖，隨后哈希函數被應用于輸入數據中的每個條目，哈希函數的結果將映射條目到位圖的一個位上，該位設置為1；第二步算法對空位的數量進行計算，并使用這個數字輸入到下面的公式來獲得估計。
n=-m ln Vn
在方程中，m是位圖的大小，n是空位和映射的大小的比率。需要重點注意的是原始位圖的大小，可以遠小于預期的最大基數。小多少取決于你能忍受多少錯誤的結果。因為位圖的大小、m，小于不同元素的總數，將會有碰撞。這些碰撞都可以節省空間，但同時也造成了錯誤的估計。所以通過控制原始映射的大小，我們可以估算碰撞的次數，因此我們將在最終結果中看到誤差量。
Hyper LogLog
顧名思義，Hyper LogLog計數器的特點是，你僅需要使用loglog(Nmax)+一個常數那么多位就可以對Nmax進行計數。如線性計數器的Hyper LogLog計數器使設計人員能夠指定所需的精度公差，在Hyper LogLog的情況下，這是通過定義所需的相對標準偏差和你期望要計數的最大基數。大部分計數通過一個輸入數據流、M，并應用一個哈希函數設置h（M）來工作。這將產生一個S = h(M) of {0,1}^∞字符串的可觀測結果。通過分割成m子字符串的哈希輸入流，并為每個子數據保持m的觀測值擴展了Hyper LogLog。使用額外的觀測值的平均值，產生一個計數器，其精度提高為m的大小增長，只需要一個在輸入集的每個元素上恒定要執行的操作數目。其結果是，這個計數器可以僅使用1.5 kb的空間計算精度為2%的十億個截然不同的項。與執行 HashSet所需的120 兆字節進行比較，這種算法的效率變得很明顯。
合并分布式計數器
我們已經證明了使用上面描述的計數器我們可以估算大集合的基數。但是，如果你的原始輸入數據集不適合于單臺機器，你能做些什么？這正是我們在AddThis所面臨的問題。我們的數據分散在數百臺服務器上，并且每個服務器只包含整個數據集子集的一部分。這就是事實，我們可以合并一組分布式計數器的內容，這是至關重要的。這個想法有點令人費解，但如果你花費一些時間去思考這個概念，就會發現其與基本的基數估計值相比并沒有太大的不同。因為計數器代表映射中的位作為基數，我們可以采取兩個兼容計數器并將其位合并到單一的地圖。這個算法已經處理碰撞，所以我們可以得到一個基數估計所需的精密，即使我們從來沒有把所有的輸入數據到一臺機器。這是非常有用的，節省了我們在網絡中移動數據的大量時間和精力。
總結
希望這篇文章能幫助你更好地理解這個概念和概率計數器的應用。如果估計大集合的基數是一個問題，而你又碰巧使用一個基于JVM的語言，那么你應該使用stream-lib項目——它提供了其他幾個流處理工具以及上文所述的算法的實現。
