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

一文带你看懂 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 命令我们创建了一个名为 test 的 bitarray 并将其第二位设置成 1，再使用getbit test 2 获取对应位的值。setbit命令功能是将对应的 key 指定 offset 的位置设置为 1 或 0，getbit 命令是获取指定 offset 位置的值。test 是一个位数组通过上面的命令值变成0000 0010 。

接下来我们再创建一个名为test2的位数组，并且通过多次使用 setbit 命令和 bitcount ，bitcount 命令的作用是用来统计位数组中 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 命令时，我们分两步：

计算出创建多少个字节数组(offset / 8) + 1;判断是否长度不够需要进行扩容;计算出 offset 对应的字节位置 byte = offset / 8;计算出 offset 对应的 bit 位，bit = (offset mod 8) + 1;根据 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 命令也就知道如何计算了，过程是类似的。

找到对应的字节数组 byte = offset / 8;计算出对应的 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 设计与实现(第二版)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。