缓存击穿之布隆过滤器bloom Filter实现方式

作者: baby_honour | 来源:发表于2018-11-22 10:40 被阅读290次

原文:https://blog.csdn.net/ocean_fan/article/details/78350431
一、什么是缓存击穿

查询一个在缓存内必然不存在的数据，导致每次请求都要去存储层去查询，这样缓存就失去了意义。如果在大流量下数据库可能挂掉。缓存击穿是黑客攻击系统的常用手段。

二、怎么解决缓存击穿问题？

采用布隆过滤器来实现。

什么是布隆过滤器？

它是一种空间效率极高的概率型算法和数据结构，用于判断一个元素是否在集合中(类似Hashset)。它的核心是一个很长的二进制向量和一系列的hash函数。

java中如何使用布隆过滤器？

使用谷歌的guava实现布隆过滤器。

bloom Filter布隆过滤器优劣势？

优势:
1)全量存储但不存储元素本身，在某些保密要求非常严格的场合有优势
2)空间效率高
3)插入/查询时间都是常数，远远超过一般算法

劣势:
1）存在误算率，随着存入的元素数量增加，误算率也随着增加
2)一般情况下不能从布隆过滤器删除元素
3)数组长度以及hash函数个数确定过程复杂

布隆过滤器的使用场景？
1)垃圾邮件地址过滤(地址数量很庞大)
2)爬虫URL地址去重

解决缓存击穿问题

4)浏览器安全浏览网址提醒
5)google 分布式数据库Bigtable以及Hbase使用布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数
6)文档存储检索系统也可以采用布隆过滤器来检测先前存储的数据

三、java中使用guava中的bloom Filter解决缓存击穿问题
工程目录结构图:

@PostConstruct和@PreDestroy

从Java EE 5规范开始，Servlet中增加了两个影响Servlet生命周期的注解（Annotion）；@PostConstruct和@PreDestroy。这两个注解被用来修饰一个非静态的void()方法。写法有如下两种方式：

@PostConstruct
Public void someMethod() {}
或者
public @PostConstruct void someMethod(){}

被@PostConstruct修饰的方法会在服务器加载Servle的时候运行，并且只会被服务器执行一次。PostConstruct在构造函数之后执行,init()方法之前执行。PreDestroy（）方法在destroy()方法执行执行之后执行

@PostConstruct和@PreDestroy

模拟100个线程同时查询缓存中必不存在的情况。

package com.ocean.cache;
 
import java.util.List;
import java.util.UUID;
import java.util.concurrent.CountDownLatch;
 
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
 
import org.junit.Test;
import org.junit.runner.RunWith;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.ValueOperations;
import org.springframework.test.context.ContextConfiguration;
import org.springframework.test.context.junit4.SpringJUnit4ClassRunner;
 
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import com.ocean.dao.UserDao;
import com.ocean.dto.UserDto;
 
/**
 * 缓存击穿
 * @author 
 *
 */
@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(locations = {"classpath:config/spring/spring-dao.xml",
        "classpath:config/spring/spring-bean.xml",
        "classpath:config/spring/spring-redis.xml"})
public class CacheBreakDownTest {
    private static final Logger logger = LoggerFactory.getLogger(CacheBreakDownTest.class);
    
    private static final int THREAD_NUM = 100;//线程数量
    
    @Resource
    private UserDao UserDao;
    
    @Resource
    private RedisTemplate redisTemplate;
    
    private int count = 0;
    
    //初始化一个计数器
    private CountDownLatch countDownLatch = new CountDownLatch(THREAD_NUM);
    
    private BloomFilter<String> bf;
    
    List<UserDto> allUsers;
    
    @PostConstruct
    public void init(){
        //将数据从数据库导入到本地
        allUsers = UserDao.getAllUser();
        if(allUsers == null || allUsers.size()==0){
            return;
        }
        //创建布隆过滤器(默认3%误差)
        bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), allUsers.size());
        //将数据存入布隆过滤器
        for(UserDto userDto : allUsers){
            bf.put(userDto.getUserName());
        }
    }
    
    @Test
    public void cacheBreakDownTest(){
        for(int i=0;i<THREAD_NUM;i++){
            new Thread(new MyThread()).start();
            //计数器减一
            countDownLatch.countDown();
        }
        try {
            Thread.currentThread().join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    class MyThread implements Runnable{
 
        @Override
        public void run() {
            try {
                //所有子线程等待，当子线程全部创建完成再一起并发执行后面的代码
                countDownLatch.await();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //随机产生一个字符串
            String randomUser = UUID.randomUUID().toString();
//          String randomUser = allUsers.get(new Random().nextInt(allUsers.size())).getUserName();
            String key = "Key:"+randomUser;
            
            //如果布隆过滤器中不存在这个用户直接返回，将流量挡掉
            if(!bf.mightContain(randomUser)){
                System.out.println("bloom filter don't has this user");
                return;
            }
            //查询缓存，如果缓存中存在直接返回缓存数据
            ValueOperations<String,String> operation = (ValueOperations<String, String>) redisTemplate.opsForValue();
            synchronized (countDownLatch) {
                Object cacheUser = operation.get(key);
                if(cacheUser!=null){
                    System.out.println("return user from redis");
                    return;
                }
                //如果缓存不存在查询数据库
                List<UserDto> user = UserDao.getUserByUserName(randomUser);
                if(user == null || user.size() == 0){
                    return;
                }
                //将mysql数据库查询到的数据写入到redis中
                System.out.println("write to redis");
                operation.set("Key:"+user.get(0).getUserName(), user.get(0).getUserName());
            }
        }
        
    }
}

maven配置文件pom.xml

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">  
     <modelVersion>4.0.0</modelVersion>
  <groupId>manager</groupId>
  <artifactId>manager</artifactId>
  <packaging>war</packaging>
  <version>0.0.1-SNAPSHOT</version>
  <name>manager Maven Webapp</name>
  <url>http://maven.apache.org</url>
  <properties>
        <guava.version>21.0</guava.version>
    </properties>
    <dependencies>  
        <dependency>  
            <groupId>junit</groupId>  
            <artifactId>junit</artifactId>  
            <version>4.9</version>  
        </dependency> 
        
        <dependency>
            <groupId>org.mockito</groupId>
            <artifactId>mockito-all</artifactId>
            <version>1.10.19</version>
            <scope>test</scope>
        </dependency> 
        <!-- spring-mvc包 -->  
        <dependency>  
            <groupId>org.springframework</groupId>  
            <artifactId>spring-webmvc</artifactId>  
            <version>4.2.0.RELEASE</version>  
        </dependency>  
        <!-- jsp显示数据需要的jar包 -->  
        <dependency>  
            <groupId>jstl</groupId>  
            <artifactId>jstl</artifactId>  
            <version>1.2</version>  
        </dependency>  
        <!--日志 -->  
        <dependency>  
            <groupId>log4j</groupId>  
            <artifactId>log4j</artifactId>  
            <version>1.2.17</version>  
        </dependency>  
        <dependency>  
            <groupId>org.apache.logging.log4j</groupId>  
            <artifactId>log4j-core</artifactId>  
            <version>2.0</version>  
        </dependency>  
        <dependency>  
            <groupId>org.apache.logging.log4j</groupId>  
            <artifactId>log4j-api</artifactId>  
            <version>2.0</version>  
        </dependency>  
        <!--spring4.0以上json和java对象的转换jackson包 spring4.0以上需要jackson2.6版本 -->  
        <dependency>  
            <groupId>com.fasterxml.jackson.core</groupId>  
            <artifactId>jackson-core</artifactId>  
            <version>2.6.1</version>  
        </dependency>  
        <dependency>  
            <groupId>com.fasterxml.jackson.core</groupId>  
            <artifactId>jackson-databind</artifactId>  
            <version>2.6.1</version>  
        </dependency>  
        <dependency>  
            <groupId>com.fasterxml.jackson.core</groupId>  
            <artifactId>jackson-annotations</artifactId>  
            <version>2.6.1</version>  
        </dependency>  
        <!--mybatis的包 -->  
        <dependency>  
            <groupId>org.mybatis</groupId>  
            <artifactId>mybatis</artifactId>  
            <version>3.2.8</version>  
        </dependency>  
        <!--mybatis和spring整合包 -->  
        <dependency>  
            <groupId>org.mybatis</groupId>  
            <artifactId>mybatis-spring</artifactId>  
            <version>1.2.2</version>  
        </dependency>  
        <!-- 我使用的连接数据的jar包 -->  
        <dependency>  
            <groupId>commons-dbcp</groupId>  
            <artifactId>commons-dbcp</artifactId>  
            <version>1.4</version>  
        </dependency>  
        <dependency>  
            <groupId>org.springframework</groupId>  
            <artifactId>spring-jdbc</artifactId>  
            <version>4.2.0.RELEASE</version>  
        </dependency>  
        <!--spring事务tx包的引用 -->  
        <dependency>  
            <groupId>org.springframework</groupId>  
            <artifactId>spring-tx</artifactId>  
            <version>4.2.0.RELEASE</version>  
        </dependency>  
  
        <!--数据库jar包 -->  
        <dependency>
            <groupId>mysql</groupId>
            <artifactId>mysql-connector-java</artifactId>
            <version>5.1.39</version>
        </dependency> 
        <dependency>  
            <groupId>commons-io</groupId>  
            <artifactId>commons-io</artifactId>  
            <version>2.2</version>  
        </dependency>  
        
        <!-- https://mvnrepository.com/artifact/dom4j/dom4j -->
        <dependency>
            <groupId>dom4j</groupId>
            <artifactId>dom4j</artifactId>
            <version>1.6.1</version>
        </dependency>
         <dependency>  
            <groupId>jaxen</groupId>  
            <artifactId>jaxen</artifactId>  
            <version>1.1.6</version>  
        </dependency>
        <!-- google guava jar -->
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>${guava.version}</version>
        </dependency>
        
        <dependency>
            <groupId>org.slf4j</groupId>
            <artifactId>slf4j-api</artifactId>
            <version>1.7.21</version>
        </dependency>
        
        <!-- https://mvnrepository.com/artifact/org.springframework/spring-test -->
    <dependency>
        <groupId>org.springframework</groupId>
        <artifactId>spring-test</artifactId>
        <version>4.2.9.RELEASE</version>
        <scope>test</scope>
    </dependency>
    
    <dependency> 
            <groupId>redis.clients</groupId> 
            <artifactId>jedis</artifactId>
            <version>2.6.2</version>
    </dependency>
    
    <!-- https://mvnrepository.com/artifact/org.springframework.data/spring-data-redis -->
    <dependency>
        <groupId>org.springframework.data</groupId>
        <artifactId>spring-data-redis</artifactId>
        <version>1.2.0.RELEASE</version>
    </dependency>
        
    </dependencies>  
    <build>  
        <finalName>manager</finalName>  
    </build>  
</project>

spring-bean.xml文件

<beans xmlns="http://www.springframework.org/schema/beans"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:mvc="http://www.springframework.org/schema/mvc"  
    xmlns:context="http://www.springframework.org/schema/context"  
    xmlns:aop="http://www.springframework.org/schema/aop" xmlns:tx="http://www.springframework.org/schema/tx"  
    xsi:schemaLocation="http://www.springframework.org/schema/beans   
        http://www.springframework.org/schema/beans/spring-beans-3.2.xsd   
        http://www.springframework.org/schema/mvc   
        http://www.springframework.org/schema/mvc/spring-mvc-3.2.xsd   
        http://www.springframework.org/schema/context   
        http://www.springframework.org/schema/context/spring-context-3.2.xsd   
        http://www.springframework.org/schema/aop   
        http://www.springframework.org/schema/aop/spring-aop-3.2.xsd   
        http://www.springframework.org/schema/tx   
        http://www.springframework.org/schema/tx/spring-tx-3.2.xsd ">  
    
    <bean id="orderDao" class="com.ocean.spring.bean.OrderDao">
    </bean>
    
    <bean id="orderService" class="com.ocean.spring.bean.OrderService">
        <!-- 需要注入的属性 -->
        <property name="orderDao" ref="orderDao">
        </property>
    </bean>  
</beans>

spring-dao.xml文件

<beans xmlns="http://www.springframework.org/schema/beans"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:mvc="http://www.springframework.org/schema/mvc"  
    xmlns:context="http://www.springframework.org/schema/context"  
    xmlns:aop="http://www.springframework.org/schema/aop" xmlns:tx="http://www.springframework.org/schema/tx"  
    xsi:schemaLocation="http://www.springframework.org/schema/beans   
        http://www.springframework.org/schema/beans/spring-beans-3.2.xsd   
        http://www.springframework.org/schema/mvc   
        http://www.springframework.org/schema/mvc/spring-mvc-3.2.xsd   
        http://www.springframework.org/schema/context   
        http://www.springframework.org/schema/context/spring-context-3.2.xsd   
        http://www.springframework.org/schema/aop   
        http://www.springframework.org/schema/aop/spring-aop-3.2.xsd   
        http://www.springframework.org/schema/tx   
        http://www.springframework.org/schema/tx/spring-tx-3.2.xsd ">  
    <!--配置数据库连接属性-->  
    <!--配置数据库连接属性加载db.properties的数据库连接信息文件 这里配置有很多学问，需要我以后学习-->  
    <context:property-placeholder location="classpath:db.properties"></context:property-placeholder>  
    <bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource">  
        <property name="driverClassName" value="${jdbc.driver}"/>  
        <property name="url" value="${jdbc.url}"/>  
        <property name="username" value="${jdbc.username}"/>  
        <property name="password" value="${jdbc.password}"/>  
        <property name="maxActive" value="30"/>  
        <property name="maxIdle" value="5"/>  
    </bean>  
  
    <!-- 让spring管理sqlsessionfactory 使用mybatis和spring整合包中的 -->  
    <bean id="sqlSessionFactory" class="org.mybatis.spring.SqlSessionFactoryBean">  
        <!--注入数据库连接对象-->  
        <property name="dataSource" ref="dataSource"/>  
        <!--加载mybatis配置文件 这里mybatis配置文件的工作都在spring中配置了所以mybatis只是配置别名就可以-->  
        <property name="configLocation" value="classpath:/config/mybatis/mybatisconfig.xml"/>  
    </bean>  
      
    <!-- mapper扫描器 -->  
   <!--  <bean class="org.mybatis.spring.mapper.MapperScannerConfigurer">  
        扫描的包，如果要扫描多个，中间用,隔开  
        <property name="basePackage" value="com.ys.mybatis.mapper"></property>  
        <property name="sqlSessionFactoryBeanName" value="sqlSessionFactory" />  
    </bean> -->
    
    <bean id="userDao" class="org.mybatis.spring.mapper.MapperFactoryBean">
        <property name="sqlSessionFactory" ref="sqlSessionFactory" />
        <property name="mapperInterface" value="com.ocean.dao.UserDao" />
    </bean> 
  
</beans>

spring-redis.xml文件

 
<beans xmlns="http://www.springframework.org/schema/beans"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:mvc="http://www.springframework.org/schema/mvc"  
    xmlns:context="http://www.springframework.org/schema/context"  
    xmlns:aop="http://www.springframework.org/schema/aop" xmlns:tx="http://www.springframework.org/schema/tx"  
    xsi:schemaLocation="http://www.springframework.org/schema/beans   
        http://www.springframework.org/schema/beans/spring-beans-3.2.xsd   
        http://www.springframework.org/schema/mvc   
        http://www.springframework.org/schema/mvc/spring-mvc-3.2.xsd   
        http://www.springframework.org/schema/context   
        http://www.springframework.org/schema/context/spring-context-3.2.xsd   
        http://www.springframework.org/schema/aop   
        http://www.springframework.org/schema/aop/spring-aop-3.2.xsd   
        http://www.springframework.org/schema/tx   
        http://www.springframework.org/schema/tx/spring-tx-3.2.xsd ">  
    
    <!-- redis 连接池-->
    <bean id="jedisPoolConfig" class="redis.clients.jedis.JedisPoolConfig">
    </bean>
 
 <!-- redis 数据源 -->
    <bean id="jedisConnectionFactory"
    class="org.springframework.data.redis.connection.jedis.JedisConnectionFactory">
    
    <!-- 连接地址 -->    
    <property name="hostName" value="127.0.0.1" />
    <!-- 连接端口号 -->
    <property name="port" value="6379" />
    <!-- 连接超时时间 -->
    <!-- <property name="timeout" value="3000" /> -->
    <!-- 连接连接池 -->
    <property name="poolConfig" ref="jedisPoolConfig" />
   
    <property name="usePool" value="true" />
    </bean>
 
 
    <bean id="redisTemplate" class="org.springframework.data.redis.core.RedisTemplate">
        <property name="connectionFactory" ref="jedisConnectionFactory" />
        <!-- 解决redis序列化问题 -->
        <property name="keySerializer">  
            <bean class="org.springframework.data.redis.serializer.StringRedisSerializer" />  
        </property>  
        <property name="valueSerializer">  
            <bean class="org.springframework.data.redis.serializer.StringRedisSerializer" />  
        </property>  
        <property name="hashKeySerializer">  
            <bean class="org.springframework.data.redis.serializer.StringRedisSerializer" />  
        </property>  
        <property name="hashValueSerializer">  
            <bean class="org.springframework.data.redis.serializer.StringRedisSerializer" />  
         </property> 
    </bean> 
</beans>

mybatisconfig.xml文件

<?xml version="1.0" encoding="UTF-8" ?>  
<!DOCTYPE configuration  
PUBLIC "-//mybatis.org//DTD Config 3.0//EN"  
"http://mybatis.org/dtd/mybatis-3-config.dtd">  
<configuration>  
    <typeAliases>  
        <!-- 扫描别名 -->  
       <typeAlias type="com.ocean.dto.UserDto" alias="userDto" />
    </typeAliases>  
<!-- 加载我们的Sql语句的xml文件 -->  
  <mappers>
        <mapper resource="config/mybatis/user.xml" />
  </mappers>        
<!-- 使用自动扫描器时，mapper.xml文件如果和mapper.java接口在一个目录则此处不用定义mappers -->  
</configuration>

user.xml文件

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper PUBLIC 
    "-//mybatis.org//DTD Mapper 3.0//EN" 
    " http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="com.ocean.dao.UserDao">
    <select id="getUser" resultType="userDto" parameterType="int">
        select account userName,password passWord from market.`store_account` where id = #{id}
    </select>
    
    <select id="getAllUser" resultType="userDto">
        select account userName,password passWord from market.`store_account`
    </select>
    
    <select id="getUserByUserName" resultType="userDto" parameterType="String">
        select account userName,password passWord from market.`store_account` where account = #{userName}
    </select>
</mapper>

缓存击穿之布隆过滤器bloom Filter实现方式

什么是布隆过滤器？

解决缓存击穿问题

@PostConstruct和@PreDestroy

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

小白架构师之路