一文带你看懂 Redis BitArray 如何实现高性能的位操作

Redis 作为当代互联网行业无可替代的 Key-Value 数据库,在我们日常的工作中占据主要的角色,对于常用的命令相信大家都很熟悉。今天给大家分享一个平时可能用到的少,但是也很重要的一个类型 BitArray。我们先通过简单的命令使用,了解该命令的用法,然后再给大家介绍一下底层的实现原理,帮助大家更好的了解。

简单使用

我们先看下什么是BitArray 位数组。Redis 使用字符串对象来存储位数组,一个 Byte 字节有 8 个 bit 位,通过控制每一个 bit 位为 0 或者 1来表示某个元素对应的值或者状态。通过使用 8 个 bit 位可以对复杂操作节省很多的空间。BitArray 相关的操作命令有 SETBIT,GETBIT,BITCOUNT,BITOP。下面我们依次看下命令的使用,最后再看下实现的原理。

首先我们在本地启动一个 Redis 实例,再启动一个客户端去链接如下图,

通过redis-cli 链接客户端,执行相应的命令,接下来使用一下 BitArray 相关的命令,

通过setbit test 2 1 命令我们创建了一个名为 testbitarray 并将其第二位设置成 1,再使用getbit test 2 获取对应位的值。setbit命令功能是将对应的 key 指定 offset 的位置设置为 1 或 0,getbit 命令是获取指定 offset 位置的值。test 是一个位数组通过上面的命令值变成0000 0010

接下来我们再创建一个名为test2的位数组,并且通过多次使用 setbit 命令和 bitcountbitcount 命令的作用是用来统计位数组中 1 的个数,通过下面我们看到第一次使用 bitcount test2 命令时结果为 1,当使用了 setbit test2 1 1 命令后再次使用 bitcount 命令我们发现结果已经变成 2 了。其中 test2 的刚开始是0000 0100 后面变成0000 0101

bitop 命令相信大家都能理解,都是一些与,或,异或,非的运算,就不赘述了,具体使用可以看上图。

原理

前面说到 Redis 是通过字符串对象来实现位数组的,所以字符串对象有的功能,在位数组上面都是有的,在Redis 底层位数组的存储结构也是基于 SDS (简单动态字符串)的,如下:

其中 len 字段表示包含的 buf 数组的个数,buf[i] 表示的是第i个字节数组里面具体的数值,buf[len] 是末尾的分隔符\0 。上图中的buf[0] 是一个字节,其中有 8 个 bit 位,在使用了 setbit 命令后初始值为0000 0000,buf[1] 中就是分隔符\0

SETBIT

当我们执行setbit key offset value 命令时,我们分两步:

  1. 计算出创建多少个字节数组(offset / 8) + 1;
  2. 判断是否长度不够需要进行扩容;
  3. 计算出 offset 对应的字节位置 byte = offset / 8;
  4. 计算出 offset 对应的 bit 位,bit = (offset mod 8) + 1;
  5. 根据 offset 找到对应的位置将此处的值改成value 并返回旧值;

假设我们执行的命令时setbit test2 3 1,第一步先计算字节个数 (3 / 8) + 1 = 1,计算出来我们只需要一个字节;第二步跟原始 len 进行比较,发现不需要扩容;3. 根据 offset 计算存放的字节 3 / 8 = 0 则,存放的 buf[0] 中;第四部计算 bit,( 3 mod 8) + 1 = 4,表示的是第四个 bit 位。经过一轮 test2 就变成了 0000 1000

setbit 命令执行的操作都是常数级别的,时间复杂度为 O(1)。

GETBIT

我们知道的setbit 命令是如何实现的,那么getbit 命令也就知道如何计算了,过程是类似的。

  1. 找到对应的字节数组 byte = offset / 8;
  2. 计算出对应的 bit 位bit = (offset mod 8) + 1;

经过上面的计算我们可以知道当执行命令 getbit test2 3 的时候,先算出 3 / 8 = 0 ,找到 buf[0],再使用(3 mod 8) + 1 = 4,找到 bit 位。

看到这里细心的小伙伴就会有疑问,会说不对啊,根据这个计算返回的值应该是 0 啊,因为上面 setbit命令执行完的结果是0000 1000 啊。

能发现这个问题的小伙伴说明很用心在看了,这里就要跟大家说下了,虽然 setbit 命令执行完结果是0000 1000 但是在 buf[0] 中存储的确实反过来的,即为0001 0000。采用的是逆序的方式来保存位数组的。

之所以采用逆序保存位数组是为了减少位数组的移动,提高性能,感兴趣的小伙伴可以自行研究一下。

BITCOUNT 命令

bitcount 命令是用来计算一个位数组中 1 的个数,说起来比较简单,但是实现起来却很有讲究。我们设想一下,统计一个位数组中 1 的个数有多少个,最简单的办法就是遍历,依次累加。但是当我们的位数组很大的时候,整个效率就会变得非常慢,因为遍历是跟长度正相关的,当存放 100MB 的位数组整个遍历需要八亿次。而当达到 500MB 时整个遍历就达到了四十亿次!

在 Redis 中采用的是查表和 variable-precision SWAR 算法,查表是指当位数组长度小于 128 时,直接根据预设的映射表找到对应 1 的个数,直接返回。而variable-precision SWAR 算法相对比较复杂,阿粉也还要再研究研究,今天就先不分享了。

BITOP 命令

bitop 命令相对简单一点,因为 Redis 底层是基于 C 语言实现的,C语言本身就支持相关的逻辑运算。因为本身就是二进制位数组,所以对应的逻辑运算会简单很多就不赘述了,相信大家都能理解。

参考资料

Redis 设计与实现(第二版)

Java Geek Tech wechat
欢迎订阅 Java 极客技术,这里分享关于 Java 的一切。