如何使用bloomfilter构建大型Java缓存系统

标签: 教程 cache Java | 发表时间:2014-09-12 08:00 | 作者:刘 家财
出处:http://www.importnew.com

背景

在如今的软件当中,缓存是解决很多问题的一个关键概念。你的应用可能会进行CPU密集型运算。你当然不想让这些运算一边又一边的重复执行,相反,你可以只执行一次, 把这个结果放在内存中作为缓存。有时系统的瓶颈在I/O操作上,比如你不想重复的查询数据库,你想把结果缓存起来,只在数据发生变化时才去数据查询来更新缓存。

与上面的情况类似,有些场合下我们需要进行快速的查找来决定如何处理新来的请求。例如,考虑下面这种情况,你需要确认一个URL是否指向一个恶意网站,这种需求可能会有很多。如果我们把所有恶意网站的URL缓存起来,那么会占用很大的空间。或者另一种情况,需要确认用户输入的字符串是包含了美国的地名。像“华盛顿的博物馆”——在这个字符串中,华盛顿是美国的一个地名。我们应该把美国所有的地名保存在内存中然后再查询吗?那样的话缓存会有多大?是否能在不使用数据库的前提下来高效地完成?

这就是为什么我们要跨越基本的数据结构map,在更高级的数据结构像布隆过滤器(bloomfilter)中来寻找答案。你可以把布隆过滤器看做Java中的集合(collection),你可以往它里面添加元素,查询某个元素是否存在(就像一个HashSet)。如果布隆过滤器说没有这个元素,这个结果可能是错误的。如果我们在设计布隆过滤器时足够细心,我们可以把这种出错的概率控制在可接受范围内。

解释

布隆过滤器被设计为一个具有N的元素的位数组A(bit array),初始时所有的位都置为0.

添加元素

要添加一个元素,我们需要提供k个哈希函数。每个函数都能返回一个值,这个值必须能够作为位数组的索引(可以通过对数组长度进行取模得到)。然后,我们把位数组在这个索引处的值设为1。例如,第一个哈希函数作用于元素I上,返回x。类似的,第二个第三个哈希函数返回y与z,那么:

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

查找元素

查找的过程与上面的过程类似,元素将会被会被不同的哈希函数处理三次,每个哈希函数都返回一个作为位数组索引值的整数,然后我们检测位数组在x、y与z处的值是否为1。如果有一处不为1,那么就说明这个元素没有被添加到这个布隆过滤器中。如果都为1,就说明这个元素在布隆过滤器里面。当然,会有一定误判的概率。

算法优化

通过上面的解释我们可以知道,如果想设计出一个好的布隆过滤器,我们必须遵循以下准则:

  • 好的哈希函数能够尽可能的返回宽范围的哈希值。
  • 位数组的大小(用m表示)非常重要:如果太小,那么所有的位很快就都会被赋值为1,这样就增加了误判的几率。
  • 哈希函数的个数(用k表示)对索引值的均匀分配也很重要。

计算m的公式如下:

m = - nlog p / (log2)^2;

这里p为可接受的误判率。

计算k的公式如下:

k = m/n log(2) ;

这里k=哈希函数个数,m=位数组个数,n=待检测元素的个数(后面会用到这几个字母)。

哈希算法

哈希算法是影响布隆过滤器性能的地方。我们需要选择一个效率高但不耗时的哈希函数,在论文《更少的哈希函数,相同的性能指标:构造一个更好的布隆过滤器》中,讨论了如何选用2个哈希函数来模拟k个哈希函数。首先,我们需要计算两个哈希函数h1(x)与h2(x)。然后,我们可以用这两个哈希函数来模仿产生k个哈希函数的效果:

gi(x) = h1(x) + ih2(x);

这里i的取值范围是1到k的整数。

Google guava类库使用这个技巧实现了一个布隆过滤器,哈希算法的主要逻辑如下:

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;
}

应用

从数学公式中,我们可以很明显的知道使用布隆过滤器来解决问题。但是,我们需要很好地理解布隆过滤器所能解决问题的领域。像我们可以使用布隆过滤器来存放美国的所有城市,因为城市的数量是可以大概确定的,所以我们可以确定n(待检测元素的个数)的值。根据需求来修改p(误判概率)的值,在这种情况下,我们能够设计出一个查询耗时少,内存使用率高的缓存机制。

实现

Google Guava类库有一个实现,查看这个类的构造函数,在这里面需要设置待检测元素的个数与误判率。

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)

更多资料

相关文章

相关 [bloomfilter java 缓存] 推荐:

如何使用bloomfilter构建大型Java缓存系统

- - ImportNew
在如今的软件当中,缓存是解决很多问题的一个关键概念. 你的应用可能会进行CPU密集型运算. 你当然不想让这些运算一边又一边的重复执行,相反,你可以只执行一次, 把这个结果放在内存中作为缓存. 有时系统的瓶颈在I/O操作上,比如你不想重复的查询数据库,你想把结果缓存起来,只在数据发生变化时才去数据查询来更新缓存.

java使用memcached缓存

- - Linux - 操作系统 - ITeye博客
服务器端安装,部署,启动:. 用于监听的UNIX套接字路径(禁用网络支持) -a . UNIX套接字访问掩码,八进制数字(默认:0700) -m 指定最大使用内存大小(默认64MB). -t 线程数(默认4) -l 绑定地址 (默认:所有都允许,无论内外网或者本机更换IP,有安全隐患,若设置为127.0.0.1就只能本机访问) -d start 启动memcached服务.

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains(),作用分别是将元素加入其中以及判断一个元素是否在其中,类似于Java中的Set接口,它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法,当我们需要查询某个元素是否包含在BloomFilter中时,如果返回true,结果可能是不正确 的,也就是元素也有可能不在其中;但是如果返回的是false,那么元素一定不在其中.

写Java也得了解CPU缓存

- - 忘我的追寻
CPU,一般认为写C/C++的才需要了解,写高级语言的(Java/C#/pathon…)并不需要了解那么底层的东西. 我一开始也是这么想的,但直到碰到LMAX的 Disruptor,以及 马丁的博文,才发现写Java的,更加不能忽视CPU. 经过一段时间的阅读,希望总结一下自己的阅读后的感悟. 本文主要谈谈CPU缓存对Java编程的影响,不涉及具体CPU缓存的机制和实现.

BloomFilter--大规模数据处理利器

- - CSDN博客云计算推荐文章
Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法. 通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合.   为了说明Bloom Filter存在的重要意义,举一个实例:.   假设要你写一个网络蜘蛛(web crawler).

Hbase 布隆过滤器BloomFilter介绍

- - CSDN博客推荐文章
bloom filter的数据存在StoreFile的meta中,一旦写入无法更新,因为StoreFile是不可变的. Bloomfilter是一个列族(cf)级别的配置属性,如果你在表中设置了Bloomfilter,那么HBase会在生成StoreFile时包含一份bloomfilter结构的数据,称其为MetaBlock;MetaBlock与DataBlock(真实的KeyValue数据)一起由LRUBlockCache维护.

通过JAVA反射修改JDK1.6*当中DNS缓存内容

- - Taobao QA Team
为了实现性能压测时的域名动态绑定功能,尝试通过java反射修改JDK1.6×当中的DNS缓存,感谢在此过程中林轩同学的大力帮助. 网上也存在着修改DNS缓存的方法,但是都是基于jdk1.5的,无法应用. 另外,大部分都是修改的缓存过期时间,而没有真正去尝试修改dns 的cache内容,所以尝试了很多种方法,并且查看了jdk的源代码,终于实现了修改dns缓存内容和时间,如下,欢迎大家一起探讨.

从Java视角理解CPU缓存(CPU Cache)

- - 淘宝网通用产品团队博客
从Java视角理解系统结构连载, 关注我的微博( 链接)了解最新动态众所周知, CPU是计算机的大脑, 它负责执行程序的指令; 内存负责存数据, 包括程序自身数据. 同样大家都知道, 内存比CPU慢很多. 其实在30年前, CPU的频率和内存总线的频率在同一个级别, 访问内存只比访问CPU寄存器慢一点儿.

Java中的锁(Locks in Java)

- - 并发编程网 - ifeve.com
原文链接 作者:Jakob Jenkov 译者:申章 校对:丁一. 锁像synchronized同步块一样,是一种线程同步机制,但比Java中的synchronized同步块更复杂. 因为锁(以及其它更高级的线程同步机制)是由synchronized同步块的方式实现的,所以我们还不能完全摆脱synchronized关键字( 译者注:这说的是Java 5之前的情况).

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.