Bloom filter trước SQLite: giảm truy vấn hụt và phát hiện bộ lọc cũ

Bloom filter trước SQLite: giảm truy vấn hụt và phát hiện bộ lọc cũ

Bloom filter có thể giúp bỏ qua truy vấn khóa không tồn tại khi bộ lọc đã chứa đầy đủ các khóa của dữ liệu đang đọc. Kết quả dương tính vẫn phải được xác minh bằng database. Nếu database đã thêm khóa mới mà bộ lọc chưa biết, đường tắt “âm tính thì trả không có” có thể trả lời sai.

Thí nghiệm dưới đây tạo một file SQLite với 20.000 khóa và chạy 100.000 lượt kiểm tra. Với bộ lọc được tính cho đúng quy mô, số câu SELECT giảm từ 100.000 xuống 10.894, toàn bộ câu trả lời vẫn khớp cách hỏi trực tiếp database. Sau đó mã cố ý để bộ lọc cũ và tái hiện một câu trả lời sai. Đây là phép đếm truy vấn thực thi, chưa phải phép đo thời gian chạy.

Bộ lọc quyết định có cần hỏi database

Bài nguyên lý, cấu trúc và các biến thể của Bloom filter trình bày phần nền tảng. Ở đây, công việc cụ thể là trả lời câu hỏi “khóa này có trong bảng SQLite không?” với nhiều lượt tra cứu không tìm thấy, gọi là truy vấn hụt.

Bloom filter chỉ trả lời “có thể có” hoặc “không có trong tập khóa đã được đưa vào bộ lọc”. Trong RocksDB, một ứng dụng thực tế của ý tưởng này là kiểm tra bộ lọc gắn với file SST trước khi tìm tiếp trong dữ liệu. Thí nghiệm Python này tự đặt bộ lọc ở tầng ứng dụng trước SQLite; nó không sử dụng RocksDB hay bật một tùy chọn Bloom filter của SQLite. Tài liệu Bloom filter của RocksDB

Với database và bộ lọc cùng một tập khóa, đường đọc có ba trường hợp:

Kết quả Bloom Hành động Câu trả lời cuối
Âm tính Bỏ qua SELECT Không có
Dương tính; database tìm thấy Chạy SELECT Có
Dương tính; database không tìm thấy Chạy SELECT Không có; đây là false positive

False positive làm tốn thêm truy vấn. Nó không làm sai câu trả lời trong đường đọc này vì database vẫn xác nhận các kết quả dương tính. Trái lại, coi dương tính Bloom là bằng chứng chắc chắn khóa đã có sẽ làm mất bước xác minh cần thiết.

Dữ liệu và cách đếm

Mã tạo 20.000 khóa known:0 đến known:19999, lưu trong cột khóa chính kiểu text của một file SQLite tạm. Workload có 10.000 khóa lấy từ tập đã lưu và 90.000 khóa absent:... tách biệt hoàn toàn. Thứ tự truy vấn được xáo trộn bằng seed 20261119.

Cách chuẩn chạy một câu SELECT có tham số cho mỗi khóa. Cách dùng Bloom chỉ chạy câu đó khi bộ lọc báo dương tính. Mã đối chiếu từng kết quả với cách chuẩn và dùng sqlite3.set_trace_callback để đếm các câu SELECT thực sự được SQLite thực thi trong mỗi lượt. Các câu tạo bảng, nạp dữ liệu và kiểm tra bộ lọc cũ được tách khỏi số đếm workload. Tài liệu sqlite3 của Python 3.10

Hai bộ lọc đều được thêm cùng 20.000 khóa. Bộ thứ nhất được tính cho 20.000 phần tử, bộ thứ hai chỉ được tính cho 10.000 phần tử rồi bị nạp gấp đôi dự kiến. Cả hai có mục tiêu false positive 1% lúc thiết kế.

Cấu hình Thiết kế cho 20.000 khóa Thiết kế cho 10.000 khóa
Khóa thực sự đã thêm 20.000 20.000
Số bit $m$ 191.702 95.851
Số phép băm $k$ 7 7
Số byte của mảng bit 23.963 11.982
Bit đã bật 51,8054% 76,7848%
False positive trên 90.000 khóa vắng 894 14.182
False positive rate đo được 0,9933% 15,7578%
SELECT trong workload 10.894 24.182
Kết quả khác cách chuẩn 0 0

Số byte là độ dài bytearray chứa bit, không phải toàn bộ RAM của đối tượng hay tiến trình Python. Workload cố định này cho một kết quả tái lập; nó không mô tả tất cả phân bố khóa hoặc tải truy vấn production.

Vì sao cùng mục tiêu 1% nhưng đo ra gần 16%?

Với giả định các phép băm phân bố gần đều và độc lập, có thể ước tính tham số từ số phần tử dự kiến $n_0$ và xác suất mong muốn $p_0$:

$$ m = \left\lceil -\frac{n_0\ln p_0}{(\ln 2)^2}\right\rceil,\qquad k = \max\left(1,\operatorname{round}\left(\frac{m}{n_0}\ln 2\right)\right) $$

Khi đã thêm $n$ khóa, một xấp xỉ cho false positive rate là:

$$ p(n) \approx \left(1-e^{-kn/m}\right)^k $$

Thế $n=20\,000$ vào hai cấu hình cho xấp xỉ 1,0039% và 15,7451%, gần các tỷ lệ đo trong bảng. Mục tiêu 1% không tự giữ nguyên khi số khóa tăng vượt thiết kế. Số bit vẫn cố định; càng nhiều bit bật, càng dễ gặp khóa vắng mà mọi vị trí băm của nó đều đã bật.

Mẫu số của false positive rate ở đây là 90.000 lượt hỏi khóa không tồn tại, không phải 100.000 lượt hỏi tổng cộng hoặc 10.894 lượt Bloom báo dương tính. Chính cách chọn mẫu số này cũng được dùng trong phần thống kê point lookup của tài liệu RocksDB đã dẫn.

Chạy lại toàn bộ phép kiểm tra

Lần chạy trong bài dùng Python 3.10.11, SQLite 3.40.1 trên macOS arm64. Mã chỉ dùng thư viện chuẩn và cần Python từ 3.10 vì dùng int.bit_count(). Nó dùng SHA-256 trên tiền tố chỉ số phép băm có độ dài cố định và khóa UTF-8 để kết quả không phụ thuộc hash() ngẫu nhiên theo tiến trình. Đây là cách làm dễ đối chiếu, chưa được tối ưu chi phí hashing cho production. Các công thức xác suất là xấp xỉ theo mô hình băm, không phải bảo đảm từ SHA-256 cho mọi bộ dữ liệu. Tài liệu hashlib

Lưu thành bloom_sqlite_check.py và chạy python3 bloom_sqlite_check.py. Chương trình in phiên bản Python, SQLite và JSON kết quả, đồng thời kiểm tra các điều kiện đúng bằng assert.

  1from contextlib import closing
  2import hashlib
  3import json
  4import math
  5import platform
  6from pathlib import Path
  7import random
  8import sqlite3
  9from tempfile import TemporaryDirectory
 10
 11SEED = 20261119
 12KEY_COUNT = 20_000
 13QUERY_COUNT = 100_000
 14ERROR_RATE = 0.01
 15
 16
 17class BloomFilter:
 18    def __init__(self, capacity, error_rate):
 19        if capacity < 1 or not 0 < error_rate < 1:
 20            raise ValueError("capacity must be positive and error_rate must be between 0 and 1")
 21        self.bit_count = math.ceil(-capacity * math.log(error_rate) / math.log(2) ** 2)
 22        self.hash_count = max(1, round(self.bit_count / capacity * math.log(2)))
 23        self.bits = bytearray((self.bit_count + 7) // 8)
 24
 25    def positions(self, key):
 26        encoded = key.encode("utf-8")
 27        for index in range(self.hash_count):
 28            prefix = b"bloom-v1\0" + SEED.to_bytes(8, "big") + index.to_bytes(4, "big")
 29            digest = hashlib.sha256(prefix + encoded).digest()
 30            yield int.from_bytes(digest, "big") % self.bit_count
 31
 32    def add(self, key):
 33        for position in self.positions(key):
 34            self.bits[position // 8] |= 1 << (position % 8)
 35
 36    def maybe_contains(self, key):
 37        return all(self.bits[position // 8] & (1 << (position % 8))
 38                   for position in self.positions(key))
 39
 40
 41def exact_lookup(connection, key):
 42    return connection.execute("SELECT 1 FROM items WHERE key = ?", (key,)).fetchone() is not None
 43
 44
 45def build_filter(connection, capacity):
 46    bloom = BloomFilter(capacity, ERROR_RATE)
 47    for (key,) in connection.execute("SELECT key FROM items"):
 48        bloom.add(key)
 49    return bloom
 50
 51
 52def measure_filter(connection, bloom, capacity, queries, baseline, trace_counts):
 53    false_positives = 0
 54    for key, truth in zip(queries, baseline):
 55        maybe = bloom.maybe_contains(key)
 56        if maybe:
 57            answer = exact_lookup(connection, key)
 58            false_positives += not truth
 59        else:
 60            answer = False
 61        assert answer == truth
 62    false_negatives = sum(not bloom.maybe_contains(f"known:{i}") for i in range(KEY_COUNT))
 63    assert false_negatives == 0
 64    selects = trace_counts["selects"]
 65    assert selects == baseline.count(True) + false_positives
 66    set_bits = sum(value.bit_count() for value in bloom.bits)
 67    negative_queries = baseline.count(False)
 68    return {
 69        "capacity": capacity,
 70        "inserted_distinct_keys": KEY_COUNT,
 71        "m_bits": bloom.bit_count,
 72        "k_hashes": bloom.hash_count,
 73        "bitarray_bytes": len(bloom.bits),
 74        "set_bits": set_bits,
 75        "bit_occupancy": set_bits / bloom.bit_count,
 76        "approximate_false_positive_rate": (1 - math.exp(-bloom.hash_count * KEY_COUNT / bloom.bit_count)) ** bloom.hash_count,
 77        "negative_queries": negative_queries,
 78        "false_positives": false_positives,
 79        "observed_false_positive_rate": false_positives / negative_queries,
 80        "inserted_key_false_negatives": false_negatives,
 81        "workload_point_selects": selects,
 82        "workload_point_selects_skipped": len(queries) - selects,
 83        "all_answers_match_baseline": True,
 84    }
 85
 86
 87def check_stale_filter(connection, bloom, trace_counts):
 88    counter = 0
 89    while bloom.maybe_contains(f"late:{counter}"):
 90        counter += 1
 91    key = f"late:{counter}"
 92    assert not exact_lookup(connection, key)
 93    with connection:
 94        connection.execute("INSERT INTO items(key) VALUES (?)", (key,))
 95    truth = exact_lookup(connection, key)
 96    trace_counts["selects"] = 0
 97    stale_answer = bloom.maybe_contains(key) and exact_lookup(connection, key)
 98    assert truth and not stale_answer
 99    stale_selects = trace_counts["selects"]
100    assert stale_selects == 0
101    bloom.add(key)
102    trace_counts["selects"] = 0
103    updated_answer = bloom.maybe_contains(key) and exact_lookup(connection, key)
104    updated_selects = trace_counts["selects"]
105    trace_counts["selects"] = 0
106    rebuilt = build_filter(connection, KEY_COUNT)
107    rebuild_selects = trace_counts["selects"]
108    trace_counts["selects"] = 0
109    rebuilt_answer = rebuilt.maybe_contains(key) and exact_lookup(connection, key)
110    rebuilt_selects = trace_counts["selects"]
111    assert updated_answer == rebuilt_answer == truth
112    assert updated_selects == rebuild_selects == rebuilt_selects == 1
113    return {
114        "late_key": key,
115        "database_answer_after_insert": truth,
116        "stale_filter_guard_answer": stale_answer,
117        "stale_guard_point_selects": stale_selects,
118        "answer_after_add": updated_answer,
119        "updated_guard_point_selects": updated_selects,
120        "answer_after_rebuild": rebuilt_answer,
121        "rebuild_full_table_scans": rebuild_selects,
122        "rebuilt_guard_point_selects": rebuilt_selects,
123        "rebuild_distinct_keys": KEY_COUNT + 1,
124    }
125
126
127def main():
128    rng = random.Random(SEED)
129    known_queries = rng.sample([f"known:{i}" for i in range(KEY_COUNT)], 10_000)
130    queries = known_queries + [f"absent:{i}" for i in range(90_000)]
131    rng.shuffle(queries)
132    assert len(queries) == QUERY_COUNT and len(set(queries)) == QUERY_COUNT
133    with TemporaryDirectory(prefix="bloom-sqlite-") as temporary:
134        database = Path(temporary) / "items.sqlite"
135        with closing(sqlite3.connect(database)) as connection:
136            trace_counts = {"selects": 0}
137
138            def trace(statement):
139                if statement.lstrip().upper().startswith("SELECT"):
140                    trace_counts["selects"] += 1
141
142            connection.set_trace_callback(trace)
143            with connection:
144                connection.execute("CREATE TABLE items(key TEXT PRIMARY KEY NOT NULL)")
145                connection.executemany("INSERT INTO items(key) VALUES (?)",
146                                       ((f"known:{i}",) for i in range(KEY_COUNT)))
147            trace_counts["selects"] = 0
148            baseline = [exact_lookup(connection, key) for key in queries]
149            baseline_selects = trace_counts["selects"]
150            assert baseline_selects == QUERY_COUNT
151            assert baseline.count(True) == 10_000
152            rows = []
153            filters = []
154            for capacity in (KEY_COUNT, KEY_COUNT // 2):
155                trace_counts["selects"] = 0
156                bloom = build_filter(connection, capacity)
157                assert trace_counts["selects"] == 1
158                filters.append(bloom)
159                trace_counts["selects"] = 0
160                rows.append(measure_filter(connection, bloom, capacity, queries, baseline, trace_counts))
161            trace_counts["selects"] = 0
162            report = {
163                "python": platform.python_version(),
164                "sqlite": sqlite3.sqlite_version,
165                "machine": platform.machine(),
166                "seed": SEED,
167                "hash": "SHA-256 with seed and hash-index byte prefixes",
168                "target_false_positive_rate": ERROR_RATE,
169                "baseline_workload_point_selects": baseline_selects,
170                "build_full_table_scans_per_filter": 1,
171                "results": rows,
172                "stale_filter": check_stale_filter(connection, filters[0], trace_counts),
173            }
174    print(json.dumps(report, indent=2))
175
176
177if __name__ == "__main__":
178    main()

Bộ lọc cũ làm hỏng đường đọc ra sao?

Sau phần đo, mã tìm một khóa late:... đang được bộ lọc báo âm tính, rồi thêm chỉ vào SQLite. Lần chạy này chọn được late:0. Kết quả truy vấn trực tiếp là có, nhưng đường đọc dùng bộ lọc trả không có và không hỏi database. Sau khi thêm khóa đó vào bộ lọc hoặc dựng lại bộ lọc từ bảng hiện tại, hai cách đọc lại khớp nhau.

Đây là lỗi đồng bộ giữa hai tập dữ liệu. Tính chất “không có false negative” của Bloom filter áp dụng cho các khóa đã được thêm đúng vào chính bộ lọc đó, với cùng quy tắc mã hóa, chuẩn hóa khóa và băm, không bị xóa bit hay hỏng dữ liệu. Nó không chứng minh một bộ lọc cũ biết mọi khóa vừa được ghi vào database.

Ở phần workload tĩnh, mã kiểm tra tất cả 20.000 khóa đã thêm và thu được 0 false negative. Trường hợp khóa mới sau đó không phủ định kiểm tra này: khóa mới chưa nằm trong tập mà bộ lọc đại diện. Trong hệ thống có dữ liệu thay đổi, điều kiện cần bảo vệ là mọi khóa mà đường đọc có thể thấy trong database đều đã được phản ánh trong bộ lọc đang dùng. Tỷ lệ false positive thấp trên một workload tĩnh không tự chứng minh điều kiện đồng bộ này.

Một cách triển khai dễ kiểm soát là ghép bộ lọc với phiên bản dữ liệu bất biến và chỉ công bố cả cặp sau khi dựng xong. Nếu không xác nhận được bộ lọc còn bao phủ dữ liệu đang đọc, hãy bỏ đường tắt và truy vấn database. Việc cập nhật bộ lọc sau một lần ghi chỉ đủ cho ví dụ một tiến trình tuần tự; nhiều writer hoặc nhiều replica cần giao thức công bố, đồng bộ và xử lý lỗi riêng. Đoạn mã trên không thực hiện giao thức đó.

Không được xóa bit tùy tiện khi xóa một dòng: các khóa khác có thể dùng chung bit. Một bộ lọc giữ thêm dấu vết của khóa đã bị xóa thường gây truy vấn thừa; một bộ lọc thiếu khóa đang tồn tại có thể làm đường đọc trả sai. Hai tình huống có hậu quả khác nhau.

Số truy vấn giảm có đủ để chọn Bloom filter?

Với 90% lượt hỏi là khóa vắng, cấu hình đúng bỏ qua 89.106 trong 100.000 câu SELECT, tương ứng 89,106%. Cấu hình quá tải vẫn trả đúng nhưng phải hỏi database nhiều hơn do false positive tăng. Nếu workload chủ yếu hỏi khóa đã có, ít truy vấn được bỏ qua, trong khi mỗi lượt vẫn phải trả chi phí kiểm tra bộ lọc.

Thí nghiệm chưa đo thời gian hash, độ trễ truy vấn, page cache, chi phí dựng và phân phối bộ lọc hay tải đồng thời. Vì vậy không thể đổi mức giảm số SELECT thành cùng mức giảm thời gian chạy, số lần đọc đĩa hoặc chi phí hệ thống. SQLite có chỉ mục trên khóa chính, và dữ liệu nhỏ có thể đã nằm trong cache; bộ lọc Python tự viết vẫn có thể làm tổng thời gian tăng.

Nếu mục tiêu là xử lý dữ liệu lớn hơn thay vì lọc point lookup, xem thí nghiệm DuckDB phân tích CSV với ngân sách bộ nhớ giới hạn. Hai phép thử minh họa cùng một yêu cầu khi chọn tối ưu: đo đúng đại lượng cần cải thiện và giữ một kết quả chuẩn để phát hiện thay đổi hành vi.

Bình luận