如果我们需要记录用户在一年时间内每天是否登陆我们的应用这一需求该如何完成呢?如果使用普通的 key/value，每个用户要记录 365 个，当用户上亿的时候，需要的存储空间是惊人的。所幸，Redis 提供了位图数据结构，这样每天的登陆记录只占据一个位，365 天就是 365 个位，46 个字节 就可以完全容纳下，这就大大节约了存储空间。
请输入图片描述

基本操作

      Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组。

  • SETBIT:为位数组指定偏移量上的二进制位设置值，偏移量从0开始计数，二进制位的值只能为0或1。返回原位置值。
  • GETBIT:获取指定偏移量上二进制位的值。
  • BITCOUNT:统计位数组中值为1的二进制位数量。
  • BITOP:对多个位数组进行按位与、或、异或运算。

127.0.0.1:6379> SETBIT first 0 1    # 0000 0001
(integer) 0
127.0.0.1:6379> SETBIT first 3 1    # 0000 1001
(integer) 0
127.0.0.1:6379> SETBIT first 0 0    # 0000 1000
(integer) 1

127.0.0.1:6379> GETBIT first 0
(integer) 0
127.0.0.1:6379> GETBIT first 3
(integer) 1

127.0.0.1:6379> BITCOUNT first      # 0000 1000
(integer) 1
127.0.0.1:6379> SETBIT first 0 1    # 0000 1001
(integer) 0
127.0.0.1:6379> BITCOUNT first      # 0000 1001
(integer) 2
127.0.0.1:6379> SETBIT first 1 1    # 0000 1011
(integer) 0
127.0.0.1:6379> BITCOUNT first      # 0000 1011
(integer) 3

127.0.0.1:6379> SETBIT x 3 1        
(integer) 0
127.0.0.1:6379> SETBIT x 1 1        
(integer) 0
127.0.0.1:6379> SETBIT x 0 1        # 0000 1011
(integer) 0
127.0.0.1:6379> SETBIT y 2 1        
(integer) 0
127.0.0.1:6379> SETBIT y 1 1        # 0000 0110
(integer) 0
127.0.0.1:6379> SETBIT z 2 1        
(integer) 0
127.0.0.1:6379> SETBIT z 0 1        # 0000 0101
(integer) 0

127.0.0.1:6379> BITOP AND andRes x y z    #0000 0000
(integer) 1
127.0.0.1:6379> BITOP OR orRes x y z      #0000 1111
(integer) 1
127.0.0.1:6379> BITOP XOR x y z           #0000 1000
(integer) 1

# 对给定的位数组进行按位取反
127.0.0.1:6379> SETBIT value 0 1
(integer) 0
127.0.0.1:6379> SETBIT value 3 1            #0000 1001
(integer) 0
127.0.0.1:6379> BITOP NOT notValue value    #1111 0110
(integer) 1

底层结构

      Redis使用字符串对象(SDS)来表示位数组，因为字符串对象使用的SDS数据结构是二进制安全的，所以程序可以直接使用SDS结构来保存位数组，并使用SDS结构的操作函数来处理位数组。
      如下展示了一个用SDS表示的一字节长的位数组：

  • redisObject.type的值为REDIS_STRING,表示这是一个字符串对象
  • sdshdr.len的值为1，表示这个SDS保存了一个一字节长的位数组
  • buf数组中的buf[0]字节保存了一字节长的位数组
  • buf数组中的buf[1]字节保存了SDS程序自动追加到值的末尾空字符'0'

请输入图片描述

      buf数组的每个字节都用一行来表示，每个格子buf[i]表示这是buf数组的哪个字节，而buf[i]之后的8个格子则代表这个字节中的八个位。

注意:buf数组保存的位数组为01001101,和它的存储顺序是完全相反的。这有好处，继续看哦!

      为了看官能更好的理解位数组的表示，下面展示一个3字节的位数组：

  • 位数组由buf数组中的buf[0]、buf[1]、buf[2]三个字节保存。真实数据为1111 0000 1100 0011 1010 0101

请输入图片描述

GETBIT的实现

      GETBIT用于返回位数组在偏移量上的二进制位的值。
      GITBIT命令的执行过程如下：

  1. 计算byte = $\lfloor offset\div8 \rfloor$，byte值表示指定的offset位于位数组的那个字节(就是计算在那个buf[i]中的i)
  2. 指定buf[i]中的i了，接下来就要计算在这8个字节中的第几位呢？使用bit = (offset mod 8)+1计算可得
  3. 根据byte和bit在bitarray中定位到目标值返回即可

举个栗子

      array表示上图中的三个字节位数组。以GETBIT array 3为例：

  1. byte = $\lfloor 3 \div8 \rfloor$得到值为0，说明在buf[0]上
  2. bit = (3 mod 8 ) + 1得到值为4
  3. 定位到buf[0]字节的从左至右第4个位置上

请输入图片描述

      因为GETBIT命令执行的所有操作都可以在常数时间内完成，所以该命令的算法复杂度为O(1)。

SETBIT的实现

      SETBIT用于将位数组在偏移量的二进制位的值设为value，并向客户端返回旧值。
      SITBIT命令的执行过程如下：

  1. 计算len = $\lfloor offset\div8 \rfloor$ + 1，len值记录了保存offset偏移量指定的二进制位至少需要多少字节
  2. 检查位数组的长度是否小于len，如果是的话，将SDS的长度扩展为len字节,并将所有新扩展空间的二进制位设置为0
  3. 计算byte = $\lfloor offset\div8 \rfloor$，byte值表示指定的offset位于位数组的那个字节(就是计算在那个buf[i]中的i)
  4. 使用bit = (offset mod 8)+1计算可得目标buf[i]的具体第几位
  5. 根据byte和bit的值，首先保存oldValue，然后将新值value设置到目标位上
  6. 返回旧值

      因为SETBIT命令执行的所有操作都可以在常数时间内完成，所以该命令的算法复杂度为O(1)。

举个栗子

      array表示上图中的三个字节位数组。以SETBIT array 10 1为例：

  1. len = $\lfloor 10 \div8 \rfloor$ + 1得到值为2，说明至少需要2字节长的位数组
  2. 检查是否需要扩容，不需要
  3. 计算byte = 1
  4. 计算bit = 3
  5. 保存oldValue，设置新值
  6. 返回oldValue

请输入图片描述

举个栗子2.0

      假设目标位数组为1字节长度。执行SETBIT array 12 1，执行如下：

  1. len = $\lfloor 12 \div8 \rfloor$ + 1得到值为2，说明至少需要2字节长的位数组
  2. 检查是否需要扩容，需要呀！程序会要求将位数组的长度扩展为2,。不过尽管程序只要求2字节长的位数组，但SDS的空间预分配策略会为SDS额外多分配2字节的未使用空间，在加上为保存空字符而额外分配的1字节，扩展后buf数组的实际长度为5字节。
  3. 计算byte = 1
  4. 计算bit = 5
  5. 保存oldValue，设置新值
  6. 返回oldValue

请输入图片描述

有个很NICE的现象，由于我们采用逆序保存位数组，所以在扩容后我们不需要改动旧数据。如果不使用逆序那还要移动旧数据呢！

BITCOUNT的实现

      BITCOUNT命令用于统计给定位数组中值为1的二进制位的数量。功能似乎不复杂，但实际上要高效地实现这个命令并不容易，需要用到一些精巧的算法。

暴力遍历

      实现BITCOUNT命令最简单直接的方法，就是遍历位数组中的每个二进制位，并在遇到值为1的二进制位时将计数器加1。

小数据量还好，大数据量直接PASS!

查表法

      对于一个有限集合来说，集合元素的排列方式是有限的，并且对于一个有限长度的位数组来说，它能表示的二进制位排列也是有限的。根据这个原理，我们可以创建一个表，表的键为某种排列的位数组，而表的值则是相应位数组中值为1的二进制位的数量。
      对于8位长的位数组来说，我们可以创建下表，通过这个表格我们可以一次从位数组中读入8位，然后根据这8位的值进行查表，直接知道这个值包含了多少个1。
请输入图片描述

可惜，查表法耗内存呀!

二进制位统计算法:variable-precision SWAR算法

      统计一个位数组中非0二进制位的数量在数学上被称为"计算汉明重量"。目前已知效率最好的通用算法为variable-precision SWAR算法，该算法通过一系列位移和位运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要使用任何额外的内存。

uint32_t swar(uint32_t i) {
    i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
    i = (i*(0x01010101) >> 24);
    return i;
}

以下是调用此算法的步骤：

  1. 步骤一计算出的值i的二进制表示可以按每两个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量；
  2. 步骤二计算出的值i的二进制表示可以按每四个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量；
  3. 步骤三计算出的值i的二进制表示可以按每八个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量；
  4. 步骤四的i*0x01010101语句计算出bitarray的汉明重量并记录在二进制位的最高八位，而>>24语句则通过右移运算，将bitarray的汉明重量移动到最低八位，得出的结果就是bitarray的汉明重量。

举个栗子

      对于调用swar(0x3A70F21B)，步骤一将计算出值0x2560A116,这个值表的每两个二进制位的十进制表示记录了0x3A70F21B每两个二进制位的汉明重量。
请输入图片描述

      步骤二将计算出值0x22304113,这个值表的每四个二进制位的十进制表示记录了0x3A70F21B每四个二进制位的汉明重量。
请输入图片描述

      步骤三将计算出值0x4030504,这个值表的每八个二进制位的十进制表示记录了0x3A70F21B每八个二进制位的汉明重量。
请输入图片描述

      步骤四首先计算0x4030504 * 0x01010101 = 0x100C0904，将汉明重量聚集到二进制位的最高八位。
请输入图片描述

      之后计算0x100C0904 >> 24，将汉明重量移动到低八位，得到最终值0x10,即十进制16。

如果您是Java程序员，可以去看看Integer.bitCount方法，一样哦!

Redis的实现

      在Redis中BITCOUNT的实现用到了查表法和variable-precision SWAR两种算法。
      在执行BITCOUNT命令时，程序会根据未处理的二进制位的数量来决定使用哪种算法：

  • 如果未处理的二进制位的数量大于等于128，那么程序使用variable-precision SWAR算法来计算二进制位的汉明重量
  • 如果未处理的二进制位的数量小于128，那么程序使用查表法来计算二进制位的汉明重量。

版权属于：带翅膀的猫

本文链接：https://www.chengpengper.cn/archives/107/

转载时须注明出处及本声明

Last modification：February 27th, 2024 at 05:23 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏