Khó PHP

Bloom filter thực chiến: cách chạy, toán false positive, tính kích thước, PHP và Redis

Bỏ qua hàng triệu lần tra database chỉ với vài MB bit. Bloom filter chạy ra sao, toán false positive, tính kích thước, code PHP và command BF của Redis.

18 Th11, 2026 15 phút Cập nhật 23 Th10, 2026 7 Khối code
Sơ đồ
graph LR A[Phần tử] --> B[Hash hai lần: h1 và h2] B --> C[k vị trí bit: h1 cộng i nhân h2 mod m] C --> D[Mảng m bit] D --> E{Đủ k bit đều bật?} E -->|không| F[Chắc chắn không có] E -->|có| G[Có thể có - kiểm lại trong DB]

Mỗi email mình gửi đi đều phải kiểm tra danh sách chặn trước: 50 triệu địa chỉ đã bounce, bị báo spam hoặc đã hủy đăng ký. Kiểm tra chỉ là một lần tra primary key, bản thân nó nhanh, nhưng job gửi newsletter bắn 3 triệu email mỗi giờ, và 99,7% số lần tra trả về "không bị chặn". Mình đang trả giá cho 3 triệu round trip tới database mỗi giờ chủ yếu để biết rằng chẳng có gì ở đó.

Bloom filter trả lời đúng câu hỏi đó với chi phí rất rẻ: "phần tử này có chắc chắn không nằm trong tập hay không?" Nó không bao giờ nói "không" sai, thỉnh thoảng nói "có" sai, và làm vậy với lượng memory cố định bất kể phần tử dài cỡ nào. Với danh sách của mình, 86 MiB trong memory đã thay gần hết đống query đó. Phần 0,3% còn lại cộng thêm 0,1% false positive vẫn đi xuống database để lấy câu trả lời thật.

Bloom filter chạy ra sao

Bloom filter là một mảng m bit, ban đầu toàn số 0, cộng với k hàm hash, mỗi hàm map một phần tử vô một trong m vị trí.

  • Add: hash phần tử k lần và bật k bit đó lên 1.
  • Query: hash phần tử k lần. Nếu có bất kỳ bit nào là 0 thì phần tử chưa từng được add, chắc chắn luôn. Nếu tất cả đều là 1 thì phần tử có thể đã được add, hoặc mấy bit đó bị các phần tử khác bật lên.
graph LR A[Phần tử] --> B[Hash hai lần: h1 và h2] B --> C[k vị trí bit: h1 cộng i nhân h2 mod m] C --> D[Mảng m bit] D --> E{Đủ k bit đều bật?} E -->|không| F[Chắc chắn không có] E -->|có| G[Có thể có - kiểm lại trong DB]

Bloom filter thường không xóa được, vì tắt một bit có thể xóa luôn dấu vết của phần tử khác dùng chung bit đó. Cũng không liệt kê được phần tử: filter chỉ lưu dấu vân tay của việc có mặt, không lưu dữ liệu. Cả hai vừa là giới hạn vừa là ưu điểm: chi phí memory cho mỗi phần tử nhỏ và cố định, dù phần tử là email 10 byte hay URL 2 KB.

Mình không cần k hàm hash độc lập. Kirsch và Mitzenmacher đã chứng minh hai hash gốc ghép theo h1 + i * h2 với i = 0 .. k-1 cho ra tỉ lệ false positive tiệm cận y vậy. Cài đặt thực tế nào cũng làm theo cách này.

Phần toán: false positive và cách tính kích thước

Sau khi chèn n phần tử, xác suất một bit cụ thể vẫn là 0 xấp xỉ e^(-kn/m). False positive xảy ra khi cả k bit của một phần tử không có trong tập đều là 1, từ đó ra mấy công thức dùng để tính kích thước:

n = items you expect to insert
m = bits in the array
k = number of hash functions
p = false positive rate

p  ~ (1 - e^(-k*n/m))^k            false positive rate for given m, n, k
m  = -n * ln(p) / (ln 2)^2         bits needed for target p
k  = (m / n) * ln 2                optimal number of hash functions

target p     bits per item     k
1%           9.59              7
0.1%         14.38             10
0.01%        19.17             13

Mấy điều rút ra từ bảng:

  • Mỗi lần giảm tỉ lệ false positive mười lần tốn thêm khoảng 4,8 bit cho mỗi phần tử. Đi từ 1% xuống 0,1% rẻ lắm.
  • Memory chỉ phụ thuộc n và p, không bao giờ phụ thuộc độ dài phần tử. 50 triệu email ở 0,1% cần 718.879.379 bit, khoảng 86 MiB. Cũng đống email đó mà bỏ vô Redis set thì tốn cỡ vài gigabyte.
  • k tăng chậm. Nhiều hàm hash hơn mức tối ưu còn làm tệ hơn, vì mảng bị lấp đầy nhanh hơn.
  • Nhồi quá tải thì chất lượng giảm từ từ nhưng nhanh. Filter tính cho 1 triệu phần tử ở 1% mà chứa 2 triệu thì false positive lên khoảng 15%. Luôn tính dư cho tăng trưởng, và build lại khi gần chạm sức chứa.

Cài đặt bằng PHP

String của PHP là một mảng bit xài rất ổn: một byte chứa tám bit, truy cập theo index là O(1). hash('xxh128'), có từ PHP 8.1, nhanh và phân bố đều; mình cắt hai số nguyên 32-bit từ digest của nó để làm double hashing.

namespace App\Support;

use InvalidArgumentException;

final class BloomFilter
{
    private string $bits;

    private function __construct(
        public readonly int $size,      // m, number of bits
        public readonly int $hashes,    // k
        ?string $bits = null,
    ) {
        $this->bits = $bits ?? str_repeat("\0", intdiv($size + 7, 8));
    }

    /** Size the filter for $expected items at false positive rate $fpRate. */
    public static function forCapacity(int $expected, float $fpRate): self
    {
        if ($expected < 1 || $fpRate <= 0.0 || $fpRate >= 1.0) {
            throw new InvalidArgumentException('Need expected >= 1 and 0 < fpRate < 1');
        }
        $m = (int) ceil(-$expected * log($fpRate) / (M_LN2 ** 2));
        $k = max(1, (int) round($m / $expected * M_LN2));

        return new self($m, $k);
    }

    public function add(string $item): void
    {
        foreach ($this->positions($item) as $bit) {
            $byte = $bit >> 3;
            $this->bits[$byte] = chr(ord($this->bits[$byte]) | (1 << ($bit & 7)));
        }
    }

    /** false = definitely absent, true = probably present. */
    public function mightContain(string $item): bool
    {
        foreach ($this->positions($item) as $bit) {
            if ((ord($this->bits[$bit >> 3]) & (1 << ($bit & 7))) === 0) {
                return false;
            }
        }

        return true;
    }

    /** Kirsch-Mitzenmacher double hashing: k positions from two base hashes. */
    private function positions(string $item): array
    {
        $digest = hash('xxh128', $item, true);
        $h1 = unpack('N', $digest, 0)[1];
        $h2 = unpack('N', $digest, 4)[1] | 1;   // odd, so the stride never collapses to 0

        $out = [];
        for ($i = 0; $i < $this->hashes; $i++) {
            $out[] = ($h1 + $i * $h2) % $this->size;
        }

        return $out;
    }

    public function serialize(): string
    {
        return pack('JJ', $this->size, $this->hashes) . $this->bits;
    }

    public static function unserialize(string $data): self
    {
        ['m' => $m, 'k' => $k] = unpack('Jm/Jk', $data);

        return new self($m, $k, substr($data, 16));
    }
}

Vị trí được tính modulo m với hash gốc 32-bit, ổn cho filter tới vài tỉ bit. Định dạng serialize() chỉ là header 16 byte cộng mảng bit thô, nên lưu được vô file, object storage, hay một Redis string bình thường, và load lên trong vài mili giây.

Xài nó làm bước kiểm tra trước database trông như vầy:

use App\Support\BloomFilter;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Storage;

// Build once (nightly job): 50M suppressed emails at 0.1% -> about 86 MiB.
$filter = BloomFilter::forCapacity(50_000_000, 0.001);
DB::table('suppressed_emails')->orderBy('id')->lazyById(10_000)->each(
    fn ($row) => $filter->add(strtolower($row->email)),
);
Storage::put('bloom/suppressed.bin', $filter->serialize());

// Hot path: most addresses are NOT suppressed and never touch the database.
function isSuppressed(BloomFilter $filter, string $email): bool
{
    $email = strtolower($email);
    if (! $filter->mightContain($email)) {
        return false;                       // definite answer, no query
    }

    return DB::table('suppressed_emails')->where('email', $email)->exists();
}

Filter chỉ đi tắt cho câu trả lời "không". Câu "có thể" thì rơi xuống nguồn dữ liệu chính, nên tính đúng đắn không bao giờ phụ thuộc vô filter.

Kiểm chứng phần toán

Trước khi tin công thức với traffic production, đo thử đi. Script nháp này build filter cho 100.000 phần tử ở 1% rồi dò 200.000 phần tử không có trong tập:

# Check the formula against reality before trusting it in production.
import hashlib
import math


def positions(item: str, m: int, k: int) -> list[int]:
    d = hashlib.blake2b(item.encode(), digest_size=16).digest()
    h1 = int.from_bytes(d[:8], "big")
    h2 = int.from_bytes(d[8:], "big") | 1
    return [(h1 + i * h2) % m for i in range(k)]


n, p = 100_000, 0.01
m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
k = max(1, round(m / n * math.log(2)))
bits = bytearray(m)
for i in range(n):
    for pos in positions(f"member-{i}", m, k):
        bits[pos] = 1

trials = 200_000
false_hits = sum(
    all(bits[pos] for pos in positions(f"stranger-{i}", m, k)) for i in range(trials)
)
print(f"m={m} k={k} measured={false_hits / trials:.4%} target={p:.2%}")
# m=958506 k=7 measured=~1.0% target=1.00%

Nếu tỉ lệ đo được cao hơn mục tiêu nhiều, thủ phạm thường là hash yếu (ví dụ crc32 trên các key na ná nhau), vị trí không được mod m cho đúng, hoặc số phần tử nhiều hơn dự tính.

Bloom filter trong Redis

Khi nhiều app server cần xài chung một filter và nó thay đổi trong ngày, giữ nó trong Redis thay vì build lại ở từng process. Redis 8 có sẵn Bloom filter; bản cũ hơn thì lấy từ Redis Stack hoặc module RedisBloom.

# Redis 8 ships Bloom filters in the core distribution
# (older versions: Redis Stack or the RedisBloom module).
redis-cli BF.RESERVE emails:suppressed 0.001 50000000
redis-cli BF.MADD emails:suppressed [email protected] [email protected]
redis-cli BF.EXISTS emails:suppressed [email protected]      # 1 = probably
redis-cli BF.EXISTS emails:suppressed [email protected]      # 0 = definitely not
redis-cli BF.INFO emails:suppressed

BF.RESERVE nhận tỉ lệ lỗi và sức chứa rồi tự làm phần toán giùm mình. Nếu chèn vượt sức chứa, RedisBloom mặc định thêm một sub-filter mới (scaling) chứ không âm thầm xuống cấp, đổi lại tốn thêm memory và tra cứu chậm hơn chút. Từ Laravel thì gửi command dạng raw:

namespace App\Support;

use Illuminate\Support\Facades\Redis;

final class RedisBloom
{
    public function __construct(private string $key) {}

    public function add(string ...$items): void
    {
        Redis::executeRaw(['BF.MADD', $this->key, ...$items]);
    }

    public function mightContain(string $item): bool
    {
        return (int) Redis::executeRaw(['BF.EXISTS', $this->key, $item]) === 1;
    }
}

Mấy use case Redis điển hình: "user này đã thấy bài này chưa" để lọc trùng feed, hàng đợi URL của crawler ("mình đã fetch URL này chưa"), kiểm tra sơ bộ username hay mã coupon còn trống không, và logic rate limiting kiểu "lần đầu thấy IP này". Nếu chỉ có Redis thường, thuật toán y vậy chạy được với SETBIT/GETBIT trên một string key, tính vị trí trong PHP rồi pipeline các command.

Kiểm thử

Có ba tính chất quan trọng: không bao giờ có false negative, tỉ lệ false positive gần mục tiêu, và serialize không mất dữ liệu. Với một tập key sinh cố định, mấy test này tất định vì hash là tất định.

// tests/Unit/BloomFilterTest.php
use App\Support\BloomFilter;

it('never returns a false negative', function () {
    $filter = BloomFilter::forCapacity(10_000, 0.01);
    foreach (range(1, 10_000) as $i) {
        $filter->add("user-{$i}@example.com");
    }

    foreach (range(1, 10_000) as $i) {
        expect($filter->mightContain("user-{$i}@example.com"))->toBeTrue();
    }
});

it('keeps the false positive rate near the target', function () {
    $filter = BloomFilter::forCapacity(10_000, 0.01);
    foreach (range(1, 10_000) as $i) {
        $filter->add("user-{$i}");
    }

    $hits = 0;
    foreach (range(1, 50_000) as $i) {
        $hits += $filter->mightContain("stranger-{$i}") ? 1 : 0;
    }

    expect($hits / 50_000)->toBeLessThan(0.02);
});

it('survives a serialize round trip', function () {
    $filter = BloomFilter::forCapacity(1_000, 0.01);
    $filter->add('hello');

    $copy = BloomFilter::unserialize($filter->serialize());

    expect($copy->size)->toBe($filter->size)
        ->and($copy->hashes)->toBe($filter->hashes)
        ->and($copy->mightContain('hello'))->toBeTrue()
        ->and($copy->mightContain('world'))->toBeFalse();
});

Test false positive assert theo gấp đôi mục tiêu chứ không theo đúng mục tiêu: tỉ lệ đo được dao động chút đỉnh tùy key, và test có mặt để bắt hash hỏng hay tính sai kích thước, mấy lỗi đó lộ ra ở mức 10% hay 50%, không phải 1,1%.

Những lỗi hay gặp

  • Coi "có thể" là "có". Bloom filter chỉ giúp bỏ qua việc khi câu trả lời là "không". Thứ gì chặn user, trừ tiền hay xóa dữ liệu dựa trên một câu "có thể" thì phải xác nhận lại với nguồn dữ liệu gốc.
  • Tính thiếu kích thước. Tỉ lệ false positive tăng nhanh khi vượt sức chứa. Tính theo mức tối đa dự kiến, theo dõi số phần tử đã chèn, và build lại hoặc đổi sang filter co giãn trước khi chạm ngưỡng.
  • Cố xóa phần tử. Tắt bit sẽ sinh ra false negative. Nếu cần xóa, xài counting Bloom filter hoặc Cuckoo filter (command CF.* trong Redis), hoặc định kỳ build lại từ database.
  • Chuẩn hóa không nhất quán. [email protected] với [email protected] hash ra khác nhau. Chuẩn hóa y chang nhau lúc chèn và lúc tra.
  • Hash yếu hoặc tương quan. crc32 của mấy chuỗi na ná nhau, hay hai hash lấy từ cùng 32 bit, làm vị trí bị dồn cục và tăng false positive. Xài hash tốt 64 hoặc 128 bit và lấy h1, h2 từ hai phần khác nhau của nó.
  • Xài filter ở chỗ một set là đủ. Với 10.000 phần tử, một mảng PHP hay Redis set cho kết quả chính xác mà vẫn nhỏ xíu.

Khi nào nên và không nên xài Bloom filter

Nên xài khi:

  • đa số lần tra là cho phần tử không có trong tập, và câu trả lời "không" giúp tiết kiệm một query database, một lần đọc disk hay một lần gọi network;
  • tập dữ liệu lớn (hàng triệu phần tử) và memory là chuyện đáng tính;
  • chấp nhận được một tỉ lệ nhỏ lần tra "có thể" bị dư vì phía sau còn bước kiểm tra chính xác chậm hơn;
  • cần chuyển dữ liệu về sự có mặt tới nhiều node hay client với chi phí thấp.

Không nên khi:

  • cần câu trả lời chính xác mà không có đường lùi;
  • cần xóa phần tử, liệt kê chúng hay gắn giá trị cho chúng;
  • tập đủ nhỏ để một cấu trúc chính xác chỉ tốn vài megabyte;
  • đa số lần tra là cho phần tử có trong tập, vì khi đó gần như lần nào cũng phải xuống database và filter chẳng tiết kiệm được gì.

Với danh sách chặn của mình, filter biến 3 triệu query mỗi giờ thành khoảng 12.000, và database biến mất luôn khỏi profile của job gửi newsletter.

Thử thách tương tác

Thử thách

Luyện tập ngay điều vừa học. Viết lời giải, mở gợi ý nếu bí.

Đề bài

Cài phần tính kích thước Bloom filter và một Bloom filter nhỏ. optimalSize(int $n, float $p): array (Python: optimal_size(n, p) trả về tuple) trả về [m, k] với m = ceil(-n * ln(p) / (ln 2)^2) và k = max(1, round(m / n * ln 2)); throw InvalidArgumentException (Python: ValueError) trừ khi n >= 1 và 0 < p < 1. BloomFilter(m, k) có: indexes(item) trả về k vị trí bit bằng double hashing, h1 = crc32 của các byte UTF-8 của item, h2 = crc32 của dãy byte đó đảo ngược, OR bit với 1, và vị trí thứ i = (h1 + i * h2) mod m với i từ 0 tới k-1, đúng thứ tự đó (PHP: crc32($item) và crc32(strrev($item)); Python: zlib.crc32(data) và zlib.crc32(data[::-1])); add(item) bật tất cả các bit đó; mightContain(item) (Python: might_contain) trả về false nếu có bất kỳ bit nào của item chưa bật, ngược lại trả về true; bitCount() (Python: bit_count) trả về số bit khác nhau đang bật.

Code khởi tạo

php
/**
 * Optimal Bloom filter size for $n items at false positive rate $p.
 *
 * @return array{0: int, 1: int} [m bits, k hash functions]
 */
function optimalSize(int $n, float $p): array
{
    // TODO: throw InvalidArgumentException unless $n >= 1 and 0 < $p < 1
    // TODO: m = ceil(-n * ln(p) / (ln 2)^2), k = max(1, round(m / n * ln 2))
    throw new LogicException('TODO');
}

final class BloomFilter
{
    /** @var array<int, bool> */
    private array $bits = [];

    public function __construct(public readonly int $m, public readonly int $k) {}

    /** @return list<int> */
    public function indexes(string $item): array
    {
        // TODO: h1 = crc32($item), h2 = crc32(strrev($item)) | 1
        // TODO: return [(h1 + i * h2) % m for i = 0 .. k-1]
        throw new LogicException('TODO');
    }

    public function add(string $item): void
    {
        // TODO: set every bit returned by indexes()
        throw new LogicException('TODO');
    }

    public function mightContain(string $item): bool
    {
        // TODO: false as soon as one bit is not set, true otherwise
        throw new LogicException('TODO');
    }

    public function bitCount(): int
    {
        // TODO: number of distinct bits that are set
        throw new LogicException('TODO');
    }
}
python
import math
import zlib


def optimal_size(n: int, p: float) -> tuple[int, int]:
    """Return (m bits, k hash functions) for n items at false positive rate p."""
    # TODO: raise ValueError unless n >= 1 and 0 < p < 1
    # TODO: m = ceil(-n * ln(p) / (ln 2)^2), k = max(1, round(m / n * ln 2))
    raise NotImplementedError


class BloomFilter:
    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        self.bits: set[int] = set()

    def indexes(self, item: str) -> list[int]:
        # TODO: data = item.encode(); h1 = zlib.crc32(data); h2 = zlib.crc32(data[::-1]) | 1
        # TODO: return [(h1 + i * h2) % m for i in range(k)]
        raise NotImplementedError

    def add(self, item: str) -> None:
        # TODO: set every bit returned by indexes()
        raise NotImplementedError

    def might_contain(self, item: str) -> bool:
        # TODO: False as soon as one bit is not set, True otherwise
        raise NotImplementedError

    def bit_count(self) -> int:
        # TODO: number of distinct bits that are set
        raise NotImplementedError

Lời giải của bạn

Gợi ý

Đã mở hết gợi ý
Gợi ý 1

Xài log() / math.log() cho logarit tự nhiên; làm tròn lên m trước rồi mới tính k từ nó

Gợi ý 2

Một set (hoặc mảng có key là vị trí) là đủ để lưu bit nào đang bật; bitCount chính là kích thước của nó

Gợi ý 3

Ép h2 thành số lẻ bằng | 1 để các vị trí liên tiếp không bị lặp khi h2 bằng 0

Lời giải · php
/**
 * Optimal Bloom filter size for $n items at false positive rate $p.
 *
 * @return array{0: int, 1: int} [m bits, k hash functions]
 */
function optimalSize(int $n, float $p): array
{
    if ($n < 1 || $p <= 0.0 || $p >= 1.0) {
        throw new InvalidArgumentException('Need n >= 1 and 0 < p < 1');
    }
    $m = (int) ceil(-$n * log($p) / (log(2) ** 2));
    $k = max(1, (int) round($m / $n * log(2)));

    return [$m, $k];
}

final class BloomFilter
{
    /** @var array<int, bool> */
    private array $bits = [];

    public function __construct(public readonly int $m, public readonly int $k) {}

    /** @return list<int> */
    public function indexes(string $item): array
    {
        $h1 = crc32($item);
        $h2 = crc32(strrev($item)) | 1;
        $out = [];
        for ($i = 0; $i < $this->k; $i++) {
            $out[] = ($h1 + $i * $h2) % $this->m;
        }

        return $out;
    }

    public function add(string $item): void
    {
        foreach ($this->indexes($item) as $i) {
            $this->bits[$i] = true;
        }
    }

    public function mightContain(string $item): bool
    {
        foreach ($this->indexes($item) as $i) {
            if (!isset($this->bits[$i])) {
                return false;
            }
        }

        return true;
    }

    public function bitCount(): int
    {
        return count($this->bits);
    }
}
Lời giải · python
import math
import zlib


def optimal_size(n: int, p: float) -> tuple[int, int]:
    """Return (m bits, k hash functions) for n items at false positive rate p."""
    if n < 1 or not 0 < p < 1:
        raise ValueError("need n >= 1 and 0 < p < 1")
    m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
    k = max(1, round(m / n * math.log(2)))
    return m, k


class BloomFilter:
    def __init__(self, m: int, k: int) -> None:
        self.m = m
        self.k = k
        self.bits: set[int] = set()

    def indexes(self, item: str) -> list[int]:
        data = item.encode()
        h1 = zlib.crc32(data)
        h2 = zlib.crc32(data[::-1]) | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item: str) -> None:
        self.bits.update(self.indexes(item))

    def might_contain(self, item: str) -> bool:
        return all(i in self.bits for i in self.indexes(item))

    def bit_count(self) -> int:
        return len(self.bits)

Cùng chủ đề PHP