為了更好地理解已經(jīng)明確基數(shù)的大數(shù)據(jù)集的挑戰(zhàn)，我們假設(shè)你的日志文件包含16個(gè)字符的ID,并且你想統(tǒng)計(jì)不同ID的數(shù)量.例如:
4f67bfc603106cb2
這16個(gè)字符需要用128位來表示。6萬5千個(gè)ID將需要1MB的空間。我們每天收到30多億條事件記錄，每條記錄都有一個(gè)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)存的機(jī)器來計(jì)算不同的元素，并且這只是計(jì)算一天內(nèi)日志事件記錄的唯一ID的內(nèi)存消耗。如果我們想要統(tǒng)計(jì)數(shù)周或數(shù)月的數(shù)據(jù)，這問題只會變得更加困難。我們身邊當(dāng)然不會有一臺配備幾百GB內(nèi)存的空閑機(jī)器，所以我們需要一個(gè)更好的解決方案。
解決這一問題的常見辦法是使用位圖(博客：海量數(shù)據(jù)處理算法—Bit-Map)。位圖可以快速、準(zhǔn)確地獲取一個(gè)給定輸入的基數(shù)。位圖的基本思想是使用哈希函數(shù)把數(shù)據(jù)集映射到一個(gè)bit位，每個(gè)輸入元素與bit位是一一對應(yīng)。這樣Hash將沒有產(chǎn)生碰撞沖突，并減少需要計(jì)算每個(gè)元素映射到1個(gè)bit的空間。雖然Bit-map大大節(jié)省了存儲空間，但當(dāng)統(tǒng)計(jì)很高的基數(shù)或非常大的不同的數(shù)據(jù)集，它們?nèi)匀挥袉栴}。例如，如果我們想要使用Bit-map計(jì)數(shù)十億，你將需要Bit-map位，或需要每個(gè)約120 MB的計(jì)數(shù)器。稀疏的位圖可以被壓縮，以獲得更多的空間效率，但也并不總是有幫助的。
幸運(yùn)的是，基數(shù)估計(jì)是一個(gè)熱門的研究領(lǐng)域。我們已經(jīng)利用這項(xiàng)研究提供了一個(gè)開源實(shí)現(xiàn)的基數(shù)估計(jì)、集合元素檢測和top-k算法。
基數(shù)估計(jì)算法就是使用準(zhǔn)確性換取空間。為了說明這一點(diǎn)，我們用三種不同的計(jì)算方法統(tǒng)計(jì)所有莎士比亞作品中不同單詞的數(shù)量。請注意，我們的輸入數(shù)據(jù)集增加了額外的數(shù)據(jù)以致比問題的參考基數(shù)更高。這三種技術(shù)是：Java HashSet、Linear Probabilistic Counter以及一個(gè)Hyper LogLog Counter。結(jié)果如下：
該表顯示，我們統(tǒng)計(jì)這些單詞只用了512 bytes，而誤差在3%以內(nèi)。相比之下，HashMap的計(jì)數(shù)準(zhǔn)確度最高，但需要近10MB的空間，你可以很容易地看到為什么基數(shù)估計(jì)是有用的。在實(shí)際應(yīng)用中準(zhǔn)確性并不是很重要的，這是事實(shí)，在大多數(shù)網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)計(jì)算的情況下，用概率計(jì)數(shù)器會節(jié)省巨大的空間。
線性概率計(jì)數(shù)器
線性概率計(jì)數(shù)器是高效的使用空間，并且允許實(shí)現(xiàn)者指定所需的精度水平。該算法在注重空間效率時(shí)是很有用的，但你需要能夠控制結(jié)果的誤差。該算法分兩步運(yùn)行：第一步，首先在內(nèi)存中分配一個(gè)初始化為都為0的Bit-map，然后使用哈希函數(shù)對輸入數(shù)據(jù)中的每個(gè)條目進(jìn)行hash計(jì)算，哈希函數(shù)運(yùn)算的結(jié)果是將每條記錄(或者是元素)映射到Bit-map的一個(gè)Bit位上，該Bit位被置為1;第二步，算法計(jì)算空的bit位數(shù)量，并使用這個(gè)數(shù)輸入到下面的公式來進(jìn)行估算：
n=-m ln Vn
在公式中，m是 Bit-map的大小，Vn是空bit位和map的大小的比率。需要重點(diǎn)注意的是原始Bit-map的大小，可以遠(yuǎn)小于預(yù)期的最大基數(shù)。到底小多少取決于你可以承受誤差的大小。因?yàn)锽it-map的大小m小于不同元素的總數(shù)將會產(chǎn)生碰撞。雖然碰撞可以節(jié)省空間，但同時(shí)也造成了估算結(jié)果出現(xiàn)誤差。所以通過控制原始map的大小，我們可以估算碰撞的次數(shù)，以致我們將在最終結(jié)果中看到誤差有多大。
Hyper LogLog
顧名思義，Hyper LogLog計(jì)數(shù)器就是估算Nmax為基數(shù)的數(shù)據(jù)集僅需使用loglog(Nmax)+O(1) bits就可以。如線性計(jì)數(shù)器的Hyper LogLog計(jì)數(shù)器允許設(shè)計(jì)人員指定所需的精度值，在Hyper LogLog的情況下，這是通過定義所需的相對標(biāo)準(zhǔn)差和預(yù)期要計(jì)數(shù)的最大基數(shù)。大部分計(jì)數(shù)器通過一個(gè)輸入數(shù)據(jù)流M，并應(yīng)用一個(gè)哈希函數(shù)設(shè)置h(M)來工作。這將產(chǎn)生一個(gè)S = h(M) of {0,1}^∞字符串的可觀測結(jié)果。通過分割哈希輸入流成m個(gè)子字符串，并對每個(gè)子輸入流保持m的值可觀測 ，這就是相當(dāng)一個(gè)新Hyper LogLog(一個(gè)子m就是一個(gè)新的Hyper LogLog)。利用額外的觀測值的平均值，產(chǎn)生一個(gè)計(jì)數(shù)器，其精度隨著m的增長而提高，這只需要對輸入集合中的每個(gè)元素執(zhí)行幾步操作就可以完成。其結(jié)果是，這個(gè)計(jì)數(shù)器可以僅使用1.5 kb的空間計(jì)算精度為2%的十億個(gè)不同的數(shù)據(jù)元素。與執(zhí)行 HashSet所需的120 兆字節(jié)進(jìn)行比較，這種算法的效率很明顯。
合并分布式計(jì)數(shù)器