incubator-cassandra-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Benjamin>
Subject Re: boonfilters
Date Wed, 07 Apr 2010 23:26:08 GMT
(Should mention: suggesting reading the Dynamo paper for general
background, not for Bloom filters, which are fantastically covered in
the Wikipedia entry).

On Wed, Apr 7, 2010 at 4:11 PM, Benjamin Black <> wrote:
> Please read this:
> On Wed, Apr 7, 2010 at 1:27 PM, S Ahmed <> wrote:
>> Just reading up on boonfilters, few questions.
>> Basically boonfilters let give you a true/false if a particular key exists,
>> and they *may* give you a false positive i.e. they key exists but never a
>> false negative i.e. the key doesn't exist.
>> The core of boonfilters is its hashing mechanism that marks the in-memory
>> matrix/map if the key exists.
>> 1. Is the only place boonfilters are used in Cassandra is when you want to
>> see if a particular key exists in a particular node?
>> 2. Are boonfilters a fixed size, or they adjust as to the # of keys?  any
>> example size?
>> 3. Boonfilters don't give false negatives:
>>    So you hit a node, and perform a lookup in the boonfilter for a key.  It
>> says "yes", but when you do a lookup the object returned is null, so then
>> you flag that this node needs this particular key during replication.
>> Have I grasp this concept?
>> Really loving this project, learning allot from the code.  It would be great
>> if someone could do a walkthrough of common functionality in a detailed way
>> :)

View raw message