Log Structured Merge Tree: Veritabanlarında Yazma İşlemleri Nasıl Hızlanır?

Veritabanlarında ölçeklenme deyince çoğu kişinin aklına önce daha güçlü makineler ya da daha fazla sunucu gelir. Ama bazen asıl mesele, verinin diske nasıl yazıldığıdır. Bu yazıda B+ Tree yaklaşımından başlayıp Log Structured Merge Tree yani LSM Tree yapısına kadar giden fikri adım adım kuracağız.

Klasik Veritabanı Yazma Modeli

Bir uygulamada istemci sunucuya veri gönderir, sunucu da kalıcı durumu korumak için bunu veritabanına yazar. Geleneksel ilişkisel veritabanlarında indeksleme için sıkça B+ Tree kullanılır. B+ Tree, yani şöyle düşün: Veriyi sıralı tutmaya çalışan, arama ve ekleme işlemlerini dengeli biçimde yapan ağaç tabanlı bir yapıdır.

sequenceDiagram
    participant C as "İstemci"
    participant S as "Sunucu"
    participant D as "Veritabanı"
    participant T as "B+ Tree İndeksi"

    C->>S: "Yeni kayıt gönderir"
    S->>D: "INSERT isteği"
    D->>T: "Ağaç yapısında ekleme yapar"
    T-->>D: "İndeks güncellendi"
    D-->>S: "Yazma onayı"
    S-->>C: "İşlem tamamlandı"

Bu diyagram klasik yazma yolunu gösterir. Her kayıt için veritabanına ayrı istek gider, indeks güncellenir ve sunucu onay bekler.

B+ Tree hem aramada hem eklemede genellikle O(log n) davranış verir. Bu iyi bir denge gibi görünür. Ama yazma sayısı çok arttığında her işlem için ayrı disk erişimi, ayrı ağ trafiği ve ayrı onay beklemek ciddi maliyet yaratır.

İlk Fikir: Yazmaları Toplu Göndermek

Şimdi şöyle bir düşün: Sunucu gelen her küçük yazmayı anında veritabanına göndermek yerine bir süre bellekte biriktirse ve sonra hepsini tek seferde yazsa ne olur? Ağ üzerindeki gereksiz başlıklar azalır, veritabanı daha az I/O çağrısı alır ve her kayıt için ayrı ayrı onay beklemek yerine toplu onay alınır.

flowchart TD
    A["İstemcilerden gelen yazmalar"] --> B["Sunucu belleğinde geçici tampon"]
    B --> C{"Tampon eşiğe ulaştı mı?"}
    C -- "Hayır" --> B
    C -- "Evet" --> D["Kayıtları tek blok halinde gönder"]
    D --> E["Veritabanına toplu yaz"]
    E --> F["Tek onay döndür"]

Bu yapı, küçük yazma isteklerini daha büyük bir yazma bloğuna dönüştürür. Kazanç daha az ağ konuşması ve daha az disk çağrısıdır; maliyet ise sunucuda ekstra bellek kullanımıdır.

Bu noktada bellek kullanımı yönetilebilir bir bedeldir. Çünkü tampon boyutu sınırlanabilir. Asıl kritik soru şudur: Yazmaları hızlandırırken okumaları yavaşlatmadan bunu nasıl yaparız?

Log Mantığı: Yazmak İçin En Hızlı Yol

Log, yani şöyle düşün: Yeni veriyi mevcut yapının ortasına yerleştirmek yerine sadece sona eklersin. Bu yüzden yazma işlemi çok hızlıdır. Bir linked list gibi, son noktaya gidip yeni parçayı eklersin.

flowchart LR
    A["Kayıt 1"] --> B["Kayıt 2"]
    B --> C["Kayıt 3"]
    C --> D["Yeni kayıt"]
    D --> E["Sonraki yeni kayıt"]

Log yapısında yazmalar hızlıdır çünkü veri sırayla eklenir. Ama sadece log üzerinde arama yaparsan kayıt bulmak için baştan sona tarama gerekebilir; bu da okuma tarafında pahalıdır.

Buradaki gerilim veritabanı tasarımının kalbidir: Yazma için log harikadır, okuma için tek başına yeterli değildir. LSM Tree tam olarak bu ikisini uzlaştırmaya çalışır.

LSM Tree’nin Ana Fikri

Log Structured Merge Tree, yani şöyle düşün: Yeni veriler önce hızlı yazılabilen bir bellek yapısına alınır, sonra sıralı dosyalar halinde diske dökülür ve arka planda bu dosyalar birleştirilir. Böylece yazmalar sıralı ve hızlı kalırken okumalar da sıralı yapılar üzerinden yapılabilir.

flowchart TD
    subgraph Bellek["Bellek Katmanı"]
        A["Yeni yazmalar"] --> B["Memtable / yazma tamponu"]
    end

    subgraph Disk["Disk Katmanı"]
        C["SSTable 1<br/>Sıralı kayıtlar"]
        D["SSTable 2<br/>Sıralı kayıtlar"]
        E["Daha büyük SSTable"]
    end

    B --> F{"Eşik doldu mu?"}
    F -- "Evet" --> C
    F -- "Hayır" --> B
    C --> G["Arka plan compaction"]
    D --> G
    G --> E

Bu diyagram LSM Tree’nin temel akışını gösterir. Veri önce bellekte toplanır, sonra sıralı dosyalar halinde diske yazılır ve zamanla daha büyük sıralı parçalara birleştirilir.

SSTable, yani Sorted String Table, şöyle hayal edebilirsin: Diskte duran, içindeki kayıtları anahtara göre sıralı saklayan değişmez bir dosya. Değişmez olması önemlidir; çünkü yeni yazmalar eski dosyanın içine sokulmaz, yeni bir sıralı dosya olarak eklenir.

Neden Her Şeyi Tek Büyük Dosyada Sıralamıyoruz?

İlk bakışta en temiz çözüm tüm veriyi tek büyük sıralı dosyada tutmak gibi görünebilir. Ama her küçük yazma geldiğinde devasa dosyayı yeniden sıralamak çok pahalıdır. Bunun yerine LSM Tree küçük sıralı parçalar üretir ve bu parçaları kontrollü şekilde birleştirir.

flowchart TD
    A["6 kayıtlık SSTable"] --> C["12 kayıtlık SSTable"]
    B["6 kayıtlık SSTable"] --> C
    D["6 kayıtlık SSTable"] --> F["12 kayıtlık SSTable"]
    E["6 kayıtlık SSTable"] --> F
    C --> G["24 kayıtlık SSTable"]
    F --> G

Bu yapı merge sort mantığına benzer. Aynı boyuttaki iki sıralı parça birleşerek daha büyük sıralı bir parça üretir; böylece okuma sırasında bakılması gereken dosya sayısı azalır.

Compaction, yani şöyle düşün: Küçük sıralı dosyaları arka planda birleştirip daha büyük ve daha düzenli dosyalar haline getirme işidir. Bu işlem yazma yolunu durdurmadan, sistemin daha okunabilir bir disk düzenine kavuşmasını sağlar.

Okuma Tarafında Ne Olur?

LSM Tree yazmaları hızlandırırken okumaları tamamen bedavaya getirmez. Bir kayıt aranırken önce bellekteki güncel yazmalara bakılır, sonra diskteki SSTable dosyaları kontrol edilir. Eğer çok fazla SSTable varsa her birine bakmak maliyetli olabilir.

flowchart TD
    A["Okuma isteği"] --> B["Memtable kontrol edilir"]
    B --> C{"Kayıt bulundu mu?"}
    C -- "Evet" --> Z["Sonuç döndürülür"]
    C -- "Hayır" --> D["En yeni SSTable kontrol edilir"]
    D --> E{"Bulundu mu?"}
    E -- "Evet" --> Z
    E -- "Hayır" --> F["Daha eski SSTable kontrol edilir"]
    F --> G{"Bulundu mu?"}
    G -- "Evet" --> Z
    G -- "Hayır" --> H["Kayıt yok cevabı"]

Bu diyagram LSM Tree’de okumanın katmanlı yapısını gösterir. Sistem önce en güncel verinin olabileceği yere bakar, sonra daha eski sıralı dosyalara doğru ilerler.

Sıralı dosyalar sayesinde her SSTable içinde binary search yapılabilir. Binary search, yani şöyle düşün: Sıralı bir telefon rehberinde sayfaları tek tek çevirmek yerine her seferinde aralığı ikiye bölerek aramak gibi çalışır.

Bloom Filter ile Gereksiz Okumaları Azaltmak

Çok sayıda SSTable olduğunda en büyük sorun, aranan kaydın hangi dosyada olmadığını hızlıca anlayabilmektir. Burada Bloom filter devreye girer. Bloom filter, yani şöyle düşün: Bir kayıt kesinlikle yoksa bunu hızlıca söyleyen, ama bazen “olabilir” diyerek seni dosyaya bakmaya yönlendiren küçük bir kontrol yapısıdır.

flowchart TD
    A["Okuma isteği: belirli anahtar"] --> B["SSTable Bloom filter kontrolü"]
    B --> C{"Bloom filter ne diyor?"}
    C -- "Kesinlikle yok" --> D["Bu SSTable atlanır"]
    C -- "Olabilir" --> E["SSTable içinde binary search yapılır"]
    E --> F{"Kayıt bulundu mu?"}
    F -- "Evet" --> G["Sonuç döndürülür"]
    F -- "Hayır" --> H["False positive oluştu"]

Bloom filter gereksiz disk okumalarını azaltır. False positive olabilir, yani kayıt yokken var olabilir diyebilir; ama false negative üretmez, yani kayıt gerçekten varsa “kesin yok” demez.

SSTable büyüdükçe Bloom filter’ın da daha dikkatli tasarlanması gerekir. Daha fazla veri, yanlış olumlu ihtimalini artırır; bu yüzden bit sayısı ve hash fonksiyonları gibi ayarlar okuma performansı için önemlidir.

LSM Tree Ne Kazandırır?

LSM Tree’nin gücü, yazma işlemlerini rastgele disk güncellemeleri yerine sıralı yazmalara çevirmesidir. Diskler ve SSD’ler için sıralı yazma genellikle daha verimlidir. Üstelik küçük yazmalar bellekte toplanıp toplu şekilde diske aktarıldığı için sistem yüksek yazma trafiğini daha rahat taşır.

Bunun bedeli ise arka planda sürekli çalışan compaction süreci ve okuma yolundaki ek karmaşıklıktır. Sen de fark etmişsindir ki burada amaç tek bir veri yapısıyla her şeyi çözmek değil; bellek, log, sıralı dosya, compaction ve Bloom filter gibi parçaları birlikte kullanarak dengeli bir sistem kurmaktır.

flowchart LR
    A["Hızlı yazma ihtiyacı"] --> B["Log tabanlı ekleme"]
    B --> C["Bellekte toplama"]
    C --> D["Sıralı SSTable olarak diske yazma"]
    D --> E["Arka planda compaction"]
    E --> F["Daha az dosyada daha hızlı okuma"]
    F --> G["Bloom filter ile gereksiz aramaları azaltma"]

Bu son diyagram LSM Tree’nin genel stratejisini özetler. Yazma yolu hızlı tutulur, okuma yolu ise sıralama, birleştirme ve filtreleme teknikleriyle yönetilebilir hale getirilir.

Özet

LSM Tree, yazma ağırlıklı sistemlerde veriyi doğrudan karmaşık bir indeksin içine yerleştirmek yerine önce hızlıca log benzeri bir yapıya alır. Sonra bu veriyi sıralı SSTable dosyalarına dönüştürür ve arka planda compaction ile daha büyük, daha düzenli parçalar üretir. Böylece yazmalar hızlı kalırken okumalar da tamamen kontrolsüz bir log taramasına dönüşmez. Bloom filter gibi yardımcı yapılar ise hangi dosyalara bakmaya değmeyeceğini önceden söyleyerek okuma maliyetini düşürür.

Bu yazı How databases scale writes: The power of the log videosundan ilham alınarak yazılmıştır.

Kaynakça

• https://www.youtube.com/watch?v=_5vrfuwhvlQ&list=PLMCXHnjXnTnvo6alSjVkgxV-VH6EPyvoX&index=21