HyperLogLog

HyperLogLog并不是一種新的數(shù)據(jù)結構（實際類型為字符串類型），而是一種基數(shù)算法，通過HyperLogLog可以利用極小的內存空間完成獨立總數(shù)的統(tǒng)計，數(shù)據(jù)集可以是IP、Email、ID等。HyperLogLog提供了3個命令：pfadd、pfcount、pfmerge。例如2019-4-7的訪問用戶是uuid-1、uuid-2、uuid-3、uuid-4，2019-4-8的訪問用戶是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. 計算獨立用戶數(shù)

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

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

   如果此時向2019-4-8:unique:ids插入uuid-1、uuid-2、uuid-3、uuid-90，結果是5（新增uuid-90）。當前這個例子內存節(jié)省的效果還不是很明顯，下面使用腳本向HyperLogLog插入100萬個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萬個用戶，每次插入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
   

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

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

   但是，同時可以看到pfcount的執(zhí)行結果并不是100萬：

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

   可以對100萬個uuid使用集合類型進行測試，代碼如下：

   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
   

   可以看到內存使用了84MB

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

   但獨立用戶數(shù)為100萬

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

   下表列出了使用集合類型和HyperLogLog統(tǒng)計百萬級用戶的占用空間對比。

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

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

3. 合并

   pfmerge destkey sourcekey [sourcekey ...]

   pfmerge可以求出多個HyperLogLog的并集并賦值給destkey，例如要計算2019-4-7到2019-4-8的訪問獨立用戶數(shù)，可以按照如下方式來執(zhí)行，可以看到最終獨立用戶數(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內存占用量非常小，但是存在錯誤率，開發(fā)者在進行數(shù)據(jù)結構選型時只需要確認如下兩條即可：

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