一、布隆过滤器BloomFilter

1.1、面试题

1.2、布隆过滤器简介

1.2.1、设计思想

1.3、特点

1.4、布隆过滤器原理

1.4.1、实现原理与数据结构

1.4.2、添加key、查询key

1.4.3、hash冲突导致数据不精准

1.4.4、三步骤

1.4.5、布隆过滤器误判，为什么不要删除

1.4.6、小结

1.5、使用场景

1.6、实现布隆过滤器

1.6.1、架构设计

1.6.2、步骤设计

1.6.3、实现springboot+redis7+mybatis实现基础案例

1.6.4、布隆过滤器加bitmap

1.7、布隆过滤器的优缺点

一、布隆过滤器BloomFilter

1.1、面试题

如何判断2亿个电话是否已经存在？

1、通过数据查询----数据量太大速度慢

2、数据预防在内存集合中:内存太大。

1.2、布隆过滤器简介

由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断集合中存在某个元素

1.2.1、设计思想

目的：减少内存占用

方式：不保存数据，只是在内存中做一个是否存在的标记flag

本质就是判断具体数据是否存在于一个大的集合中。

注意：

布隆过滤器是一种类似set的数据结构，只是统计结果在巨量数据下不够完美。

1.3、特点

1、高效地插入和查询，占用空间少，返回地结果是不确定性和不够完美。

2、一个元素如果判断结果存在时，元素不一定存在，但判断结果为不存在时，则一定不存在。

3、布隆过滤器可以添加元素，但是不能删除元素，由于涉及hashcode判断依据，删掉元素会导致误判率增加。

1.4、布隆过滤器原理

1.4.1、实现原理与数据结构

原理：

布隆过滤器是一种专门用来解决去重问题的高级数据结构。

本质上是一个大型位数组和几个不同的无偏hash函数(无偏即分布均匀)。由一个初值都为零的bit数组和多个个哈希函数构成，用来快速判断某个数据是否存在。但是根hyperloglog一样，它也一样有那么一点点不精确，存在一定的误判率。

1.4.2、添加key、查询key

添加key：

使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1都完成add操作。

查询key：

只要有其中一位是零就表示这个key不存在，如果都是1，则不一定存在对应的key。

结论：有，是可能有，无，是一定无

1.4.3、hash冲突导致数据不精准

使用Java代码模拟

@Test
    void contextLoads() {
        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());
        HashSet<Object> set = new HashSet<>();
        int i1;
        for (int i = 0; i < 1000000; i++) {
             i1 = new Object().hashCode();
            if (set.contains(i1)){
                System.out.println("运行到第" + i +"次出现哈希值冲突的值"+ i1);
                continue;
            }
            set.add(i1);
        }
    }

1.4.4、三步骤

初始化bitmap：

布隆过滤器本质上是由长度为m的位向量或位列表组成，最初值均设置为0

添加占坑位：

当我们向布隆过滤器中添加数据时，为了尽量地址不冲突，会使用多个hash函数对key进行运算，算得一个下标索引值，然后对位数组长度进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置。再把位数组的这几个位置都置为1就完成了add操作。
例如，我们添加一个字符串wmyskxz，对字符串进行多次hash(key)→取模运行→得到坑位。

判断是否存在：

向布隆过滤器查询某个key是否存在时，先把这个key通过相同的多个hash函数进行运算，查看对应的位置是否都为1,只要有一个位为零，那么说明布隆过滤器中这个key不存在;
如果这几个位置全都是1，那么说明极有可能存在;
因为这些位置的1可能是因为其他的key存在导致的，也就是前面说过的hash冲突。。。

就比如我们在add了字符串wmyskxz数据之后，很明显下面1/3/5这几个位置的1是因为第一次添加的wmyskxz而导致的;
此时我们查询一个没添加过的不存在的字符串inexistent-key,它有可能计算后坑位也是1/3/5，这就是误判了.....

1.4.5、布隆过滤器误判，为什么不要删除

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竞是哪个输入产生的，因此误判的根源在于相同的bit 位被多次映射且置1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。
如果我们直接删除这一位的话，会影响其他的元素

特性：
布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

1.4.6、小结

1、是否存在：有，不一定有，无，一定无

2、使用时最好不要让实际元素数量大于初始化数量，一次给够避免扩容。

3、当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个size更大的容器，在将所有历史元素批量add进行。

1.5、使用场景

1、解决缓存穿透的问题，和redis结合bitmap使用。

2、黑名单校验，识别垃圾短信

3、安全连接网址判断

1.6、实现布隆过滤器

1.6.1、架构设计

Java -----》布隆过滤器 ---》redis ----》mysql

1.6.2、步骤设计

setBit的构建：

1、@PostConstruct初始化白名单数据

2、计算元素的hash值

3、通过hash值算出对应的二进制数组坑位

4、将对应坑位的值修改为数字1，表示存在

getBit查询是否存在：

1、计算元素的hash值

2、通过hash值算出对应的二进制数组的坑位

3、返回对应坑位的值，0表示无，1表示存在

1.6.3、实现springboot+redis7+mybatis实现基础案例

sql表

CREATE TABLE t_customer(
id INT(20) NOT NULL AUTO_INCREMENT,
cname VARCHAR(50) NOT NULL,
age INT(10) NOT NULL,
phone VARCHAR(20) NOT NULL,
sex TINYINT(4) NOT NULL,
birth TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
PRIMARY KEY(id),
KEY idx_cname(cname)
)AUTO_INCREMENT=10 DEFAULT CHARSET=utf8mb4;

pom文件

 <properties>
        <java.version>8</java.version>
        <mysql.version>5.1.47</mysql.version>
        <mapper.version>4.1.5</mapper.version>
        <druid.version>1.1.16</druid.version>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>

        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <optional>true</optional>
        </dependency>
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-pool2</artifactId>
        </dependency>
        <dependency>
            <groupId>io.springfox</groupId>
            <artifactId>springfox-swagger2</artifactId>
            <version>2.9.2</version>
        </dependency>
        <dependency>
            <groupId>io.springfox</groupId>
            <artifactId>springfox-swagger-ui</artifactId>
            <version>2.9.2</version>
        </dependency>
        <!--canal-->
        <dependency>
            <groupId>com.alibaba.otter</groupId>
            <artifactId>canal.client</artifactId>
            <version>1.1.0</version>
        </dependency>
        <dependency>
            <groupId>redis.clients</groupId>
            <artifactId>jedis</artifactId>
            <version>4.3.1</version>
        </dependency>
        <dependency>
            <groupId>io.lettuce</groupId>
            <artifactId>lettuce-core</artifactId>
            <version>6.2.3.RELEASE</version>
        </dependency>
        <!--mysql驱动-->
        <dependency>
            <groupId>mysql</groupId>
            <artifactId>mysql-connector-java</artifactId>
            <version>${mysql.version}</version>
        </dependency>
        <dependency>
            <groupId>com.alibaba</groupId>
            <artifactId>druid-spring-boot-starter</artifactId>
            <version>1.1.17</version>
        </dependency>
        <dependency>
            <groupId>org.mybatis.spring.boot</groupId>
            <artifactId>mybatis-spring-boot-starter</artifactId>
            <version>2.2.2</version>
        </dependency>
        <dependency>
            <groupId>org.mybatis</groupId>
            <artifactId>mybatis</artifactId>
            <version>3.4.6</version>
        </dependency>
        <dependency>
            <groupId>tk.mybatis</groupId>
            <artifactId>mapper-spring-boot-starter</artifactId>
            <version>2.0.0</version>
        </dependency>
        <dependency>
            <groupId>org.mybatis.generator</groupId>
            <artifactId>mybatis-generator-core</artifactId>
            <version>1.3.2</version>
            <scope>compile</scope>
            <optional>true</optional>
        </dependency>
        <dependency>
            <groupId>tk.mybatis</groupId>
            <artifactId>mapper</artifactId>
            <version>${mapper.version}</version>
        </dependency>
        <!--hutool-->
        <dependency>
            <groupId>cn.hutool</groupId>
            <artifactId>hutool-all</artifactId>
            <version>5.7.13</version>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
        <!--persistence-->
        <dependency>
            <groupId>javax.persistence</groupId>
            <artifactId>persistence-api</artifactId>
            <version>1.0.2</version>
        </dependency>
    </dependencies>
    
    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <excludes>
                        <exclude>
                            <groupId>org.projectlombok</groupId>
                            <artifactId>lombok</artifactId>
                        </exclude>
                    </excludes>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.mybatis.generator</groupId>
                <artifactId>mybatis-generator-maven-plugin</artifactId>
                <version>1.3.2</version>
                <configuration>
                    <configurationFile>${basedir}/src/main/resources/generatorConfig.xml</configurationFile>
                    <overwrite>true</overwrite>
                    <verbose>true</verbose>
                </configuration>
                <dependencies>
                    <dependency>
                        <groupId>mysql</groupId>
                        <artifactId>mysql-connector-java</artifactId>
                        <version>${mysql.version}</version>
                    </dependency>
                    <dependency>
                        <groupId>tk.mybatis</groupId>
                        <artifactId>mapper</artifactId>
                        <version>${mapper.version}</version>
                    </dependency>
                </dependencies>
            </plugin>
        </plugins>
    </build>

config.properties

package.name=com.cjc.redis7

jdbc.driverClass = com.mysql.jdbc.Driver
jdbc.url = jdbc:mysql://localhost:3307/test1?useSSL=false
jdbc.user = root
jdbc.password =123456

generatorConfig.xml

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE generatorConfiguration
        PUBLIC "-//mybatis.org//DTD MyBatis Generator Configuration 1.0//EN"
        "http://mybatis.org/dtd/mybatis-generator-config_1_0.dtd">

<generatorConfiguration>
    <properties resource="config.properties"/>

    <context id="Mysql" targetRuntime="MyBatis3Simple" defaultModelType="flat">
        <property name="beginningDelimiter" value="`"/>
        <property name="endingDelimiter" value="`"/>

        <plugin type="tk.mybatis.mapper.generator.MapperPlugin">
            <property name="mappers" value="tk.mybatis.mapper.common.Mapper"/>
            <property name="caseSensitive" value="true"/>
        </plugin>

        <jdbcConnection driverClass="${jdbc.driverClass}"
                        connectionURL="${jdbc.url}"
                        userId="${jdbc.user}"
                        password="${jdbc.password}">
        </jdbcConnection>

        <javaModelGenerator targetPackage="${package.name}.entities" targetProject="src/main/java"/>

        <sqlMapGenerator targetPackage="${package.name}.mapper" targetProject="src/main/java"/>

        <javaClientGenerator targetPackage="${package.name}.mapper" targetProject="src/main/java" type="XMLMAPPER"/>

        <table tableName="t_customer" domainObjectName="Customer">
            <generatedKey column="id" sqlStatement="JDBC"/>
        </table>
    </context>
</generatorConfiguration>

使用 generator生成实体类与mapper文件如下

@Table(name = "t_customer")
@Data
public class Customer {
    @Id
    @GeneratedValue(generator = "JDBC")
    private Integer id;

    private String cname;

    private Integer age;

    private String phone;

    private Byte sex;

    private Date birth;
}

public interface CustomerMapper extends Mapper<Customer> {
}

<?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.cjc.redis7.mapper.CustomerMapper" >
  <resultMap id="BaseResultMap" type="com.cjc.redis7.entities.Customer" >
    <!--
      WARNING - @mbg.generated
    -->
    <id column="id" property="id" jdbcType="INTEGER" />
    <result column="cname" property="cname" jdbcType="VARCHAR" />
    <result column="age" property="age" jdbcType="INTEGER" />
    <result column="phone" property="phone" jdbcType="VARCHAR" />
    <result column="sex" property="sex" jdbcType="TINYINT" />
    <result column="birth" property="birth" jdbcType="TIMESTAMP" />
  </resultMap>
</mapper>

修改pom

#MySQL5.7
spring.datasource.type=com.alibaba.druid.pool.DruidDataSource
spring.datasource.driver-class-name=com.mysql.jdbc.Driver
spring.datasource.url=jdbc:mysql://localhost:3307/test1?useUnicode=true&characterEncoding=utf-8&useSSL=false
spring.datasource.username=root
spring.datasource.password=123456
spring.datasource.druid.test-while-idle=false
#mybatis配置
mybatis.mapper-locations=classpath:mapper/*.xml
mybatis.type-aliases-package=com.cjc.redis7.entities
#redis单机配置
spring.redis.database=0
spring.redis.host=192.168.200.110
spring.redis.port=6379
spring.redis.password=123456
spring.redis.lettuce.pool.max-active=8
spring.redis.lettuce.pool.max-wait=-1ms
spring.redis.lettuce.pool.max-idle=8
spring.redis.lettuce.pool.min-idle=0

修改主启动类

service

@Service
@Slf4j
public class CustomerServiceImpl implements CustomerService {
    public static final String  CACHA_KEY_CUSTOMER = "customer:";
    @Autowired
    private CustomerMapper customerMapper;
    @Autowired
    private RedisTemplate redisTemplate;

    /**
     * 添加数据
     * @param customer
     */
    @Override
    public void addCustomer(Customer customer) {
        //将数据存入mysql
        int i = customerMapper.insertSelective(customer);
        if (i > 0){
           //插入数据成功，重新查询并存入redis
            Customer result = customerMapper.selectByPrimaryKey(customer.getId());
            //redis缓存key
            String key = CACHA_KEY_CUSTOMER + customer.getId();
            //将查询的数据写入redis
            redisTemplate.opsForValue().set(key,result);
        }
    }

    @Override
    public Customer findCustomerById(Integer customerId) {
        Customer customer = null;
        //缓存redis的key
        String key = CACHA_KEY_CUSTOMER + customerId;
        //先在redis中查询
        customer = (Customer) redisTemplate.opsForValue().get(key);
        //redis查询有直接返回，没有则查询mysql
        if (customer == null){
            //查询mysql
            customer = customerMapper.selectByPrimaryKey(customerId);
            //MySQL查询有，redis没有
            if (customer != null){
                //将查询的数据回写到redis,保存数据一致性
                redisTemplate.opsForValue().set(key,customer);
            }
        }
        return customer;
    }
}

controller

@RestController
@Api(tags = "布隆过滤器")
@Slf4j
public class CustomerController {
    @Autowired
    private CustomerService customerService;
    @RequestMapping(value = "/addCustomer",method = RequestMethod.POST)
    @ApiOperation("向redis写入数据")
    public void addCustomer(){
        for (int i = 0; i < 2; i++) {
            Customer customer = new Customer();
            customer.setCname("customer" + i);
            customer.setAge(i + 10);
            customer.setPhone("123450" + i);
            customer.setSex((byte) i);
            customer.setBirth(Date.from(LocalDateTime.now().atZone(ZoneId.systemDefault()).toInstant()));
            customerService.addCustomer(customer);
        }
    }
    @RequestMapping(value = "/findCustomerById/{id}",method = RequestMethod.GET)
    @ApiOperation("查询Customer")
    public Customer findCustomerById(@PathVariable("id") Integer id) {
         return customerService.findCustomerById(id);
    }

}

1.6.4、布隆过滤器加bitmap

/**
 * 布隆过滤器白名单初始化工具类，一开始就设置一部分数据为白名单所有
 * 白名单业务默认规定，布隆过滤器有，redis是极大可能有
 */
@Component
@Slf4j
public class BloomFilterInit {
   @Autowired
    private RedisTemplate redisTemplate;
   //初始化白名单数据
   @PostConstruct
   public void init(){
      //白名单客户加载到布隆过滤器
      String key = RedisUtils.CACHA_KEY_CUSTOMER + "16";
      //计算hashValue，由于存在计算出负数可能，取绝对值
      int hashValue = Math.abs(key.hashCode());
      //通过hashValue和2的32次方后取余，获得对应的下标坑位
      long index = (long)(hashValue % Math.pow(2,32));
      log.info(key + "对应的下标坑位是:{}",index);
      //设置redis里面的bitmap对应类型白名单whitelistCustomer，将该值设为1
      redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);
   }
}

@Component
@Slf4j
public class CheckUtils {
    @Autowired
    private RedisTemplate redisTemplate;
    public boolean checkWithBloomFilter(String checkItem,String key){
        //计算hashValue，由于存在计算出负数可能，取绝对值
        int hashValue = Math.abs(key.hashCode());
        //通过hashValue和2的32次方后取余，获得对应的下标坑位
        long index = (long)(hashValue % Math.pow(2,32));
        //检查是否存在
        Boolean exist = redisTemplate.opsForValue().getBit(checkItem, index);
        log.info(key + "对应的下标坑位index" + index + "是否存在：" + exist);
        return exist;
    }
}

@Override
    public Customer findCustomerByIdWithBloomFilter(Integer customerId) {
        Customer customer = null;
        //缓存redis的key
        String key = redisUtils.CACHA_KEY_CUSTOMER + customerId;
        //布隆过滤器check ，有可能有，无肯定无
        if (!checkUtils.checkWithBloomFilter("whitelistCustomer",key)){
            log.info("白名单没有，不可以访问:" + key);
            return null;
        }
        //先在redis中查询
        customer = (Customer) redisTemplate.opsForValue().get(key);
        //redis查询有直接返回，没有则查询mysql
        if (customer == null){
            //查询mysql
            customer = customerMapper.selectByPrimaryKey(customerId);
            //MySQL查询有，redis没有
            if (customer != null){
                //将查询的数据回写到redis,保存数据一致性
                redisTemplate.opsForValue().set(key,customer);
            }
        }
        return customer;
    }

@RequestMapping(value = "/findCustomerByIdWithBloomFilter/{id}",method = RequestMethod.GET)
    @ApiOperation("查询布隆过滤器查询Customer")
    public Customer findCustomerByIdWithBloomFilter(@PathVariable("id") Integer id){
        return customerService.findCustomerByIdWithBloomFilter(id);
    }