有个兄弟私下跟我说他在面试狗东时有一道面试题没回答上来Redis 的Bitmap和布隆过滤器啥区别与关系其实就是考小老弟对这两种工具的底层数据结构是否了解不算太难的题。不过bitmap和布隆过滤器在大数据量和高并发业务的使用频率不低知识点应该掌握下既然问了那咱们简单的梳理下它们的底层原理、应用场景以及它们之间的关联。BitmapRedis中的Bitmap位图是一种较为特殊数据类型它以最小单位bit来存储数据我们知道一个字节由 8个 bit 组成和传统数据结构用字节存储相比这使得它在处理大量二值状态true、false 或 0、1等只有两种状态数据时具有极高的空间效率。不过它不是一种全新的数据类型其底层实现仍是基于String类型。便于理解你可以将 Bitmap 的底层结构看成是由一系列 bit 位组成的数组在此数组中每个位都对应一个偏移量类似数组的下标。通过将特定偏移量上的位值设置为 0 或 1来表示不同的状态。比如我们要设计一个答题游戏系统。其规则为若用户答对全部 7 道题则可获得大奖。每个答题用户都有自己的 key即answer:user:X。使用 bitmap 记录用户的答题情况将题号设置为对应偏移量当用户答对 ✅ 题目时 偏移量位值设为 1当用户答错 ❌ 题目时位值设为 0。假如用户user:1答对了 2、5、7 号题可将对应偏移量为 2、5、7 的位值设置为 1其余位值默认设为 0。若要查看该用户对某个题目的回答情况只需按照偏移量遍历此数据结构一旦碰到位值为 1 的情况即表示该题回答正确。答题活动结束后接下来需要统计获奖者即那些全部答对 7 道题的用户。要快速统计用户是否全部答对题目可以使用BITCOUNT命令来统计位值中被设置为 1 的数量。通过执行BITCOUNT answer:userX 7这样的操作进行判断若结果等于 7则表明该用户全部答对了题目。聪明的你或许会产生疑惑如果想用 bitmap 判断邮箱地址是否在黑名单内偏移量该如何设置呢遗憾的是bitmap 并不支持直接以字符串作为偏移量。不过我们可以对邮箱进行哈希运算得到哈希值进而算出偏移量。由于用到哈希运算就不可避免地会出现数据碰撞问题即不同的字符串可能得出相同的哈希值。这样一来状态判断就可能不准确。别急后边介绍布隆过滤器Bloom Filter看它如何来优化这个问题。操作命令Bitmap 的操作命令不多且使用简单主要用到的就是SETBIT、GETBIT、BITCOUNT、BITOP几个命令。SETBIT用于设置指定偏移量上的位值其时间复杂度为 O (1)。例如当用户答对了第 7 题时可以将题号对应的偏移量为 7 的位值设置为 1以此表示该题已被答对。# 用户key answer:user:1 # 偏移量题号 7 # 题答对置为 1 SETBIT answer:user:1 7 1GETBIT获取指定偏移量上的位值同样具有高效的时间复杂度。可以快速查询用户对特定题号的回答状态。# 查询用户第 7 题的回答情况1-答对 0-答错 GETBIT answer:user:1 7BITCOUNT用于统计位值中被设置为 1 的数量。比如上边我可以很容易统计答对全部题目的用户但也仅能知道个数无法查看具体的哪个题目。# 统计用户答对题为 1 的个数 BITCOUNT answer:user:1BITOP对一个或多个 bitmap 进行位运算并将结果保存到新的键中支持 AND、OR、NOT、XOR 四种操作。这个命令的用法是将多个bitmap中相同偏移量的位值进行运算。若我想知道用户 1 和用户 2 都答对的题目经过 AND 运算后假如只有题号 1 是两个用户都答对的题目那么生成新的结果集中就只有题号 1 对应的位值为 1。# 用户1 和 用户2 都答对的题目可以看出只有题号1的都答对了 SETBIT answer:user:1 1 1 SETBIT answer:user:1 2 0 SETBIT answer:user:1 3 1 SETBIT answer:user:2 1 1 SETBIT answer:user:2 2 1 SETBIT answer:user:2 3 0 BITOP AND resultbitmap answer:user:1 answer:user:2扬长避短优点极高空间效率bitmap 是真的节省数据存储空间。粗略的算一下一亿位的 Bitmap 大概才占 12MB 的内存相比其他数据结构能极大地节省存储空间快速查询位操作通常比其他数据结构查询速度更快。无论是设置位值还是获取位值时间复杂度都为 O (1)能够快速响应查询请求易于操作支持单个位操作、位统计、位逻辑运算等运算效率高不需要进行比较和移位缺点由于数据结构特点导致它仅适用于表示两种状态即 0 和 1。对于需要表示更多状态的情况Bitmap 就不适用了只有当数据比较密集时才有优势如果我们只设置2030888888888三个偏移量的位值则需要创建一个 99999999 长度的 BitMap 但是实际上只存了3个数据这时候就有很大的空间浪费碰到这种问题的话可以通过引入另一个Roaring BitMap来解决应用场景看到 Bitmap 还是比较简单的一种数据结构占用空间小查询效率高非常适用于记录状态的场景它的应用场景很常见比如用户签到状态连续签到天数用户的在线状态统计活跃用户问卷答题等等吧布隆过滤器上边咱们提到 bitmap 记录字符元素的状态时需要先借助哈希运算得出偏移量。但引入哈希运算后可能会出现哈希碰撞的情况导致状态误判。布隆过滤器对这个问题做了进一步的优化做到了可控误判率当我们将一个邮箱地址添加到集合中多个不同的哈希函数会将这个邮箱地址映射到 bitmap 中的不同偏移量位置上且将这些位值置为 1。要判断邮箱地址是否在集合中通过相同的哈希函数映射到 bitmap 上的多个位置如果这些位上的值都为 1则邮箱可能存在集合中如果有任何一个位置的值为 0则元素一定不在集合中。这是布隆过滤器的特点。虽然但是布隆过滤器还是会发生误判的情况额但好在我们可以通过调整布隆过滤器的大小和哈希函数的数量来控制误判率。操作命令布隆过滤器的命令也不多主要用到的如下几个BF.RESERVE创建一个新的布隆过滤器并指定容量 capacity 和误判率 error_rate。BF.RESERVE key error_rate capacity BF.RESERVE myfilter 0.000001 999999BF.INFO获取布隆过滤器的信息包括容量、误判率等。BF.INFO keyBF.ADD和BF.MADD分别是向布隆过滤器中添加元素和批量添加# 向布隆过滤器中添加元素 BF.ADD myfilter hello BF.MADD key item [item ...]BF.EXISTS和BF.MEXISTS分别是检查布隆过滤器中某个元素和批量检查元素是否存在# 元素是否存在于布隆过滤器中 BF.EXISTS myfilter hello # 元素是否存在于布隆过滤器中 BF.MEXISTS key item [item ...]扬长避短优点布隆过滤器的空间占用也是极小它本身不存储完整的数据和 bitmap 一样底层也是通过 bit 位来表示数据是否存在。性能比较稳定无论集合中元素的数量有多少插入和查询操作的时间复杂度都非常低通常为 O (k)其中 k 是哈希函数的个数。也就是说在处理大规模数据时布隆过滤器的性能不会随着数据量的增加而急剧下降。缺点存在一定的误识别率布隆过滤器存在误判的情况即当一个元素实际上不在集合中时有可能被判断为在集合中。这是因为多个元素可能通过哈希函数映射到相同的位置导致误判。但是当布隆过滤器判断一个元素不在集合中时则是 100% 正确的。删除元素比较困难一般情况下不能直接从布隆过滤器中删除元素。这是因为一个位置可能被多个元素映射到如果直接将该位置的值置为 0可能会影响其他元素的判断。应用场景布隆过滤器存在一定的误判所以使用它的场景就一定要允许不准确的情况发生解决 Redis 缓存穿透问题秒杀商品详情通常会被缓存到 Redis 中。如果有大量恶意请求查询不存在的商品通过布隆过滤器可以快速判断这些商品不存在从而避免了对数据库的查询减轻了数据库的压力。邮箱黑名单过滤在邮件系统中可以使用布隆过滤器来过滤垃圾邮件和恶意邮件。将已知的垃圾邮件发送者的地址或特征存储在布隆过滤器中新邮件来时判断发送者是否在黑名单中。对爬虫网址进行过滤在爬虫程序中为了避免重复抓取相同的网址可以使用布隆过滤器来记录已经抓取过的网址。新网址出现时先判断是否已抓取过。太多太多了..... 有个兄弟私下跟我说他在面试狗东时有一道面试题没回答上来Redis 的Bitmap和布隆过滤器啥区别与关系其实就是考小老弟对这两种工具的底层数据结构是否了解不算太难的题。不过bitmap和布隆过滤器在大数据量和高并发业务的使用频率不低知识点应该掌握下既然问了那咱们简单的梳理下它们的底层原理、应用场景以及它们之间的关联。BitmapRedis中的Bitmap位图是一种较为特殊数据类型它以最小单位bit来存储数据我们知道一个字节由 8个 bit 组成和传统数据结构用字节存储相比这使得它在处理大量二值状态true、false 或 0、1等只有两种状态数据时具有极高的空间效率。不过它不是一种全新的数据类型其底层实现仍是基于String类型。便于理解你可以将 Bitmap 的底层结构看成是由一系列 bit 位组成的数组在此数组中每个位都对应一个偏移量类似数组的下标。通过将特定偏移量上的位值设置为 0 或 1来表示不同的状态。比如我们要设计一个答题游戏系统。其规则为若用户答对全部 7 道题则可获得大奖。每个答题用户都有自己的 key即answer:user:X。使用 bitmap 记录用户的答题情况将题号设置为对应偏移量当用户答对 ✅ 题目时 偏移量位值设为 1当用户答错 ❌ 题目时位值设为 0。假如用户user:1答对了 2、5、7 号题可将对应偏移量为 2、5、7 的位值设置为 1其余位值默认设为 0。若要查看该用户对某个题目的回答情况只需按照偏移量遍历此数据结构一旦碰到位值为 1 的情况即表示该题回答正确。答题活动结束后接下来需要统计获奖者即那些全部答对 7 道题的用户。要快速统计用户是否全部答对题目可以使用BITCOUNT命令来统计位值中被设置为 1 的数量。通过执行BITCOUNT answer:userX 7这样的操作进行判断若结果等于 7则表明该用户全部答对了题目。聪明的你或许会产生疑惑如果想用 bitmap 判断邮箱地址是否在黑名单内偏移量该如何设置呢遗憾的是bitmap 并不支持直接以字符串作为偏移量。不过我们可以对邮箱进行哈希运算得到哈希值进而算出偏移量。由于用到哈希运算就不可避免地会出现数据碰撞问题即不同的字符串可能得出相同的哈希值。这样一来状态判断就可能不准确。别急后边介绍布隆过滤器Bloom Filter看它如何来优化这个问题。操作命令Bitmap 的操作命令不多且使用简单主要用到的就是SETBIT、GETBIT、BITCOUNT、BITOP几个命令。SETBIT用于设置指定偏移量上的位值其时间复杂度为 O (1)。例如当用户答对了第 7 题时可以将题号对应的偏移量为 7 的位值设置为 1以此表示该题已被答对。# 用户key answer:user:1 # 偏移量题号 7 # 题答对置为 1 SETBIT answer:user:1 7 1GETBIT获取指定偏移量上的位值同样具有高效的时间复杂度。可以快速查询用户对特定题号的回答状态。# 查询用户第 7 题的回答情况1-答对 0-答错 GETBIT answer:user:1 7BITCOUNT用于统计位值中被设置为 1 的数量。比如上边我可以很容易统计答对全部题目的用户但也仅能知道个数无法查看具体的哪个题目。# 统计用户答对题为 1 的个数 BITCOUNT answer:user:1BITOP对一个或多个 bitmap 进行位运算并将结果保存到新的键中支持 AND、OR、NOT、XOR 四种操作。这个命令的用法是将多个bitmap中相同偏移量的位值进行运算。若我想知道用户 1 和用户 2 都答对的题目经过 AND 运算后假如只有题号 1 是两个用户都答对的题目那么生成新的结果集中就只有题号 1 对应的位值为 1。# 用户1 和 用户2 都答对的题目可以看出只有题号1的都答对了 SETBIT answer:user:1 1 1 SETBIT answer:user:1 2 0 SETBIT answer:user:1 3 1 SETBIT answer:user:2 1 1 SETBIT answer:user:2 2 1 SETBIT answer:user:2 3 0 BITOP AND resultbitmap answer:user:1 answer:user:2扬长避短优点极高空间效率bitmap 是真的节省数据存储空间。粗略的算一下一亿位的 Bitmap 大概才占 12MB 的内存相比其他数据结构能极大地节省存储空间快速查询位操作通常比其他数据结构查询速度更快。无论是设置位值还是获取位值时间复杂度都为 O (1)能够快速响应查询请求易于操作支持单个位操作、位统计、位逻辑运算等运算效率高不需要进行比较和移位缺点由于数据结构特点导致它仅适用于表示两种状态即 0 和 1。对于需要表示更多状态的情况Bitmap 就不适用了只有当数据比较密集时才有优势如果我们只设置2030888888888三个偏移量的位值则需要创建一个 99999999 长度的 BitMap 但是实际上只存了3个数据这时候就有很大的空间浪费碰到这种问题的话可以通过引入另一个Roaring BitMap来解决应用场景看到 Bitmap 还是比较简单的一种数据结构占用空间小查询效率高非常适用于记录状态的场景它的应用场景很常见比如用户签到状态连续签到天数用户的在线状态统计活跃用户问卷答题等等吧布隆过滤器上边咱们提到 bitmap 记录字符元素的状态时需要先借助哈希运算得出偏移量。但引入哈希运算后可能会出现哈希碰撞的情况导致状态误判。布隆过滤器对这个问题做了进一步的优化做到了可控误判率当我们将一个邮箱地址添加到集合中多个不同的哈希函数会将这个邮箱地址映射到 bitmap 中的不同偏移量位置上且将这些位值置为 1。要判断邮箱地址是否在集合中通过相同的哈希函数映射到 bitmap 上的多个位置如果这些位上的值都为 1则邮箱可能存在集合中如果有任何一个位置的值为 0则元素一定不在集合中。这是布隆过滤器的特点。虽然但是布隆过滤器还是会发生误判的情况额但好在我们可以通过调整布隆过滤器的大小和哈希函数的数量来控制误判率。操作命令布隆过滤器的命令也不多主要用到的如下几个BF.RESERVE创建一个新的布隆过滤器并指定容量 capacity 和误判率 error_rate。BF.RESERVE key error_rate capacity BF.RESERVE myfilter 0.000001 999999BF.INFO获取布隆过滤器的信息包括容量、误判率等。BF.INFO keyBF.ADD和BF.MADD分别是向布隆过滤器中添加元素和批量添加# 向布隆过滤器中添加元素 BF.ADD myfilter hello BF.MADD key item [item ...]BF.EXISTS和BF.MEXISTS分别是检查布隆过滤器中某个元素和批量检查元素是否存在# 元素是否存在于布隆过滤器中 BF.EXISTS myfilter hello # 元素是否存在于布隆过滤器中 BF.MEXISTS key item [item ...]扬长避短优点布隆过滤器的空间占用也是极小它本身不存储完整的数据和 bitmap 一样底层也是通过 bit 位来表示数据是否存在。性能比较稳定无论集合中元素的数量有多少插入和查询操作的时间复杂度都非常低通常为 O (k)其中 k 是哈希函数的个数。也就是说在处理大规模数据时布隆过滤器的性能不会随着数据量的增加而急剧下降。缺点存在一定的误识别率布隆过滤器存在误判的情况即当一个元素实际上不在集合中时有可能被判断为在集合中。这是因为多个元素可能通过哈希函数映射到相同的位置导致误判。但是当布隆过滤器判断一个元素不在集合中时则是 100% 正确的。删除元素比较困难一般情况下不能直接从布隆过滤器中删除元素。这是因为一个位置可能被多个元素映射到如果直接将该位置的值置为 0可能会影响其他元素的判断。应用场景布隆过滤器存在一定的误判所以使用它的场景就一定要允许不准确的情况发生解决 Redis 缓存穿透问题秒杀商品详情通常会被缓存到 Redis 中。如果有大量恶意请求查询不存在的商品通过布隆过滤器可以快速判断这些商品不存在从而避免了对数据库的查询减轻了数据库的压力。邮箱黑名单过滤在邮件系统中可以使用布隆过滤器来过滤垃圾邮件和恶意邮件。将已知的垃圾邮件发送者的地址或特征存储在布隆过滤器中新邮件来时判断发送者是否在黑名单中。对爬虫网址进行过滤在爬虫程序中为了避免重复抓取相同的网址可以使用布隆过滤器来记录已经抓取过的网址。新网址出现时先判断是否已抓取过。太多太多了..... 
