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）。

1package guava;
2
3import com.google.common.base.Strings;
4import com.google.common.collect.Lists;
5import com.google.common.collect.Maps;
6import com.google.common.hash.BloomFilter;
7import com.google.common.hash.Funnel;
8import com.google.common.hash.PrimitiveSink;
9import org.junit.Before;
10import org.junit.Test;
11
12import java.io.BufferedWriter;
13import java.io.File;
14import java.io.FileWriter;
15import java.io.IOException;
16import java.nio.charset.Charset;
17import java.util.List;
18import java.util.Map;
19import java.util.Random;
20
21/**
22 * Created by hgf on 16/8/25.
23 */
24public class BloomFilterTest {
25
26    private BloomFilter<String> bloomFilter;
27
28    private final static String TOKEN = "token-[0-9]+";
29
30    private final static String prefix = "token-";
31
32    private List<String> tokens = Lists.newArrayList();
33
34    private Map<String, Integer> map = Maps.newHashMap();
35
36    private Map<String, Integer> reflect = Maps.newHashMap();
37
38    @Before
39    public void init() {
40        Random random = new Random();
41
42        for (int i = 0; i < 10000; i++) {
43            tokens.add(prefix + random.nextInt(10000));
44        }
45        try {
46            writeSource();
47        } catch (IOException e) {
48            e.printStackTrace();
49        }
50    }
51
52    @Test
53    public void test() {
54    //此处使用的是自定义funnel，可以使用guava默认实现的funnel。
55    //全部实现在Funnels中。Funnels.stringFunnel(Charset.defaultCharset())
56    //注意此处布隆过滤器大小，应估算的稍大
57        bloomFilter = BloomFilter.create(stringFunnel(), tokens.size());
58
59        int repeatTimes = 0;
60        for (String token : tokens) {
61            //参照数据
62            Integer tmp = reflect.get(token);
63            if (tmp == null) {
64                reflect.put(token, 1);
65            } else {
66                reflect.put(token, tmp + 1);
67            }
68
69            //布隆过滤器数据
70            boolean hasToken = bloomFilter.mightContain(token);
71            if (hasToken) {
72                Integer times = map.get(token);
73                if (times == null) {
74                    map.put(token, 2);
75                } else {
76                    map.put(token, times + 1);
77                }
78                repeatTimes++;
79            } else {
80                bloomFilter.put(token);
81            }
82        }
83
84        System.out.println("随机token中重复次数:" + repeatTimes);
85//        //打印重复的token
86//        System.out.println("bloom filter 判断为重复的token数:" + map);
87
88        compareResult();
89    }
90
91    private void compareResult() {
92
93        int wrongCount = 0;
94        for (String token : map.keySet()) {
95            Integer tmp = map.get(token);
96            if (!(tmp != null && tmp.intValue() == reflect.get(token).intValue())) {
97                wrongCount++;
98                System.out.println("错误统计:\t" + token + "\t" + tmp + "\t" + reflect.get(token));
99            }
100        }
101        System.out.println("总统计出错,对比结果:" + wrongCount+"次");
102    }
103
104    private void writeSource() throws IOException {
105        File file = new File("source.txt");
106        try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(file))) {
107            for (String token : tokens) {
108                bufferedWriter.write(token);
109                bufferedWriter.newLine();
110            }
111        }
112
113    }
114
115    public static Funnel<String> stringFunnel() {
116        return StringFunnel.INSTANCE;
117    }
118
119    private enum StringFunnel implements Funnel<String> {
120        INSTANCE;
121
122        @Override
123        public void funnel(String from, PrimitiveSink into) {
124            if (isToken(from)) {
125                into.putString(from, Charset.defaultCharset());
126            }
127        }
128
129        private boolean isToken(String token) {
130            return (!Strings.isNullOrEmpty(token) && token.matches(TOKEN));
131        }
132
133    }
134}
135

输出结果

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

注意点

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

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

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

场景

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

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

与Tair方案对比

优势：

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

劣势：

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