Redis Bitmap

10 minute
4549 words
Tags:
#Redis

Bitmap 位图

Redis 的位图 bitmap 是由多个二进制位组成的数组, 数组中的每个二进制都有与之对应的偏移量(索引), 用户通过这些偏移量可以对位图中指定的一个或多个二进制位进行操作.

Redis 为位图提供了一系列操作命令, 通过这些命令, 用户可以:

SETBIT: 设置二进制位的值

REDIS
SETBIT bitmap offset value
Click to expand and view more

为位图指定偏移量上的二进制位设置值, 该命令会返回二进制位被设置之前的旧值作为结果.

当执行 SETBIT 时, 如果位图不存在, 或者位图当前的大小无法满足用户想要执行的设置操作, 那么 Redis 将对被设置的位图进行扩展, 使得位图可以满足用户的设置请求. 由于位图的扩展以字节为单位, 所以扩展后的位图包含的二进制数量可能会比用户要求的稍多一些. 且在扩展的同时, 会将未设置的二进制位初始化为 0.

与一些可以使用负数的 Redis 命令不同, SETBIT 命令只能使用正数偏移量, 尝试输入负数作为偏移量将引发一个错误

GETBIT: 获取二进制位的值

REDIS
GETBIT bitmap offset
Click to expand and view more

与 SETBIT 命令一样, GETBIT 命令也只能接受正数作为偏移量.
对于偏移量超过位图索引的命令, GETBIT 命令将返回 0 作为结果.

BITOCUNT: 统计被设置的二进制数量

REDIS
BITCOUNT key
Click to expand and view more

对于值为 10010100 的位图 bitmap001, 可以通过执行以下命令来统计有多少个二进制位被设置成了1:

REDIS
BITCOUNT bitmap001
(integer) 3 -- 这个位图有 3 个二进制位为 1
Click to expand and view more

此外, 还可以只统计位图指定直接范围内的二进制位

REDIS
BITCOUNT bitmap [start end]
Click to expand and view more

start 参数和 end 参数与本章之前介绍的 SETBIT 命令和 GETBIT 命令的 offset 参数并不相同, 这两个参数用来指定字节偏移量而不是二进制位偏移量.

例如通过以下命令计算位图 bitmap003 中第一个字节中 有多少个 1:

REDIS
BITCOUNT bitmap003 0 0
Click to expand and view more

BITCOUNT 命令的 start 参数和 end 参数的值不久可以是正数, 还可以是负数:

REDIS
BITCOUNT bitmap003 -1 -1
Click to expand and view more

上面命令统计位图 bitmap003 最后一个字节中 1 的数量.

示例: 用户行为记录器

为了分析用户行为并借此改善服务质量, 很多网站都会记录用户在网站的一举一动. 为此, 可以使用集和 Set 或者 HyperLogLog 来记录所有执行了指定行为的用户, 但这种做法有两种缺陷:

为了尽可能节约内存, 并精确记录每个用户是否执行了指定行为, 可以使用以下方法:

PYTHON
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())
Click to expand and view more

BITPOS: 查找第一个指定的二进制值

REDIS
BITPOS bitmap value
Click to expand and view more

例如, 通过下面命令, 可以知道位图 bitmap003 第一个被设置为 1 的二进制位所在的偏移量(索引):

REDIS
BITPOS bitmap003 1
(integer) 0 -- 位图第一个被设置位 1 的二进制位的偏移量是 0
Click to expand and view more

默认情况下, BITPOS 会查找所有二进制位, 在有需要的情况下, 用户也可以通过可选的 start 参数和 end 参数, 让 BITPOS 命令只在指定字节范围内的二进制位中进行查找:

REDIS
BITPOS bitmap value [start end]
Click to expand and view more

返回结果为查找到位的整体偏移量, 而不是在 start 和 end 内的偏移量.

和 BITCOUNT 命令以, BITPOS 命令的 start 和 end 参数也可以是负数.

比如, 下面代码就展示了如何在位图 bitmap003 的倒数第一个字节中, 查找第一个值位 0 的二进制位:

REDIS
BITPOS bitmap003 0 -1 -1
(integer) 17
Click to expand and view more

当用户尝试对一个不存在的位图或者一个唯有位都位 0 的位图, 执行查找值位 1 的二进制位时, BITPOS 命令将返回 -1 作为结果:

REDIS
BITPOS not-exists-bitmap 1 -- 在不存在的位图中查找
(integer) -1

BITPOS all-0-bitmap 1 -- 在一个所有位都被设置为 0 的位图查找
(integer) -1
Click to expand and view more

BITOP: 执行二进制位运算

用户可以通过 BITOP 命令, 对一个或多个位图执行指定的二进制位运算, 并将运算结果存储到指定的键中

REDIS
BITOP operation result_key bitmap [bitmap ...]
Click to expand and view more

其中, operation 参数值可以是 AND, OR, XOR, NOT 中的任意一个, 这 4 个值分别对应逻辑并、逻辑或、逻辑异或和逻辑非4种运算, 其中 AND, OR, XOR 这 3 种运算允许用户使用任意数量的位图作为输入, 而 NOT 只允许一个位图作为输入. BITOP 命令这将计算结果存储到指定键中后, 会返回被存储位图的字节长度.

例如, 通过以下命令, 对位图 bitmap001, bitmap002, bitmap003 执行逻辑并运算, 然后将结果存储到键 and_result 中:

PLAINTEXT
BITOP ADD and_result bitmap001 bitmap002 bitmap003
(integer) 3 -- 运算结果 and_result 位图的长度为 3 字节
Click to expand and view more

当 BITOP 命令在对两个长度不同的位图执行运算时, 会将长度较短的那个位图中不存在的二进制位看作 0.

BITFIELD: 在位图中存储整数值

BITFIELD 命令允许用户在位图中的任意区域 field 存储指定长度的整数值, 并对这些整数值执行加法或减法操作.
BITFIELD 命令支持 SET, GET, INCRBY, OVERFLOW 这 4 个子命令, 接下来将分别介绍这些子命令.

示例: 紧凑计数器

PYTHON
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,
        )
Click to expand and view more

假如要为一家游戏公司创建一个记录每个玩家每月登陆数的计数器, 按照一个月 30 天, 一天登陆 2~3 次的频率来计算, 一个普通玩家一个月的登陆次数通常不会超过 100 次. 对于这么小的数值, 使用 long 类型进行存储将浪费大量空间, 因此可以使用紧凑计数器来存储用户登陆次数:

PYTHON
client = Redis()
counter = CompactCounter(client, "login_count", 16, False) # 建立计数器
print(counter.increase(10086)) # 记录第 1 次登陆
print(counter.increase(10086)) # 再记录第 1 次登陆
print(counter.get(10086)) # 获取登陆次数
Click to expand and view more

Related Posts

Start searching

Enter keywords to search articles

↑↓
↵
ESC
⌘K Shortcut