专栏首页SmartSi使用Redis Bitmap简单快速实时计算指标

使用Redis Bitmap简单快速实时计算指标

传统上,度量指标一般由批处理作业执行(每小时运行,每天运行等)。Redis 中的 Bitmap 可以允许我们实时计算指标,并且非常节省空间。在1.28亿用户场景中,经典度量指标(如’日活’)在 MacBook Pro上只需不到50毫秒,而且只需要16 MB内存。

1. Bitmap

又可以称之为 Bitset。

Bitmap 或 Bitset 是一个由 0 和 1 构成的数组。在 Bitmap 中每一个 bit 被设置为 0 或 1,数组中的每个位置被称为 offset。AND,OR,XOR等操作符,以及其他位操作都是 Bitmaps 的常用操作。

2. 基数

Bitmap 中 1 的个数称之为基数。我们有一种有效算法来计算基数,例如,在 MacBook Pro 上,在包含10亿位填充90%的 Bitmap 上计算基数耗时 21.1 ms。

3. Redis中的Bitmap

Redis 允许二进制键和二进制值。Bitmap 也是二进制值。将键指定 offset 设置为 0 或 1,setbit(key,offset,value) 操作需要用 O(1) 时间复杂度。

4. 一个简单的例子:每日活跃用户

为了统计今天登录的不同用户,我们创建了一个 Bitmap,其中每个用户都由一个 offset 标识。当用户访问页面或执行操作时,会将表示用户ID的 offset 设置为 1。

在这个简单的例子中,每次用户登录时,我们都会执行:

redis.setbit(daily_active_users,user_id,1)

这会将 daily_active_users Bitmap 键对应 offset 设置为1。这是一个 O(1) 时间复杂度操作。对此 Bitmap 进行基数统计会统计出今天一共登录了 9 个用户。键是 daily_active_users,值为 1011110100100101。

当然,由于每天活跃用户每天都会在改变,我们需要一种方法每天创建一个新的 Bitmap。我们只需在 Bitmap 键后面追加一个日期即可。例如,如果我们想要计算某天在音乐应用中播放至少1首歌曲的不同用户,我们可以将键名称设置为 play:yyyy-mm-dd。如果我们想要计算每小时播放至少一首歌曲的用户数量,我们可以将键名称设置为 play:yyyy-mm-dd-hh。为了计算每日指标,只要用户播放歌曲,我们就会在 play:yyyy-mm-dd 键中将用户对应的 bit 设置为1。

redis.setbit(play:yyyy-mm-dd, user_id, 1)

今天播放歌曲的不同用户是存储以 play:yyyy-mm-dd 为键的值。要计算每周或每月度量指标,我们可以简单地计算一周或一个月中所有每日 Bitmap 的并集,然后计算结果 Bitmap 的总体基数。

你还可以非常轻松地提取更复杂的指标。例如,11月播放歌曲的会员用户为:

(play:2011-11-01 ∪ play:2011-11-02 ∪...∪play:2011-11-30) ∩ premium:2011-11

5. 使用1.28亿用户进行性能比较

下表显示了针对1.28亿用户在1天,7天和30天计算的比较。通过组合每日 Bitmap 计算7日和30日指标:

周期

耗时 (MS)

每日

50.2

每周

392.0

每月

1624.8

6. 优化

在上面的示例中,我们可以通过在 Redis 中缓存计算的每日,每周,每月计数来优化每周和每月计算。

这是一种非常灵活的方法。缓存的另一个好处是它允许快速群组分析,例如使用手机的每周唯一用户 - 手机用户 Bitmap 与每周活跃用户 Bitmap 的交集。或者,如果我们想要滚动计算过去n天内的唯一用户,那么缓存每日唯一用户的计数会使这变得简单 - 只需从缓存中获取前n-1天并将其与实时每日计数结合起来即可,而这只需要50ms。

7. 示例代码

下面的Java代码片段指定用户操作和日期来计算唯一用户:

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
Jedis redis = new Jedis("localhost");
...
public int uniqueCount(String action, String date) {
  String key = action + ":" + date;
  BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
  return users.cardinality();
}

下面的代码片段计算指定用户操作和日期列表的唯一用户:

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
Jedis redis = new Jedis("localhost");
...
public int uniqueCount(String action, String... dates){
  BitSet all = new BitSet();
  for (String date : dates) {
    String key = action + ":" + date;
    BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
    all.or(users);
  }
  return all.cardinality();
}

英译对照

  • 基数: Population Count

原文:REDIS BITMAPS – FAST, EASY, REALTIME METRICS

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HBase Schema 设计

    HBase 与传统关系数据库(例如MySQL,PostgreSQL,Oracle等)在架构的设计以及为应用程序提供的功能方面有很大的不同。HBase 权衡了其中...

    smartsi
  • Stream 对于流处理技术的谬见

    我们在思考流处理问题上花了很多时间,更酷的是,我们也花了很多时间帮助其他人认识流处理,以及如何在他们的组织里应用流处理来解决数据问题。

    smartsi
  • Flink 动态表的持续查询

    越来越多的公司采用流处理,并将现有的批处理应用迁移到流处理,或者对新的用例采用流处理实现的解决方案。其中许多应用集中在流数据分析上,分析的数据流来自各种源,例如...

    smartsi
  • JVM堆引发swap的情况分析

    虚拟机技术可以使得一个只有1g物理内存的机器可以运行总共需要4g内存的任务,主要方法是通过虚拟内存和物理内存映射来实现的,当物理内存不够用的时候,可以通过swa...

    春哥大魔王
  • 微信车票背后的设计故事

    公交车票,对于现在的我们而言或许稍显陌生,但在回忆里,那曾是一代人的情怀,伴随着共同的成长,伴随时光的逝去,让我们品味一路风景与欢乐,到达人生的每一站。

    鹅厂新鲜事儿
  • 安全编码实践之三:身份验证和会话管理防御

    我一直致力于安全编码实践,并试图尽可能多地学习基本要点。在过去的几年里,我已经意识到一个小小的漏洞在普通人的生活中可能造成的伤害。像WannaCry和Petya...

    Bypass
  • 锵锵话车展:大数据应把产品信息直达每个人

    大数据文摘
  • 轻松学习正则表达式

    转载自:http://www.cnblogs.com/sxwgf/archive/2011/11/17/2252076.html

    颍川
  • 2017 NIPS 哪家强?我们统计了大会发文数量,谷歌和CMU稳居老大

    大数据文摘
  • UAS:大众点评用户行为系统

    随着整个中国互联网下半场的到来,用户红利所剩无几,原来粗放式的发展模式已经行不通,企业的发展越来越趋向于精耕细作。美团的价值观提倡以客户为中心,面对海量的用户行...

    美团技术团队

扫码关注云+社区

领取腾讯云代金券