如果要统计一篇文章的阅读量,可以直接使用复述的增加指令来完成。如果要求阅读量必须按用户去重,那就可以使用组来记录阅读了这篇文章的所有用户id,获取组集合的长度就是去重阅读量。但是如果爆款文章阅读量太大,将会浪费太多存储空间。这时候我们就要使用复述,提供的HyperLogLog数据结构来代替集,它只会占用最多12 k的存储空间就可以完成海量的去重统计。但是它牺牲了准确度,它是模糊计数,误差率约为0.81%。
那么有没有一种不怎么浪费空间的精确计数方法呢?我们首先想到的就是位图,可以使用位图的一个位来表示一个用户id。如果一个用户id是32字节,那么使用位图就只需要占用1/256的空间就可以完成精确计数。但是如何将用户id映射到位图的位置呢?如果用户id是连续的整数这很好办,但是通常用户系统的用户id并不是整数,而是字符串或者是有一定随机性的大整数。
我们可以强行给每个用户id赋予一个整数序列,然后将用户id和整数的对应关系存在复述中。
这里你也许会提出疑问,你说是为了节省空间,这里存储用户id和整数的映射关系就不浪费空间了么?这个问题提的很好,但是同时我们也要看到这个映射关系是可以复用的,它可以统计所有文章的阅读量,还可以统计签到用户的日活,月活,还可以用在很多其它的需要用户去重的统计场合中。所谓“功在当代,利在千秋”就是这个意思。
有了这个映射关系,我们就很容易构造出每一篇文章的阅读打点位图,来一个用户,就将相应位图中相应的位置为一。如果位从0变成1,那么就可以给阅读数加1。这样就可以很方便的获得文章的阅读数。
而且我们还可以动态计算阅读了两篇文章的公共用户量有多少?将两个位图做一下,计算,然后统计位图中第一位的个数。同样,还可以有或计算,XOR计算等等都是可行的。
问题又来了!复述的位图是密集位图,什么意思呢?如果有一个很大的位图,它只有最后一个位是1,其它都是零,这个位图还是会占用全部的内存空间,这就不是一般的浪费了。你可以想象大部分文章的阅读量都不大,但是它们的占用空间却是很接近的,和哪些爆款文章占据的内存差不多。
看来这个方案行不通,我们需要想想其它方案!这时咆哮位图(RoaringBitmap)来了。
它将整个大位图进行了分块,如果整个块都是零,那么这整个块就不用存了。但是如果位1比较分散,每个块里面都有1,虽然单个块里的1很少,这样只进行分块还是不够的,那该怎么办呢?我们再想想,对于单个块,是不是可以继续优化?如果单个块内部位1个数量很少,我们可以只存储所有1位的块内偏移量(整数),也就是存一个整数列表,那么块内的存储也可以降下来。这就是单个块位图的稀疏存储形式,存储偏移量整数列表。只有单块内的1位超过了一个阈值,才会一次性将稀疏存储转换为密集存储。
咆哮位图除了可以大幅节约空间之外,还会降低,或者等位运算的计算效率。以前需要计算整个位图,现在只需要计算部分块。如果块内非常稀疏,那么只需要对这些小整数列表进行集合的,或运算,如是计算量还能继续减轻。
这里既不是用空间换时间,也没有用时间换空间,而是用逻辑的复杂度同时换取了空间和时间。
咆哮位图的位长最大为2 ^ 32,对应的空间为512(普通位图),位偏移被分割成高16位和低16位,高16位表示块偏移,低16位表示块内位置,单个块可以表达64 k的位长,也就是8 k字节。最多会有64 k个块。现代处理器的L1缓存普遍要大于8 k,这样可以保证单个块都可以全部放入L1缓存,可以显著提升性能。
如果单个块所有的位全是零,那么它就不需要存储。具体某个块是否存在也可以是用位图来表达,当块很少时,用整数列表表示,当块多了就可以转换成普通位图。整数列表占用的空间少,它还有类似于ArrayList的动态扩容机制避免反复扩容复制数组内容。当列表中的数字超出4096个时,会立即转变成普通位图。
