Bloom Filter – probabilistyczna struktura, blacklisty tokenów, negative cache

Bloom Filter to probabilistyczna struktura danych która odpowiada na pytanie „czy ten element może być w zbiorze?” – z gwarancją braku false negatives i kontrolowanym poziomem false positives. Używa ułamka pamięci potrzebnej tablicy hashowej. Gdy masz milion zakazanych tokenów, setki tysięcy unikalnych emaili do walidacji albo cache który musi odrzucić żądania bez trafień do bazy – Bloom Filter jest właściwym narzędziem.

Jak działa Bloom Filter

Bloom Filter to tablica bitów o stałym rozmiarze m i k funkcji hashujących. Dodanie elementu: policz k hashów, ustaw odpowiednie bity na 1. Sprawdzenie elementu: policz k hashów, sprawdź czy wszystkie bity są 1. Jeśli jakikolwiek bit = 0 → element na pewno NIE jest w zbiorze. Jeśli wszystkie bity = 1 → element PRAWDOPODOBNIE jest w zbiorze (może być false positive).

<?php

declare(strict_types=1);

class BloomFilter
{
    private array $bits;     // tablica bitów (SplFixedArray byłaby szybsza)
    private int $size;       // rozmiar tablicy bitów
    private int $hashCount;  // liczba funkcji hashujących

    /**
     * @param int $expectedItems  Spodziewana liczba elementów
     * @param float $falsePositiveRate  Akceptowalny poziom false positives (0.01 = 1%)
     */
    public function __construct(int $expectedItems, float $falsePositiveRate = 0.01)
    {
        // Optymalny rozmiar: m = -(n * ln(p)) / (ln(2))^2
        $this->size = (int) ceil(
            -($expectedItems * log($falsePositiveRate)) / (log(2) ** 2)
        );

        // Optymalna liczba hashów: k = (m/n) * ln(2)
        $this->hashCount = (int) ceil(
            ($this->size / $expectedItems) * log(2)
        );

        $this->bits = array_fill(0, $this->size, 0);

        echo "Bloom Filter: {$this->size} bitów ({$this->getBitsSizeKB()} KB), {$this->hashCount} funkcji hash\n";
    }

    public function add(string $item): void
    {
        foreach ($this->getHashPositions($item) as $position) {
            $this->bits[$position] = 1;
        }
    }

    public function mightContain(string $item): bool
    {
        foreach ($this->getHashPositions($item) as $position) {
            if ($this->bits[$position] === 0) {
                return false; // DEFINITELY NOT in set
            }
        }

        return true; // PROBABLY in set (may be false positive)
    }

    // Generuje k różnych pozycji bitów dla danego elementu
    private function getHashPositions(string $item): array
    {
        $positions = [];

        for ($i = 0; $i < $this->hashCount; $i++) {
            // Użyj różnych seedów dla każdej funkcji hashującej
            $hash = hexdec(substr(md5("{$i}:{$item}"), 0, 8));
            $positions[] = $hash % $this->size;
        }

        return $positions;
    }

    public function getBitsSizeKB(): float
    {
        return round($this->size / 8 / 1024, 2);
    }

    // Szacunkowy poziom false positives dla aktualnego wypełnienia
    public function estimateFalsePositiveRate(int $insertedItems): float
    {
        $filledBits = 1 - pow(M_E, -($this->hashCount * $insertedItems) / $this->size);
        return pow($filledBits, $this->hashCount);
    }
}

Praktyczne zastosowanie – blacklista tokenów

<?php

declare(strict_types=1);

// Problem: masz 1 000 000 unieważnionych JWT tokenów
// Sprawdzanie każdego w bazie danych = za wolne
// Trzymanie wszystkich w Redis = za dużo pamięci

// Bloom Filter: 1% false positive rate, 1M tokenów
$revokedTokens = new BloomFilter(
    expectedItems:       1_000_000,
    falsePositiveRate:   0.01
);

// Bloom Filter: ~1.14M bitów = ~143 KB zamiast ~40 MB dla 1M stringów w HashSecie
// BloomFilter: 1198884 bitów (146.34 KB), 7 funkcji hash

// Ładujemy unieważnione tokeny (tylko raz przy starcie lub przez cron)
$revokedTokenIds = [
    'token_abc123_user42_session1',
    'token_def456_user15_session2',
    // ... 999 998 więcej
];

foreach ($revokedTokenIds as $token) {
    $revokedTokens->add($token);
}

// Middleware autentykacji
function validateJwtToken(string $token, BloomFilter $revokedList): bool
{
    // Fast path: Bloom Filter powie "definitely not revoked" dla 99% tokenów
    if (!$revokedList->mightContain($token)) {
        return true; // na pewno nie jest na blackliście - idź dalej
    }

    // Slow path: tylko ~1% tokenów trafi tutaj (false positives + prawdziwe trafienia)
    // Sprawdź w bazie danych tylko gdy Bloom Filter mówi "może być"
    return !isTokenRevokedInDatabase($token);
}

function isTokenRevokedInDatabase(string $token): bool
{
    // Jedno zapytanie do bazy - tylko dla ~1% requestów
    return false; // uproszczenie
}

// Wyniki:
// 99% requestów: Bloom Filter odpowiada natychmiast, zero zapytań do bazy
// ~1% requestów: jedno zapytanie do bazy (false positives + prawdziwe)
// vs bez Bloom Filter: 100% requestów = zapytanie do bazy

Bloom Filter dla cache stampede prevention

<?php

declare(strict_types=1);

// Problem: "cold cache" - milion requestów uderza w bazę gdy cache wygasa
// Rozwiązanie: Bloom Filter jako "negatywny cache" dla kluczy które NIE istnieją

class BloomCacheLayer
{
    private BloomFilter $negativeCache; // klucze KTÓRYCH NIE MA w bazie

    public function __construct(
        private \Psr\SimpleCache\CacheInterface $cache,
        private \PDO $pdo
    ) {
        $this->negativeCache = new BloomFilter(
            expectedItems: 100_000,
            falsePositiveRate: 0.001 // 0.1% false positive
        );
    }

    public function getProduct(int $id): ?array
    {
        $cacheKey = "product_{$id}";

        // 1. Sprawdź cache
        $cached = $this->cache->get($cacheKey);
        if ($cached !== null) {
            return $cached;
        }

        // 2. Sprawdź Bloom Filter - czy ten ID na pewno nie istnieje?
        if ($this->negativeCache->mightContain("product_{$id}")) {
            // Bloom Filter mówi "może istnieć" - sprawdź bazę
            // false positive rate 0.1% = 1 na 1000 sprawdzeń to fałszywy alarm
        } else {
            // Bloom Filter mówi "NA PEWNO NIE ISTNIEJE" - zero zapytań do bazy
            return null;
        }

        // 3. Zapytanie do bazy (tylko gdy Bloom Filter nie jest pewny)
        $product = $this->fetchFromDatabase($id);

        if ($product === null) {
            // Produkt nie istnieje - dodaj do negative cache
            $this->negativeCache->add("product_{$id}");
            return null;
        }

        // 4. Zapisz w cache
        $this->cache->set($cacheKey, $product, 3600);
        return $product;
    }

    private function fetchFromDatabase(int $id): ?array
    {
        $stmt = $this->pdo->prepare('SELECT * FROM catalog_product_entity WHERE entity_id = ?');
        $stmt->execute([$id]);
        return $stmt->fetch(\PDO::FETCH_ASSOC) ?: null;
    }
}

Walidacja unikalności emaili bez bazy

<?php

// Problem: rejestracja 10000 użytkowników dziennie
// Każde sprawdzenie unikalności emaila = zapytanie do bazy

$registeredEmails = new BloomFilter(
    expectedItems: 5_000_000,   // 5M użytkowników
    falsePositiveRate: 0.001    // 0.1% false positives
);

// Ładuj istniejące emaile przy starcie (lub z Redis persistence)
$allEmails = fetchAllEmailsFromDb(); // jeden duży SELECT raz
foreach ($allEmails as $email) {
    $registeredEmails->add(strtolower($email));
}

// Przy rejestracji
function isEmailAvailable(string $email, BloomFilter $filter): bool
{
    $normalized = strtolower(trim($email));

    // Fast path: 99.9% nowych emaili - Bloom Filter mówi "wolny"
    if (!$filter->mightContain($normalized)) {
        return true; // na pewno wolny - zero zapytań do bazy
    }

    // Slow path: 0.1% - sprawdź w bazie (false positive lub email zajęty)
    return !isEmailInDatabase($normalized);
}

// Wynik: 99.9% rejestracji bez zapytania do bazy dla sprawdzenia unikalności

Porównanie Bloom Filter vs alternatywy

Podsumowanie

Bloom Filter jest narzędziem do specyficznych problemów: wielkie zbiory danych gdzie false positives są akceptowalne, a pamięć i czas odpowiedzi mają krytyczne znaczenie. W PHP e-commerce zastosowania to blacklisty tokenów, negatywny cache dla nieistniejących zasobów i wstępna walidacja unikalności bez uderzenia w bazę. Kluczowe ograniczenie: nie można usuwać elementów (standardowy Bloom Filter) i trzeba akceptować że ~1% odpowiedzi „może być w zbiorze” to fałszywe alarmy.