布隆过滤器 BloomFilter

面试题

现有 50 亿个电话号码，如何要快速准确判断这些电话号码是否已经存在？
判断是否存在，布隆过滤器了解过吗？
安全连接网址，全球数 10 亿的网址判断？
黑名单校验，识别垃圾邮件
白名单校验，识别出合法用户进行后续处理

概述

由一个初值都为 0 的 bit 数组和多个哈希函数构成，用来快速判断集合中是否存在某个元素。其本质就是判断具体数据是否存在于一个大的集合中。

Redis-布隆过滤器初始状态

目的：减少内存占用

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

备注：布隆过滤器是一种类似 set 的数据结构，只是统计结果在巨量数据下有点小瑕疵，不够完美。它实际上是一个很长的二进制数组和一系列随机 Hash 算法映射函数，主要用于判断一个元素是否在集合中。

作用

高效地插入和查询，占用空间少，返回的结果是不确定性 + 不够完美。
一个元素如果判断结果：存在时，元素不一定存在，但是判断结果不存在时，元素一定不存在。
布隆过滤器可以添加元素，但是不能删除元素，由于涉及 Hashcode 判断依据，删掉元素会导致误判率增加。

布隆过滤器原理

布隆过滤器实现原理和数据结构

原理

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

实质就是一个大型位数组和几个不同的无偏 Hash 函数（无偏表示分布均匀）。由一个初值都为零的 bit 数组和多个 Hash 函数构成，用来快速判断某个数据是否存在。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率。

添加 Key 和查询 Key

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

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

结论：有，是可能有；无，是肯定无

Hash 冲突导致数据不精准

当有变量被加入集合时，通过 N 个映射函数将这个变量映射成位图中的 N 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

Redis-布隆过滤器赋值状态

查询某个变量的时候我们只要看看这些点是不是都是 1，就可以大概率知道集合中有没有它。如果这些点，有任何一个为零则被查询变量一定不在，如果都是 1，则被查询变量很可能存在。因为映射函数本身就是散列函数，散列函数是会有碰撞的。

正是基于布隆过滤器的快速检测特性，我们可以在把数据写入数据库时，使用布隆过滤器做个标记。当缓存缺失后，应用查询数据库时，可以通过查询布隆过滤器快速判断数据是否存在。如果不存在，就不用再去数据库中查询了。这样一来，即使发生缓存穿透了，大量请求只会查询 Redis 和布隆过滤器，而不会挤压到数据库，就不会影响数据库的正常运行。布隆过滤器可以使用 Redis 实现，本身就能承担较大的并发访问压力。

哈希函数

哈希函数的概念是：将任意大小的输入数据转换为特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。

Redis-哈希函数概念

如果两个散列值是不相同的（根据同一个函数）那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。

散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况成为”散列冲突“。用 Hash 表存储大数据量时，空间效率还是很低，当只有一个 Hash 函数时，还很容易发生哈希碰撞。

Java 中 Hash 冲突案例

HashCodeConflictDemo.java

public class HashCodeConflictDemo {
    public static void main(String[] args) {
        Set<Integer> hashCodeSet = new HashSet<>();
        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());
        System.out.println("柳柴".hashCode());
        System.out.println("柴柕".hashCode());
        for (int i = 0; i <200000; i++) {
            int hashCode = new Object().hashCode();
            if(hashCodeSet.contains(hashCode)) {
                System.out.println("出现了重复的hashcode: "+hashCode+"\t 运行到"+i);
                break;
            }
            hashCodeSet.add(hashCode);
        }
    }
}

使用步骤

初始化 Bitmap

布隆过滤器本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0。

Redis-布隆过滤器初始状态

添加数据

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

例如，我们添加一个字符串 wmyskxz，对字符串进行多次 Hash(Key) → 取模运行→ 得到位置。

Redis-布隆过滤器-Add-操作

判断是否存在

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

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

Redis-布隆过滤器查询不存在的-Key-时存在误判

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

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

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

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

总结

使用时最好不要让实际元素数量远大于初始化数量，一次给够避免扩容；
当实际元素数量超过初始化数量时，应该对布隆过滤器进行重建，重新分配一个 size 更大的过滤器，在将所有的历史元素批量 add 进行。

布隆过滤器使用场景

解决缓存穿透的问题

一般情况下，和 Redis 结合 Bitmap 使用，先查询缓存 Redis 是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。缓存透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

使用布隆过滤器解决缓存穿透的问题

把已存在数据的 Key 存在布隆过滤器中，相当于 Redis 前面挡着一个布隆过滤器；
当有新的请求时，先到布隆过滤器中查询是否存在；
如果布隆过滤器中不存在该条数据则直接返回；
如果布隆过滤器中已存在，才去查询缓存 Redis，如果 Redis 里没查询到则再查询 MySQL 数据库。

Redis-布隆过滤器解决缓存穿透问题

黑名单校验，识别垃圾邮件

发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。

假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，在收到邮件时，判断邮件地址是否在布隆过滤器中即可。

安全连接网址，全球上 10 亿的网址判断

手写布隆过滤器

整体架构

Redis-布隆过滤器案例整体架构

二进制数组构建过程：

预加载符合条件的记录；
计算每条记录 Hash 值；
计算 Hash 值对应的 Bitmap 数组索引；
修改值为 1。

查找元素是否存在的过程：

计算元素的 Hash 值；
计算 Hash 值对应二进制数组的索引；
找到数组中对应索引的值，0 表示不存在，1 表示存在。

步骤设计

Redis 的 setbit/getbit

Terminal

127.0.0.1:6379> keys *
whitelistCustomer
customer:11
127.0.0.1:6379> type whitelistCustomer
string
127.0.0.1:6379> GETBIT whitelistCustomer 1
0
127.0.0.1:6379> GETBIT whitelistCustomer 1772098690
1
127.0.0.1:6379>

Redis 自带的二进制数组 Bitmap，布隆过滤器就是 whitelistCustomer，在 1772098690 这个索引有 1 表示有 customer:11 这个用户存在，key:customer:11 对应索引 index：1772098756

setBit 的构建过程

@PostConstruct 初始化白名单数据；
计算元素的 Hash 值；
通过上一步 Hash 值算出对应的二进制数组的索引；
将对应索引的值修改为数字 1，表示存在。

getBit 查询是否存在

计算元素的 Hash 值；
通过上一步 Hash 值算出对应的二进制数组的索引；
返回对应索引的值，0 表示无，1 表示存在。

Spring Boot Redis MyBatis 案例基础与一键编码环境整合

MyBatis 通用 Mapper4

mybatis-generator http://mybatis.org/generator/ (opens in a new tab)
MyBatis 通用 Mapper4 官网 http://github.com/abel533/Mapper (opens in a new tab)
新建 Spring Boot Model：mybatis_generator

一键生成

t_customer

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`)
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8mb4

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<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/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
 
    <groupId>dev.matrixlab.redis7</groupId>
    <artifactId>mybatis_generator</artifactId>
    <version>1.0-SNAPSHOT</version>
 
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.6.10</version>
        <relativePath/>
    </parent>
 
 
    <properties>
        <!--  依赖版本号 -->
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <maven.compiler.source>1.8</maven.compiler.source>
        <maven.compiler.target>1.8</maven.compiler.target>
        <java.version>1.8</java.version>
        <hutool.version>5.5.8</hutool.version>
        <druid.version>1.1.18</druid.version>
        <mapper.version>4.1.5</mapper.version>
        <pagehelper.version>5.1.4</pagehelper.version>
        <mysql.version>5.1.39</mysql.version>
        <swagger2.version>2.9.2</swagger2.version>
        <swagger-ui.version>2.9.2</swagger-ui.version>
        <mybatis.spring.version>2.1.3</mybatis.spring.version>
    </properties>
 
 
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
 
        <!--Mybatis 通用mapper tk单独使用，自己带着版本号-->
        <dependency>
            <groupId>org.mybatis</groupId>
            <artifactId>mybatis</artifactId>
            <version>3.4.6</version>
        </dependency>
        <!--mybatis-spring-->
        <dependency>
            <groupId>org.mybatis.spring.boot</groupId>
            <artifactId>mybatis-spring-boot-starter</artifactId>
            <version>${mybatis.spring.version}</version>
        </dependency>
        <!-- Mybatis Generator -->
        <dependency>
            <groupId>org.mybatis.generator</groupId>
            <artifactId>mybatis-generator-core</artifactId>
            <version>1.4.0</version>
            <scope>compile</scope>
            <optional>true</optional>
        </dependency>
        <!--通用Mapper-->
        <dependency>
            <groupId>tk.mybatis</groupId>
            <artifactId>mapper</artifactId>
            <version>${mapper.version}</version>
        </dependency>
        <!--persistence-->
        <dependency>
            <groupId>javax.persistence</groupId>
            <artifactId>persistence-api</artifactId>
            <version>1.0.2</version>
        </dependency>
 
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <optional>true</optional>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
            <exclusions>
                <exclusion>
                    <groupId>org.junit.vintage</groupId>
                    <artifactId>junit-vintage-engine</artifactId>
                </exclusion>
            </exclusions>
        </dependency>
    </dependencies>
 
    <build>
        <resources>
            <resource>
                <directory>${basedir}/src/main/java</directory>
                <includes>
                    <include>**/*.xml</include>
                </includes>
            </resource>
            <resource>
                <directory>${basedir}/src/main/resources</directory>
            </resource>
        </resources>
        <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.6</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>
</project>

src/main/resources/config.properties

#t_customer表包名
package.name=dev.matrixlab.redis7
 
jdbc.driverClass = com.mysql.jdbc.Driver
jdbc.url = jdbc:mysql://localhost:3306/bigdata
jdbc.user = root
jdbc.password =123456
 
```xml filename="generatorConfig.xml" showLineNumbers copy
<?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>

双击插件 mybatis-generator:generate，一键生成 entity + mapper 接口 + xml 实现 SQL

Spring Boot MyBatis Redis 缓存实战编码

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<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/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
 
    <groupId>dev.matrixlab.redis7</groupId>
    <artifactId>redis7_study</artifactId>
    <version>1.0-SNAPSHOT</version>
 
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.6.10</version>
        <relativePath/>
    </parent>
 
    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <maven.compiler.source>1.8</maven.compiler.source>
        <maven.compiler.target>1.8</maven.compiler.target>
        <junit.version>4.12</junit.version>
        <log4j.version>1.2.17</log4j.version>
        <lombok.version>1.16.18</lombok.version>
    </properties>
 
    <dependencies>
        <!--SpringBoot通用依赖模块-->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <!--jedis-->
        <dependency>
            <groupId>redis.clients</groupId>
            <artifactId>jedis</artifactId>
            <version>4.3.1</version>
        </dependency>
        <!--lettuce-->
        <!--<dependency>
            <groupId>io.lettuce</groupId>
            <artifactId>lettuce-core</artifactId>
            <version>6.2.1.RELEASE</version>
        </dependency>-->
        <!--SpringBoot与Redis整合依赖-->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-pool2</artifactId>
        </dependency>
        <!--swagger2-->
        <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>
        <!--Mysql数据库驱动-->
        <dependency>
            <groupId>mysql</groupId>
            <artifactId>mysql-connector-java</artifactId>
            <version>5.1.47</version>
        </dependency>
        <!--SpringBoot集成druid连接池-->
        <dependency>
            <groupId>com.alibaba</groupId>
            <artifactId>druid-spring-boot-starter</artifactId>
            <version>1.1.10</version>
        </dependency>
        <dependency>
            <groupId>com.alibaba</groupId>
            <artifactId>druid</artifactId>
            <version>1.1.16</version>
        </dependency>
        <!--mybatis和springboot整合-->
        <dependency>
            <groupId>org.mybatis.spring.boot</groupId>
            <artifactId>mybatis-spring-boot-starter</artifactId>
            <version>1.3.0</version>
        </dependency>
        <!--hutool-->
        <dependency>
            <groupId>cn.hutool</groupId>
            <artifactId>hutool-all</artifactId>
            <version>5.2.3</version>
        </dependency>
        <!--persistence-->
        <dependency>
            <groupId>javax.persistence</groupId>
            <artifactId>persistence-api</artifactId>
            <version>1.0.2</version>
        </dependency>
        <!--通用Mapper-->
        <dependency>
            <groupId>tk.mybatis</groupId>
            <artifactId>mapper</artifactId>
            <version>4.1.5</version>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-autoconfigure</artifactId>
        </dependency>
        <!--通用基础配置junit/devtools/test/log4j/lombok/-->
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>${junit.version}</version>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>log4j</groupId>
            <artifactId>log4j</artifactId>
            <version>${log4j.version}</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>${lombok.version}</version>
            <optional>true</optional>
        </dependency>
    </dependencies>
 
    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
            </plugin>
        </plugins>
    </build>
 
</project>

src/main/resources/application.yml

server.port=7777
 
spring.application.name=redis7_study
 
# ========================logging=====================
logging.level.root=info
logging.level.dev.matrixlab.redis7=info
logging.pattern.console=%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger- %msg%n 
 
logging.file.name=D:/mylogs2023/redis7_study.log
logging.pattern.file=%d{yyyy-MM-dd HH:mm:ss.SSS} [%thread] %-5level %logger- %msg%n
 
# ========================swagger=====================
spring.swagger2.enabled=true
#在springboot2.6.X结合swagger2.9.X会提示documentationPluginsBootstrapper空指针异常，
#原因是在springboot2.6.X中将SpringMVC默认路径匹配策略从AntPathMatcher更改为PathPatternParser，
# 导致出错，解决办法是matching-strategy切换回之前ant_path_matcher
spring.mvc.pathmatch.matching-strategy=ant_path_matcher
 
# ========================redis单机=====================
spring.redis.database=0
# 修改为自己真实IP
spring.redis.host=192.168.111.185
spring.redis.port=6379
spring.redis.password=111111
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
 
# ========================alibaba.druid=====================
spring.datasource.type=com.alibaba.druid.pool.DruidDataSource
spring.datasource.driver-class-name=com.mysql.jdbc.Driver
spring.datasource.url=jdbc:mysql://localhost:3306/bigdata?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=dev.matrixlab.redis7.entities
 
# ========================redis集群=====================
#spring.redis.password=111111
## 获取失败 最大重定向次数
#spring.redis.cluster.max-redirects=3
#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
##支持集群拓扑动态感应刷新,自适应拓扑刷新是否使用所有可用的更新，默认false关闭
#spring.redis.lettuce.cluster.refresh.adaptive=true
##定时刷新
#spring.redis.lettuce.cluster.refresh.period=2000
#spring.redis.cluster.nodes=192.168.111.185:6381,192.168.111.185:6382,192.168.111.172:6383,192.168.111.172:6384,192.168.111.184:6385,192.168.111.184:6386

Redis7Study7777.java

package dev.matrixlab.redis7;
 
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import tk.mybatis.spring.annotation.MapperScan;
 
@SpringBootApplication
@MapperScan("dev.matrixlab.redis7.mapper") //import tk.mybatis.spring.annotation.MapperScan;
public class Redis7Study7777 {
    public static void main(String[] args) {
        SpringApplication.run(Redis7Study7777.class,args);
    }
}

Customer.java

package dev.matrixlab.redis7.entities;
 
import javax.persistence.GeneratedValue;
import javax.persistence.Id;
import javax.persistence.Table;
import java.io.Serializable;
import java.util.Date;
 
@Table(name = "t_customer")
public class Customer implements Serializable {
    @Id
    @GeneratedValue(generator = "JDBC")
    private Integer id;
 
    private String cname;
 
    private Integer age;
 
    private String phone;
 
    private Byte sex;
 
    private Date birth;
 
    public Customer() {
    }
 
    public Customer(Integer id, String cname) {
        this.id = id;
        this.cname = cname;
    }
 
    /**
      * @return id
      */
    public Integer getId() {
        return id;
    }
 
    /**
      * @param id
      */
    public void setId(Integer id) {
        this.id = id;
    }
 
    /**
      * @return cname
      */
    public String getCname() {
        return cname;
    }
 
    /**
      * @param cname
      */
    public void setCname(String cname) {
        this.cname = cname;
    }
 
    /**
      * @return age
      */
    public Integer getAge() {
        return age;
    }
 
    /**
      * @param age
      */
    public void setAge(Integer age) {
        this.age = age;
    }
 
    /**
      * @return phone
      */
    public String getPhone() {
        return phone;
    }
 
    /**
      * @param phone
      */
    public void setPhone(String phone) {
        this.phone = phone;
    }
 
    /**
      * @return sex
      */
    public Byte getSex() {
        return sex;
    }
 
    /**
      * @param sex
      */
    public void setSex(Byte sex) {
        this.sex = sex;
    }
 
    /**
      * @return birth
      */
    public Date getBirth() {
        return birth;
    }
 
    /**
      * @param birth
      */
    public void setBirth(Date birth) {
        this.birth = birth;
    }
 
    @Override
    public String toString()
    {
        return "Customer{" +
                "id=" + id +
                ", cname='" + cname + '\'' +
                ", age=" + age +
                ", phone='" + phone + '\'' +
                ", sex=" + sex +
                ", birth=" + birth +
                '}';
    }
}

CustomerMapper.java

package dev.matrixlab.redis7.mapper;
 
import dev.matrixlab.redis7.entities.Customer;
import tk.mybatis.mapper.common.Mapper;
 
public interface CustomerMapper extends Mapper<Customer> {
}

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

CustomerSerivce.java

package dev.matrixlab.redis7.service;
 
import dev.matrixlab.redis7.entities.Customer;
import dev.matrixlab.redis7.mapper.CustomerMapper;
import dev.matrixlab.redis7.utils.CheckUtils;
import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
 
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
 
@Service
@Slf4j
public class CustomerSerivce {
    public static final String CACHE_KEY_CUSTOMER = "customer:";
 
    @Resource
    private CustomerMapper customerMapper;
    @Resource
    private RedisTemplate redisTemplate;
 
    public void addCustomer(Customer customer) {
        int i = customerMapper.insertSelective(customer);
 
        if(i > 0) {
            //到数据库里面，重新捞出新数据出来，做缓存
            customer=customerMapper.selectByPrimaryKey(customer.getId());
            //缓存key
            String key=CACHE_KEY_CUSTOMER+customer.getId();
            //往mysql里面插入成功随后再从mysql查询出来，再插入redis
            redisTemplate.opsForValue().set(key,customer);
        }
    }
 
    public Customer findCustomerById(Integer customerId) {
        Customer customer = null;
        //缓存key的名称
        String key=CACHE_KEY_CUSTOMER+customerId;
        //1 查询redis
        customer = (Customer) redisTemplate.opsForValue().get(key);
        //redis无，进一步查询mysql
        if(customer==null){
            //2 从mysql查出来customer
            customer=customerMapper.selectByPrimaryKey(customerId);
            // mysql有，redis无
            if (customer != null) {
                //3 把mysql捞到的数据写入redis，方便下次查询能redis命中。
                redisTemplate.opsForValue().set(key,customer);
            }
        }
        return customer;
    }
}

Controller

CustomerController.java

package dev.matrixlab.redis7.controller;
 
import dev.matrixlab.redis7.entities.Customer;
import dev.matrixlab.redis7.service.CustomerSerivce;
import io.swagger.annotations.Api;
import io.swagger.annotations.ApiOperation;
import lombok.extern.slf4j.Slf4j;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;
 
import javax.annotation.Resource;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.util.Random;
import java.util.Date;
import java.util.concurrent.ExecutionException;
 
@Api(tags = "客户Customer接口+布隆过滤器讲解")
@RestController
@Slf4j
public class CustomerController {
    @Resource private CustomerSerivce customerSerivce;
 
    @ApiOperation("数据库初始化2条Customer数据")
    @RequestMapping(value = "/customer/add", method = RequestMethod.POST)
    public void addCustomer() {
        for (int i = 0; i < 2; i++) {
            Customer customer = new Customer();
            customer.setCname("customer"+i);
            customer.setAge(new Random().nextInt(30)+1);
            customer.setPhone("1381111xxxx");
            customer.setSex((byte) new Random().nextInt(2));
            customer.setBirth(Date.from(LocalDateTime.now().atZone(ZoneId.systemDefault()).toInstant()));
            customerSerivce.addCustomer(customer);
        }
    }
    @ApiOperation("单个用户查询，按customerid查用户信息")
    @RequestMapping(value = "/customer/{id}", method = RequestMethod.GET)
    public Customer findCustomerById(@PathVariable int id) {
        return customerSerivce.findCustomerById(id);
    }
}

启动测试 Swagger

新增布隆过滤器案例

代码示例

BloomFilterInit.java

package dev.matrixlab.redis7.filter;
 
import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;
 
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
 
/**
 * 布隆过滤器白名单初始化工具类，一开始就设置一部分数据为白名单所有，
 * 白名单业务默认规定：布隆过滤器有，redis也有。
 */
@Component
@Slf4j
public class BloomFilterInit {
    @Resource
    private RedisTemplate redisTemplate;
 
    @PostConstruct//初始化白名单数据，故意差异化数据演示效果......
    public void init() {
        //白名单客户预加载到布隆过滤器
        String uid = "customer:12";
        //1 计算hashcode，由于可能有负数，直接取绝对值
        int hashValue = Math.abs(uid.hashCode());
        //2 通过hashValue和2的32次方取余后，获得对应的下标坑位
        long index = (long) (hashValue % Math.pow(2, 32));
        log.info(uid+" 对应------坑位index:{}",index);
        //3 设置redis里面bitmap对应坑位，该有值设置为1
        redisTemplate.opsForValue().setBit("whitelistCustomer",index,true);
    }
}

CheckUtils.java

package dev.matrixlab.redis7.utils;
 
import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Component;
 
import javax.annotation.Resource;
 
@Component
@Slf4j
public class CheckUtils {
    @Resource
    private RedisTemplate redisTemplate;
 
    public boolean checkWithBloomFilter(String checkItem,String key) {
        int hashValue = Math.abs(key.hashCode());
        long index = (long) (hashValue % Math.pow(2, 32));
        boolean existOK = redisTemplate.opsForValue().getBit(checkItem, index);
        log.info("----->key:"+key+"\t对应坑位index:"+index+"\t是否存在:"+existOK);
        return existOK;
    }
}

CustomerSerivce.java

package dev.matrixlab.redis7.service;
 
import dev.matrixlab.redis7.entities.Customer;
import dev.matrixlab.redis7.mapper.CustomerMapper;
import dev.matrixlab.redis7.utils.CheckUtils;
import lombok.extern.slf4j.Slf4j;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
 
import javax.annotation.PostConstruct;
import javax.annotation.Resource;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
 
@Service
@Slf4j
public class CustomerSerivce {
    public static final String CACHE_KEY_CUSTOMER = "customer:";
 
    @Resource
    private CustomerMapper customerMapper;
    @Resource
    private RedisTemplate redisTemplate;
 
    @Resource
    private CheckUtils checkUtils;
 
    public void addCustomer(Customer customer){
        int i = customerMapper.insertSelective(customer);
 
        if(i > 0)
        {
            //到数据库里面，重新捞出新数据出来，做缓存
            customer=customerMapper.selectByPrimaryKey(customer.getId());
            //缓存key
            String key=CACHE_KEY_CUSTOMER+customer.getId();
            //往mysql里面插入成功随后再从mysql查询出来，再插入redis
            redisTemplate.opsForValue().set(key,customer);
        }
    }
 
    public Customer findCustomerById(Integer customerId){
        Customer customer = null;
 
        //缓存key的名称
        String key=CACHE_KEY_CUSTOMER+customerId;
 
        //1 查询redis
        customer = (Customer) redisTemplate.opsForValue().get(key);
 
        //redis无，进一步查询mysql
        if(customer==null)
        {
            //2 从mysql查出来customer
            customer=customerMapper.selectByPrimaryKey(customerId);
            // mysql有，redis无
            if (customer != null) {
                //3 把mysql捞到的数据写入redis，方便下次查询能redis命中。
                redisTemplate.opsForValue().set(key,customer);
            }
        }
        return customer;
    }
 
    /**
     * BloomFilter → redis → mysql
     * 白名单：whitelistCustomer
     * @param customerId
     * @return
     */
 
    @Resource
    private CheckUtils checkUtils;
    public Customer findCustomerByIdWithBloomFilter (Integer customerId)
    {
        Customer customer = null;
 
        //缓存key的名称
        String key = CACHE_KEY_CUSTOMER + customerId;
 
        //布隆过滤器check，无是绝对无，有是可能有
        //===============================================
        if(!checkUtils.checkWithBloomFilter("whitelistCustomer",key))
        {
            log.info("白名单无此顾客信息:{}",key);
            return null;
        }
        //===============================================
 
        //1 查询redis
        customer = (Customer) redisTemplate.opsForValue().get(key);
        //redis无，进一步查询mysql
        if (customer == null) {
            //2 从mysql查出来customer
            customer = customerMapper.selectByPrimaryKey(customerId);
            // mysql有，redis无
            if (customer != null) {
                //3 把mysql捞到的数据写入redis，方便下次查询能redis命中。
                redisTemplate.opsForValue().set(key, customer);
            }
        }
        return customer;
    }
}

CustomerController.java

package dev.matrixlab.redis7.controller;
 
import dev.matrixlab.redis7.entities.Customer;
import dev.matrixlab.redis7.service.CustomerSerivce;
import io.swagger.annotations.Api;
import io.swagger.annotations.ApiOperation;
import lombok.extern.slf4j.Slf4j;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RestController;
 
import javax.annotation.Resource;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.util.Random;
import java.util.Date;
import java.util.concurrent.ExecutionException;
 
@Api(tags = "客户Customer接口+布隆过滤器讲解")
@RestController
@Slf4j
public class CustomerController {
 
    @Resource private CustomerSerivce customerSerivce;
 
    @ApiOperation("数据库初始化2条Customer数据")
    @RequestMapping(value = "/customer/add", method = RequestMethod.POST)
    public void addCustomer() {
        for (int i = 0; i < 2; i++) {
            Customer customer = new Customer();
 
            customer.setCname("customer"+i);
            customer.setAge(new Random().nextInt(30)+1);
            customer.setPhone("1381111xxxx");
            customer.setSex((byte) new Random().nextInt(2));
            customer.setBirth(Date.from(LocalDateTime.now().atZone(ZoneId.systemDefault()).toInstant()));
 
            customerSerivce.addCustomer(customer);
        }
    }
 
    @ApiOperation("单个用户查询，按customerid查用户信息")
    @RequestMapping(value = "/customer/{id}", method = RequestMethod.GET)
    public Customer findCustomerById(@PathVariable int id) {
        return customerSerivce.findCustomerById(id);
    }
 
    @ApiOperation("BloomFilter案例讲解")
    @RequestMapping(value = "/customerbloomfilter/{id}", method = RequestMethod.GET)
    public Customer findCustomerByIdWithBloomFilter(@PathVariable int id) throws ExecutionException, InterruptedException {
        return customerSerivce.findCustomerByIdWithBloomFilter(id);
    }
}

测试说明

布隆过滤器有，redis 有；
布隆过滤器无，redis 无；
布隆过滤器无，直接返回。

布隆过滤器优缺点

优点

高效地插入和删除，内存占用 bit 空间少。

缺点

不能删除元素。因为删除元素会导致误判率增加，因为 hash 冲突同一个位置可能存地东西是多个共有的，你删除一个元素的同时可能也把其他的删除了。
存在误判，不能精准过滤。

布谷鸟过滤器

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。

论文《Cuckoo Filter：Better Than Bloom》

https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf#:~:text=Cuckoo%20%EF%AC%81lters%20support%20adding%20and%20removing%20items%20dynamically,have%20lower%20space%20overhead%20than%20space-optimized%20Bloom%20%EF%AC%81lters (opens in a new tab).

案例落地实战 HyperLogLog GEO Bitmap 缓存挑战与解决方案