专栏首页普通程序员如何高效计算DAU

如何高效计算DAU

项目中一直有计算DAU这类的需求,业务开发者往往埋个点,其他是事情就交给数据团队了。

如果自己要做一个这样的计数器怎么做呢?一个朴素的想法是通过hashmap实现,时间复杂度是O(1)。这个方法在计数对象较少的情况下还是不错的,但是如果计数对象很多(比如计算独立访问IP),意味着hashmap的key非常多,内存消耗是非常大。

阅读开源IM软件GoBelieve代码,看到了下面一个函数

这个函数的目的是计算IM的日活用户量,采用了redis一个命令“PFADD”。赶紧查一下帮助文档,看到下面一段执行记录

这个方法用于计算日活DAU太合适不过。仔细查看Redis文档,HyperLogLog结构下支持三个方法,PFADD,PFCOUNT,PFMERGE。通过这几个方案,能够很容易实现计数类的一些需求。

HyperLogLog是什么?

HyperLogLog是一种基数估计算法。在理解技术估计算法之前,我们需要先知道基数计数法的概念(有没有感觉读书的时候似曾相识)。

基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数,例如统计某个网站的UV,或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。 要实现基数计数,最简单的做法是记录集合中所有不重复的元素集合Su,当新来一个元素xi,若Su中不包含元素xi,则将xi加入Su,否则不加入,计数值就是Su的元素数量。这种做法存在两个问题:

1、当统计的数据量变大时,相应的存储内存也会线性增长(文章开始用hashmap技术的办法就有这个问题)

2、当集合Su变大,判断其是否包含新加入元素xi的成本变大

大数据量背景下,要实现基数计数,首先需要确定存储统计数据的方案,以及如何根据存储的数据计算基数值;另外还有一些场景下需要融合多个独立统计的基数值,例如对一个网站分别统计了三天的UV,现在需要知道这三天的UV总量是多少,怎么融合多个统计值。

除了hashmap,另一个容易被想到的办法是位图BitMap。位图可以快速、准确地获取一个给定输入的基数。位图的基本思想是使用哈希函数把数据集映射到一个bit位,每个输入元素与bit位是一一对应。这样Hash将没有产生碰撞冲突,并减少需要计算每个元素映射到1个bit的空间。位图大大节省了空间,但是当统计很高的基数或非常大的不同的数据集,它的空间开销依然较大,同时可能带来稀疏位图等问题。

技术估计算法(HyperLogLog是其中一种)就是来解决海量数据技术难题的!基数估计算法使用准确性换取空间。

为了说明这一点,这里引用《Big Data Counting: How To Count A Billion Distinct Objects Using Only 1.5K》文章的实验数据。

文章用三种不同的计算方法统计所有莎士比亚作品中不同单词的数量。请注意,我们的输入数据集增加了额外的数据以致比问题的参考基数更高。这三种技术是:Java HashSet、Linear Probabilistic Counter以及一个Hyper LogLog Counter。结果如下:

该表显示,Hyper LogLog Counter统计这些单词只用了512 bytes,而误差在3%以内。相比之下,HashMap的计数准确度最高,但需要近10MB的空间,基数估计非常有用!在实际应用中,某些统计的准确性并不是很重要。在大多数网络规模和网络计算的情况下,用概率计数器会节省巨大的空间。

HyperLogLog的算法原理可以搜索《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》这篇文章。下边截个算法具体实现过程

算法看不懂没关系(很多做AI的人也不清楚反向传播算法),重要的是要知道怎么正确使用Redis中实现的HyperLogLog算法。

redis中实现的HyperLogLog,只需要12K内存,在标准误差0.81%的前提下,能够统计2^64个数据!

所以不要担心统计数据太大,redis内存不够用,放心使用就好。

本文分享自微信公众号 - 普通程序员(farmerbrag),作者:封宇

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 事务注解(@Transactional)引起的数据覆盖故障

    最近组织团队内技术培训,刘聪为分享的一个跟事务和写数据库相关的case(bug)很有代表性。用事务,要小心!

    普通程序员
  • IM系统服务端消息加解密方案

    端到端加密是最安全的,只有聊天双方知道具体是什么消息,传输链路和消息服务器端都不知道消息内容。但是端到端加密在有些场景不适用,比如大规模群聊就不太好办。另外基于...

    普通程序员
  • 二百元成本单网站每天爬取百万量级数据的方法

    在网络爬虫抓取信息的过程中,如果抓取频率高过了网站设置的阀值,会被禁止访问。通常,网站的反爬虫机制依据IP来标识爬虫。

    普通程序员
  • 国内常用静态资源 CDN 公共库加速服务

    当然,用别人的 CDN 都是不保险的,所以建议在 CDN 读取失败的时候从自己服务器提供

    剑行者
  • 安永发布全球金融科技应用指数报告 中国领跑全球!

    近日,全球知名咨询机构安永发布《2017年金融科技应用指数报告》(EY FinTech Adoption Index 2017》,对全球20个主要经济体的金融...

    点滴科技资讯
  • Protocol Buffers

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    于小勇
  • 剑指Offer-二维数组中的查找

    package Array; /** * 二维数组中的查找 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。...

    武培轩
  • 专用车制造业巨头“云化”实录

    中集车辆(集团)有限公司(以下简称:中集车辆集团),是在原深圳中集重型机械有限公司的基础上,于2003年获国家商务部批准成立的。中集车辆集团是世界最大的集装箱制...

    安畅
  • Angularjs中UI Router超级详细的教程{{上}}

    这篇文章主要介绍了Angularjs中UI Router全攻略,涉及到angularjs ui router的基本用法,需要的朋友参考下吧 首先给大家介绍ang...

    前朝楚水
  • 打造前端MAC工作站(九)配置XAMMP,打造apache+php+mysql本地服务器

    打造前端MAC工作站(九)配置XAMMP,打造apache+php+mysql本地服务器 前言 虽然我们是前端工程师,但是以php+mysql为开发语言和数据库...

    FungLeo

扫码关注云+社区

领取腾讯云代金券