@satyajeetsahoo/bloom-filter

A probabilistic data structure for massive set membership checks.

Why use this package?

Imagine you have 10 million users, and during registration, you need to check if an email already exists. Querying the database every time is extremely slow and resource-heavy. A Bloom Filter lives in your cache and can tell you in <1ms if the email is definitely not in the database, skipping the DB query entirely.

Features

• Constant Time: $O(1)$ lookups regardless of how many millions of items are stored.
• Massive Memory Savings: Stores 100,000s of emails in just a few kilobytes of RAM.

Installation

npm install @satyajeetsahoo/bloom-filter

Configuration

This package requires a Cache strategy (from @satyajeetsahoo/cache) to store the bit array.

import { createBloomFilter } from '@satyajeetsahoo/bloom-filter';
import { CacheService } from '@satyajeetsahoo/cache';

const cache = CacheService.createCache('redis', { client: redisInstance });

export const emailBloomFilter = createBloomFilter({
  store: cache, 
  key: 'bloom:emails',
  expectedItems: 1000000,     // Optimize for 1 million emails
  falsePositiveRate: 0.01     // 1% false positive rate
});

Usage Examples

Preventing DB Queries for New Registrations

// 1. Add emails to the filter when users register
await emailBloomFilter.add('[email protected]');

// 2. Check existence later
const mayExist = await emailBloomFilter.has('[email protected]');

if (!mayExist) {
  // DEFINITELY NOT IN DB. Safe to register without querying Postgres!
  return registerUser();
} else {
  // MIGHT BE IN DB (1% false positive chance). Query DB to confirm.
  const user = await db.users.findByEmail('[email protected]');
  if (user) throw new Error('Email taken');
}