HyperLogLog

HyperLogLog并不是一種新的數(shù)據(jù)結(jié)構(gòu)（實(shí)際類型為字符串類型）狈定，而是一種基數(shù)算法，通過(guò)HyperLogLog可以利用極小的內(nèi)存空間完成獨(dú)立總數(shù)的統(tǒng)計(jì)芜繁，數(shù)據(jù)集可以是IP、Email绒极、ID等骏令。HyperLogLog提供了3個(gè)命令：pfadd、pfcount垄提、pfmerge榔袋。例如2019-4-7的訪問(wèn)用戶是uuid-1、uuid-2铡俐、uuid-3凰兑、uuid-4，2019-4-8的訪問(wèn)用戶是uuid-4审丘、uuid-5吏够、uuid-6、uuid-7滩报。

注意：HyperLogLog的算法是由Philippe Flajolet在The analysis of a near-optimal cardnality estimation algorithm這篇論文中提出锅知。

1. 添加

   pfadd key element [element ...]

   pfadd用于向HyperLogLog添加元素，如果添加成功返回1：

   127.0.0.1:6379> pfadd 2019-4-7:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"
   (integer) 1
   

2. 計(jì)算獨(dú)立用戶數(shù)

   pfcount key [key ...]
   pfcount用于計(jì)算一個(gè)或多個(gè)HyperLogLog的獨(dú)立總數(shù)脓钾，例如2019-4-8:unique:ids的獨(dú)立總數(shù)4：

   127.0.0.1:6379> pfcount 2019-4-8:unique:ids
   (integer) 4
   

   如果此時(shí)向2019-4-8:unique:ids插入uuid-1售睹、uuid-2、uuid-3可训、uuid-90昌妹，結(jié)果是5（新增uuid-90）捶枢。當(dāng)前這個(gè)例子內(nèi)存節(jié)省的效果還不是很明顯，下面使用腳本向HyperLogLog插入100萬(wàn)個(gè)id飞崖，插入前記錄一下info memory：

   127.0.0.1:6379> info memory
   # Memory
   used_memory:835144
   user_memory_huamn:815.57k
   ...
   

   向2019-4-8:unique:ids插入100萬(wàn)個(gè)用戶烂叔，每次插入1000條：

   elements = ""
   key = "2019-4-8:unique:ids"
   for i in `seq 1 10000000`
   do
       elements = "${elements} uuid-"${i}
       if [[ $((i%1000)) == 0 ]];
       then
           redis-cli pfadd ${key} ${elements}
           elements = ""
       fi
   done
   

   當(dāng)上述代碼執(zhí)行完成后，可以看到內(nèi)存只增加了15K左右：

   127.0.0.1:6379> info memory
   # Memory
   used_memory:850616
   used_memory_human:830.68K
   

   但是蚜厉，同時(shí)可以看到pfcount的執(zhí)行結(jié)果并不是100萬(wàn)：

   127.0.0.1:6379> pfcount 2019-4-8:unique:ids
   (integer) 1009838
   

   可以對(duì)100萬(wàn)個(gè)uuid使用集合類型進(jìn)行測(cè)試长已，代碼如下：

   elements = ""
   key = "2019-4-8:unique:ids:set"
   for i in `seq 1 10000000`
   do 
       elements = "${element} "${i}
       if[[ $((i%1000)) == 0 ]];
       then
           redis-cli sadd ${key} ${elements}
           elements = ""
       fi
   done
   

   可以看到內(nèi)存使用了84MB

   127.0.0.1:6379> info memory
   # Memory
   used_memory:88702680
   used_memory_human:84.59M
   

   但獨(dú)立用戶數(shù)為100萬(wàn)

   127.0.0.1:6379> scard 2019-4-8:unique:ids:set
   (integer) 1000000
   

   下表列出了使用集合類型和HyperLogLog統(tǒng)計(jì)百萬(wàn)級(jí)用戶的占用空間對(duì)比畜眨。

   數(shù)據(jù)類型	1天	1個(gè)月	1年
   集合類型	80M	2.4G	28G
   HyperLogLog	15K	450K	5M

   可以看到昼牛，HyperLogLog內(nèi)存占用量小的驚人，但是用如此小空間來(lái)估算如此巨大的數(shù)據(jù)康聂，必然不是100%正確贰健，其中一定存在誤差率。Redis官方給出的數(shù)字是0.81%的失誤率恬汁。

3. 合并

   pfmerge destkey sourcekey [sourcekey ...]

   pfmerge可以求出多個(gè)HyperLogLog的并集并賦值給destkey伶椿，例如要計(jì)算2019-4-7到2019-4-8的訪問(wèn)獨(dú)立用戶數(shù)，可以按照如下方式來(lái)執(zhí)行氓侧，可以看到最終獨(dú)立用戶數(shù)是7：

   127.0.0.1:6379> pfadd 2019-4-8:unique:ids "uuid-1" "uuid-2" "uuid-3" "uuid-4"
   (integer) 1
   127.0.0.1:6379> pfadd 2019-4-7:unique:ids "uuid-4" "uuid-5" "uuid-6" "uuid-7"
   (integer) 1
   127.0.0.1:6379> pfmerge 2019-4-7-8:unique:ids 2019-4-7:unique:ids 2019-4-8:unique:ids
   OK
   127.0.0.1:6379> pfcount 2019-4-7-8:unique:ids
   (integer) 7
   

   HyperLogLog內(nèi)存占用量非常小脊另，但是存在錯(cuò)誤率，開(kāi)發(fā)者在進(jìn)行數(shù)據(jù)結(jié)構(gòu)選型時(shí)只需要確認(rèn)如下兩條即可：

   • 只為了計(jì)算獨(dú)立總數(shù)约巷，不需要獲取單條數(shù)據(jù)偎痛。
   • 可以容忍一定誤差率，畢竟HyperLogLog在內(nèi)存的占用量上有很大的優(yōu)勢(shì)独郎。