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.xdnf.cn/news/3010.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

微信小程序开发,诗词鉴赏app

文章目录 1. 项目功能思维导图2. 项目涉及到的技术点3. 开发环境4. 项目运行效果5. 部分功能实现6. 关于本人其它项目的介绍 1. 项目功能思维导图 2. 项目涉及到的技术点 使用MySQL数据库实现数据存储使用setInterval实现启动页3s倒计时使用storage实现数据持久化存储&#xf…

什么是阿里云上的主机安全服务?

在数字化时代&#xff0c;数据安全和网络安全成为了企业最关心的问题之一。随着越来越多的企业将业务迁移至云端&#xff0c;如何确保云环境的安全性&#xff0c;成为了企业必须面对的重要挑战。阿里云安全中心&#xff08;SAS&#xff09;作为一款全面的云安全解决方案&#x…

在K8s平台部署个人博客

在K8s平台部署个人博客 实验步骤查看wordpress前端的service配置word press 实验步骤 kubectl create secret generic mysql-pass --from-literalpasswordYOUR_PASSWORD把mysql.tar.gz和wordpress.tar.gz上传到K8s工作节点&#xff0c;手动解压即可&#xff1a; 通过网盘分享的…

【原创】java+ssm+mysql收纳培训网系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…

Java | Leetcode Java题解之第523题连续的子数组和

题目&#xff1a; 题解&#xff1a; class Solution {public boolean checkSubarraySum(int[] nums, int k) {int m nums.length;if (m < 2) {return false;}Map<Integer, Integer> map new HashMap<Integer, Integer>();map.put(0, -1);int remainder 0;fo…

【时间之外】IT人求职和创业应知【27】

目录 新闻一物理智能公司完成4亿美元融资 新闻二A股IPO和再融资受理、审核回暖 新闻三AI流量变现财富峰会举办 认知和思考决定了你的赚钱能力。以下是今天可能引起你思考的热点新闻&#xff1a; 今日关键字&#xff1a;没吃过猪肉&#xff0c;还没见过猪跑吗&#xff1f; 新…

【前端开发入门】JavaScript快速入门--函数技巧

目录 引言一、函数基本注意事项1. 函数定义2. 默认参数3. 函数返回值及闭包3.1 举个函数返回值的简单例子3.2 当我需要利用函数内部变量做一些运算时&#xff0c;就需要使用js的闭包 二、函数注释1. 单行注释2. 多行注释3. 进阶玩法 三、总结 引言 本系列教程旨在帮助一些零基础…

权威认证!蓝卓获评IDC数字工厂领导者

日前&#xff0c;全球领先的IT市场研究和咨询公司IDC公布了《IDC MarketScape: 中国数字工厂整体解决方案厂商评估&#xff0c;2024》。其中&#xff0c;蓝卓成功入选IDC中国数字工厂整体解决方案厂商&#xff0c;位列领导者象限。 数字工厂整体解决方案领导者 《IDC MarketSc…

$tab的所有用法以及vue关闭页面的方法汇总

1、最简单粗暴的就是直接window.close(); 2.可以设置一个窗口的显示隐藏变量&#xff0c;比如点击新增按钮时&#xff0c;新增页面窗口就进行显示&#xff0c;点击关闭就把这个值置为flase 在最外层绑定open 初始值设为false 点击新增和修改按钮时&#xff0c;把状态置为true即…

全同态加密基于多项式环计算的图解

全同态加密方案提供了一种惊人的能力 —— 能够在不知道数据具体内容的情况下对数据进行计算。这使得你可以在保持潜在敏感源数据私密的同时&#xff0c;得出问题的答案。 这篇文章的整体结构包括多项式环相关的数学介绍&#xff0c;基于多项式环的加密和解密是如何工作的&…

10天进阶webpack---(2)webpack模块兼容性处理

回顾CMJ和ESM的区别 CMJ的本质可以使用一个函数概括 // require函数的伪代码 function require(path){if(该模块有缓存吗){return 缓存结果;}function _run(exports, require, module, __filename, __dirname){// 模块代码会放到这里}var module {exports: {}}_run.call(mod…

【STM32】NVIC / EXTI / AFIO 介绍

文章目录 中断系统NVIC简介NVIC基本结构NVIC优先级分组EXTI外部中断EXIT基本结构AFIO复用IO口EXTI内部框图 AFIO / EXTI / NVIC 相关函数AFIO相关函数EXTI相关函数NVIC相关函数 旋转编码器简介对射式红外传感器计次接线图CountSensor&#xff08;传感器&#xff09;驱动程序封装…

【Linux内核大揭秘】程序地址空间

文章目录 什么是程序地址空间地址空间的组成虚拟内存技术 如何理解程序地址空间页表页表的细节关于堆区 在Linux中如何查看各个分段的信息总结 什么是程序地址空间 程序地址空间是一个程序在执行期间可以访问的内存范围。它由操作系统为每个进程分配&#xff0c;以确保进程之间…

nginx代理出现的请求头中获取不到acc_token问题

1.问题 程序开发完成之后&#xff0c;发现页面登录之后&#xff0c;获取不到用户信息。发现时没有获取到token信息。本地程序开发完成&#xff0c;后端服务成功署到服务器。通过云服务器开放对应的端口&#xff0c;使用本地的前端服务&#xff0c;直接连接服务器后端服务&…

WordPress之generatepress主题安装

1.打开主题列表 2.如果没有自己需要主题点击安装新主题 点击安装并启用 3.不喜欢的 主题可以点击主题进去删除 4.主题自定义编辑 打开自定义&#xff0c;可以修改布局&#xff0c;颜色&#xff0c;排版等等

MySQL之JDBC入门详解

01-JDBC入门 一、JDBC概念 jdbc : java database connection , java数据库连接 jdbc是sun公司定义的java程序访问数据库的规范。 二、JDBC操作需要6步 三、入门程序 1、使用eclipse打开一个新的工作空间 2、切换到java视图界面 3、创建java工程&#xff1a;01-jdbc-helloworl…

BackTrader-Commission 06

Backtrader 策略实例&#xff0c;该部分内容通过使用backtrader对常用的策略实例的编写&#xff0c;提高和熟悉backtrader的实际场景的使用。 [Backtrader]实例:均线策略 [Backtrader] 实例:MACD策略 [Backtrader] 实例:KDJ 策略 [Backtrader] 实例:RSI 与 EMA 结合 [Backtrade…

WordPress伪静态设置

为什么要设置WordPress伪静态&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;中&#xff0c;静态URL通常被认为更易于搜索引擎爬虫抓取和索引&#xff0c;有助于提高网站的搜索引擎排名。 WordPress伪静态设置方法主要依赖于服务器环境&#xff0c;以下是针对不同服务器…

sublime python出现中文乱码怎么办

一、乱码现象 利用sublime自带编译快捷方式ctrlB会出现中文乱码的情况。 print("没有循环数据!") print("完成循环!") 二、寻找原因 1、由于之前我已经安装了插件ConvertToUTF8&#xff0c;排除文本编码错误问题。 2、相同的代码在插件sublimerepl搭建的…

【ARM Linux 系统稳定性分析入门及渐进 1.2 -- Crash 工具依赖内容】

请阅读:【Linux 维测及Crash使用专栏】 文章目录 Prerequisites1. 内核对象文件2. 内存镜像3. 平台处理器类型4. Linux 内核版本 Prerequisites crash 工具需要依赖下面的内容&#xff1a; 1. 内核对象文件 vmlinux 文件&#xff1a;需要一个 vmlinux 内核对象文件&#xff…