Skip to content

Latest commit

 

History

History
325 lines (261 loc) · 13 KB

布隆过滤器.md

File metadata and controls

325 lines (261 loc) · 13 KB
Raw

布隆过滤器(Bloom Filter)详解

直观的说，bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。 和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。

算法：
  1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
  2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
  3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
  4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

优点：

  1. 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

  2. 布隆过滤器可以表示全集，其它任何数据结构都不能。

缺点：

  1. 算法判断key在集合中时，有一定的概率key其实不在集合中
  2. 无法删除

典型的应用场景：

  1. 某些存储系统的设计中，会存在空查询缺陷：当查询一个不存在的key时，需要访问慢设备，导致效率低下。 比如一个前端页面的缓存系统，可能这样设计：先查询某个页面在本地是否存在，如果存在就直接返回，如果不存在，就从后端获取。但是当频繁从缓存系统查询一个页面时，缓存系统将会频繁请求后端，把压力导入后端。这是只要增加一个bloom算法的服务，后端插入一个key时，在这个服务中设置一次 需要查询后端时，先判断key在后端是否存在，这样就能避免后端的压力。
  2. 网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等。

一、什么是布隆过滤器

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

二、实现原理

HashMap 的问题

讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：

Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：

值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

删除问题

目前我们知道布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上图中的 bit 位 4 被两个值共同覆盖的话，一旦你删除其中一个值例如 “tencent” 而将其置位 0，那么下次判断另一个值例如 “baidu” 是否存在的话，会直接返回 false，而实际上你并没有删除它。

如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。

怎么选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。

大Value拆分

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

Java实现布隆过滤器

package com.unclezs.novel.utis;


import java.io.*;
import java.util.Arrays;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;

public class BloomFileter implements Serializable {
private static final long serialVersionUID = -5221305273707291280L;
private final int[] seeds;
private final int size;
private final BitSet notebook;
private final MisjudgmentRate rate;
private final AtomicInteger useCount = new AtomicInteger(0);
private final Double autoClearRate;

@Override
public String toString() {
	return "BloomFileter{" +
			"seeds=" + Arrays.toString(seeds) +
			", size=" + size +
			", notebook=" + notebook +
			", rate=" + rate +
			", useCount=" + useCount +
			", autoClearRate=" + autoClearRate +
			'}';
}

/**
 * 默认中等程序的误判率：MisjudgmentRate.MIDDLE 以及不自动清空数据（性能会有少许提升）
 * 
 * @param dataCount
 *            预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
 */
public BloomFileter(int dataCount) {
	this(MisjudgmentRate.MIDDLE, dataCount, null);
}

/**
 * 
 * @param rate
 *            一个枚举类型的误判率
 * @param dataCount
 *            预期处理的数据规模，如预期用于处理1百万数据的查重，这里则填写1000000
 * @param autoClearRate
 *            自动清空过滤器内部信息的使用比率，传null则表示不会自动清理，
 *            当过滤器使用率达到100%时，则无论传入什么数据，都会认为在数据已经存在了
 *            当希望过滤器使用率达到80%时自动清空重新使用，则传入0.8
 */
public BloomFileter(MisjudgmentRate rate, int dataCount, Double autoClearRate) {
	long bitSize = rate.seeds.length * dataCount;
	if (bitSize < 0 || bitSize > Integer.MAX_VALUE) {
		throw new RuntimeException("位数太大溢出了，请降低误判率或者降低数据大小");
	}
	this.rate = rate;
	seeds = rate.seeds;
	size = (int) bitSize;
	notebook = new BitSet(size);
	this.autoClearRate = autoClearRate;
}

public void add(String data) {
	checkNeedClear();

	for (int i = 0; i < seeds.length; i++) {
		int index = hash(data, seeds[i]);
		setTrue(index);
	}
}

public boolean check(String data) {
	for (int i = 0; i < seeds.length; i++) {
		int index = hash(data, seeds[i]);
		if (!notebook.get(index)) {
			return false;
		}
	}
	return true;
}

/**
 * 如果不存在就进行记录并返回false，如果存在了就返回true
 * 
 * @param data
 * @return
 */
public boolean addIfNotExist(String data) {
	checkNeedClear();

	int[] indexs = new int[seeds.length];
	// 先假定存在
	boolean exist = true;
	int index;

	for (int i = 0; i < seeds.length; i++) {
		indexs[i] = index = hash(data, seeds[i]);

		if (exist) {
			if (!notebook.get(index)) {
				// 只要有一个不存在，就可以认为整个字符串都是第一次出现的
				exist = false;
				// 补充之前的信息
				for (int j = 0; j <= i; j++) {
					setTrue(indexs[j]);
				}
			}
		} else {
			setTrue(index);
		}
	}

	return exist;

}
private void checkNeedClear() {
	if (autoClearRate != null) {
		if (getUseRate() >= autoClearRate) {
			synchronized (this) {
				if (getUseRate() >= autoClearRate) {
					notebook.clear();
					useCount.set(0);
				}
			}
		}
	}
}

public void setTrue(int index) {
	useCount.incrementAndGet();
	notebook.set(index, true);
}

private int hash(String data, int seeds) {
	char[] value = data.toCharArray();
	int hash = 0;
	if (value.length > 0) {

		for (int i = 0; i < value.length; i++) {
			hash = i * hash + value[i];
		}
	}

	hash = hash * seeds % size;
	// 防止溢出变成负数
	return Math.abs(hash);
}

public double getUseRate() {
	return (double) useCount.intValue() / (double) size;
}

public void saveFilterToFile(String path) {
	try (ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path))) {
		oos.writeObject(this);
	} catch (Exception e) {
		throw new RuntimeException(e);
	}

}

public static BloomFileter readFilterFromFile(String path) {
	try (ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path))) {
		return (BloomFileter) ois.readObject();
	} catch (Exception e) {
		throw new RuntimeException(e);
	}
}

/**
 * 清空过滤器中的记录信息
 */
public void clear() {
	useCount.set(0);
	notebook.clear();
}

public MisjudgmentRate getRate() {
	return rate;
}

/**
 * 分配的位数越多，误判率越低但是越占内存
 * 
 * 4个位误判率大概是0.14689159766308
 * 
 * 8个位误判率大概是0.02157714146322
 * 
 * 16个位误判率大概是0.00046557303372
 * 
 * 32个位误判率大概是0.00000021167340
 * 
 * @author Uncle
 *
 */
public enum MisjudgmentRate {
	// 这里要选取质数，能很好的降低错误率
	/**
	 * 每个字符串分配4个位
	 */
	VERY_SMALL(new int[] { 2, 3, 5, 7 }),
	/**
	 * 每个字符串分配8个位
	 */
	SMALL(new int[] { 2, 3, 5, 7, 11, 13, 17, 19 }), //
	/**
	 * 每个字符串分配16个位
	 */
	MIDDLE(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }), //
	/**
	 * 每个字符串分配32个位
	 */
	HIGH(new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
			101, 103, 107, 109, 113, 127, 131 });

	private int[] seeds;

	private MisjudgmentRate(int[] seeds) {
		this.seeds = seeds;	
	}

	public int[] getSeeds() {
		return seeds;
	}

	public void setSeeds(int[] seeds) {
		this.seeds = seeds;
	}

}

public static void main(String[] args) {
		BloomFileter fileter = new BloomFileter(7);
		System.out.println(fileter.addIfNotExist("/8/8217/5159455.html"));
		System.out.println(fileter.addIfNotExist("/8/8217/5159456.html"));
	    System.out.println(fileter.addIfNotExist("/8/8217/5159457.html"));
		fileter.saveFilterToFile("F:/test.obj");
		BloomFileter fileter = readFilterFromFile("F:/test.obj");
		System.out.println(fileter.getUseRate());
		System.out.println(fileter.addIfNotExist("/8/8217/5159455.html"));
}

} ``

贡献人员名单

CHANGELOG

V1.0 2019/3/3