طراحی دیتابیسهای کلید-مقدار مبتنی بر LSM-Tree (Log-Structured Merge-tree)

حدس RUM و دوراهی بنیادین موتورهای ذخیرهسازی: B+Tree در برابر LSM-Tree

طبق قضیه معروف RUM Conjecture در معماری پایگاههای داده، هیچ موتور ذخیرهسازی نمیتواند به طور همزمان هر سه فاکتور Read Overhead (سربار خواندن)، Update/Write Overhead (سربار نوشتن) و Memory/Storage Overhead (سربار فضا) را بهینه کند؛ شما همیشه مجبورید دو مورد را به قیمت فدا کردن سومی انتخاب کنید.

دیتابیسهای رابطهای سنتی (مانند PostgreSQL و InnoDB در MySQL) از ساختار B+Tree استفاده میکنند. در یک B+Tree، دادهها در صفحات با اندازه ثابت (مثلاً ۸ یا ۱۶ کیلوبایت) روی دیسک نگهداری میشوند. وقتی یک کلید تصادفی را درج یا ویرایش میکنید، دیتابیس باید کل صفحه ۱۶ کیلوبایتی را از دیسک بخواند، تغییر را در محل (In-Place Update) اعمال کند و در صورت پر شدن صفحه، آن را به دو صفحه بشکند (Page Split). این عملیات باعث ایجاد Random I/O شدید و بالا رفتن ضریب تقویت نوشتن (Write Amplification Factor - WAF) میشود؛ به طوری که برای نوشتن ۱۰۰ بایت داده، ۱۶ کیلوبایت روی SSD بازنویسی میگردد!

در مقابل، دیتابیسهای مدرنِ نوشتن-محور (مانند RocksDB، Apache Cassandra، ScyllaDB و CockroachDB/Pebble) بر پایه معماری LSM-Tree (Log-Structured Merge-Tree) طراحی شدهاند که تمام نوشتنهای تصادفی را به نوشتنهای ترتیبی فوقسریع (Sequential Append-Only I/O) تبدیل میکند.

کالبدشکافی مسیر نوشتن (Write Path) در LSM-Tree: چرا درج داده در کسری از میلیثانیه انجام میشود؟

در یک موتور LSM-Tree، هیچ فایلی روی دیسک هرگز در محل ویرایش نمیشود (Immutable Files). مسیر نوشتن یک زوج (Key, Value) تنها شامل دو گام حافظه و نوشتن ترتیبی است:

• ۱. ثبت در گزارش پیشنویس (WAL - Write-Ahead Log): برای تضمین پایداری داده در صورت قطع برق، دستور به انتهای یک فایل ترتیبی روی دیسک (WAL) اضافه میشود.
• ۲. درج در حافظه مرتبشده (MemTable): همزمان، کلید و مقدار در یک ساختار داده مرتب درون رم (معمولاً یک Concurrent SkipList با پیچیدگی $O(\log N)$ بدون نیاز به قفل سراسری) درج میشوند و بلافاصله به کلاینت پاسخ موفقیت داده میشود!
• ۳. تخلیه به دیسک (Flush to L0 SSTable): وقتی حجم MemTable به سقف مشخصی (مثلاً ۶۴ مگابایت) میرسد، به حالت فقط-خواندنی (Immutable MemTable) درآمده و یک ترد پسزمینه آن را به صورت کاملاً مرتب در قالب یک فایل غیرقابل تغییر به نام SSTable (Sorted String Table) در سطح صفر دیسک (Level 0) مینویسد.

نحوه مدیریت حذف رکوردها (Deletes) و نشانگر Tombstone

از آنجا که فایلهای SSTable روی دیسک غیرقابل تغییر (Immutable) هستند، دستور DELETE نمیتواند به سراغ فایلهای قبلی برود و کلید را پاک کند! در عوض، حذف یک کلید در LSM-Tree نیز یک عملیات نوشتن است: یک رکورد ویژه به نام Tombstone (سنگ قبر) با زمان جدیدتر در MemTable درج میشود تا نسخههای قدیمیترِ آن کلید را در زمان خواندن مخفی کند و در نهایت در فرآیند Compaction از روی دیسک پاک نماید.

مسیر خواندن (Read Path) و نقش حیاتی فیلتر بلوم و فهرست تنک (Sparse Index)

قیمت سرعت بالای نوشتن در LSM-Tree، پیچیدهتر شدن مسیر خواندن (Read Amplification) است؛ زیرا آخرین نسخه یک کلید ممکن است در MemTable باشد یا در یکی از دهها فایل SSTable روی دیسک! برای اینکه موتور مجبور نباشد تمام فایلهای دیسک را باز کند، دو بهینهسازی در هر فایل SSTable تعبیه میشود:

• فیلتر بلوم به ازای هر SSTable (Per-SSTable Bloom Filter): پیش از لمس کردن دیسک برای یک فایل SSTable، موتور کلید را در فیلتر بلوم آن فایل (با اختصاص ۱۰ بیت به ازای هر کلید) بررسی میکند. اگر فیلتر بلوم پاسخ منفی بدهد، با ۹۹ درصد اطمینان آن کلید در آن فایل وجود ندارد و کل فایل رد میشود!
• فهرست تنک در رم (Sparse Memory Index): چون کلیدها درون هر SSTable به صورت صعودی مرتب شدهاند، نیازی نیست آدرس تکتک کلیدها را در رم نگه داریم. تنها کلید اولِ هر بلوک ۴ کیلوبایتی (Data Block) در رم نگهداری میشود و با یک جستجوی دودویی (Binary Search)، دقیقاً بلوک هدف از دیسک خوانده میشود.

فرآیند Compaction: نبرد Size-Tiered در برابر Leveled Compaction

با انباشته شدن فایلهای SSTable، تردهای پسزمینه فرآیند Compaction را اجرا میکنند که دقیقاً مانند الگوریتم Merge Sort (مرتبسازی ادغامی چندمسیره)، چندین فایل SSTable را به صورت استریم خوانده، کلیدهای تکراری و Tombstoneها را دور میریزد و فایلهای مرتب جدید میسازد:

• استراتژی Size-Tiered Compaction (پیشفرض Cassandra): فایلهای هماندازه را با هم ادغام میکند. کمترین ضریب تقویت نوشتن (WAF پایین) را دارد، اما به فضای خالی دیسک بسیار زیادی (تا ۵۰ درصد کل دیسک برای Space Amplification) نیاز دارد.
• استراتژی Leveled Compaction (پیشفرض RocksDB): دیسک را به سطوح توانی ($L_1 = 10\text{MB}, L_2 = 100\text{MB}, L_3 = 1\text{GB}, \dots$) تقسیم میکند و تضمین مینماید که در سطوح $L_1$ به بعد، بازه کلیدهای هیچ دو فایلی همپوشانی نداشته باشند. این روش فضای دیسک و تاخیر خواندن را به شدت بهینه میکند.

پیادهسازی موتور ذخیرهسازی LSM-Tree (شامل WAL، MemTable، SSTable، Sparse Index و Bloom Filter) در پایتون

در کد زیر، یک نمونه کارآمد و آموزشی از موتور ذخیرهسازی LSM-Tree از صفر پیادهسازی شده است که چرخه نوشتن در WAL، مرتبسازی در MemTable، پشتیبانی از Tombstone، تخلیه به SSTable با Sparse Index و جستجوی سریع با فیلتر بلوم را نمایش میدهد:

import bisect
import hashlib
import json
import os
from pathlib import Path
from typing import Dict, List, Optional, Tuple

TOMBSTONE = '__LSM_TOMBSTONE__'

class SimpleBloomFilter:
    def __init__(self, size_bits: int = 8192, num_hashes: int = 5):
        self.size_bits = size_bits
        self.num_hashes = num_hashes
        self.bit_array = bytearray(size_bits // 8)

    def _hashes(self, key: str) -> List[int]:
        digest = hashlib.sha256(key.encode('utf-8')).digest()
        h1 = int.from_bytes(digest[:8], 'big')
        h2 = int.from_bytes(digest, 'big')
        return [(h1 + i * h2) % self.size_bits for i in range(self.num_hashes)]

    def add(self, key: str) -> None:
        for bit in self._hashes(key):
            self.bit_array[bit // 8] |= (1 << (bit % 8))

    def might_contain(self, key: str) -> bool:
        return all(self.bit_array[bit // 8] & (1 << (bit % 8)) for bit in self._hashes(key))

class SSTableSegment:
    """Immutable on-disk Sorted String Table with Sparse Index and Bloom Filter."""
    def __init__(self, file_path: Path, sparse_stride: int = 16):
        self.file_path = file_path
        self.sparse_stride = sparse_stride
        self.bloom = SimpleBloomFilter()
        self.sparse_keys: List[str] = []
        self.sparse_offsets: List[int] = []

    @classmethod
    def flush_from_memtable(cls, file_path: Path, sorted_items: List[Tuple[str, str]], stride: int = 16) -> 'SSTableSegment':
        segment = cls(file_path, sparse_stride=stride)
        with open(file_path, 'wb') as f:
            for idx, (k, v) in enumerate(sorted_items):
                offset = f.tell()
                segment.bloom.add(k)
                if idx % stride == 0:
                    segment.sparse_keys.append(k)
                    segment.sparse_offsets.append(offset)
                line = (json.dumps({'k': k, 'v': v}) + '\n').encode('utf-8')
                f.write(line)
        return segment

    def search(self, key: str) -> Optional[str]:
        if not self.bloom.might_contain(key):
            return None  # Fast path: 99% of disk reads avoided via Bloom Filter

        pos = bisect.bisect_right(self.sparse_keys, key) - 1
        if pos < 0:
            return None

        start_offset = self.sparse_offsets[pos]
        with open(self.file_path, 'rb') as f:
            f.seek(start_offset)
            for _ in range(self.sparse_stride):
                line = f.readline()
                if not line:
                    break
                record = json.loads(line.decode('utf-8'))
                if record['k'] == key:
                    return record['v']
                if record['k'] > key:
                    break
        return None

class LSMStorageEngine:
    def __init__(self, data_dir: str = '/tmp/lsm_engine', memtable_limit: int = 1000):
        self.data_dir = Path(data_dir)
        self.data_dir.mkdir(parents=True, exist_ok=True)
        self.wal_path = self.data_dir / 'active.wal'
        self.memtable: Dict[str, str] = {}
        self.memtable_limit = memtable_limit
        self.sstables: List[SSTableSegment] = []  # Newest at the end
        self._wal_file = open(self.wal_path, 'ab', buffering=0)

    def put(self, key: str, value: str) -> None:
        wal_entry = (json.dumps({'k': key, 'v': value}) + '\n').encode('utf-8')
        self._wal_file.write(wal_entry)
        self.memtable[key] = value
        if len(self.memtable) >= self.memtable_limit:
            self._flush_memtable()

    def delete(self, key: str) -> None:
        self.put(key, TOMBSTONE)

    def _flush_memtable(self) -> None:
        sorted_items = sorted(self.memtable.items(), key=lambda item: item[0])
        sst_path = self.data_dir / f'sstable_{len(self.sstables):05d}.sst'
        segment = SSTableSegment.flush_from_memtable(sst_path, sorted_items)
        self.sstables.append(segment)
        self.memtable.clear()
        self._wal_file.close()
        self._wal_file = open(self.wal_path, 'wb', buffering=0)

    def get(self, key: str) -> Optional[str]:
        # 1. Check active in-memory MemTable first
        if key in self.memtable:
            val = self.memtable[key]
            return None if val == TOMBSTONE else val

        # 2. Search immutable SSTables from newest to oldest
        for segment in reversed(self.sstables):
            val = segment.search(key)
            if val is not None:
                return None if val == TOMBSTONE else val
        return None