Redis（五）--详解布隆过滤器和缓存穿透解决⽅案
⼀、使⽤场景
1.布隆过滤器的特性是：去重，多数去重场景都跟这个特性有关。⽐如爬⾍的时候去掉相同的URL，推送消息去掉相同的消息等。
2.解决缓存击穿的问题。
3.反垃圾邮件，从数⼗亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理，垃圾短信).
⼆、概念
其内部维护⼀个全为0的bit数组，需要说明的是，布隆过滤器有⼀个误判率的概念，误判率越低，则数组越长，所占空间越⼤。误判率越⾼则数组越⼩，所占的空间越⼩。
我们可以通过⼀个int型的整数的32⽐特位来存储32个10进制的数字，那么这样所带来的好处是内存占⽤少、效率很⾼（不需要⽐较和位移）⽐如我们要存储5(101)、3(11)四个数字，那么我们申请int型的内存空间，会有32个⽐特位。这四个数字的⼆进制分别对应从右往左开始数，⽐如第⼀个数字是5，对应的⼆进制数据是101, 那么从右往左数到第5位，把对应的⼆进制数据存储到32个⽐特位上。
第⼀个5就是 00000000000000000000000000101000
输⼊3时候    00000000000000000000000000001100
如何⽣成⼀个布隆过滤器？
原理如下假设集合⾥⾯有3个元素{x, y, z}，哈希函数的个数为3。⾸先将位数组进⾏初始化，将⾥⾯每个位都设置位0。对于集合⾥⾯的每⼀个元素，将元素依次通过3个哈希函数进⾏映射，每次映射都会产⽣⼀个哈希值，这个值对应位数组上⾯的⼀个点，然后将位数组对应的位置标记为1。接下来按照该⽅法处理所有的输⼊对象，每个对象都可能把bitMap中⼀些⽩位置涂⿊，也可能会遇到已经涂⿊的位置，遇到已经为⿊的让他继续为⿊即可。处理完所有的输⼊对象之后，在bitMap中可能已经有相当多的位置已经被涂⿊。⾄此，⼀个布隆过滤器⽣成完成，这个布隆过滤器代表之前所有输⼊对象组成的集合。(向布隆过滤器中添加 key 时，会使⽤多个 hash 函数对 key 进⾏ hash 算得⼀个整数索引值然后对位数组长度进⾏取模运算得到⼀个位置，每个 hash 函数都会算得⼀个不同的位置。再把位数组的这⼏个位置都置为 1 就完成了 add 操作。)
如何去判断⼀个元素是否存在bit array中呢？
原理是⼀样，根据k个哈希函数去得到的结果，如果所有的结果都是1，表⽰这个元素可能（假设某个元素通过映射对应下标为
4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1）存在。如果⼀旦发现其中⼀个⽐特位的元素是0，表⽰这个元素⼀定不存在⾄于k个哈希函数的取值为多少，能够最⼤化的降低错误率（因为哈希函数越多，映射冲突会越少），这个地⽅就会涉及到最优的哈希函数个数的⼀个算法逻辑。(向布隆过滤器询问key 是否存在时，跟 add ⼀样，也会把 hash 的⼏个位置都算出来，看看位数组中这⼏个位置是否都为 1，只要有⼀个位为 0，那么说明布隆过滤器中这个 key 不存在。如果都是 1，这并不能说明这个 key 就⼀定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组⽐较稀疏，判断正确的概率就会很⼤，如果这个位数组⽐较拥挤，判断正确的概率就会降低。)
它的优点是空间效率和查询时间都远远超过⼀般的算法，缺点是有⼀定的误识别率和删除困难。
三、项⽬实战
1.命令模式，Redis 官⽅提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后。
可以使⽤docker容器进⾏安装，docker容器安装可以参照之前的⽂章。
docker pull redislabs/rebloom
# 运⾏容器
docker run -p  6379:6379 redislabs/rebloom
# 连接容器中的 redis 服务
docker exec -it 1a7ca288bcbe redis-cli
命令：
bf.add boolean:aaron:test user1
bf.add boolean:aaron:test user2
bf.add boolean:aaron:test user3
#批量操作
bf.madd boolean:aaron:test user4 user5 user6
#redis 连接
pool = redis.ConnectionPool(host='192.168.XXX.XXX', port=6379)
r = redis.Redis(connection_pool=pool)
#布隆过滤器
def boolean_test():
r.delete("boolean:aaron:test")
#指定错误率
#正式操作的命令 add 和 exists
for i in range(10000):
ret = r.execute_command("bf.exists", "boolean:aaron:test", "user%d" % i)
if ret == 0:
print(i)
break
print(ret)
#主函数，执⾏⾏数filter过滤对象数组
if __name__ == '__main__':
boolean_test()
3.Java代码，以解决解决缓存击穿的问题为例。
4.3.1 阐述原因和解决思路
什么是缓存穿透？
正常情况下，我们去查询数据都是存在。那么请求去查询⼀条压根⼉数据库中根本就不存在的数据，也就是缓存和数据库都查询不到这条数据，但是请求每次都会打到数据库上⾯去。这种查询不存在数据的现象我们称为缓存穿透。
穿透带来的问题
试想⼀下，如果有⿊客会对你的系统进⾏攻击，拿⼀个不存在的id 去查询数据，会产⽣⼤量的请求到数据库去查询。可能会导致你的数据库由于压⼒过⼤⽽宕掉。(之前项⽬就是这样做的，没有考虑到)
4.3.2 解决思路：
缓存空值
之所以会发⽣穿透，就是因为缓存中没有存储这些空数据的key。从⽽导致每次查询都到数据库去了。那么我们就可以为这些key对应的值设置为null 丢到缓存⾥⾯去。后⾯再出现查询这个key 的请求的时候，直接返回null 。这样，就不⽤在到数据库中去⾛⼀圈了，但是别忘了设置过期时间。
BloomFilterBloomFilter
类似于⼀个hbase set ⽤来判断某个元素（key）是否存在于某个集合中。这种⽅式在⼤数据场景应⽤⽐较多，⽐如 Hbase 中使⽤它去判断数据是否在磁盘上。还有在爬⾍场景判断url 是否已经被爬取过。这种⽅案可以加在第⼀种⽅案中，在缓存之前在加⼀层BloomFilter ，在查询的时候先去 BloomFilter 去查询 key 是否存在，如果不存在就直接返回，存在再⾛查缓存 -> 查 DB。
4.3.3 代码
a.使⽤redisTemplate
通过查看⽹上资料和查看官⽹，还有直接导⼊源码并没有直接相关的API。有两种⽅式可以间接使⽤redisTemplate达到布隆过滤器。        第⼀种⽅式，集合Lua脚本。
dis.zfr.demoredis.mq;
import org.springframework.beans.factory.annotation.Autowired;
import org.RedisTemplate;
import org.script.DefaultRedisScript;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestMapping;
import java.util.Collections;
@Controller
public class RedisController {
@Autowired
private RedisTemplate<String, String> redisTemplate;
/**
* 布隆过滤器
* @param id
* @return
*/
@RequestMapping("/lua/{id}")
public String sendLua(@PathVariable String id) {
//添加key值
String script = "return redis.call('bf.add',KEYS[1],ARGV[1])";
DefaultRedisScript<Boolean> redisScript = new DefaultRedisScript<>(script, Boolean.class);
Boolean user4 = ute(redisScript, Collections.singletonList("boolean:aaron:test"), String.valueOf("user"+id));        System.out.println(user4);
//判断是否存在
String scriptEx = "return redis.call('bf.exists',KEYS[1],ARGV[1])";
DefaultRedisScript<Boolean> redisScript1 = new DefaultRedisScript<>(scriptEx, Boolean.class);
Boolean user6 = ute(redisScript1, Collections.singletonList("boolean:aaron:test"), String.valueOf("user"+id));        System.out.println(user6);
return "";
}
}
第⼀次打印结果是：true true 。
第⼆次打印结果是：false true 。因为user11已经存在了。
第⼆种⽅式，⽹上⼤部分实现⽅式，通过使⽤Google的布隆过滤器，然后结合redisTemplate。
Google布隆过滤器⼯具类：
1. pom坐标
<dependency>
<groupId&le.guava</groupId>
<artifactId>guava</artifactId>
<version>22.0</version>
</dependency>
2.代码

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。