cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ryan King (JIRA)" <j...@apache.org>
Subject [jira] Updated: (CASSANDRA-1555) Considerations for larger bloom filters
Date Fri, 03 Dec 2010 23:18:14 GMT

     [ https://issues.apache.org/jira/browse/CASSANDRA-1555?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Ryan King updated CASSANDRA-1555:
---------------------------------

    Attachment: CASSANDRA-1555v2.patch

Here's a patch that takes a better approach-

It uses the SSTable version to tell which type of bloomfilter to use. In order to make this
work I had to do some refactorings in the Iterators. There were a number of places where we
were passing around CFMetaData objects, where a SSTableReader would be better because it would
allow us to get at the Descriptor for that table. AFAICT all the callpoints had an SSTableReader
available, so this refactoring was not very intrusive.

The new thing is the BigBloomFilter, which uses OpenBitset and LongMurmurHash. Some of it
is copy/paste from BloomFilter.

All unit and system test pass, but this could use some more testing, for sure, especially
around the upgrade path.

Also, the LongMurmurHash seems to have more collisions. I'll see if I can figure out why.

One other note: FilterTest became FilterTestHelper because it no longer has any test methods
of its own.

> 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
>            Assignee: Ryan King
>             Fix For: 0.8
>
>         Attachments: cassandra-1555.tgz, CASSANDRA-1555v2.patch
>
>
> 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.


Mime
View raw message