boonfilters

[S Ahmed <sa...@gmail.com>]

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
:)

Re: boonfilters

[Benjamin Black <b...@b3k.us>]

(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 <b...@b3k.us> wrote:
> Please read this:
> http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
>
> On Wed, Apr 7, 2010 at 1:27 PM, S Ahmed <sa...@gmail.com> 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
>> :)
>>
>

Re: boonfilters

[Benjamin Black <b...@b3k.us>]

Please read this:
http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html

On Wed, Apr 7, 2010 at 1:27 PM, S Ahmed <sa...@gmail.com> 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
> :)
>

Re: boonfilters

[Jonathan Ellis <jb...@gmail.com>]

2010/4/7 Peter Schüller <sc...@spotify.com>:
> Bloom filters are by their very nature lossy in the sense that you
> cannot determine later what you put into it. Re-sizing a bloom filter
> implies re-creating it from scratch. I'm not sure what cassandra does
> however.

Since our data files are immutable we don't have to worry about that;
we just create a new filter of the appropriate size when we perform
compaction.

Re: boonfilters

[Jonathan Ellis <jb...@gmail.com>]

2010/4/7 Peter Schüller <sc...@spotify.com>:
> Someone correct me if I'm wrong, but my understanding is that the
> bloom filters are only used to optimize the case of a key being
> non-existent, such that you only have to go down on disk for a very
> small number of requests for non-existent keys. I do not believe bloom
> filters have any interaction with replication. The reason to use a
> bloom filter is that it trades great memory efficiency for the
> possibility of false positives.

We also use row-level bloom filters when you request columns by name
(as opposed to by slice).

-Jonathan

Re: boonfilters

[David Strauss <da...@fourkitchens.com>]

On 2010-04-07 20:34, Peter Schüller wrote:
> Re-sizing a bloom filter implies re-creating it from scratch.

Not necessarily. Depending on your hash, you can sometimes shrink
without regeneration (and without other penalties). It's also sometimes
possible to enlarge the bloom filter without regeneration at the cost of
increased false positives you wouldn't have if you regenerated.

Here's a trivial counterexample to your statement, starting with a bloom
filter with two positions: odd and even.

I can shrink it down to a single bit with an "or" operation. I can
enlarge it to modulo 10 by filling in the odd bits if my current odd bit
is filled and the same with the even numbers and bit.

In the case of the shrink operation, I'm not regenerating or losing any
accuracy. In the case of the enlarge operation, I'll get considerably
more false positives than I would on regeneration, but my operation is
still correct.

Even with complex or cryptographic hashes, a bloom filter based on
using, say, the first X bits might be expandable or shrinkable without
regeneration.

-- 
David Strauss
   | david@fourkitchens.com
Four Kitchens
   | http://fourkitchens.com
   | +1 512 454 6659 [office]
   | +1 512 870 8453 [direct]

Re: Bloom Filters

[Jeff Schmitz <je...@me.com>]

I think D Boon from Minutemen RIP

Sent from my iPhone

On Apr 8, 2010, at 11:06 AM, Tatu Saloranta <ts...@gmail.com>  
wrote:

> On Thu, Apr 8, 2010 at 5:05 AM, Ran Tavory <ra...@gmail.com> wrote:
>> +1 For boon.
>> I kinda liked it...
>
> :-)
>
> Surely we can find a minor tweak to bloom, and call "enhanced version
> Boon filter. Plus there's plenty of related names from thereon! (boom,
> booze etc).
>
> -+ Tatu +-

Re: Bloom Filters

[Tatu Saloranta <ts...@gmail.com>]

On Thu, Apr 8, 2010 at 5:05 AM, Ran Tavory <ra...@gmail.com> wrote:
> +1 For boon.
> I kinda liked it...

:-)

Surely we can find a minor tweak to bloom, and call "enhanced version
Boon filter. Plus there's plenty of related names from thereon! (boom,
booze etc).

-+ Tatu +-

Re: Bloom Filters

[S Ahmed <sa...@gmail.com>]

hehe, sorry guys.

On Thu, Apr 8, 2010 at 8:05 AM, Ran Tavory <ra...@gmail.com> wrote:

> +1 For boon.
> I kinda liked it...
>
> On Apr 8, 2010 3:03 PM, "Jeff Schmitz" <je...@me.com> wrote:
>
> That typo in subject line was driving me nuts
>
> Sent from my iPhone
>
> On Apr 8, 2010, at 2:04 AM, gabriele renzi <rf...@gmail.com> wrote:
>
>  2010/4/7 Peter Schüller <sc...@spotify.com>:
> >
> >> (bloomfilters, not boonfilters)
> >>
> >> Speaking in general, not specific to cassandra:
> >>
> >>  2. Are boonfilters a fixed size, or they adjust as to the # of keys?
>  any
> >>> example size?
> >>>
> >>
> >> Bloom filters are by their very nature lossy in the sense that you
> >> cannot determine later what you put into it. Re-sizing a bloom filter
> >> implies re-creating it from scratch. I'm not sure what cassandra does
> >> however.
> >>
> >
> > i believe traditional bloom filters requires you to recreate it from
> > scratch, but there are bloom filters that adapt dinamically to the
> > number of elements stored keeping the error rate constant (IIRC the
> > paper describing them was just "Scalable Bloom Filters").
> >
> >
> >
> >
> > --
> > blog en: http://www.riffraff.info
> > blog it: http://riffraff.blogsome.com
> >
>

Re: Bloom Filters

[Ran Tavory <ra...@gmail.com>]

+1 For boon.
I kinda liked it...

On Apr 8, 2010 3:03 PM, "Jeff Schmitz" <je...@me.com> wrote:

That typo in subject line was driving me nuts

Sent from my iPhone

On Apr 8, 2010, at 2:04 AM, gabriele renzi <rf...@gmail.com> wrote:

 2010/4/7 Peter Schüller <sc...@spotify.com>:
>
>> (bloomfilters, not boonfilters)
>>
>> Speaking in general, not specific to cassandra:
>>
>>  2. Are boonfilters a fixed size, or they adjust as to the # of keys?  any
>>> example size?
>>>
>>
>> Bloom filters are by their very nature lossy in the sense that you
>> cannot determine later what you put into it. Re-sizing a bloom filter
>> implies re-creating it from scratch. I'm not sure what cassandra does
>> however.
>>
>
> i believe traditional bloom filters requires you to recreate it from
> scratch, but there are bloom filters that adapt dinamically to the
> number of elements stored keeping the error rate constant (IIRC the
> paper describing them was just "Scalable Bloom Filters").
>
>
>
>
> --
> blog en: http://www.riffraff.info
> blog it: http://riffraff.blogsome.com
>

Bloom Filters

[Jeff Schmitz <je...@me.com>]

That typo in subject line was driving me nuts

Sent from my iPhone

On Apr 8, 2010, at 2:04 AM, gabriele renzi <rf...@gmail.com> wrote:

> 2010/4/7 Peter Schüller <sc...@spotify.com>:
>> (bloomfilters, not boonfilters)
>>
>> Speaking in general, not specific to cassandra:
>>
>>> 2. Are boonfilters a fixed size, or they adjust as to the # of  
>>> keys?  any
>>> example size?
>>
>> Bloom filters are by their very nature lossy in the sense that you
>> cannot determine later what you put into it. Re-sizing a bloom filter
>> implies re-creating it from scratch. I'm not sure what cassandra does
>> however.
>
> i believe traditional bloom filters requires you to recreate it from
> scratch, but there are bloom filters that adapt dinamically to the
> number of elements stored keeping the error rate constant (IIRC the
> paper describing them was just "Scalable Bloom Filters").
>
>
>
>
> -- 
> blog en: http://www.riffraff.info
> blog it: http://riffraff.blogsome.com

Re: boonfilters

[gabriele renzi <rf...@gmail.com>]

2010/4/7 Peter Schüller <sc...@spotify.com>:
> (bloomfilters, not boonfilters)
>
> Speaking in general, not specific to cassandra:
>
>> 2. Are boonfilters a fixed size, or they adjust as to the # of keys?  any
>> example size?
>
> Bloom filters are by their very nature lossy in the sense that you
> cannot determine later what you put into it. Re-sizing a bloom filter
> implies re-creating it from scratch. I'm not sure what cassandra does
> however.

i believe traditional bloom filters requires you to recreate it from
scratch, but there are bloom filters that adapt dinamically to the
number of elements stored keeping the error rate constant (IIRC the
paper describing them was just "Scalable Bloom Filters").




-- 
blog en: http://www.riffraff.info
blog it: http://riffraff.blogsome.com

Re: boonfilters

[Peter Schüller <sc...@spotify.com>]

(bloomfilters, not boonfilters)

Speaking in general, not specific to cassandra:

> 2. Are boonfilters a fixed size, or they adjust as to the # of keys?  any
> example size?

Bloom filters are by their very nature lossy in the sense that you
cannot determine later what you put into it. Re-sizing a bloom filter
implies re-creating it from scratch. I'm not sure what cassandra does
however.

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

Someone correct me if I'm wrong, but my understanding is that the
bloom filters are only used to optimize the case of a key being
non-existent, such that you only have to go down on disk for a very
small number of requests for non-existent keys. I do not believe bloom
filters have any interaction with replication. The reason to use a
bloom filter is that it trades great memory efficiency for the
possibility of false positives.

-- 
/ Peter Schuller aka scode

RE: boonfilters

[Stu Hood <st...@rackspace.com>]

> 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?
Each node stores a set of SSTables locally, each with a BloomFilter attached: the filters are used to check whether a particular SSTable contains information about a key/row. See http://wiki.apache.org/cassandra/MemtableSSTable for more information on SSTables.

> 2. Are boonfilters a fixed size, or they adjust as to the # of keys?  any
> example size?
Since SSTables are immutable once written, the BloomFilter for an SSTable has a fixed size based on the number of keys that will be stored in the SSTable. There are calculations embedded in Cassandra that attempt to make an optimal size/false positive tradeoff: see org.apache.cassandra.utils.BloomCalculations.

> 3. ...
> It says "yes", but when you do a lookup the object returned is null
No: the BloomFilter answers the question "might there be data for this key in this SSTable?", and the two possible answers it can give are "maybe" or "definitely not". When the BloomFilter says "maybe" we have to go to disk to check out the content of the SSTable.

Thanks,
Stu

-----Original Message-----
From: "S Ahmed" <sa...@gmail.com>
Sent: Wednesday, April 7, 2010 3:27pm
To: dev@cassandra.apache.org
Subject: boonfilters

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
:)

Re: boonfilters

[Tim Estes <ti...@digitalreasoning.com>]

Bloomfilters I think is what you mean- correct?


Sent from my iPhone

On Apr 7, 2010, at 3:27 PM, "S Ahmed" <sa...@gmail.com> 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
> :)