IAli
Tüm Yazılar
LSM-Tree ve B-Tree: Veritabanı Depolama Motorlarının Analizi

LSM-Tree ve B-Tree: Veritabanı Depolama Motorlarının Analizi

RocksDB ve PostgreSQL disk modelleri: Write amplification, read amplification, memtable, SSTable birleştirme ve indeksleme ödünleşimleri incelemesi.

Veritabanı mimarisinde depolama motoru seçimi, bir uygulamanın kaldırabileceği yazma ve okuma profilini doğrudan belirler. İlişkisel veritabanları onlarca yıldır B-Tree indeksleme modelini temel alırken, dağıtık ve yüksek yazma hacmine sahip sistemler Log-Structured Merge-Tree (LSM-Tree) mimarisini benimsemiştir. Bu iki yaklaşım arasındaki ayrım bir popülerlik tercihi değildir. Donanımın fiziksel kısıtları ile algoritmik ödünleşimlerin zorunlu bir sonucudur.

Bu analizde PostgreSQL ve SQLite tarafındaki B-Tree sayfa yapısı ile RocksDB tarafındaki LSM-Tree mimarisinin disk üzerindeki davranışlarını karşılaştırıyoruz.

1. Disk Fiziği ve İki Farklı Felsefe

Geleneksel sabit disklerde mekanik okuma kafasının plaka üzerinde hareket etmesi rastgele erişimlerde 5 ile 10 milisaniye arasında gecikme yaratır. Katı hal sürücülerinde (SSD) ve NVMe cihazlarında mekanik kafa bulunmasa bile flaş bellek bloklarının fiziksel yapısı rastgele yazmaları cezalandırır. Flaş hücreleri 4 KB veya 8 KB boyutundaki sayfalarda okunup yazılabilir ancak silme işlemi yalnızca 2 MB ile 8 MB arasındaki silme blokları düzeyinde yapılabilir. Aynı bloğa tekrar yazabilmek için önce o bloğun silinmesi gerekir. Bu durum SSD kontrolcüsünün arka planda çöp toplama yapmasına ve donanım düzeyinde yazma çarpanı (write amplification) oluşmasına yol açar.

İki temel depolama felsefesi bu fiziksel kısıtlara farklı yanıtlar üretir:

  • B-Tree Felsefesi (Yerinde Güncelleme): Veri sayfaları sabit boyuttadır. Bir satır güncellendiğinde ya da yeni bir kayıt eklendiğinde ilgili kayıt bellekteki tampon havuzunda doğrudan ait olduğu sayfa içine yazılır ve daha sonra aynı disk konumuna geri yazılır.
  • LSM-Tree Felsefesi (Yalnızca Ekleme): Veriler diske yerinde güncellenmez. Tüm ekleme, güncelleme ve silme işlemleri sıralı bir kütüğün sonuna eklenir. Eski kayıtlar geçersiz kılınır ve daha sonra arka plan birleştirme süreçleriyle temizlenir.

2. B-Tree ve Sayfa Tabanlı Depolama: PostgreSQL Modeli

PostgreSQL ve SQLite gibi ilişkisel veritabanları verilerini diskte sabit boyutlu sayfalarda saklar. PostgreSQL için bu değer derleme anında belirlenen 8 KB boyutudur. SQLite varsayılan olarak 4 KB sayfa boyutu kullanır.

Sayfa Bölünmesi Maliyeti

B-Tree yapısında veriler yaprak sayfalarda sıralı tutulur. Sayfa içine yeni bir kayıt eklenmek istendiğinde ve sayfada boş yer kalmadığında bir sayfa bölünmesi gerçekleşir:

  1. Depolama motoru yeni bir 8 KB sayfa tahsis eder.
  2. Dolu olan sayfadaki anahtarların yaklaşık yarısı yeni sayfaya taşınır.
  3. Üst düzey düğüme yeni sayfayı işaret eden bir anahtar eklenir.
  4. Üst düğüm de doluysa bölünme ağacın köküne doğru kademeli olarak yayılır.

Rastgele anahtar dağılımına sahip yoğun yazma iş yüklerinde sayfa bölünmeleri depolama verimliliğini düşürür. Bölünme sonrasında sayfaların doluluk oranı genellikle yüzde 50 ile yüzde 70 arasında kalır. Bu durum hem disk alanının gereğinden fazla kullanılmasına hem de bellek tamponlarının parçalanmasına yol açar.

WAL ve Yırtık Sayfa Koruması

PostgreSQL, elektrik kesintisi veya sistem çökmesi durumunda veri bütünlüğünü sağlamak için Write-Ahead Logging (WAL) mekanizmasına güvenir. Bir sayfa bellekte değiştirilmeden önce yapılan değişiklik WAL kütüğüne yazılır.

Ancak işletim sistemleri ve disk denetleyicileri veriyi genellikle 512 bayt veya 4 KB sektörler halinde yazar. PostgreSQL 8 KB boyutundaki bir sayfayı işletim sistemi önbelleğinden diske yazarken güç kesilirse sayfanın yalnızca bir kısmı (örneğin ilk 4 KB) diske yazılabilir. Buna yırtık sayfa (torn page) denir. Yırtık bir sayfa yapısal olarak bozulduğu için standart WAL kayıtları ile onarılamaz.

PostgreSQL bu sorunu full_page_writes parametresi ile çözer:

TEXT
PostgreSQL Checkpoint Döngüsü ve WAL Yazma Davranışı:
1. Checkpoint tamamlanır.
2. shared_buffers içindeki bir 8 KB sayfa ilk kez değiştirilir (dirty page).
3. full_page_writes açık olduğunda:
   Yapılan 20 baytlık küçük güncelleme için bile 8 KB sayfanın tamamı WAL içine yazılır.
4. Aynı sayfa bir sonraki checkpoint işlemine kadar tekrar değişirse yalnızca delta farkı yazılır.

Bu mekanizma çökmelere karşı koruma sağlar fakat yoğun rastgele yazma iş yüklerinde checkpoint sonrasında yüksek bir WAL yazma dalgasına yol açar. Birkaç baytlık bir alan güncellemesi için diske 8 KB tam sayfa yazılması B-Tree motorlarının yazma çarpanını yükseltir.

3. LSM-Tree Mimarisi: RocksDB Modeli

LSM-Tree mimarisinin temel amacı rastgele disk yazmalarını sıralı yazmalara dönüştürmektir. RocksDB veri akışını üç ana bileşen üzerinden yönetir:

  1. Write-Ahead Log (WAL): Dayanıklılık sağlamak için her yazma işlemi önce diske sıralı olarak eklenir. Disk denetleyicisi yalnızca dosyanın sonuna yazar.
  2. MemTable: Eşzamanlı olarak veriler RAM üzerinde sıralı bir veri yapısına yazılır. RocksDB varsayılan olarak kilit çekişmesini azaltan ve eşzamanlı okuma-yazma verimi yüksek olan SkipList yapısını kullanır.
  3. SSTable (Sorted String Table): MemTable yapılandırılan boyuta (örneğin 64 MB) ulaştığında değiştirilemez olarak işaretlenir ve arka plan iş parçacığı tarafından diske sıralı bloklar halinde dökülür.
TEXT
LSM-Tree Veri Akışı ve Katman Yapısı:

Yazma İsteği (Put / Delete)
       │
       ├───> [ WAL (Disk, Append-Only) ] ── (Çökme Güvenliği)
       │
       └───> [ MemTable (RAM, SkipList) ]
                   │
                   │ (Bellek dolunca Flush)
                   ▼
       [ Seviye 0 (L0 SSTables) ] ── Anahtar aralıkları birbiriyle çakışabilir
         [SST-1]  [SST-2]  [SST-3]
                   │
                   │ (Leveled Compaction)
                   ▼
       [ Seviye 1 (L1 SSTables) ] ── Ayrık anahtar aralıkları (Çakışma yok)
         [A-D]    [E-H]    [I-L]    [M-P]
                   │
                   │ (10x Boyut Çarpanı)
                   ▼
       [ Seviye 2 (L2 SSTables) ] ── Ayrık anahtar aralıkları
         [A-B] [C-D] [E-F] [G-H] [I-J] [K-L] ...

SSTable Dosya Formatı

Diske dökülen her SSTable dosyası sıralı anahtar-değer çiftlerinden oluşur ve dahili olarak şu bölümlere ayrılır:

  • Veri Blokları (Data Blocks): Genellikle 4 KB boyutunda sıkıştırılmış sıralı kayıtlar.
  • İndeks Bloğu (Index Block): Her veri bloğunun son anahtarını ve dosya içindeki konumunu tutar. İki seviyeli ikili arama yapılmasını sağlar.
  • Filter Blokları (Bloom Filter): İstenen bir anahtarın bu SSTable içinde yer alıp almadığını negatif aramalarda disk okuması yapmadan eleyen olasılıksal veri yapısı.

4. Birleştirme (Compaction) Stratejileri

LSM-Tree mimarisinde disk üzerindeki dosyalar değiştirilemez olduğu için güncellemeler ve silmeler yeni kayıtlar olarak eklenir. Bir anahtar silindiğinde diske silme işareti (tombstone) yazılır. Zamanla aynı anahtarın birden fazla sürümü diskte birikir. Disk alanını geri kazanmak ve okuma performansını korumak için arka planda birleştirme çalışır.

RocksDB iki temel birleştirme stratejisi sunar:

Leveled Compaction Modeli

Leveled Compaction modelinde diskteki veriler katmanlara ayrılır. L0 dışındaki her seviyede dosyaların anahtar aralıkları birbirinden kesin olarak ayrılmıştır:

  • L0 seviyesindeki dosya sayısı level0_file_num_compaction_trigger (varsayılan 4) değerine ulaştığında L0 dosyaları L1 seviyesindeki ilgili anahtar aralığına sahip dosyalarla birleştirilir.
  • Her seviyenin maksimum toplam boyutu bir öncekinin 10 katıdır (örneğin L1 256 MB, L2 2,5 GB, L3 25 GB).
  • Bir seviye boyut sınırını aştığında o seviyeden bir dosya seçilir ve bir alt seviyedeki çakışan dosyalarla birleştirme algoritması mantığıyla birleştirilerek alt seviyeye yazılır.

Leveled Compaction dengeli bir alan çarpanı (yaklaşık 1.1 ile 1.2 arası) sağlar. Verinin diskteki kopyası asgari düzeydedir. Ancak bir baytlık veri en alt seviyeye inene kadar tekrar tekrar okunup yazıldığı için yazma çarpanı (Write Amplification) 10 ile 30 kat arasına çıkabilir.

Size-Tiered (Universal) Compaction

Cassandra tarafından yaygınlaştırılan, RocksDB içinde ise Universal Compaction adıyla bulunan bu modelde benzer boyuttaki SSTable dosyaları birikir:

  • Sistem belirli sayıda benzer boyutlu SSTable oluştuğunda bunları tek bir büyük SSTable olarak birleştirir.
  • Farklı seviyelerdeki anahtar aralıkları çakışabilir.

Veriler her seviyede defalarca alt katmanlara elenmediği için yazma çarpanı düşüktür (genellikle 2 ile 8 kat arası). Ancak birden fazla dosya aynı anahtarı içerebileceği için okuma çarpanı (Read Amplification) yükselir. Ayrıca en büyük birleştirme sırasında eski dosyalar ile yeni dosya aynı anda diskte bulunmak zorundadır. Bu durum disk kullanımının geçici olarak ikiye katlanmasına yol açar.

5. Okuma Yolu ve Bloom Filtrelerinin Rolü

LSM-Tree mimarisinde yazma yolu sıralı kütük sayesinde hızlıyken, okuma yolu birden fazla dosyaya bakmayı gerektirir.

Bir anahtar sorgulandığında depolama motoru şu sırayı izler:

  1. Aktif MemTable kontrol edilir.
  2. Değiştirilemez MemTable yapıları taranır.
  3. L0 seviyesindeki tüm SSTable dosyaları taranır çünkü L0 dosyalarının anahtar aralıkları birbiriyle çakışabilir.
  4. L1, L2 ve alt seviyelerde ikili arama ile ilgili dosya bulunur ve taranır.

Eğer aranan anahtar veritabanında mevcut değilse, sistem en alt seviyeye kadar tüm katmanları diskten okumak zorunda kalabilir. Bu durum okuma çarpanını yükseltir.

TEXT
Bloom Filtresi Kontrol Mekanizması:

Aranan Anahtar: "user_9481"
        │
        ▼
[ Hash Fonksiyonları (h1, h2, h3) ]
        │
        ▼
[ Bit Dizisi: 0 1 0 0 1 1 0 1 0 0 ]
        │
        ├──> Herhangi bir bit 0 ise:
        │    SONUÇ: Anahtar bu dosyada YOK (Sıfır Yanlış Negatif).
        │    Disk G/Ç işlemi tamamen iptal edilir.
        │
        └──> Tüm bitler 1 ise:
             SONUÇ: Anahtar bu dosyada OLABİLİR.
             SSTable veri bloğu diskten okunur.
             (Yanlış Pozitif Oranı: 10 bit/anahtar için ~%1)

RocksDB her SSTable için blok tabanlı Bloom filtreleri oluşturur. Anahtar başına 10 bit ayrıldığında yanlış pozitif oranı yaklaşık yüzde 1 seviyesine iner. Bloom filtresi sayesinde var olmayan anahtarlar için diske gereksiz okuma istekleri gönderilmez.

Buna karşın aralık sorguları LSM-Tree için ek maliyet getirir. B-Tree yapısında yaprak sayfalar çift yönlü bağlı liste ile bağlı olduğu için sıralı bir aralık taraması diskten ardışık blokları okur. LSM-Tree tarafında ise her seviyeden ayrı bir yineleyici açılması ve bu yineleyicilerin bir öncelik kuyruğu üzerinden birleştirilerek tek bir akışa dönüştürülmesi gerekir.

6. RUM Hipotezi ve Motor Ödünleşimleri

Harvard Üniversitesi araştırmacıları tarafından ortaya konan RUM Hipotezi (Read, Update, Memory/Space Conjecture) depolama motorlarının sınırlarını net bir çerçeveye oturtur:

Bir erişim yöntemi tasarlanırken Read Overhead (R), Update Overhead (U) ve Memory/Space Overhead (M) parametrelerinden yalnızca ikisi optimize edilebilir. Üçüncüsü zorunlu olarak feda edilir.

TEXT
RUM Hipotezi Ödünleşim Üçgeni:

                     [ Read (R) ]
                     /                              /                     B-Tree    /                       Alanı    /                                 /                     [ Space (M) ] ──────────────────── [ Update (U) ]
                           LSM-Tree
                            Alanı

Depolama motorlarının bu üçgen üzerindeki konumları şöyledir:

Metrik B-Tree (PostgreSQL / SQLite) LSM-Tree (RocksDB Leveled) LSM-Tree (Size-Tiered)
Yazma Çarpanı (WA) Yüksek (Sayfa bölünmeleri, WAL FPW) Orta-Yüksek (10-30x) Düşük (2-8x)
Okuma Çarpanı (RA) Düşük (Kökten yaprağa doğrudan erişim) Düşük-Orta (Bloom filtreleri ile dengelenir) Yüksek (Birden fazla dosya taranır)
Alan Çarpanı (SA) Orta (Sayfa doluluk oranı %50-70) Düşük (1.1 - 1.2x) Yüksek (Geçici olarak 2.0x)
G/Ç Deseni Rastgele sayfa yazmaları, sıralı WAL Sıralı yazma, arka plan birleştirme Sıralı yazma
Aralık Sorgusu Hızlı ve doğrudan Birleştirme yığını nedeniyle daha yüksek CPU Birleştirme yığını nedeniyle yüksek CPU

7. Mimari Karar Kriterleri

Depolama motorunun seçimi doğrudan uygulamanın veri profiline dayanmalıdır:

  1. B-Tree Tercih Edilmeli:

    • İş yükü baskın olarak okuma ağırlıklıysa (örneğin yüzde 80 okuma, yüzde 20 yazma).
    • Karmaşık aralık sorguları, çoklu ikincil indeksler ve ilişkisel bütünlük kısıtları bulunuyorsa.
    • Öngörülebilir okuma gecikmesi isteniyorsa ve arka plan birleştirme dalgalanmaları tolere edilemiyorsa.
    • Örnek: Finansal işlemler, kurumsal ERP ve e-ticaret sepet sistemleri (PostgreSQL).
  2. LSM-Tree Tercih Edilmeli:

    • İş yükü baskın olarak yazma ağırlıklıysa veya zaman serisi verisi (metrikler, sensör verileri, kütükler) akıyorsa.
    • SSD donanımının ömrü ve yazma dayanıklılığı korunmak isteniyorsa.
    • Veri hacmi çok yüksekse ve sıkıştırma verimliliği ile disk maliyeti öncelikliyse.
    • Örnek: Dağıtık anahtar-değer depoları, metrik toplama motorları, kütük indeksleyiciler (RocksDB, ClickHouse MergeTree motoru).

8. Üretim Ortamı İçin Yapılandırma Notları

İki motor türü de varsayılan ayarlarla ağır yük altında darboğaza girebilir.

RocksDB kullanırken yazma tıkanıklıklarını önlemek için şu parametreler izlenmelidir:

  • write_buffer_size: MemTable boyutudur. 64 MB ile 128 MB arasında başlatılmalıdır.
  • max_write_buffer_number: Bellekte aynı anda tutulabilecek MemTable sayısıdır. En az 4 veya 6 olarak ayarlanmalıdır.
  • level0_file_num_compaction_trigger: L0 birleştirme eşiğidir. Değer çok düşükse birleştirme iş parçacıkları doyar, çok yüksekse okuma gecikmesi artar.
  • block_cache: Sık erişilen veri bloklarını RAM içinde tutmak için sistem belleğinin önemli bir kısmı (örneğin yüzde 30-50) önbelleğe ayrılmalıdır.

PostgreSQL tarafında ise sayfa bölünmelerini ve WAL patlamalarını dizginlemek için şu adımlar değerlendirilmelidir:

  • checkpoint_completion_target: Varsayılan 0.9 olarak bırakılmalı, checkpoint G/Ç yükü zamana yayılmalıdır.
  • max_wal_size: Sık checkpoint oluşmasını önlemek için üretim sunucularında yeterince yüksek (örneğin 16 GB veya 32 GB) tutulmalıdır.
  • fillfactor: Yoğun güncellenen tablolarda sayfa doluluk faktörü yüzde 70 veya 80 seviyesine çekilerek HOT (Heap-Only Tuples) güncellemelerine yer açılmalı ve B-Tree indekslerinin her güncellemede şişmesi engellenmelidir.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...