1.什么是布隆过滤器
巴顿.布隆于一九七零年提出的,其主旨是采用一个很长的二进制数组,通过一系列的Hash函数来确定该数据是否存在。
本质就是一串二进制数组
2.举一个栗子解释布隆过滤器
以京东举例,京东的每一个商品都有一个唯一的SDK编号。
当用户请求该商品的流程是
系统使用redis缓存服务器提高性能,商品的数据会加载到缓存服务器中,用户访问商品,如果缓存里面存在就会直接返回给用户,不会走数据库。
但是当有人使用爬虫恶意请求缓存中不存在的数据(缓存穿透攻击),少量的缓存穿透是没有影响的。
缓存穿透攻击是指恶意用户在短时内大量查询不存在的数据,导致大量请求被送达数据库进行查询,当请求数量超过数据库负载上限时,使系统响应出现高延迟甚至瘫痪的攻击行为。
布隆过滤器就是预防缓存穿透攻击的方法之一
3.布隆过滤器的原理
3.1 初始化一个n位的二进制数组
3.2 使用若干个hash函数对物品编码取模
比如1号商品使用三个hash函数取模后得到的结果为1,5,99那就分别在这个二进制数组相应的位置将0变为1
2号商品同理,将二进制数组的1,3,98位由0变为1,如果是1就不动作。
直到将缓存中所有的商品都进行操作
3.3 后续判断过程
当有商品查询到来,如果缓存中有直接返回。
如果缓存中没有,使用布隆过滤器查询,查询不到进行拦截
注意布隆过滤器存在误判的情况
4 减少误判的措施
增加二进制数组的位数
增加hash次数