vuexvuex12-12 04:45

活跃用户(UV)统计方法

why

面对海量的请求,如何计算UV?

How

一、基于Bitmap

Bitmap是一串连续的2进制数字(0或1),每一位所在的位置为偏移(offset),在bitmap上可执行AND,OR,XOR以及其它位操作。

为了统计今日登录的用户数,我们建立了一个bitmap,每一位标识一个用户ID。当某个用户访问我们的网页或执行了某个操作,就在bitmap中把标识此用户的位置为1。在Redis中获取此bitmap的key值是通过用户执行操作的类型和时间戳获得的。


image.png

这个简单的例子中,每次用户登录时会执行一次redis.setbit(daily_active_users, user_id, 1)。将bitmap中对应位置的位置为1,时间复杂度是O(1)。统计bitmap结果显示有今天有9个用户登录。Bitmap的key是daily_active_users,它的值是1011110100100101。

因为日活跃用户每天都变化,所以需要每天创建一个新的bitmap。我们简单地把日期添加到key后面,实现了这个功能。例如,要统计某一天有多少个用户至少听了一个音乐app中的一首歌曲,可以把这个bitmap的redis key设计为play:yyyy-mm-dd-hh。当用户听了一首歌曲,我们只是简单地在bitmap中把标识这个用户的位置为1,时间复杂度是O(1)。

二、基于BloomFilter

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

1、初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0:


image.png

2、当来了一个元素 a,进行判断,使用两个哈希函数,计算出该元素对应的Hash值为1和5,然后到Bloom Filter中判断第1位和第5位的值,上面全部为0,因此a不在Bloom Filter内,将 a 添加进去:


image.png

3、随着元素的插入,Bloom filter 中修改的值变多,出现误判的几率也随之变大,当新来一个元素时,满足其在Bloom Filter内的条件,即所有对应位都是 1 ,这样就可能有两种情况,一是这个元素就在集合内,没有发生误判;还有一种情况就是发生误判,出现了哈希碰撞,这个元素本不在集合内。


image.png

4、基于bloom filter的逻辑很简单

判断该请求不在bloom filter里面,把该用户加入bloom filter 同时UV++

5、其他方法
参考文章https://blog.csdn.net/firenet1/article/details/77247649

官场书屋二维码

小额赞赏

000
评论