星星点灯
0%

Redis系列第四篇之Bitmap

发表于 更新于 分类于 本文字数： 4.2k 阅读时长 ≈ 4 分钟

前言

Bitmap实际上并不是一种数据类型，而是定义在String类型上的面向位的操作。因为String是二进制安全的并且最大长度为512MB，所以String可以建立2^32个不同的位。位操作被分为两种：

  • 常数时间的单独一个位的操作，比如设置某个位的值为1或者0，或者或者某个位的值
  • 对一组bit位的操作，例如在给定的位范围内计算被设置的bit数量（如人口统计）

Bitmap最大的一个优点是当存储信息时可以节省极大的空间。例如一个系统中的用户ID由递增的ID表示，只需使用512MB的内存，就可以记住40亿用户的单比特信息（例如，知道用户是否想收到通讯）。

Bitmap使用SETBIT和GETBIT命令设置和获取位的值：

1
2
> SETBIT key 10 1
> GETBIT key 10

SETBIT命令第一个参数表示需要被设置的位，第二个参数表示需要设置的值（1或者0）。需要注意的是，当被设置的位超过字符串当前的长度时，SETBIT命令将会自动增加字符串的长度。GETBIT返回指定位上的值，对于超过字符串当前长度范围的位，总是被视为0。

Bitmap有三个命令是基于对一组位进行操作的命令:

  1. BITOP：在不同字符串之间执行逐位的操作，Redis提供的操作有的：AND，OR，XOR
  2. BITCOUNT：统计值为1的位数
  3. BITPOS：获取第一个被设置位0或者1的位

BITPOS和BITCOUNT都可以对字符串的字节范围进行操作，Bitmap的常见使用场景有：

  • 各种实时分析
  • 存储与对象ID相关的布尔信息

比如想统计网站最长的用户连续访问天数，可以使用Bitmap，每个位的值作为该天是否访问网站的标志（第一位表示第一天，第二位表示第二天，以此类推），每当用户访问网站时可以使用SETBIT设置该天对应的位为1，最后统计连续设置为1的位的数量即可。使用BITCOUNT可以统计出用户访问网站的天数，使用BITPOS即可统计出最长的连续访问天数。为了分片数据集，最好避免使用大键，可以让每个键存储M个位，将（位数/M）的值与键名关联，将（位数%M）可以获取位数处于键内的位置。

下面是Bitmap相关命令。

BITCOUNT key [ start end [ BYTE | BIT]]

  • 可用版本： v2.6.0开始
  • 历史： 从v7.0.0开始增加BYTE|BIT选项
  • 时间复杂度： O(N)
  • 解释： 计算字符串中被设置为1的位数。默认情况下，字符串中所有的字节都会被检查，可以通过start和end选项指定命令仅执行于字符串的某个范围内（start和end可以为正数或者负数，整数表示以从头到尾的顺序计算，反之负数表示丛尾到头的顺序计算，-1表示最后一位，-2表示倒数第二位等等）。不存在的key被视为空字符串，命令将返回0。默认情况下，start和end选项指明的是字节范围，调用方可以通过BIT选项来指明位范围。
  • 返回值： Integer（整型），返回被设置为1的位数。

BITFIELD key GET encoding offset | [OVERFLOW WRAP | SAT | FAIL] SET encoding offset value | INCRBY encoding offset increment [ GET encoding offset | [OVERFLOW WRAP | SAT | FAIL] SET encoding offset value | INCRBY encoding offset increment …]

  • 可用版本： v3.2.0开始
  • 时间复杂度： 对于每个子命令的时间复杂度为O(1)
  • 解释： 此命令将Redis字符串视为一个bit数组，可以处理不同比特宽度的特定整数字段和任意非（必要）对齐的偏移，例如可以将偏移量为1234的有符号5位整数设置为一个特定的值，从偏移量4567检索到一个31位无符号整数，同样此命令也可以处理指定偏移量整数的增量和减量，提供用户可以配置的保证和明确指定的上溢和下溢行为。BITFIELD可以在一次调用中使用多个位字段，并返回一个回复数组，每个数组对应相应顺序的操作结果。
  • 选项（子命令）说明：
    1. SET encoding offset value 设置指定位字段同时返回这些字段的旧值
    2. GET encoding offset 返回指定位字段的值
    3. INCRBY encoding offset increment 增加或者减少（如果给定的增量为负数）指定位字段同时返回操作后的新值
    4. OVERFLOW [WARP|SAT|FAIL] 此子命令通过设置溢出行为来改变连续的INCRBY和SET子命令溢出时的调用行为，需要注意的是OVERFLOW只影响子命令列表中位于其之后的SET和INCRBY子命令，直到下一个OVERFLOW语句。
      • WARP： 针对有符号和无符号的整数，在无符号整数的情况下，WARP就像对整数所能包含的最大值进行模数化操作（C的标准行为）。对于有符号的整数，WARP意味着溢出是朝着最负的值重新开始的，而溢出是朝着最正的值重新开始的，如果一个i8整数被设置为127，将其递增1会产生-128
      • SAT： 使用饱和算法，在下溢时，值被设置为最小的整数值，而在上溢时，则设置为最大的整数值。例如，一个i8整数从值120开始增量为10，将导致值为127，进一步增量将始终保持在127。同样的情况也发生在下溢上，但是数值会被封锁在最负的数值上
      • FAIL： 不会对检测到的上溢或下溢执行任何操作。相应的返回值设置为NULL以向调用者发出条件信号
    5. 整数编码（encoding）的可选值有：i表示有符号整数，i16表示有符号的16位整数；u表示无符号整数，u8表示无符号的8位整数，有符号整数支持的编码最多为64位，无符号整数最多支持63位。无符号整数的这种限制是由于目前Redis协议无法返回64位无符号整数作为回复。
  • 命令使用实例； 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    >   BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
      1) (integer) 1
      2) (integer) 1
    >   BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
      1) (integer) 2
      2) (integer) 2
    >   BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
      1) (integer) 3
      2) (integer) 3
    >   BITFIELD mykey incrby u2 100 1 OVERFLOW SAT incrby u2 102 1
      1) (integer) 0
      2) (integer) 3
  • 返回值： Array（数组），返回每个子命令的操作结果，结果顺序与子命令顺序一致。OVERFLOW返回值为nil

BITFIELD_RO key GET encoding offset [ encoding offset …]

  • 可用版本： v6.2.0开始
  • 时间复杂度： O(N)，N为子命令数量
  • 解释： BITFIELD命令的只读形式，不同的是BITFIELD_RO只接受GET子命令，并且可以安全在只读副本集中。
  • 返回值： Array（数组），返回每个子命令的操作结果，结果顺序与子命令顺序一致

BITOP operation destkey key [key …]

  • 可用版本： v2.6.0开始
  • 时间复杂度： O(N)
  • 解释： 在多个key之间执行逐位地进行位操作，并且将结果存储进destkey中，BITOP支持的位操作命令有：AND、OR、XOR、NOT（其中NOT操作只接受一个key）：
    • BITOP AND destkey srckey1 srckey2 srckey3 … srckeyN
    • BITOP OR destkey srckey1 srckey2 srckey3 … srckeyN
    • BITOP XOR destkey srckey1 srckey2 srckey3 … srckeyN
    • BITOP NOT destkey srckey
      命令执行时，对于长度不相同的字符串来说，Redis将会用0进行填充，使其长度达到最长字符串的长度；同时对于不存在的key，Redis也将其视为全为0的字符串
  • 返回值： Integer（整型），返回存储在目标键中的字符串长度，该字符串长度等于输入键中对应的字符串中长度最长的值

BITPOS key bit [ start [ end [ BYTE | BIT]]]

  • 可用版本： v2.8.7开始
  • 历史： 从v7.0.0开始增加BYTE和BIT选项
  • 时间复杂度： O(N)
  • 解释： 返回字符串中第一个被设置为0或者1的位的位置。此命令将字符串视为从左到右的位数组，其中第一个字节的最高有效位在位置0，第二个字节的最高有效位在位置8，依此类推。
    默认情况下，字符串中包含的所有字节都将被检查。调用方可以通过参数start和end，指明只在指定的区间内查找位（也可以只传递start，操作将假定end是字符串的最后一个字节）。默认情况下，范围被解释为一个字节的范围，而不是一个比特的范围，所以start=0和end=2意味着查看前三个字节；可以使用可选的BIT修饰符来指定应将范围解释为位范围，当使用BIT选项时，start=0和end=2表示看前三位。
    不存在的key将被视为空字符串；start和end的值既可以是正数也可以是负数，正数表示从正序，反之为倒序。
  • 返回值： Integer（整型），返回指定范围内第一个0或者1所在的位或者字节数。

GETBIT key offset

  • 可用版本： v2.2.0开始
  • 时间复杂度： O(1)
  • 解释： 返回存储在位置offset处的位值。当offset超过字符串长度时，超出部分的字符串被假定为一个位值为0的连续空间；当key不存在时，它被假定为一个空字符串，因此偏移量总是超出范围，并且该值也被假定为一个以0填充的连续空间
  • 返回值： Integer（整型），返回存储在位置offset处的值

SETBIT key offset value

  • 可用版本： v2.2.0开始
  • 时间复杂度： O(1)
  • 解释： 设置或者清除offset处的位值，设置的值可以是0或者1。当key不存在时，将会创建一个新的字符串值，字符串的长度会自动增长（填充0）以确保它可以达到偏移量处的位置。偏移量参数必须大于或等于0，并且小于 2^32（因为Redis字符串长度限制位512MB）
  • 返回值： Integer（整型），返回存储在offset的旧值

参考资料

Redis Bitmap