• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

redis源码阅读之hyperloglog

redis 海叔叔 21小时前 4次浏览 已收录 0个评论

hyperloglog是redis用来实现基值估算的。

这边理解就要分两头了

概念 解释
基值 学过数学的朋友们都应该对这个概念不陌生吧,就是一个集合当中包含的不同元素的个数
估算 估算就比较简单了,就是给出的值没有那么精确。

为什么要用估算呢?就是为了防止在数据量过大,但统计时只关心量,而不要求记录所有元素的所有数据的时候用的。比如算个什么日活跃用户这种,这时候要算的数据具有如下两个特点:1)去重;2)不需要记录具体的用户信息。这个时候就是我们hyperloglog登场的时候咯~~
hyperloglog在使用内存方面是非常节省的,它对每个key仅花费12KB(16384 个 6-bit registers)来存储,当一个元素到来时,它先是进行哈希,然后将其分配到16384个register当中的一个。
至于怎么估算,这里就要用到register当中的数据了。首先,register当中存放的是分配到当前register的值当中,二进制表示,从最后一位向前数,连续0的个数的最大值的对数(以2为底)。这里的数学理论依据是:一堆数,若其中二进制表示,从最后一位向前数,连续0的个数的最大值为k,那么这一堆数的基大概为2k个。但是随着数据量的不断增大,2k和2k+1的差距也会越来越大,redis就巧妙的采取了将各个桶中的基进行调和求平均的方法来得到估算值,这期间还会用到修正因子神马的,这里就不细究了。

这里还要再说一下hyperloglog的具体存储方式,当数据量较大的时候,恒定每个key占用12KB,这种方式叫密集存储方式,其内存排列如下:

这里需要注意的是当取某一个register的内容时,由于其实6bit对齐,但是一个字节是8bit这里需要考虑数据位的提取问题。

但是如果数据量比较小的时候,仍旧采用这种方式就会造成一定的浪费,redis的解决方法就是采取最多对两个字节进行编码的稀疏存储的方式来表示所存数据,具体如下, 下表中的数据表示为二进制:

编码方式 解释(current register included)
ZERO: 00xxxxxx(单字节) 连续的N=xxxxxx+1个register为空,最多表示64个空register
XZERO:
01xxxxxx-yyyyyyyy(双字节)
连续的N=00xxxxxx-yyyyyyyy + 1个register均为空,最多表示16384个register为空,即hyperloglog的初始状态
VAL: 1vvvvvxx(单字节) 连续M=xx+1个register的值为vvvvv+1

当使用稀疏表示,并且表中只有3个非0的register,其位置分别为1000,1020,1021的时候,其内存表示为

其中前两个字节表示有1000个空register,
第三个字节表示第1001(下标为1000)个register的值为2
第四字节表示后面的19个register为空
第五个字节表示后面连续两个register的值为3
最后两个字节表示后面的register均为空

这样的话,稀疏表示方法的局限也就露出来了,也就是单个register的最大保存值为32,当某一个register的值超过32的时候,会促使redis将其存储结构变为密集型存储。

由于有16384个register,而且基数统计要遍历所有的register,如果每来一个元素就整个遍历一下所有的register,就会显得很不划算,redis是设置了一个64位缓存来缓和这一现象,如果缓存最高位为1,则表示信息已经过期,如果为0,则余下的63位表示调和之后的值,该值只会在请求基数的时候才会重新计算,平时每次在更新register的时候都会将这一缓存的最高位置为1以表示过期。

redis当中使用了hllhdr来存储hyperloglog的相关信息,以便于操作,代码如下:

在函数当中,比较核心的就是计算count和转换这边了,计算count代码如下:

稀疏型存储转换为密集型存储代码如下,逐个遍历字节:


喜欢 (1)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址