一、布隆过滤器是什么，一定要用吗?

二、布隆过滤器使用场景

 三、通过google布隆过滤器存储数据

四、google布隆过滤器的缺点分析

五、Redis布隆过滤器安装

六、 Redis布隆过滤器与springboot的整合 (集合lua脚本)

导读：本博文介绍了布隆过滤器的使用场景，以及google布隆过滤器和redis布隆过滤器分别的使用方法。当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在 

一、布隆过滤器是什么，一定要用吗?

布隆过滤器是什么：

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

优点:

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势

缺点：

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣

流量攻击：故意访问不存在的数据，导致程序不断访问DB数据库的数据(缓存穿透-解决方式将空值加到缓存中，防止大量攻击到db)

安全阻截：当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉(提前做ID数据判断是否是合格的)

思考：key：10000 10001 10002 10003 千万大集合，查找key是否在集合里面 

java常用数据结构，判断key是否在集合中:
set map key,value list 有序get[0]、get[1]；
list.contain (key)遍历数据，进行equals()比较，性能低 
set.contain(key) hashcode比较，性能较高，64位大概会占用1G
map.get(key) hashcode比较，性能还行，会出现hashcode冲突问题

上述常用做法，用小数据量还可以，大数据量不是占用内存过高，就是性能很低

二、布隆过滤器使用场景

使用场景：

网页爬虫对URL的去重，避免爬取相同的URL地址；

反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；

缓存穿透，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

 三、通过google布隆过滤器存储数据

通过google布隆过滤器存储会员数据:

1、程序启动时将数据放入内存中
2、google自动创建布隆过滤器
3、用户ID进来之后判断是否是会员

pom.xml

com.google.guavaguava21.0

 构建底库:

 private BloomFilter bf;    /***     * PostConstruct 程序启动时候加载此方法     */    @PostConstruct    public void initBloomFilter() { SysUserExample sysUserExample = new SysUserExample(); List sysUserList = sysUserMapper.selectByExample(sysUserExample); if(CollectionUtils.isEmpty(sysUserList)){     return; } //创建布隆过滤器(默认3%误差) bf = BloomFilter.create(Funnels.integerFunnel(),sysUserList.size()); for (SysUser sysUser:sysUserList) {     bf.put(sysUser.getId()); }    }

查询是否存在:

    /***     * 判断id可能存在于布隆过滤器里面     * @param id     * @return     */    public boolean userIdExists(int id){ return bf.mightContain(id);    }

四、google布隆过滤器的缺点分析

google缺点：

内存级别产物
重启即失效
本地内存无法用在分布式场景
不支持大数据量存储

这里引入redis的布隆过滤器

可扩展性Bloom过滤器,一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器
不存在重启即失效或者定时任务维护的成本

基于goole实现的布隆过滤器需要启动之后初始化布隆过滤器缺点：需要网络IO,性能比基于内存的过滤器低

当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存在 

五、Redis布隆过滤器安装

Redis布隆过滤器安装过程 自己构建一个bitMap
git在centos7下面的安装：    

1、安装git，直接使用yum安装即可：yum -y install git2、创建git用户，git用户可以正常通过ssh使用git，但无法登录shell，因为我们为git用户指定的git-shell每次一登录就自动退出。useradd -m -d /home/git -s /usr/bin/git-shell git3、初始化git仓库mkdir -p /data/gitcd /data/gitgit init --bare project1.gitchown git.git project1.git -R4、创建免密钥cd /home/gitmkdir .sshchmod 700 .sshtouch .ssh/authorized_keyschmod 600 .ssh/authorized_keyschown git.git .ssh -R

下载并编译模块：

 $ git clone git：//github.com/RedisLabsModules/rebloom $ cd rebloom $ make    # 当前路径会生成一个rebloom.so文件

 将Rebloom加载到Redis中，在redis.conf里面添加

loadmodule /usr/local/rebloom/rebloom.so

 # 更改配置后重启Redis即可
上述的安装提到需要重启Redis，但是生产环境的Redis可不是你想重启就重启的。使用MODULE LOAD 不重启redis加载rebloom插件
MODULE LOAD /"rebloom.so的绝对路径"/redisbloom.so

命令:

添加元素：BF.ADD(添加单个)、BF.MADD(添加多个)、BF.INSERT(添加多个)

检查元素是否存在：BF.EXISTS(查询单个元素)、BF.MEXISTS(查询多个元素)
BF.ADD bloom redis         
BF.EXISTS bloom redis#判断是否存在
BF.EXISTS bloom nonxist 

六、 Redis布隆过滤器与springboot的整合 (集合lua脚本)

bloomFilterAdd.lua

local bloomName = KEYS[1]local value = KEYS[2]-- bloomFilterlocal result_1 = redis.call('BF.ADD', bloomName, value)return result_1

bloomFilterExist.lua

local bloomName = KEYS[1]local value = KEYS[2]-- bloomFilterlocal result_1 = redis.call('BF.EXISTS', bloomName, value)return result_1

本博文因需通过浏览器验证添加效果，所以将新增通过id增加的放到controller中，正式开发过程中可根据业务项目启动中查询数据加到redis中或者每天定时更新redis过滤器值。

新增：

   private static final String bloomFilterName = "isVipBloom";@Resource    private RedisService redisService;    @RequestMapping("/bloom/redisIdAdd")    public boolean redisidAdd(int id){ return redisService.bloomFilterAdd(bloomFilterName,id);    }    @Autowired    private RedisTemplate redisTemplate;    public Boolean bloomFilterAdd(String filterName,int value){ DefaultRedisScript bloomAdd = new DefaultRedisScript(); bloomAdd.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterAdd.lua"))); bloomAdd.setResultType(Boolean.class); List keyList= new ArrayList(); keyList.add(filterName); keyList.add(value+""); Boolean result = (Boolean) redisTemplate.execute(bloomAdd,keyList); return result;    }

查询是否存在:

    @Resource    private RedisService redisService;      @RequestMapping("/bloom/redisIdExists")    public boolean redisidExists(int id){ return redisService.bloomFilterExists(bloomFilterName,id);    }    @Autowired    private RedisTemplate redisTemplate;   public Boolean bloomFilterExists(String filterName,int value){ DefaultRedisScript bloomExists= new DefaultRedisScript(); bloomExists.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterExist.lua"))); bloomExists.setResultType(Boolean.class); List keyList= new ArrayList(); keyList.add(filterName); keyList.add(value+""); Boolean result = (Boolean) redisTemplate.execute(bloomExists,keyList); return result;    }

 效果验证:放入111 333 ，查询111存在  ，444不存在