基數(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ù)器會(huì)節(jié)省巨大的空間。

再者，如果我們要實(shí)現(xiàn)記錄網(wǎng)站每天訪問的獨(dú)立IP數(shù)量這樣的一個(gè)功能：

集合實(shí)現(xiàn)：

使用集合來儲(chǔ)存每個(gè)訪客的 IP ，通過集合性質(zhì)（集合中的每個(gè)元素都各不相同）來得到多個(gè)獨(dú)立 IP，然后通過調(diào)用 SCARD 命令來得出獨(dú)立 IP 的數(shù)量。

舉個(gè)例子，程序可以使用以下代碼來記錄 2017 年 12 月 5 日，每個(gè)網(wǎng)站訪客的 IP ：

ip = get_vistor_ip() SADD'2017.12.5::unique::ip'ip

然后使用以下代碼來獲得當(dāng)天的唯一 IP 數(shù)量：

SCARD'2017.12.5::unique::ip'

集合實(shí)現(xiàn)的問題

使用字符串來儲(chǔ)存每個(gè)IPv4 地址最多需要耗費(fèi)15 字節(jié)（格式為 ‘XXX.XXX.XXX.XXX’，比如’202.189.128.186’）。

下表給出了使用集合記錄不同數(shù)量的獨(dú)立 IP 時(shí)，需要耗費(fèi)的內(nèi)存數(shù)量：

獨(dú)立IP數(shù)量 一天 一個(gè)月 一年
一百萬?15 MB?450 MB?5.4 GB?
一千萬?150 MB?4.5 GB?54 GB?
一億?1.5 GB?45 GB?540 GB?

隨著集合記錄的 IP 越來越多，消耗的內(nèi)存也會(huì)越來越多。另外如果要儲(chǔ)存 IPv6 地址的話，需要的內(nèi)存還會(huì)更多一些。為了更好地解決像獨(dú)立 IP 地址計(jì)算這種問題，Redis 在 2.8.9 版本添加了 HyperLogLog 結(jié)構(gòu)。

Redis數(shù)據(jù)結(jié)構(gòu)HyperLogLog

Redis HyperLogLog 是用來做基數(shù)統(tǒng)計(jì)的算法，HyperLogLog 的優(yōu)點(diǎn)是，在輸入元素的數(shù)量或者體積非常非常大時(shí)，計(jì)算基數(shù)所需的空間總是固定的、并且是很小的。在Redis 里面，每個(gè) HyperLogLog 鍵只需要花費(fèi) 12 KB 內(nèi)存，就可以計(jì)算接近 2^64 個(gè)不同元素的基數(shù)。這和使用集合計(jì)算基數(shù)時(shí)，元素越多耗費(fèi)內(nèi)存就越多的集合形成鮮明對比。但是，因?yàn)?HyperLogLog 只會(huì)根據(jù)輸入元素來計(jì)算基數(shù)，而不會(huì)儲(chǔ)存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個(gè)元素。

什么是基數(shù)?

比如數(shù)據(jù)集 {1, 3, 5, 7, 5, 7, 8}， 那么這個(gè)數(shù)據(jù)集的基數(shù)集為 {1, 3, 5 ,7, 8}, 基數(shù)(不重復(fù)元素)為5。 基數(shù)估計(jì)就是在誤差可接受的范圍內(nèi)，快速計(jì)算基數(shù)。

估算值：算法給出的基數(shù)并不是精確的，可能會(huì)比實(shí)際稍微多一些或者稍微少一些，但會(huì)控制在合理的范圍之內(nèi)。

幾個(gè)命令

將元素添加至 HyperLogLog

1、PFADD key element [element …]

將任意數(shù)量的元素添加到指定的 HyperLogLog 里面。

這個(gè)命令可能會(huì)對 HyperLogLog 進(jìn)行修，以便反映新的基數(shù)估算值，如果 HyperLogLog 的基數(shù)估算值在命令執(zhí)行之后出現(xiàn)了變化，那么命令返回1，否則返回0。

命令的復(fù)雜度為 O(N) ，N 為被添加元素的數(shù)量。

2、PFCOUNT key [key …]

返回給定 HyperLogLog 的基數(shù)估算值。

當(dāng)只給定一個(gè) HyperLogLog 時(shí)，命令返回給定 HyperLogLog 的基數(shù)估算值。

當(dāng)給定多個(gè) HyperLogLog 時(shí)，命令會(huì)先對給定的 HyperLogLog 進(jìn)行并集計(jì)算，得出一個(gè)合并后的HyperLogLog ，然后返回這個(gè)合并 HyperLogLog 的基數(shù)估算值作為命令的結(jié)果（合并得出的HyperLogLog 不會(huì)被儲(chǔ)存，使用之后就會(huì)被刪掉）。

當(dāng)命令作用于單個(gè) HyperLogLog 時(shí)， 復(fù)雜度為 O(1) ， 并且具有非常低的平均常數(shù)時(shí)間。

當(dāng)命令作用于多個(gè) HyperLogLog 時(shí)， 復(fù)雜度為 O(N) ，并且常數(shù)時(shí)間也比處理單個(gè) HyperLogLog 時(shí)要大得多。

PFADD 和 PFCOUNT 的使用示例

redis>PFADD unique::ip::counter'192.168.0.1'(integer)1redis>PFADD unique::ip::counter'127.0.0.1'(integer)1redis>PFADD unique::ip::counter'255.255.255.255'(integer)1redis>PFCOUNT unique::ip::counter(integer)3

?

?

合并多個(gè) HyperLogLog

3、PFMERGE destkey sourcekey [sourcekey …]

將多個(gè) HyperLogLog 合并為一個(gè) HyperLogLog ，合并后的 HyperLogLog 的基數(shù)估算值是通過對所有給定 HyperLogLog 進(jìn)行并集計(jì)算得出的。

PFMERGE 的使用示例

redis> PFADD str1"apple""banana""cherry"(integer)1redis> PFCOUNT str1 (integer)3redis> PFADD str2"apple""cherry""durian""mongo"(integer)1redis> PFCOUNT str2 (integer)4redis> PFMERGE str1&2str1 str2 OK redis> PFCOUNT str1&2(integer)5Hyperloglog算法淺說

這個(gè)算法的目的：比如給你一個(gè)數(shù)組，int a[]={1,1,2,6,9,8,5,4,1,2}，則這個(gè)數(shù)組里一共有十個(gè)元素，其中distinct的數(shù)一共有7個(gè)，它們是1,2,4,5,6,8,9。

這個(gè)算法就是判斷輸入流中互不相同的元素一共有多少個(gè)。這個(gè)算法是概率算法，但是它的精確度很高。

該算法出自論文《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》，下載鏈接：。具體論文的理論推導(dǎo)不詳細(xì)介紹，簡述下其思想核心。

在理想狀態(tài)下，將一堆數(shù)據(jù)hash至[0,1]，每兩點(diǎn)距離相等，1/間距即可得出這堆數(shù)據(jù)的基數(shù)。然而實(shí)際情況往往不能如愿，只能通過一些修正不斷的逼近這個(gè)實(shí)際的基數(shù)。實(shí)際采用的方式一是分桶，二是取kmax。分桶將數(shù)據(jù)分為m組，每組取第k個(gè)位置的值，所有組中得到最大的kmax，(k-1)/kmax得到估計(jì)的基數(shù)。

HLL算法的另一個(gè)主觀上的理解可以用拋硬幣的方式來理解。以當(dāng)硬幣拋出反面為一次過程，當(dāng)你拋n次硬幣全為正面的概率為1/2^n。當(dāng)你經(jīng)歷過k(k很大時(shí))次這樣的過程，硬幣不出現(xiàn)反面的概率基本為0。假設(shè)反面為1，正面為0，每拋一次記錄1或者0，當(dāng)記錄上顯示為0000000…001時(shí)，這種可以歸結(jié)為小概率事件，基本不會(huì)發(fā)生。轉(zhuǎn)換到基數(shù)的想法就是，可以通過第一個(gè)1出現(xiàn)前0的個(gè)數(shù)n來統(tǒng)計(jì)基數(shù)，基數(shù)大致為2^(n+1)時(shí)。硬幣當(dāng)中可以統(tǒng)計(jì)為(1/2*1+1/4*2+1/8*3…)，大致可以這么去想。

我們首先需要以下幾個(gè)輔助函數(shù)或者數(shù)據(jù)

1、int hash(type input);//將輸入的元素hash成一個(gè)32bit的整數(shù)，輸入可能是整數(shù)，也可能是字符串，甚至是結(jié)構(gòu)體，etc

2、unsigned int position(int input);//返回input的二進(jìn)制表示中，從左往右數(shù)，第一個(gè)1出現(xiàn)的位置，比如

position(1000000100000111110)=1position(0001111000011100000)=4position(000000)=7

3、m=2^b,其中b在[4,16]之間

4、幾個(gè)常數(shù)

constdoublea16=0.673constdoublea32=0.697constdoublea64=0.709constdoubleam=0.7213/(1+1.079/m) (m>=128)

有了這四個(gè)準(zhǔn)備之后，我們就可以開始用hyperloglog來實(shí)現(xiàn)計(jì)數(shù)了：m=2^b個(gè)計(jì)數(shù)器，M[1]到M[m]都初始化為0

for(v=input) {x=hash(v); j=1+(binary) w=x(b+1)x(b+2)....x32 M[j]=max(M[j],position(w)); } res=am*m^2*S(1,m,2^(-M[j]))