Overview

This project implements a Bloom Filter for checking if a username already exists.

✨ A Bloom Filter is a smart and space-efficient way to check membership. Unlike a normal list or set, it doesn’t store the actual data. Instead, it uses a bit array and a few hash functions to quickly tell you:

• ✅ Definitely not present → the username does not exist
• ⚠️ Maybe present → the username might exist (small chance of false positive)

That’s the trade-off: Bloom Filters save a lot of memory and are super fast ⚡, but they allow a small chance of false positives.
However, they never give false negatives 🛡️ → if the filter says a username doesn’t exist, you can trust it.

🚀 Why use it here?

• ⚡ Fast checks: Instantly see if a username is taken
• 💾 Memory efficient: Handles a very large number of usernames with little space
• 🛠️ Practical: Useful as a first-pass filter before making costly database calls

💡 In short: it’s a lightweight helper that reduces load on your database while keeping username checks quick.

⚙️ Setup Bloom Filter

To make our Bloom Filter work, we first need hash functions and a way to decide the bit size and array size of the filter.

🔑 Hash Functions

---

In /src/utils/hashfunctions.ts, a class named Hashfunctions is created.
It includes four different hash functions:

• 🌀 djb2Hash
• 📊 sdbmHash
• ⚡ fnv1aHash
• 🔐 jenkinsHash

Each of these functions takes a username and the bit array size, then returns a unique value.
Multiple hash functions are used to spread usernames across the bit array and reduce collisions.

📐 Bit Size Calculation

---

The size of the bit array (m) depends on:

• 👥 n → number of expected users
• 🎯 P → desired false positive probability

Formula:

m = -(n * ln(P)) / (ln(2)^2)

📦 Array Size Calculation

---

Since the bit array is implemented in chunks (using integers), we also calculate the array size (a) as:

a = ceil(m / 32)

This makes sure the bits fit neatly into memory blocks while keeping the filter efficient.

💡 In short:

• Hash functions decide where each username maps inside the bit array.
• m ensures accuracy vs. memory usage.
• a makes the bit array practical to store in memory blocks.

📊 Storage Comparison

---

To give you a feel for the memory savings, here’s what happens if we try to store usernames directly vs. using a Bloom Filter.

Assumptions

• Average username = 16 characters (~16 bytes).
• “Direct storage” = just storing raw usernames (no database overhead counted).
• “Bloom Filter” = bit array sized to keep false positives low.
  • 1% false positive rate (P = 0.01)
  • 0.1% false positive rate (P = 0.001)

Users	Direct Storage	Bloom Filter (1%)	Bloom Filter (0.1%)
10K	~156 KB	~12 KB	~18 KB
100K	~1.5 MB	~117 KB	~176 KB
1M	~15 MB	~1.14 MB	~1.71 MB

💡 Takeaway:

• Storing usernames directly takes a lot more memory as the user base grows.
• A Bloom Filter keeps the space tiny (especially noticeable at 100K+ users).
• Even with stricter accuracy (0.1% false positives), the Bloom Filter is still much smaller than raw storage.

🔄 Bloom Filter Operations

There are two main operations in our Bloom Filter, implemented in
/src/utils/bloomUtils.ts:

• 📝 updateBloomArray → adds a username to the Bloom Filter
• 🔍 checkBloomArray → checks if a username might exist

📝 updateBloomArray

---

export function updateBloomArray(
  hashes: number[],
  bitArray: number[]
): number[] {
  hashes.forEach((hashIndex) => {
    const intIndex = Math.floor(hashIndex / 32);
    const bitIndex = hashIndex % 32;
    bitArray[intIndex] |= 1 << bitIndex;
  });

  return bitArray;
}

👉 What happens here:

• For each hash value, we figure out which integer in the bit array it belongs to (intIndex).

• Then we find which bit inside that integer to flip (bitIndex).

• Finally, we set that bit to 1 (using bitwise OR |=).

• Result → the username’s positions are marked in the Bloom Filter.

Think of it as: “marking spots in the bit array where this username lives.”

🔍 checkBloomArray

---

export function checkBloomArray(hashes: number[], bitArray: number[]): boolean {
  return hashes.every((hashIndex) => {
    const intIndex = Math.floor(hashIndex / 32);
    const bitIndex = hashIndex % 32;
    return (bitArray[intIndex] & (1 << bitIndex)) !== 0;
  });
}

👉 What happens here:

• For each hash value, we again find the correct integer and bit position.

• We check if that bit is set (1).

• If all the required bits are 1, the function returns true → the username might exist.

• If even one bit is 0, the function returns false → the username definitely does not exist.

💡 In short:

• updateBloomArray = mark bits for a username.

• checkBloomArray = verify bits for a username.

🧩 Visual Example

---

Suppose the hash functions give us indexes: 5, 12, 33, 47.

Our bit array is split into chunks of 32 bits (each stored as an integer):

Int Index	Bit Positions (0 → 31)	After Update
0	00000000000000000000010000100000	Bits 5 & 12 set
1	00000000000000000000000000010010	Bits 33 & 47 set
2	00000000000000000000000000000000	unchanged

📌 Breakdown:

• Hash 5 → Int 0, Bit 5 → flip that bit
• Hash 12 → Int 0, Bit 12 → flip that bit
• Hash 33 → Int 1, Bit 1 (33 % 32 = 1) → flip that bit
• Hash 47 → Int 1, Bit 15 (47 % 32 = 15) → flip that bit

So when we check later, if all these bits are 1, we say the username “probably exists.”

🚀 Performance Improvement

Working with a Bloom Filter is already efficient, but we wanted it to be even smoother.
That’s why we plugged in Redis as a caching layer.

With Redis:

• ⚡ Checking usernames becomes super fast.
• 📦 The Bloom Filter bit array is shared across all app instances.
• 🔄 Data survives restarts, so we don’t lose progress.

All the cache logic lives in:
/src/cache/cache.ts

👉 In short: Redis keeps our Bloom Filter quick, reliable, and easy to scale.

📈 Performance Overview

This project was tested with a target of 10,000 usernames to see how fast things can go.

1️⃣ Without Bloom Filter

If we check every username directly in the database, things slow down quickly as the number of users grows.

---

2️⃣ With Bloom Filter

With the Bloom Filter, most username checks happen in memory (or via Redis).
For 99% of the cases where the username is available (does not exist), the Bloom Filter can tell us immediately without hitting the database, giving an instant response.

---

💡 The takeaway:

• With the Bloom Filter, we drastically reduce expensive database lookups.
• Checks are super fast, even with thousands of usernames.
• Memory use stays low, but performance stays high — a nice win-win!

🚀 How to Run the Project

Follow these steps to get the project running locally:

1. Clone the repository

git clone https://github.com/SRRayhan066/Bloom-Filter

2. Go into the project folder

cd Bloom-Filter

3. Set up your environment variables

• Open the .env file.
• Set your MongoDB connection string:

MONGO_URI=<your-mongodb-uri>

4. Install dependencies

npm install

5. Run the project

npm run dev