面试官：什么是布隆过滤器？如何解决高并发缓存穿透问题？

布隆过滤器是一种空间效率高的概率型数据结构，用于快速判断元素是否在集合中；解决高并发缓存穿透可通过布隆过滤器预先过滤无效请求，避免数据库压力。

• 定义：布隆过滤器由二进制向量和多个哈希函数组成，用于检索元素是否在集合中。其核心原理是通过哈希函数将元素映射到二进制数组的多个位置，并将这些位置标记为1。
  

• 优点：

  空间效率高：相比传统数据结构（如哈希表），布隆过滤器以极低的内存占用实现高效检索。

  查询速度快：哈希函数计算和数组访问均为常数时间复杂度（O(1)）。

• 缺点：

  存在误判率：可能将不存在的元素误判为存在（但不会漏判）。

  删除困难：直接删除元素可能导致误删其他元素的哈希冲突位置。

1. 构建过程：

   初始化一个长度为n的二进制数组，所有位初始化为0。

   对每个元素，通过k个哈希函数计算其在数组中的k个位置，并将这些位置的值设为1。

   示例：对商品ID id1，哈希函数计算得到位置2、5、8，将数组对应位置设为1。

   

2. 查询过程：

   对查询元素，通过相同的k个哈希函数计算k个位置。

   若所有位置的值均为1，则元素可能存在；若任一位置为0，则元素一定不存在。

   示例：查询商品ID时，若三个哈希位置中有一个为0，则直接返回不存在。

   

1. 缓存穿透问题：

   现象：大量请求查询缓存中不存在的数据，导致请求直接穿透到数据库，引发数据库压力激增甚至崩溃。

   原因：恶意攻击或业务逻辑缺陷导致频繁查询无效数据。

2. 布隆过滤器的解决方案：

   预过滤机制：在缓存层前部署布隆过滤器，将所有可能存在的数据ID预先存入过滤器。

   拦截无效请求：查询缓存前，先通过布隆过滤器判断数据是否存在。若不存在，直接返回空结果，避免数据库查询。

   流程优化：

   缓存未命中时，先查询布隆过滤器。

   若过滤器返回不存在，直接终止请求；若可能存在，再查询数据库并更新缓存。

3. 误判率控制：

   参数调整：

   增加二进制数组长度（n）：降低哈希冲突概率，减少误判。

   增加哈希函数数量（k）：提高元素特征维度，进一步降低冲突。

   权衡点：误判率设置过小会导致性能下降（哈希计算次数增加），通常建议误判率为1%。

1. 内存占用分析：

   实验表明，存储1000万数据时，布隆过滤器仅需约1.19MB内存（计算公式：10000000/8/1024/1024≈1.19MB）。

   相比传统数据结构，内存效率显著提升。

2. Java实现示例：

   使用Redisson框架的RBloomFilter：

   Config config = new Config();config.useSingleServer().setAddress("redis://172.16.67.37:6379");RedissonClient client = Redisson.create(config);RBloomFilter<String> bloomFilter = client.getBloomFilter("test-filter");bloomFilter.tryInit(1000000L, 0.01); // 初始化：100万数据，1%误判率bloomFilter.add("Tom哥");System.out.println(bloomFilter.contains("微观技术")); // 输出falseSystem.out.println(bloomFilter.contains("Tom哥")); // 输出true

3. 删除操作处理：

   方案1：定时重建过滤器（类似CopyOnWrite机制），定期生成新过滤器替换旧过滤器。

   方案2：使用计数布隆过滤器，通过维护等长计数器数组解决冲突问题（删除时计数器减一，归零后更新主数组）。

4. 典型应用场景：

   缓存穿透防护：拦截无效请求，保护数据库。

   爬虫URL去重：避免重复爬取相同URL。

   反垃圾邮件：快速判断邮箱是否在垃圾邮件列表中。

布隆过滤器通过空间换时间的策略，以极低的内存占用和高效的查询性能，成为解决高并发缓存穿透问题的理想工具。在实际应用中，需根据业务需求调整误判率、数组长度和哈希函数数量，并在删除操作时选择合适的维护方案（如定时重建或计数器扩展）。