I Read this: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
My Questions:
1.) Is it correct, that Cassandra only uses the bloom filter, to find out the SST (Sorted String Table) which most likely contains the key? As there might be several SSTs and Cassandra does not know in Which SST a key might be? So to speed this up looking in all SSTs bloomfilters are used. Is this correct? (I am trying to understand how cassandra works...)
2.) Why are (as explained in the link above) keys hashed several times? Is it correct that the keys need to be hashed with different Hash functions several times, to get a better "random distribution of the" Bits? If this is wrong, why does a key need to be hashed several times? This will cost CPU cycles? If I have the output of several Hash functions, what is done with the results, are they ANDed or XORded. Does this make any difference?
3.)Using MD5 how big is the difference of "Fales positives by using the Bloomfilter" compared to SHA1 (which according to the articles is random distributed)? Why is MD5 not random distributed?
Thanks very much!! Jens
1) Yes, see this in the cassandra wiki,
Cassandra uses bloom filters to save IO when performing a key lookup: each SSTable has a bloom filter associated with it that Cassandra checks before doing any disk seeks, making queries for keys that don't exist almost free
The columns of a key may be spread out in several sstables. If it wasn't for bloom filters, every read of a key would have to read every sstable, which is prohibitively expensive. By using bloom filters, cassandra almost always only has to look in the sstables which contain data for that key.
2) This might give you a better understanding of bloom filters. You hash k times to give independent positions in an array of size m. For example, if A and B are the elements in the set, and you have k = 2, your hash functions are md5 and sha1, and m = 16, you can do
md5(A) % m = 7
sha1(A) % m = 12
md5(B) % m = 15
sha1(B) % m = 12
This gives you m[7], m[12] and m[15] are true for the filter.
To see if C is in the set, you do
md5(C) % m = 8
sha1(C) % m = 12
Since m[8] is false, you know C is not in the set, however, for D
md5(D) % m = 7
sha1(D) % m = 15
Both m[7] and m[15] is true, but D is not in the set, so D is a false positive.
This does cost cpu cycles, but you are trading cpu cycles for reduced io, which makes sense for cassandra.
3) The article doesn't mention md5. md5 is randomly distributed, and I would guess the difference between md5 and sha-1 for bloom filters is not large.