Redis 二进制位数组

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

其中, SETBIT命令用于为位数组指定偏移量上的二进制设置值, 位数组的偏移量从0开始计数, 而二进制位的值则可以是0或者1。

GETBIT命令则用于获取位数组指定偏移量上的二进制位的值.

BIGCOUNT命令用于统计维数组里面, 值为1的二进制位的数量.

BITOP命令既可以对多个位数组进行按位与(and),按位或(or),按位异或(xor),取反操作(not)运算

位数组的表示

Redis使用字符串对象来表示位数组, 因为字符串对象使用的SDS数据结构是二进制安全的, 所以程序可以直接使用SDS结构来保存位数组, 并使用SDS结构的操作函数来处理位数组.

在使用redisObject保存位数组时, buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的. 例如: buf[0] 字节中, 各个位的值分别是: 1,0,1,1,0,0,1,0, 这表示buf[0]字节保存的位数组为0100 1101. 使用逆序来保存为数组可以简化SETBIT命令的实现。

GETBIT 命令的实现

GETBIT命令用于返回位数组bitarray在offset偏移量上的二进制位的值:

GETBIT <bitarray> <offset>

GETBIT命令的执行过程如下:

计算byte=[offset / 8]0,byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节.
计算bit=(offset mod 8) + 1bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位
根据byte值和bit值, 在位数组bitarray中定位offset偏移量指定的二进制位, 并返回这个位的值.

GETBIT执行步骤

GETBIT <bitarray> 3

将执行以下操作:

[3/8]的值为0
(3 mod 8) + 1 的值为4
定位到buf[0]字节上面, 然后取出该字节上的第四个二进制位的值
向客户端返回二进制位上的1

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

SETBIT 命令的实现

SETBIT用于将数组bitarray在offset偏移量上的二进制位的值设置为value, 并向客户端返回二进制位被设置之前的旧值:

SETBIT <bitarray> <offset> <value>

以下是SETBIT命令的执行过程:

计算len=[offset / 8] + 1, len值记录了保存offset偏移量指定的二进制位至少需要多少字节.
检查bitarray键保存的位数组(也即是SDS)的长度是否小于len, 如果是的话, 将SDS的长度扩展为len字节, 并将所有新扩展空间的二进制位的值设置为0(此处还是会遵循SDS的扩展原则)
计算byte=[offset / 8],byte值记录了offset偏移量指定的二进制位保存在维数组的哪个字节
计算 bit=(offset mod 8) + 1,bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位.
根据byte值和bit值, 在bitarray键保存的维数组中定位offset偏移量指定的二进制位, 首先将指定二进制位在值保存在oldvalue变量, 然后将新值value设置为这个二进制位的值
向客户端返回oldvalue变量的值.

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

为什么SETBIT采用逆序存储???

BIGCOUNT 命令的实现

BITCOUNT命令用于统计给定位数组中, 值为1的二进制位的数量。

二进制位统计算法(1): 遍历算法

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

尽管遍历算法对单个二进制位的检查可以在很短的时间内完成, 但是重复执行上亿次这种检查肯定不是一个搞笑程序应有的表现, 为了让BITCOUNT命令的实现尽可能地高效, 程序必须尽可能地增加每次检查所能处理的二进制位的数量，从而减少检查操作执行的次数.

二进制统计算法(2): 查表算法

优化检查操作的一个办法是使用查找表:

对于一个有限集合来说, 集合元素的排列方式是有限的
而对于一个有限长度的位数组来说, 它能表示的二进制位排列也是有限的

根据这个原理,我们可以创建一个表, 表的键为某种排列的位数组, 而表的值则是相应位数组中, 值为1的二进制位的数量。

创建了这种表之后, 我们可以根据输入的位数组进行查表, 在无须对位数组的每个位进行检查的情况下, 直接知道这个位数组包含了多少个值为1的二进制位。

存在的问题

因为查表法是典型的空间换时间策略, 算法在计算方面节约的时间是通过花费额外的内存换取而来的, 节约的时间越多, 花费的内存越大
除了内存大小的问题之外, 查表法的效果还会受到CPU缓存的限制：对于固定大小的CPU缓存来说, 创建的表格越大, CPU缓存所能保存的内容比整个表格的比例就越少, 查表时出现缓存不命中的情况就会越高, 混村的换入和换出操作就会越频繁, 最终影响查表法的实际效率。

为了搞笑地实现BITCOUNT命令, 我们需要一种不会带来内存压力, 并且可以在一次检查中统计多个二进制位的算法。

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

BITCOUNT命令要结局的问题——统计一个位数组中非0二进制位的数量，在数学上被称为计算汉明重量.

因为汉明重量经常被用于信息论, 编码理论和密码学, 所以研究人员针对计算汉明重量开发了多种不同的算法, 一些处理器甚至直接带有计算汉明重量的指令, 而对于不具备这种特殊命令的普通处理器来说, 目前已知效率最好的通用算法为variable-precision SWAR算法, 该算法通过一系列位移和位运算操作, 可以在常数时间内计算多个字节的汉明重量, 并且不需要使用任何额外的内存。

uint32_t swar(uint32_t i) {
 // 步骤1
 i = (i & 0x55555555) + ((i >> 1) & 0x55555555);

 // 步骤2
 i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

 // 步骤3
 i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

 // 步骤4
 i = (i * (0x01010101) >> 24);
 return i;
}

SWAR的执行步骤

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

二进制位统计算法(4): Redis的实现

BITCOUNT命令的实现用到了查表和variable-precision SWAR两种算法:

查表算法使用键长位8位的表, 表中记录了从0000 0000 到 1111 1111在内的所有二进制位的汉明重量
至于variable-precision SWAR 算法方面, BITCOUNT命令在每次循环中载入128个二进制位, 然后调用四次32位variable-precision SWAR 算法来计算128个二进制位的汉明重量

在执行BITCOUNT命令时, 程序会根据未处理的二进制位的数量来决定使用哪种算法:

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

NOTE: 这个BITCOUNT实现的算法复杂度为O(n)，其中n为输入二进制位的数量

BITOP命令的实现

因为C语言直接支持对字节执行逻辑与(&),逻辑或(|),逻辑异或(^),逻辑非(~)操作, 所以BITOP命令的AND,OR,XOR,NOT四个操作都是直接给予这些逻辑操作实现的:

在执行BITOP AND命令时, 程序会用& 操作计算出所有输入二进制位的逻辑与结果, 然后保存在指定的键上面
在执行BITOP OR命令时, 程序用|操作计算出所有输入二进制位的逻辑或结果, 然后保存在指定的键上面
在执行BITOP XOR命令时, 程序用^操作计算出所有输入二进制位的逻辑异或结果, 然后保存在指定的键上面
在执行BITOP NOT命令时, 程序用~操作计算出输入二进制位的逻辑非结果, 然后保存在指定的键上面。

BITOP AND result x y

以上命令的执行步骤

创建一个空白的位数组value, 用于保存AND操作的结果
对两个位数组的第一个字节执行buf[0] & buf[0]操作, 并将结果保存到value[0]字节
对两个数组的第二个字节执行buf[1] & buf[1]操作, 并将结果保存到value[1]字节
对连个数组的第三个字节执行buf[2] & buf[2]操作, 并将结果保存到value[2]字节
经过前面的三次逻辑与操作, 程序得到结果, 并将结果保存在result上面

NOTE: BITOP OR,BITOP XOR,BITOP NOT命令的执行过程和这里列出的BITOP AND的执行过程类似

因为BITOP AND,BITOP OR,BITOP XOR三个命令可以接受多个位数组作为输入, 程序需要遍历输入的每个位数组的每个字节来进行计算, 所以这些命令的复杂度位O(N^2); 与此相反, 因为BITOP NOT命令只接受一个位数组输入, 所以它的复杂度位O(n).