Redis-HyperLogLog算法和使用

Published: 14 Jun 2020 Category: redis

一、HyperLogLog算法

HyperLogLog算法经常在数据库中被用来统计某一字段的Distinct Value(下文简称DV),比如Redis的HyperLogLog结构。

HyperLogLog算法可以使用固定大小的字节计算任意大小的DV,本文先介绍该算法的原理,然后通过剖析stream-lib(一个Java实现的实时计算库)对此算法的实现来进一步理解该算法。

1.1 一些概念

基数就是指一个集合中不同值的数目,比如[a,b,c,d]的基数就是4,[a,b,c,d,a]的基数还是4,因为a重复了一个,不算。基数也可以称之为Distinct Value,简称DV。下文中可能有时候称呼为基数,有时候称之为DV,但都是同一个意思。HyperLogLog算法就是用来计算基数的

1.2 基本原理

在理想状态下,将一堆数据hash至[0,1],每两点距离相等,1/间距 即可得出这堆数据的基数。然而实际情况往往不能如愿,只能通过一些修正不断的逼近这个实际的基数。实际采用的方式一是分桶,二是取kmax。分桶将数据分为m组,每组取第k个位置的值,所有组中得到最大的kmax,(k-1)/kmax得到估计的基数。

HLL算法的另一个主观上的理解可以用抛硬币的方式来理解。以当硬币抛出反面为一次过程,当你抛n次硬币全为正面的概率为1/2^n。当你经历过k(k很大时)次这样的过程,硬币不出现反面的概率基本为0。假设反面为1,正面为0,每抛一次记录1或者0,当记录上显示为0000000…001时,这种可以归结为小概率事件,基本不会发生。转换到基数的想法就是,可以通过第一个1出现前0的个数n来统计基数,基数大致为2^(n+1)时。硬币当中可以统计为(1/2*1+1/4*2+1/8*3…),大致可以这么去想。

在 Redis 中,HyperLogLog设置为:m=16834,p=6,L=16834 * 6。占用内存为=16834 * 6 / 8 / 1024 = 12K

二、用法

From https://www.cnblogs.com/linguanh/p/10460421.html

统计 APP或网页 的一个页面,每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次。

如果用HashMap,会导致数据量很大。

除此之外还有B+ 树,Bitmap 位图,以及HyperLogLog。

在一定条件允许下,如果允许统计在巨量数据面前的误差率在可接受的范围内,1000万浏览量允许最终统计出少了一两万这样子,那么就可以采用HyperLogLog算法来解决上面的计数类似问题。

HyperLogLog,下面简称为HLL,它是 LogLog 算法的升级版(HLL用调和平均数代替LL的平均数算法),作用是能够能够使用极少的内存来统计巨量的数据,虽然提供的去重计数是不精确的。

REF

https://www.jianshu.com/p/55defda6dcd2
https://baijiahao.baidu.com/s?id=1611726471431642966&wfr=spider&for=pc