Take you step by step to use Redis+Bitmap to achieve billion-level massive data statistics

This article is a practical part of Redis. It introduces the method of using Redis Bitmap to achieve billion-level massive data statistics. I hope it will be helpful to everyone!

#In the business scenario of mobile applications, we need to save such information: a key is associated with a data collection. [Related recommendations: Redis Video Tutorial]

Common scenarios are as follows:

• Give a userId to determine the user’s login status;
• Display The number of check-ins of users in a certain month and the time of first check-in;
• The check-in situation of 200 million users in the last 7 days, counting the total number of users who have continuously checked in within 7 days;

Normally, The number of users and visits we face are huge, such as millions or tens of millions of users, or tens of millions or even billions of access information.

So, we must choose a collection type that can count large amounts of data (such as billions) very efficiently.

How to choose an appropriate data set, we must first understand the commonly used statistical models and use reasonable data analysis to solve practical problems.

Four statistical types:

• Binary status statistics;

• Aggregation statistics;

• Sorting statistics;

• Cardinality statistics.

This article will use Binary state statistics type as the beginning of the practical series. String, Set, Zset, List, hash## will be used in the article. # Extended data types other than Bitmap can be implemented.

The instructions involved in the article can be run and debugged through the online Redis client, address:

try.redis.io/, which is super convenient.

Message

Share more and pay more. Create more value for others in the early stage without considering returns. In the long run, these efforts will repay you exponentially.

Especially when you first start cooperating with others, don't worry about short-term returns. It doesn't make much sense. It's more about exercising your own vision, perspective and problem-solving abilities.

Binary status statistics

Brother Ma, what are binary status statistics?

That is, the values ​​of the elements in the collection are only 0 and 1. In the scenario of check-in and check-in and whether the user is logged in, you only need to record

check-in (1) or Not signed in (0) , Logged in (1) or Not logged in (0) .

Suppose we use the String type implementation of Redis in the scenario of determining whether the user is logged in (

key -> userId, value -> 0 means offline, 1 - login), if To store the login status of 1 million users, if it is stored in the form of strings, 1 million strings will need to be stored, which consumes too much memory.

Brother Ma, why does the String type have high memory overhead?

In addition to recording actual data, the String type also requires additional memory to record data length, space usage and other information.

When the saved data contains strings, the String type is saved using the Simple Dynamic String (SDS) structure, as shown in the following figure:

• len: Occupies 4 bytes, indicating the used length of buf.
• alloc: 4 bytes, indicating the actual allocated length of buf, usually > len.
• buf: byte array, saves the actual data. Redis automatically adds a "\0" at the end of the array, which occupies an additional byte of overhead.

So, in addition to buf storing actual data in SDS, len and alloc are additional overhead.

In addition, there is the overhead of a

RedisObject structure, because Redis has many data types, and different data types have the same metadata to record (such as the time of the last access , number of citations, etc.).

So, Redis will use a RedisObject structure to uniformly record these metadata and point to the actual data.

#For binary state scenarios, we can use Bitmap to achieve it. For example, we use one bit to represent the login status, and 100 million users only occupy 100 million bits of memory ≈ (100000000 / 8/ 1024/1024) 12 MB.

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

What is 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。在统计海量数据的时候将大大减少内存占用。

原文地址：https://juejin.cn/post/6999908907791417351

作者：码哥字节

更多编程相关知识，请访问：编程视频！！

The above is the detailed content of Take you step by step to use Redis+Bitmap to achieve billion-level massive data statistics. For more information, please follow other related articles on the PHP Chinese website!