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 1SETBIT answer:user:2 1 1
SETBIT answer:user:2 2 1
SETBIT answer:user:2 3 0BITOP 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 和 布隆过滤器的原理、用法以及它们各自的优缺点和应用场景,大环境不好更要多多提升自身技术能力,而且现在面试三句不离大数据量和高并发,此类问题想要应对自如,不仅要有深度还要有广度,掌握这两个知识点多提供一种答案也是好的。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Springboot3.3.5 启动流程(源码分析)

一图搞懂 SpringBoot 启动流程&#xff08;清晰明了&#xff09;&#xff1a; createWebServer &#xff08;ServletWebApplicationContext&#xff09;流程 finishBeanFactoryInitialization&#xff08;ServletWebApplicationContext&#xff09;Bean装配流程 真正干活的&am…

CSS实现图片3D立体效果

概述 本文主要讲述如何通过 CSS 简单的设置就可以实现图片的 3D 立体效果。 3D 立体效果 当鼠标移入某一个图片上时,其余图片会像该图片倾斜。 具体实现 静图如下: 倒影效果图片会有一个倒影效果,其代码如下: <style>img {-webkit-box-reflect: below 1px linea…

java: 无法访问org.springframework.web.bind.annotation.RequestMapping

一、报错问题 java: 无法访问org.springframework.web.bind.annotation.RequestMapping 二、原因分析 SpringBoot使用了3.0或者3.0以上&#xff0c;因为Spring官方发布从Spring6以及SprinBoot3.0开始最低支持JDK17。所以仅需要将SpringBoot版本降低为3.0以下即可&#xff08;或…

Node.js:Express 服务 路由

Node.js&#xff1a;Express 服务 & 路由 创建服务处理请求req对象 静态资源托管托管多个资源挂载路径前缀 路由模块化 Express是Node.js上的一个第三方框架&#xff0c;可以快速开发一个web框架。本质是一个包&#xff0c;可以通过npm直接下载。 创建服务 Express创建一…

知识中台赋能法律咨询服务:八大核心优势

法律咨询服务领域&#xff0c;知识中台以其独特的功能和优势&#xff0c;为行业发展注入了新的活力。以下是知识中台在法律咨询服务中展现的八大核心优势&#xff1a; 一、法律知识资源的全面整合 知识中台致力于收集、整理和整合各类法律知识资源&#xff0c;包括法律法规、…

【青牛科技】GC5931:工业风扇驱动芯片的卓越替代者

在工业领域&#xff0c;工业风扇的稳定高效运行对于维持良好的生产环境至关重要。而驱动芯片作为工业风扇控制系统的核心元件&#xff0c;其性能直接影响风扇的工作状态。芯麦 GC5931 作为一款新型驱动芯片&#xff0c;在替代 A5931/Allegro 应用于工业风扇中展现出了非凡的优势…

使用Netty实现一个简单的聊天服务器

✅作者简介&#xff1a;热爱Java后端开发的一名学习者&#xff0c;大家可以跟我一起讨论各种问题喔。 &#x1f34e;个人主页&#xff1a;Hhzzy99 &#x1f34a;个人信条&#xff1a;坚持就是胜利&#xff01; &#x1f49e;当前专栏&#xff1a;Netty &#x1f96d;本文内容&a…

【HarmonyOS】鸿蒙应用低功耗蓝牙BLE的使用心得 (二)

【HarmonyOS】鸿蒙应用低功耗蓝牙BLE的使用心得 &#xff08;二&#xff09; 一、前言 目前鸿蒙应用的实现逻辑&#xff0c;基本都是参考和移植Android端来实现。针对BLE低功耗蓝牙来说&#xff0c;在鸿蒙化的实现过程中。我们发现了&#xff0c;鸿蒙独有的优秀点&#xff0c…

第六十三周周报 GCN-CNNGA

文章目录 week 63 GCN-CNNGA摘要Abstract1. 题目2. Abstract3. 文献解读3.1 Introduction3.2 创新点 4. 网络结构4.1 数据分析4.2 混合深度学习框架的发展4.3 Mul4.4 CNN block4.5 GCN block4.6 GRU block4.7 注意力机制4.8 模型评估标准 5. 实验结果5.1 不同邻接矩阵的性能评价…

geoserver+postgis 最短路径规划常见问题记录

一、说明 具体实现步骤可参考其他博文&#xff0c;下面的这个博主写的很详细&#xff0c;步骤很清晰&#xff0c;注释也很全。geoserverpostgis 最短路径规划_geoserver 最短路径 存储过程-CSDN博客 本次文章&#xff0c;仅记录过程中需要注意的方面。 二、数据预处理 目标&a…

石油安全理论知识题库 考试宝在线刷题

一、单选题&#xff08;每题有4个选项&#xff0c;其中只有1个是正确的&#xff0c;将正确的选项号填入括号内&#xff09; 1.新修订的《中华人民共和国安全生产法》于&#xff08; &#xff09;正式实施。 A、2014年1月1日 B、2014年12月1日 C、2015年1月1日 D、2015年…

航空标志灯技术革新:提升夜间飞行安全

航空标志灯 随着低空飞行活动的增多和新型飞行器&#xff08;如无人机、热气球和直升机&#xff09;的普及&#xff0c;地面重要设施的安全面临前所未有的挑战。因此&#xff0c;航空标志灯的安装变得尤为重要。它们通过提升城市天际线、广袤乡村、跨河桥梁及电力网络等复杂地…

前后端交互接口(三)

前后端交互接口&#xff08;三&#xff09; 前言 前两集我们先做了前后端交互接口的约定以及浅浅的阅读了一些proto代码。那么这一集我们就来看看一些重要的proto代码&#xff0c;之后把protobuffer给引入我们的项目当中&#xff01; gateway.proto 我们来看一眼我们的网关…

机器学习—sigmoid的替代品

Z状结肠激活函数&#xff0c;在隐藏层中&#xff0c;在输出层&#xff0c;因为用逻辑回归建立神经网络&#xff0c;创造了大量的逻辑回归单元&#xff0c;但是如果你使用其他激活函数&#xff0c;神经网络可以变得更加强大。 以需求预测为例&#xff0c;给定价格&#xff0c;航…

数据分析-44-时间序列预测之深度学习方法TCN

文章目录 1 TCN简介1.1 网络示意图1.2 TCN优点2 模拟应用2.1 模拟数据2.2 预处理创建滞后特征2.3 划分训练集和测试集2.4 创建TCN模型2.5 模型训练2.6 模型预测3 自定义my_TCN模型3.1 my_TCN()函数3.2 训练模型3.3 模型预测3.4 改进4 参考附录1 TCN简介 时间卷积网络(TCN)是…

2024最新AI绘画系统软件(Midjourney)+GPT4文档分析总结,多模态识图理解,AI文生图/图生图/混图生图(图像混合)

一、前言 人工智能的快速发展已成为全球关注的焦点&#xff0c;其应用领域广泛&#xff0c;涵盖绘图、语言处理、视频编辑等。前沿技术不仅推动科技创新&#xff0c;还在艺术创作、内容生产和商业实践等方面展示出巨大潜力。例如&#xff0c;AI语言模型显著提升了内容自动生成、…

input file检验成功之后才可以点击

input file检验成功之后才可以点击 需求 在上传发票前需要先填写发票号&#xff0c;然后点击选择文件直接完成上传功能 实现思路 在没有输入发票号之前&#xff0c;file按钮不可用不能点击&#xff0c;输入之后&#xff0c;按钮可用&#xff0c;点击之后选择文件&#xff…

每日OJ题_牛客_AB31活动安排_区间贪心_C++_Java

目录 牛客_AB31活动安排_区间贪心 题目解析 C代码 Java代码 牛客_AB31活动安排_区间贪心 活动安排_牛客题霸_牛客网 描述&#xff1a; 给定n个活动&#xff0c;每个活动安排的时间为[ai,bi)。求最多可以选择多少个活动&#xff0c;满足选择的活动时间两两之间没有重合。 …

购物车-多元素组合动画css

学习 渡一课程 多元素组合动画 练习。 在我们开发购物车功能时&#xff0c;经常会有点击添加按钮&#xff0c;就会有一个小圆点掉进购物车的动画&#xff0c;如下图所示&#xff0c;今天我们通过css来实现。 首先实现多元素组合动画 直接上代码&#xff0c;可以复制到本地使用…

深度学习:bert模型

multi-headed机制 1、通过不同的head得到多个特征表达&#xff0c;一般8个head 2、将所有特征拼接在一起 3、降维&#xff0c;将Z0~Z7连接一个FC全连接实现降维 多层堆叠 位置编码 如何实现位置编码&#xff1f; &#xff08;1&#xff09;为每个时间步添加一个0-1范围内的数…