本篇文章带大家了解一下Redis中的Bitmaps,详细介绍 Bitmaps 概念,操作以及常见应用,希望对大家有所帮助!
一、简单介绍 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 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 ((因为最大是512MB,符号占1位)。
2、分配内存,一次分配之后,后续相同的key不会再有分配开销,官网描述:在 2010 款 MacBook Pro 上,设置位数 2 (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有 :AND,OR,XOR 和 NOT
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
0110 0001 | 0110 0001 | 0110 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。
如图,一个 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 年的活动最终形成了这个画(这里是一部分):
这里面有一百万个像素点,据统计至少十万人参与了这个游戏,并发量很高,如何保证可用性呢?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
看起来就是这样的:
上面是这个游戏对于 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的详细内容,更多请关注Work网其它相关文章!