Ayende @ Rahien

It's a girl

Reviewing LevelDB: Part XVII– Filters? What filters? Oh, those filters…

I was all set to finish this series, when I realized that I missed something important, I didn’t covered, and indeed, I don’t currently understand, what filters are, and how are they used.

As usual, once I actually got to the part of the code where this is actually handled (instead of ignoring it), it made a lot more sense:

image

And that, following with the rest of the code that I read makes a lot more sense.

A SST is a sorted table, essentially. We have the keys and the blocks, etc. And we can find a value very quickly. But what if you could do this even more cheaply?

Using a bloom filter is a good way to never get false negative, and it will reduce the amount of work we have to do if we can’t find the key in the SST drastically (only need to read the filter value, don’t even need to do any additional checks). Quite elegant, even if I say so myself.

There is one thing to pay attention to and that is that you can define your own comparator, in which case you must also define you own filter policy. If you use a comparator that ignore casing, you also need to provider a filter that ignore casing.

Comments

Igor Kalders
04/15/2013 12:22 PM by
Igor Kalders

Thanks for highlighting the concept of Bloom Filter, which I was ignorant of up until now :)

Frank Quednau
04/17/2013 10:30 AM by
Frank Quednau

Kelly Sommers once had a piece on blom filters, to explain how it works... http://kellabyte.com/2013/01/24/using-a-bloom-filter-to-reduce-expensive-operations-like-disk-io/

Andrew
04/23/2013 03:53 AM by
Andrew

An interesting article which summarizes LevelDB quite nicely. The visuals really helped me understand the different levels and the log interaction

Comments have been closed on this topic.