<翻译> 如何利用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说数据项不存在, 那数据项的确不存在, 不必怀疑。 但是如果它说数据项存在, 可能是误报, 有可能数据项真的不存在。 如果我们考虑周全, 就能减少误报的可能。

阅读全文