You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Stu Hood (JIRA)" <ji...@apache.org> on 2010/09/29 06:44:33 UTC
[jira] Created: (CASSANDRA-1555) Considerations for larger bloom
filters
Considerations for larger bloom filters
---------------------------------------
Key: CASSANDRA-1555
URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
Project: Cassandra
Issue Type: Improvement
Components: Core
Reporter: Stu Hood
Fix For: 0.8
To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
A few options:
* Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
* Partition the java.util.BitSet behind our current BloomFilter
** Straightforward bit partitioning: bit N is in bitset N // 2^31
** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916174#action_12916174 ]
Stu Hood commented on CASSANDRA-1555:
-------------------------------------
> EWAH looks interesting. Would be interesting to see what that does for our BF.
I looked at it a bit more: it can't set() bits in random order (must ascend) and doesn't appear to support more than 2^31 bits. So we'd need another solution for filter creation, although we could compress into an EWAH at load time.
> More generally I suspect that degrading BF FP rate for extremely skinny rows can actually be the right thing to do.
rcoli posted a usecase for ~240 million rows in ~90GB of data: I wouldn't call ~400 bytes extremely skinny, but 90GB is way too early to be degrading performance.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Ryan King (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12923172#action_12923172 ]
Ryan King commented on CASSANDRA-1555:
--------------------------------------
We have a patch to deal with having larger bitsets. I'm in the process of making it into a patchset but wanted to make some comments and get feedback first.
Its not based on the lucent bitset or EWAH for a couple reasons (which might not be totally legit):
EWAH looks like it might be useful for reducing on-disk storage for BFs, but it doesn't appear to be useful for in-memory usage because the cost of checking a bit is linear, not constant. That seems like a serious performance degradation that's not even worth considering. And reducing the storage footprint for BFs seems like the least of our concerns at this point (not that we should never do it).
Lucene's OpenBitSet is implemented as an array of longs and looks genuinely useful and would allow us to have BFs of up to 64\*2\*\*32-1 bits (274,877,906,943). Our implementation [http://github.com/kakugawa/cassandra/compare/fbb7c26acde572abf625...cassandra-0.6-counts-bf#diff-5] uses an array of BitSets and can therefore handle up to 2\*\*30*2\*\*31 bits (2.30584301 x 10\*\*18). That's quite a bit more bits, but I'm not sure if its worth it if the lucene approach can cover us.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916030#action_12916030 ]
Stu Hood commented on CASSANDRA-1555:
-------------------------------------
Also interesting: http://code.google.com/p/javaewah/
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916201#action_12916201 ]
Stu Hood commented on CASSANDRA-1555:
-------------------------------------
> If we're "degrading" from 6.71e-05 to 0.00108 FP to save memory, then yes, that's definitely the right thing to do
They were actually at 0.0229 FP, but point taken.
> it would still be nice to be able to configure the BF FP rate
Perhaps. But, that doesn't excuse us from finding reasonable defaults.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (CASSANDRA-1555) Considerations for
larger bloom filters
Posted by "Ryan King (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12923172#action_12923172 ]
Ryan King edited comment on CASSANDRA-1555 at 10/20/10 5:22 PM:
----------------------------------------------------------------
We have a patch to deal with having larger bitsets. I'm in the process of making it into a patchset but wanted to make some comments and get feedback first.
Its not based on the lucent bitset or EWAH for a couple reasons (which might not be totally legit):
EWAH looks like it might be useful for reducing on-disk storage for BFs, but it doesn't appear to be useful for in-memory usage because the cost of checking a bit is linear, not constant. That seems like a serious performance degradation that's not even worth considering. And reducing the storage footprint for BFs seems like the least of our concerns at this point (not that we should never do it).
Lucene's OpenBitSet is implemented as an array of longs and looks genuinely useful and would allow us to have BFs of up to 64\*2\*\*32-1 bits (274,877,906,943). Our implementation [http://github.com/kakugawa/cassandra/compare/fbb7c26acde572abf625...cassandra-0.6-counts-bf#diff-5] uses an array of BitSets and can therefore handle up to 2\*\*30*2\*\*31 bits (2.30584301 x 10\*\*18). That's quite a bit more bits, but I'm not sure if its worth it if the lucene approach can cover us.
UPDATE: note that the lucene impl is 17 GB worth of data. I doubt we'd go over that anytime soon.
was (Author: kingryan):
We have a patch to deal with having larger bitsets. I'm in the process of making it into a patchset but wanted to make some comments and get feedback first.
Its not based on the lucent bitset or EWAH for a couple reasons (which might not be totally legit):
EWAH looks like it might be useful for reducing on-disk storage for BFs, but it doesn't appear to be useful for in-memory usage because the cost of checking a bit is linear, not constant. That seems like a serious performance degradation that's not even worth considering. And reducing the storage footprint for BFs seems like the least of our concerns at this point (not that we should never do it).
Lucene's OpenBitSet is implemented as an array of longs and looks genuinely useful and would allow us to have BFs of up to 64\*2\*\*32-1 bits (274,877,906,943). Our implementation [http://github.com/kakugawa/cassandra/compare/fbb7c26acde572abf625...cassandra-0.6-counts-bf#diff-5] uses an array of BitSets and can therefore handle up to 2\*\*30*2\*\*31 bits (2.30584301 x 10\*\*18). That's quite a bit more bits, but I'm not sure if its worth it if the lucene approach can cover us.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Sylvain Lebresne (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916178#action_12916178 ]
Sylvain Lebresne commented on CASSANDRA-1555:
---------------------------------------------
Even if we should probably have a way to support big BF, it would still be nice to be able to
configure the BF FP rate. 2+GB for BFs can start to be an heavy weight on your memory.
For some loads, it could be better to actually keep your memory for row cache for instance.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916139#action_12916139 ]
Jonathan Ellis commented on CASSANDRA-1555:
-------------------------------------------
EWAH looks interesting. Would be interesting to see what that does for our BF.
(More generally I suspect that degrading BF FP rate for extremely skinny rows can actually be the right thing to do.)
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Jonathan Ellis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12916184#action_12916184 ]
Jonathan Ellis commented on CASSANDRA-1555:
-------------------------------------------
bq. 90GB is way too early to be degrading performance
Well, that depends. If we're "degrading" from 6.71e-05 to 0.00108 FP to save memory, then yes, that's definitely the right thing to do or even a 16GB heap will get exhausted pretty quickly. But if we're having to degrade to > 1% FP then that would be something to address.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (CASSANDRA-1555) Considerations for larger bloom
filters
Posted by "Stu Hood (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Stu Hood updated CASSANDRA-1555:
--------------------------------
Description:
To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2^31 bits, which java.util.BitSet can't handle directly.
A few options:
* Switch to a BitSet class which supports 2^31 * 64 bits (Lucene's OpenBitSet)
* Partition the java.util.BitSet behind our current BloomFilter
** Straightforward bit partitioning: bit N is in bitset N // 2^31
** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
All of these options require new approaches to serialization.
was:
To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2 GB, which java.util.BitSet can't handle directly.
A few options:
* Switch to a BitSet class which supports 2^63 bits (Lucene's OpenBitSet)
* Partition the java.util.BitSet behind our current BloomFilter
** Straightforward bit partitioning: bit N is in bitset N // 2^31
** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
All of these options require new approaches to serialization.
Well that's embarrassing.
> Considerations for larger bloom filters
> ---------------------------------------
>
> Key: CASSANDRA-1555
> URL: https://issues.apache.org/jira/browse/CASSANDRA-1555
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Stu Hood
> Fix For: 0.8
>
>
> To (optimally) support SSTables larger than 143 million keys, we need to support bloom filters larger than 2^31 bits, which java.util.BitSet can't handle directly.
> A few options:
> * Switch to a BitSet class which supports 2^31 * 64 bits (Lucene's OpenBitSet)
> * Partition the java.util.BitSet behind our current BloomFilter
> ** Straightforward bit partitioning: bit N is in bitset N // 2^31
> ** Separate equally sized complete bloom filters for member ranges, which can be used independently or OR'd together under memory pressure.
> All of these options require new approaches to serialization.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.