likes
comments
collection
share

布隆过滤器适配Spring Cache及问题与解决策略

作者站长头像
站长
· 阅读数 1

布隆过滤器适配Spring Cache及问题与解决策略

铿然架构  |  作者  /  铿然一叶 这是  铿然架构  的第 113  篇原创文章

1. 介绍

本文主要内容为提供一个MVP实例去介绍布隆过滤器的落地方案，包含以下内容：

● 使用注解 + 拦截器 + spring自动配置，使能简单方便的使用布隆过滤器

● 适配Spring Cache，关联Spring Cache的注解参数，不需要重复配置注解参数

● 核心类结构设计和代码

● 使用中可能存在的问题和解决策略

除以上内容外，也会顺带回顾一下布隆过滤器基本知识，如果你已经熟悉，可以直接跳过布隆过滤器介绍章节。

2. 布隆过滤器

2.1 布隆过滤器简介

布隆过滤器（Bloom Filter）是一种空间效率很高的数据结构，用于快速判断一个元素是否在一个集合中。它的特点是高效且节省空间，但代价是有一定的误判率。其特点有：

● 快速查找

布隆过滤器可以非常快速地判断一个元素是否可能在集合中。这种查找速度通常比传统的数据结构（如哈希表、平衡树）要快。

● 空间效率

与存储所有元素的完整列表相比，布隆过滤器使用的空间更少（因为不存实际数据，只存key的hash结果）。这使得它在处理大量数据时非常有用。

如下是空间对比：

布隆过滤器适配Spring Cache及问题与解决策略 布隆过滤器存储的数据是根据对象计算出来的hash值取模得到的位置信息，在相应位置上打上"1"，每个位置只占1 bit，假设计算出来16个位置，也只是16 bit，远远小于1 int，更别说缓存里存的是对象了。

因此，对于恶意攻击，不可能把所有不存在的数据的key存在缓存中（缓存比布隆过滤器占用空间大得太多，内存将撑爆），在下次查询时直接返回空对象；而如果不放在缓存就要查询数据库才知道数据实际是否存在，导致缓存穿透，此时使用占用空间小的布隆过滤器就比较合适。

● 误判率

布隆过滤器可能会错误地判断某个不在集合中的元素为在集合中（即假阳性），但它绝不会错误地判断某个在集合中的元素为不在集合中（即没有假阴性）。这种特性使得它适用于那些对偶尔的误判容忍度较高的应用场景。

● 不支持删除

传统的布隆过滤器不支持从集合中删除元素。一旦一个元素被加入，就无法从过滤器中移除。虽然存在变体（如计数布隆过滤器）可以支持删除操作，但这会增加复杂性和空间需求。

由于其特有的误判率，它通常用在对准确性要求不是绝对严格的场合。

2.2 布隆过滤器应用场景

● 网络爬虫的URL去重

网络爬虫在抓取网页时，使用布隆过滤器可以高效地检查一个URL是否已经被访问过，从而避免重复抓取。

● 缓存穿透优化

在数据库查询中，布隆过滤器可以用来检查某个键值是否存在于数据库中，以减少对不存在数据的查询请求，从而减轻数据库的负担。

● 分布式系统中的数据同步

在分布式系统中，布隆过滤器可以用来高效地同步不同节点间的数据集，判断某个数据是否已经在其他节点存在。

● 垃圾邮件和欺诈信息过滤

电子邮件服务提供商或社交网络服务可以使用布隆过滤器来过滤垃圾邮件或欺诈信息，快速判断某些关键词或特征是否出现在已知的垃圾信息列表中。

● 密码黑名单

在用户创建账户或更改密码时，布隆过滤器可以用来检查密码是否出现在已知的被泄露密码列表中，从而提高账户安全性。

● 分布式数据库和NoSQL数据库

在这些数据库系统中，布隆过滤器可以用来减少对磁盘的访问次数，快速判断数据是否存在于某个数据块中。

● 网络协议的快速查找和决策

在某些网络协议中，布隆过滤器可以用来快速决定一个数据包是否符合特定的规则集。

● 生物信息学和基因组学

在这些领域，布隆过滤器可以用于快速查询基因序列数据库，检查特定的序列是否存在。

2.3 布隆过滤器存在的问题

布隆过滤器（Bloom Filter）是一种空间效率很高的数据结构，用于测试一个元素是否是一个集合的成员。尽管它非常有效，但也存在一些问题和局限性：

● 误判率（False Positives）

布隆过滤器可能会错误地判断某个不存在集合中的元素为存在。这是因为布隆过滤器通过多个哈希函数来设置位，而不同元素可能会导致相同的位被设置。误判率可以通过增加布隆过滤器的大小和使用更多的哈希函数来降低，但不能完全消除。

● 无法删除元素

布隆过滤器不支持从集合中删除元素。这是因为删除元素需要清除某些位，但这可能会影响到其他元素。存在一些布隆过滤器的变体，如计数布隆过滤器，可以支持删除操作，但这会增加复杂性和空间需求。

● 固定大小

布隆过滤器在创建时需要确定大小。如果预估的元素数量过小，会导致高误判率；如果过大，则会浪费空间。动态调整布隆过滤器的大小不是一个简单的任务。

● 无法确定元素是否一定不存在

虽然布隆过滤器可以告诉你一个元素可能存在于集合中，但它不能确定地告诉你一个元素一定不在集合中。

● 优化参数需要

选择合适的哈希函数和确定布隆过滤器的大小需要根据具体应用场景进行优化，这可能需要一定的经验和实验。

● 不提供数据存储

布隆过滤器只能告诉你某个元素可能在集合中，但它不存储任何关于元素本身的信息。

3. 布隆过滤器落地方案MVP

3.1 介绍

本MVP基于解决缓存穿透场景来设计和实现。

缓存穿透场景如下：

布隆过滤器适配Spring Cache及问题与解决策略

恶意攻击发起的大量查询请求数据在数据库里完全不存在，这样依赖数据库数据的缓存里自然也不会存在，于是导致这些恶意请求直达数据库，引发数据库超负载变得不可用。

为了解决缓存穿透，数据查询流程如下：

布隆过滤器适配Spring Cache及问题与解决策略

 步骤 说明
1布隆过滤器的数据必须是全量，否则会误判不存在而直接返回空结果，设计时可以给布隆过滤器增加一个状态，例如new-loading-ready，状态就绪后可用。
2首先查询布隆过滤器，存在则继续查询缓存，否则直接返回空结果。
3这一步根据实际情况选择，如果删除的数据量不大，即使缓存穿透影响也小。
4这一步统一约定一个能表达查询不到数据的结果对象则可。
5布隆过滤器中存在的数据才继续查询缓存，避免大量无效请求穿透缓存搞垮数据库。
6缓存没有找到数据则从数据库获取数据。
7将数据库查询结果放入第一步加载的全量布隆过滤器。
8将数据库查询结果放入缓存。
9从缓存获取到数据返回。

3.2 布隆过滤器设计

3.2.1 使用什么布隆过滤器

从简单场景开始，选择一个本地布隆过滤器，谷歌的guava库，使用非常简单，且对开发者友好，示例代码如下：

// 只需要两个参数：期望插入记录数，容错率，hash函数个数会自动计算
BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 99999999, 0.01);

// 直接放入对象，对于缓存穿透场景为缓存的key
bloomFilter.put(object);

引入maven依赖：

    <dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>32.1.3-jre</version>
    </dependency>

3.2.2 核心类设计

核心类如下：

布隆过滤器适配Spring Cache及问题与解决策略

类描述
IBloomFilter布隆过滤器接口，没有直接使用谷歌的布隆过滤器，通过接口封装，将来容易替换底层实现。
CombinationBloomFilter有删除功能的布隆过滤器接口，使用时可以决定使用哪一种。
SimpleBloomFilter布隆过滤器实现类，包含了一个谷歌guava库的BloomFilter实例，本类充当代理作用。
SimpleCombinationBloomFilter有删除功能的布隆过滤器实现类，包含两个谷歌guava库的BloomFilter实例，一个记录全量数据，一个记录删除数据（因为布隆过滤器无法删除，所有单独用一个实例来记录删除数据）。
BloomFilter谷歌guava库的布隆过滤器，底层使用的是它。
BloomFilterManager布隆过滤器管理接口，用来获取布隆过滤器，不同的name对应不同的缓存name，例如:"account","customer"，对应两个不同缓存和布隆过滤器。
SimpleBloomFilterManager布隆过滤器管理接口实现类
BloomFilterSpec布隆过滤器参数对象，包括全量布隆过滤器参数和删除布隆过滤器参数。
BloomFilterProperties布隆过滤器属性，除了上述提到的参数集合（以map方式按name存储的参数对象），还包括应用运行的一些其他参数，例如要扫描处理的包名，需要从配置文件读取的文本格式的参数。
BloomFilterAutoConfiguration自动配置类，使得只要引入本库，就可以使用布隆过滤器。

3.2.3 核心代码

3.2.3.1 SimpleBloomFilterManager

布隆过滤器管理类，用于获取布隆过滤器，会根据配置参数识别是否返回有删除功能的布隆过滤器：

public class SimpleBloomFilterManager implements BloomFilterManager {
    private Map<String, IBloomFilter> bloomFilterMap = new ConcurrentHashMap<>();

    private Map<String, BloomFilterSpec> bloomFilterSpecMap;

    public SimpleBloomFilterManager(Map<String, BloomFilterSpec> bloomFilterSpecMap) {
        this.bloomFilterSpecMap = bloomFilterSpecMap;
    }

    @Override
    public IBloomFilter getBloomFilter(String name) {
        if (bloomFilterMap.containsKey(name)) {
            return bloomFilterMap.get(name);
        } else {
            IBloomFilter IBloomFilter = create(name, getBloomFilterSpec(name));
            bloomFilterMap.put(name, IBloomFilter);
            return IBloomFilter;
        }
    }

    @Override
    public String[] getNames() {
        return new String[0];
    }

    private IBloomFilter create(String name, BloomFilterSpec bloomFilterSpec) {
        // 根据配置参数识别是否返回有删除功能的布隆过滤器
        if (bloomFilterSpec.isCombinationFilter()) {
            return new SimpleCombinationBloomFilter(name, getBloomFilterSpec(name));
        } else {
            return new SimpleBloomFilter(name, getBloomFilterSpec(name));
        }
    }

    private BloomFilterSpec getBloomFilterSpec(String name) {
        if (bloomFilterSpecMap.containsKey(name)) {
            return bloomFilterSpecMap.get(name);
        } else {
            return bloomFilterSpecMap.get(Constants.DEFAULT_BLOOM_FILTER_NAME);
        }
    }
}

3.2.3.2 SimpleBloomFilter

全量布隆过滤器。

public class SimpleBloomFilter implements IBloomFilter {

    @Getter
    protected String name;

    protected BloomFilter filter;

    private BloomFilterStatus status = BloomFilterStatus.NEW;

    public SimpleBloomFilter(String name, BloomFilterSpec bloomFilterSpec) {
        this.name = name;
        filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),
                bloomFilterSpec.getExpectedInsertions(),bloomFilterSpec.getFpp());
    }

    @Override
    public boolean mightContain(Object value) {
        return filter.mightContain(value);
    }

    @Override
    public boolean put(Object value) {
        return filter.put(value);
    }

    @Override
    public BloomFilterStatus getStatus() {
        return status;
    }

    @Override
    public void setStatus(BloomFilterStatus status) {
        this.status = status;
    }
}

3.2.3.3 SimpleCombinationBloomFilter

有删除功能的布隆过滤器，继承自SimpleBloomFilter，多了删除相关的操作，内部是双布隆过滤器，一个记录全量数据，一个记录删除数据：

public class SimpleCombinationBloomFilter extends SimpleBloomFilter implements CombinationIBloomFilter {

    private BloomFilter deleteBloomFilter;

    public SimpleCombinationBloomFilter(String name, BloomFilterSpec bloomFilterSpec) {
        super(name, bloomFilterSpec);
        deleteBloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),
                bloomFilterSpec.getExpectedDelInsertions(), bloomFilterSpec.getDelFpp());
    }

    @Override
    public boolean mightContain(Object value) {
        if (super.mightContain(value)) {
            // 已经被删除返回false，否则返回true
            return !deleteBloomFilter.mightContain(value);
        }
        return false;
    }

    @Override
    public boolean delete(Object value) {
        return deleteBloomFilter.put(value);
    }
}

3.2.3.4 BloomFilterAutoConfiguration

自动配置类，使能自动配置启用布隆过滤器能力：

@Log
@ConditionalOnProperty(prefix = "kengcoder.bloomfilter", name = "enabled", havingValue = "true", matchIfMissing = false)
@EnableConfigurationProperties(BloomFilterProperties.class)
public class BloomFilterAutoConfiguration {

    @Bean
    @ConditionalOnMissingBean(BloomFilterScanner.class)
    public BloomFilterScanner bloomFilterScanner(BloomFilterProperties bloomFilterProperties) {
        if (log.isLoggable(Level.INFO)) {
            log.info("Automatically configure kengcoder.bloomfilter");
        }

        BloomFilterScanner.addScannerCheckers(Arrays.asList(new PackageScannerChecker()));
        BloomFilterScanner.addScannablePackages(bloomFilterProperties.getScanPackages());
        BloomFilterScanner.addScannerExcludeBeanNames(bloomFilterProperties.getExcludesForScanning());
        return new BloomFilterScanner();
    }

    @Bean
    @ConditionalOnMissingBean(BloomFilterManager.class)
    public BloomFilterManager bloomFilterManager(BloomFilterProperties bloomFilterProperties) {
        return new SimpleBloomFilterManager(bloomFilterProperties.getBloomFilterSpecMap());
    }
}

对应的配置参数例子：

kengcoder:
  bloomfilter:
    enabled: true # 是否启用布隆过滤器
    scanPackages: com.kengcoder.springawsome.cache.service  # 要扫描使用布隆过滤器的包
    defaultExpectedInsertions: 2000000,20000  # 默认期望插入记录数，前面是全量布隆过滤器，后面是删除布隆过滤器
    defaultFpp: 0.01,0.01 # 默认容错率，前面是全量布隆过滤器，后面是删除布隆过滤器
    expectedInsertionsList: book=2000000,20000;customer=2000000,20000 # 按name配置的希望插入记录数，格式同默认期望插入记录数
    fppList: book=0.01,0.01;customer=0.01,0.01 # 按name配置的容错率，格式同默认容错率

另外要在resources\META-INF\spring目录下的配置文件"org.springframework.boot.autoconfigure.AutoConfiguration.imports"中加入：

com.kengcoder.springawsome.bloomfilter.autoconfigure.BloomFilterAutoConfiguration

3.3 适配Spring Cache

Spring Cache通过注解实现缓存能力，使用起来比较方便，如果能适配Spring Cache缓存注解，那么对于编码方式使用的缓存适配应该更容易。

通过以下用例来验证适配能力，包含增、删、查操作：

    @BloomFilterable
    @Cacheable(cacheNames = {"book"})
    public Book findBook(String bookId) {
        // XXX
    }

    @BloomFilterable
    @Cacheable(cacheNames = {"book"}, key = "#bookId")
    public Book findBookForKey(String bookId) {
        // XXX
    }

    @BloomFilterable
    @Cacheable(cacheNames = {"book"}, keyGenerator = "myKeyGenerator")
    public Book findBookForKeyGenerator(String bookId) {
        // XXX
    }

    @BloomFilterPut
    @CachePut(cacheNames = {"book"}, key = "#book.bookId")
    public Book addBook(Book book) {
        // XXX
    }

    @BloomFilterEvict
    @CacheEvict(cacheNames = {"book"})
    public Book removeBook(String bookId) {
        // XXX
    }

布隆过滤器的注解设计和spring cache注解对应，方便使用。

综合来看有以下关键点要解决：

● spring cache各种缓存key的生成方式要继承过来，以便将key放入布隆过滤器。

● 支持解析spring spel表达式，例如：key = "#book.bookId"。

● 因查询布隆过滤器的步骤要放在最前面，因此要拦截住spring cache注解对应的操作，并让它在布隆过滤器操作执行之后才执行，。

3.3.1 核心类设计

核心类如下：

布隆过滤器适配Spring Cache及问题与解决策略

类描述
BloomFilterable查询数据注解，适配Cacheable注解。
BloomFilterPut插入数据注解，适配CachePut注解。
BloomFilterEvict删除数据注解，适配CacheEvict注解。
InterceptorHandler拦截器，拦截有以上注解的方法做处理。
BloomFilterOperator布隆过滤器操作接口。
AbstractBloomFilterOperator布隆过滤器操作抽象类，提供共性的方法。
BloomFilterableOperator布隆过滤器查询数据操作者，实现查询逻辑。
BloomFilterPutOperator布隆过滤器插入数据操作者，实现插入逻辑。
BloomFilterPutOperator布隆过滤器删除数据操作者，实现删除逻辑。
BloomFilterOperatorRegistry布隆过滤器操作注册器，建立布隆过滤器注解和对应操作者关系，通过注解来查找对应的操作者。

3.3.2 核心代码

3.3.2.1 InterceptorHandler

拦截布隆过滤器注解，根据不同注解获取对应得Operator并调用：

    protected Object doInvoke(InvocationWrapper invocation) throws Throwable {
        Class<?> targetClass = invocation.getTarget().getClass();
        Method specificMethod = ClassUtils.getMostSpecificMethod(invocation.getMethod(), targetClass);

        if (specificMethod != null && !specificMethod.getDeclaringClass().equals(Object.class)) {
            final BloomFilterPut bloomFilterPut = ReflectionUtil.getAnnotation(specificMethod, targetClass, BloomFilterPut.class);
            final BloomFilterable bloomFilterable = ReflectionUtil.getAnnotation(specificMethod, targetClass, BloomFilterable.class);
            final BloomFilterEvict bloomFilterEvict = ReflectionUtil.getAnnotation(specificMethod, targetClass, BloomFilterEvict.class);

            List<Annotation> BloomFilterAnnoList = Arrays.asList(bloomFilterPut, bloomFilterable, bloomFilterEvict);
            // 一个方法只会使用一个注解，取第一个则可
            Optional<Annotation> optionalAnnotation = BloomFilterAnnoList.stream().filter(Objects::nonNull).findFirst();

            // 根据布隆过滤器注解获取对应的Executor，并调用
            if (optionalAnnotation.isPresent()) {
                BloomFilterOperator executor = BloomFilterOperatorRegistry.getExecutor(optionalAnnotation.get().annotationType().getName());
                return executor.execute(specificMethod, targetClass, invocation, beanFactory);
            }
        }
        return invocation.proceed();
    }

3.3.2.2 AbstractBloomFilterOperator

布隆过滤器操作抽象类，负责获取布隆过滤器，生成缓存key这些公共操作：

public abstract class AbstractBloomFilterOperator implements BloomFilterOperator {
    @Override
    public abstract Object execute(Method specificMethod, Class<?> targetClass, InvocationWrapper invocation, BeanFactory beanFactory);

    // 获取布隆过滤器，根据缓存名称获取，注：缓存名称可以设置多个，这里只考虑设置1个的场景。
    protected IBloomFilter getBloomFilter(String[] cacheNames, BeanFactory beanFactory) {
        BloomFilterManager bloomFilterManager = beanFactory.getBean(Constants.BLOOM_FILTER_MANAGER_BEAN, BloomFilterManager.class);
        return bloomFilterManager.getBloomFilter(cacheNames[0]);
    }

    protected Object getKey(String cacheKey, String keyGeneratorBeanName, Method specificMethod,
                          InvocationWrapper invocation, Class<?> targetClass, BeanFactory beanFactory) {
        Object key = null;
        // 通过参数 key = "#bookId"获取
        if (StringUtils.isNotEmpty(cacheKey)) {
            key = getKeyByCacheKey(cacheKey, specificMethod, invocation);

            // 通过参数 keyGenerator = "myKeyGenerator" 获取
        } else if (StringUtils.isNotEmpty(keyGeneratorBeanName)) {
            key = getKeyByGenerator(beanFactory.getBean(keyGeneratorBeanName, KeyGenerator.class), specificMethod, invocation, targetClass);

            // 没有指定key和keyGenerator参数
        } else {
            key = getKeyByGenerator(new SimpleKeyGenerator(), specificMethod, invocation, targetClass);
        }
        return key;
    }

    private Object getKeyByCacheKey(String cacheKey, Method specificMethod, InvocationWrapper invocation) {
        DefaultParameterNameDiscoverer defaultParameterNameDiscoverer = new DefaultParameterNameDiscoverer();
        String[] parameterNames = defaultParameterNameDiscoverer.getParameterNames(specificMethod);

        ExpressionParser parser = new SpelExpressionParser();
        Expression expression = parser.parseExpression(cacheKey);
        StandardEvaluationContext ctx = new StandardEvaluationContext();

        Object[] args = invocation.getArguments();
        // 填充表达式上下文环境
        for(int i=0;i<parameterNames.length;i++){
            ctx.setVariable(parameterNames[i], args[i]);
        }
        return expression.getValue(ctx, Object.class);
    }

    private Object getKeyByGenerator(KeyGenerator keyGenerator, Method specificMethod, InvocationWrapper invocation, Class<?> targetClass) {
        return keyGenerator.generate(targetClass, specificMethod, invocation.getArguments());
    }
}

上面的getKeyByCacheKey方法对spring spel表达式做了解析，要解析如下表达式应该也不是问题：

condition = "#bookId.equals(\"102\")"

unless = "#bookId.equals(\"102\")"

3.3.2.3 BloomFilterableOperator

布隆过滤器查询操作，如果查询到结果则继续处理，否则返回空对象：

public class BloomFilterableOperator extends AbstractBloomFilterOperator {
    @Override
    public Object execute(Method specificMethod, Class<?> targetClass, InvocationWrapper invocation, BeanFactory beanFactory) {
        final Cacheable cacheable = ReflectionUtil.getAnnotation(specificMethod, targetClass, Cacheable.class);
        IBloomFilter bloomFilter = getBloomFilter(cacheable.cacheNames(), beanFactory);
        Object key = getKey(cacheable.key(), cacheable.keyGenerator(), specificMethod, invocation, targetClass, beanFactory);
        // 布隆过滤器存在则继续处理，否则返回null
        if (bloomFilter.mightContain(key)) {
            return invocation.proceed();
        } else {
            // 这里返回什么空对象可以约定好，此处仅用于示例
            return null;
        }
    }
}

3.3.2.4 BloomFilterPutOperator

布隆过滤器插入操作：

public class BloomFilterPutOperator extends AbstractBloomFilterOperator {
    @Override
    public Object execute(Method specificMethod, Class<?> targetClass, InvocationWrapper invocation, BeanFactory beanFactory) {
        final CachePut cachePut = ReflectionUtil.getAnnotation(specificMethod, targetClass, CachePut.class);
        IBloomFilter bloomFilter = getBloomFilter(cachePut.cacheNames(), beanFactory);
        Object key = getKey(cachePut.key(), cachePut.keyGenerator(), specificMethod, invocation, targetClass, beanFactory);
        bloomFilter.put(key);
        return invocation.proceed();
    }
}

3.3.2.5 BloomFilterEvictOperator

布隆过滤器删除操作，需要使用有删除功能的布隆过滤器（可通过配置参数控制，只要多配置2个删除操作的参数就会自动生成有删除功能的布隆过滤器）：

public class BloomFilterEvictOperator extends AbstractBloomFilterOperator {
    @Override
    public Object execute(Method specificMethod, Class<?> targetClass, InvocationWrapper invocation, BeanFactory beanFactory) {
        final CacheEvict cacheEvict = ReflectionUtil.getAnnotation(specificMethod, targetClass, CacheEvict.class);
        IBloomFilter bloomFilter = getBloomFilter(cacheEvict.cacheNames(), beanFactory);
        Object key = getKey(cacheEvict.key(), cacheEvict.keyGenerator(), specificMethod, invocation, targetClass, beanFactory);
        ((SimpleCombinationBloomFilter)bloomFilter).delete(key);
        return invocation.proceed();
    }
}

3.3.2.6 BloomFilterOperatorRegistry

注册布隆过滤器操作者，使用时通过布隆过滤器注解获取对应的操作者：

public class BloomFilterOperatorRegistry {
    private static Map<String, BloomFilterOperator> executorMap = new HashMap<>();

    static {
        register(BloomFilterable.class.getName(), new BloomFilterableOperator());
        register(BloomFilterPut.class.getName(), new BloomFilterPutOperator());
        register(BloomFilterEvict.class.getName(), new BloomFilterEvictOperator());
    }

    public static BloomFilterOperator getExecutor(String name) {
        return executorMap.get(name);
    }

    private static void register(String name, BloomFilterOperator executor) {
        executorMap.put(name, executor);
    }
}

3.3.3 拦截Spring cache注解操作

布隆过滤器拦截器的执行优先级要高于spring cache拦截器才能达到此目的。

3.3.3.1 Spring cache拦截器执行顺序

在ProxyCachingConfiguration.java中从EnableCaching注解获取：

        if (this.enableCaching != null) {
            advisor.setOrder(this.enableCaching.<Integer>getNumber("order"));
        }

注：这里如果找不到enableCaching注解，默认优先级是: Ordered.LOWEST_PRECEDENCE。

EnableCaching注解默认值:

public @interface EnableCaching {
	int order() default Ordered.LOWEST_PRECEDENCE;
}

常量定义：

Ordered.java

	int LOWEST_PRECEDENCE = Integer.MAX_VALUE;

因此如果不改变EnableCaching的order参数，布隆过滤器的order只要小于Integer.MAX_VALUE则可（越小优先级越高），保险起见，也可以显示定义一个常量设置EnableCaching的order参数，哪怕取值还是Integer.MAX_VALUE，然后将布隆过滤器的order参数定义为该值减1，这样无论EnableCaching的优先级常量怎么修改都不会有问题。

3.3.3.2 布隆过滤器拦截器优先级处理

上个小节提到了order的取值设置要小于spring cache中EnableCaching注解order属性取值，另外为了让order生效，取决拦截器是怎么实现的，例如：

● 如果继承自AbstractPointcutAdvisor，调用setOrder方法则可。

● 如果是实现MethodInterceptor接口，那么同时还要实现Ordered接口的getOrder方法来返回优先级。

具体代码这里不再赘述。

3.4 验证

3.4.1 验证代码

验证代码就是一般的结构Controller + Service + DAO。

3.4.1.1 BookController

@Component
@RestController
@RequestMapping(method = {RequestMethod.GET})
public class BookController {

    @Autowired
    private BookService bookService;

    @RequestMapping("/findBook")
    public Book findBook(@RequestBody String bookId) {
        Book book = bookService.findBook(bookId);
        return book;
    }

    @RequestMapping("/findBookForKeyGenerator")
    public Book findBookForKeyGenerator(@RequestBody String bookId) {
        Book book = bookService.findBookForKeyGenerator(bookId);
        return book;
    }

    @RequestMapping("/findBookForKey")
    public Book findBookForKey(@RequestBody String bookId) {
        Book book = bookService.findBookForKey(bookId);
        return book;
    }

    @RequestMapping("/addBook")
    public String addBook(@RequestBody Book book) {
        bookService.addBook(book);
        return "add book [" + book.getBookId() + "] success.";
    }

    @RequestMapping("/removeBook")
    public String removeBook(@RequestBody String bookId) {
        bookService.removeBook(bookId);
        return "remove book [" + bookId + "] success.";
    }
}

3.4.1.2 BookService

@Service
public class BookService {

    @BloomFilterable
    @Cacheable(cacheNames = {"book"})
    public Book findBook(String bookId) {
        log("findBook", bookId);
        Book book = MockBookDB.findBook(bookId);
        log(book);
        return book;
    }

    @BloomFilterable
    @Cacheable(cacheNames = {"book"}, key = "#bookId")
    public Book findBookForKey(String bookId) {
        log("findBookForKey", bookId);
        Book book = MockBookDB.findBook(bookId);
        log(book);
        return book;
    }

    @BloomFilterable
    @Cacheable(cacheNames = {"book"}, keyGenerator = "myKeyGenerator")
    public Book findBookForKeyGenerator(String bookId) {
        log("findBookForKeyGenerator", bookId);
        Book book = MockBookDB.findBook(bookId);
        log(book);
        return book;
    }

    @BloomFilterPut
    @CachePut(cacheNames = {"book"}, key = "#book.bookId")
    public Book addBook(Book book) {
        log("addBook", book.getBookId());
        MockBookDB.addBook(book);
        log(book);
        // 这里要返回结果才会添加到缓存中
        return book;
    }

    @BloomFilterEvict
    @CacheEvict(cacheNames = {"book"})
    public Book removeBook(String bookId) {
        log("removeBook", bookId);
        Book book = MockBookDB.removeBook(bookId);
        log(book);
        return book;
    }
}

3.4.1.3 MockBookDB

这里已经内置了一些数据：

public class MockBookDB {
    private static Map<String, Book> bookMap = new ConcurrentHashMap<>();

    static {
        addBook(new Book("101", "架构整洁之道", "罗伯特C. 马丁"));
        addBook(new Book("102", "重构", "马丁·福勒"));
        addBook(new Book("103", "分析模式", "马丁·福勒"));
    }

    public static Book findBook(String bookId) {
        return bookMap.get(bookId);
    }

    public static void addBook(Book book) {
        bookMap.put(book.getBookId(), book);
    }

    public static Book removeBook(String bookId) {
        return bookMap.remove(bookId);
    }
}

3.4.2 验证过程

3.4.2.1 查询DB里有的书

前面提到，使用布隆过滤器要先加载全量数据到布隆过滤器里，当前我们没有实现这个功能，所以此时查询会返回空结果（因为优先查询布隆过滤器，没有则直接返回空结果）。

发起请求：

http://localhost:8080/findBookForKey

请求bookId：103

拦截到BloomFilterable获取到相应的Operator：

布隆过滤器适配Spring Cache及问题与解决策略

Operator执行，因为布隆过滤器没有数据，会走到返回空结果分支：

布隆过滤器适配Spring Cache及问题与解决策略

请求结果也返回null。

3.4.2.2 添加一本新书

此时会写入布隆过滤器、缓存、数据库。

发起请求：

http://localhost:8080/addBook

请求数据：

{
  "bookId": "104",
  "name": "代码整洁之道",
  "author": "罗伯特·C·马丁"
}

查找到对应Operator将数据添加到布隆过滤器中：

布隆过滤器适配Spring Cache及问题与解决策略

之后才存入缓存，证明拦截器顺序有效：

布隆过滤器适配Spring Cache及问题与解决策略

3.4.2.3 查询刚添加的新书

此场景为模拟布隆过滤器已经加载数据。

发起请求：

http://localhost:8080/findBookForKey

请求bookId：104

这一次布隆过滤器查找到了数据，继续调用业务方法：

布隆过滤器适配Spring Cache及问题与解决策略

接着从缓存查询数据：

布隆过滤器适配Spring Cache及问题与解决策略

返回正确结果:

{
    "bookId": "104",
    "name": "代码整洁之道",
    "author": "罗伯特·C·马丁"
}

3.4.2.4 删除刚添加的新书后查询

因为这里的布隆过滤器支持删除，删除后再查询则不会去查询缓存和数据库，直接返回null。

发起删除请求：

http://localhost:8080/removeBook

请求bookId：104

从布隆过滤器删除数据：

布隆过滤器适配Spring Cache及问题与解决策略

接着从缓存删除数据，再次证明拦截器顺序有效：

布隆过滤器适配Spring Cache及问题与解决策略

发起查询请求：

http://localhost:8080/findBookForKey

请求bookId：104

可以看到全量布隆过滤器有数据：

布隆过滤器适配Spring Cache及问题与解决策略

删除过滤器也有数据，因此上面代码片段会返回false：

布隆过滤器适配Spring Cache及问题与解决策略

最后走到空结果分支，也不会从缓存查询数据：

布隆过滤器适配Spring Cache及问题与解决策略

至此，所有用例验证完毕，结果符合预期，落地方案基本可行。

4. 布隆过滤器问题和应对策略

上面已经对布隆过滤器落地方案做了基本验证，要真正使用还要分析可能存在的问题并制定应对策略。

4.1 查询数据

4.1.1 布隆过滤器数据还在加载中

● 场景

应用每次启动时，布隆过滤器数据加载需要时间，未加载完成时有服务请求。

● 影响

布隆过滤器数据不全，如果使用会导致误判数据不存在，返回空结果。

● 解决策略

1.布隆过滤器做预加载，等加载完成后再使用对应服务，缺点是服务ready有一定时间，完成前不能使用服务，优点是一旦提供服务，就能避免恶意攻击。

2.布隆过滤器数据加载过程中也放开服务，同时布隆过滤器增加状态，加载完成后切换状态，并开始使用布隆过滤器，缺点是布隆过滤器加载期间，服务可能会收到恶意攻击影响，优点是可以尽快提供服务。

3.服务请求增加动态限流控制，缓解上述策略2的问题，如果识别到恶意攻击则限流，否则不做处理。

4.增加攻击难度，例如登陆后才能使用服务，查询key有内置规则，如ID第5位固定为3等等，在查询前先校验规则是否满足。但这些方法不能解决根本问题，也不是所有场景都适用。

4.1.2 数据不一致

● 场景

布隆过滤器和缓存数据不一致。

● 影响

布隆过滤器数据多，则多出来的数据会导致缓存穿透。

布隆过滤器数据少，则会影响部分请求无法正常返回结果。

● 解决策略

1.定期全量比对数据并同步更新，同时布隆过滤器要支持删除操作，解决由于删除操作导致布隆过滤器数据多的问题。

2.记录布隆过滤器未命中数据，自动异步比对缓存并刷新，为了防止恶意攻击，刷新队列为有界队列，超出就丢弃，在非恶意攻击场景下无效查询并不会很多，能有效解决正常场景的不一致问题。

3.提供手动精确同步能力，在应对客户重大紧急投诉情况下发起。

4.暂时挂起布隆过滤器，此为应对极端场景，大量客户投诉必须立即解决，但同时要评估恶意攻击的影响。一般情况下不建议这么做，可以尝试通过策略3解决，两者区别是要实现策略3的能力研发代价较大。

4.2 新增数据

主要问题是数据不一致，导致后期查询数据出现问题，解决策略为保证布隆过滤器和缓存操作的可靠性，和事务一致性。

4.3 更新数据

可能存在的问题是key值被修改，解决策略是要先删除后写入，同时布隆过滤器要支持删除操作。

数据不一致也可能存在，解决策略同前所述。

4.4 删除数据

4.4.1 布隆过滤器有缓存无

● 场景

删除数据，布隆过滤器不支持删除操作，导致数据比缓存多。

● 影响

多出来的数据如果发起查询导致缓存穿透。

● 解决策略

1.布隆过滤器支持删除操作。

2.在容忍范围内不需要解决，比如对于删除数据，用户不会再发起查询，其次即使发起查询，占总量比例也很小，影响可控。

4.4.2 先删后增

● 场景

通用的数据（key值相同），先删除了然后增，而布隆过滤器支持删除操作，已经记录了数据被删除。

● 影响

删除后增加的数据由于已经在布隆过滤器删除记录中，查询时无法返回结果。

● 解决策略

1.清除“有删除记录的布隆过滤器”，同时全量刷新布隆过滤器，保证数据是最新的。两者也可以结合起来用，“有删除记录的布隆过滤器”继续使用，同时定期刷新布隆过滤器，刷新完成后就清除“删除记录过滤器”，不过在过程中会有新的删除记录不应该被从布隆过滤器删除，这部分会有少量的缓存穿透。

2.再增加一个删/增记录布隆过滤器，优先级最高，先判断这个，然后是删除记录布隆过滤器，然后是全量布隆过滤器，此方法不能根本解决多次重复删除新增的问题，并且相关同步逻辑有些复杂，不建议使用此策略。

4.5 文章开头提到的共性问题

4.5.1 误判率

● 问题

布隆过滤器可能会错误地判断某个不存在集合中的元素为存在。

● 策略

这个没法避免，误判率和布隆过滤器大小，实际要存储的数据有关系，能做的是增大布隆过滤器可存储记录数，从而减小误判率，使得在可接受范围内。

4.5.2 无法删除元素

● 问题

布隆过滤器不支持从集合中删除元素。这是因为删除元素需要清除某些位，但这可能会影响到其他元素。存在一些布隆过滤器的变体，如计数布隆过滤器，可以支持删除操作，但这会增加复杂性和空间需求。

● 策略

无法删除导致的结果就是数据删除了，布隆过滤器还存在，导致误判，引起缓存穿透，另外还包括反复删除/增加相同key值数据的场景，这些在前面问题列表中已分析。

4.5.3 固定大小

● 问题

布隆过滤器在创建时需要确定大小。如果预估的元素数量过小，会导致高误判率；如果过大，则会浪费空间。动态调整布隆过滤器的大小不是一个简单的任务。

● 策略

只能参考实际业务量来评估，这个问题在评估数据库存储空间时同样存在，依赖评估算法和经验。

4.5.4 无法确定元素是否一定不存在

● 问题

虽然布隆过滤器可以告诉你一个元素可能存在于集合中，但它不能确定地告诉你一个元素一定不在集合中。

● 策略

这是因为两个对象hash计算后得到的位置信息一致，一个确实存在，一个可能并不存在，但因为位置信息一致，都认为存在。

这种情况没法避免，即使初始化时降低误判率也不能完全避免，只要误判率在可接受范围内就可以。

4.5.5 优化参数需要

● 问题

选择合适的哈希函数和确定布隆过滤器的大小需要根据具体应用场景进行优化，这可能需要一定的经验和实验。

● 策略

一般情况下，合适的hash函数交给专业的人去设计，只要使用则好（例如guava根据大小和误判率自行选择hash函数），对于大小问题前面已经描述。

4.5.6 不提供数据存储

● 问题

布隆过滤器只能告诉你某个元素可能在集合中，但它不存储任何关于元素本身的信息。

● 策略

对于使用场景来说，这点应该不算是问题，需要元素本身的信息就从缓存或数据库查询。

4.6 应对策略总体原则

● 优先解决必然会出问题的场景

例如某个场景无法正常返回数据，那么就需要解决，如果某个操作只是冗余操作，并不影响业务，可以根据实际情况决定是否解决。

● 布隆过滤器的删除能力不是必须

不是所有场景都要支持有删除能力的布隆过滤器，如果删除操作本身非常少，影响到的缓存穿透占比也很少，在可接受范围内，那么可以不支持。

● 与其他手段结合

与其他手段一起结合解决恶意攻击，例如动态限流，熔断，通过细分场景找到合适的方案。

5. 总结

本文基于缓存穿透业务场景，结合基本用例，验证了如何使用布隆过滤器，并适配spring cache的MVP，同时分析了存在的问题和解决策略，为后续在实际业务中使用布隆过滤器提供参考，核心内容包括：

● 谷歌guava库的布隆过滤器简单易用，可以直接上手。

● 布隆过滤器的基本设计和使用，包括有删除能力的布隆过滤器，可以通过组合的方式支持删除能力。

● 适配spring cache的思路，解析注解的spel表达式，端到端打通过程。

● 布隆过滤器的问题解决策略，依赖实际业务场景和容忍度来选择，并非所有问题都要解决。

6. 思考

● 能不能直接拦截spring cache的cache操作？

● 通常缓存都有失效时间，对于这种缓存失效场景布隆过滤器要如何处理？

● 带计数能力的布隆过滤器用来支持删除操作，是否比本文提到的通过额外布隆过滤器实例来记录删除数据更好？

● 分布式场景下应该如何适配？

其他阅读：