Redis bitmap

什么是Redis bitmap

Redis 的 bitmap 是通过一个 bit 位来表示某个元素对应的值或者状态,其中的 key 就是对应元素本身。Bitmaps 本身不是一种数据结构,实际上它就是字符串(key 对应的 value 就是上图中最后的一串二进制),但是它可以对字符串的位进行操作。

Bitmaps 单独提供了一套命令,所以在 Redis 中使用 Bitmaps 和使用字符串的方法不太相同。可以把 Bitmaps 想象成一个以 “位” 为单位的数组,数组的每个单元只能存储 0 和 1,数组的下标在 Bitmaps 中叫做偏移量。

bitmap特点

Bitmaps 本身不是一种数据结构, 实际上它就是字符串,但是它可以对字符串的位进行操作。

Bitmaps 单独提供了一套命令, 所以在 Redis 中使用 Bitmaps 和使用字符串的方法不太相同。 可以把 Bitmaps 想象成一个以位为单位的数组, 数组的每个单元只能存储 0 和 1,数组的下标在 Bitmaps 中叫做偏移量。

bitmap优缺点

优点

  1. 基于最小的单位 bit 进行存储,所以非常省空间。
  2. 设置时候时间复杂度 O(1)、读取时候时间复杂度 O(n),操作是非常快的。
  3. 二进制数据的存储,进行相关计算的时候非常快。
  4. 方便扩容。

限制

redis 中 bit 映射被限制在 512MB 之内,所以最大是 2^32 位。建议每个 key 的位数都控制下,因为读取时候时间复杂度 O(n),越大的串读的时间花销越多。

bitmap命令详解

设置值SETBIT

语法

SETBIT key offset value

说明

对 key 所储存的字符串值,设置或清除指定偏移量上的位(bit)。位的设置或清除取决于 value 参数,可以是 0 也可以是 1 。当 key 不存在时,自动生成一个新的字符串值。

字符串会进行伸展(grown)以确保它可以将 value 保存在指定的偏移量上。当字符串值进行伸展时,空白位置以 0 填充。offset 参数必须大于或等于 0 ,小于 2^32 (bit 映射被限制在 512 MB 之内)。对使用大的 offset 的 SETBIT 操作来说,内存分配可能造成 Redis 服务器被阻塞。

返回值

字符串值指定偏移量上原来储存的位(bit)。

示例

26_redis bitmaps.png

从以上示例我们可以看出,我们使用 SETBIT 命令可以设置某个位的值,如果没有设置值的位默认值为 0,同时,SETBIT 只能设置 0 和 1,我们设置了 2,提示我们出错了。

获取值GETBIT

语法

GETBIT key offset

说明

对 key 所储存的字符串值,获取指定偏移量上的位(bit)。当 offset 比字符串值的长度大,或者 key 不存在时,返回 0。

返回值

字符串值指定偏移量上的位(bit)。

示例

27_redis bitmaps.png

从以上示例我们可以看出,我们使用 SETBIT 命令可以设置某个位的值,使用 GETBIT 可以获取某个位的值。

获取值为1个数BITCOUNT

语法

BITCOUNT key start

说明

计算给定字符串中,被设置为 1 的比特位的数量。一般情况下,给定的整个字符串都会被进行计数,通过指定额外的 start 或 end 参数,可以让计数只在特定的位上进行。

start 和 end 参数的设置和 GETRANGE 命令类似,都可以使用负数值: 比如 -1 表示最后一个字节,-2 表示倒数第二个字节,以此类推。不存在的 key 被当成是空字符串来处理,因此对一个不存在的 key 进行 BITCOUNT 操作,结果为 0。

返回值

被设置为 1 的位的数量。

示例

28_redis bitmaps.png

从以上示例我们可以看出,我们使用 SETBIT 命令设置某个位的值,最后我们使用 BITCOUNT 可以获取被设置为 1 的位的个数。

注意

BITCOUNT 命令返回的是一个指定 key 中位的值为 1 的个数(是以 byte 为单位不是 bit)”,这就是坑的所在。所以 bitcount 0 0 那么就应该是第一个 “字节” 中 1 的数量的,注意是字节,第一个字节也就是 1,2,3,4,5,6,7,8 这八个位置上。

bitmap运算BITOP

语法

BITOP operation destkey key [key ...]

说明

对一个或多个保存二进制位的字符串 key 进行位元操作,并将结果保存到 destkey 上。operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种:

  • BITOP AND destkey key [key …] ,对一个或多个 key 求逻辑并,并将结果保存到 destkey。
  • BITOP OR destkey key [key …] ,对一个或多个 key 求逻辑或,并将结果保存到 destkey。
  • BITOP XOR destkey key [key …] ,对一个或多个 key 求逻辑异或,并将结果保存到 destkey。
  • BITOP NOT destkey key ,对给定 key 求逻辑非,并将结果保存到 destkey。

除了 NOT 操作之外,其他操作都可以接受一个或多个 key 作为输入。当 BITOP 处理不同长度的字符串时,较短的那个字符串所缺少的部分会被看作 0。空的 key 也被看作是包含 0 的字符串序列。

返回值

保存到 destkey 的字符串的长度,和输入 key 中最长的字符串长度相等。

示例

AND 操作具体如下:

29_redis bitmaps.png

从以上示例我们可以看出,使用 BITOP 可以操作两个或者多个 bitmaps,并且只有两位都是 1 时,结果对应的位才为 1。

注意

BITOP 的复杂度为 O(N) ,当处理大型矩阵(matrix)或者进行大数据量的统计时,最好将任务指派到附属节点(slave)进行,避免阻塞主节点。

计算偏移量

语法

BITPOS key bit [start][end]

说明

返回字符串里面第一个被设置为 1 或者 0 的 bit 位。返回一个位置,把字符串当做一个从左到右的字节数组,第一个符合条件的在位置 0,其次在位置 8,等等。

GETBIT 和 SETBIT 相似的也是操作字节位的命令。默认情况下整个字符串都会被检索一次,只有在指定 start 和 end 参数(指定 start 和 end 位是可行的),该范围被解释为一个字节的范围,而不是一系列的位。所以 start=0 并且 end=2 是指前三个字节范围内查找。

注意,返回的位的位置始终是从 0 开始的,即使使用了 start 来指定了一个开始字节也是这样。和 GETRANGE 命令一样,start 和 end 也可以包含负值,负值将从字符串的末尾开始计算,-1 是字符串的最后一个字节,-2 是倒数第二个,等等。不存在的 key 将会被当做空字符串来处理。

返回值

命令返回字符串里面第一个被设置为 1 或者 0 的 bit 位。如果我们在空字符串或者 0 字节的字符串里面查找 bit 为 1 的内容,那么结果将返回 -1。如果我们在字符串里面查找 bit 为 0 而且字符串只包含 1 的值时,将返回字符串最右边的第一个空位。

如果有一个字符串是三个字节的值为 0xff 的字符串,那么命令 BITPOS key 0 将会返回 24,因为 0-23 位都是 1。基本上,我们可以把字符串看成右边有无数个 0。然而,如果你用指定 start 和 end 范围进行查找指定值时,如果该范围内没有对应值,结果将返回 -1。

示例

30_redis bitmaps.png

我们首先使用了 SETBIT 设置位的值,接着,我们分别使用了 BITPOS 获取了第一个 1 的偏移量和第一位为 0 的偏移量,我们可以看出,第一个为 1 的偏移量就是我们设置的 100.

bitmap使用场景

视频属性的无限延伸

需求描述

一个拥有亿级数据量的短视频 app,视频存在各种属性(是否加锁、是否特效等等),需要做各种标记。

可能想到的解决方案

  1. 存储在 mysql 中,肯定不行,一个是随着业务增长属性一直增加,并且存在有时间限制的属性,直接对数据库进行加减字段是非常不合理的做法。即使是存在一个字段中用 json 等压缩技术存储也存在读效率的问题,并且对于大几亿的数据来说,废弃的字段回收起来非常麻烦。
  2. 直接记录在 redis 中,根据业务属性+uid 为 key 来存储。读写效率角度没毛病,但是存储的角度来说key的数据量都大于 value 了,太耗费空间了。即使是用 json 等压缩技术来存储。也存在问题,解压需要时间,并且大几亿的数据回收也是难题。

设计方案

使用 redis 的 bitmap 进行存储。key 由属性 id+视频分片 id 组成。value 按照视频 id 对分片范围取模来决定偏移量 offset。10 亿视频一个属性约 120m 还是挺划算的。

用户在线状态

需求描述

需要对子项目提供一个接口,来提供某用户是否在线?

设计方案

使用 bitmap 是一个节约空间效率又高的一种方法,只需要一个 key,然后用户 id 为偏移量 offset,如果在线就设置为 1,不在线就设置为 0,3 亿用户只需要 36MB 的空间。

统计活跃用户

需求描述

需要计算活跃用户的数据情况。

设计方案

使用时间作为缓存的 key,然后用户 id 为 offset,如果当日活跃过就设置为 1。之后通过 bitOp 进行二进制计算算出在某段时间内用户的活跃情况。

用户签到

需求分析

用户需要进行签到,对于签到的数据需要进行分析与相应的运运营策略。

设计方案

使用 redis 的 bitmap,由于是长尾的记录,所以 key 主要由 uid 组成,设定一个初始时间,往后每加一天即对应 value 中的 offset 的位置。