BloomFilter - 布隆过滤器

快来打我* 2024-03-23 14:32 43阅读 0赞

## 1、BloomFilter ##

1.1 创建一个容量为 100000 个元素、误判率为 0.05（即在检查成员资格时有 5% 的概率出现误判）的 Bloom 过滤器。  
1.2 生成 100000 个随机的 UUID 字符串，并将它们添加到一个列表中。  
1.3 对于列表中的每个 UUID 字符串，使用 mightContain() 方法来检查其是否在 Bloom 过滤器中存在，输出检查结果。

public class MyBloom {
        
        public static void main(String[] args) {
        
            // 创建一个容量为 100000 个元素、误判率为 0.05（即在检查成员资格时有 5% 的概率出现误判）的 Bloom 过滤器。
            // 对于大多数应用场景来说，Bloom 过滤器的误判率一般会被控制在 1% ~ 5% 之间。
            // 如果误判率太高，那么过滤器的效果就会受到影响，如果误判率太低，那么空间和时间的开销就会变得不划算。
            BloomFilter filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 100000, 0.05);
            List<String> ids = new ArrayList<>();
    
            // 生成 100000 个随机的 UUID 字符串，并将它们添加到一个列表中。
            IntStream.rangeClosed(1, 100000).forEach(index -> {
        
                String id = UUID.randomUUID().toString();
                ids.add(id);
                // 使用 put() 方法将每个 UUID 字符串插入到 Bloom 过滤器中。
                filter.put(id);
            });
    
            ids.forEach(id -> {
        
                // 对于列表中的每个 UUID 字符串，使用 mightContain() 方法来检查其是否在 Bloom 过滤器中存在，输出检查结果。
                // 在正常情况下，所有的检查结果都应该是 false，但是由于误判率的存在，约有 5% 的检查结果会是 true。
                System.out.println(id + ":" + filter.mightContain(id + 1));
            });
        }
    }

## 2、防止缓存穿透 ##

当布隆过滤器中可能存在该元素时，会从缓存中获取结果并返回；否则会查询数据库，并将查询结果放入缓存中。同时，每次将元素添加到布隆过滤器时，也会将元素添加到缓存中。这样就能够防止缓存穿透，同时也能够保证缓存命中率的高效使用。  
2.1 使用 ThreadPoolExecutor 来模拟并发插入元素  
2.2 在多线程环境下并发检查元素

/**
     * 当布隆过滤器中可能存在该元素时，会从缓存中获取结果并返回；否则会查询数据库，并将查询结果放入缓存中。
     * 同时，每次将元素添加到布隆过滤器时，也会将元素添加到缓存中。这样就能够防止缓存穿透，同时也能够保证缓存命中率的高效使用。
     * @author Administrator
     */
    public class MyBloomFilter {
        
        public static void main(String[] args) throws Exception {
        
            int dataSize = 1000000;
            double falsePositiveRate = 0.01;
            BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), dataSize, falsePositiveRate);
    
            // 使用 ThreadPoolExecutor 来并发插入元素
            int threadPoolSize = 4;
            ThreadPoolExecutor executor = new ThreadPoolExecutor(
                    threadPoolSize, threadPoolSize,
                    0L, TimeUnit.MILLISECONDS,
                    new LinkedBlockingQueue<>());
            List<CompletableFuture<Void>> futures = new ArrayList<>();
            for (int i = 0; i < dataSize; i++) {
        
                final String element = UUID.randomUUID().toString();
                // 如果布隆过滤器中不存在该元素，则查询数据库并将查询结果放入缓存,将元素添加到布隆过滤器中
                // ...
                futures.add(CompletableFuture.runAsync(() -> filter.put(element), executor));
            }
            // 参数是一个具体大小的 CompletableFuture 数组，其中 futures.size() 是数组大小。
            // 这样做的缺点是需要多一次计算数组大小的开销，并且可能会导致数组容量过大或过小。
            // CompletableFuture.allOf(futures.toArray(new CompletableFuture[futures.size()])).join();
            // 参数是一个零长度的 CompletableFuture 数组。这样做的优点是可以省略数组大小的计算，且不会产生过大或过小的数组。编译器会根据传入参数的类型推断数组大小。
             CompletableFuture.allOf(futures.toArray(new CompletableFuture[0])).join();
    
    
            // 在多线程环境下并发检查元素
            List<String> queryList = IntStream.rangeClosed(1, dataSize / 10)
                    .mapToObj(i -> UUID.randomUUID().toString())
                    .collect(Collectors.toList());
            futures = new ArrayList<>();
            for (String element : queryList) {
        
                // 如果布隆过滤器中可能存在该元素，则从缓存中获取结果并返回
                futures.add(CompletableFuture.supplyAsync(() -> filter.mightContain(element), executor)
                        .thenAccept(result -> System.out.println(element + ": " + result)));
            }
            // CompletableFuture.allOf(futures.toArray(new CompletableFuture[futures.size()])) .join();
            CompletableFuture.allOf(futures.toArray(new CompletableFuture[0])) .join();
    
            executor.shutdown();
        }
    }