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

初始化:对于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方案对比
优势:
- 判断重复节约大量内存空间。
劣势:
- 在分布式场景中,目前需要自己包装服务。