文档章节

布隆过滤器redis缓存

须臾之余
 须臾之余
发布于 08/27 00:00
字数 1319
阅读 15
收藏 0

Bloom Filter布隆过滤器
算法背景
如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希
表,Hash table)等等数据结构都是这种思路,存储位置要么是磁盘,要么是内存。很多时候要么是以时间换空间,要么是以空间换时
间。
在响应时间要求比较严格的情况下,如果我们存在内里,那么随着集合中元素的增加,我们需要的存储空间越来越大,以及检索的时间越
来越长,导致内存开销太大、时间效率变低。
此时需要考虑解决的问题就是,在数据量比较大的情况下,既满足时间要求,又满足空间的要求。即我们需要一个时间和空间消耗都比较
小的数据结构和算法。Bloom Filter就是一种解决方案。
Bloom Filter 概念
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以
用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。
它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断,但不会漏掉判断。也就是Bloom Filter判断元
素不再集合,那肯定不在。如果判断元素存在集合中,有一定的概率判断错误。因此,Bloom Filter”不适合那些“零错误的应用场合。
而在能容忍低错误率的应用场合下,Bloom Filter比其他常见的算法(如hash,折半查找)极大节省了空间。
Bloom Filter 原理
布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我
们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检
元素很可能在。这就是布隆过滤器的基本思想。
Bloom Filter跟单哈希函数Bit-Map不同之处在于:Bloom Filter使用了k个哈希函数,每个字符串跟k个bit对应。从而降低了冲突的概
率。


Bloom Filter的缺点
bloom filter之所以能做到在时间和空间上的效率比较高,是因为牺牲了判断的准确率、删除的便利性
存在误判,可能要查到的元素并没有在容器中,但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单,
那么可以通过建立一个白名单来存储可能会误判的元素。
删除困难。一个放入容器的元素映射到bit数组的k个位置上是1,删除的时候不能简单的直接置为0,可能会影响其他元素的判
断。可以采用Counting Bloom Filter
Bloom Filter 实现
布隆过滤器有许多实现与优化,Guava中就提供了一种Bloom Filter的实现。
在使用bloom filter时,绕不过的两点是预估数据量n以及期望的误判率fpp,
在实现bloom filter时,绕不过的两点就是hash函数的选取以及bit数组的大小。
对于一个确定的场景,我们预估要存的数据量为n,期望的误判率为fpp,然后需要计算我们需要的Bit数组的大小m,以及hash函数的个
数k,并选择hash函数  
(1)Bit数组大小选择
  根据预估数据量n以及误判率fpp,bit数组大小的m的计算方式:
(2)哈希函数选择
由预估数据量n以及bit数组长度m,可以得到一个hash函数的个数k:
哈希函数的选择对性能的影响应该是很大的,一个好的哈希函数要能近似等概率的将字符串映射到各个Bit。选择k个不同的哈希函数比较
麻烦,一种简单的方法是选择一个哈希函数,然后送入k个不同的参数

原文:https://www.cnblogs.com/zhanggguoqi/p/10571225.html

本文转载自:https://www.cnblogs.com/zhanggguoqi/p/10571225.html

须臾之余
粉丝 125
博文 68
码字总数 178724
作品 0
吉安
程序员
私信 提问
Redis缓存使用-穿透、雪崩、热点key问题

一、缓存穿透 redis缓存穿透:查询一个数据库中不存在的数据,比如商品详情,查询一个不存在的ID,每次都会访问DB,如果有人恶意破坏,很可能直接对DB造成过大地压力。 解决方案: 1、缓存空...

淡淡的倔强
02/25
0
0
分布式系列之缓存设计中常见的问题

缓存这个东西相信大家工作中都接触得比较多,相应的在不同场景下也会遇到各种各样的问题。下面我列举几种可能会遇到的问题并提供一些解决建议。 1、如何把海量数据存放在缓存中并提供快速查询...

浮云骑士LIN
2018/07/24
0
0
redis redis击穿、雪崩的预防解决方案

redis的缓存击穿? 缓存穿透是指查询一个根本不存在的数据,缓存层和存储层都不会命中,但是出于容错的考虑,如果从存储层查不到数据则不写入缓存层,如图 11-3 所示整个过程分为如下 3 步:...

edison_kwok
05/02
55
0
LevelDB 入门 —— 全面了解 LevelDB 的功能特性

本节我们将全面了解一下 LevelDB 的各种特性。LevelDB 的开发语言是 C++,考虑到会使用 C++ 语言的同学不是很多,在本节我们将使用 Java 语言来描述 LevelDB 的特性。其它语言栈的同学也不必...

技术小能手
01/11
0
0
Redis架构之防雪崩设计:网站不宕机背后的兵法

导读:互联网系统中不可避免要大量用到缓存,在缓存的使用过程中,架构师需要注意哪些问题?本文以 Redis 为例,详细探讨了最关键的 3 个问题。 一、缓存穿透预防及优化 缓存穿透是指查询一个...

HOT_POT
2018/08/08
92
0

没有更多内容

加载失败,请刷新页面

加载更多

好程序员大数据教程分享Scala系列之模式匹配和样例类

好程序员大数据教程分享Scala系列之模式匹配和样例类 1.样例类 在Scala中样例类是一中特殊的类,样例类是不可变的, 可以通过值进行比较,可用于模式匹配。 定义一个样例类: 构造器中每一个...

好程序员官网
10分钟前
3
0
让nginx上的静态网页在访问的时候没有html后缀

需求背景: 公司产品小姐姐觉得这个访问带html后缀不专业,要求访问不带html后缀 nginx 配置 #原配置 location / { index index.html index.htm index.php; try_files $...

Linux_Anna
11分钟前
2
0
beetl的内置函数

函数调用Beetl内置函数请参考附录,以下列出了常用的函数date 返回一个java.util.Date类型的变量,如 date() 返回一个当前时间(对应java的java.util.Date); ${date( "2011-1-1" , "yy...

gantaos
11分钟前
3
0
spring cloud 2.x版本 Gateway自定义过滤器教程

前言 本文采用Spring cloud本文为2.1.8RELEASE,version=Greenwich.SR3 [toc] 本文基于前两篇文章eureka-server、eureka-client、eureka-ribbon、eureka-feign和spring-gataway的实现。 参考......

毛毛向前冲V5
15分钟前
3
0
VPGAME 的 Kubernetes 迁移实践

作者 | 伍冲斌 VPGAME 运维开发工程师 导读:VPGAME 是集赛事运营、媒体资讯、大数据分析、玩家社群、游戏周边等为一体的综合电竞服务平台。总部位于中国杭州,在上海和美国西雅图分别设立了...

阿里巴巴云原生
20分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部