guava-布隆过滤器

超硬核！直播聊聊工业软件的 “中国心”

背景

原有的去重方案是：

1. 使用linux命令去重
   • 缺点
     1. 出现问题只能重来，控制粒度很粗。
     2. 程序与操作系统过渡耦合，如果系统中sort或者uniq命令出现问题，则去重功能不能使用。
     3. 使得push opt的用户数据以文件的形式存在，不方便多主机、操作系统共享，妨碍后期push opt多主节点发展。
   • 优点
     1. 实现简单
     2. 一般功能稳定
2. 使用tair去重
   • 缺点
     1. 浪费大量珍贵的内存资源
     2. 不一定可靠，也可能丢失数据
     3. tair出现问题后，用户去重功能彻底不能使用。
   • 优点
     1. 一般不会出现问题；
     2. 访问迅速；
     3. 接近O(1)时间复杂度得知哪条重复。
     4. 适合分布式系统中去重

为什么使用布隆过滤器

原理


初始化：对于x,y,z三个数，经过{k1,k2,k3}三个hash函数，将向量空间中的某些位置标记为1，作为初始向量空间。

判断：当新进入一个数据，w，进过{k1,k2,k3}hash函数，在向量空间上所有位置均为1，表示命中这个数，这个数已经在bloomfilter中。如果部分为1或者全为0，表示这个数不在bloomfilter中。

性能分析

参考：csdn博客

如果hash函数个数为k个，那么bloom过滤器插入和判断一个数的时间复杂度是O(k)，空间复杂度为O(size)。size为bloomfilter的位数组大小。

优缺点分析

• 优点：常数时间复杂度，占用很少的内存。
• 缺点：不会漏判一个已经发送过的token，但是可能误判一个每发送过的为发送了。此时发生了hash冲突。但是当hash空间一定大的时候，是可以降低冲突的。还有发送push，少发了几个是可以容忍的。（类似tair丢失极少量数据是可以容忍的）

使用

Guava的布隆过滤器通过调用BloomFilter类的静态函数创建，传递一个Funnel对象以及一个代表预期插入数量的整数。

Funnel对象的作用，将数据发送给一个接收器（Slink）。

package guava;

import com.google.common.base.Strings;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import org.junit.Before;
import org.junit.Test;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.charset.Charset;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * Created by hgf on 16/8/25.
 */
public class BloomFilterTest {

    private BloomFilter<String> bloomFilter;

    private final static String TOKEN = "token-[0-9]+";

    private final static String prefix = "token-";

    private List<String> tokens = Lists.newArrayList();

    private Map<String, Integer> map = Maps.newHashMap();

    private Map<String, Integer> reflect = Maps.newHashMap();

    @Before
    public void init() {
        Random random = new Random();

        for (int i = 0; i < 10000; i++) {
            tokens.add(prefix + random.nextInt(10000));
        }
        try {
            writeSource();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    @Test
    public void test() {
    //此处使用的是自定义funnel，可以使用guava默认实现的funnel。
    //全部实现在Funnels中。Funnels.stringFunnel(Charset.defaultCharset())
    //注意此处布隆过滤器大小，应估算的稍大
        bloomFilter = BloomFilter.create(stringFunnel(), tokens.size());

        int repeatTimes = 0;
        for (String token : tokens) {
            //参照数据
            Integer tmp = reflect.get(token);
            if (tmp == null) {
                reflect.put(token, 1);
            } else {
                reflect.put(token, tmp + 1);
            }

            //布隆过滤器数据
            boolean hasToken = bloomFilter.mightContain(token);
            if (hasToken) {
                Integer times = map.get(token);
                if (times == null) {
                    map.put(token, 2);
                } else {
                    map.put(token, times + 1);
                }
                repeatTimes++;
            } else {
                bloomFilter.put(token);
            }
        }

        System.out.println("随机token中重复次数:" + repeatTimes);
//        //打印重复的token
//        System.out.println("bloom filter 判断为重复的token数:" + map);

        compareResult();
    }

    private void compareResult() {

        int wrongCount = 0;
        for (String token : map.keySet()) {
            Integer tmp = map.get(token);
            if (!(tmp != null && tmp.intValue() == reflect.get(token).intValue())) {
                wrongCount++;
                System.out.println("错误统计:\t" + token + "\t" + tmp + "\t" + reflect.get(token));
            }
        }
        System.out.println("总统计出错,对比结果:" + wrongCount+"次");
    }

    private void writeSource() throws IOException {
        File file = new File("source.txt");
        try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(file))) {
            for (String token : tokens) {
                bufferedWriter.write(token);
                bufferedWriter.newLine();
            }
        }

    }

    public static Funnel<String> stringFunnel() {
        return StringFunnel.INSTANCE;
    }

    private enum StringFunnel implements Funnel<String> {
        INSTANCE;

        @Override
        public void funnel(String from, PrimitiveSink into) {
            if (isToken(from)) {
                into.putString(from, Charset.defaultCharset());
            }
        }

        private boolean isToken(String token) {
            return (!Strings.isNullOrEmpty(token) && token.matches(TOKEN));
        }

    }
}

输出结果

随机token中重复次数:3709
错误统计:   token-7746  2   1
错误统计:   token-5714  2   1
错误统计:   token-1718  3   2
错误统计:   token-7065  3   2
错误统计:   token-8875  4   3
错误统计:   token-3599  2   1
错误统计:   token-8563  2   1
总统计出错,对比结果:7次

注意点

预期插入数量是很关键的一个参数。当插入的数量接近或高于预期值的时候，布隆过滤器将会填满，这样的话，它会产生很多无用的误报点。

有另一个版本的 BloomFilter.create 方法，它额外接收一个参数，一个代表假命中概率水平的双精度数字（必须大于零且小于1）

假命中概率等级影响哈希表储存或搜索元素的数量。百分比越低，哈希表的性能越好。

场景

适用判断一个元素是否在某个集合（该集合往往数据量庞大）出现，并允许一定小概率错误的场景。
例如：判断一个url或者邮件地址或者token，是否出现在给定集合中。

• 做缓存的时候，使用bloomfilter，不给只访问过一次的数据做缓存，数据量大但是大多都只需要访问一次。
• 对大型分布式的NOSQL，使用布隆过滤器判断某一行数据是否存在，避免无谓的磁盘读写和查找。HBASE，BIGTABLE
• 判断恶意网址。
• 避免爬虫爬取同样的url，陷入爬取旋涡。
• 推荐网站避免给用户推送同样的url。

与Tair方案对比

优势：

• 判断重复节约大量内存空间。

劣势：

• 在分布式场景中，目前需要自己包装服务。