布隆过滤器（BloomFilter）简介和使用

布隆过滤器介绍

Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员。如果检测结果为true，该元素不一定在集合中；但如果检测结果为false，该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况，可见 Bloom filter 是牺牲了正确率和时间以节省空间。

优缺点

• 插入和查询元素很快
• 空间占用小（因为布隆过滤器是不存储元素本身的）
• 不能删除元素
• 存在误判概率（在集合内可能错误，但是不在集合内就是真的不在）

应用场景

• 网页爬虫对URL的去重，避免爬取相同的URL地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（同理，垃圾短信）；
• 缓存穿透，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。

Java中使用

Google的提供的Guava库中已经实现了BloomFilter，我们可以直接使用Guava的实现，参见：https://guava.dev/releases/20.0/api/docs/com/google/common/hash/BloomFilter.html

下面是使用示例：

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

import java.nio.charset.StandardCharsets;

/**
 * @author 码农俱乐部 https://mlog.club
 */
public class BloomFilterTest {
    /**
     * 预计元素数量
     */
    private static final int EXPECTED_INSERTIONS = 1000000; // 100w

    public static void main(String[] args) {
        BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), EXPECTED_INSERTIONS);

        // 插入元素
        for (int i = 0; i < EXPECTED_INSERTIONS; i++) {
            filter.put(String.valueOf(i));
        }

        // 判断是否存在
        boolean mightContain = filter.mightContain("1");
        System.out.println(mightContain);
    }
}

在Redis中使用BloomFilter

上面我们介绍了在Guava中如何使用BloomFilter，但是在Guava中使用有一个缺点：占用JVM内存。Guava的实现是将所有的数据放入到内存中的，应用重启内存中的数据都会丢失。

不用担心，贴心的Redis已经帮我们实现了BloomFilter，下面我们介绍下如何在Redis中使用BloomFilter。

Redisson是Java中快速、轻量Redis客户端。下面我们通过Redisson来调用Redis的BloomFilter。

RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// initialize Bloom filter with 
// expectedInsertions = 55000000
// falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
bloomFilter.count();

Redisson还支持Redis中的分布式布隆过滤器RClusteredBloomFilter。RClusteredBloomFilter内存效率更高，缩小了所有Redis节点占用的内存。请注意RClusteredBloomFilter只能在Redisson的集群模式下使用。

下面我们来看下RClusteredBloomFilter的使用示例：

RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");
// initialize Bloom filter with 
// expectedInsertions = 255000000
// falseProbability = 0.03
bloomFilter.tryInit(255000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));

本文由码农俱乐部原创，转载请在文章内容中明显位置注明出处，本文链接：https://mlog.club/topic/688