<翻译> 如何利用Bloom Filter在Java中构建大规模基于内存的缓存

原文地址: http://www.javacodegeeks.com/2014/07/how-to-use-bloom-filter-to-build-a-large-in-memory-cache-in-java.html

缓存(Cache)是用来解决当下软件性能问题时需要考虑的一个很重要的手段。 你的程序可能有密集的CPU操作,而你却不想一遍又一遍的折磨CPU。 相反, 你会将结果抽取出来并缓存到内存中。 有时候系统的瓶颈也可能是IO操作, 比如你不想重复执行数据库的查询,而是把查询结果缓存起来, 只是在数据库的数据改变的时候才去更新缓存。

类似地还有一些其它需要cache的情况如处理收到的request时我们需要执行一个快速的查询。例如, 你需要判断一个URL是否指向了一个恶意网站。 可能有非常多的(恶意网站的)URL, 如果我们将所有的恶意网址都缓存起来, 需要很大的空间。 又比如我们需要识别用户输入的字符串中是否包含美国的一个地方。 比如用户输入华盛顿的博物馆, 这个字符串中华盛顿是美国的一个地名。 我们要把美国所有的地名缓存起来以供查找? 缓存会变得多大?没有数据库支持的这样做是否有效?
这就是我们淘汰map数据结构而去宣召一个更先进数据结构-boomfilter。 你可以把blommfilter看作类似java collection中的类。 可以把数据项放到它里面,可以检查某个数据项是否已经存在。 如果Bloomfilter说数据项不存在, 那数据项的确不存在, 不必怀疑。 但是如果它说数据项存在, 可能是误报, 有可能数据项真的不存在。 如果我们考虑周全, 就能减少误报的可能。

算法解释

Bloomfilter 设计为一个m bit的数组。 初始所有的bit为0.

增加项:

为了增加数据项, 需要提供k个hash函数。每个hash将会产生一个数字,对应bit数组的一个位置 (0 ~ m)。 我们会将此位置设置为 1. 例如hash1函数的计算数据项的值为x, hash2函数为y, hash3函数为z。

将bit数组中相应的位置设置为1:

1
A[x]=A[y]=A[z] = 1

查找项:

查找时的逻辑类似增加数据项, 通过hash1, hash2, hash3 ...计算出三个位置x, y, z。 我们需要检查bit数组中x, y, z的位置的值是否为1. 如果不全为1, 数据项肯定没有被增加过. 但是如果全为1, 也可能是假阳性的(数据项也可能从未被增加过)

调优

从上面的解释可以清晰的看出, 为了设计一个好的bloomfilter我们需要遵循一下的原则:

  • 良好的hash函数确保尽可能快的产生一定范围的哈希值
  • 数组的大小m至关重要. 如果太小, 可能很快所有的位置都被设置为1, 误报率会非常的高。
  • hash functions的数量也非常重要。 所有的值要尽可能的均匀分布。

如果我们能预估我们会在bloomfilter存多少个数据项,我们就能计算出最优的k和m值。 跳过数学理论的细节, 下面的公式足够我们写出一个好的bloomfilter。

计算m的公式:
$m = - \frac{n\log^p}{(\log2)^2}$

这里的 p为 误报率。

计算k的公式:
$k = \frac{m}{n} \log2$

k是hash函数的数量。 m是bit数, n是数据项的数量。

在线计算: 点击这里

哈希

Hash函数也是影响bloomfilter性能的因素. 我们需要选择有效且不费时的hash函数。在论文 “Less Hashing, Same Performance: Building a Better Bloom Filter” 讨论了怎么使用两个hash函数产生k个哈希函数。 首先需要计算两个哈希函数h1(x) 和 h2(x), 然后我们使用这两个hash函数模拟k个哈希函数。
$g_i(x) = h_1(x) + ih_2(x)$
i的值域为 {1..k}.

Google guava library 在它的bloomfilter实现中使用了这个技巧。 Hash的代码逻辑如下 :

1
2
3
4
5
6
7
8
long hash64 = …; //calculate a 64 bit hash function
//split it in two halves of 32 bit hash values
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
//Generate k different hash functions with a simple loop
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
}

应用

很清楚怎么使用数学公式计算合适的值来创建bloomfilter来处理问题。 我们需要很好的理解其意义。就像我们使用bloomfilter来处理美国所有的城市名一样。 城市的数学我们早已获悉,所以我们可以确定n的值的大小。 依照业务选择你期望的p值(误报率). 这样我们就可以使用有效的内存创建一个完美的cache, 查询时间也很短。

实现

Google guava 库实现了Bloomfilter. 构造函数需要传入期望的数据项和误报率.

1
2
3
4
5
6
7
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
//Create Bloomfilter
int expectedInsertions = ….;
double fpp = 0.03; // desired false positive probability
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), expectedInsertions,fpp)

参考资源: