Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Message-ID: <2457897.103071291418294776.JavaMail.jira@thor>
Date: Fri, 3 Dec 2010 18:18:14 -0500 (EST)
From: "Ryan King (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Subject: [jira] Updated: (CASSANDRA-1555) Considerations for larger bloom
 filters
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


     [ 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.