乐趣区

关于redis:Redis-实战篇巧用-Bitmap-实现亿级数据统计

jiezi

在挪动利用的业务场景中，咱们须要保留这样的信息：一个 key 关联了一个数据汇合。

常见的场景如下：

  • 给一个 userId，判断用户登陆状态；
  • 显示用户某个月的签到次数和首次签到工夫；
  • 两亿用户最近 7 天的签到状况，统计 7 天内间断签到的用户总数；

通常状况下，咱们面临的用户数量以及访问量都是微小的，比方百万、千万级别的用户数量，或者千万级别、甚至亿级别的访问信息。

所以，咱们必须要抉择可能十分高效地统计大量数据（例如亿级）的汇合类型。

如何抉择适合的数据汇合，咱们首先要理解罕用的统计模式，并使用正当的数据了性来解决理论问题。

四种统计类型：

  1. 二值状态统计；
  2. 聚合统计；
  3. 排序统计；
  4. 基数统计。

本文将由 二值状态统计类型 作为实战篇系列的开篇，文中将用到 String、Set、Zset、List、hash 以外的拓展数据类型 Bitmap 来实现。

文章波及到的指令能够通过在线 Redis 客户端运行调试，地址：https://try.redis.io/，超不便的说。

寄语

多分享多付出，后期多给他人发明价值并且不计回报，从久远来看，这些付出都会成倍的回报你。

特地是刚开始跟他人单干的时候，不要去计较短期的回报，没有太大意义，更多的是锤炼本人的视线、视角以及解决问题的能力。

二值状态统计

码哥，什么是二值状态统计呀？

也就是汇合中的元素的值只有 0 和 1 两种，在签到打卡和用户是否登陆的场景中，只需记录 签到 (1) 或 未签到 (0)， 已登录 (1) 或未登陆(0)。

如果咱们在判断用户是否登陆的场景中应用 Redis 的 String 类型实现（key -> userId，value -> 0 示意下线，1 – 登陆），如果存储 100 万个用户的登陆状态，如果以字符串的模式存储，就须要存储 100 万个字符串了，内存开销太大。

码哥，为什么 String 类型内存开销大？

String 类型除了记录理论数据以外，还须要额定的内存记录数据长度、空间应用等信息。

当保留的数据蕴含字符串，String 类型就应用简略动静字符串（SDS）构造体来保留，如下图所示：

  • len：占 4 个字节，示意 buf 的已用长度。
  • alloc：占 4 个字节，示意 buf 理论调配的长度，通常 > len。
  • buf：字节数组，保留理论的数据，Redis 主动在数组最初加上一个“\0”，额定占用一个字节的开销。

所以，在 SDS 中除了 buf 保留理论的数据，len 与 alloc 就是额定的开销。

另外，还有一个 RedisObject 构造的开销，因为 Redis 的数据类型有很多，而且，不同数据类型都有些雷同的元数据要记录（比方最初一次拜访的工夫、被援用的次数等）。

所以，Redis 会用一个 RedisObject 构造体来对立记录这些元数据，同时指向理论数据。

对于二值状态场景，咱们就能够利用 Bitmap 来实现。比方登陆状态咱们用一个 bit 位示意，一亿个用户也只占用 一亿 个 bit 位内存 ≈（100000000 / 8/ 1024/1024）12 MB。

大略的空间占用计算公式是：($offset/8/1024/1024) MB

什么是 Bitmap 呢？

Bitmap 的底层数据结构用的是 String 类型的 SDS 数据结构来保留位数组，Redis 把每个字节数组的 8 个 bit 位利用起来，每个 bit 位 示意一个元素的二值状态（不是 0 就是 1）。

能够将 Bitmap 看成是一个 bit 为单位的数组，数组的每个单元只能存储 0 或者 1，数组的下标在 Bitmap 中叫做 offset 偏移量。

为了直观展现，咱们能够了解成 buf 数组的每个字节用一行示意，每一行有 8 个 bit 位，8 个格子别离示意这个字节中的 8 个 bit 位，如下图所示：

8 个 bit 组成一个 Byte，所以 Bitmap 会极大地节俭存储空间。 这就是 Bitmap 的劣势。

判断用户登陆态

怎么用 Bitmap 来判断海量用户中某个用户是否在线呢？

Bitmap 提供了 GETBIT、SETBIT 操作，通过一个偏移值 offset 对 bit 数组的 offset 地位的 bit 位进行读写操作，须要留神的是 offset 从 0 开始。

只须要一个 key = login_status 示意存储用户登陆状态汇合数据，将用户 ID 作为 offset，在线就设置为 1，下线设置 0。通过 GETBIT判断对应的用户是否在线。50000 万 用户只须要 6 MB 的空间。

SETBIT 命令

SETBIT <key> <offset> <value>

设置或者清空 key 的 value 在 offset 处的 bit 值（只能是 0 或者 1）。

GETBIT 命令

GETBIT <key> <offset>

获取 key 的 value 在 offset 处的 bit 位的值，当 key 不存在时，返回 0。

如果咱们要判断 ID = 10086 的用户的登陆状况：

第一步，执行以下指令，示意用户已登录。

SETBIT login_status 10086 1

第二步，查看该用户是否登陆，返回值 1 示意已登录。

GETBIT login_status 10086

第三步，登出，将 offset 对应的 value 设置成 0。

SETBIT login_status 10086 0

用户每个月的签到状况

在签到统计中，每个用户每天的签到用 1 个 bit 位示意，一年的签到只须要 365 个 bit 位。一个月最多只有 31 天，只须要 31 个 bit 位即可。

比方统计编号 89757 的用户在 2021 年 5 月份的打卡状况要如何进行？

key 能够设计成 uid:sign:{userId}:{yyyyMM}，月份的每一天的值 – 1 能够作为 offset（因为 offset 从 0 开始，所以 offset = 日期 - 1）。

第一步，执行上面指令示意记录用户在 2021 年 5 月 16 号打卡。

SETBIT uid:sign:89757:202105 15 1

第二步，判断编号 89757 用户在 2021 年 5 月 16 号是否打卡。

GETBIT uid:sign:89757:202105 15

第三步，统计该用户在 5 月份的打卡次数，应用 BITCOUNT 指令。该指令用于统计给定的 bit 数组中，值 = 1 的 bit 位的数量。

BITCOUNT uid:sign:89757:202105

这样咱们就能够实现用户每个月的打卡状况了，是不是很赞。

如何统计这个月首次打卡工夫呢？

Redis 提供了 BITPOS key bitValue [start] [end]指令，返回数据表示 Bitmap 中第一个值为 bitValue 的 offset 地位。

在默认状况下，命令将检测整个位图，用户能够通过可选的 start 参数和 end 参数指定要检测的范畴。

所以咱们能够通过执行以下指令来获取 userID = 89757 在 2021 年 5 月份 首次打卡 日期：

BITPOS uid:sign:89757:202105 1

须要留神的是，咱们须要将返回的 value + 1，因为 offset 从 0 开始。

间断签到用户总数

在记录了一个亿的用户间断 7 天的打卡数据，如何统计出这间断 7 天间断打卡用户总数呢？

咱们把每天的日期作为 Bitmap 的 key，userId 作为 offset，若是打卡则将 offset 地位的 bit 设置成 1。

key 对应的汇合的每个 bit 位的数据则是一个用户在该日期的打卡记录。

一共有 7 个这样的 Bitmap，如果咱们能对这 7 个 Bitmap 的对应的 bit 位做『与』运算。

同样的 UserID offset 都是一样的，当一个 userID 在 7 个 Bitmap 对应对应的 offset 地位的 bit = 1 就阐明该用户 7 天间断打卡。

后果保留到一个新 Bitmap 中，咱们再通过 BITCOUNT 统计 bit = 1 的个数便失去了间断打卡 7 天的用户总数了。

Redis 提供了 BITOP operation destkey key [key ...]这个指令用于对一个或者多个 键 = key 的 Bitmap 进行位元操作。

opration 能够是 and、OR、NOT、XOR。当 BITOP 解决不同长度的字符串时，较短的那个字符串所短少的局部会被看作 0。空的 key 也被看作是蕴含 0 的字符串序列。

便于了解，如下图所示：

3 个 Bitmap，对应的 bit 位做「与」操作，后果保留到新的 Bitmap 中。

操作指令示意将 三个 bitmap 进行 AND 操作，并将后果保留到 destmap 中。接着对 destmap 执行 BITCOUNT 统计。

// 与操作
BITOP AND destmap bitmap:01 bitmap:02 bitmap:03
// 统计 bit 位 =  1 的个数
BITCOUNT destmap

简略计算下 一个一亿个位的 Bitmap 占用的内存开销，大概占 12 MB 的内存（10^8/8/1024/1024），7 天的 Bitmap 的内存开销约为 84 MB。同时咱们最好给 Bitmap 设置过期工夫，让 Redis 删除过期的打卡数据，节俭内存。

小结

思路才是最重要，当咱们遇到的统计场景只须要统计数据的二值状态，比方用户是否存在、ip 是否是黑名单、以及签到打卡统计等场景就能够思考应用 Bitmap。

只须要一个 bit 位就能示意 0 和 1。在统计海量数据的时候将大大减少内存占用。

往期举荐

Redis 外围篇：唯快不破的机密

Redis 日志篇：无畏宕机疾速复原的杀手锏

Redis 高可用篇：你管这叫主从架构数据同步原理？

Redis 高可用篇：你管这叫 Sentinel 哨兵集群原理

Redis 高可用篇：Cluster 集群能撑持的数据有多大？

退出移动版