布隆过滤器原理与实战：从入门到面试 ⭐⭐⭐

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterDemo {

    public static void main(String[] args) {
        // 创建一个预期插入 1000 个元素的布隆过滤器，期望误判率为 0.01 (1%)
        BloomFilter<String> bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(Charsets.UTF_8),
            1000,          // 预期插入数量
            0.01           // 期望误判率
        );

        // 添加元素
        bloomFilter.put("https://www.example.com/page1");
        bloomFilter.put("https://www.example.com/page2");
        bloomFilter.put("https://www.example.com/page3");

        // 检查元素
        System.out.println(bloomFilter.mightContain("https://www.example.com/page1")); // true
        System.out.println(bloomFilter.mightContain("https://www.example.com/page4")); // false 或 true（误判）
        System.out.println(bloomFilter.mightContain("not-exists")); // false（确定不存在）
    }
}

import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
import java.util.List;

@Service
public class BloomFilterService {

    private final RedisTemplate<String, String> redisTemplate;
    private static final String BLOOM_FILTER_KEY = "bloom:urls";

    public BloomFilterService(RedisTemplate<String, String> redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    /**
     * 添加 URL 到布隆过滤器
     */
    public void addUrl(String url) {
        redisTemplate.opsForValue().setBit(BLOOM_FILTER_KEY, generateBitIndex(url), true);
    }

    /**
     * 批量添加 URL
     */
    public void addUrls(List<String> urls) {
        urls.forEach(this::addUrl);
    }

    /**
     * 检查 URL 是否可能存在于过滤器中
     */
    public boolean mightContain(String url) {
        long bitIndex = generateBitIndex(url);
        Boolean result = redisTemplate.opsForValue().getBit(BLOOM_FILTER_KEY, bitIndex);
        return Boolean.TRUE.equals(result);
    }

    /**
     * 生成位数组索引（简化版本，实际生产中应使用多个哈希函数）
     */
    private long generateBitIndex(String url) {
        int hash = url.hashCode();
        return Math.abs(hash);
    }
}

@Service
public class ProductService {

    private final RedisTemplate<String, Object> redisTemplate;
    private final String BLOOM_FILTER_KEY = "bloom:product:ids";

    public ProductService(RedisTemplate<String, Object> redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    /**
     * 查询商品详情
     * 解决缓存穿透的核心逻辑：
     * 1. 先查布隆过滤器，如果返回不存在 → 直接返回 null（不查数据库）
     * 2. 如果返回可能存在 → 继续查 Redis 缓存
     * 3. 如果缓存未命中 → 查数据库
     */
    public Product getProduct(Long productId) {
        // 步骤1：布隆过滤器检查
        if (!bloomFilterMightContain(productId)) {
            // 布隆过滤器明确返回不存在，直接返回
            return null;
        }

        // 步骤2：查 Redis 缓存
        String cacheKey = "product:" + productId;
        Product cached = (Product) redisTemplate.opsForValue().get(cacheKey);
        if (cached != null) {
            return cached;
        }

        // 步骤3：查数据库
        Product product = productMapper.selectById(productId);

        // 步骤4：写缓存
        if (product != null) {
            redisTemplate.opsForValue().set(cacheKey, product, 1, TimeUnit.HOURS);
        }

        return product;
    }

    /**
     * 添加商品时同步更新布隆过滤器
     */
    public void addProduct(Product product) {
        productMapper.insert(product);
        // 添加商品后，将商品ID加入布隆过滤器
        addToBloomFilter(product.getId());
    }

    private boolean bloomFilterMightContain(Long productId) {
        // 调用 Redis 的 BF.EXISTS 命令
        return Boolean.TRUE.equals(
            redisTemplate.execute(new RedisCallback<Boolean>() {
                @Override
                public Boolean doInRedis(RedisConnection connection) throws DataAccessException {
                    return connection.commands().bFExists(
                        BLOOM_FILTER_KEY.getBytes(),
                        String.valueOf(productId).getBytes()
                    ) == 1;
                }
            })
        );
    }

    private void addToBloomFilter(Long productId) {
        redisTemplate.execute(new RedisCallback<Void>() {
            @Override
            public Void doInRedis(RedisConnection connection) throws DataAccessException {
                connection.commands().bFAdd(
                    BLOOM_FILTER_KEY.getBytes(),
                    String.valueOf(productId).getBytes()
                );
                return null;
            }
        });
    }
}

public class DistributedBloomFilter {

    private final List<String> redisNodes; // Redis 节点列表
    private final int nodeCount;

    public DistributedBloomFilter(List<String> redisNodes) {
        this.redisNodes = redisNodes;
        this.nodeCount = redisNodes.size();
    }

    /**
     * 根据 URL 的哈希值选择对应的 Redis 节点
     */
    private String getNodeForUrl(String url) {
        int hashCode = url.hashCode();
        int index = Math.abs(hashCode % nodeCount);
        return redisNodes.get(index);
    }

    public void addUrl(String url) {
        String node = getNodeForUrl(url);
        // 调用对应节点的 BF.ADD 命令
        redisTemplate.getConnectionFactory()
            .getConnection(node)
            .bfAdd(("bloom:" + node).getBytes(), url.getBytes());
    }

    public boolean mightContain(String url) {
        String node = getNodeForUrl(url);
        return redisTemplate.getConnectionFactory()
            .getConnection(node)
            .bfExists(("bloom:" + node).getBytes(), url.getBytes());
    }
}

Jedis jedis = new Jedis("localhost", 6379);
// 添加
jedis.bfAdd("bloom:users", "user123");
// 检查
boolean exists = jedis.bfExists("bloom:users", "user123") == 1;
// 批量添加
List<String> items = Arrays.asList("a", "b", "c");
jedis.bfMAdd("bloom:users", items.stream()
    .map(SafeEncoder::encode)
    .toArray(byte[][]::new));