Redis 实用小技巧—— bitmap 应用之「签到统计」

简介

在上一篇文章《Redis 实用小技巧—— bitmap 应用之「缓存穿透」问题的处理》中,我们了解到了「缓存穿透」的原理以及如何通过「布隆过滤器」来解决这种问题。在接下来的文章中,我们再来讨论一个老生常谈的问题 —— 如何借助 bitmap 解决「签到统计」相关的问题。

话不多说,准备发车~

签到统计

「签到统计」的场景一般如下:

用户在系统中每天都有签到行为,需要统计用户在某一天是否签到,用户在一段时间内的签到天数(比如统计某个自然月的出勤率),某段时间内整体用户签到情况。

以上就是签到统计场景中经常遇到的几种情况。

如果使用 MySQL 存储的话,一方面数据量会比较大,另一方面统计查询的时候,速度会比较慢。

这种场景,我们可以考虑使用 bitmap 实现,毕竟「海量数据」+「存在与否」两大要素都已经满足了。

现在,我们就来看看用 bitmap 如何实现。

实际上,理解了布隆过滤器的原理以后,再来理解签到问题就相对简单的多了(这也是为什么我们把布隆过滤器放到开始讲的原因)。

bitmap 纬度设计

在我看来,「签到统计」的难点在于 bitmap 的设计。这里我们尝试从几个不同的维度来设计 bitmap 。

需要说明的是,我们并没有引导你直接使用哪种「最优」的解决方案,那并不是我们的初衷。我们会在一步步讨论中,「探索」出一种看上去更「合理」的方案。
针对签到这种场景,我们可以从三个维度来设计 bitmap 。

时间纬度

我们可以按照日期来设计 bitmap 的 key ,如:USER_SIGN:20230615,以用户 ID 作为偏移量。如果 ID 为 1000 的用户在 2023年6月15日签到过的话,则会执行以下操作:

> SETBIT USER_SIGN:20230615 1000 1

这样设计的话,我们可以很方便地统计用户在某一天是否签到,如下:

> GETBIT USER_SIGN:20230615 1000 

或者统计某一天有多少用户签到,如下:

> BITCOUNT USER_SIGN:20230615

但是不好的地方是,每一天都需要一张 bitmap 来存储,一年则需要 365 张 bitmap 。一张 bitmap 按 512 MB 算的话(假设最高位不幸被占用),一年的存储需要分配 186880 MB ,即 18 GB 之多。

而且,当我需要统计某个人在某段时间内的签到情况的时候,会变的比较复杂:需要依次获取区间内每一张 bitmap 表的签到情况,然后再通过代码逻辑来处理。

用户纬度

我们还可以按照用户的纬度来设计 bitmap 的 key ,如:USER_SIGN:1000,以签到日期作为偏移量。

这里我们可以设定一个初始日期,然后以统计日期距离初始日期的差值作为偏移量。假设初始统计日期是2023年6月1日,那么 ID 为 1000 的用户在2023年6月14日签到过的话,则会执行以下操作:

> SETBIT USER_SIGN:1000 13 1

这样做的好处是,我们可以很方便地统计用户在某一天是否签到,如下(判断 ID 为 1000 在2023年6月14日是否签到):

> GETBIT USER_SIGN:1000 13 

以及用户在某段时间内的签到的情况,如下(统计 ID 为 1000 的用户在2023年6月1日到2023年6月14日之间的签到天数):

> BITCOUNT USER_SIGN:1000 0 13

但是不好的地方是,每个用户都需要一张 bitmap 来存储,如果有 1000 万用户的话,则需要 1000 万张 bitmap 来存储,而如果一张 bitmap 按 512 MB 算的话(尽管现实中等不到那一天),总共需要分配 200000 * 512 MB 的空间,具体是多少就不计算了,相信那已经超出了 Redis 的承受范围。

而且,当我们需要统计某一天内所有签到的人数时,也是比较麻烦的。需要遍历所有用户在某一天的签到情况,20 万用户遍历一遍,想想就觉得恐怖。

混合纬度

通过「时间维度」和「用户维度」来设计 bitmap ,我们发现各有利弊(尽管我们的担心在实际场景中可能不会遇到),那能不能把两者结合一下,直接用一张 bitmap 表搞定呢?

我们先来看看在内存分配方面能不能满足。一张 bitmap 表能够存储 2^32 - 1位数据,大概 42.9 亿的数据。假设我们有 1000 万用户的话,按用户每天都签到来统计,一年的数据量大概在 36.5 亿的数据,也是基本可以满足的(如果不满足的话,我们可以缩短 bitmap 的统计周期,比如半年存一张 bitmap )。

接下来,我们看看如何「分配空间」的问题 —— 这是一个需要花时间考虑的问题。

我们先来个简单暴力点的设计。

假设我们按照 1000 万用户的上限来设计,我们将 0 ~ 1000万 - 1 的位置记录全部用户在初始化日期(以2023年6月1日为例)的签到,1000万 ~ 2000万 - 1 的位置用来记录全部用户 2023年6月2日的的签到。以此类推,按照我们的预算,在一张 bitmap 上分配一年的空间也是足够的。如下图所示:

接下来我们要做的就是存储了。

当 ID 为 1000 的用户在2023年6月15日进行签到时,我们需要做四件事:

  1. 确定日期所在区间的起始偏移量位置。签到日期是2023年6月15日,则该日期所在的区间相对于起始日期(2023年6月1日)的偏移量为 14。
  2. 确定用户 ID 在日期所在区间内的偏移量。假设用户的 ID 为 1000,则用户在日期所在区间内的偏移量为 1000。
  3. 确定用户 ID 在整体区间的偏移量。计算公式为:日期区间偏移量 * 日期区间大小 + 用户在日期区间内的偏移量。这里计算结果为:14 * 1000万 + 1000 = 140001000 。
  4. 设置 bitmap 值:SETBIT USER_SIGN 140001000 1

存储完数据以后,接下来就开始考虑如何实现我们的统计需求了。这里我们看看前两个维度中遇到的统计需求,能不能一一解决。

首先判断用户在某一天是否签到。这里我们根据统计日期的偏移量和用户的 ID 计算出用户在这一天签到对应的偏移量(存储步骤中已经介绍),然后通过 GITBIT 就可以判断了。如下:

> GETBIT USER_SIGN 140001000

然后是某一天有多少用户签到的场景。我们根据统计日期计算出该日期对应的偏移量的起始和截止位置,然后通过 BITCOUNT 命令即可得到结果:

> BITCOUNT key [统计日期起始偏移量] [统计日期截止偏移量]

接下来,让我们统计用户在一段时间内的签到情况。这种情况稍微有点复杂了,不过还算 OK 。

首先我们需要计算出用户在这段时间内所有的偏移量情况。这里我们通过公式,很容易就可以求出来(如果数据量多的话,就多求一会)。

接下来,我们需要查询出这些偏移量位置上 bit 位的设置情况。

你可以使用 GETBIT 的方式分多次查询。当然,如果数据量如果在可控范围内的话(不超过 Redis 单次请求的载荷),建议你使用 PIPELINE 的方式进行查询,如下(以 laravel 实现为例):

/**
 * 混合维度统计签到
 *
 * @param array $offsets 偏移量列表
 * @return mixed
 */
public function signCountByMix(array $offsets)
{
    return $this->client->pipeline(function ($redis) use ($offsets) {
        foreach ($offsets as $offset) {
            $redis->getbit($this->bucket, $offset);
        }
    });
}

这样,我们就能够拿到我们想要的结果了。

这种方案看似已经解决了「时间维度」和「用户维度」不易解决的问题,但是并不算理想。因为这种按假定上限「平均分配」的方法很容易受到上限的限制:比如我们的用户量突然突破了 1000 万该怎么办?这样原有的已经定好的规则就被打破了。这显然不是一个「合理」的方案。

其实,只要我们把日期这个区间做成「动态浮动」的空间,这个问题就迎刃而解了。那该怎么「浮动」呢?

我们可以在每次初始化日期区间的时候,顺便记录下当前日期的最大的偏移量位置。当用户签到时,我们会拿用户 ID 计算出用户在当前日期区间内的偏移量位置,然后和记录的截止偏移量位置进行比较,如果超出了记录的值,则进行替换。这样,在次日进行统计时,会以上一次记录的截止偏移量位置作为次日的起始偏移量的位置,重复之前的过程。如下图所示:

这样做,我们的日期区间分布就成了「动态浮动」的了,而且比起之前的方案来,不仅灵活,能表示的范围也更大了。

不过,因为现在日期区间的边界是保存在记录中的了,所以在计算具体的偏移量时,我们需要先从记录中把所有日期的偏移量位置查出来,然后进行计算。我们用 Hash 来存储这些信息,用日期来作 Field ,每天保存当天最大的偏移量(即最大的用户),这样每次统计的时候,直接 HMGET 获取到所有日期的偏移量信息,也不会有什么压力。

这样设计,看似存储上「更为合理」了,但是实现逻辑上却变的复杂了。

比如,我们要判断用户在某一天是否签到:我们需要先计算出用户在这一天的偏移量,计算思路与优化前的思路一样。不同的是,这里我们取日期的偏移量的时候,需要从 Hash 中进行获取。

计算用户在某段时间内的签到情况的时候,也需要先通过程序计算出用户在这段时间内具体的偏移量,然后再进行批量获取。

如果需要统计某一天内所有的签到用户数,我们只需要拿到这一天的起始(上一条记录的截止偏移量)和截止偏移量,然后进行 BITCOUNT 运算即可。

到这里,看似所有的问题都得到了完美的解决。难道这就是「最合理」的方案了么?

其实不然。

在日常开发中,还有一种常见的统计场景:统计在某段时间内连续签到的用户。特别是对于经常玩游戏的小伙伴肯定不陌生 ——「连续签到七天,大奖等你来拿」,是不是很熟悉?

对于这种场景,我们这种方案貌似就不那么「灵通」了 —— 因为我们在一张 bitmap 上通过偏移量即表达了时间,又表达了用户。我们在解决统计的问题时,是借助了命令和程序来处理的。这对于可控的区间统计是可以接受的,但是这里我们需要遍历每一个 bit 位来获取用户的签到信息,然后通过运算得到最终的结果。这笔开销无疑还是很大的。

额。。。难道忙活了半天,白忙活了么?

返璞归真

其实,我们在一步步升级我们方案的过程中,都是以理论作为升级的「标尺」。但是理想的风花雪月,总要回归现实的锅碗瓢盆。

过日子,讲究的是「实际」。

现在,我们回头来看「时间维度」这个设计。

在这个维度的讨论中,我们列举了两条限制因素:存储空间和时间区间内用户签到的统计。

我们当时是按照 bitmap 最大的内存开销来假设的,即 512 MB 。这个空间能存储大约 42.9 亿的数据量,假设我们的用户量有1亿的话,实际分配的空间只有 12 MB 左右,一年占用的空间大概 4.3 GB 左右。虽然也很大,但是这种签到数据,我们可能不需要保存这么久,所以实际占用的空间可能会更小。

针对另一个限制条件,如果我们要统计某段时间内,用户的签到情况,通过 pipeline 批量处理的话,开销也不是很大。

关键点来了:现在如果需要统计某段时间内连续签到的用户,在这种方案下就变的简单多了。我们只需要通过 BITOP 进行 AND 的位运算操作就可以了,如下:

> BITOP AND USER_CONTINUAL_SIGN  USER_SIGN:20230601 USER_SIGN:20230602 [USER_SIGN:20230603 ...]

然后我们可以通过 BITCOUNT 统计连续签到的用户数,或者通过程序结合 pipeline 依次获取连续签到的用户信息。

看到没有,兜兜转转,我们又回到了起点 —— 「不忘初心,方得始终」

当然,如果你的用户存储使用了分表逻辑的话,无法通过一个主键 ID 来代表唯一用户的话,可以考虑通过一个映射算法或者通过 Redis 「自增发号器」来给每个用户分配一个唯一的 ID 。这里不推荐使用之前「布隆过滤器」的映射算法,一是存在冲突的可能性,二是太分散对于存储空间不够友好。

好了,到这里,关于「签到统计」就要告一段落了。

总结

在这篇文章中,我们讨论了针对「签到统计」的一些设计方案。

我们从「时间维度」、「用户维度」和「混合维度」三种不同的维度来分析了实现的一些细节。这里的处理思路与之前文章中讨论的「布隆过滤器」有所不同。

首先,「布隆过滤器」主要是为了解决「存在与否」的问题,而「签到统计」除了解决「存在与否」的问题,可能还会牵扯到「位运算」(比如「时间维度」中,我们需要统计某段时间内连续签到的用户),这种情况下「布隆过滤器」的解决思路就不合适了。

其次,「签到统计」是面向多个维度的。在本文中,我们就讨论了「时间维度」和「用户维度」两个具体的维度。这也是「布隆过滤器」的场景中不需要重点关心的。

用一句话总结「签到统计」的处理思路就是:

通过合理地规划 bitmap 的布局,在满足存储空间的前提下,借助 Redis 命令和程序,更加高效合理地处理各种常见的签到场景。

在下一篇文章 《Redis 实用小技巧—— bitmap 应用之「位排序」》中,我们将以「位排序」这个小场景作为我们系列文章的收篇之作。

感谢各位的持续关注~

本作品采用《CC 协议》,转载必须注明作者和本文链接
你应该了解真相,真相会让你自由。
本帖由系统于 1年前 自动加精
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 14

:+1: :+1: :+1: :+1: :+1: :+1: :+1: :+1: :+1: :+1: :+1:

1年前 评论
laisxn

可以考虑使用 Redis 的 Lua 脚本来一次性获取多次的签到记录。Lua 脚本可以在 Redis 服务器端执行,减少了网络开销

1年前 评论
快乐的皮拉夫 (楼主) 1年前

很不错,很棒。楼主加油

1年前 评论
快乐的皮拉夫 (楼主) 1年前

这个“日期区间偏移量”是怎么计算得来的呢

1年前 评论
快乐的皮拉夫 (楼主) 1年前
王小大 (作者) 1年前
_jue

有些时候使用这个统计就是灾难,建议也说一下缺点,那些场景使用会有问题。

1年前 评论

对于用户id,存储跳跃性比较大的这个问题怎么处理呢

4个月前 评论
快乐的皮拉夫 (楼主) 4个月前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
文章
38
粉丝
110
喜欢
653
收藏
719
排名:273
访问:3.5 万
私信
所有博文
社区赞助商