Redis数据结构之位图 BitMap

书接上回

上一篇我们学习的 zset集合这一数据类型。其内部是由skiplist和hashtable这种两种数据结构编码的。 如果不记得了，那就来坐穿梭机回去看看吧。 开始穿梭

接下来，我们继续学习一个新的"数据类型", 位图, bitmap.（注意啦,数据类型，我加了引号！！）

bitmap简介

那么什么是bitmap,我们先从名字上来说，bit，计算机中最小的单位，一个bit表示一个二进制位。map，映射，图。所以，bitmap就是表示对二进制位的映射。那具体是怎么回事呢？bitmap其实就是以字符串的形式对二进制位进行操作，从而达到节约空间占用的作用。

而且，bitmap，中文的意思就是位图。 不知道你用没用过C语言的位图结构，他们的目的都是一样。

可能你还是不理解，别急，往下看。

bitmap 怎么用呢？

恰巧，前几天小编在面试中被问到过这个问题。

面试官说： 有个业务场景：我们这边有10000家线下门店，我们要对部分门店进行广告投放，怎么记录某条广告投放给哪家门店里了呢？我们的门店id是递增的。

首先我们可以有三张表，广告表(G表)，门店表（M表），广告门店关联表（GM表）。

如果我们投放广告的时候，把每条广告和每个门店的关联作为一条数据插入到GM表中，那么这个表中的数据量增长还是非常快的。如果有10万家门店呢？广告的投放和撤销比较频繁。也就是说数据的修改也是比较频繁的。那怎么搞呢？

门店的id是递增的，那么我们可以这么搞，用10001个二进制位表示10000家门店的id，如果该门店投放了该广告，就把该位置上的数字置为1。并且每四个字节转换成一个整数型数，将（10000/8/4）313个整形数按照一定的规则转换成字符串存储到GM表中。表示一条广告已经投放的门店。这样我们就使用了0.1kb左右的空间记录了某条广告投放门店的情况。

其实呢，这就是使用bitmap进行存储的。

接下来，我们看下如何使用 位图。

bitmap的基本命令

• SETBIT

setbit key offset value

对 key 所储存的字符串值，设置或清除指定偏移量上的位(bit)。 位的设置或清除取决于 value 参数，可以是 0 也可以是 1 。 当 key 不存在时，自动生成一个新的字符串值。 字符串会进行伸展(grown)以确保它可以将 value 保存在指定的偏移量上。当字符串值进行伸展时，空白位置以 0填充。 offset 参数必须大于或等于 0 ，小于 2^32 (bit 映射被限制在 512 MB 之内)。

假设我们使用 位图来存储Redis这个字符串。

在演示这个命令之前，我们首先来看下 如何使用二进制来表示字符串。

Redis 中的 R 对应 ASCII 码是: 82. 转化成二进制就是: 0b01010010,其他字符依次如下所示： Redis 中的 e 对应 ASCII 码是: 101. 转化成二进制就是: 0b01100101， Redis 中的 d 对应 ASCII 码是: 100. 转化成二进制就是: 0b01100100， Redis 中的 i 对应 ASCII 码是: 105. 转化成二进制就是: 0b01101001， Redis 中的 s 对应 ASCII 码是: 115. 转化成二进制就是: 0b01110011。

看到这里，我要告诉你一个知识点：对于位图的操作，我们可以实现 零存整取 。 什么意思呢？

我来给你演示一下

如上图，R 这个字符，对应的每个二进制上的数。由于位图会自动填充空位为0，所以我们只需要设置二进制位上为1的就可以了。具体命令如下

127.0.0.1:6379> setbit k87 1 1
(integer) 0
127.0.0.1:6379> setbit k87 3 1
(integer) 0
127.0.0.1:6379> setbit k87 6 1
(integer) 0
127.0.0.1:6379> get k87
"R"

解释一下，我们根据 R 每个二进制位上数值设置到 k87 中，然后通过get k87这个命令，返回了 R。 这就是所谓的 零存整取。如果我继续设置剩下的 edis字符串呢？

127.0.0.1:6379> setbit k87 9 1
(integer) 0
127.0.0.1:6379> setbit k87 10 1
(integer) 0
127.0.0.1:6379> setbit k87 13 1
(integer) 0
127.0.0.1:6379> setbit k87 15 1
(integer) 0
127.0.0.1:6379> setbit k87 17 1
(integer) 0
127.0.0.1:6379> setbit k87 18 1
(integer) 0
127.0.0.1:6379> setbit k87 21 1
(integer) 0
127.0.0.1:6379> setbit k87 25 1
(integer) 0
127.0.0.1:6379> setbit k87 26 1
(integer) 0
127.0.0.1:6379> setbit k87 28 1
(integer) 0
127.0.0.1:6379> setbit k87 31 1
(integer) 0
127.0.0.1:6379> setbit k87 33 1
(integer) 0
127.0.0.1:6379> setbit k87 34 1
(integer) 0
127.0.0.1:6379> setbit k87 35 1
(integer) 0
127.0.0.1:6379> setbit k87 38 1
(integer) 0
127.0.0.1:6379> setbit k87 39 1
(integer) 0
127.0.0.1:6379> get k87
"Redis"

这里你就可能说，有谁会这样使用，自己计算出每个位，然后去获取完整的？ 是啊，不过这里只是一个例子，来说明 位图 零存整取 功能，接下来，我们接着看 位图 整存零取的功能。

这里呢，就要介绍 gitbit 这个命令。

• GETBIT

GETBIT key offset

对 key 所储存的字符串值，获取指定offset上的位(bit).

如果key不存在，获取offset超出范围，返回0.

首先我们设置 一个 string 类型的字符串到Redis中，然后依次获取每一位上的值。

可以和下图进行比对。

127.0.0.1:6379> set k88 Redis
OK
127.0.0.1:6379> getbit k88 0
(integer) 0
127.0.0.1:6379> getbit k88 1
(integer) 1
127.0.0.1:6379> getbit k88 2
(integer) 0
127.0.0.1:6379> getbit k88 3
(integer) 1
127.0.0.1:6379> getbit k88 4
(integer) 0
127.0.0.1:6379> getbit k88 5
(integer) 0
127.0.0.1:6379> getbit k88 6
(integer) 1
127.0.0.1:6379> getbit k88 7
(integer) 0
127.0.0.1:6379> getbit k88 8
(integer) 0
127.0.0.1:6379> getbit k88 9
(integer) 1
127.0.0.1:6379> getbit k88 10
(integer) 1
# ....
127.0.0.1:6379> getbit k88 38
(integer) 1
127.0.0.1:6379> getbit k88 39
(integer) 1
## 演示超出范围
127.0.0.1:6379> getbit k88 40
(integer) 0
127.0.0.1:6379> getbit k88 41
(integer) 0
127.0.0.1:6379> getbit k88 42
(integer) 0
127.0.0.1:6379> 

这个就是 位图提供的 整存零取的功能了。综合上面的两项功能，我们轻而易举的就可以得出Redis 的位图是可以 零存零取的。就是使用 setbit 和 gitbit 命令了。这里就不演示了。

• BITCOUNT

bitCount key [start] [end]

计算指定key的对应字符串，被设置为1的比特位的数量。

还是以上面的Redis为例，一共是19位1.我们来演示一下

## 不存在的时候，返回0
127.0.0.1:6379> bitcount k89
(integer) 0
127.0.0.1:6379> set k89 Redis
OK
127.0.0.1:6379> bitcount k89 
(integer) 19
# 注意这里start end 都是表示字节。
127.0.0.1:6379> bitcount k89 0 1 
(integer) 7

这个适合什么场景下使用呢？ 比如,我们要计算某个用户登录天数。第一天登录的时候，我们 可以设置 setbit user1 1 1,第二天设置 setbit use1 2 1,那么使用 bitcount user1 就能知道该用户总共的登录天数了，也能够计算出该用户在哪天登录了。

• BITPOS

bitpos key bit [start] [end]

返回key的指定区段内容，第一个bit的位置。

比如我们以 Redis 为例, 如下图

127.0.0.1:6379> set key90 Redis
OK
127.0.0.1:6379> bitops key90 1
(error) ERR unknown command `bitops`, with args beginning with: `key90`, `1`, 
127.0.0.1:6379> bitpos key90 1
(integer) 1
127.0.0.1:6379> bitpos key90 0
(integer) 0
# 这里的start和end也指的是字节
127.0.0.1:6379> bitpos key90 0 2 10
(integer) 16
127.0.0.1:6379> bitpos key90 1 2 10
(integer) 17

• BITOP

BITOP operation destkey key [key …]

对一个或多个保存二进制位的字符串 key 进行位元操作，并将结果保存到 destkey 上。

operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种：

BITOP AND destkey key [key ...] ，对一个或多个 key 求逻辑并，并将结果保存到 destkey 。

BITOP OR destkey key [key ...] ，对一个或多个 key 求逻辑或，并将结果保存到 destkey 。

BITOP XOR destkey key [key ...] ，对一个或多个 key 求逻辑异或，并将结果保存到 destkey 。

BITOP NOT destkey key ，对给定 key 求逻辑非，并将结果保存到 destkey 。

除了 NOT 操作之外，其他操作都可以接受一个或多个 key 作为输入。

这里我们做一个简单例子。

127.0.0.1:6379> setbit k91_1 0 1
(integer) 0
127.0.0.1:6379> setbit k91_1 1 1
(integer) 0
127.0.0.1:6379> setbit k91_1 2 1
(integer) 0
127.0.0.1:6379> setbit k91_1 3 1
(integer) 0
127.0.0.1:6379> get k91_1 # 1111 (低位->高位)
"\xf0"
127.0.0.1:6379> setbit k91_2 3 1
(integer) 0
127.0.0.1:6379> setbit k91_2 4 1
(integer) 0
127.0.0.1:6379> setbit k91_2 5 1
(integer) 0
127.0.0.1:6379> get k91_2 # 000111 (低位->高位)
"\x1c"

## and 操作
127.0.0.1:6379> bitop AND k91_d_1 k91_1 k91_2
(integer) 1
127.0.0.1:6379> get k91_d_1 # 000100 (低位->高位)
"\x10"


## OR 操作
127.0.0.1:6379> bitop OR k91_d_2 k91_1 k91_2
(integer) 1
127.0.0.1:6379> get k91_d_2 # 111111 (低位->高位)
"\xfc"

## XOR 亦或操作
127.0.0.1:6379> bitop XOR k91_d_3 k91_1 k92_2
(integer) 1
127.0.0.1:6379> get k91_d_3 # 111011 (低位->高位)
"\xf0"

## NOT 操作
127.0.0.1:6379> bitop NOT k91_d_4 k91_1
(integer) 1
127.0.0.1:6379> get k91_d_4 # 00001111 (低位->高位)
"\x0f"
127.0.0.1:6379> bitop NOT k91_d_5 k91_2
(integer) 1
127.0.0.1:6379> get k91_d_5 # 111011 (低位->高位)
"\xe3"

• BITFIELD

BITFIELD key [GET type offset] [SET type offset value] [INCRBY type offset increment] [OVERFLOW WRAP|SAT|FAIL]

BITFIELD 命令可以将一个 Redis 字符串看作是一个由二进制位组成的数组， 并对这个数组中储存的长度不同的整数进行访问 （被储存的整数无需进行对齐）。 换句话说， 通过这个命令， 用户可以执行诸如 “对偏移量 1234 上的 5 位长有符号整数进行设置”、 “获取偏移量 4567 上的 31 位长无符号整数”等操作。 此外， BITFIELD 命令还可以对指定的整数执行加法操作和减法操作， 并且这些操作可以通过设置妥善地处理计算时出现的溢出情况。 这是一个比较复杂的命令了。我们依次来看看。

• GET type offset

type是什么呢？ type是返回的数值类型。可选值有：i8（有符号8个bit位）,i16（有符号16个bit位）,u8（无符号8个bit位）,u16（无符号16个bit位）,…

这个的命令的功能就是返回执行的二进制的范围，offset是指第几个二进制位。 注意： BITFIELD 命令最大支持64 位长的有符号整数以及 63 位长的无符号整数， 其中无符号整数的 63 位长度限制是由于 Redis 协议目前还无法返回 64 位长的无符号整数而导致的。

用下面这个例子来演示一下。

127.0.0.1:6379> set k92 Redis
OK
127.0.0.1:6379> bitfield k92 get i8 0
1) (integer) 82
127.0.0.1:6379> bitfield k92 get u8 0
1) (integer) 82
127.0.0.1:6379> bitfield k92 get i16 0
1) (integer) 21093
127.0.0.1:6379> bitfield k92 get u16 0
1) (integer) 21093

结合上面的那张图，我们看下

我们手动的将前8个bit位装换成10进制，就是82。高位为0，所以此时，u8和i8的值是一样的。同样的 u16,i16,u24,u48,大家可以自行验证一下。

• SET type offset value

这个命令是和GET命令相反的一个命令。

直接用一个例子来演示一下。

127.0.0.1:6379> bitfield k93 SET u8 0 82
1) (integer) 0
127.0.0.1:6379> get k93
"R"
127.0.0.1:6379> bitfield k93 SET u8 8 101
1) (integer) 0
127.0.0.1:6379> get k93
"Re"
127.0.0.1:6379> bitfield k93 SET u8 16 100
1) (integer) 0
127.0.0.1:6379> get k93
"Red"
# ... 
# 剩下的i和s，大家自己试一下吧

• INCRBY type offset increment

从制定的偏移位开始，增加increment。

什么意思呢？

来演示一下:

字符A的ASCII码是65，R是82，如果从A变成R，需要增加17。

127.0.0.1:6379> set k94 A
OK
127.0.0.1:6379> bitfield k94 INCRBY u8 0 17
1) (integer) 82
127.0.0.1:6379> get k94
"R"
127.0.0.1:6379> bitfield k94 INCRBY u8 8 101
1) (integer) 101get
127.0.0.1:6379> get k94
"Re"

• OVERFLOW WRAP|SAT|FAIL

这是bitmap对 INCRBY 命令执行时，发生异常行为的控制。

用户可以通过 OVERFLOW 命令以及以下展示的三个参数， 指定 BITFIELD 命令在执行自增或者自减操作时， 碰上向上溢出（overflow）或者向下溢出（underflow）情况时的行为：

WRAP ： 使用回绕（wrap around）方法处理有符号整数和无符号整数的溢出情况。 对于无符号整数来说， 回绕就像使用数值本身与能够被储存的最大无符号整数执行取模计算， 这也是 C 语言的标准行为。 对于有符号整数来说， 上溢将导致数字重新从最小的负数开始计算， 而下溢将导致数字重新从最大的正数开始计算。 比如说， 如果我们对一个值为 127 的 i8 整数执行加一操作， 那么将得到结果 -128 。

SAT ： 使用饱和计算（saturation arithmetic）方法处理溢出， 也即是说， 下溢计算的结果为最小的整数值， 而上溢计算的结果为最大的整数值。 举个例子， 如果我们对一个值为 120 的 i8 整数执行加 10 计算， 那么命令的结果将为 i8 类型所能储存的最大整数值 127 。 与此相反， 如果一个针对 i8 值的计算造成了下溢， 那么这个 i8 值将被设置为 -127 。

FAIL ： 在这一模式下， 命令将拒绝执行那些会导致上溢或者下溢情况出现的计算， 并向用户返回空值表示计算未被执行。

我们演示一下这几种情况

# 使用 WRAP 方式，重复执行相同的命令，在一个2bit上，从 0,1,2,3 来回折返。
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 1
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 2
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 3
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 0
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 1
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 2
127.0.0.1:6379> bitfield k95_1 OVERFLOW WRAP incrby u2 1 1
1) (integer) 3

# 使用 SAT 方式，当要发生溢出的时候，不再执行。
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 1
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 2
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 3
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 3
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 3
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 3
127.0.0.1:6379> bitfield k95_2 OVERFLOW SAT incrby u2 1 1
1) (integer) 3

# 使用FAIL模式，则返回(nil)，不执行且返回nil
127.0.0.1:6379> bitfield k95 OVERFLOW FAIL incrby u2 102 1
1) (nil)

BITFIELD 命令的作用在于它能够将很多小的整数储存到一个长度较大的位图中， 又或者将一个非常庞大的键分割为多个较小的键来进行储存， 从而非常高效地使用内存， 使得 Redis 能够得到更多不同的应用 —— 特别是在实时分析领域： BITFIELD 能够以指定的方式对计算溢出进行控制的能力， 使得它可以被应用于这一领域。

以上就是Redis中bitmap相关的命令了。下面我简单的来看下 bitmap 这种"数据结构"是如何实现的。

注意，这里的数据结构我还是加上了引号。具体为什么呢？

bitmap 的实现

话不多说，我们直接去看看源码中是怎么实现的。直接搜文件 bit

我们要看src目录下的，所以，直接看bitops.c

这里我们就是以一个命令setbit为例简单的来看看bitmap的运行过程。

/**
 * SETBIT 命令的实现
 * @param c 客户端对象
 */
void setbitCommand(client *c) {
    robj *o; ///  setbit key offset value 中的 key对应的Redis Object。
    char *err = "bit is not an integer or out of range";
    size_t bitoffset; /// 指定要修改的位的偏移量
    ssize_t byte, bit;  /// byte: 要修改的位 所占的字节。第byte个字节上。 bit，在所占字节中的第bit位上。
    int byteval, bitval; /// byteval: 要修改的位所占的字节的值。十进制数。  bitVal 是原来的指定bit上的值
    long on; /// 修改的值。就是 setbit key offset value 中的value。

    /// 解析 offset 参数，是否符合规范(是否位负数，是否超过512M)
    if (getBitOffsetFromArgument(c, c->argv[2], &bitoffset, 0, 0) != C_OK)
        return;
    /// 解析 value 参数 => 赋值给on变量
    if (getLongFromObjectOrReply(c, c->argv[3], &on, err) != C_OK)
        return;

    /// 验证on(value)只能是0或者1
    if (on & ~1) {
        addReplyError(c, err);
        return;
    }
    /// 返回key对应的对象
    /// 该对象是一个OBJ_STRING类型
    if ((o = lookupStringForBitCommand(c, bitoffset)) == NULL) return;

    /// 获取当前位置上的值
    byte = bitoffset >> 3; /// 计算出字节，确定offset所在的字节。
    byteval = ((uint8_t *) o->ptr)[byte]; /// 将指定字节上的数转换成无符号整型数。
    bit = 7 - (bitoffset & 0x7); /// 计算要修改的位，是当前字节中的第几位。
    bitval = byteval & (1 << bit); /// 计算出修改后的值。(bitVal是修改后的整个字节上值)

    /* Update byte with new bit value and return original value */
    /// 更新 String 的值为 bitVal，并且返回原来的值。
    byteval &= ~(1 << bit); /// 将字节上原来的值，指定位上置为0.(即要赋值的位，bit为当前字节中的位。)
    byteval |= ((on & 0x1) << bit); /// 将on的值复制给byteVal,取或运算，如果on为1，则1，若on为0，则0，上一行代码已经将指定位置置为了0.
    ((uint8_t *) o->ptr)[byte] = byteval; /// 修改对象中指定字节的值。
    signalModifiedKey(c->db, c->argv[1]); /// 通知修改了key。
    notifyKeyspaceEvent(NOTIFY_STRING, "setbit", c->argv[1], c->db->id);
    server.dirty++; // 从上次保存到数据库的更改次数
    addReply(c, bitval ? shared.cone : shared.czero); /// 返回原来的值
}

上面代码就是 setBit 命令的实现过程了，这篇文章中我们不做研究我们只看第27行.这一行中有一个 lookupStringForBitCommand 方法。在这里我们猜测一下，bitmap 其实就是一个 OBJ_STRING 类型的结构。

到底是不是呢？

看一下源码。

/**
 * 这是用于需要将位写入字符串对象的命令实现的辅助函数。
 *
 * 否则，如果密钥持有错误的类型，则返回NULL，并且*向客户端发送错误。
 * 该命令创建或填充字符串零，以便可以寻址“ maxbit”位。
 * 该对象最终返回。
 * 否则，如果密钥持有错误的类型，则返回NULL并将错误发送给客户端。
 */
robj *lookupStringForBitCommand(client *c, size_t maxbit) {
    size_t byte = maxbit >> 3; // 计算字节
    /// 为写操作找出一个key。 【setbit key offset value】中argv[1] 即为key
    robj *o = lookupKeyWrite(c->db, c->argv[1]);

    /// 是否找到了key
    if (o == NULL) {
        /// 没有找到。 创建一个对象写入。对象为OBJ_STRING类型。
        o = createObject(OBJ_STRING, sdsnewlen(NULL, byte + 1));
        dbAdd(c->db, c->argv[1], o);
    } else {
        /// 找到了key对象，如果不是 OBJ_STRING 类型直接返回。
        if (checkType(c, o, OBJ_STRING)) return NULL;
        /// 获取要修改的对象。上一行代码已经进行了判断，确定其为 OBJ_STRING 类型。
        o = dbUnshareStringValue(c->db, c->argv[1], o);
        /// 增加 STRING类型的长度
        o->ptr = sdsgrowzero(o->ptr, byte + 1);
    }
    return o;
}

在第17行和第23行。就很清楚了。

所以，在文章一开始加上引号的 数据结构 ，谜题就解开了。

bitmap 并不是一个新的数据结构，本质上是用 STRING 这个数据结构来实现的。

如果你想看bitmap的全部源码，那么满足你！！:point_right::point_right: 点击这里:point_left::point_left:

公众号里回复 redis源码,即可获取完整路径哦

虽然redis源码不是我写的，但是我看过的都加上注释啦~

除此之外，小白还自己实现了一个 bitmap。感兴趣的朋友欢迎 star.:point_right::point_right: bitMap源码,点击这里 :point_left::point_left:

公众号里回复 bitmap,即可获取完整路径哦

当然: JDK也提供了一个BitMap的实现，叫BitSet，位于java.util包下。其底层使用的是一个long类型的数组，一个long代表一个word。但BitSet没有解决上面提到的输入稀疏的问题。谷歌开源的EWAHCompressedBitMap解决了输入稀疏的问题。

这里我们总结一下。

Redis的数据类型	底层实现结构	文章参考
STRING	sds	数据类型之String
list	quicklist, ziplist	数据类型之list
hash	ziplist, dict	数据类型之hash
set	dict ,intset	数据类型之set
zset	dict, skipList	数据类型之zset
bitmap	sds	数据类型之bitmap

最后

希望与你一起遇见更好的自己