javaroad

Appearance

Bitmap详解 ​

一、Bitmap是什么？ ​

Bitmap是Redis提供的位级操作数据类型，本质是二进制位的集合（每个位只能是0或1）。它通过**字符串（SDS）**作为底层存储结构，将每个字节（8位）拆分为独立的位，实现对海量布尔值（是/否、存在/不存在）的高效存储与查询。

1. 核心特点 ​

  • 空间效率极高：1位（bit）存储1个布尔值，例如存储1亿个用户的在线状态，仅需1亿/8 = 12.5MB（远小于集合Set的400MB+）。
  • 位操作原子性：所有位操作命令（如SETBIT、BITCOUNT）都是原子的，无需担心并发冲突。
  • 支持丰富的位运算：包括位设置（SETBIT）、位获取（GETBIT）、位计数（BITCOUNT）、位合并（BITOP）、位查找（BITPOS）等。

二、Bitmap底层原理 ​

Bitmap的底层依赖Redis的字符串类型（SDS，简单动态字符串），每个字符串的字节（char）对应8个二进制位。以下是关键原理的拆解：

1. 位索引与字节映射 ​

Bitmap的位索引从0开始，每个字节的8位对应连续的位索引。例如：

  • 字节0（第1个字节）对应位索引0~7（位0是字节的最低位，位7是最高位）；
  • 字节1（第2个字节）对应位索引8~15；
  • 字节n对应位索引8n ~ 8n+7。

示例：字符串"\x03"（二进制00000011）对应的位状态：

位索引01234567
位值11000000

2. 动态扩展机制 ​

当设置的位索引超过当前字符串长度时，Redis会自动扩展字符串，填充0（默认值）。扩展逻辑如下：

  • 计算需要的字节数：ceil(offset + 1 / 8)（offset是位索引，从0开始）；
  • 分配新的SDS空间（根据Redis的扩容策略，通常会预留额外空间以减少后续扩容次数）；
  • 将原数据复制到新空间，并填充0至扩展的字节；
  • 更新SDS的len（当前长度）和free（剩余空间）字段。

示例：当前字符串长度为2字节（16位），执行SETBIT key 20 1（设置位20为1）：

  • 需要的字节数：ceil(21/8) = 3字节（位20对应第3个字节的第4位：20 = 8*2 +4）；
  • 扩展字符串至3字节，前2字节保留原数据，第3字节填充0；
  • 将第3字节的第4位（1<<4 = 16）设置为1，最终第3字节的值为0x10（二进制00010000）。

3. 核心命令的底层实现 ​

Bitmap的所有命令都基于**位掩码（Bit Mask）**操作，以下是关键命令的原理拆解：

（1）SETBIT：设置位值 ​

  • 命令格式：SETBIT key offset value（value只能是0或1）；
  • 底层逻辑：
    1. 计算位对应的字节位置：byte_pos = offset / 8；
    2. 计算位对应的字节内偏移：bit_pos = offset % 8；
    3. 生成位掩码：mask = 1 << bit_pos（例如bit_pos=2，掩码是00000100）；
    4. 修改字节值：
      • 若value=1：用OR操作（byte |= mask），将目标位设为1；
      • 若value=0：用AND操作（byte &= ~mask），将目标位设为0；
    5. 写回字节至SDS，并更新字符串长度（若需要扩展）。

示例：SETBIT key 10 1（设置位10为1）：

  • byte_pos = 10 /8 = 1（第2个字节）；
  • bit_pos =10 %8 =2（字节内第2位）；
  • 掩码：1<<2 =4（00000100）；
  • 若原字节值为0x00（00000000），则修改后为0x04（00000100）。

（2）GETBIT：获取位值 ​

  • 命令格式：GETBIT key offset；
  • 底层逻辑：
    1. 计算byte_pos和bit_pos（同SETBIT）；
    2. 若byte_pos超过字符串长度，返回0（未设置的位默认是0）；
    3. 生成掩码mask =1 << bit_pos；
    4. 用AND操作（byte & mask）提取目标位：若结果非0，返回1，否则返回0。

示例：GETBIT key 10（获取位10的值）：

  • 若字节1的值为0x04（00000100），则0x04 & 4 =4（非0），返回1。

（3）BITCOUNT：统计1的个数 ​

  • 命令格式：BITCOUNT key [start end]（start和end是字节索引，默认统计全部位）；
  • 底层逻辑： Redis使用预计算查表法（bitcount_table）加速统计，该表存储了每个字节（0~255）的1的个数（例如bitcount_table[0x0f] =4，bitcount_table[0xff] =8）。
    1. 遍历指定范围内的每个字节；
    2. 查表获取该字节的1的个数，累加得到总次数。

优化：对于大范围（如超过1024字节），Redis会使用64位整数的位计数指令（如x86的popcnt指令），将数据分成64位块，快速统计每个块的1的个数，进一步提升速度。

示例：字符串"\x03"（00000011）的BITCOUNT结果为2（位0和位1为1）。

（4）BITOP：位运算（AND/OR/XOR/NOT） ​

  • 命令格式：BITOP OP dstkey srckey1 srckey2 ...（OP可以是AND、OR、XOR、NOT）；
  • 底层逻辑：
    1. 计算输出字符串的长度：max(len(srckey1), len(srckey2), ...)（NOT操作的输出长度等于输入长度）；
    2. 逐个字节处理：
      • 对于AND/OR/XOR：取每个输入字符串的对应字节（若输入字符串长度不足，视为0），执行位运算；
      • 对于NOT：取输入字符串的对应字节，执行取反操作（~byte）；
    3. 将结果字节写入输出字符串（dstkey）。

示例：BITOP OR dst a b（合并a和b的位，取或）：

  • a的字符串为"\x15"（00010101，位0、2、4为1）；
  • b的字符串为"\x2c"（00101100，位2、3、5为1）；
  • 或运算后，dst的字符串为"\x3d"（00111101，位0、2、3、4、5为1）。

（5）BITPOS：查找第一个0或1的位置 ​

  • 命令格式：BITPOS key bit [start end]（bit是0或1，start和end是字节索引）；
  • 底层逻辑： Redis使用二分查找+块遍历加速查找：
    1. 二分查找找到第一个包含目标位的块（如每8字节一块）；
    2. 在该块内遍历每个字节，找到第一个包含目标位的字节；
    3. 在该字节内遍历每个位（从位0到位7），找到第一个目标位，计算其全局索引。

示例：字符串"\x0b"（00001011，位0、1、3为1）的BITPOS key 0结果为2（第一个0的位置是位2）。

三、Bitmap的优势 ​

  1. 空间效率：1位存储1个布尔值，远优于其他数据类型（如Set的4字节/元素）。
  2. 时间效率：位操作是原子的，且命令的时间复杂度低（SETBIT/GETBIT为O(1)，BITCOUNT/BITOP为O(n)，n是处理的字节数）。
  3. 功能丰富：支持位设置、获取、统计、合并、查找等操作，满足多种场景需求。

四、Bitmap的适用场景 ​

Bitmap适合存储海量布尔值且需要高效统计的场景，以下是典型案例：

1. 用户签到系统 ​

  • 设计：用sign:user:uid作为key，offset表示日期（如从2025-01-01开始的天数），1表示签到，0表示未签到。
  • 操作：
    • 签到：SETBIT sign:user:123 191 1（2025-07-11是第191天）；
    • 统计当月签到次数：BITCOUNT sign:user:123 24 26（假设7月有31天，对应字节索引24~26，共31位）；
    • 查找第一个未签到日期：BITPOS sign:user:123 0 24 26。

2. 活跃用户统计 ​

  • 设计：用active:yyyyMMdd作为key，offset表示用户ID，1表示活跃。
  • 操作：
    • 统计周活跃用户：BITOP OR active:week active:20250706 active:20250707 ... active:20250712，然后BITCOUNT active:week；
    • 统计同时活跃在周一和周二的用户：BITOP AND active:monday-tuesday active:20250707 active:20250708，然后BITCOUNT。

3. 用户在线状态 ​

  • 设计：用online作为key，offset表示用户ID，1表示在线，0表示离线。
  • 操作：
    • 获取用户在线状态：GETBIT online 123；
    • 统计在线人数：BITCOUNT online。

4. 布隆过滤器（Bloom Filter） ​

  • 设计：用Bitmap实现布隆过滤器，用于快速判断元素是否在集合中（有一定误判率）。
  • 原理：对元素进行多次哈希，将对应的位设为1；查询时，若所有哈希位都为1，则元素可能存在（否则一定不存在）。

五、Bitmap的局限性 ​

  1. 偏移量限制：虽然Redis支持2^32-1的偏移量（约4GB位），但过大的偏移量会导致内存浪费（如设置偏移量为1亿，需要12.5MB空间，即使大部分位是0）。
  2. 范围查询效率：遍历所有位（如查找所有签到日期）的效率较低，适合统计而非明细查询。
  3. 复杂查询麻烦：例如查找连续签到超过7天的用户，需要结合BITOP和BITPOS命令，逻辑较复杂。

六、总结 ​

Bitmap是Redis中最高效的数据类型之一，通过位级操作实现了高空间效率和高时间效率，适合处理海量布尔值的场景。其底层依赖字符串（SDS），通过位索引与字节映射、动态扩展、预计算查表等机制，保证了操作的高效性。

理解Bitmap的原理，能帮助我们在用户签到、活跃统计、在线状态等场景中，选择最合适的数据类型，发挥Redis的最大性能。

关键结论：

  • Bitmap的本质是字符串的位级使用；
  • 位索引从0开始，每个字节对应8位；
  • 核心优势是空间效率和位操作原子性；
  • 适合海量布尔值存储与统计的场景。