布隆过滤器：提高效率与降低成本的秘密

方宣宙

一、背景介绍二、认识布隆过滤器2.1布隆过滤器简介2.2优点2.3缺点2.4适用场景三、布隆过滤器原理3.1结构3.2添加元素3.3查询元素四、布隆过滤器误判率4.1参数4.2推导过程4.3误判率公式五、实现方式5.1Guava实现5.2Redis实现六、布隆过滤器商业运用6.1业务场景6.2布隆过滤器选择6.3使用布隆过滤器效果一、背景介绍在互联网中，我们经常遇到需要在大量数据中判断目标数据是否存在的情况。例如，在网络爬虫中，我们需要判断某个网址是否已经被访问过。为了实现这一功能，通常需要使用一个容器来存储已访问过的网址。如果将这些数据直接存储在磁盘中，每次判断都要进行磁盘查询，这将导致大量的IO操作，效率较低。因此，我们希望将这些数据保存在内存中。在数据量较小的情况下，可以使用Redis来存储这些数据。但是，当数据量超过上千万时，将会消耗几GB甚至几十GB的内存空间。然而，对于仅需要记录数据是否存在的情况而言，这样使用大量内存显然是浪费的。为了解决这个问题，我们可以使用布隆过滤器(BloomFilter)。布隆过滤器是一种占用空间少且时间效率高的工具。二、认识布隆过滤器2.1布隆过滤器简介布隆过滤器（BloomFilter）是1970年由布隆提出的，它实质上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。作用：它是一个空间效率高的概率型数据结构，用来告诉你:一个元素一定不存在或者可能存在。2.2优点相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（即hash函数的个数）。Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。布隆过滤器可以表示全集，其它任何数据结构都不能。2.3缺点有误判率存在。不支持删除。2.4适用场景预防缓存穿透：布隆过滤器快速判断数据是否存在，避免通过查询数据库来判断数据是否存在。网络爬虫：布隆过滤器可以用来去重已经爬取过的URL。邮箱的垃圾邮件过滤。黑白名单。三、布隆过滤器原理3.1结构布隆过滤器实现原理就是一个超大位数的数组和多个不同Hash算法函数。假设位数组的长度为m，哈希函数的个数为k。如下图，一个长度16位的数组，3个不同Hash算法函数，数组里面存储的是bit位，只放0和1，初始为0。不同Hash算法函数指定长度数组3.2添加元素将要添加的元素分别通过k个哈希函数计算得到k个哈希值，这k个hash值对应位数组上的k个位置，然后将这k个位置设置为1。我们添加一个data1和data2两个元素，两个元素根据三个hash算法函数计算出的值，需要说明一点三个值可能会存在相同的值。其中data1计算出1、8、13三值，我们把数组中对应的位置设置为1。Hash1(data1)=1Hash2(data1)=8Hash3(data1)=13如图：data2计算出2、5、13三值，我们把数组中对应的位置设置为1Hash1(data2)=2Hash2(data2)=5Hash3(data2)=13如图：我们发现data1和data2经过hash函数后，出现了一个相同值，这种是正常的，也正是因为这种情况的存在，需要多个函数来保证每个元素尽可能对应数组位置的唯一性，可以看下两个元素在一起的效果。如图：当不同元素在不同或者相同的hash函数计算后，得到同一个值，依旧只需要这个位置保持1即可。3.3查询元素将要查询的元素分别通过k个哈希函数计算得到k个哈希值，这k个hash值对应位数组上的k个位置。如果这k个位置中有一个位置为0，则此元素一定不存在集合中。如果这k个位置全部为1，则这个元素可能存在。我们在刚才添加过data1和data2两个元素的布隆过滤器查询以下三种元素，data1已添加到布隆过滤器元素，data3和data4都是未添加到布隆过滤器元素。查询data1先根据添加时的三个hash函数计算分别对应值，值分别是1、8、13，然后查询数组中这三个位置的值是否为1。Hash1(data1)=1Hash2(data1)=8Hash3(data1)=13如图：我们可以看到数组中1、8、13这三个位置都是1，data1可能存在于该布隆过滤器。我们从添加的角度来看，我们知道data1是一定存在于该布隆过滤器的，为什么还要是说可能呢，是因为查询出来三个位置都为1不能代表这个三个1都是同一个元素添加的，下面我们看下元素data3的查询。查询data3先根据添加时的三个hash函数计算分别对应值，值分别是2、8、13，然后查询数组中这三个位置的值是否为1。Hash1(data3)=2Hash2(data3)=8Hash3(data3)=13如图：我们已知的该布隆过滤器我们没有添加给data3，为什么data3查询出来三个位置的值都为1呢。我们可以看到data3所命中的位置分别是data2添加时把位置2赋值的1，和data1添加时把位置8和位置13赋值的1，都是由其他元素改变的位置对应的值，所以命中位置全部为1。这个元素可能存在。我们查询一下data4，看下命中位置不全为0的数据。查询data4先根据添加时的三个hash函数计算分别对应值，值分别是2、8、13，然后查询数组中这三个位置的值是否为1。Hash1(data4)=1Hash2(data4)=8Hash3(data4)=12如图：我们可以看到data4元素的hash函数3计算之后的值是12，数组位置12的值是0，没有元素在位置12赋值过1。如果data4存在于该布隆过滤器，则一定在添加data4时会把位置12赋值1，此时位置12还是0，则说明该布隆过滤器未添加过data4元素，所以位置中有一个位置为0。则此元素一定不存在布隆过滤器中。四、布隆过滤器误判率刚才查询时我们发现data3没有添加过到布隆过滤器，却在布隆过滤器查询到了，这种情况就是布隆过滤器误判了。那可以不存在误判或者减少误判吗？事实上误判是一定存在的，我们可以尽可能减小误判。下面说下如何得到误判率。4.1参数m：布隆过滤器的bit长度。n：插入过滤器的元素个数。k：哈希函数的个数。4.2推导过程布隆过滤器某个位不置为1的概率：哈希k次某个位置不置为1的概率：根据极限：得：添加n个元素某个位置不置为1的概率：添加n个元素某个位置置为1的概率：查询一个元素，k次hash后误判的概率为都命中1的概率：4.3误判率公式1、布隆过滤器的误差率为：2、在m和n一定,误判率尽量小的情况下，hash函数个数为：3、误判率和n确定的情况下，bit长度为：4、由误判率公式可知，在k一定的情况下，当n增加时，误判率增加，m增加时，误判率减少。五、实现方式5.1Guava实现guava是谷歌开源工具类，其中就有能直接实现布隆过滤器的方法，不需要重复造轮子。方法名功能参数返回值put添加元素put(Tobject)booleanmightContain检查元素是否存在mightContain(Tobject)booleancopy根据此实例创建一个新的BloomFiltecopy()BloomFilterapproximateElementCount已添加到Bloom过滤器的元素的数量approximateElementCount()longexpectedFpp返回元素存在的错误概率expectedFpp()doubleisCompatible确定给定的Bloom筛选器是否与此Bloom筛选器兼容isCompatible(BloomFilterthat)booleanputAll通过执行的逐位OR将此Bloom过滤器与另一个Bloom过滤器组合putAll(BloomFilterthat)void引入依赖    com.google.guava        23.0测试代码 private static void GuavaBloomFilter() {    // 创建布隆过滤器对象    BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),EXPECTED_INSERTIONS,FALSE_PROBABILITY);    // 向过滤器中添加元素    bloomFilter.put("element001");    bloomFilter.put("element003");    // 判断元素是否存在    System.out.println(bloomFilter.mightContain("element001"));//true    System.out.println(bloomFilter.mightContain("element002"));//false    // 已添加到Bloom过滤器的元素的数量    System.out.println(bloomFilter.approximateElementCount());// 2    // 返回元素存在的错误概率    System.out.println(bloomFilter.expectedFpp());}5.2Redis实现开源Redisson(RBloomFilter)。Redis4.0官方提供布隆过滤器插件。通过Redis提供的bitMap自己实现。5.2.1开源Redisson方式Redisson方法方法名功能参数返回值add添加元素add(Tobject)booleancontains检查元素是否存在contains(Tobject)booleancount已添加到Bloom过滤器的元素的数量count()longgetExpectedInsertions返回的预期插入元素的个数getExpectedInsertions()longgetFalseProbability返回元素存在的错误概率getFalseProbability()doublegetHashIterations返回每个元素使用的哈希迭代次数getHashIterations()intgetSize返回此实例所需Redis内存的位数getSize()longtryInit初始化Bloom筛选器参数tryInit(longexpectedInsertions,doublefalseProbability)booleandelete删除对象delete()boolean引入依赖    org.redisson        3.22.1测试代码private static void RedissonBloomFilter() {    Config config = new Config();    config.useSingleServer().setAddress("redis://" + REDIS_IP + ":" + REDIS_PORT);    config.useSingleServer().setPassword(REDIS_PASSWORD);    // 获取客户端    RedissonClient redissonClient = Redisson.create(config);    RBloomFilter bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_NAME);    // 初始化布隆过滤器：预期插入量为100000000L,预期错误概率为1%    bloomFilter.tryInit(EXPECTED_INSERTIONS, FALSE_PROBABILITY);    // 插入数据    bloomFilter.add("element001");    bloomFilter.add("element003");    // 判断下面元素是否在布隆过滤器中    System.out.println(bloomFilter.contains("element002"));//false    System.out.println(bloomFilter.contains("element001"));//true    // 已添加到Bloom过滤器的元素的数量    System.out.println(bloomFilter.count());//2    // 预期插入元素的个数    System.out.println(bloomFilter.getExpectedInsertions());//1000000    // 元素存在的错误概率    System.out.println(bloomFilter.getFalseProbability());//0.01    // 每个元素使用的哈希迭代次数    System.out.println(bloomFilter.getHashIterations());    // 实例所需Redis内存的位数    System.out.println(bloomFilter.getSize());}5.2.2Redis4.0官方提供布隆过滤器插件基础命令命令功能参数BF.RESERVE创建一个大小为capacity，错误率为error_rate的空的BloomBF.RESERVE{key}{error_rate}{capacity}[EXPANSION{expansion}][NONSCALING]BF.ADD向key指定的Bloom中添加一个元素itomBF.ADD{key}{item}BF.MADD向key指定的Bloom中添加多个元案BF.MADD{key}{item...}BF.INSERT向key指定的Bloom中添加多个元素，添加时可以指定大小和错误率，且可以控制在Bloom不存在的时候是否自动创建BF.INSERT{key}[CAPACITY{cap}][ERROR{error}][EXPANSION{expansion}][NOCREATE][NONSCALING]ITEMS{item...}BF.EXISTS检查一个元秦是否可能存在于key指定的Bloom中BF.EXISTS{key}{item}BF.MEXISTS同时检查多个元素是否可能存在于key指定的Bloom中BF.MEXISTS{key}{item...}BF.SCANDUMP对Bloom进行增量持久化操作BF.SCANDUMP{key}{iter}BF.LOADCHUNK加载SCANDUMP持久化的Bloom数据BF.LOADCHUNK{key}{iter}{data}BF.INFO查询key指定的Bloom的信息BF.INFO{key}BF.DEBUG查看BloomFilter的内部详细信息(如每层的元素个数，错误率等)BF.DEBUG(key}引入依赖            redis.clients                4.2.0    测试代码 private static void RedisBloomFilter() {    // 建立连接    BloomFilterCommands bloomFilterCommands = new JedisPooled(REDIS_IP, REDIS_PORT, "", REDIS_PASSWORD);    // 构建布隆过滤器参数    BFReserveParams bfReserveParams = new BFReserveParams();    bfReserveParams.expansion(2);    // 创建一个过滤器    String test = bloomFilterCommands.bfReserve(BLOOM_FILTER_NAME, FALSE_PROBABILITY, EXPECTED_INSERTIONS, bfReserveParams);    // 向过滤器中添加元素    bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element001");    bloomFilterCommands.bfAdd(BLOOM_FILTER_NAME, "element003");    // 判断元素是否存在    System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element001"));//true    System.out.println(bloomFilterCommands.bfExists(BLOOM_FILTER_NAME, "element002"));//false}5.2.3通过Redis提供的bitMap自己实现自定义方法方法名功能参数返回值add添加元素add(Stringkey,Stringelement,intexpireSec)booleancontains检查元素是否存在contains(Stringkey,Stringelement)booleangetExpectedInsertions返回的预期插入元素的个数getExpectedInsertions()longgetFalseProbability返回元素存在的错误概率getFalseProbability()doublegetNumHashFunctions返回每个元素使用的哈希迭代次数getNumHashFunctions()intgetBitmapLength返回Bitmap长度getBitmapLength()longBloomFilterUtils创建Bloom对象BloomFilterUtils(longexpectedInsertions,doublefalseProbability)BloomFilterUtils测试代码  public class BloomFilterUtils {    private static final String BF_KEY_PREFIX = "bf_";    private long numApproxElements;    private double falseProbability;    // hash个数    private int numHashFunctions;    // 数组长度    private int bitmapLength;    private JedisResourcePool jedisResourcePool;    /**     * 构造布隆过滤器。注意：在同一业务场景下，三个参数务必相同     *     * @param numApproxElements 预估元素数量     * @param fpp               可接受的最大误差     * @param jedisResourcePool Codis专用的Jedis连接池     */    public BloomFilterUtils(Long numApproxElements, double fpp, JedisResourcePool jedisResourcePool) {        this.numApproxElements = numApproxElements;        this.falseProbability = fpp;        this.jedisResourcePool = jedisResourcePool;        // 数组长度 m = (n * lnp)/ln2^2        bitmapLength = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2)));        // hash个数 k = (n / m ) * ln2        numHashFunctions = Math.max(1, (int) Math.round((double) bitmapLength / numApproxElements * Math.log(2)));    }    /**     * 取得预估元素数量     */    public long getExpectedInsertions() {        return numApproxElements;    }    /**     * 返回元素存在的错误概率     */    public double getFalseProbability() {        return falseProbability;    }    /**     * 取得自动计算的最优哈希函数个数     */    public int getNumHashFunctions() {        return numHashFunctions;    }    /**     * 取得自动计算的最优Bitmap长度     */    public int getBitmapLength() {        return bitmapLength;    }    /**     * 计算一个元素值哈希后映射到Bitmap的哪些bit上     *     * @param element 元素值     * @return bit下标的数组     */    private long[] getBitIndices(String element) {        long[] indices = new long[numHashFunctions];        // 元素  使用MurMurHash3 128位Hash算法转换值        byte[] bytes = Hashing.murmur3_128()                .hashObject(element, Funnels.stringFunnel(Charset.forName("UTF-8")))                .asBytes();        // 低8位转Long值        long hash1 = Longs.fromBytes(                bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]        );        // 高8位转Long值        long hash2 = Longs.fromBytes(                bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]        );        long combinedHash = hash1;        // 双重哈希进行散列        for (int i = 0; i  < numHashFunctions; i++) {            indices[i] = (combinedHash & Long.MAX_VALUE) % bitmapLength;            combinedHash += hash2;        }        return indices;    }    /**     * 插入元素     *     * @param key       原始Redis键，会自动加上'bf_'前缀     * @param element   元素值，字符串类型     * @param expireSec 过期时间（秒）     */    public void add(String key, String element, int expireSec) {        if (key == null || element == null) {            throw new RuntimeException("键值均不能为空");        }        String actualKey = BF_KEY_PREFIX.concat(key);        try (Jedis jedis = jedisResourcePool.getResource()) {            try (Pipeline pipeline = jedis.pipelined()) {                // 遍历元素所有hash结果的bit位置                for (long index : getBitIndices(element)) {                    pipeline.setbit(actualKey, index, true);                }                pipeline.syncAndReturnAll();            }            jedis.expire(actualKey, expireSec);        }    }    /**     * 检查元素在集合中是否（可能）存在     *     * @param key     原始Redis键，会自动加上'bf_'前缀     * @param element 元素值，字符串类型     */    public boolean contains(String key, String element) {        if (key == null || element == null) {            throw new RuntimeException("键值均不能为空");        }        String actualKey = BF_KEY_PREFIX.concat(key);        boolean result = false;        try (Jedis jedis = jedisResourcePool.getResource()) {            // 遍历元素所有hash结果的bit位置            try (Pipeline pipeline = jedis.pipelined()) {                for (long index : getBitIndices(element)) {                    pipeline.getbit(actualKey, index);                }                result = !pipeline.syncAndReturnAll().contains(false);            }        }        return result;    }    public static void main(String[] args) {        String path = ath.getCurrentPath() + "/config/zzjodis.properties";        ConfigReadUtil configReadUtil = new ConfigReadUtil(path);        try {            JedisResourcePool jedisResourcePool = RoundRobinJedisPool.                    create()                    .curatorClient(configReadUtil.getString("jodisZkStr"), 5000)                    .zkProxyDir(configReadUtil.getString("zkProxyDir"))                    .team(configReadUtil.getString("team"))                    .connectionTimeoutMs(configReadUtil.getInt("connectionTimeoutMs"))                    .soTimeoutMs(configReadUtil.getInt("soTimeoutMs"))                    .appKey(configReadUtil.getString("appKey"))                    .password("".equals(configReadUtil.getString("password")) ? null : configReadUtil.getString("password"))                    .build();            BloomFilterUtils bloomFilterUtils = new BloomFilterUtils(10000, 0.01, jedisResourcePool);            bloomFilterUtils.add("filter01", "element001", 30 * 60);            System.out.println(bloomFilterUtils.contains("filter01", "element001"));  // true            System.out.println(bloomFilterUtils.contains("filter01", "element002"));  // false        } catch (Exception e) {            e.printStackTrace();        }    }}六、布隆过滤器商业运用6.1业务场景在C1看视频得曝光活动项目中，为了在个人中心页为拥有在架商品的用户展示活动入口，需要高效地判断用户是否有在架商品。目前存在上亿存量用户和上百万的在架商品用户。每次用户进入个人中心页时，需要查询用户是否有在架商品，以确定是否展示活动入口。然而，直接查询商品服务会导致大量的重复查询和增加服务耗时。可以使用布隆过滤器来优化此过程，它只需要几十MB内存，相比于使用Redis存储每日在架商品用户需要几GB内存，更加高效节省内存消耗。6.2布隆过滤器选择实现方式储存位置适用场景备注Guava机器单机只需要机器内存不需要其他资源Redissonredis分布式连接Redis即可使用Redis插件redis分布式需要对redis集群进行设置支持布隆过滤器插件Redis的bitMapredis分布式需要自己实现添加和查询对于分布式服务环境，Guava方式不适合使用，而Redis插件需要复杂的配置和高成本支持。相比之下，Redisson连接Redis并进行插入和查询的方式更适合当前场景，因此最终选择了Redisson方式。6.3使用布隆过滤器效果1、内存占用情况上线初期，我们将符合条件的用户存入Codis缓存中。这使得内存从1.98GB增长到9.52GB，此次数据量占用了7.54GB的内存。随后，为进一步优化，我们成功将用户量缩小了25倍。这使得内存占用降至308.8MB。最终，我们切换到了Redisson方式使用布隆过滤器。这次Redis内存从2.7172GB增长到2.7566GB，而数据量仅占用39.4MB的内存。使用Codis内存占用情况插入数据前：插入数据后：使用布隆过滤器内存占用情况插入数据前：插入数据后：2、通过使用布隆过滤器减少对商品服务的查询，从而提升服务性能。之前需要查询商品服务来判断用户商品状态，但使用布隆过滤器后，减少了这部分服务间的调用耗时，整体流程的耗时减少了大约5ms。作者介绍李帅齐，转转商业后端开发工程师，目前负责商业C端相关业务系统开发(广告检索、计费以及特征工程系统等)。