Redis 中 Bitmap 原理和应用

Bitmap

Redis中的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 的操作命令不多且使用简单,主要用到的就是SETBITGETBITBITCOUNTBITOP几个命令。

SETBIT:用于设置指定偏移量上的位值,其时间复杂度为 O (1)。例如,当用户答对了第 7 题时,可以将题号对应的偏移量为 7 的位值设置为 1,以此表示该题已被答对。

# 用户key answer:user:1
# 偏移量:题号 7 
# 题答对,置为 1
SETBIT answer:user:1 7 1 

GETBIT:获取指定偏移量上的位值,同样具有高效的时间复杂度。可以快速查询用户对特定题号的回答状态。

# 查询用户第 7 题的回答情况,1-答对 0-答错
GETBIT answer:user:1 7

BITCOUNT:用于统计位值中被设置为 1 的数量。比如上边我可以很容易统计答对全部题目的用户,但也仅能知道个数,无法查看具体的哪个题目。

# 统计用户答对题为 1 的个数
BITCOUNT answer:user:1 

BITOP:对一个或多个 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 就不适用了;

  • 只有当数据比较密集时才有优势,如果我们只设置(20,30,888888888)三个偏移量的位值,则需要创建一个 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 999999

BF.INFO:获取布隆过滤器的信息,包括容量、误判率等。

BF.INFO <key>

BF.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 中。如果有大量恶意请求查询不存在的商品,通过布隆过滤器可以快速判断这些商品不存在,从而避免了对数据库的查询,减轻了数据库的压力。

  • 邮箱黑名单过滤:在邮件系统中,可以使用布隆过滤器来过滤垃圾邮件和恶意邮件。将已知的垃圾邮件发送者的地址或特征存储在布隆过滤器中,新邮件来时判断发送者是否在黑名单中。

  • 对爬虫网址进行过滤:在爬虫程序中,为了避免重复抓取相同的网址,可以使用布隆过滤器来记录已经抓取过的网址。新网址出现时,先判断是否已抓取过。

总结

        本文梳理了 bitmap 和 布隆过滤器的原理、用法以及它们各自的优缺点和应用场景,大环境不好更要多多提升自身技术能力,而且现在面试三句不离大数据量和高并发,此类问题想要应对自如,不仅要有深度还要有广度,掌握这两个知识点多提供一种答案也是好的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/912900.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于 STM32 的天气时钟项目中添加天气数据的网络获取功能

基于 STM32 的天气时钟项目中添加天气数据的网络获取功能&#xff0c;您需要确保您的开发环境具备网络连接能力。这里以 ESP8266 Wi-Fi 模块为例&#xff0c;详细说明如何实现网络获取天气数据的功能。 1. 硬件连接 连接 ESP8266 模块 请参考以下连接方式&#xff0c;将 ESP82…

mysql-springboot netty-flink-kafka-spark(paimon)-minio

1、下载spark源码并编译 mkdir -p /home/bigdata && cd /home/bigdata wget https://archive.apache.org/dist/spark/spark-3.4.3/spark-3.4.3.tgz 解压文件 tar -zxf spark-3.4.3.tgz cd spark-3.4.3 wget https://raw.githubusercontent.com/apache/incubator-celeb…

【Spring】体系结构

Spring框架至今集成了多个模块&#xff0c;这些模块分布在数据访问/集成&#xff08;Data Access/Integration&#xff09;、Web层、面向切面的编程&#xff08;Aspect Oriented Programming&#xff0c;AOP&#xff09;模块、植入&#xff08;Instrumentation&#xff09;模块…

软件缺陷等级评定综述

1. 前言 正确评估软件缺陷等级&#xff0c;在项目的生命周期中有着重要的作用&#xff1a; 指导缺陷修复的优先级和资源分配 在软件开发和维护过程中&#xff0c;资源&#xff08;包括人力、时间和资金&#xff09;是有限的。通过明确缺陷的危险等级&#xff0c;可以帮助团队合…

Linux:vim命令总结及环境配置

文章目录 前言一、vim的基本概念二、vim模式命令解析1. 命令模式1&#xff09;命令模式到其他模式的转换&#xff1a;2&#xff09;光标定位&#xff1a;3&#xff09;其他命令&#xff1a; 2. 插入模式3. 底行模式4. 替换模式5. 视图模式6. 外部命令 三、vim环境的配置1. 环境…

Obsidian的Git插件设置配置全流程 -- 简单的电脑端多平台同步方案及常见问题

Obsidian的Git插件设置配置全流程 -- 简单的电脑端多平台同步方案及常见问题 参考文章引言1. git 介绍及安装2. git 本地配置及远程仓库链接3. obsidian 的 git 插件4. 常用的使用场景和对应的命令4.1. 本地仓库已推送到远端&#xff0c;如何在另一个电脑上第一次同步4.2 多端同…

【优选算法篇】微位至简,数之恢宏——解构 C++ 位运算中的理与美

文章目录 C 位运算详解&#xff1a;基础题解与思维分析前言第一章&#xff1a;位运算基础应用1.1 判断字符是否唯一&#xff08;easy&#xff09;解法&#xff08;位图的思想&#xff09;C 代码实现易错点提示时间复杂度和空间复杂度 1.2 丢失的数字&#xff08;easy&#xff0…

Redis(3):持久化

一、Redis高可用概述 在介绍Redis高可用之前&#xff0c;先说明一下在Redis的语境中高可用的含义。   我们知道&#xff0c;在web服务器中&#xff0c;高可用是指服务器可以正常访问的时间&#xff0c;衡量的标准是在多长时间内可以提供正常服务&#xff08;99.9%、99.99%、9…

高亚科技签约酸动力,助力研发管理数字化升级

近日&#xff0c;中国企业管理软件资深服务商高亚科技与广东酸动力生物科技有限公司&#xff08;以下简称“酸动力”&#xff09;正式签署合作协议。借助高亚科技的8Manage PM项目管理软件&#xff0c;酸动力将进一步优化项目过程跟踪与节点监控&#xff0c;提升研发成果的高效…

大模型领域最值得看的 9 本新书,找到了

在人工智能革命的浪潮中&#xff0c;程序员们正站在技术变革的最前沿。本书单精选了关于人工智能在各行业应用的最新著作&#xff0c;从医疗诊断到金融风控&#xff0c;从智能制造到智慧城市&#xff0c;全面展现AI如何重塑行业生态&#xff0c;推动社会进步。通过阅读这些书籍…

加入GitHub Spark需要申请

目录 加入GitHub Spark需要申请 GitHub Spark 一、产品定位与特点 二、核心组件与功能 三、支持的AI模型 四、应用场景与示例 五、未来展望 六、申请体验 加入GitHub Spark需要申请 GitHub Spark 是微软旗下GitHub在2024年10月30日的GitHub Universe大会上推出的一款革…

Rust移动开发:Rust在iOS端集成使用介绍

iOS调用Rust 上篇介绍了 Rust移动开发&#xff1a;Rust在Android端集成使用介绍, 这篇主要看下iOS上如何使用Rust&#xff0c;Rust可以给移动端开发提供跨平台&#xff0c;通用组件支持。 该篇适合对iOS、Rust了解&#xff0c;想知道如何整合调用和编译的&#xff0c;如果想要…

【月之暗面kimi-注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

2024 CSS保姆级教程四

CSS中的动画 CSS动画&#xff08;CSS Animations&#xff09;是为层叠样式表建议的允许可扩展标记语言&#xff08;XML&#xff09;元素使用CSS的动画的模块​ 即指元素从一种样式逐渐过渡为另一种样式的过程​ 常见的动画效果有很多&#xff0c;如平移、旋转、缩放等等&#…

[C++11] Lambda 表达式

lambda 表达式&#xff08;Lambda Expressions&#xff09;作为一种匿名函数&#xff0c;为开发者提供了简洁、灵活的函数定义方式。相比传统的函数指针和仿函数&#xff0c;lambda 表达式在简化代码结构、提升代码可读性和编程效率方面表现出色。 Lambda 表达式的基本语法 在…

AI4SCIENSE(鄂维南院士:再谈AI for Science)

鄂维南院士&#xff1a;再谈AI for Science_哔哩哔哩_bilibili 以往处理高维问题 量子力学&#xff1a;单变量乘积 统计学&#xff1a;旋转 AI4S 处理数据 蛋白质折叠&#xff1f; 不是纯粹的数据驱动 物理学等学科基本原理 例&#xff1a;分子动力学 数据模型 流程图 这…

接收nVisual中rabbitmq数据不成功问题排查

rabbitmq服务部署成功的情况下&#xff0c;消息对接不成功一般原因为消息发送失败&#xff0c;发送失败大多数可能为global_settings表配置错误。下面从两个方面解决消息对接不成功问题。 1.数据是否成功发送 检查global_settings表中rabbitmq发送消息配置信息是否正确 #MQS…

SpringBoot框架学习总结 及 整合 JDBC Mybatis-plus JPA Redis 我的学习笔记

SpringBoot框架学习总结 及 整合 JDBC Mybatis-plus JPA Redis 我的学习笔记 一、SpringBoot概述二、创建SpringBoot程序1. 使用maven方式创构建2. 使用Spring Initializr构建3. SpringBoot热部署4. SpringBoot的跨域处理 三、基础配置1.配置文件的作用2.配置文件格式2.yaml3.S…

【AIGC】如何通过ChatGPT轻松制作个性化GPTs应用

创建个性化的GPTs应用是一个涉及技术、设计和用户体验的过程。以下是详细步骤&#xff1a; ###1.确定应用目标和用户群体 在开始之前&#xff0c;你需要明确你的应用的目标和目标用户。这将帮助你在设计、开发和个性化方面做出相应的决策。例如&#xff0c;如果你的应用是为了…

strtok函数详解

strtok函数 strtok 函数是一个字符串分割函数&#xff0c;用于将字符串分割成一系列的标记。这个函数通过一组分隔符字符来确定标记的边界&#xff0c;每次调用都会返回字符串中的下一个标记&#xff0c;并且将原始字符串中的分隔符替换为空字符‘\0’&#xff0c;从而实际上是…