一、背景

學(xué)習(xí)Hadoop時(shí)接觸的第一個(gè)樣例就是word count，即統(tǒng)計(jì)文本中詞的數(shù)量。各種BI、營銷產(chǎn)品中不可或缺的模塊就是統(tǒng)計(jì)報(bào)表。在常見的搜索分頁模塊，也需要提供總記錄數(shù)。

統(tǒng)計(jì)在SQL引擎中可謂最基礎(chǔ)、最核心的能力之一?？赡苡捎谒A(chǔ)了，就像排序一樣，我們常常會忽視它背后的原理。通常的計(jì)數(shù)是非常簡單的，例如統(tǒng)計(jì)文本行數(shù)在linux系統(tǒng)上一個(gè)wc命令就搞定了。

除了通常的計(jì)數(shù)，統(tǒng)計(jì)不重復(fù)元素個(gè)數(shù)的需求也非常常見，這種統(tǒng)計(jì)稱為基數(shù)統(tǒng)計(jì)。對于Presto這種分布式SQL引擎，計(jì)數(shù)的實(shí)現(xiàn)原理值得深入研究，特別是基數(shù)統(tǒng)計(jì)。關(guān)于普通計(jì)數(shù)和基數(shù)計(jì)數(shù)，最典型的例子莫過于PV/UV。

二、基數(shù)統(tǒng)計(jì)主要算法

在SQL語法里面，基數(shù)統(tǒng)計(jì)對應(yīng)到count(distinct field)或者aprox_distinct()。通常做精確計(jì)數(shù)統(tǒng)計(jì)需要用到Set這種數(shù)據(jù)結(jié)構(gòu)。通過Set不僅可以獲得數(shù)量信息，還能不重不漏地獲取每一個(gè)元素。

Set內(nèi)部有兩種實(shí)現(xiàn)實(shí)現(xiàn)原理：Hash和Tree。

在海量數(shù)據(jù)的前提下，Hash和Tree有一個(gè)致命的問題：內(nèi)存消耗，而且隨著數(shù)據(jù)量級的增長，內(nèi)存消耗也是線性增長。

面對Set內(nèi)存消耗的問題，通常有兩種思路：

一種是選取其他內(nèi)存占用更小的數(shù)據(jù)結(jié)構(gòu)，例如bitmap；

另一種是放棄精確，從數(shù)學(xué)上尋求近似解，典型的算法有Linear Count和HyperLogLog。

2.1 Bitmap

在數(shù)據(jù)庫領(lǐng)域Bitmap并不是新事物，一般用作索引，稱為位圖索引。所謂位圖索引，就是用一個(gè)bit位向量來記錄某個(gè)字段值是否存在于對應(yīng)的記錄。它有一個(gè)前置條件：記錄要有永久的編號，類似于從1開始的自增主鍵。

2.1.1 位圖向量的構(gòu)建

舉個(gè)例子，假設(shè)表user記錄如下：

這是很典型的一張數(shù)據(jù)庫表。對于表中的字段，如何構(gòu)建位圖索引呢？以age字段為例：

• S1: 確定字段的取值集合空間: {30,40,50} 一共3個(gè)選項(xiàng)。
• S2: 依次為每個(gè)選項(xiàng)構(gòu)建一個(gè)長度為6的bit向量，得到一個(gè)3*6的位圖。3表示字段age的取值基數(shù)，6表示記錄數(shù)。

S3: 基于表設(shè)置位圖相應(yīng)向量值。例如：age=30的記錄id分別為{1,2,6}，那么在向量1,2,6位置置為1，其他置為0。得到110001。

同理，對于name字段，其向量位圖為：

可以看出，如果對于數(shù)據(jù)表的一個(gè)字段，如果記錄數(shù)為n且字段的取值基數(shù)為m，那么會得到一個(gè)m*n的位圖。

2.1.2 位圖向量的應(yīng)用

有了位圖向量，該如何使用呢？假設(shè)查詢SQL為

select count(1) from user where age=40;

則取age字段位圖中age=40的向量：110001。統(tǒng)計(jì)其中1的個(gè)數(shù)，即可得到最終結(jié)果。

假設(shè)查詢SQL更復(fù)雜一些：

select count(1) from user where age=40 and name='baz'

則取age字段位圖中age=40的向量：110001和name='foo'的向量：100100。兩個(gè)向量進(jìn)行交集運(yùn)算：

最后統(tǒng)計(jì)結(jié)果為1。

關(guān)于Bitmap的思想，筆者認(rèn)為最巧妙的一點(diǎn)就是通過位運(yùn)算實(shí)現(xiàn)了集合運(yùn)算。如下圖所示：

在不同的業(yè)務(wù)場景中，這里的集合可以賦予不同的業(yè)務(wù)含義。

2.1.3 位圖向量的優(yōu)點(diǎn)

將字段的篩選變成了向量計(jì)算后，會非常節(jié)約內(nèi)存，而且可以通過分段長度編碼等方式對bitmap向量進(jìn)行壓縮。而且位運(yùn)算直接對內(nèi)存中的二進(jìn)制位進(jìn)行操作，執(zhí)行效率非常高，是性能提升的一大殺器。

理解了bitmap后，可以發(fā)現(xiàn)對于整型字段，可以直接用bitmap進(jìn)行基數(shù)統(tǒng)計(jì)。筆者曾經(jīng)實(shí)驗(yàn)過，對于3億數(shù)據(jù)量級使用roaringbitmap工具，bitmap消耗內(nèi)存約30M，而且如果數(shù)據(jù)分布非常密集內(nèi)存消耗還有很大的壓縮空間。唯一的缺點(diǎn)是非數(shù)值型字段，需要進(jìn)行額外的轉(zhuǎn)換處理。

2.2 Linear Count算法

Linear Count簡稱LC算法，LC算法的流程非常簡單(背后的數(shù)學(xué)思想不簡單)。

算法描述如下：

初始化：給定m個(gè)房間，房間存儲數(shù)字，初始化為0。
迭代執(zhí)行：對于要進(jìn)行基數(shù)統(tǒng)計(jì)的集合，用一個(gè)哈希函數(shù)處理集合中的每一個(gè)元素。通過哈希函數(shù)處理后，元素就可以放置到一個(gè)房間中。
收尾：統(tǒng)計(jì)m個(gè)房間中空房間的數(shù)量U。
結(jié)論：集合中不重復(fù)元素的個(gè)數(shù)估計(jì)值可以通過如下公式計(jì)算：n=-m*log(U/m)。

這樣就把一個(gè)統(tǒng)計(jì)問題轉(zhuǎn)換成了一個(gè)數(shù)學(xué)問題。公式非常簡潔，看到這里大腦中一定會出現(xiàn)許多的問題：

• 這個(gè)公式是怎么得到的？

這里涉及到概率論與數(shù)理統(tǒng)計(jì)知識，簡單來說就是分布、期望、方差、最大似然估計(jì)。數(shù)學(xué)相關(guān)的知識比較初級，陳希孺的《概率論與數(shù)理統(tǒng)計(jì)》基本能覆蓋這個(gè)公式的數(shù)學(xué)原理。

• 這個(gè)算法的精確度怎么樣？

這個(gè)問題從數(shù)學(xué)的角度，就是問方差(標(biāo)準(zhǔn)差)。這里沒法給一個(gè)具體的值，跟滿桶率控制， m的選擇有關(guān)。

這個(gè)算法相比精確計(jì)數(shù)很省空間嗎？

這個(gè)毋庸置疑，不然直接精確統(tǒng)計(jì)就可以了。

• m和最終結(jié)果n需要滿足什么關(guān)系？

（畢竟當(dāng)沒有空房間時(shí)，這個(gè)公式就有問題了。） 這里直接給結(jié)論吧，隨著m和n的增大，m大約為n的十分之一。

2.3 HyperLogLog算法

HyperLogLog簡稱HLL算法，它有如下的特點(diǎn)：

1. 可以實(shí)現(xiàn)由極小的內(nèi)存開銷統(tǒng)計(jì)出巨量的數(shù)據(jù)。在 Redis中實(shí)現(xiàn)的HyperLogLog，只需要12K內(nèi)存就能統(tǒng)計(jì)2^64個(gè)數(shù)據(jù)。
2. 可以方便實(shí)現(xiàn)分布式擴(kuò)展。(這個(gè)點(diǎn)對算法在業(yè)務(wù)系統(tǒng)中落地非常關(guān)鍵)

理解HLL算法，需要如下幾個(gè)知識點(diǎn)的鋪墊：伯努利實(shí)驗(yàn)、調(diào)和平均數(shù)。

伯努利實(shí)驗(yàn)有很多的呈現(xiàn)方式，本文例舉其中的一種： 取一枚硬幣，不斷拋擲，直到硬幣落地結(jié)果為正面朝上。這樣的執(zhí)行過程稱為一輪實(shí)驗(yàn)。從描述可以看出一輪實(shí)驗(yàn)完成拋擲硬幣的次數(shù)是隨機(jī)的。

一輪實(shí)驗(yàn)對應(yīng)的Java代碼實(shí)現(xiàn)如下：

private Random random = new Random();
/**
? 0代表正面
? 1代表反面
? 拋擲直到出現(xiàn)正面
? @return 拋擲的次數(shù)
*/
public int tossCoin(){
int r,cnt=0;
do{
r=random.nextInt(2);
cnt++;
}while (r<1);
return cnt;
}

可以看出，每執(zhí)行一輪實(shí)驗(yàn)就會得到一個(gè)數(shù)字，代表這輪實(shí)驗(yàn)拋擲硬幣的次數(shù)。例如：

執(zhí)行了10輪，可能的結(jié)果如下：

3,1,4,1,1,2,3,4,1,1

執(zhí)行了100輪，可能的結(jié)果如下：

1,1,2,1,1,2,1,4,2,1,3,1,1,1,1,3,1,2,1,1,2,4,2,3,2,1,1,1,3,1,2,2,6,1,2,4,1,2,2,1,1,3,1,1,1,1,1,1,1,1,1,4,2,1,1,1,1,1,3,1,2,4,4,4,1,3,2,1,5,1,1,1,1,1,1,1,5,1,1,7,1,1,4,1,3,2,1,1,5,2,1,1,5,2,1,1,4,1,1,1

執(zhí)行了1000輪，可能的結(jié)果如下：

1,2,1,2,1,3,3,3,1,1,2,2,1,2,1,1,1,1,1,2,1,7,1,1,1,2,2,1,1,3,5,2,3,2,3,1,1,3,1,  ...,4,1,1,1,2,2,1,3,1,1,1,2,1,1,1,2,1,4,2,2,1,2,2,2,1,1,1,2,2,2,1,1,1,2,2,1,1,3,2,6,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1

這時(shí)候問題就來了，我們這樣按上面的規(guī)則不停的拋硬幣只是為了應(yīng)付無聊的時(shí)間嗎？當(dāng)然不是！我們關(guān)注的重點(diǎn)是：

當(dāng)然，這個(gè)最大值是隨機(jī)變動(dòng)的，它不是一個(gè)固定的值。但是隱約中有個(gè)規(guī)律：執(zhí)行的輪次越多，輪次對應(yīng)的最大值也越大。數(shù)學(xué)上可以給一個(gè)很粗略的公式來擬合這種關(guān)系：n=2^p。

換言之，我們可以通過p來估計(jì)n。到這里就出現(xiàn)了問題解決思路的轉(zhuǎn)換：

將基數(shù)統(tǒng)計(jì)問題轉(zhuǎn)換成概率論里面參數(shù)估計(jì)的問題。

思維轉(zhuǎn)換到了數(shù)學(xué)領(lǐng)域，就可以用數(shù)學(xué)的工具來解決問題。通常用概率論的思維解決問題，會面臨如下幾個(gè)攔路虎。

問題一：最大值不穩(wěn)定，容易受到極值影響。

在概率上，對于極值我們的處理策略是多實(shí)驗(yàn)幾輪，通過平均值來消除極值的影響。這個(gè)就引出了第二基礎(chǔ)知識點(diǎn)：調(diào)和平均數(shù)。

數(shù)學(xué)上其實(shí)有許多的平均數(shù)計(jì)算方式：算術(shù)平均數(shù)、幾何平均數(shù)、平方平均數(shù)。這里選用調(diào)和平均數(shù)主要是消除極值的影響。通常有個(gè)笑話說，我的收入是1萬，老板的收入是1億，我們平均收入是5000萬，我被平均了。如果用調(diào)和平均數(shù)，得到的結(jié)果就是1999.98。

關(guān)于調(diào)和平均數(shù)的公式，非常容易理解：

關(guān)于數(shù)學(xué)，確切地說是概率論的知識點(diǎn)，還有很多。例如估計(jì)方法是有偏估計(jì)還是無偏估計(jì)？，估計(jì)的方差和標(biāo)準(zhǔn)差是多大？這里涉及到較為底層的概率論知識，就先略過。

略過數(shù)學(xué)知識，關(guān)鍵的問題在于，我們?nèi)绾螌⒋鶖?shù)統(tǒng)計(jì)問題跟上面的伯努利實(shí)驗(yàn)建立聯(lián)系？這兩個(gè)點(diǎn)之間的橋梁就是Hash函數(shù)。第一次見識到Hash函數(shù)還能這樣用，確實(shí)大開眼界。

對于相同的數(shù)，通過hash函數(shù)生成的散列值是相同的，這就進(jìn)行了排重。當(dāng)然不排除不同的數(shù)據(jù)生成同樣的hash值，形成沖突。由于選取的hash函數(shù)例如MurmurHash3沖突率低，可以忽略這個(gè)因素。

實(shí)際上，由于Hash函數(shù)生成的二進(jìn)制串通常具備均勻的特性，所以Hash函數(shù)生成的二進(jìn)制串可以視為拋擲硬幣的結(jié)果。

對于一個(gè)待進(jìn)行基數(shù)統(tǒng)計(jì)的集合(例如一個(gè)表中符合條件的字段值)，為了降低估計(jì)的錯(cuò)誤率，我們分成m組。某個(gè)值歸屬于哪個(gè)組由hash函數(shù)生成結(jié)果對應(yīng)的前幾位決定，剩下的二進(jìn)制串用于計(jì)算當(dāng)前輪伯努利實(shí)驗(yàn)第一次出現(xiàn)正面時(shí)拋擲的次數(shù)，記為p。

所以算法描述如下：

簡單來說就是統(tǒng)計(jì)每個(gè)組最大的p, 然后用現(xiàn)成的公式計(jì)算結(jié)果即到達(dá)預(yù)估的結(jié)果。

三、分布式計(jì)數(shù)核心流程

對于Hadoop中的入門案例wordcount，可以發(fā)現(xiàn)如果用Presto SQL表達(dá)如下(以tpch數(shù)據(jù)集customer表name字段為例)：

select w, count(1) cnt from (
select split(name,'#') words from customer
) t1 cross join  UNNEST(t1.words) AS t (w)
group by w;

可以看出相比大段的代碼，SQL處理對用于來說要簡單的多。無論是哪種表達(dá)方式，核心點(diǎn)就是分組統(tǒng)計(jì)。

在MapReduce框架核心流程如下：

那么在Presto， 其執(zhí)行流程是什么樣呢？

從邏輯上，都是類似的。先分組聚合，然后匯總聚合。

四、基數(shù)統(tǒng)計(jì)在Presto中的落地

對于基數(shù)統(tǒng)計(jì)問題Presto支持兩種實(shí)現(xiàn)方式。一種是追求精確的count distinct; 另一種是提供近似統(tǒng)計(jì)的approx_distinct。

count distinct的核心細(xì)節(jié)

以SQL ：select count(distinct id) from hive_table 為例。

即以id為主key, 對數(shù)據(jù)進(jìn)行hash分發(fā)，進(jìn)行部分聚合，最終整體聚合。依然是map-reduce的思路，只不過數(shù)據(jù)按id進(jìn)行了分發(fā)。

aprox_distinct的核心細(xì)節(jié)

這里就免去了基于id的hash分發(fā)策略。所以也減少了一個(gè)stage。至于approx_distinct的內(nèi)部細(xì)節(jié)，基礎(chǔ)框架airlift中，封裝了HyperLogLog算法的實(shí)現(xiàn)，采用的函數(shù)是MurMurHash3算法，生成64位散列值。前6位用于計(jì)算當(dāng)前散列值所在分組m。實(shí)現(xiàn)過程中還有一個(gè)很有意思的細(xì)節(jié)：基于待統(tǒng)計(jì)的數(shù)據(jù)量，實(shí)現(xiàn)中同時(shí)采用了Linear Count算法和HyperLogLog算法。

五、業(yè)務(wù)建議

通過上面的分析，我們可以發(fā)現(xiàn)高基數(shù)統(tǒng)計(jì)是一個(gè)非常消耗內(nèi)存的操作，特別是在分布式系統(tǒng)背景下，不僅消耗內(nèi)存，而且涉及大量網(wǎng)絡(luò)數(shù)據(jù)傳輸。如果分析對應(yīng)的業(yè)務(wù)場景，可以提供近似值而非精確值，那么就能大幅度降低系統(tǒng)消耗和響應(yīng)時(shí)間，提升用戶體驗(yàn)?；蛘咴谠O(shè)計(jì)產(chǎn)品的時(shí)候，對于一些場景的計(jì)數(shù)，可以優(yōu)先提供近似估計(jì)，如果用戶確實(shí)需要精確計(jì)數(shù)，那么在管理好用戶響應(yīng)時(shí)間預(yù)期下，再提供查詢精確值的接口。

理解了精確統(tǒng)計(jì)和近似統(tǒng)計(jì)的細(xì)節(jié)及各種優(yōu)缺點(diǎn)，處理問題的思路就會更開闊。例如：在設(shè)計(jì)存儲索引時(shí)，我們可以優(yōu)先使用HyperLogLog統(tǒng)計(jì)一個(gè)字段的基數(shù)近似值，如果得到的結(jié)果不是高基數(shù)，那么我們可以對字段構(gòu)建bitmap索引，借此提升數(shù)據(jù)處理的效率。

在《我們?nèi)绾巫叩浇裉欤褐厮苁澜绲?項(xiàng)創(chuàng)新 》一書中有這樣一個(gè)觀點(diǎn)讓人記憶深刻：我們衡量越精確，控制的能力就越強(qiáng)。但是它沒有說的是，衡量越精確，成本就越大。