Bloomfilter和Cassandra =为什么使用和为什么散列几次？

Question

我阅读： http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html

我的问题：

1）它是正确的，那卡桑德拉仅使用布隆过滤器，找出SST（排序字符串表），这极有可能包含的关键？由于可能有几个SST和Cassandra不知道哪个SST可能是关键？所以为了加快这个速度，在所有SSTs中使用bloomfilters。它是否正确？ （我想了解卡桑德拉是如何工作的？）

2）为什么（在上面的链接）键哈希几次解释呢？是否正确，密钥需要用不同的哈希函数多次哈希，以获得更好的“比特的随机分布”？如果这是错误的，为什么一个密钥需要被多次散列？这会花费CPU周期吗？如果我有几个哈希函数的输出，那么结果是做什么的，它们是“与”还是“异或”。这有什么区别吗？

3）使用MD5多大的“费尔斯阳性使用布隆过滤器”相比，SHA1（其中根据物品不同的是随机分布的）？为什么MD5不是随机分布的？

非常感谢！ 延

Answer 1

1）是，看到在卡桑德拉维基this，

卡桑德拉使用布隆过滤器执行键查找时保存IO：每个的SSTable具有与它相关联的布隆过滤器，卡桑德拉做之前检查任何磁盘寻找，使不存在的键的查询几乎免费

columns of a key可能分布在几个sstables。如果不是布隆过滤器，每次读取密钥都必须读取每个sstable，这是非常昂贵的。通过使用bloom过滤器，cassandra几乎总是只需查看包含该键的数据的sstable。

2）This可能会给你更好的理解布隆过滤器。您散列k次以给出大小为m的数组中的独立位置。例如，如果A和B是该组中的元素，并且你有K = 2，您的散列函数MD5和SHA1，并且m = 16，则可以做

md5(A) % m = 7 
sha1(A) % m = 12 

md5(B) % m = 15 
sha1(B) % m = 12 

这给你M [7 ]，m [12]和m [15]适用于滤波器。

要查看C是在集，您做

md5(C) % m = 8 
sha1(C) % m = 12 

因为m [8]是假的，你知道C是不是在集，但是，对于d

md5(D) % m = 7 
sha1(D) % m = 15 

m [7]和m [15]都是正确的，但D不在集合中，因此D是误报。

这确实成本的CPU周期，但你所交易的CPU周期减少IO，这是有道理的卡桑德拉。

3）文章没有提到MD5。 md5是随机分布的，我猜想bloom滤波器的md5和sha-1之间的差别并不大。

Answer 2

作为sbridges答案的第三点的补充。

MD5和SHA-1是随机分布的，但是是密码散列函数。在实现任何类型的布隆过滤器时，性能中唯一的瓶颈是哈希时间。这就是为什么使用密码函数会降低应用程序性能的原因。

建议使用非密码哈希函数，如Murmur哈希。 This paper，建议构造和散列函数，如：

g(x) = h1(x) + i * h2(x) 

其中，g（x）是新的散列函数，h1和h2是标准的散列函数，i是迭代的范围从0到k中的数目。

通过使用这种技术，使用两个散列函数（假设k> 2）可以达到相同的性能。