ceejbot/xx-bloom

yet another bloom filter implementation for node.js; backed by xxhash

Yet another Bloom filter implementation for node.js. Everybody has to write one, as you know. Backed by Xxhash via node-xxhash. Xxhash is a fast general-purpose hash, which is all a bloom filter needs. Three variations are provided: a straight Bloom filter, a counting filter (from which items can be removed), and a straight Bloom filter backed by redis. The first two have synchronous APIs. The redis one perforce requires callbacks.

To install: npm install bloomxx

Usage

BloomFilter

To create a filter, pass an options hash to the constructor:

var options =
{
	bits: 1024,
	hashes: 7,
	seeds: [1, 2, 3, 4, 5, 6, 7]
};
filter = new BloomFilter(options);

You can pass in seeds for the hash functions if you like, or they'll be randomly generated. Seeds must be integers.

You may also pass in a buffer as generated by filter.toBuffer().

createOptimal()

To create a filter optimized for the number of items you'll be storing and a desired error rate:

filter = BloomFilter.createOptimal(estimatedItemCount, errorRate);

The error rate parameter is optional. It defaults to 0.005, or a 0.5% rate.

add()

filter.add('cat');

Adds the given item to the filter. Can also accept buffers and arrays containing strings or buffers:

filter.add(['cat', 'dog', 'coati', 'red panda']);

has()

To test for membership:

filter.has('dog');

clear()

To clear the filter:

filter.clear();

toBuffer()

Returns a buffer with seeds and filter data.

fromBuffer()

Reconstitutes a filter from a freeze-dried buffer.

CountingFilter

Uses about 8 times as much space as the regular filter. Basic usage is exactly the same as the plain Bloom filter:

filter = new CountingFilter({ hashes: 8, bits: 1024 });`
filter2 = CountingFilter.createOptimal(estimatedItemCount, optionalErrorRate);

Add a list, test for membership, then remove:

filter.add(['cat', 'dog', 'coati', 'red panda']);
filter.has('cat'); // returns true
filter.remove('cat');
filter.has('cat'); // returns false most of the time

The counting filter tracks its overflow count in filter.overflow. Overflow will be non-zero if any bit has been set more than 255 times. Once the filter has overflowed, removing items is no longer reliable.

Check for overflow:

filter.hasOverflowed(); // returns boolean
filter.overflow; // integer count of number of times overflow occurred

RedisFilter

This is a plain vanilla bloom filter backed by redis. Its api is asychronous.

RedisFilter.createOrRead({
		key: 'cats', // the key used to store data in redis; will also set 'cats:meta'
		bits: 1024,  // filter size in bits
		hashes: 8,   // number of hash functions
		redis: redis.createClient(port, host)  // redis client to use
	}, function(err, filter)
	{
		filter.add(['cat', 'jaguar', 'lion', 'tiger', 'leopard'], function(err)
		{
			filter.has('caracal', function(err, result)
			{
				assert(result === false);
			});
		});
	});

The options hash can also specify host and port, which will be used to create a redis client. createOrRead() will attempt to find a filter saved at the given key and create one if it isn't found.

createOptimal(itemCount, errorRate, options)

Returns a filter sized for the given item count and desired error rate, with other options as specified in the options hash.

clear(function(err) {})

Clear all bits.

del(function(err) {})

Delete the filter from redis.

Licence

MIT.

xx-bloom's Issues

how can i add counting filter with redis ?

is there a quick way that i can use counting filter with redis ? (i need to be able to delete some of the items in my list )

Serialization?

How to load/save from persistent storage?

use redis getbit instead of hset

Salam,

use redis getbit/setbit instead of hset

https://redis.io/commands/getbit
https://redis.io/commands/setbit

Counting filter / overflow issue

I was playing around with the counting filter and I'm seeing some problems with the hasOverflowed function - it seems like it is pretty wildly off.

Take this example:

var
  bloom   = require('bloomxx'),
  cFilter = bloom.CountingFilter.createOptimal(75),
  i;

for (i = 0; i < 10000; i += 1) {
  cFilter.add(String(Math.random()));
}
cFilter.add('kyle');

console.log('overflowed?', cFilter.hasOverflowed(), cFilter.overflow);

console.log('has name: kyle?',cFilter.has('kyle'));
console.log('has name: bob?',cFilter.has('bob'));
console.log('removed kyle');
cFilter.remove('kyle');
console.log('has name: kyle?',cFilter.has('kyle'));

For me, this is resulting in the following output:

overflowed? false 0
has name: kyle? true
has name: bob? true
removed kyle
has name: kyle? true

Since the loop is only inserting random numbers and the we manually insert 'kyle', 'bob' should not be returning true. I would also guess that an optimal filter for size 75 would have overflowed way before 10,001 members. Or am I missing something in the implementation?

Making async API optional on non-redis filters.

This would allow us to implement the non-redis filters for now and have redis support in the future!