全部博文（330）
分类：
2011-06-05 15:46:28
从这篇文章开始，我会陆续介绍一些bloom filter的应用。Bloom filter于1970年由Burton Bloom在一篇名为的论文中提出。这篇论文同时将bloom filter（论文中不叫这个，只说是一种哈希方法，Bloom还没有自负到直接将其命名为bloom filter，呵呵）应用在拼写检查中。从此以后，bloom filter就被广泛用于拼写检查之类的字典应用以及数据库中。到了90年代，bloom filter又赶上了网络和Web的浪潮，重新焕发了青春，各种变种和网络应用层出不穷。今天要介绍的summary cache就是bloom filter一个经典的分布式应用。
今天，web caching的概念已经得到广泛接受。为了减少带宽使用、降低web server的负载，我们常常通过代理服务器（proxy）浏览网页，浏览过的网页会被cache在proxy中，如果有别的请求或者下一次访问相同的网页，proxy就不用将请求转给web server，而是直接将本地cache的网页返回。当然，网页是经常变化的，因此proxy在返回cache的网页之前会做一些检查，只有满足特定的条件之后才会使用cache的网页，以保证client得到的不是过期的网页。
一旦网络中存在很多proxy，我们自然希望它们之间能够共享cache，这样可以进一步减少对web server的访问，web cache sharing的概念就由此而来。在bloom filter被提议应用在web cache sharing之前，Internet Cache Protocol（ICP）作为一种web cache之间相互协作的协议已经被广泛应用。ICP的设计思路是，proxy中只要有cache miss发生，马上发送查询消息给它邻近的proxy，看能不能在它们的cache中找到相关的网页。这种方案随着proxy数量的增加，网络通信量和proxy的CPU占用率都成二次方增长，因此扩展性很差，并有很大的开销。为了减少这些开销，一篇名为的论文提出了一种名为Summary Cache的协议。也就是在这篇文章中，Counting Bloom Filter被提出。
Summary Cache采用了和ICP完全不同的设计思路。为了proxy之间能够协作，它们必须知道彼此cache的内容。ICP采用的是实时获取的方案，需要协作时才发请求广播式地查询。这样当然获取的信息是最准确的，但也导致通信的开销很大。Summary cache利用了这样一个简单的事实：proxy中的cache在短时间内不会有很大幅度的变化。因此它希望将proxy中cache的内容用简洁的形式表示（cache summary），让每个proxy保存所有其它proxy的cache summary，然后定期更新summary。这样一来，每当cache miss发生时，proxy会首先检查自己保存的所有cache summary，然后将请求发给那些检查结果为“有”的proxy。
这种设计有两个关键的点需要认真考虑，一个是cache summary更新的频率，另一个是如何简洁地表示cache的内容，即如何构建cache summary。对于第一个问题，论文作者的回答是，当cache更新的内容在1%－10%之间时发送更新信息，或者每隔一段时间发送更新，这段时间的长度也应该保证cache的更新幅度在1%－10%之间。对于第二个问题，你应该已经猜出答案了，就是用bloom filter。每一个cache的网页由URL唯一标识，因此proxy的cache内容可以表示为一个URL列表。进而我们可以将URL列表这个集合用bloom filter表示，从而支持membership query。当false positive发生时，无非是请求的proxy以为另一个proxy有某个网页而实际没有，这样会造成一定的延时。由于cache的网页本身就有可能过期，因此很低的false positive概率很难造成什么影响。在cache更新后通知其它proxy时，有两种选择，一种是发送整个更新后的bloom filter，另一种是只发送bloom filter的更新位置。前者适合在更新频率较低的情况下使用，后者在更新频率高的情况下使用。
另外，前面提到这篇论文提出了Counting Bloom Filter（CBF），下面我们就介绍一下它的应用。Proxy在发送cache summary以及保存其它proxy的cache summary时，无疑使用的是占用空间更少的标准bloom filter。但是proxy同时要表示自己本地的cache集合，由于本地的cache不断加入新的网页，也不断移除不经常使用的网页，因此是一个动态变化的集合。标准bloom filter不支持删除操作，因此不能胜任这个工作。为了避免不断重建bloom filter，作者通过把bloom filter中的每一位扩展为一个counter来支持删除操作，同时，位到counter的扩展使得CBF到bloom filter的转化非常方便。从这个应用我们也可以看到，很多情况下我们需要bloom filter支持删除操作，但同时也希望支持删除操作之后还能还原为标准的bloom filter，以减少网络传输的信息量。
相比ICP，我们可以看到Summary Cache用不是最新、也不精确的cache summary换取了可扩展性。由于cache本身具有一定的过期性，summary cache牺牲的一点精确性很难对整个cache的命中率产生什么影响。论文作者通过实验比较，发现ICP和summary cache在命中率上几乎相同，但summary cache将网络通信量和proxy的CPU占用率大幅减少。这个例子很典型地说明了将bloom filter用在对错误有一定容忍度的应用场合时带来的巨大好处，同时也印证了bloom filter“正确率换空间”的思想在网络环境下有很大的应用空间。
