Bloom Filter: Kiểm tra Email/Username trong 100 triệu record với RAM tối thiểu

Bloom Filter: Kiểm tra Email/Username trong 100 triệu record với RAM tối thiểu | Shanverse

Codetypescript

1function normalizeUsername(value: string): string {2  return value.normalize("NFKC").trim().toLocaleLowerCase("en-US");3}45function normalizeEmail(value: string): string {6  const trimmed = value.normalize("NFKC").trim();7  const at = trimmed.lastIndexOf("@");8  if (at < 1) throw new Error("Invalid email");910  const local = trimmed.slice(0, at);11  const domain = trimmed.slice(at + 1).toLowerCase();12  return `${local}@${domain}`;13}

Codetypescript

1import { createHash } from "node:crypto";23class BloomFilter {4  readonly bitCount: number;5  readonly hashCount: number;6  private readonly bits: Buffer;78  constructor(9    readonly expectedItems: number,10    readonly falsePositiveRate: number,11  ) {12    if (!Number.isSafeInteger(expectedItems) || expectedItems <= 0) {13      throw new Error("expectedItems must be a positive safe integer");14    }15    if (!(falsePositiveRate > 0 && falsePositiveRate < 1)) {16      throw new Error("falsePositiveRate must be between 0 and 1");17    }1819    const ln2 = Math.log(2);20    this.bitCount = Math.ceil(21      (-expectedItems * Math.log(falsePositiveRate)) / (ln2 * ln2),22    );23    this.hashCount = Math.max(24      1,25      Math.round((this.bitCount / expectedItems) * ln2),26    );27    this.bits = Buffer.alloc(Math.ceil(this.bitCount / 8));28  }2930  add(value: string): void {31    for (const index of this.indices(value)) {32      const byteIndex = Math.floor(index / 8);33      const bitMask = 1 << (index % 8);34      this.bits[byteIndex] |= bitMask;35    }36  }3738  mightContain(value: string): boolean {39    for (const index of this.indices(value)) {40      const byteIndex = Math.floor(index / 8);41      const bitMask = 1 << (index % 8);4243      if ((this.bits[byteIndex] & bitMask) === 0) return false;44    }4546    return true;47  }4849  memoryBytes(): number {50    return this.bits.byteLength;51  }5253  private *indices(value: string): Generator<number> {54    const digest = createHash("sha256").update(value).digest();55    const h1 = digest.readBigUInt64BE(0);56    const h2 = digest.readBigUInt64BE(8) | 1n;57    const modulo = BigInt(this.bitCount);5859    for (let i = 0; i < this.hashCount; i++) {60      yield Number((h1 + BigInt(i) * h2) % modulo);61    }62  }63}6465const emails = new BloomFilter(100_000_000, 0.001);66console.log(emails.hashCount);   // xấp xỉ 1067console.log(emails.memoryBytes()); // xấp xỉ 171 MiB6869emails.add(normalizeEmail("alice@example.com"));70console.log(emails.mightContain(normalizeEmail("alice@example.com")));

Codetypescript

1async function checkUsernameAvailability(raw: string) {2  const username = normalizeUsername(raw);3  const key = `username:v2:${username}`;45  const maybeExists = await bloom.mightContain(key);67  if (!maybeExists) {8    return { likelyAvailable: true, source: "bloom-negative" };9  }1011  const exists = await usersRepository.existsByNormalizedUsername(username);12  return { likelyAvailable: !exists, source: "database-confirmed" };13}

Codetypescript

1async function registerUser(input: RegisterInput) {2  const username = normalizeUsername(input.username);3  const email = normalizeEmail(input.email);45  try {6    const user = await usersRepository.insertWithUniqueConstraints({7      ...input,8      normalizedUsername: username,9      normalizedEmail: email,10    });1112    await outbox.publish("user-identity-created", {13      normalizedUsername: username,14      normalizedEmail: email,15    });1617    return user;18  } catch (error) {19    if (isUniqueViolation(error)) throw new IdentityAlreadyExistsError();20    throw error;21  }22}

Codejavascript

1BF.ADD identity:email:v3 "email:v3:alice@example.com"2BF.EXISTS identity:email:v3 "email:v3:bob@example.com"34BF.MADD identity:username:v2 "username:v2:alice" "username:v2:bob"5BF.MEXISTS identity:username:v2 "username:v2:alice" "username:v2:carol"

Bloom Filter: Kiểm tra Email/Username trong 100 triệu record với RAM tối thiểu

Bài toán 100 triệu record

Quy tắc quan trọng nhất

Comments

Cấu trúc bên trong

Công thức sizing

100 triệu phần tử cần bao nhiêu RAM?

Chọn false-positive rate theo chi phí thật

Normalize trước khi hash

TypeScript implementation từ đầu

Complexity

Luồng kiểm tra username đúng trong production

Đồng bộ Bloom Filter bằng CDC hoặc Outbox

Redis Bloom Filter

Một filter 100 triệu phần tử có scale trên Redis Cluster không?

Điều gì xảy ra khi vượt capacity?

Rebuild không downtime

Delete và rename

Cache penetration

Bloom Filter không phù hợp khi nào?

So sánh các lựa chọn

Testing

Unit/property tests

Integration tests

Metrics production

Anti-patterns

Production checklist

Kết luận

Tài liệu tham khảo

Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd

Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)

Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số

Bài toán 100 triệu record

Quy tắc quan trọng nhất

Comments

Cấu trúc bên trong

Công thức sizing

100 triệu phần tử cần bao nhiêu RAM?

Chọn false-positive rate theo chi phí thật

Normalize trước khi hash

TypeScript implementation từ đầu

Complexity

Luồng kiểm tra username đúng trong production

Đồng bộ Bloom Filter bằng CDC hoặc Outbox

Redis Bloom Filter

Một filter 100 triệu phần tử có scale trên Redis Cluster không?

Điều gì xảy ra khi vượt capacity?

Rebuild không downtime

Delete và rename

Cache penetration

Bloom Filter không phù hợp khi nào?

So sánh các lựa chọn

Testing

Unit/property tests

Integration tests

Metrics production

Anti-patterns

Production checklist

Kết luận

Tài liệu tham khảo

Related posts

Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd

Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)

Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số