為了更好地理解已經(jīng)明確基數(shù)的大數(shù)據(jù)集的挑戰(zhàn)，我們假設(shè)你的日志文件包含16個字符的ID,并且你想統(tǒng)計不同ID的數(shù)量.例如:

　　4f67bfc603106cb2

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

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

　　幸運的是，基數(shù)估計是一個熱門的研究領(lǐng)域。我們已經(jīng)利用這項研究提供了一個開源實現(xiàn)的基數(shù)估計、集合元素檢測和top-k算法。

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

　　該表顯示，我們統(tǒng)計這些單詞只用了512 bytes，而誤差在3%以內(nèi)。相比之下，HashMap的計數(shù)準確度最高，但需要近10MB的空間，你可以很容易地看到為什么基數(shù)估計是有用的。在實際應(yīng)用中準確性并不是很重要的，這是事實，在大多數(shù)網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)計算的情況下，用概率計數(shù)器會節(jié)省巨大的空間。

　　線性概率計數(shù)器

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

　　n=-m ln Vn

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

　　Hyper LogLog

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

　　合并分布式計數(shù)器

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

　　Next Steps

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