You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Jonathan Ellis (JIRA)" <ji...@apache.org> on 2009/04/09 17:15:13 UTC
[jira] Created: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Bloom filters have much higher false-positive rate than expected
----------------------------------------------------------------
Key: CASSANDRA-68
URL: https://issues.apache.org/jira/browse/CASSANDRA-68
Project: Cassandra
Issue Type: Bug
Reporter: Jonathan Ellis
Assignee: Jonathan Ellis
Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by Jonathan Ellis <jb...@gmail.com>.
On Sat, Apr 11, 2009 at 9:53 PM, Prashant Malik <pm...@gmail.com> wrote:
> The results are a bit counter intuitive here I would have expected it to be
> faster with the same FP rate but I am not sure why it is slower if you are
> just using a couple of hash functions and using double hashing.
Murmur is a higher-quality hash and takes more operations to achieve
its better key distribution. But since the new implementation always
uses two calls to Murmur no matter how many hashes are needed it is
virtually constant time.
> I am sorry I haven't looked at the test code but have you tried it with
> large strings as keys ? e.g 128 byte keys , also with Longs.
The random strings generated are 128 bytes.
-Jonathan
Re: [jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by Jonathan Ellis <jb...@gmail.com>.
On Sat, Apr 11, 2009 at 9:53 PM, Prashant Malik <pm...@gmail.com> wrote:
> The results are a bit counter intuitive here I would have expected it to be
> faster with the same FP rate but I am not sure why it is slower if you are
> just using a couple of hash functions and using double hashing.
Murmur is a higher-quality hash and takes more operations to achieve
its better key distribution. But since the new implementation always
uses two calls to Murmur no matter how many hashes are needed it is
virtually constant time.
> I am sorry I haven't looked at the test code but have you tried it with
> large strings as keys ? e.g 128 byte keys , also with Longs.
The random strings generated are 128 bytes.
-Jonathan
Re: [jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by Prashant Malik <pm...@gmail.com>.
The results are a bit counter intuitive here I would have expected it to be
faster with the same FP rate but I am not sure why it is slower if you are
just using a couple of hash functions and using double hashing.
We had done these experiments a while back and found results matching with
the theoretical tables.
I am sorry I haven't looked at the test code but have you tried it with
large strings as keys ? e.g 128 byte keys , also with Longs.
But this is an interesting exercise for sure :).
Thanks
Prashant
On Sat, Apr 11, 2009 at 4:31 PM, Sandeep Tata (JIRA) <ji...@apache.org>wrote:
>
> [
> https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698145#action_12698145]
>
> Sandeep Tata commented on CASSANDRA-68:
> ---------------------------------------
>
> I ran some more tests, here's what I found:
>
> Old code:
> Test MAX_FP Actual FP
> FalsePositivesInt/Random 0.1 0.142
> FalsePositivesInt/Random 0.01 (pass)
> FalsePositivesInt/Random 0.001 (pass)
> Words 0.1 0.15
> Words 0.01 (pass)
> Words 0.001 0.0013
>
> New code:
>
> FalsePositivesInt/Random 0.1 (pass)
> FalsePositivesInt/Random 0.01 (pass)
> FalsePositivesInt/Random 0.001 (pass)
> Words 0.1 (pass)
> Words 0.01 (pass)
> Words 0.001 (pass)
>
> The old bloomfilter certainly reports up to 50% more than expected false
> positive rates for some cases. The new bloomfilter is more predictable, it
> always passes.
>
> On my machine, some quick-n-crude tests show that the new bloom-filter is
> about 4x slower. (I tested at FP rate = 0.01) . When you take into account
> the fact that the penalty for a false positive at least 3 orders of
> magnitude more expensive than the actual hash calculation (an FP usually
> means you'll end up hitting disk unnecessarily), it makes sense to use it
> even when you set the FP rate to 0.001. It is even more useful at higher
> rates.
>
> > Bloom filters have much higher false-positive rate than expected
> > ----------------------------------------------------------------
> >
> > Key: CASSANDRA-68
> > URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> > Project: Cassandra
> > Issue Type: Bug
> > Reporter: Jonathan Ellis
> > Assignee: Jonathan Ellis
> > Fix For: 0.3
> >
> > Attachments:
> 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch,
> 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch,
> 0003-rename-BloomFilter.fill-add.patch,
> 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch,
> 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch,
> 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch,
> fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
> >
> >
> > Gory details:
> http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
Re: [jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by Prashant Malik <pm...@gmail.com>.
The results are a bit counter intuitive here I would have expected it to be
faster with the same FP rate but I am not sure why it is slower if you are
just using a couple of hash functions and using double hashing.
We had done these experiments a while back and found results matching with
the theoretical tables.
I am sorry I haven't looked at the test code but have you tried it with
large strings as keys ? e.g 128 byte keys , also with Longs.
But this is an interesting exercise for sure :).
Thanks
Prashant
On Sat, Apr 11, 2009 at 4:31 PM, Sandeep Tata (JIRA) <ji...@apache.org>wrote:
>
> [
> https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698145#action_12698145]
>
> Sandeep Tata commented on CASSANDRA-68:
> ---------------------------------------
>
> I ran some more tests, here's what I found:
>
> Old code:
> Test MAX_FP Actual FP
> FalsePositivesInt/Random 0.1 0.142
> FalsePositivesInt/Random 0.01 (pass)
> FalsePositivesInt/Random 0.001 (pass)
> Words 0.1 0.15
> Words 0.01 (pass)
> Words 0.001 0.0013
>
> New code:
>
> FalsePositivesInt/Random 0.1 (pass)
> FalsePositivesInt/Random 0.01 (pass)
> FalsePositivesInt/Random 0.001 (pass)
> Words 0.1 (pass)
> Words 0.01 (pass)
> Words 0.001 (pass)
>
> The old bloomfilter certainly reports up to 50% more than expected false
> positive rates for some cases. The new bloomfilter is more predictable, it
> always passes.
>
> On my machine, some quick-n-crude tests show that the new bloom-filter is
> about 4x slower. (I tested at FP rate = 0.01) . When you take into account
> the fact that the penalty for a false positive at least 3 orders of
> magnitude more expensive than the actual hash calculation (an FP usually
> means you'll end up hitting disk unnecessarily), it makes sense to use it
> even when you set the FP rate to 0.001. It is even more useful at higher
> rates.
>
> > Bloom filters have much higher false-positive rate than expected
> > ----------------------------------------------------------------
> >
> > Key: CASSANDRA-68
> > URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> > Project: Cassandra
> > Issue Type: Bug
> > Reporter: Jonathan Ellis
> > Assignee: Jonathan Ellis
> > Fix For: 0.3
> >
> > Attachments:
> 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch,
> 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch,
> 0003-rename-BloomFilter.fill-add.patch,
> 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch,
> 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch,
> 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch,
> fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
> >
> >
> > Gory details:
> http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
>
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sandeep Tata updated CASSANDRA-68:
----------------------------------
Attachment: fp_test_for_old_code_v2.patch
If you want to compare the FP rates for before and after, first apply fp_test_for_old_code_v2.patch. The tests in BloomFilterTest print out the # false positives.
Roll back those patches and apply Jonathan's 1-4 to use the new bloomfilter.
(v2 of patch uses 10000 elements to be directly comparable to Jonathan's patches, v1 changed this value to 100000)
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697813#action_12697813 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
To answer the question from IRC:
The new hash generator is increasingly faster than the old as more hashes are needed. But the real win is in lower false positives, meaning the user has to do that much less of the far more expensive operations that it's trying to avoid by using a bloom filter in the first place.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697714#action_12697714 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
Made words test optional.
Also split 0004 changes into tests and code, but I don't think that's going to be too useful. If you want to test the old hash functions the easiest thing is probably to modify Filter.getHashBuckets to use the old hash functions instead.
But I remember that you will see from 50% to 200% more FP than you should. Sorry I don't have the code anymore. (Lost in a git rebase, apparently.)
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698411#action_12698411 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
Any further questions / comments / objections before we commit?
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch
2. replace JenkinsHash w/ MurmurHash. its hash distribution is just as good, and it's faster
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697984#action_12697984 ]
Sandeep Tata commented on CASSANDRA-68:
---------------------------------------
What we need now is some code so we can reproduce the false-positive rate comparison :-)
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697708#action_12697708 ]
Sandeep Tata commented on CASSANDRA-68:
---------------------------------------
Modify tests to catch FileNotFound for "/usr/share/dict/words" and not run those tests per conversation on irc.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch
Attached 0004-v3, which cleans out printlns and adds the FP ratio to the assertionerror.
Attached 0005, which switches to the old hash generation code on top of the new Filter + tests framework.
Several small tests always fail because of hash collisions where there should not be any. For our purposes these are noise except to confirm that the hash generation is broken.
False positives for testWords is the big red fail. 17% more FP than expected at MAX_FAILURE_RATE. of 0.1. Increase MFP to force more hases to be used and this goes up: 22% at 0.01, and 66% at 0.001. It would keep going up but we're maxing out the precalculated probabilities in BloomCalculations here. (A FP of 0.001 is _not_ all that low for a bloom filter, btw, but for what we are using it for so far it is probably adequate.)
Note also that testManyRandom fails because the old code is limited to 11 hashes. The new code can generate as many as needed.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch
4. rewrite bloom filters to use murmur hash and combinatorics to generate better hash values. (again: see blog post if you want details of approaches that were tried and rejected.) add test suite.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0004a-tests.patch
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697756#action_12697756 ]
Sandeep Tata commented on CASSANDRA-68:
---------------------------------------
+1
This is a large patch, but the code is structured nicely so it shouldn't be too hard for others to take a look.
I have 2 suggestions for changes:
1. Can you add short high-level comments describing the design of the Filter, BloomFilter, CountingBloomFilter classes so others who want to take a look at the patch get the idea quickly ?
2. Since this is a somewhat large patch, I'd wait a couple of days to check if people have questions:
a) the new bloomfilter is any faster/slower than the old one
b) they have some tests comparing false-positive rates of this vs old one.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sandeep Tata updated CASSANDRA-68:
----------------------------------
Attachment: fp_test_for_old_code.patch
Patch to run false positive tests on the old code -- based completely on Jonathan's unit tests that test the new bloomfilters.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch, fp_test_for_old_code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0004b-code.patch
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0003-rename-BloomFilter.fill-add.patch
3. rename BloomFilter.fill -> add
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0004-v3.patch
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697759#action_12697759 ]
Sandeep Tata commented on CASSANDRA-68:
---------------------------------------
The regression to watch for is if the bloomfilters sizes are significantly different. I'm guessing not : Jonathan -- do you have any estimates?
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697799#action_12697799 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
I commented getHashBuckets which is the core of the change. Those who are not familiar with bloom filters in general are referred to wikipedia. :)
Normal BloomFilter size is going to be the same as the old; both are based on a BitSet which is about as efficient as you can get.
CountingBloomFilter size is going to be half the size of the old since the old uses a full byte per bucket and this uses a half byte. (If you reach a count of 15 your filter is way too small to be useful anyway; there is no reason to allow a count of 255.)
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch
1. r/m unused code, including entire CountingBloomFilter
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697947#action_12697947 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
Avinash,
1. BC is not an issue. The numbers there are fine.
2. Yes, patch 4 adds back a new CBF that uses half the memory (by using a half byte per bucket instead of a full byte).
3. the problem is the hash functions themselves. to elaborate, the old code used a hardcoded list of hash functions which were NOT independent -- for 6 or less hash functions, these functions were only actually generating 2 distinct hash values, so the false positive rate was far far higher than would have been expected. After extensive comparsions with Jenkins, Murmur, and SHA-based approaches, it now generates hashes using Murmur as a base and then combinatorics as described here: http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
We're concluding it's faster based on the two weeks of testing I did. :) But the real win is getting to the theoretically predicted false positive rate instead of much higher.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Avinash Lakshman (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697944#action_12697944 ]
Avinash Lakshman commented on CASSANDRA-68:
-------------------------------------------
The reason I ask is the following:
(1) The Bloom Calculations table is straight out of some paper. I cannot quite recall now.
(2) THe Counting Bloom Filter is left there because I think it could still be used for certain purposes. So I wouldn't want to get rid of it too soon.
(3) We use 8 bits/element and 5 hash function to get the false positive rate as indicated by the paper in its table which is captured in the Bloom Calculations.
So how are we concluding which hash is faster based on what scientific evidence? I am not quite sure I follow the rest of the comments w.r.t. the justification of this patch.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698410#action_12698410 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
Prashant wrote on the mailing list:
"The results are a bit counter intuitive here I would have expected it to be faster with the same FP rate but I am not sure why it is slower if you are just using a couple of hash functions and using double hashing... I am sorry I haven't looked at the test code but have you tried it with large strings as keys ? e.g 128 byte keys , also with Longs."
I replied:
"Murmur is a higher-quality hash and takes more operations to achieve its better key distribution. But since the new implementation always uses two calls to Murmur no matter how many hashes are needed it is virtually constant time. The random strings generated are 128 bytes."
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697991#action_12697991 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
Fine. Here is a simple test that demonstrates the problem on the old code that you could have written in about a minute:
public class BloomFilterTest
{
@Test
public void testHashes() {
Set<Integer> hashResults = new HashSet<Integer>();
for (ISimpleHash hash : BloomFilter.hashLibrary_) {
hashResults.add(hash.hash("1"));
}
assert hashResults.size() == BloomFilter.hashLibrary_.size() : hashResults.size();
}
}
This shows that the old hash functions only generate 5 unique values (from 11 functions). A little inspection will show that only 2 of those are in the first six, as I mentioned above.
If that doesn't tell you "oh yeah the false positive rate will be the roof" then you need to read the wikipedia page on Bloom filters. :)
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12699356#action_12699356 ]
Jonathan Ellis commented on CASSANDRA-68:
-----------------------------------------
One other point that is probably obvious: this change is incompatible with old serialized bloomfilters since the hash values for a given key necessarily change.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Fix Version/s: 0.3
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-68:
------------------------------------
Attachment: words.gz
here is the /usr/share/dict//words I'm using (gzipped). it's the one from ubuntu 8.10 wamerican package.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Avinash Lakshman (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12697939#action_12697939 ]
Avinash Lakshman commented on CASSANDRA-68:
-------------------------------------------
What's the problem here again? Not sure I follow? What is the fundamental reason for any change here?
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004a-tests.patch, 0004b-code.patch
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-68) Bloom filters have much higher
false-positive rate than expected
Posted by "Sandeep Tata (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-68?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12698145#action_12698145 ]
Sandeep Tata commented on CASSANDRA-68:
---------------------------------------
I ran some more tests, here's what I found:
Old code:
Test MAX_FP Actual FP
FalsePositivesInt/Random 0.1 0.142
FalsePositivesInt/Random 0.01 (pass)
FalsePositivesInt/Random 0.001 (pass)
Words 0.1 0.15
Words 0.01 (pass)
Words 0.001 0.0013
New code:
FalsePositivesInt/Random 0.1 (pass)
FalsePositivesInt/Random 0.01 (pass)
FalsePositivesInt/Random 0.001 (pass)
Words 0.1 (pass)
Words 0.01 (pass)
Words 0.001 (pass)
The old bloomfilter certainly reports up to 50% more than expected false positive rates for some cases. The new bloomfilter is more predictable, it always passes.
On my machine, some quick-n-crude tests show that the new bloom-filter is about 4x slower. (I tested at FP rate = 0.01) . When you take into account the fact that the penalty for a false positive at least 3 orders of magnitude more expensive than the actual hash calculation (an FP usually means you'll end up hitting disk unnecessarily), it makes sense to use it even when you set the FP rate to 0.001. It is even more useful at higher rates.
> Bloom filters have much higher false-positive rate than expected
> ----------------------------------------------------------------
>
> Key: CASSANDRA-68
> URL: https://issues.apache.org/jira/browse/CASSANDRA-68
> Project: Cassandra
> Issue Type: Bug
> Reporter: Jonathan Ellis
> Assignee: Jonathan Ellis
> Fix For: 0.3
>
> Attachments: 0001-r-m-unused-code-including-entire-CountingBloomFilte.patch, 0002-replace-JenkinsHash-w-MurmurHash.-its-hash-distrib.patch, 0003-rename-BloomFilter.fill-add.patch, 0004-rewrite-bloom-filters-to-use-murmur-hash-and-combina.patch, 0004-v3.patch, 0004a-tests.patch, 0004b-code.patch, 0005-switch-back-to-old-hash-generation-code-to-demonstra.patch, fp_test_for_old_code.patch, fp_test_for_old_code_v2.patch, words.gz
>
>
> Gory details: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.