二进制数组 bitmap | 彩潭有鲤的札记

type

status

date

slug

summary

位数组的表示

用SDS表示的，一字节长的位数组：

redisObject.type的值为REDIS_STRING，表示这是一个字符串对象。

sdshdr.len的值为1，表示这个SDS保存了一个一字节长的位数组

buf数组中的buf[0]字节保存了一字节长的位数组

buf数组中的buf[1]字节保存了SDS程序自动追加到值的末尾的空字符'\0'

为了方便与表示二进制位，把buf[0]一字节表示为下面所示的状态（1字节8位）

buf数组保存二进制位与我们平时表示的二进制为顺序是相反的，例如在上图中buf数组第1字节表示的二进制为10110010，实质上其表示的是01001101，使用逆序来保存位数组可以简化SETBIT命令的实现。

下面表示了另一个位数组

sdshdr.len属性的值为3，表示这个SDS保存了一个三字节长的位数组

位数组由buf数组中的buf[0]、buf[1]、buf[2]三个字节保存，和之前说明的一样，buf数组使用逆序来保存位数组：位数组1111 0000 1100 0011 1010 0101在buf数组中会被保存为1010 0101 1100 0011 0000 1111

GETBIT命令的实现

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

GETBIT 命令的执行过程如下：

计算， byte 值记录了 offset 偏移量指定的二进制位保存在位数组的哪个字节

计算， bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第几个二进制位

根据 byte 值和 bit 值，在位数组 bitarray 中定位 offset 偏移量指定的二进制位，并返回这个位的值

对于所示的位数组来说，命令：GETBIT <bitarray> 3

执行以下操作：

3/8的值为 0 。

的值为 4 。

定位到 buf[0] 字节上面，然后取出该字节上的第 4 个二进制位（从左向右数）的值。

向客户端返回二进制位的值 1

命令：GETBIT <bitarray> 10

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

SETBIT命令

用于为位数组指定偏移量上的二进制位设置值，并将之前二进制位的旧值返回。SETBIT命令执行的所有操作都可以在常数时间内完成，该命令的时间复杂度为

bitarray：二进制位数组

offset：偏移量（从0开始）

value：设置的值

SETBIT命令的执行过程

计算len=[offset÷8]+1，len值记录了保存offset偏移量指定的二进制位至少需要多少字节

检查bitarray键保存的位数组（也即是SDS）的长度是否小于len，如果是的话，将 SDS的长度扩展为len字节，并将所有新扩展空间的二进制位的值设置为0

计算byte=[offset÷8]，byte值记录了offset偏移量指定的二进制位保存在位数组的哪个字节

计算bit=（offset mod 8）+1，bit值记录了offset偏移量指定的二进制位是byte字节的第几个二进制位

根据byte值和bit值，在bitarray键保存的位数组中定位offset偏移量指定的二进制位，首先将指定二进制位现在值保存在oldvalue变量，然后将新值value设置为这个二进制位的值

向客户端返回oldvalue变量的值

对下图所示的位数组执行命令：SETBIT <bitarray> 1 1

计算[1÷8]+1，得出值1，这表示保存偏移量为1的二进制位至少需要1字节长位数组

检查位数组的长度，发现SDS的长度不小于1字节，无须执行扩展操作

计算[1÷8]，得出值0，说明偏移量为1的二进制位位于buf[0]字节

计算（1 mod 8）+1，得出值2，说明偏移量为1的二进制位是buf[0]字节的第2个二进制位

定位到buf[0]字节的第2个二进制位上面，将二进制位现在的值0保存到oldvalue变量，然后将二进制位的值设置为1

向客户端返回oldvalue变量的值0

需要对位数组进行扩展的例子

假设对所示的位数组执行命令：SETBIT <bitarray> 12 1

计算[12÷8]+1，得出值2，这表示保存偏移量为12的二进制位至少需要2字节长的位数组

对位数组的长度进行检查，得知位数组现在的长度为1字节，这比执行命令所需的最小长度2字节要小，所以程序会要求将位数组的长度扩展为2字节。不过，尽管程序只要求2 字节长的位数组，但SDS的空间预分配策略会为SDS额外多分配2字节的未使用空间，再加上为保存空字符而额外分配的1字节，扩展之后buf数组的实际长度为5字节

计算[12÷8]，得出值1，说明偏移量为12的二进制位位于buf[1]字节中

计算（12 mod 8）+1，得出值5，说明偏移量为12的二进制位是buf[1]字节的第5个二进制位

定位到buf[1]字节的第5个二进制位，将二进制位现在的值0保存到oldvalue变量，然后将二进制位的值设置为1

向客户端返回oldvalue变量的值0。左图展示了SETBIT命令定位并设置指定二进制位的过程，而右图则展示了SETBIT 命令执行之后，位数组的样子

因为buf数组使用逆序来保存位数组，所以当程序对buf数组进行扩展之后，写入操作可以直接在新扩展的二进制位中完成，而不必改动位数组原来已有的二进制位。相反地，如果buf数组使用和书写位数组时一样的顺序来保存位数组，那么在每次扩展buf数组之后，程序都需要将位数组已有的位进行移动，然后才能执行写入操作，这比SETBIT命令目前的实现方式要复杂，并且移位带来的CPU时间消耗也会影响命令的执行速度

BITCOUNT命令

功能：用于统计位数组里面，值为1的二进制位的数量

遍历算法

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

遍历算法虽然实现起来简单，但效率非常低，因为这个算法在每次循环中只能检查一个二进制位的值是否为1，所以检查操作执行的次数将与位数组包含的二进制位的数量成正比

查表算法

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

对于一个有限集合来说，集合元素的排列方式是有限的

而对于一个有限长度的位数组来说，它能表示的二进制位排列也是有限的

根据这个原理，可以创建一个表，表的键为某种排列的位数组，而表的值则是相应位数组中，值为1的二进制位的数量。创建了这种表之后，就可以根据输入的位数组进行查表，在无须对位数组的每个位进行检查的情况下，直接知道这个位数组包含了多少个值为1的二进制位。

对于8位长的位数组来说可以创建下面的表格，通过这个表格，可以一次从位数组中读入8个位，然后根据这8个位的值进行查表，直接知道这个值包含了多少个值为1的位

查表法是一种比遍历算法更好的统计办法，但受限于查表法带来的内存压力，以及缓存不命中可能带来的影响，只能考虑创建键长为8位或者键长为16位的表，而这两种表带来的效率提升，对于处理非常长的位数组来说仍然远远不够

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

variable-precision SWAR算法

BITCOUNT命令要解决的问题——统计一个位数组中非0二进制位的数量，在数学上被称为“计算汉明重量（Hamming Weight）”

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

一个处理32位长度位数组的variable-precision SWAR算法的实现：

调用swar（bitarray）的执行步骤：

步骤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，这个值就是0x3A70F21B的汉明重量，如下表所示

swar函数每次执行可以计算32个二进制位的汉明重量，它比之前介绍的遍历算法要快32 倍，比键长为8位的查表法快4倍，比键长为16位的查表法快2倍，并且因为swar函数是单纯的计算操作，所以它无须像查表法那样，使用额外的内存

另外，因为swar函数是一个常数复杂度的操作，所以可以按照自己的需要，在一次循环中多次执行swar，从而按倍数提升计算汉明重量的效率：如果在一次循环中调用两次swar函数，那么计算汉明重量的效率就从之前的一次循环计算32位提升到了一次循环计算64位，如果在一次循环中调用四次swar函数，那么一次循环就可以计算128个二进制位的汉明重量，这比每次循环只调用一次swar函数要快四倍！

Redis的实现

BITCOUNT命令的实现用到了查表和variable-precisionSWAR两种算法：

查表算法使用键长为8位的表，表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量

至于variable-precision SWAR算法方面，BITCOUNT命令在每次循环中载入128个二进制位，然后调用四次32位variable-precision SWAR算法来计算这128个二进制位的汉明重量

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

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

如果未处理的二进制位的数量小于128位，那么程序使用查表算法来计算二进制位的汉明重量

伪代码:

这个BITCOUNT实现的算法复杂度为 ，其中为输入二进制位的数量

可以用以下公式来计算BITCOUNT命令在处理长度为n的二进制位输入时，命令中的两个循环需要执行的次数：

第一个循环的执行次数可以用公式loop 1=n÷128」计算得出

第二个循环的执行次数可以用公式loop 2=n mod 128计算得出

BITOP命令

功能：可以对多个位数组进行按位与（and）、按位或（or）、按位异或（xor）、取反（not）

复杂度：

BITOP AND、BITOP OR、BITOP XOR三个命令可以接受多个位数组作为输入，程序需要遍历输入的每个位数组的每个字节来进行计算，所以这些命令的复杂度为

BITOP NOT命令只接受一个位数组输入，它的复杂度为

BITOP命令的实现因为C语言直接支持对字节执行逻辑与（&）、逻辑或（|）、逻辑异或（^）和逻辑非（~）操作，所以BITOP命令的AND、OR、XOR和NOT四个操作都是直接基于这些逻辑操作实现的：

在执行BITOP AND命令时，程序用&操作计算出所有输入二进制位的逻辑与结果，然后保存在指定的键上面

在执行BITOP OR命令时，程序用|操作计算出所有输入二进制位的逻辑或结果，然后保存在指定的键上面

在执行BITOP XOR命令时，程序用^操作计算出所有输入二进制位的逻辑异或结果，然后保存在指定的键上面

在执行BITOP NOT命令时，程序用~操作计算出输入二进制位的逻辑非结果，然后保存在指定的键上面

应用场景

Bitmap 类型非常适合二值状态统计的场景，这里的二值状态就是指集合元素的取值就只有 0 和 1 两种，在记录海量数据时，Bitmap 能够有效地节省内存空间。

签到统计

在签到打卡的场景中，我们只用记录签到（1）或未签到（0），所以它就是非常典型的二值状态。

签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是 31 天）的签到情况用 31 个 bit 位就可以，而一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型。

假设我们要统计 ID 100 的用户在 2022 年 6 月份的签到情况，就可以按照下面的步骤进行操作。

第一步，执行下面的命令，记录该用户 6 月 3 号已签到。

第二步，检查该用户 6 月 3 日是否签到。

第三步，统计该用户在 6 月份的签到次数。

这样，就知道该用户在 6 月份的签到情况了。

如何统计这个月首次打卡时间呢？

Redis 提供了 BITPOS key bitValue [start] [end]指令，返回数据表示 Bitmap 中第一个值为 bitValue 的 offset 位置。

在默认情况下，命令将检测整个位图，用户可以通过可选的 start 参数和 end 参数指定要检测的范围。所以我们可以通过执行这条命令来获取 userID = 100 在 2022 年 6 月份首次打卡日期：

需要注意的是，因为 offset 从 0 开始的，所以我们需要将返回的 value + 1 。

判断用户登陆态

Bitmap 提供了 GETBIT、SETBIT 操作，通过一个偏移值 offset 对 bit 数组的 offset 位置的 bit 位进行读写操作，需要注意的是 offset 从 0 开始。

只需要一个 key = login_status 表示存储用户登陆状态集合数据，将用户 ID 作为 offset，在线就设置为 1，下线设置 0。通过 GETBIT判断对应的用户是否在线。 5000 万用户只需要 6 MB 的空间。

假如我们要判断 ID = 10086 的用户的登陆情况：

第一步，执行以下指令，表示用户已登录。

第二步，检查该用户是否登陆，返回值 1 表示已登录。

第三步，登出，将 offset 对应的 value 设置成 0。

连续签到用户总数

如何统计出这连续 7 天连续打卡用户总数呢？

把每天的日期作为 Bitmap 的 key，userId 作为 offset，若是打卡则将 offset 位置的 bit 设置成 1。

key 对应的集合的每个 bit 位的数据则是一个用户在该日期的打卡记录。

一共有 7 个这样的 Bitmap，如果能对这 7 个 Bitmap 的对应的 bit 位做『与』运算。同样的 UserID offset 都是一样的，当一个 userID 在 7 个 Bitmap 对应对应的 offset 位置的 bit = 1 就说明该用户 7 天连续打卡。

结果保存到一个新 Bitmap 中，再通过 BITCOUNT 统计 bit = 1 的个数便得到了连续打卡 7 天的用户总数了。

Redis 提供了 BITOP operation destkey key [key ...]这个指令用于对一个或者多个 key 的 Bitmap 进行位元操作。

operation 可以是 and、OR、NOT、XOR。当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0 。空的 key 也被看作是包含 0 的字符串序列。

假设要统计 3 天连续打卡的用户数，则是将三个 bitmap 进行 AND 操作，并将结果保存到 destmap 中，接着对 destmap 执行 BITCOUNT 统计，如下命令：

即使一天产生一个亿的数据，Bitmap 占用的内存也不大，大约占 12 MB 的内存（10^8/8/1024/1024），7 天的 Bitmap 的内存开销约为 84 MB。同时最好给 Bitmap 设置过期时间，让 Redis 删除过期的打卡数据，节省内存。