Redis 학습: 비트맵에 대한 깊은 이해
- 青灯夜游앞으로
- 2022-02-07 09:59:353013검색
이 기사에서는 Redis의 비트맵을 이해하고 비트맵의 개념, 작동 및 일반적인 응용 프로그램을 자세히 소개합니다. 모든 사람에게 도움이 되기를 바랍니다.
Redis 버전: 6.2.6
1. 간략한 소개 Bitmaps
Bitmap은 실제 데이터 유형이 아니며, String 유형에 정의된 비트 지향 연산 집합입니다. 문자열은 바이너리 안전 blob이고 최대 길이가 512MB이므로 최대 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 키 오프셋] 명령을 사용하여 이 문자열의 해당 비트 값을 얻을 수 있습니다:
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
오프셋 이 명령은 위와 같이 오프셋을 나타냅니다. 오프셋 1, 2, 7 비트의 값은 1이고 나머지 비트는 0입니다. 해당 이진 값은 0110 0001이며 이는 문자 a의 ASCII 값입니다.
다음으로 [SETBIT 키 오프셋 값] 명령을 사용하여 다음과 같이 특정 비트의 값을 변경할 수 있습니다.
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에서 문자열을 비트 단위로 조작하는 도구입니다. 이 도구에 따르면 문자열을
바이너리 배열집합으로 사용할 수 있습니다.
10억 명의 사용자 온라인 상태를 기록하는 방법은 무엇입니까?여기서 우리는 바이너리 문자열을 사용하여 수십억 사용자의 로그인 상태를 기록합니다. 바이너리의 각 비트는 사용자를 나타내고, 0은 로그인되지 않았음을 나타내고, 1은 로그인되었음을 나타내고, 비트맵은 로그인할 때마다 업데이트하는 데 사용됩니다. 비트 값에 따라 최종 결과는 다음과 같습니다.
이 저장 방법에 필요한 저장 공간의 양을 계산해 보겠습니다:
十亿用户，每一个用户占 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의 기본 명령어와 응용 프로그램을 소개하겠습니다.
2. 비트맵 작업
SETBIT
시간 복잡도: O(1)SETBIT key offset value
지정된 키의 오프셋 위치에서 값을 업데이트하세요. 값은 0 또는 1만 가능합니다.
참고 :
1. Offset은 오프셋을 나타내며 최대값은 2
32-1((최대값이 512MB이므로 부호는 1비트를 차지합니다.) 2. 메모리를 할당합니다. 한 번 할당한 후에는 동일한 키가 할당 오버헤드가 있습니다. 2010 MacBook Pro에서는 비트 수를 2
32-1(512MB 할당)으로 설정하는 데 약 300밀리초가 걸립니다. , 해당 오프셋 작업 이전의 값을 반환합니다. GETBIT
시간 복잡도: O(1)GETBIT 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, 시작 및 끝 매개변수는 비트가 아닌 바이트를 나타냅니다. 공식 웹사이트에 따르면 바이트 또는 비트는 버전 7.0 이후에만 지정할 수 있습니다.
2. 통계는 0
3입니다. 시간 복잡도는 O(n)입니다. 이 n은 시작과 끝 매개변수 사이의 데이터 양을 의미하므로 데이터 양이 너무 많으면 시작과 끝을 사용하거나 더 많은 키를 생성하세요.BITOP
시간 복잡도:O(n )
BITOP operation destkey key [key ...]
여러 키(문자열 값 포함) 간에 비트 단위 연산을 수행하고 결과를 대상 키에 저장합니다여기서 연산은 다음과 같습니다: AND,
OR, XOR 및
NOTdestkey는 다음 키에 대해 비트 연산을 수행한 후 destkey에 저장됩니다. 如上面示例，将 k1 ，k2，k3，进行按位与之后结果储存在 dk1 中，dk1 后面的 \x00 是十六进制， a\x00\x00 转换成二进制就是： 0110 0001 0000 0000 0000 0000。 BITPOS 时间复杂度： O(N) 返回字符串中设置为 1 或 0 的第一位的位置。 需要注意： 1、这里的 start 、end 参数指的是 Byte，在7.0版本后可以指定 Byte或bit。 2、bitpos 、 setbit 、 getbit 遵循相同的位位置约定。 3、查询 1 时，不存在的 key 或者 对应范围的字符串全是 0 ，返回 -1。 4、查询 0 时，有三种特殊情况： BITFIFLD 该命令将 Redis 字符串视为位数组，并且能够处理不同位宽和任意非（必要）对齐偏移量的特定整数字段，该命令有get、set、incrby操作 就是说可以利用这个命令，按位分段的处理字符串，举个例子： k1的二进制如上表格所示，接下来我们使用BITFIFLD命令来操作 k1 GET： SET： INCRBY：递增或者递减 在使用 INCRBY 进行递增或递减操作时，有 溢出控制 ，而且 Redis 提供了三种行为来控制溢出： WRAP ：环绕，在无符号整数的情况下，换行就像对整数可以包含的最大值进行模运算 在有符号的情况下，向上溢出到负值，向下溢出到正值，以 i8 为例 127 + 1 到 -128 SAT： 使用饱和算法，即下溢时设置为最小整数值，溢出时设置为最大整数值。 FAIL：在此模式下，不会对检测到的上溢或下溢执行任何操作。相应的返回值设置为 NULL 以向调用者发出条件信号。就是说，溢出就返回 NUll。 另外，以上的 BITFIELD 命令可以多个一起使用： BITFIELD_RO BITFIELD命令的只读变体。它就像原始的BITFIELD一样，但只接受 在上面的描述中，介绍了 Bitmaps 可以记录用户的在线状态，除此之外还可以用他做那些功能呢？ 首先我们来总结一下Bitmaps的特点： 基于这些特点，我们可以用 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中： 经过上述代码，将用户的性别加载到了 redis 的 bitmap中，其他的标签如 职业、消费大于五百，与此类似。 在Redis中有了我们所需的用户标签信息后，就可以开始使用了，像我们上述的需求，可以用 BITOP 命令的 AND操作，将男性、程序员、月均消费大于五百这三个Bitmap 生成一个 同时满足这三个条件的 Bitmap，标签过多的时候可以这样做。在这里我们就三个条件，可以简单一点直接在代码里查三次： 上面就是一个Bitmap在营销系统中应用的小例子，可以在这基础上进行很多扩展，比如每个标签的实时的增量加载，每个广告和标签的绑定关系的动态配置，标签的自动生成等等等等。。。。 我们接下来可以看一下 Bitmaps 在用户行为记录中的应用，现在产品提了一个新的需求： 我想知道有多少用户点进了我们的弹窗广告 点击弹窗广告之后，前端发送请求，后端记录用户的点击状态： 后面如果想统计数量，可以直接用 BITCOUNT 命令。其他行为的记录和这个相似，如是否拖动到底部，停留时间是否大于n秒等等，这里就不做赘述啦。 协同制图 这个例子来源于Redis官网，是 Reddit 在 2017 年愚人节的一个游戏 r/place，这是一个非常有趣的 Bitmaps 的应用。 游戏介绍： 一个画板，上面有1000 * 1000 个像素点，每个玩家每五分钟可以编辑一个像素点(有十六种颜色提供选择)，参与的玩家数量不限，72 小时后截止。 游戏很简单，每个人只要编辑像素点的颜色即可，17 年的活动最终形成了这个画（这里是一部分）： 这里面有一百万个像素点，据统计至少十万人参与了这个游戏，并发量很高，如何保证可用性呢？Reddit 在这里就使用了 Redis 的 Bitmap： 先定义画板中的像素的位置，用 x 表示横坐标，y 表示纵坐标，每一个像素点的位置都对应 Bitmap 的一个offset。 思路很简单，主要是解决下面两个问题： 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가 아닌 경우 비트맵을 사용하는 방법은 무엇입니까? 실제 개발에서는 눈송이 알고리즘이나 UUID 도구에서 생성된 ID를 사용하는 등 사용자의 ID가 자동 증가되지 않을 수 있습니다. 이 경우 오프셋이 너무 커서 비트맵을 직접 사용할 수 없습니다. 크기가 큰. 이때 Bloom 필터를 참고하여 특정 범위 내에서 사용자 ID를 매핑하는 ID 매핑 알고리즘을 설계할 수 있습니다. Bitmaps 영구 저장을 수행할 때 공간을 절약하는 방법은 무엇입니까? RLE 알고리즘 과 같은 압축 알고리즘을 사용하세요. 비트맵을 사용하면 연속적인 위치 데이터 반복이 많이 발생하며 이러한 반복에는 압축할 여지가 있습니다. 예를 들어 처음 1000비트는 모두 0입니다. , 그러면 한 문장만 저장하세요. 00,000 대신 0 1,000개만... 이렇게 천 개를 저장하세요. 더 많은 프로그래밍 관련 지식을 보려면 프로그래밍 소개를 방문하세요! ! // 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"
// 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 key bit [start [end [BYTE|BIT]]]
示例
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
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
BITFIELD key [GET encoding offset] [SET encoding offset value] [INCRBY encoding offset increment] [OVERFLOW WRAP|SAT|FAIL]
127.0.0.1:6379> set k1 aaa
OK
a
a
a
0110 0001
0110 0001
0110 0001
// 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
// 将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"
// -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"
// 以 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
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
// 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
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)
127.0.0.1:6379> BITFIELD k1 overflow FAIL incrby u8 0 -98 get u8 0
1) (nil)
2) (integer) 97
GET子命令并且可以安全地用于只读副本。Bitmaps 的应用
// 用户标签加载伪代码
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;
} // 用户首页广告获取伪代码
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 "没有广告";
} // 用户点击广告行为记录伪代码
public Response getHomepageAds(User user) {
String adActionKey = "homepage_ad_action_open";
jedis.setbit(adActionKey,user.getId(),"1");
}
用户编辑像素点时，将 位置信息(x,y) 和 颜色信息 用 Bitmap 储存，读取画板数据也是直接利用 Bitmap。
4. 작은 확장
위 내용은 Redis 학습: 비트맵에 대한 깊은 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!