LSM-tree so với B-tree: ghi tuần tự đổi lấy đọc nhiều bảng hơn

Câu hỏi bài này trả lời: LSM-tree ghi nhanh vì chỉ ghi tuần tự, vậy cái giá là gì: mỗi entry bị ghi lại bao nhiêu lần, mỗi lần tra cứu phải mở bao nhiêu bảng, và Bloom filter cùng compaction đổi hai con số đó ra sao khi đặt cạnh B-tree?

Cần biết trước: composite index (B-tree), Bloom filter và skip list và hash table. Lab là mô phỏng đếm bằng thư viện chuẩn của Python 3.14.4 trên macOS arm64, không ghi tệp thật và không đo thời gian: đây không phải benchmark của engine thật.

Ba thành phần và ba thước đo

LSM-tree (log-structured merge-tree) không sửa dữ liệu tại chỗ. Mỗi lần ghi đi vào memtable, một cấu trúc có thứ tự nằm trong RAM; wiki RocksDB ghi rằng cài đặt mặc định của memtable dựa trên skip list, và memtable đầy thì thành bất biến rồi một luồng nền ghi nó ra tệp SST. Mỗi lần xả như vậy tạo một bảng (SSTable, trong code gọi là run) đã sắp xếp và bất biến trên đĩa. Càng nhiều bảng thì mỗi lần tra cứu càng phải xem nhiều bảng, nên compaction gộp các bảng lại, giữ bản mới nhất của mỗi khóa và bỏ các bản bị ghi đè (tài liệu LevelDB còn nói compaction bỏ dấu xóa khi không tầng sâu hơn nào còn chứa khoảng khóa đó). Mỗi bảng có thể kèm một Bloom filter trong RAM để bỏ qua bảng chắc chắn không có khóa; RocksDB tạo filter cho từng tệp SST mới khi cấu hình chính sách filter.

Bài báo gốc (O’Neil, Cheng, Gawlick, O’Neil, Acta Informatica 1996) mô tả cùng ý dưới dạng nhiều thành phần C0 (trong bộ nhớ) và C1, C2… (trên đĩa, kích thước tăng dần) nối nhau bằng một tiến trình gộp cuốn chiếu (rolling merge). Bài nói thẳng về cái giá: tra cứu cần phản hồi ngay có thể mất hiệu quả I/O, nên LSM-tree hữu ích nhất khi số lần insert nhiều hơn số lần tra cứu, và với ba thành phần trở lên mỗi lần tra cứu thường tốn thêm khoảng một lần đọc trang cho mỗi thành phần trên đĩa.

Bài đo ba thứ, đều theo đơn vị đếm:

• Write amplification (WA): số entry mà xả memtable và compaction ghi xuống bảng, chia cho số entry người dùng ghi.
• Read amplification: số bảng phải đọc cho một lần tra cứu khóa. Đọc Bloom filter trong RAM không tính là đọc bảng.
• Space amplification: số entry đang lưu chia cho số khóa còn sống.

Byte, thời gian, cache của hệ điều hành và nén nằm ngoài mô hình.

Lab: memtable, bảng bất biến và ba chính sách compaction

Tạo thư mục trống rồi lưu mô phỏng. ratio là hệ số kích thước giữa hai tầng liền nhau. Chính sách leveled giữ tối đa một bảng mỗi tầng: khi bảng của tầng i đạt memtable × ratio^(i+1) entry thì cả bảng được gộp xuống tầng i+1. Chính sách tiered giữ tới ratio bảng mỗi tầng và gộp chúng thành một bảng ở tầng sau khi đủ ratio. Chính sách none không bao giờ gộp. Mỗi bảng có Bloom filter 10 bit mỗi entry và k = 7 (theo bài trước, dương tính giả lý thuyết khoảng 0,82%); bộ trộn 64 bit nhanh thay cho BLAKE2b để dựng filter mỗi lần compaction, và lab đo dương tính giả qua số bảng đọc thừa nên không dựa vào giả định độc lập của công thức.

import bisect
from collections import defaultdict

MASK = (1 << 64) - 1


def mix(x: int) -> int:
    """Bộ trộn 64 bit (dạng splitmix64): đủ nhanh để dựng Bloom filter nhiều lần."""
    x = (x + 0x9E3779B97F4A7C15) & MASK
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
    return x ^ (x >> 31)


class Bloom:
    def __init__(self, count: int, bits_per_key: int = 10, k: int = 7) -> None:
        self.m = max(64, count * bits_per_key)
        self.k = k
        self.bits = bytearray(self.m)

    def positions(self, key: int) -> list[int]:
        h1 = mix(key)
        h2 = mix(h1) | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key: int) -> None:
        for position in self.positions(key):
            self.bits[position] = 1

    def __contains__(self, key: int) -> bool:
        return all(self.bits[position] for position in self.positions(key))


class Run:
    """SSTable: danh sách khóa đã sắp, bất biến sau khi tạo, kèm Bloom filter."""

    def __init__(self, items: list[tuple[int, int]]) -> None:
        self.keys = [key for key, _ in items]
        self.values = [value for _, value in items]
        self.bloom = Bloom(len(items))
        for key in self.keys:
            self.bloom.add(key)

    def __len__(self) -> int:
        return len(self.keys)

    def find(self, key: int) -> int | None:
        index = bisect.bisect_left(self.keys, key)
        if index < len(self.keys) and self.keys[index] == key:
            return self.values[index]
        return None


def merge(newest_first: list[Run]) -> list[tuple[int, int]]:
    """Gộp các run đã sắp; với khóa trùng giữ bản của run mới nhất."""
    merged: dict[int, int] = {}
    for run in reversed(newest_first):
        merged.update(zip(run.keys, run.values))
    return sorted(merged.items())


class LSM:
    """policy: none (không compact), tiered (gộp `ratio` run cùng tầng) hoặc leveled (mỗi tầng một run)."""

    def __init__(self, memtable_size: int, ratio: int, policy: str) -> None:
        assert policy in ("none", "tiered", "leveled")
        self.memtable: dict[int, int] = {}
        self.memtable_size = memtable_size
        self.ratio = ratio
        self.policy = policy
        self.levels: list[list[Run]] = []
        self.written: dict[int, int] = defaultdict(int)
        self.user_writes = 0

    def put(self, key: int, value: int) -> None:
        self.user_writes += 1
        self.memtable[key] = value
        if len(self.memtable) >= self.memtable_size:
            run = Run(sorted(self.memtable.items()))
            self.memtable = {}
            self.add_run(0, run)

    def add_run(self, level: int, run: Run) -> None:
        while len(self.levels) <= level:
            self.levels.append([])
        if self.policy == "leveled":
            existing = self.levels[level]
            if existing:
                run = Run(merge([run, *existing]))
            self.written[level] += len(run)
            capacity = self.memtable_size * self.ratio ** (level + 1)
            if len(run) >= capacity:
                self.levels[level] = []
                self.add_run(level + 1, run)
            else:
                self.levels[level] = [run]
            return
        self.written[level] += len(run)
        self.levels[level].append(run)
        if self.policy == "tiered" and len(self.levels[level]) >= self.ratio:
            runs = self.levels[level]
            self.levels[level] = []
            self.add_run(level + 1, Run(merge(list(reversed(runs)))))

    def get(self, key: int, use_bloom: bool) -> tuple[int | None, int]:
        """Trả về (giá trị, số run phải đọc); Bloom filter nằm trong RAM nên không tính là đọc."""
        if key in self.memtable:
            return self.memtable[key], 0
        reads = 0
        for level in self.levels:
            for run in reversed(level):
                if use_bloom and key not in run.bloom:
                    continue
                reads += 1
                value = run.find(key)
                if value is not None:
                    return value, reads
        return None, reads

    def runs(self) -> int:
        return sum(len(level) for level in self.levels)

    def stored(self) -> int:
        return len(self.memtable) + sum(len(run) for level in self.levels for run in level)

Compaction đổi chi phí ghi lấy chi phí đọc

Hai workload, memtable 128 entry. Workload chèn: 50.000 khóa ngẫu nhiên khác nhau vào store trống, rồi tra khóa có và khóa vắng (10.000 lần mỗi loại; riêng none dùng 1.000 lần vì có 390 bảng). Workload ghi đè: 50.000 lần ghi vào 10.000 khóa. Lab dừng nếu có lần tra nào trả sai giá trị, nếu số bảng đọc cho khóa vắng khi không dùng Bloom khác số bảng đang có, nếu số bảng đọc thừa khi có Bloom lệch 25% trở lên so với số bảng × 0,82% hoặc Bloom giảm đọc dưới 80 lần, nếu số lần ghi mỗi tầng lệch công thức từ 8% trở lên ở các tầng đã quay đủ ít nhất 3 vòng, nếu leveled r = 10 có WA không lớn hơn 10, nếu tiered r = 4 ghi không ít hơn leveled r = 4, hoặc nếu tiered r = 10 không tốn dung lượng hơn leveled r = 10 ở workload ghi đè.

import math
import random
import statistics

from lsm import LSM

MEMTABLE = 128
INSERTS = 50_000
KEYSPACE = 10_000
UPDATES = 50_000
FALSE_POSITIVE = (1 - math.exp(-7 / 10)) ** 7
CONFIGS = (("leveled", 4), ("leveled", 10), ("tiered", 4), ("tiered", 10), ("none", 0))


def probe(tree: LSM, sample: list[int], use_bloom: bool) -> float:
    return statistics.fmean(tree.get(key, use_bloom)[1] for key in sample)


def insert_only(policy: str, ratio: int) -> dict:
    rng = random.Random(7)
    keys = rng.sample(range(10_000_000), INSERTS)
    tree = LSM(MEMTABLE, ratio, policy)
    for seq, key in enumerate(keys):
        tree.put(key, seq)
    probes = 1_000 if policy == "none" else 10_000
    present = [rng.choice(keys) for _ in range(probes)]
    seen = set(keys)
    absent: list[int] = []
    while len(absent) < probes:
        key = rng.randrange(10_000_000)
        if key not in seen:
            absent.append(key)
    truth = dict(zip(keys, range(INSERTS)))
    assert all(tree.get(key, use)[0] == truth[key] for key in present[:300] for use in (False, True))
    assert all(tree.get(key, use)[0] is None for key in absent[:300] for use in (False, True))
    return {
        "runs": tree.runs(),
        "wa": sum(tree.written.values()) / tree.user_writes,
        "per_level": [tree.written[i] / tree.user_writes for i in range(len(tree.levels))],
        "present": (probe(tree, present, False), probe(tree, present, True)),
        "absent": (probe(tree, absent, False), probe(tree, absent, True)),
    }


def overwrite(policy: str, ratio: int) -> dict:
    rng = random.Random(11)
    tree = LSM(MEMTABLE, ratio, policy)
    truth: dict[int, int] = {}
    for seq in range(UPDATES):
        key = rng.randrange(KEYSPACE)
        tree.put(key, seq)
        truth[key] = seq
    assert all(tree.get(key, True)[0] == value for key, value in truth.items())
    return {
        "wa": sum(tree.written.values()) / tree.user_writes,
        "space": tree.stored() / len(truth),
    }


def run_all() -> dict[str, dict]:
    rows: dict[str, dict] = {}
    for policy, ratio in CONFIGS:
        name = f"{policy} r={ratio}" if ratio else policy
        rows[name] = {
            "policy": policy,
            "ratio": ratio,
            "insert": insert_only(policy, ratio),
            "overwrite": overwrite(policy, ratio),
        }
    return rows


def main() -> None:
    rows = run_all()
    for name, row in rows.items():
        first, second = row["insert"], row["overwrite"]
        print(
            f"{name:12}: {first['runs']:3} run | WA {first['wa']:5.2f}"
            f" | khóa có {first['present'][0]:6.2f} -> {first['present'][1]:5.2f} run"
            f" | khóa vắng {first['absent'][0]:6.2f} -> {first['absent'][1]:5.3f} run"
            f" | ghi đè: WA {second['wa']:5.2f}, không gian x{second['space']:.2f}"
        )
        assert first["absent"][0] == first["runs"]
        expected = first["runs"] * FALSE_POSITIVE
        assert abs(first["absent"][1] - expected) / expected < 0.25
        assert first["absent"][0] / first["absent"][1] > 80
    for name, row in rows.items():
        policy, ratio, per_level = row["policy"], row["ratio"], row["insert"]["per_level"]
        if policy == "none":
            assert abs(row["insert"]["wa"] - 1) < 0.01
            continue
        expected = (ratio + 1) / 2 if policy == "leveled" else 1.0
        full = [
            level
            for level in range(len(per_level))
            if INSERTS / (MEMTABLE * ratio ** (level + 1)) >= 3
        ]
        print(
            f"{name:12}: ghi mỗi tầng {' '.join(f'{w:.2f}' for w in per_level)}"
            f" (công thức {expected:.2f} cho tầng {', '.join(map(str, full))} đã quay đủ vòng)"
        )
        assert all(abs(per_level[level] - expected) / expected < 0.08 for level in full)
    assert rows["leveled r=10"]["insert"]["wa"] > 10
    assert rows["tiered r=4"]["insert"]["wa"] < rows["leveled r=4"]["insert"]["wa"]
    assert rows["tiered r=10"]["overwrite"]["space"] > rows["leveled r=10"]["overwrite"]["space"]
    print("mô phỏng khớp: đọc đúng giá trị, đếm bảng, công thức ghi mỗi tầng, tác dụng của Bloom filter")


if __name__ == "__main__":
    main()

python3 -B lsm_stats.py

leveled r=4 :   4 run | WA 10.20 | khóa có   3.63 ->  1.02 run | khóa vắng   4.00 -> 0.035 run | ghi đè: WA  7.69, không gian x1.81
leveled r=10:   2 run | WA 12.40 | khóa có   1.77 ->  1.00 run | khóa vắng   2.00 -> 0.016 run | ghi đè: WA 11.37, không gian x1.04
tiered r=4  :   6 run | WA  4.61 | khóa có   5.45 ->  1.04 run | khóa vắng   6.00 -> 0.052 run | ghi đè: WA  3.73, không gian x2.15
tiered r=10 :  12 run | WA  2.76 | khóa có   9.61 ->  1.07 run | khóa vắng  12.00 -> 0.103 run | ghi đè: WA  2.35, không gian x3.27
none        : 390 run | WA  1.00 | khóa có 203.03 ->  2.88 run | khóa vắng 390.00 -> 3.518 run | ghi đè: WA  0.99, không gian x5.00
leveled r=4 : ghi mỗi tầng 2.49 2.47 2.46 2.13 0.66 (công thức 2.50 cho tầng 0, 1, 2 đã quay đủ vòng)
leveled r=10: ghi mỗi tầng 5.49 5.38 1.54 (công thức 5.50 cho tầng 0, 1 đã quay đủ vòng)
tiered r=4  : ghi mỗi tầng 1.00 0.99 0.98 0.98 0.66 (công thức 1.00 cho tầng 0, 1, 2 đã quay đủ vòng)
tiered r=10 : ghi mỗi tầng 1.00 1.00 0.77 (công thức 1.00 cho tầng 0, 1 đã quay đủ vòng)
mô phỏng khớp: đọc đúng giá trị, đếm bảng, công thức ghi mỗi tầng, tác dụng của Bloom filter

Đọc kết quả. Mũi tên trong cột đọc là số bảng phải đọc khi không dùng Bloom filter rồi khi có:

• Compaction đổi ghi lấy đọc. Không compact thì mỗi entry chỉ ghi một lần (WA 1,00) nhưng tra khóa vắng phải mở cả 390 bảng. Leveled r = 10 ghi mỗi entry 12,4 lần và chỉ còn 2 bảng. Tiered nằm giữa: WA 2,76 với 12 bảng, hoặc 4,61 với 6 bảng. Đây là điều bài báo gốc nói bằng ngôn ngữ chi phí I/O: gộp hoãn và theo lô làm insert rẻ, đổi lại mỗi tra cứu thêm việc.
• Leveled ghi lại mỗi entry (r+1)/2 lần ở mỗi tầng. Số ghi mỗi tầng đo được là 2,49, 2,47, 2,46 ở r = 4 (công thức 2,5) và 5,49, 5,38 ở r = 10 (công thức 5,5). Lý do: một entry vào tầng i+1 ở lần gộp thứ j trong r lần của một chu kỳ, rồi bị ghi lại ở mọi lần gộp sau trong chu kỳ đó, trung bình 1 + (r−1)/2 lần. Tăng r làm ít tầng hơn nhưng mỗi tầng ghi lại nhiều hơn, nên WA tổng của leveled không giảm khi r tăng (10,2 ở r = 4, 12,4 ở r = 10). Bài báo gốc đếm r_i + 1 trang ghi cho mỗi trang chuyển xuống một thành phần trong gộp cuốn chiếu, và wiki RocksDB nhắc rằng WA của leveled compaction thường lớn hơn 10, cùng cỡ với 12,4 ở đây; ba cách gộp (cuốn chiếu, từng tệp, cả tầng) khác nhau nên hệ số cụ thể khác nhau, bài không đòi khớp.
• Tiered ghi mỗi entry một lần mỗi tầng. WA bằng cỡ số tầng (số ghi mỗi tầng đều gần 1,00), đổi lại phải đọc nhiều bảng hơn và giữ nhiều bản cũ hơn: ở workload ghi đè, không gian là ×2,15 và ×3,27 so với ×1,81 và ×1,04 của leveled. Khớp với mô tả của RocksDB về universal compaction: nhắm WA thấp hơn và đổi bằng read amplification và space amplification.
• Bloom filter cắt đọc khóa vắng ở mọi chính sách. Số bảng đọc thừa xấp xỉ số bảng × 0,82% (leveled r = 4: 4 bảng cho 0,035), tức giảm khoảng 110 đến 125 lần ở cả năm cấu hình. Tài liệu LevelDB cũng nói 10 bit mỗi khóa giảm số lần đọc đĩa không cần thiết cho Get() khoảng 100 lần. Với khóa có, còn khoảng 1,0 đến 1,07 bảng.
• Bloom filter không thay compaction. Không compact mà có Bloom vẫn đọc 3,5 bảng cho khóa vắng và 2,88 bảng cho khóa có, so với 0,016 và 1,00 của leveled r = 10, và mỗi lần tra phải kiểm tra tới 390 filter trong RAM (bài không đo chi phí này). Bloom filter chỉ trả lời “khóa này có không”, nên không giúp quét theo dải (lập luận, không đo).
• Compaction bỏ bản cũ. Workload ghi đè lưu 50.000 lần ghi cho 10.000 khóa: không compact giữ ×5,00 entry, còn compaction đưa về ×1,04 đến ×3,27 tùy chính sách. Số này phụ thuộc vào việc 10.000 khóa sống nằm ở tầng nào lúc kết thúc, nên chỉ có thứ tự giữa các chính sách là kết luận của bài.

B-tree theo mô hình đếm

Bài báo gốc đếm B-tree như sau: insert với khóa ngẫu nhiên đọc một trang lá rồi ghi lại nó, khoảng D_e + 1 trang ngẫu nhiên với D_e là số trang trung bình không nằm trong buffer lúc tìm; các trang lá ít khi được tham chiếu lại trước khi bị đẩy khỏi buffer nên các insert không gộp được vào cùng một lần ghi trang. LSM-tree thì gộp nhiều entry vào mỗi lần ghi (bài báo lấy ví dụ C0 bằng 1/25 C1 và 250 entry mỗi trang, cho khoảng 10 entry mỗi lần gộp). Lab dựng mô hình đếm cho tầng lá: 8.192 lá, mỗi lá 128 entry, khóa insert ngẫu nhiên đều, cache LRU giữ một phần f số lá, lá bẩn bị đẩy ra thì ghi xuống đĩa. Các nút trong, nhật ký ghi trước và việc tách lá không được tính.

import random
from collections import OrderedDict

ENTRIES_PER_PAGE = 128
LEAVES = 8_192
WARMUP = 4 * LEAVES
INSERTS = 100_000


def simulate(cached_fraction: float, seed: int = 5) -> tuple[float, float]:
    """Mô hình đếm: chỉ tầng lá, khóa ngẫu nhiên đều; lá bẩn bị đẩy khỏi cache thì ghi ra đĩa."""
    rng = random.Random(seed)
    capacity = int(LEAVES * cached_fraction)
    cache: OrderedDict[int, None] = OrderedDict()
    reads = writes = 0
    for step in range(WARMUP + INSERTS):
        counted = step >= WARMUP
        leaf = rng.randrange(LEAVES)
        if leaf in cache:
            cache.move_to_end(leaf)
            continue
        cache[leaf] = None
        reads += counted
        if len(cache) > capacity:
            cache.popitem(last=False)
            writes += counted
    return reads / INSERTS, writes / INSERTS


if __name__ == "__main__":
    for fraction in (0.01, 0.1, 0.5):
        reads, writes = simulate(fraction)
        print(
            f"cache {fraction:.0%} số lá: đọc {reads:.3f} ghi {writes:.3f} trang ngẫu nhiên mỗi insert"
            f" (mô hình 1-f = {1 - fraction:.3f}), {ENTRIES_PER_PAGE * writes:.1f} entry ghi ra mỗi entry chèn"
        )
        assert abs(reads - (1 - fraction)) < 0.02 and abs(writes - (1 - fraction)) < 0.02

python3 -B btree_model.py

cache 1% số lá: đọc 0.991 ghi 0.991 trang ngẫu nhiên mỗi insert (mô hình 1-f = 0.990), 126.8 entry ghi ra mỗi entry chèn
cache 10% số lá: đọc 0.903 ghi 0.903 trang ngẫu nhiên mỗi insert (mô hình 1-f = 0.900), 115.5 entry ghi ra mỗi entry chèn
cache 50% số lá: đọc 0.501 ghi 0.501 trang ngẫu nhiên mỗi insert (mô hình 1-f = 0.500), 64.1 entry ghi ra mỗi entry chèn

Đọc và ghi đều đúng 1 − f trang ngẫu nhiên mỗi insert (lab dừng nếu lệch từ 0,02 trở lên): mỗi lần trượt cache là một lần đọc lá, và lá vừa nạp đã bẩn nên khi bị đẩy ra là một lần ghi. Với trang 128 entry, đó là 64 đến 127 entry ghi ra mỗi entry chèn. Con số này phụ thuộc trực tiếp vào số entry mỗi trang và vào việc mỗi insert làm bẩn một trang riêng; B-tree thật có nhật ký ghi trước, checkpoint và cache lớn hơn nên không nên đọc nó như WA của một engine cụ thể.

Cùng một workload, cạnh nhau

Lab cuối chạy lại mô phỏng LSM (workload chèn) và mô hình B-tree với cache 10% số lá, rồi in chung. Cột “ghi ngẫu nhiên” là số trang ghi ngẫu nhiên mỗi insert: LSM bằng 0 theo cấu trúc vì xả memtable và compaction chỉ ghi bảng liền khối. Số trong ngoặc ở cột đọc là khi có Bloom filter.

from btree_model import ENTRIES_PER_PAGE, simulate
from lsm_stats import run_all

rows = run_all()
reads, writes = simulate(0.1)
print(f"{'cách':22} {'ghi: entry/insert':>18} {'ghi ngẫu nhiên':>15} {'đọc khóa vắng':>16} {'đọc khóa có':>14}")
print(
    f"{'B-tree, cache 10% lá':22} {ENTRIES_PER_PAGE * writes:18.1f} {writes:15.2f}"
    f" {1.0:16.2f} {1.0:14.2f}"
)
labels = (
    ("none", "LSM không compact"),
    ("tiered r=10", "LSM tiered r=10"),
    ("leveled r=10", "LSM leveled r=10"),
)
for name, label in labels:
    first = rows[name]["insert"]
    print(
        f"{label:22} {first['wa']:18.2f} {0:15.2f}"
        f" {first['absent'][0]:8.2f} ({first['absent'][1]:5.3f})"
        f" {first['present'][0]:7.2f} ({first['present'][1]:4.2f})"
    )
leveled = rows["leveled r=10"]["insert"]
assert ENTRIES_PER_PAGE * writes > 5 * leveled["wa"]
assert leveled["absent"][1] < 1.0 and abs(leveled["present"][1] - 1.0) < 0.1
assert rows["none"]["insert"]["absent"][1] > 100 * leveled["absent"][1]
print("LSM leveled có Bloom đọc cỡ B-tree nhưng ghi ít hơn nhiều; không compact thì đọc đắt")

python3 -B compare.py

cách                    ghi: entry/insert  ghi ngẫu nhiên    đọc khóa vắng    đọc khóa có
B-tree, cache 10% lá                115.5            0.90             1.00           1.00
LSM không compact                    1.00            0.00   390.00 (3.518)  203.03 (2.88)
LSM tiered r=10                      2.76            0.00    12.00 (0.103)    9.61 (1.07)
LSM leveled r=10                    12.40            0.00     2.00 (0.016)    1.77 (1.00)
LSM leveled có Bloom đọc cỡ B-tree nhưng ghi ít hơn nhiều; không compact thì đọc đắt

Trong mô hình đếm này, LSM leveled r = 10 có Bloom filter tra cứu điểm tốn cỡ B-tree (1,00 bảng khi có khóa, 0,016 khi vắng, so với một trang lá) trong khi ghi ra khoảng 12 entry mỗi entry chèn thay vì khoảng 115, và không có trang ghi ngẫu nhiên nào. Lợi ích đọc đó có điều kiện: compaction phải theo kịp để số bảng ở mức 2; Bloom filter chiếm 10 bit RAM mỗi entry; và bài không đo quét theo dải (mỗi bảng đều phải xem), độ trễ do compaction chạy nền, chi phí đọc của chính compaction, hay thời gian thật.

Chọn gì trong từng tình huống

Giới hạn

• Mô phỏng đếm entry và lần đọc bảng; bài không đo byte, thời gian, I/O thật, cache của hệ điều hành, nén, nhật ký ghi trước, compaction song song hay độ trễ do compaction. Hằng số của đĩa và SSD nằm ngoài mô hình.
• Chính sách leveled trong lab gộp cả tầng xuống tầng sau; tài liệu LevelDB và RocksDB gộp từng tệp chồng khoảng với tầng sau nên hệ số WA cụ thể khác, và bài không dùng lab để dự đoán WA của engine nào.
• Bài không cài xóa với dấu xóa, quét theo dải, đọc nhất quán theo snapshot hay phục hồi sau sự cố; việc compaction bỏ dấu xóa chỉ nêu theo tài liệu LevelDB.
• Mô hình B-tree chỉ có tầng lá, khóa insert ngẫu nhiên đều, trang 128 entry là tham số và quyết định trực tiếp con số ghi mỗi insert; không có tách lá, nút trong hay nhật ký ghi trước.
• Bloom filter trong lab dùng bộ trộn nhanh thay cho BLAKE2b của bài trước, và đo dương tính giả qua số bảng đọc thừa thay vì suy từ công thức.
• Số đo thuộc Python 3.14.4 trên macOS arm64. Bài không suy ra tốc độ hay hành vi của RocksDB, LevelDB, Cassandra hay engine nào khác.
• Lab không ghi tệp ngoài thư mục bạn đã tạo; xóa thư mục đó là dọn xong.

Học tiếp và nguồn

• Bloom filter và skip list: ngẫu nhiên có chủ đích, sai số đo được: skip list làm memtable và Bloom filter làm bộ lọc của từng bảng.
• Composite index: thứ tự cột và chi phí ghi: B-tree trong database quan hệ.
• Hash table: va chạm, load factor và vì sao O(1) chỉ là kỳ vọng: hàm băm dùng để dựng Bloom filter.
• Patrick O’Neil và cộng sự, The Log-Structured Merge-Tree (LSM-Tree), Acta Informatica, 1996 (bản trên trang của tác giả, đọc 18 trang đầu): thành phần C0, C1, gộp cuốn chiếu, công thức chi phí insert của B-tree và LSM-tree, kích thước tối ưu của các thành phần.
• Google, LevelDB: implementation notes, phiên bản 1.23: nhật ký và memtable, các tầng, compaction bỏ giá trị bị ghi đè và dấu xóa.
• Google, LevelDB: index.md, phiên bản 1.23: mục Filters, Bloom filter 10 bit mỗi khóa.
• RocksDB wiki, MemTable: memtable mặc định dựa trên skip list, memtable đầy thì thành bất biến và được xả ra SST.
• RocksDB wiki, Leveled Compaction: tầng 0 chứa tệp vừa xả, hệ số kích thước giữa tầng, cách chọn tệp để gộp.
• RocksDB wiki, Universal Compaction: đánh đổi WA thấp hơn lấy read amplification và space amplification.
• RocksDB wiki, RocksDB Bloom Filter: filter cho từng tệp SST, 9,9 bit mỗi khóa cho dương tính giả 1% (công thức của bài trước cho 9,59 bit; bài không kiểm nguyên nhân chênh lệch).

Nguồn trực tuyến đọc ngày 2026-10-04; số đo thuộc Python 3.14.4 trên macOS arm64, không có nghiệm thu Linux hay engine thật.