Redis系列(十九)独立功能之BitMap(位图)

之前写过一篇文章，对位图这个数据结构及其在 Java 中的应用做了详细的介绍，同时也简单介绍了 Redis 中的位图。

位图数据结构及其在-Java 和-Redis 中的应用.

如果有兴趣，强烈推荐阅读上面的文章，可以让你对位图的认识更进一步。当然，本文会对 Redis 中的位图进行更深一些的讲解，如果你只关心 Redis 中的位图. 那么看本文就够了。

注：本文假设读者对于位图这个数据结构，有基本的认识

目录

• 介绍
• 简单使用
  • 相关命令
  • Redis 客户端示例
  • Java 代码示例
  • python 代码示例
• 进阶使用
• 实现原理
  • GETBIT
  • SETBIT
  • BITCOUNT
  • BITOP
• 应用场景
  • 用户签到/抢购等唯一限制
  • 用户标签等数据
  • 布隆过滤器
• 总结
• 参考文章
• 联系我

介绍

对于位图的基本概念及原理，本文不做介绍了。直接来介绍 Redis 中的位图。这是 Redis 官网上对于位图的介绍。

位图不是实际的数据类型，而是在字符串类型上定义的一组面向位的操作。因为字符串是二进制安全的 blob，它们的最大长度是 512 MB，所以它们适合设置为 2^32 个不同的位。
位操作分为两组：固定时间的单个位操作（如将位设置为 1 或 0，或获取其值）和对位组的操作（如在给定的位范围内计算集合位的数量）。
位图最大的优点之一是，在存储信息时，它们通常可以节省大量空间。例如，在一个使用增量用户 id 表示不同用户的系统中，仅使用 512 MB 内存就可以记住 40 亿用户的单个位信息（例如，知道用户是否希望接收时事通讯）。

从中我们可以得知，位图的一些基本操作，以及一个额外的重要信息。

Redis 的位图不是一个单独的数据结构，而是在字符串类型上的一组面向位的操作。所以 Redis 位图本质上就是一个字符串。

简单使用

相关命令

• getbit: 获取某个 key 的某个位置的值。getbit key offset.
• setbit: 设置某个位置的值。setbit key offset value.
• bitcount: 计算某个 key 中为 1 的 bit 数量。支持范围。bitcount key start end
• bitpos: 返回范围内第一个为特定 bit 的位置。bitpos key bit(0/1) start end
• bitop: 逻辑运算，支持四种逻辑运算，与，或，抑或，与非。具体的命令如下：

  BITOP AND destkey srckey1 srckey2 srckey3 ... srckeyN
  BITOP OR destkey srckey1 srckey2 srckey3 ... srckeyN
  BITOP XOR destkey srckey1 srckey2 srckey3 ... srckeyN
  BITOP NOT destkey srckey

其中 destkey 是结果存储的 key, 其余的 srckey 是参与运算的来源。

• bitfield: 在 3.2.0 之后新添加的操作指令。

在 3.2 之前，如果需要一次性操作多个位，我们只能使用管道，所以 Redis 提供了 bitfield 来进行批量的位操作。bitfield 有三个子指令，分别是 get/set/incrby，它们都可以对指定位片段进行读写，但是最多只能处理 64 个连续的位，如果 超过 64 位，就得使用多个子指令，bitfield 可以一次执行多个子指令。

# 从第三个位开始取三个位，结果是有符号数。
 bitfield huyanshi_key get i3 2  
# 一次性执行多个字指令，get 多个片段的值
bitfield huaynshi_key get u4 0 get u3 2 get i4 0 get i3 2

Redis 客户端示例

Java 代码示例

public static void main(String[] args) {
    Jedis jedis = new Jedis("localhost");
    Boolean result = jedis.setbit("huyanshi_bitmap_key", 4, false);
    Boolean result1 = jedis.getbit("huyanshi_bitmap_key", 4);
    System.out.println(result1);
}

python 代码示例

import redis

r = redis.Redis(host="localhost", port=6379)
r.setbit("huyanshi_bitmap_key", 10, 1)
print(r.getbit("huyanshi_bitmap_key", 10))

进阶使用

bitfield 命令除了上面讲述的 GET/SET 子指令之外，还有第三个子指令 incrby.

它用来对指定范围的位进行自增操作。既然提到自增，就有 可能出现溢出。如果增加了正数，会出现上溢，如果增加的是负数，就会出现下溢出。Redis 默认的处理是折返。如果出现了溢出，就将溢出的符号位丢掉。如果是 8 位无符号数 255， 加 1 后就会溢出，会全部变零。如果是 8 位有符号数 127，加 1 后就会溢出变成 -128。

bitfield 指令提供了溢出策略子指令 overflow，用户可以选择溢出行为。

• 默认是折返 (wrap).
• 失败 (fail) 报错不执行。
• 饱和截断 (sat)，超过了范围就停留在最大 最小值。

overflow 指令只影响接下来的第一条指令，这条指令执行完后溢出策略会变成默认 值折返 (wrap)。

实现原理

本节简单介绍下GETBIT,SETBIT,BITCOUNT, BITOP等几个命令的实现原理。

GETBIT

GETBIT 命令用于返回位图在 offset 偏移量上的二进制位的值，因此我们需要将 offset 转换为具体的位置，算法如下：

1. byte= [offset / 8]
2. bit = [offset % 8] + 1
3. 根据 byte 和 bit 在 SDS 的值中找到具体的值。

举个例子：
当我们执行 GETBIT huyanshi 3时。

1. byte=0,
2. bit=4
3. 在 SDS 的第一个字节中，找到第 4 个 bit 上的值，返回即可。

命令的时间复杂度是 O(1).

SETBIT

SETBIT 命令用于将位图中的某个偏移量上的二进制位的值设置为传入的 value. 并且向客户端返回旧值。

1. 计算需要的最小字节数，len=[offset / 8] + 1, 这个值代表了需要存下当前设置的位置，需要的 SDS 的最小长度。
2. 检查 SDS 长度，进行扩展
3. byte= [offset / 8]
4. bit = [offset % 8] + 1
5. 根据上面计算的 byte 和 bit, 找到对应的位置，设置新值，返回旧值。

举个例子：
当我们执行SETBIT huyanshi_key 12 1时，假设当前长度不够，需要扩展。

1. 首先计算 len=[12 /8] + 1= 2, 得出需要 SDS 长度为 2.
2. 当前长度为 1, 将 SDS 金拽扩展。
3. 计算 byte=1.
4. 计算 bit=5.
5. 根据 byte 和 bit 进行定位，设置新值，返回旧值。

命令的时间复杂度是 O(1).

需要注意的是，Redis 中的位图保存的 bit 不是按照书写顺序的，而是书写顺序的逆序，这样可以在新扩展的时候，不用移动原有 bit 的位置，直接进行写入即可。.

假如当前的二进制串为：1110, 那么 Redis 中实际存储的是：0111.

当需要扩展的时候，比如我们希望二进制串变成0101110, 那么我们首先金拽扩展。此时的二进制串变成了0111 0000, 直接在后面 4 个 0 上设置新的值即可。比较方便。

上面例子里为了简单，只写了 4 个 bit, 其实是不会出现的，bit 位是以字节单位出现的，也就是 8 个一组。

BITCOUNT

Redis 中 BITCOUNT 的实现，采用了查表和 variable-precisionSWAR 两种算法。

• 查表算法，保存了所有建厂为 8 位的汉明重量，可以直接查表获得。
• variable-precisionSWAR 算法，BITCOUNT 命令在每次循环中载入 128 个二进制位，然后调用 4 词 32 位的该算法来计算汉明重量。

当调用 BITCOUNT 时，如果未处理的二进制位大于 128 个，则使用 variable-precisionSWAR 算法，费则使用查表算法。

BITOP

Redis 是基于 C 语言的，C 语言支持对字节进行与，或，异或，非操作，因此 BITOP 操作就是调用 C 语言的对应逻辑实现的。

应用场景

应用场景其实是很考验人的，不能学以致用，在程序员行业里基本上就相当于没有学了吧。..

经过自己的摸索以及在网上的浏览，大致见到了一些应用场景，粗略的写出来，方便大家理解并且以后遇到类似的场景可以想到位图并应用他！

用户签到/抢购等唯一限制

用户签到每天只能一次，抢购活动中只能购买一件，这些需求导致的有一种查询请求，给定的 id 做没做过某事. 而且一般这种需求都无法接受你去查库的延迟。当然你查一次库之后在 redis 中写入：key = 2345 , value = 签到过了. 也是可以实现的，但是内存占用太大。

而使用位图之后，当2345用户签到过/抢购过之后，在 redis 中调用setbit 2019-07-01-签到 2345 1即可，之后用户的每次签到/抢购请求进来，只需要执行相应的 getbit 即可拿到是否放行的 bool 值。

这样记录，不仅可以节省空间，以及加快访问速度之外，还可以提供一些额外的统计功能，比如调用bitcount来统计今天签到总人数等等。统计速度一般是优于关系型数据库的，可以用来做实时的接口查询等。

用户标签等数据

大数据已经很普遍了，用户画像大家也都在做，这时候需要根据标签分类用户，进行存储。方便后续的推荐等操作。

而用户及标签的数据结构设计是一件比较麻烦的事情，且很容易造成查询性能太低。同时，对多个标签经常需要进行逻辑操作，比如喜欢电子产品的 00 后用户有哪些，女性且爱旅游的用户有哪些等等，这在关系型数据库中都会造成处理的困难。

可以使用位图来进行存储，每一个标签存储为一个位图（逻辑上，实际上你还可以按照尾号分开等等操作）, 在需要的时间进行快速的统计及计算。
如：

用户	0	1	2	3	4	5	6	7	8
爱旅游	1	0	0	1	0	0	1	0	0

可以清晰的统计出，0,3,6用户喜欢旅游。

用户	0	1	2	3	4	5	6	7	8
00 后	1	1	0	0	0	0	1	0	0

用户0,1,6是 00 后。

那么对两个位图取与即可得到爱旅游的 00 后用户为0,6.

布隆过滤器

这个就比较有名了，关于这个的详细信息可以查看 布隆过滤器 (bloom filter) 的原理及在推荐去重中的应用

总结

本文介绍了位图的基本使用方法，对 4 个常用命令的实现原理做了一点简单的介绍，需要深入了解的可以查看参考文章中的文献，继续深入了解。

Redis 位图的特殊之处在于：使用字符串来保存数据，是在 SDS 上定义的一系列位操作。为了让 SETBIT 命令执行的高效，SDS 中使用逆序来保存位数组。

总之，bitmap 可以高效且节省空间的存储与用户 ID 相关联的布尔数据。常见的可以应用其做大量数据的去重以及统计。更多的应用就开发你的想象力吧。

参考文章

《Redis 设计与实现（第二版》

[Redis 官网](https://redis.io/

完。

联系我

最后，欢迎关注我的个人公众号【 呼延十 】，会不定期更新很多后端工程师的学习笔记。
也欢迎直接公众号私信或者邮箱联系我，一定知无不言，言无不尽。

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >——>呼延十