从bitmap到布隆过滤器,再到高并发缓存设计策略
wptr33 2024-12-29 06:24 25 浏览
bitmap和布隆过滤器
海量整数中是否存在某个值--bitmap
在一个程序中,经常有让我们判断一个集合中是否存在某个数的case;大多数情况下,只需要用map或是list这样简单的数据结构,如果使用的是高级语言,还能乘上快车调用几个封装好的api,加几个if else,两三行代码就可以在控制台看自己“完美”而又“健壮”的代码跑起来了。
但是,事无完美,在高并发环境下,所有的case都会极端化,如果这是一个十分庞大的集合(给这个庞大一个具体的值吧,一个亿),简单的一个hash map,不考虑链表所需的指针内存空间,一亿个int类型的整数,就需要380多M(4byte × 10 ^8),十亿的话就是4个G,不考虑性能,光算算这内存开销,即使现在满地都是128G的服务器,也不好吃下这一壶。
bitmap则使用位数代表数的大小,bit中存储的0或者1来标识该整数是否存在,具体模型如下:
这是一个能标识0-9的“bitmap”,其中4321这四个数存在
计算一下bitmap的内存开销,如果是1亿以内的数据查找,我们只需要1亿个bit = 12MB左右的内存空间,就可以完成海量数据查找了,是不是极其诱人的一个内存缩减,以下为Java实现的bitmap代码:
public class MyBitMap {
private byte[] bytes;
private int initSize;
public MyBitMap(int size) {
if (size <= 0) {
return;
}
initSize = size / (8) + 1;
bytes = new byte[initSize];
}
public void set(int number) {
//相当于对一个数字进行右移动3位,相当于除以8
int index = number >> 3;
//相当于 number % 8 获取到byte[index]的位置
int position = number & 0x07;
//进行|或运算 参加运算的两个对象只要有一个为1,其值为1。
bytes[index] |= 1 << position;
}
public boolean contain(int number) {
int index = number >> 3;
int position = number & 0x07;
return (bytes[index] & (1 << position)) != 0;
}
public static void main(String[] args) {
MyBitMap myBitMap = new MyBitMap(32);
myBitMap.set(30);
myBitMap.set(13);
myBitMap.set(24);
System.out.println(myBitMap.contain(2));
}
}
使用简单的byte数组和位运算,就能做到时间与空间的完美均衡,是不是美美哒,wrong!试想一下,如果我们明确这是一个一亿以内,但是数量级只有10的集合,我们使用bitmap,同样需要开销12M的数据,如果是10亿以内的数据,开销就会涨到120M,bitmap的空间开销永远是和他的数据取值范围挂钩的,只有在海量数据下,他才能够大显身手。
再说说刚刚提到的那个极端case,假设这个数据量在一千万,但是取值范围好死不死就在十个亿以内,那我们不可避免还是要面对120M的开销,有方法应对么?
布隆过滤器
如果面对笔者说的以上问题,我们结合一下常规的解决方案,譬如说hash一下,我将十亿以内的某个数据,hash成一亿内的某个值,再去bitmap中查怎么样,如下图,布隆过滤器就是这么干的:
利用多个hash算法得到的值,减小hash碰撞的概率
像上面的图注所说,我们可以利用多个hash算法减小碰撞概率,但只要存在碰撞,就一定会有错误判断,我们无法百分百确定一个值是否真的存在,但是hash算法的魅力在于,我不能确定你是否存在,但是我可以确定你是否真的不存在,这也就是以上的实现为什么称之“过滤器”的原因了。
高并发缓存设计策略
why cache??
如果读者是一个计算机专业的同学,cache这个词应该是能达到让耳朵起茧的出现频次。在计算机体系中,cache是介于cpu以及内存之间,用来缓和cpu和内存处理速度差距的那么一个和事佬;在OS中,page cache又是内存和IO之间的和事佬。(搜索公众号Java知音,回复“2021”,送你一份Java面试题宝典)
cache是个和事老??听着似乎怪怪的,但是也蛮形象的啦。
前面讲了大半截的算法理论,为了防止读者犯困,直接进入下半部分主题,高并发缓存设计。
即使是在软件层,我们同样需要这么一个和事老,从最简单的服务架构开始,通常我们在服务端发起请求,然后CURD某个关系型数据库例如Mysql。但是,类似这样的架构都需要有一个磁盘作为终端持久化,即使增加索引,使用B+树的这种数据结构进行优化查询,效率还是会卡在需要频繁寻道的IO上。这个时候,一个和事老的作用就十分明显了,我们会添加一些内存操作,来缓和IO处理速度慢带来的压力。cache is not a problem,how to use it is actually a problem。
缓存一致性问题
缓存处理的机制有以下几种:
- cache aside;
- read through;
- write through;
- write behind caching;
缓存穿透问题
所谓的缓存击穿,就是当请求发出,而无法在缓存中读到数据时,请求还是会作用到database,这样的话,缓存减压的效果就不复存在了。
设想这么一个场景,如果一个用户,使用大流量恶意频繁地去查询一条数据库中没有的记录,一直击穿缓存,势必会把database打死,如何避免缓存击穿,这就是一个问题了。
有两种方案,第一种,在缓存中添加空值,如果在database中查询无果,我们大可以把值设置为null,防止下次再次访问数据库,这样做简单便捷,但是多少有些浪费空间。
第二种方案,就是使用布隆过滤器(点题),在cache与web服务器中间加一层布隆过滤器,对访问的key做记录,如此以来,同样可以解决缓存击穿的问题。
缓存雪崩问题
缓存雪崩发生于在某个时间点,缓存同时失效,例如缓存设置了失效时间,这会联动的导致大量缓存击穿问题。
加分布式锁是一种解决方案,只有拿到锁的请求才能访问database。但是这样治标不治本,当请求量过多时,大量的线程阻塞,也会把内存撑坏的。
预热数据,分散地设置失效时间,这样可以减少缓存雪崩发生的概率。
提高缓存可用性,cache的单点一样是会是缓存雪崩的隐患,大部分缓存中间件都提供高可用架构,如redis的主从+哨兵架构。
相关推荐
- redis的八种使用场景
-
前言:redis是我们工作开发中,经常要打交道的,下面对redis的使用场景做总结介绍也是对redis举报的功能做梳理。缓存Redis最常见的用途是作为缓存,用于加速应用程序的响应速度。...
- 基于Redis的3种分布式ID生成策略
-
在分布式系统设计中,全局唯一ID是一个基础而关键的组件。随着业务规模扩大和系统架构向微服务演进,传统的单机自增ID已无法满足需求。高并发、高可用的分布式ID生成方案成为构建可靠分布式系统的必要条件。R...
- 基于OpenWrt系统路由器的模式切换与网页设计
-
摘要:目前商用WiFi路由器已应用到多个领域,商家通过给用户提供一个稳定免费WiFi热点达到吸引客户、提升服务的目标。传统路由器自带的Luci界面提供了工厂模式的Web界面,用户可通过该界面配置路...
- 这篇文章教你看明白 nginx-ingress 控制器
-
主机nginx一般nginx做主机反向代理(网关)有以下配置...
- 如何用redis实现注册中心
-
一句话总结使用Redis实现注册中心:服务注册...
- 爱可可老师24小时热门分享(2020.5.10)
-
No1.看自己以前写的代码是种什么体验?No2.DooM-chip!国外网友SylvainLefebvre自制的无CPU、无操作码、无指令计数器...No3.我认为CS学位可以更好,如...
- Apportable:拯救程序员,IOS一秒变安卓
-
摘要:还在为了跨平台使用cocos2d-x吗,拯救objc程序员的奇葩来了,ApportableSDK:FreeAndroidsupportforcocos2d-iPhone。App...
- JAVA实现超买超卖方案汇总,那个最适合你,一篇文章彻底讲透
-
以下是几种Java实现超买超卖问题的核心解决方案及代码示例,针对高并发场景下的库存扣减问题:方案一:Redis原子操作+Lua脚本(推荐)//使用Redis+Lua保证原子性publicbo...
- 3月26日更新 快速施法自动施法可独立设置
-
2016年3月26日DOTA2有一个79.6MB的更新主要是针对自动施法和快速施法的调整本来内容不多不少朋友都有自动施法和快速施法的困扰英文更新日志一些视觉BUG修复就不翻译了主要翻译自动施...
- Redis 是如何提供服务的
-
在刚刚接触Redis的时候,最想要知道的是一个’setnameJhon’命令到达Redis服务器的时候,它是如何返回’OK’的?里面命令处理的流程如何,具体细节怎么样?你一定有问过自己...
- lua _G、_VERSION使用
-
到这里我们已经把lua基础库中的函数介绍完了,除了函数外基础库中还有两个常量,一个是_G,另一个是_VERSION。_G是基础库本身,指向自己,这个变量很有意思,可以无限引用自己,最后得到的还是自己,...
- China's top diplomat to chair third China-Pacific Island countries foreign ministers' meeting
-
BEIJING,May21(Xinhua)--ChineseForeignMinisterWangYi,alsoamemberofthePoliticalBureau...
- 移动工作交流工具Lua推出Insights数据分析产品
-
Lua是一个适用于各种职业人士的移动交流平台,它在今天推出了一项叫做Insights的全新功能。Insights是一个数据平台,客户可以在上面实时看到员工之间的交流情况,并分析这些情况对公司发展的影响...
- Redis 7新武器:用Redis Stack实现向量搜索的极限压测
-
当传统关系型数据库还在为向量相似度搜索的性能挣扎时,Redis7的RedisStack...
- Nginx/OpenResty详解,Nginx Lua编程,重定向与内部子请求
-
重定向与内部子请求Nginx的rewrite指令不仅可以在Nginx内部的server、location之间进行跳转,还可以进行外部链接的重定向。通过ngx_lua模块的Lua函数除了能实现Nginx...
- 一周热门
-
-
C# 13 和 .NET 9 全知道 :13 使用 ASP.NET Core 构建网站 (1)
-
因果推断Matching方式实现代码 因果推断模型
-
git pull命令使用实例 git pull--rebase
-
git pull 和git fetch 命令分别有什么作用?二者有什么区别?
-
面试官:git pull是哪两个指令的组合?
-
git 执行pull错误如何撤销 git pull fail
-
git fetch 和git pull 的异同 git中fetch和pull的区别
-
git pull 之后本地代码被覆盖 解决方案
-
还可以这样玩?Git基本原理及各种骚操作,涨知识了
-
git命令之pull git.pull
-
- 最近发表
- 标签列表
-
- git pull (33)
- git fetch (35)
- mysql insert (35)
- mysql distinct (37)
- concat_ws (36)
- java continue (36)
- jenkins官网 (37)
- mysql 子查询 (37)
- python元组 (33)
- mybatis 分页 (35)
- vba split (37)
- redis watch (34)
- python list sort (37)
- nvarchar2 (34)
- mysql not null (36)
- hmset (35)
- python telnet (35)
- python readlines() 方法 (36)
- munmap (35)
- docker network create (35)
- redis 集合 (37)
- python sftp (37)
- setpriority (34)
- c语言 switch (34)
- git commit (34)