1. 什么是基數(shù)計(jì)算

基數(shù)計(jì)算（cardinality counting）指的是統(tǒng)計(jì)一批數(shù)據(jù)中的不重復(fù)元素的個數(shù)，常見于計(jì)算獨(dú)立用戶數(shù)（UV）作谚、維度的獨(dú)立取值數(shù)等等。實(shí)現(xiàn)基數(shù)統(tǒng)計(jì)最直接的方法，就是采用集合（Set）這種數(shù)據(jù)結(jié)構(gòu)撬腾，當(dāng)一個元素從未出現(xiàn)過時钓试，便在集合中增加一個元素装黑；如果出現(xiàn)過，那么集合仍保持不變弓熏。
在大數(shù)據(jù)的場景中曹体，實(shí)現(xiàn)基數(shù)統(tǒng)計(jì)往往去面臨以下的兩個問題：

• 如果有效的存儲原始數(shù)據(jù)，以避免數(shù)據(jù)占用空間過多硝烂，這里就涉及到存儲空間壓縮的問題
• 如果能夠跨不同的維度箕别、不同的時間段實(shí)現(xiàn)基數(shù)計(jì)算，比如在計(jì)算日度UV的情況下滞谢，如果計(jì)算出周度串稀、或者月度的UV

本文旨在介紹目前比較成熟的基數(shù)計(jì)算的方式，并通過實(shí)例對比他們在解決以上兩個問題上的效果狮杨，最后引出本文的重點(diǎn)母截，HyperLogLog算法的實(shí)現(xiàn)和應(yīng)用。

2. Bitmap

2.1 基本原理

Bitmap進(jìn)行基數(shù)計(jì)算的方法橄教，是先定義一個bit數(shù)組清寇，數(shù)組中的每一位對應(yīng)數(shù)據(jù)的一種取值。由于bit是計(jì)算機(jī)中的最小單位护蝶，使用bit可以大量的減少存儲空間华烟。例如一個數(shù)組[1,3,4,5]，那么對應(yīng)的bitmap即為[0,0,0,1,1,1,0,1]持灰，后續(xù)每新增加一個元素盔夜，就和現(xiàn)有的bitmap進(jìn)行OR操作，通過計(jì)算bitmap中1的個數(shù)，即可以得到基數(shù)計(jì)算的結(jié)果喂链。

正是因?yàn)閎itmap之間對OR也是良好支持的返十，兩個bitmap在進(jìn)行OR操作之后，便是這兩個條件組合下的基數(shù)計(jì)算結(jié)果椭微，因此使用bitmap是可以實(shí)現(xiàn)任意條件下的基數(shù)計(jì)算洞坑。

2.2 空間使用

按照上面介紹的原理，進(jìn)行bitmap的構(gòu)建蝇率。假如統(tǒng)計(jì)1億數(shù)據(jù)的基數(shù)值迟杂，大約需要內(nèi)存100000000/8/1024/1024 ~= 12M，如果有100個這樣的對象瓢剿，就需要1.2G的內(nèi)存空間逢慌，可見占用內(nèi)存還是很大的，在實(shí)際業(yè)務(wù)中基本很少使用间狂。

3. Linear Counting

3.1 基本原理

Linear Counting是采用概率的方式進(jìn)行基數(shù)估計(jì)的最簡單的方法攻泼。下面通過一個實(shí)例描述Linear Counting的計(jì)算過程：

• 數(shù)據(jù)哈希：假設(shè)原始數(shù)據(jù)的基數(shù)為n，使用一組哈霞螅空間為m的哈希函數(shù)H忙菠，將原始數(shù)據(jù)轉(zhuǎn)換為滿足均勻分組的一組哈希數(shù)組。

• 分桶數(shù)據(jù)統(tǒng)計(jì)：構(gòu)建一個長度為m的bitmap纺弊，其中每一個bit對應(yīng)哈吓；叮空間的一個值。生成哈希數(shù)組的值如果存在淆游，則把相應(yīng)的bit設(shè)置為1傍睹。當(dāng)所有值設(shè)置完成后，統(tǒng)計(jì)bitmap中為0的bit數(shù)為u犹菱。

  
  

可以通過下述的公式計(jì)算基數(shù)估計(jì)的結(jié)果：

注意這里的log指的是自然對數(shù)拾稳。

公式的推導(dǎo)過程有興趣的可以參考這篇文章。其中最重要的是要清楚腊脱，在經(jīng)過n次數(shù)據(jù)的哈希后访得，bitmap中的某個bit值為0，是一個伯努利事件陕凹。記住這一點(diǎn)再理解公式推導(dǎo)就容易多了悍抑。

3.2 空間使用

Linear Counting的空間使用，和bitmap相比杜耙，空間復(fù)雜度是一致的搜骡，僅有線性下降。因此如果對于1億的原始數(shù)據(jù)泥技，仍然需要MB級別的內(nèi)存空間存儲浆兰。Linear Counting在實(shí)際應(yīng)用中也很少被使用磕仅。

4. LogLog Counting

4.1 伯努利過程

在介紹LogLog Counting之前珊豹，我們先來回顧一下伯努利過程的概念簸呈。

伯努利過程是一個由有限個或無限個的獨(dú)立隨機(jī)變量 X1, X2, X3 ,..., 所組成的離散時間隨機(jī)過程，其中 X1, X2, X3 ,..., 滿足如下條件：
對每個 i, Xi 等于 0 或 1; 對每個 i, Xi = 1 的概率等于 p. 換言之店茶，伯努利過程是一列獨(dú)立同分布的伯努利試驗(yàn)蜕便。每個Xi 的2個結(jié)果也被稱為“成功”或“失敗”。所以當(dāng)用數(shù)字 0 或 1 來表示的時候贩幻，這個數(shù)字被稱為第i個試驗(yàn)的成功次數(shù)轿腺。

舉一個常見的例子：每次拋硬幣之后，出現(xiàn)正面和反面的概率分別為1/2丛楚，如果不停地拋硬幣族壳，直至出現(xiàn)正面為止，這就是一個伯努利過程趣些。
這樣仿荆，我們假設(shè)一共進(jìn)行了n次伯努利過程，出現(xiàn)正面的次數(shù)分別為k1, k2, ... kmax坏平，那么有以下兩個結(jié)論：

• n次伯努利過程的投擲次數(shù)都不大于kmax
• n次伯努利過程拢操，至少有一次的投擲次數(shù)等于kmax

已知投擲k次才出現(xiàn)正面的概率為：1/2^k，那么：

• 第一種情況的概率為：

  
  

• 第二種情況的概率為：

  
  

如果n >> 2^k舶替，則P(x >= kmax)為0令境；如果n << 2^k，則P(x <= kmax)為0顾瞪。因此我們可以用2^k來作為n的近似估計(jì)結(jié)果舔庶。

4.2 伯努利過程與LogLog Counting

如何將基數(shù)計(jì)算，等價地認(rèn)為是一個伯努利過程陈醒，是LogLog Counting的關(guān)鍵所在惕橙。這里我們可以把原始數(shù)據(jù)進(jìn)行哈希，哈希后的數(shù)組是滿足均勻分布的孵延。把每個元素看做一個投擲硬幣的過程吕漂，將元素轉(zhuǎn)換為2進(jìn)制之后，每個bit出現(xiàn)0和1的概率是相等的尘应。從高位開始查惶凝，第一次出現(xiàn)1的位置記為k，即等同于投擲硬幣時出現(xiàn)第一個正面犬钢，將所有元素出現(xiàn)1的位置的最大值苍鲜，記為kmax，那么2^kmax就是基數(shù)計(jì)算的結(jié)果玷犹。

4.3 LogLog Counting計(jì)算過程

• 數(shù)據(jù)哈希：這個和Linear Counting是類似的混滔，都需要保證哈希后的數(shù)據(jù)是滿足均勻分布的。
• 轉(zhuǎn)換為2進(jìn)制：將哈希后的每個元素，都轉(zhuǎn)換為2進(jìn)制坯屿，由于數(shù)據(jù)在哈希后滿足均勻分布的油湖，2進(jìn)制數(shù)據(jù)每一個bit的0和1出現(xiàn)的概率都是1/2，這里設(shè)2進(jìn)制數(shù)據(jù)的位數(shù)為L领跛。
• 統(tǒng)計(jì)第一個1出現(xiàn)的位置：分別計(jì)算每個2進(jìn)制數(shù)據(jù)乏德，第一次出現(xiàn)1的次數(shù)。所有次數(shù)中的最大值為kmax吠昭，那么2^kmax就是最終結(jié)果喊括。

下圖中給出一個針對一個元素進(jìn)行k值計(jì)算的過程。

4.4 數(shù)據(jù)分桶

上面的計(jì)算過程矢棚，由于是單一估計(jì)量郑什，可能會出現(xiàn)一定的偶然性導(dǎo)致誤差。因此這里引入數(shù)據(jù)分桶的方法蒲肋。取哈夏⒄空間分成m個桶，用哈希值的前幾個bit的值來決定數(shù)據(jù)屬于哪一個桶肉津，再對桶內(nèi)的數(shù)據(jù)取k值强胰，最終計(jì)算出kmax。再將所有桶的kmax取平均數(shù)妹沙，這樣就通過多次估計(jì)取平均的方式偶洋，消除了單一估計(jì)可能存在的偶然性誤差。計(jì)算公式如下：

4.5 誤差修正和分析

以上的過程仍然是存在誤差的距糖，并不是無偏估計(jì)玄窝。將上述過程修正為無偏估計(jì)的過程由于過于復(fù)雜，這里就不再介紹了悍引。需要了解的是恩脂，最終結(jié)果的誤差公式為：

4.6 空間使用

到這里，我們就可以理解LogLog Counting中兩個log了趣斤，它們的含義分別如下：

• 第一次log俩块，和Linear Counting很類似，由于使用哈希浓领，壓縮了數(shù)據(jù)空間玉凯。
• 第二次log，由于在存儲哈希值的第一次1出現(xiàn)的次數(shù)時联贩，只需要存儲結(jié)果k漫仆，而不需要存儲原始的哈希值，進(jìn)一步節(jié)省了空間泪幌。

加入哈希之后的值有32bit盲厌，那么每個桶需要5bit保存kmax的值署照，m個桶就是m5/8 B。
如果基數(shù)是1億個（2^{27）吗浩，當(dāng)分桶數(shù)為1024時建芙，每個桶的基數(shù)上限為2}27 / 2^10 = 2^{17，log(log(2}17))=4.09拓萌，那么每個桶需要5bit保存kmax岁钓，總共需要的空間為51024/8升略，等于640B微王，可見是非常小的。

5. Adapative Counting

通過概率計(jì)算可知品嚣，LogLog Counting由于使用了幾何平均值炕倘，可能出現(xiàn)在基數(shù)較小的情況，有些桶是為空的翰撑≌中空桶對于最后平均值的計(jì)算干擾較大。
Adapative Counting的思想是將Linear Counting和LogLog Counting進(jìn)行結(jié)合眶诈。Linear Counting和LogLog Counting的存儲結(jié)構(gòu)是類似的涨醋，僅僅是Linear Couting關(guān)心桶是否為空，而LogLog Counting需要桶中的kmax逝撬。

最終分析得到的結(jié)論是：在空桶率大于0.051時浴骂，使用Linear Counting的偏差率更小宪潮；在空桶率小于0.051時溯警，使用LogLog Counting的偏差率更小。

6. HyperLogLog Counting

HyperLogLog Counting狡相，是在LogLog Counting的基礎(chǔ)上梯轻，將桶之間計(jì)算采用的幾何平均，修改為調(diào)和平均尽棕，可以有效的減少空桶對于平均值的影響喳挑。
調(diào)和平均的計(jì)算公式如下：

使用調(diào)和平均后的偏差公式為：

可見偏差期望和LogLog Counting相比要更小。

參考文獻(xiàn)

1. Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure
2. 解讀Cardinality Estimation算法（第一部分：基本概念）