Disponibilidade de Nome de Usuário com Bloom Filters

import hashlib
import math

class BloomFilter:
    def __init__(self, expected_items, false_positive_rate=0.01):
        # Calculate optimal size and hash count
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hashes(self.size, expected_items)
        self.bit_array = bytearray(self.size // 8 + 1)
        print(f"Filter size: {self.size / 8 / 1024 / 1024:.1f} MB")
        print(f"Hash functions: {self.hash_count}")

    def _optimal_size(self, n, p):
        return int(-n * math.log(p) / (math.log(2) ** 2))

    def _optimal_hashes(self, m, n):
        return int((m / n) * math.log(2))

    def _get_hashes(self, item):
        hashes = []
        for i in range(self.hash_count):
            h = hashlib.sha256(f"{item}:{i}".encode()).hexdigest()
            hashes.append(int(h, 16) % self.size)
        return hashes

    def add(self, item):
        for pos in self._get_hashes(item):
            self.bit_array[pos // 8] |= (1 << (pos % 8))

    def might_contain(self, item):
        return all(
            self.bit_array[pos // 8] & (1 << (pos % 8))
            for pos in self._get_hashes(item)
        )

# For 1 billion usernames at 1% false positive rate
bf = BloomFilter(expected_items=1_000_000_000, false_positive_rate=0.01)
# Output: Filter size: ~1144.5 MB, Hash functions: 7

bf.add("alice")
bf.add("bob")

print(bf.might_contain("alice"))   # True (definitely added)
print(bf.might_contain("charlie")) # False (definitely NOT added)
print(bf.might_contain("bob"))     # True (definitely added)

from fastapi import FastAPI
import redis

app = FastAPI()
r = redis.Redis()

# Redis has built-in Bloom filter support via RedisBloom module
# BF.RESERVE usernames 0.01 1000000000
# BF.ADD usernames "alice"

@app.get("/check-username/{username}")
async def check_username(username: str):
    username = username.lower().strip()

    # Layer 1: format validation (instant, no I/O)
    if len(username) < 3 or len(username) > 30:
        return {"available": False, "reason": "invalid_length"}

    # Layer 2: Bloom filter check (sub-millisecond, in-memory)
    possibly_taken = r.execute_command("BF.EXISTS", "usernames", username)
    if not possibly_taken:
        # Bloom filter says NO -> definitely available
        return {"available": True}

    # Layer 3: database confirmation (only for Bloom positives)
    # This path is hit for ~1% false positives + actual taken names
    taken = await db.check_username_exists(username)
    return {"available": not taken}