Bitmap 位图
Redis 的位图 bitmap 是由多个二进制位组成的数组, 数组中的每个二进制都有与之对应的偏移量(索引), 用户通过这些偏移量可以对位图中指定的一个或多个二进制位进行操作.
Redis 为位图提供了一系列操作命令, 通过这些命令, 用户可以:
- 设置或获取索引位上的二进制值
- 统计位图中有多少个二进制位被设置成了1
- 查找位图中, 第一个被设置为指定值的二进制位, 并返回其偏移量
- 对一个或多个位图执行逻辑并、逻辑或、逻辑异或以及逻辑非运算
- 将指定类型的整数存储到位图中
SETBIT: 设置二进制位的值
SETBIT bitmap offset value
为位图指定偏移量上的二进制位设置值, 该命令会返回二进制位被设置之前的旧值作为结果.
当执行 SETBIT 时, 如果位图不存在, 或者位图当前的大小无法满足用户想要执行的设置操作, 那么 Redis 将对被设置的位图进行扩展, 使得位图可以满足用户的设置请求. 由于位图的扩展以字节为单位, 所以扩展后的位图包含的二进制数量可能会比用户要求的稍多一些. 且在扩展的同时, 会将未设置的二进制位初始化为 0.
与一些可以使用负数的 Redis 命令不同, SETBIT 命令只能使用正数偏移量, 尝试输入负数作为偏移量将引发一个错误
- 复杂度: O(1)
GETBIT: 获取二进制位的值
GETBIT bitmap offset
与 SETBIT 命令一样, GETBIT 命令也只能接受正数作为偏移量.
对于偏移量超过位图索引的命令, GETBIT 命令将返回 0 作为结果.
- 复杂度: O(1)
BITOCUNT: 统计被设置的二进制数量
BITCOUNT key
对于值为 10010100 的位图 bitmap001, 可以通过执行以下命令来统计有多少个二进制位被设置成了1:
BITCOUNT bitmap001
(integer) 3 -- 这个位图有 3 个二进制位为 1
此外, 还可以只统计位图指定直接范围内的二进制位
BITCOUNT bitmap [start end]
start 参数和 end 参数与本章之前介绍的 SETBIT 命令和 GETBIT 命令的 offset 参数并不相同, 这两个参数用来指定字节偏移量而不是二进制位偏移量.
例如通过以下命令计算位图 bitmap003 中第一个字节中 有多少个 1:
BITCOUNT bitmap003 0 0
BITCOUNT 命令的 start 参数和 end 参数的值不久可以是正数, 还可以是负数:
BITCOUNT bitmap003 -1 -1
上面命令统计位图 bitmap003 最后一个字节中 1 的数量.
- 复杂度: O(N)
示例: 用户行为记录器
为了分析用户行为并借此改善服务质量, 很多网站都会记录用户在网站的一举一动. 为此, 可以使用集和 Set 或者 HyperLogLog 来记录所有执行了指定行为的用户, 但这种做法有两种缺陷:
- 如果使用集和来记录执行了指定行为的用户, 那么集和体积会随着用户数量的增大而变大, 从而消耗大量内存
- 如果使用 HyperLogLog 可以节约大量内存, 但由于其只是一个概率算法, 因此只能给出一个估算值. 并无法准确判断某个用户是否执行了这些指定行为, 这对精确分析算法带来了麻烦.
为了尽可能节约内存, 并精确记录每个用户是否执行了指定行为, 可以使用以下方法:
- 对于每项行为, 一个用户要么执行了该行为, 要么没有执行该行为. 因此可以通过一个二进制位来记录.
- 通过将用户 ID 与位图中的二进制偏移量一一映射, 可以使用一个位图来记录所有执行了指定行为的用户: 比如偏移量为 10086 的二进制位就负责记录 ID 位 10086 的用户信息, 而偏移量位 12345 的二进制位则负责记录 ID 位 12345 的用户信息.
- 每当用户执行指定行为时, 调用 SETBIT 命令, 将用户在位图中对应的二进制位的值设置为 1
- 通过调用 GETBIT 命令并判断用户对应的二进制的值是否位1, 可以知道用户是否执行了指定行为
- 通过对位图执行 BITCOUNT 命令, 可以知道多少用户执行了指定行为
from redis import Redis
def make_action_key(action):
return "action_reorder::" + action
class ActionRecorder:
def __init__(self, client, action):
self.client= client
self.bitmap = make_action_key(action)
def perform_by(self, user_id):
"""记录执行了指定行为的用户"""
self.client.setbit(self.bitmap, user_id)
def is_performed_by(self, user_id):
"""检查用户是否执行了指定行为"""
return self.client.getbit(self.bitmap, user_id)
def count_performed(self):
"""返回执行了指定行为的用户人数"""
return self.client.bitcount(self.bitmap)
client = Redis()
login_action = ActionRecorder(client, "login")
# 对以登陆用户进行记录
login_action.perform_by(10086)
login_action.perform_by(255255)
login_action.perform_by(987654321)
# ID 为 10086 的用户登陆了
print(login_action.is_performed_by(10086))
# ID 为 555 的用户没有登陆
print(login_action.is_performed_by(555))
# 统计用户执行了登陆操作
print(login_action.count_performed())
BITPOS: 查找第一个指定的二进制值
BITPOS bitmap value
例如, 通过下面命令, 可以知道位图 bitmap003 第一个被设置为 1 的二进制位所在的偏移量(索引):
BITPOS bitmap003 1
(integer) 0 -- 位图第一个被设置位 1 的二进制位的偏移量是 0
默认情况下, BITPOS 会查找所有二进制位, 在有需要的情况下, 用户也可以通过可选的 start 参数和 end 参数, 让 BITPOS 命令只在指定字节范围内的二进制位中进行查找:
BITPOS bitmap value [start end]
返回结果为查找到位的整体偏移量, 而不是在 start 和 end 内的偏移量.
和 BITCOUNT 命令以, BITPOS 命令的 start 和 end 参数也可以是负数.
比如, 下面代码就展示了如何在位图 bitmap003 的倒数第一个字节中, 查找第一个值位 0 的二进制位:
BITPOS bitmap003 0 -1 -1
(integer) 17
当用户尝试对一个不存在的位图或者一个唯有位都位 0 的位图, 执行查找值位 1 的二进制位时, BITPOS 命令将返回 -1 作为结果:
BITPOS not-exists-bitmap 1 -- 在不存在的位图中查找
(integer) -1
BITPOS all-0-bitmap 1 -- 在一个所有位都被设置为 0 的位图查找
(integer) -1
- 复杂度: O(N), 其中 N 为查找涉及的字节数量
BITOP: 执行二进制位运算
用户可以通过 BITOP 命令, 对一个或多个位图执行指定的二进制位运算, 并将运算结果存储到指定的键中
BITOP operation result_key bitmap [bitmap ...]
其中, operation 参数值可以是 AND, OR, XOR, NOT 中的任意一个, 这 4 个值分别对应逻辑并、逻辑或、逻辑异或和逻辑非4种运算, 其中 AND, OR, XOR 这 3 种运算允许用户使用任意数量的位图作为输入, 而 NOT 只允许一个位图作为输入. BITOP 命令这将计算结果存储到指定键中后, 会返回被存储位图的字节长度.
例如, 通过以下命令, 对位图 bitmap001, bitmap002, bitmap003 执行逻辑并运算, 然后将结果存储到键 and_result 中:
BITOP ADD and_result bitmap001 bitmap002 bitmap003
(integer) 3 -- 运算结果 and_result 位图的长度为 3 字节
当 BITOP 命令在对两个长度不同的位图执行运算时, 会将长度较短的那个位图中不存在的二进制位看作 0.
- 复杂度: O(N), 其中 N 位计算涉及的字节总数量
BITFIELD: 在位图中存储整数值
BITFIELD 命令允许用户在位图中的任意区域 field 存储指定长度的整数值, 并对这些整数值执行加法或减法操作.
BITFIELD 命令支持 SET, GET, INCRBY, OVERFLOW 这 4 个子命令, 接下来将分别介绍这些子命令.
根据偏移量对区域进行设置
BITFIELD bitmap SET type offset value通过 SET 子命令, 在位图的指定偏移量 offset 上设置一个 type 类型的整数值 value. 其中:
- offset 参数用于指定设置的起始偏移量. 这个偏移量从 0 开始计算, 偏移量为 0 表示设置从位图的第 1 个二进制开始
- type 参数用于指定被设置值的类型, 这个参数需要以 i 或 u 为前缀, 后跟被设置值的位长度
- value 参数用于指定被设置的整数值, 这个值的类型应该和 type 参数指定的类型一致. 如果给定值的长度超过了 type 指定的类型, 那么将根据 type 参数指定的类型阶段给定值
举个例子, 下面命令, 从偏移量 0 开始, 这只一个8位长的无符号整数值 198
BITFIELD bitmap SET u8 0 198 (integer) 0从结果可以知道, 该位图之前存储的结果为 0.
BITFIELD 命令允许用户在一次调用中执行多个子命令BITFIELD bitmap SET u8 0 123 SET i23 20 10086 1) (integer) 198 2) (integer) 0根据索引对区域进行设置
除了根据偏移量设置位图, 还可以根据给定类型的位长度, 对位图在指定索引上存储的整数进行设置.BITFIELD bitmap SET type #index value假如现在有一个位图, 其存储着多个 8 位长的无符号整数, 想要将其第 133 个 8 位无符号整数的值设置为 22.
如果使用偏移量, 就要手动计算 (133 - 1) * 8 的起始偏移量BITFIELD bitmap SET u8 1056 22这样很不方便, 因此可以使用类型直接设置 (SET 字命令索引从 0 开始)
BITFIELD bitmap SET u8 #132 22获取区域存储的值
通过使用 BITFIELD 命令的 GET 子命令, 可以从给定的偏移量或索引取出指定类型整数值BITFIELD bitmap GET type offset BITFIELD bitmap GET type #index执行加法或减法操作
除了设置于获取整数值, BITFIELD 命令还可以对位图的整数值执行加法或减法操作, 通过 INCRBY 子命令实现BITFIELD bitmap INCRBY type offset increment BITFIELD bitmap INCRBY type #index increment如果要实现加法, 仍然使用 INCRBY 命令, 但 increment 使用负数, 从而得到减法的效果
BITFIELD numbers SET u8 #0 10 -- 将区域的值设置未整数 10 1) (integer) 0 BITFIELD numbers GET u8 #0 1) (integer) 10 BITFIELD numbers INCRBY u8 #0 15 -- 将整数的值加上 15 1) (integer) 25 BITFIELD numbers INCRBY u8 #0 30 -- 将整数值加上 30 1) (integer) 55 BITFIELD numbers INCRBY u8 #0 -25 -- 将整数值减去 25 1) (integer) 30处理溢出
BITFIELD 命令还可以使用 OVERFLOW 子命令去控制 INCRBY 子命令在发生计算溢出时的行为BITFIELD bitmap [...] OVERFLOW WRAP|SAT|FAIL [...]OVERFLOW 参数有 WRAP, SAT 和 FAIL
- WRAP 表示回绕 (wrap around) 方式处理溢出, 也就是 C 语言默认的溢出处理方式.
- SAT 表示使用饱合运算 (saturation arithmetic) 方式处理溢出. 向上溢出的整数设置位最大值, 向下溢出的整数值则被设置位最小值
- FAIL 表示让 INCRBY 子命令在检测到计算会引发溢出时, 拒绝执行计算, 并返回空值表示计算失败
但 OVERFLOW 命令执行后不会产生任何返回, 此外, 如果没有设置溢出处理方式, 默认是 WRAP
需要注意的是, 由于 OVERFLOW 子命令只会对同一个 BITFIELD 调用中在其后面的 INCRBY 命令产生效果
BITFIELD bitmap INCRBY ... INCRBY OVERFLOW SAT INCRBY ...上面命令中, 前两个就使用 WRAP 方法处理溢出, 第三个使用 SAT 方法处理溢出
使用位图存储整数的原因
一般情况下, 用户使用字符串或者散列存储整数, Redis 都会为被存储的整数分配一个 long 类型的值, 并使用对象去包裹这个值, 然后再吧对象关联到数据库中而 BITFIELD 命令运行用户自行指定存储整数的类型, 并且不会使用对象去包裹这些整数, 因此当想要存储长度比 long 类型短的整数, 并且希望尽可能减少对象包括带来的内存消耗, 就可以考虑使用 BITFIELD 存储整数
复杂度: O(N), N 为用户给定的子命令数量
示例: 紧凑计数器
- 与之间实现的计数器不同, 这个计数器允许用户自行指定计数器值的位长以及类型, 而不是使用 Redis 默认的 long 类型来存储计数器值
- 与字符串或者散列实现的计数器不同, 这个计数器只能使用整数作为索引, 因此只适合存储一些与数字 ID 想关联的计数器数据
from redis import Redis
def get_bitmap_index(index):
return "#" + str(index)
class CompactCounter:
def __init__(self, client, key, bit_length, signed):
"""初始化紧凑计数器
Args:
- client 指定客户端
- key 参数指定计数器键名
- bit_length 参数指定计数器存储的整数位
- signed 参数用于指定计数器存储的符号
"""
self.client = client
self.key = key
if signed:
self.type = "i" + str(bit_length)
else:
self.type = "u" + str(bit_length)
def increase(self, index, n=1):
"""对索引 index 的计数器执行加法操作, 然后返回计数器的当前值"""
bitmap_index = get_bitmap_index(index)
result = self.client.execute_command(
"BITFIELD",
self.key,
"OVERFLOW",
"SAT",
"INCRBY",
self.type,
bitmap_index,
n,
)
return result[0]
def decrease(self, index, n=1):
"""对索引 index 上的计数器执行减法操作, 然后返回计数器的当前值"""
bitmap_index = get_bitmap_index(index)
decrement = -n
result = self.client.execute_command(
"BITFIELD",
self.key,
"OVERFLOW",
"SAT",
"INCRBY",
self.type,
bitmap_index,
decrement,
)
return result[0]
def get(self, index):
"""获取索引 index 上的计数器的当前值"""
bitmap_index = get_bitmap_index(index)
result = self.client.execute_command(
"BITfIELD",
self.key,
"GET",
self.type,
bitmap_index,
)
假如要为一家游戏公司创建一个记录每个玩家每月登陆数的计数器, 按照一个月 30 天, 一天登陆 2~3 次的频率来计算, 一个普通玩家一个月的登陆次数通常不会超过 100 次. 对于这么小的数值, 使用 long 类型进行存储将浪费大量空间, 因此可以使用紧凑计数器来存储用户登陆次数:
- 每个玩家都又一个整数类型的用户 ID, 可以使用 ID 作为计数器索引
- 对于每个玩家, 使用一个 16 位长的无符号整数来存储其一个月内的登陆次数
- 16 位无符号整数计数器能存储的最大值位 65536, 对于该功能来说, 已经足够大
client = Redis()
counter = CompactCounter(client, "login_count", 16, False) # 建立计数器
print(counter.increase(10086)) # 记录第 1 次登陆
print(counter.increase(10086)) # 再记录第 1 次登陆
print(counter.get(10086)) # 获取登陆次数
使用字符串命令对位图进行操作
由于 Redis 位图在字符串的基础上实现, 所以它会将位图键看作一个字符串键SETBIT bitmap 0 1 > (integer) 0 TYPE bitmap > string因此, 还可以使用字符串命令对位图进行操作
GET 8bit-int > "\x04" GET 32bit-ints > "\x00\x00\x00{\x00\x00\x01\x00\x00\x00\x00 ...}"也可以使用 STRLEN 命令获取位图的字节长度
STRLEN 8bit-int -- 1 字节 > (integer) 1 STRLEN 32bit-ints -- 这个位图 16 字节 > (integerf 16)还可以使用 GETRANGE 命令获取位图的其中一部分字节:
GETRANGE 32bit-ints 0 3诸如此类