Hegel2011的博客

读书 - 工作 - 生活 - 笔记

独一无二者计数问题( Count-distinct)

最近分析一个大日志文件,9亿条记录近300GB的数据。终于体会到一点大数据处理的意思。

之前根据日志,统计出里面各个域名的pv还算简单。为了开发方便,利用了Redis,开10个java线程,分别扫描不同的行,并把domain做关键字写入redis并不断计数,最后从中读出全部的值并排序。 整个过程主要开销在扫描方面。此时瓶颈出在redis上,基本上5个java线程可以把redis的cpu性能榨干。

9亿条数据分析出来了七十几万个域名,而redis处理70w个key,消耗的内存在100MB以内,所以整个运行跑上几个小时就能得到想要的结果了。

但是,客户进一步提出要分析每个domain下独立访问的用户数量是多少。这下子可就犯难了。 因为按照传统的做法,碰到需要计算独立用户的需求会建立一个集合,然后把标识往里push,最后获取一下这个set的大小,就可以得到独立用户的数量。 然而,如果对70w个域名都分别建立一张访问用户的set,则存储的开销实在太大。这意味着key-value的数量将是70w的几千甚至几万倍。 然后看了一下redis新增加的数据结构类型,发现redis中的hyperloglogs是为此种任务而生的。

HyperLogLog和count-distinct problem

建立一个集合并把数据放入,最后计算集合的大小是一种精确的求值方式。而HyperLogLog则是一种会损失一些细节但可以获得很好的近似值的估算方式。

这种算法的核心思想就是MD5+Bitmap。通过某种Hash算法,比如MD5,可以把千变万化的取值收敛成有限的值,而因为这些值也很大,所以可以认为重复的比例会很低。然后,应用Bitmap来表示这些映射结果是否已存在,最后就是计算这个Bitmap中已存在值的数量。尽管损失一些细节,也不是完全精确,但结果是足够准确了。而经过Hash的收敛,再经过Bitmap的收敛,对空间的需求就会变得少了许多许多,也就可以应用于更多关键字的计数。

以我自己对某个域名按两种方式都运行后得到的结果,分别对比如下:

精确的:1687,估计的:1685
精确的:93869,估计的:94097
精确的:305084,估计的:305281

而这种方式最大的好处,自然就是对count-distinct这类问题统计起来毫无压力了,同时得到的数据也足够好用了。

Included file 'twitter_sharing.html' not found in _includes directory