Posted on Sep 17

⚡ Scaling User Search with Bloom Filters in Node.js

#programming #tutorial #learning #development

When your system grows to millions of users, even the simplest operations—like checking if a phone number or email already exists—can become costly.

Yes, you can add database indexes, but every lookup still eats up I/O and CPU cycles. Under heavy signup traffic, this can quickly overwhelm your database.

This is where Bloom Filters come to the rescue. 🌸

🌱 What is a Bloom Filter?

A Bloom Filter is a probabilistic data structure used for set membership checks. It allows us to ask:

👉 “Does this value possibly exist?”

It can say:

❌ Definitely Not → Safe to skip DB.
✅ Might Exist → Confirm with DB.

This tiny compromise (allowing false positives, but never false negatives) gives us O(1) lookups with very little memory usage.

🔬 Anatomy of a Bloom Filter (Abscissa)

At its core, a Bloom filter is just:

A Bit Array (size m) → starts with all 0’s.
k Hash Functions → each maps an input to one of the m positions.

👉 When we add an element:

Run it through all k hash functions.
Flip those positions in the bit array to 1.

👉 When we check an element:

Run it through the same k functions.
If all those positions are 1 → the element might exist.
If any position is 0 → it definitely does not exist.

📈 Visual Abscissa

Think of it as a number line (abscissa = x-axis):

Bit Array (size m) 0 1 2 3 4 5 6 7 8 9 ... m-1 [0][0][0][0][0][0][0][0][0][0]

Each hash function picks some positions along this line.
Adding "alice@example.com" might flip positions 3, 7, and 9.
Checking "bob@example.com"? If one of its hash positions is still 0, we know Bob isn’t in the set.

⚖️ Balancing Act

More bits (m) → fewer collisions, lower false positives.
More hash functions (k) → more accuracy, but also more computation.
The sweet spot depends on expected number of elements n.

Formula for optimal k:

k=n/m(ln2)

This balance is why Bloom filters are tiny in memory yet mighty in scale.

🏗️ Our Architecture

We built a Bloom Filter Service in Node.js that acts as a fast gatekeeper before the database.

It consists of:

Routes Layer → API endpoints for clients.
Handler Layer → Processes requests, interacts with the service.
Service Layer → Manages Bloom filters, population, refresh, and lookups.

📜 Routes Layer

We expose three endpoints under /bloom_filter:

import express from 'express'; import { getBloomFilterStatus, refreshBloomFilter, checkPhoneExists } from './handler.js'; const router = express.Router(); router.get('/status', getBloomFilterStatus); router.post('/refresh', refreshBloomFilter); router.get('/check', checkPhoneExists); export default router;

GET /status → Monitor filters.
POST /refresh → Force a refresh.
GET /check?phoneNumber=... → Check existence.

⚙️ Handler Layer

The handlers sit between API requests and the service. They manage errors and responses:

import userSearchBloomFilter from '../../services/userSearchBloomFilter.js'; import { generateInternalServerErrorRepsonse } from '../../utils/errorHandler.js'; export async function getBloomFilterStatus(req, res) { try { const status = userSearchBloomFilter.getStatus(); return res.status(200).json({ success: true, data: status }); } catch (error) { const errorResponse = await generateInternalServerErrorRepsonse(error, 'getBloomFilterStatus'); return res.status(500).json(errorResponse); } } export async function refreshBloomFilter(req, res) { try { await userSearchBloomFilter.refresh(); return res.status(200).json({ success: true, message: 'Bloom filter refreshed successfully' }); } catch (error) { const errorResponse = await generateInternalServerErrorRepsonse(error, 'refreshBloomFilter'); return res.status(500).json(errorResponse); } } export async function checkPhoneExists(req, res) { try { const { phoneNumber } = req.query; if (!phoneNumber) { return res.status(400).json({ success: false, error: 'Phone number is required' }); } const mightExist = userSearchBloomFilter.mightExist(phoneNumber); return res.status(200).json({ success: true, data: { phoneNumber, mightExist, note: mightExist ? 'Might exist - check database' : 'Definitely does not exist' } }); } catch (error) { const errorResponse = await generateInternalServerErrorRepsonse(error, 'checkPhoneExists'); return res.status(500).json(errorResponse); } }

👉 Notice how checkPhoneExists does not immediately hit the DB. It asks the Bloom filter first.

🧠 Service Layer: Core Bloom Filter Logic

This is where the real magic happens.

We maintain four Bloom filters:

emailFilter
phoneFilter
alternateEmailFilter
alternatePhoneFilter

Each filter is initialized with a target capacity and error rate (0.01 = 1%).

import BloomFilter from '../utils/BloomFilter.js'; import User from '../models/user.js'; import logger from '../setup/logger.js'; class UserSearchBloomFilterService { constructor() { this.emailFilter = new BloomFilter(100000, 0.01); this.phoneFilter = new BloomFilter(100000, 0.01); this.alternateEmailFilter = new BloomFilter(50000, 0.01); this.alternatePhoneFilter = new BloomFilter(50000, 0.01); this.isInitialized = false; this.lastUpdated = null; this.updateInterval = 24 * 60 * 60 * 1000; // 24 hours }

🔄 Populating the Filters

On startup, we fetch users in batches and add their identifiers into the filters:

async populateFilters() { const batchSize = 1000; let offset = 0; let hasMoreUsers = true; while (hasMoreUsers) { const users = await User.query(qb => { qb.select('email', 'phone_number', 'alternate_email', 'alternate_phone'); qb.whereNotNull('email').orWhereNotNull('phone_number'); qb.limit(batchSize); qb.offset(offset); }).fetchAll(); const userList = users.toJSON(); if (userList.length === 0) { hasMoreUsers = false; break; } userList.forEach(user => { if (user.email) this.emailFilter.add(user.email); if (user.phone_number) this.phoneFilter.add(user.phone_number); if (user.alternate_email) this.alternateEmailFilter.add(user.alternate_email); if (user.alternate_phone) this.alternatePhoneFilter.add(user.alternate_phone); }); offset += batchSize; logger.info(`Processed ${offset} users for bloom filter`); } logger.info(`Bloom filter population completed. Total users processed: ${offset}`); }

This ensures all existing users are represented in the filter.

⚡ Lookup Logic

When a phone/email check request arrives:

mightExist(searchKey) { if (!this.isInitialized) { return true; // fail-safe until initialized } const normalizedKey = searchKey.toLowerCase().trim(); return ( this.emailFilter.mightContain(normalizedKey) || this.phoneFilter.mightContain(normalizedKey) || this.alternateEmailFilter.mightContain(normalizedKey) || this.alternatePhoneFilter.mightContain(normalizedKey) ); }

👉 If it returns false, we know for sure the user doesn’t exist.
👉 If it returns true, we query the DB to confirm.

🕒 Auto-Refreshing

To stay fresh with new data, we schedule a 24-hour refresh:

schedulePeriodicUpdate() { setInterval(async () => { try { logger.info('Starting scheduled bloom filter update'); await this.refresh(); } catch (error) { logger.error('Scheduled bloom filter update failed:', error); } }, this.updateInterval); }

This clears and repopulates the filters.

📊 Status Reporting

Finally, we can inspect filter health:

getStatus() { return { isInitialized: this.isInitialized, lastUpdated: this.lastUpdated, emailFilterStats: this.emailFilter.getStats(), phoneFilterStats: this.phoneFilter.getStats(), alternateEmailFilterStats: this.alternateEmailFilter.getStats(), alternatePhoneFilterStats: this.alternatePhoneFilter.getStats() }; }

🚀 Example Flow

A signup form checks if 1231881971 exists:

Client calls → GET /bloom_filter/check?phoneNumber=<phoneNumber>
Bloom filter says:

❌ Not in set → Return immediately (skip DB).
✅ Might exist → Query DB to confirm.

This cuts DB load massively.

✅ Benefits

O(1) Lookups → Super fast.
Reduced DB Load → Fewer queries.
Scalable → Handles millions of entries.
Fault-Tolerant → Always errs on the safe side (false positives only).

⚠️ Limitations

False Positives → Might say “exists” when it doesn’t.
No Deletion → Standard Bloom filters don’t support removing entries.
Cold Start → Until initialized, returns “might exist” to avoid false negatives.