本篇文章带大家了解一下Redis中的Bitmaps,详细介绍 Bitmaps 概念,操作以及常见应用,希望对大家有所帮助!

Redis版本:6.2.6

一、简单介绍 Bitmaps

位图不是实际的数据类型,而是在 String 类型上定义的一组面向位的操作。由于字符串是二进制安全的 blob,并且它们的最大长度为 512 MB,因此它们适合设置多达 2^32 个不同的位。【相关推荐:Redis视频教程】

上述是Redis官网对 Bitmaps 的介绍,简单理解 Bitmaps 就是 Redis 提供的一系列直接操作 String 的位的指令,比如我们现在有一个字符串 :“a”

127.0.0.1:6379> set k1 a
OK
127.0.0.1:6379> get k1 
"a"

a 的二进制是:0110 0001,我们可以利用 [ GETBIT key offset ]指令,获取这个字符串对应 位 的数值:

127.0.0.1:6379> getbit k1 0
(integer) 0
127.0.0.1:6379> getbit k1 1
(integer) 1
127.0.0.1:6379> getbit k1 2
(integer) 1
127.0.0.1:6379> getbit k1 3
(integer) 0
127.0.0.1:6379> getbit k1 4
(integer) 0
127.0.0.1:6379> getbit k1 5
(integer) 0
127.0.0.1:6379> getbit k1 6
(integer) 0
127.0.0.1:6379> getbit k1 7
(integer) 1

这个指令中的 offset 表示偏移量,如上面展示可以看到,偏移 1 位,2 位,7 位的数值是 1,其他位是 0,对应的二进制就是:0110 0001,这是字符 a 的 ASCII 值。

接下来我们可以利用 [SETBIT key offset value ] 指令,去改变某一位的值,比如:

127.0.0.1:6379> setbit k1 6 1 //偏移6位,置为1
(integer) 0
127.0.0.1:6379> get k1
"c"

如上,我们设置偏移量为 6 的位置数值为 1,这样这个二进制对象就变成了: 0110 0011,对应的就是字符 ”c“ ,我们通过 直接操作字符串的位 改变了字符串的值。

Bitmaps 在redis中是按位操作字符串的工具,根据这个工具,我们可以将字符串当作一组二进制数组来使用,我们举一个简单的例子:

如何记录十亿用户的在线状态?

这里我们 用一串二进制来记录这十亿用户的登录状态,二进制的每一位都代表一个用户,0 代表未登录,1 代表已登录,每次登录或登出都利用 Bitmaps 去更新对应位的数值,最终形成的结果看起来就是这样的:

1.png

我们用上面的一串二进制记录了这十亿用户的登录状态,为什么要这么做? 主要就是节省空间,读取或更新速度快

我们来算一下这种存储方式所需要的存储空间大小:

十亿用户,每一个用户占 1 bit
所需空间 = 1000000000 bit = 1000000000 / 8 / 1024 / 1024 = 119 MB

以 MySQL 为例,存储需要的空间大小:

假设仅有两个字段:用户id,在线状态
用户id为BIGINT类型,大小为:8 Bytes	
在线状态使用TINYINT类型,大小为:1 Bytes	
所需空间 = 1000000000 * (8 + 1) Bytes = 9000000000 Bytes = 8583 MB

差距显而易见,这也很好理解,使用 MySQL 或者Redis 的 Hash 存储,最小单元都是 字节,和直接操作 位 自然无法比较。

以上是对 Redis 的 Bitmaps 的简单介绍,接下来会介绍一下关于 Bitmaps 的基础命令以及应用。

二、Bitmaps的操作

SETBIT

时间复杂度: O(1)

SETBIT key offset value

更新指定 key 的 offset 位置处的值,value 只可以是 0 或 1

需要注意:

1、offset 表示偏移量,最大为 2 32-1((因为最大是512MB,符号占1位)。

2、分配内存,一次分配之后,后续相同的key不会再有分配开销,官网描述:在 2010 款 MacBook Pro 上,设置位数 2 32-1(512MB 分配)大约需要 300 毫秒。

3、返回值,返回对应 offset 操作之前的值。

GETBIT

时间复杂度: O(1)

GETBIT key offset

返回存储在key的字符串值中offset处的位值。

需要注意:

当 key 不存在,或者 offset 超出范围时,返回整数 0

BITCOUNT

时间复杂度: O(n)

BITCOUNT key [start end [BYTE|BIT]]

计算字符串中 1 的数量

示例:
127.0.0.1:6379> set k1 a
OK
127.0.0.1:6379> BITCOUNT k1 
(integer) 3
127.0.0.1:6379> set k1 aa
OK
127.0.0.1:6379> BITCOUNT k1
(integer) 6
127.0.0.1:6379> BITCOUNT k1 0 0 
(integer) 3
127.0.0.1:6379> BITCOUNT k1 0 1
(integer) 6
127.0.0.1:6379> BITCOUNT k1 0 -1
(integer) 6

需要注意:

1、start 和 end 参数指的是Byte,不是bit,官网介绍在7.0版本之后才可以指定 Byte或bit。

2、如果key 不存在,统计出来是0

3、时间复杂度是 O(n),这个n是指start 和 end 参数之间的数据量,所以数据量过大时善用start 和 end,或者多建几个key。

BITOP

时间复杂度: O(n)

BITOP operation destkey key [key ...]

在多个键(包含字符串值)之间执行按位运算并将结果存储在目标键中

其中 operation有 :ANDORXORNOT

destkey是指目标key,将后面的多个 key 进行按位操作后,储存在 destkey 中

// AND,按位与
127.0.0.1:6379> set k1 a
OK
127.0.0.1:6379> set k2 aa
OK
127.0.0.1:6379> set k3 aaa
OK
127.0.0.1:6379> bitop and dk1 k1 k2 k3 
(integer) 3
127.0.0.1:6379> get dk1
"a\x00\x00"

如上面示例,将 k1 ,k2,k3,进行按位与之后结果储存在 dk1 中,dk1 后面的 \x00 是十六进制, a\x00\x00 转换成二进制就是: 0110 0001 0000 0000 0000 0000。

// OR,按位或
127.0.0.1:6379> bitop or dk2 k1 k2 k3 
(integer) 3
127.0.0.1:6379> get dk2
"aaa"
---------------------
//XOR ,按位异或
127.0.0.1:6379> bitop xor dk3 k1 k2 k3 
(integer) 3
127.0.0.1:6379> get dk3
"a\x00a"
---------------------
//NOT,取反 0110 0001 取反 ->  1001 1110  -> 十六进制 \x9e
127.0.0.1:6379> bitop not dk4 k1
(integer) 1
127.0.0.1:6379> get dk4
"\x9e"

BITPOS

时间复杂度: O(N)

BITPOS key bit [start [end [BYTE|BIT]]]

返回字符串中设置为 1 或 0 的第一位的位置。

示例
127.0.0.1:6379> setbit k1 4 1
(integer) 0
127.0.0.1:6379> setbit k1 13  1
(integer) 0
127.0.0.1:6379> bitpos k1 1 
(integer) 4
127.0.0.1:6379> bitpos k1 1 0 0
(integer) 4
127.0.0.1:6379> bitpos k1 1 1 1
(integer) 13

需要注意:

1、这里的 start 、end 参数指的是 Byte,在7.0版本后可以指定 Byte或bit。

2、bitpos 、 setbit 、 getbit 遵循相同的位位置约定。

3、查询 1 时,不存在的 key 或者 对应范围的字符串全是 0 ,返回 -1。

4、查询 0 时,有三种特殊情况:

k2 = 1111 1111  , k3 不存在
---------------------------
// 不指定范围或仅指定 start,且值全是1,这时候会查出来最右侧的1的位置 + 1,可以视为右侧填充了0 
127.0.0.1:6379> BITPOS k2 0
(integer) 8
---------------------------
// 不指定范围或仅指定 start,且key不存在,返回0
127.0.0.1:6379> BITPOS k3 0
(integer) 0
---------------------------
// 指定范围,且范围内没有0,返回 -1
127.0.0.1:6379> BITPOS k2 1 1
(integer) -1

BITFIFLD

BITFIELD key [GET encoding offset] [SET encoding offset value] [INCRBY encoding offset increment] [OVERFLOW WRAP|SAT|FAIL]

该命令将 Redis 字符串视为位数组,并且能够处理不同位宽和任意非(必要)对齐偏移量的特定整数字段,该命令有get、set、incrby操作

就是说可以利用这个命令,按位分段的处理字符串,举个例子:

127.0.0.1:6379> set k1 aaa
OK
aaa
0110 00010110 00010110 0001

k1的二进制如上表格所示,接下来我们使用BITFIFLD命令来操作 k1

GET:

// u8 = 无符号 + 8 位   ;  0 = 从第0位开始
// 获取到的结果就是 : 0110 0001 ,无符号转换成十进制就是 97
127.0.0.1:6379> BITFIELD k1 get u8 0  
1) (integer) 97
// i8 = 有符号 + 8 位   ; 1 = 从第一位开始
// 结果 = 1100 0010 ,带符号转换成十进制就是 -62 (不理解为啥是-62可以看一下补码)
127.0.0.1:6379> BITFIELD k1 get i8 1
1) (integer) -62

SET:

// 将0-7位,变成98,也就是: 0110 0010 ,这对应的就是b,所以第一个字符变成了 b
127.0.0.1:6379> BITFIELD k1 set u8 0 98
1) (integer) 97
127.0.0.1:6379> get k1
"baa"
------------------------------------------
127.0.0.1:6379> BITFIELD k1 set u8 #1 98   // #1的意思是 从第二个 8 位开始
1) (integer) 97
127.0.0.1:6379> get k1
"bba"

INCRBY:递增或者递减

// -1 表示递增或递减的数值,k1 的0-7位 减1,结果是97,k1就变成了 "aba"
127.0.0.1:6379> get k1
"bba"
127.0.0.1:6379> BITFIELD k1 incrby u8 0 -1
1) (integer) 97
127.0.0.1:6379> get k1
"aba"
127.0.0.1:6379> BITFIELD k1 incrby u8 #1 -1
1) (integer) 97
127.0.0.1:6379> get k1
"aaa"

在使用 INCRBY 进行递增或递减操作时,有 溢出控制 ,而且 Redis 提供了三种行为来控制溢出:

WRAP :环绕,在无符号整数的情况下,换行就像对整数可以包含的最大值进行模运算

// 以 u8 为例,无符号,8位,那么最大值是 256
127.0.0.1:6379> BITFIELD k1 get u8 0 
1) (integer) 97
127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 256
1) (integer) 97
127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 257  // 97 + 257 = 97+257-256 = 98
1) (integer) 98
127.0.0.1:6379> BITFIELD k1 overflow WRAP incrby u8 0 200 // 98 + 200 = 298 - 256 = 42
1) (integer) 42

在有符号的情况下,向上溢出到负值,向下溢出到正值,以 i8 为例 127 + 1 到 -128

127.0.0.1:6379> set k1 aaa
OK
127.0.0.1:6379> BITFIELD k1 get u8 0 
1) (integer) 97
127.0.0.1:6379> BITFIELD k1 incrby i8 0 30
1) (integer) 127
127.0.0.1:6379> BITFIELD k1 incrby i8 0 1 
1) (integer) -128
127.0.0.1:6379> BITFIELD k1 incrby i8 0 -1
1) (integer) 127

SAT: 使用饱和算法,即下溢时设置为最小整数值,溢出时设置为最大整数值。

// u8时,最大255 最小 0
127.0.0.1:6379> set k1 aaa
OK
127.0.0.1:6379> BITFIELD k1 get u8 0 
1) (integer) 97
127.0.0.1:6379> BITFIELD k1 overflow SAT incrby u8 0 20000
1) (integer) 255
127.0.0.1:6379> BITFIELD k1 overflow SAT incrby u8 0 -213123
1) (integer) 0

FAIL:在此模式下,不会对检测到的上溢或下溢执行任何操作。相应的返回值设置为 NULL 以向调用者发出条件信号。就是说,溢出就返回 NUll。

127.0.0.1:6379> set k1 aaa
OK
127.0.0.1:6379> BITFIELD k1 get u8 0
1) (integer) 97
127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 200
1) (nil)
127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 -98
1) (nil)

另外,以上的 BITFIELD 命令可以多个一起使用:

127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 -98  get u8 0 
1) (nil)
2) (integer) 97

BITFIELD_RO

BITFIELD命令的只读变体。它就像原始的BITFIELD一样,但只接受GET子命令并且可以安全地用于只读副本。

Bitmaps 的应用

在上面的描述中,介绍了 Bitmaps 可以记录用户的在线状态,除此之外还可以用他做那些功能呢?

首先我们来总结一下Bitmaps的特点:

  • 只有 0 和 1 两种状态(描述的信息比较局限)
  • 占用的内存非常少
  • 存取速度极快 (set,get操作时间复杂度都是O(1))

基于这些特点,我们可以用 Bitmaps 来判断数据是否存在于某个集合中、也可以用于记录用户的一些行为比如登录或者某个页面的查看,关闭,签到等等,接下来我们举几个比较常见的例子。

日活统计

如何统计当前系统每天登录的用户数量?

使用Redis的Bitmaps,将 系统名+日期设置为key 如 zcy20211215,value中使用用户的Id做offset,用 0 和 1 记录用户在当天是否登录过,登录将对应的位设置为1。

这样做之后,每天可以得到一个Bitmaps,如果想获取某天登录过的用户数量,直接使用 BITCOUNT 操作即可。

如果想统计过去 30 天都登录过的用户,可以使用 BITOP AND 操作,将那 30 天的Bitmaps进行 按位与 操作。

布隆过滤器

布隆过滤器的本质是 Hash映射算法 + Bitmaps。

2.png

如图,一个 value 进入布隆过滤器,经过多个Hash算法,获取其映射在Bitmap上的位置,当所有的位置都为1时,则认为这个 value 在过滤器中,否则就认为不存在。

营销数据统计

Bitmaps 在营销系统中可以用到的场景很多:

用户画像信息的使用,一个用户有很多中标签并且无限扩展,比如 性别,是否是程序员,单身,租房,是否养宠物,我们都可以考虑用Bitmap储存和使用。

用户的行为,是否点击了广告,是否浏览到底部,是否领取优惠券等行为分别用一个Bitmap存储,用法和上面的用户画像类似。

这里举一个小例子,看一下Bitmaps在营销系统中的使用:

假设我们有一个一亿用户的电商应用,产品提了这样一个需求:

所有的男性用户在进入应用首页时,弹出一个 防脱发保健品 的广告弹窗

需求很简单,一个接口搞定,用户进入时调用 获取广告 的接口,接口中查询数据库判断是否为男性,是返回广告内容,否返回空。

这时候产品觉得这种推送不够精准,也未必男性都会掉头发,所以增加了条件: 程序员,我们的需求就变成了:

所有的 男性 且职业为 程序员 的用户在进入应用首页时,弹出一个 防脱发保健品 的广告弹窗

加了一个条件之后依然很简单,用户的 性别 和 职业 信息极有可能存在一张表,也是一次查询即可。

然而,男性程序员脱发的概率很高,但是未必都买得起防脱发保健品,这时候需要推送的更精准一点,所以再新增一个条件:在平台上月均消费超过五百 ,这个条件和上述的 男性程序员 这两个条件大概率不在同一个表中,如果用上面的方案,那就是再增加一次DB查询,速度慢且对数据库开销大,这个时候 Bitmaps 的效果就很明显了。

现有的条件是:男性程序员在平台上月均消费超过五百

在这个场景中,如果要使用 Bitmaps,首先要把数据加载到Redis里,可以用一种简单粗暴的方法,直接遍历数据库,把需要用的标签信息加载到Redis中:

    // 用户标签加载伪代码
    public Boolean loadUserLabel() {
    		// 用户性别 bitmap 数据加载
        String key = "user_label_sex_male";
        List<User> users = userDao.queryUser();
        users.forEach(
                t->{
                    if (Objects.equals(t.getSex(),"male")) {
                        jedis.setbit(key,t.getId(),"1");
                    }
                }
        );
        return true;
    }

经过上述代码,将用户的性别加载到了 redis 的 bitmap中,其他的标签如 职业、消费大于五百,与此类似。

在Redis中有了我们所需的用户标签信息后,就可以开始使用了,像我们上述的需求,可以用 BITOP 命令的 AND操作,将男性、程序员、月均消费大于五百这三个Bitmap 生成一个 同时满足这三个条件的 Bitmap,标签过多的时候可以这样做。在这里我们就三个条件,可以简单一点直接在代码里查三次:

    // 用户首页广告获取伪代码
    public Response getHomepageAds(User user) {
        // 这里写死,实际使用中是动态配置
        String maleKey = "user_label_sex_male";
        String programmerKey = "user_label_occupation_programmer";
        String spendMonth500Key = "user_label_spend_month_500";
        //去bitmap判断,该位为1,则满足条件
        if (jedis.getbit(maleKey,user.getId()) && jedis.getbit(programmerKey,user.getId()) 
                && jedis.getbit(spendMonth500Key,user.getId())) {
            return "内容";
        }
        return  "没有广告";
    }

上面就是一个Bitmap在营销系统中应用的小例子,可以在这基础上进行很多扩展,比如每个标签的实时的增量加载,每个广告和标签的绑定关系的动态配置,标签的自动生成等等等等。。。。

我们接下来可以看一下 Bitmaps 在用户行为记录中的应用,现在产品提了一个新的需求:

我想知道有多少用户点进了我们的弹窗广告

点击弹窗广告之后,前端发送请求,后端记录用户的点击状态:

    // 用户点击广告行为记录伪代码
    public Response getHomepageAds(User user) {
        String adActionKey = "homepage_ad_action_open";
        jedis.setbit(adActionKey,user.getId(),"1");
        
    }

后面如果想统计数量,可以直接用 BITCOUNT 命令。其他行为的记录和这个相似,如是否拖动到底部,停留时间是否大于n秒等等,这里就不做赘述啦。

协同制图

这个例子来源于Redis官网,是 Reddit 在 2017 年愚人节的一个游戏 r/place,这是一个非常有趣的 Bitmaps 的应用。

游戏介绍:

一个画板,上面有1000 * 1000 个像素点,每个玩家每五分钟可以编辑一个像素点(有十六种颜色提供选择),参与的玩家数量不限,72 小时后截止。

游戏很简单,每个人只要编辑像素点的颜色即可,17 年的活动最终形成了这个画(这里是一部分):

3.png

这里面有一百万个像素点,据统计至少十万人参与了这个游戏,并发量很高,如何保证可用性呢?Reddit 在这里就使用了 Redis 的 Bitmap:

先定义画板中的像素的位置,用 x 表示横坐标,y 表示纵坐标,每一个像素点的位置都对应 Bitmap 的一个offset。

	用户编辑像素点时,将 位置信息(x,y) 和 颜色信息 用 Bitmap 储存,读取画板数据也是直接利用 Bitmap。

思路很简单,主要是解决下面两个问题:

1、坐标和Bitmap之间的映射关系? 坐标如何转换成 Bitmap的 offset,offset如何转换成画板中的 x,y 坐标。

2、如何直接利用 Bitmaps 储存一个坐标点的信息? 这里就存颜色。

这个项目是这么做的:

1、由于总计像素点是 100 万个,所以设计了公式: x + 1000y = offset

储存时,将 (x,y) 转换成 offset ,比如 (1,2) 位置,那么 offset = 1 + 2000 = 2001

读取时,将 offset 转换成(x,y),比如 offset = 9008,那么 x = 9008 % 1000 = 8,y = 9008 / 1000 = 9

2、利用 Bitmaps 的 BITFIELD 命令,进行分段操作:

玩家可选择的颜色共 16 种,那么每个点至少需要 4 位,所以使用 BITFIELD 时,操作的位数字段应该是 u4

看起来就是这样的:

4.png

上面是这个游戏对于 Bitmaps 应用的简单介绍,具体实现及源码见文末Reddit 团队的博客。

利用 BITFIELD 命令,还可以判断数据是否重复,比如有 10 亿个整数,如何找出其中重复的数据? 每个数可以给 2 位,01表示出现一次,10表示有重复。

四、小扩展

当用户 Id 不是自增 Id,该如何使用 Bitmaps?

在实际开发中,用户的Id有可能不是自增的,比如使用雪花算法,或UUID工具生成的Id,这种情况直接使用 Bitmaps 是不行的,偏移量过大。这时候可以参考 布隆过滤器 ,设计一个Id的映射算法,将用户Id映射在一定范围内。

Bitmaps 进行持久化存储时,如何节省空间?

使用压缩算法,如 RLE算法

在使用Bitmaps时,会有大量连续的位置数据重复,这些重复就有压缩的空间,比如前 1000 位都是 0,那只用存一句 1000个0即可,而不是 00000...这样存一千个。

更多编程相关知识,请访问:编程入门!!

以上就是Redis学习之深入了解Bitmaps的详细内容,转载自php中文网

点赞(366) 打赏

评论列表 共有 0 条评论

暂无评论

微信小程序

微信扫一扫体验

立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部