[CASSANDRA-1555] Considerations for larger bloom filters

• Type: Improvement
• Status: Resolved
• Priority: Normal
• Resolution: Fixed
• Fix Version/s: 0.7.1
• Assignee: Ryan King
• Reporter: Stu Hood

Authors

Ryan King

Reviewers

T Jake Luciani

• Created: 29/Sep/10 04:44
• Updated: 16/Apr/19 09:33
• Resolved: 24/Dec/10 18:00

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.

Issue Links

• is related to: CASSANDRA-4303 Compressed bloomfilters
• relates to: CASSANDRA-790 SSTables limited to (2^31)/15 keys