布隆过滤器(BloomFilter)简介和使用

0 / 98

布隆过滤器介绍

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 中的分布式布隆过滤器RClusteredBloomFilterRClusteredBloomFilter内存效率更高,缩小了所有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

    公众号
    码农俱乐部
    关注公众号订阅更多技术干货!