jen*_*ens 7 hash bloom-filter cassandra
我读了这个:http: //spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
我的问题:
1.)是否正确,Cassandra只使用布隆过滤器,找出最有可能包含密钥的SST(排序字符串表)？由于可能存在多个SST并且Cassandra不知道哪个SST可能是密钥？因此,为了加速查看所有SST,使用bloomfilters.它是否正确？(我想了解卡桑德拉是如何工作的......)
2.)为什么(如上面的链接中所解释)键经过几次哈希？是否正确需要多次使用不同的Hash函数进行哈希处理才能获得更好的"随机分布"位？如果这是错误的,为什么需要多次对密钥进行哈希处理？这会耗费CPU周期吗？如果我有几个Hash函数的输出,那么对结果做了什么,它们是ANDed还是XORded.这有什么不同吗？
3.)使用MD5与SHA1(根据文章是随机分布的)相比,"使用Bloomfilter来衡量积极因素"的差异有多大？为什么MD5不是随机分布的？
非常感谢!!延
sbr*_*ges 13
1)是的,看到这个在卡桑德拉维基,
Cassandra在执行密钥查找时使用bloom过滤器来保存IO:每个SSTable都有一个与之关联的Bloom过滤器,Cassandra会在进行任何磁盘搜索之前进行检查,从而对几乎不存在的密钥进行查询
密钥的列可以分散在几个sstables中.如果它不是用于布隆过滤器,那么每次读取一个密钥都必须读取每个sstable,这非常昂贵.通过使用bloom过滤器,cassandra几乎总是只需查看包含该键数据的sstables.
2)这可能会让您更好地了解布隆过滤器.您散列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,这对于cassandra是有意义的.
3)文章没有提到md5.md5是随机分布的,我猜测布隆过滤器的md5和sha-1之间的差异并不大.