IAli
Tüm Yazılar
LSM-Tree MemTable, SSTable ve Katmanlı Compaction Mimarisi Analizi

LSM-Tree MemTable, SSTable ve Katmanlı Compaction Mimarisi Analizi

LSM-Tree depolama motorlarında MemTable, SSTable, Leveled ve Size-Tiered compaction stratejileri ile yazma amplifikasyonu ve gecikme takası.

Modern dağıtık depolama motorlarında ve yüksek hacimli anahtar-değer sistemlerinde yazma trafiği B+ Tree yapılarının rastgele disk erişim kapasitesini hızla tüketir. Patrick O'Neil ve ekibinin 1996 yılında modellediği Log-Structured Merge-tree (LSM-Tree), rastgele yazmaları sıralı diske yazma operasyonlarına dönüştürerek bu engeli aşar. RocksDB, Apache Cassandra, ScyllaDB ve CockroachDB gibi modern sistemler LSM-Tree temelinde çalışır. Sıralı yazmanın getirdiği devasa verim kazancı, arka planda yürütülen birleştirme (compaction) süreçlerinin yarattığı disk ve işlemci bedeliyle dengelenir.

Kapsam Notu: Bu analiz RocksDB Leveled Compaction ve Apache Cassandra Size-Tiered Compaction mimarileri dikkate alınarak hazırlanmıştır.

LSM-Tree Bileşenleri: MemTable, WAL ve SSTable

LSM-Tree hiyerarşisi bellek içi hızlı yapılar ile diskteki değişmez (immutable) dosya katmanlarından meydana gelir:

TEXT
YAZMA İSTEĞİ
     |
     +---> [ WAL (Write-Ahead Log) ] (Sıralı Disk Yazımı)
     |
     v
[ MemTable (RAM) ] (SkipList / SkipMap)
     | (Boyut sınırına ulaşıldığında dondurulur)
     v
[ Immutable MemTable ]
     | (Flush işlemi)
     v
[ Seviye 0 (L0) SSTable Dosyaları ] (Disk)
     |
     v (Compaction işlemi)
[ Seviye 1 (L1) SSTable Dosyaları ] (Ayrık Anahtar Aralıkları)
     |
     v
[ Seviye 2 (L2) SSTable Dosyaları ]
  1. Write-Ahead Log (WAL): Bellekteki veri elektrik kesintisinde kaybolmasın diye her değişiklik önce sıralı olarak diske eklenir (append-only).
  2. MemTable: Bellek içinde sıralı anahtar tutan yapıdır. Çoğunlukla kilit çekişmesini azaltan SkipList algoritması kullanılır.
  3. SSTable (Sorted String Table): MemTable dolduğunda dondurulur ve diske sıralı bir blok dosyası olarak dökülür (flush). Bir SSTable diske yazıldıktan sonra asla değiştirilmez (immutable). Silme işlemleri bir mezar taşı (tombstone) kaydı eklenerek yürütülür.

Birleştirme (Compaction) Stratejileri

Diske sürekli yeni SSTable dosyalarının yazılması iki sorunu beraberinde getirir: aynı anahtarın eski sürümleri diskte yer kaplar ve okuma yapan istemci doğru değeri bulmak için çok sayıda dosyayı taramak zorunda kalır. Bu karmaşayı temizlemek için arka planda birleştirme (compaction) çalışır.

Size-Tiered Compaction Strategy (STCS)

Apache Cassandra tarafından varsayılan olarak tercih edilen bu yaklaşımda benzer boyuttaki SSTable dosyaları hedeflenir:

  • Benzer büyüklüğe ulaşan belirli sayıda dosya (örneğin 4 adet) birleştirilerek daha büyük tek bir SSTable haline getirilir.
  • Avantajı: Düşük yazma amplifikasyonu (Write Amplification). Veriler diske daha az sayıda yeniden yazılır.
  • Dezavantajı: Yüksek disk alanı dalgalanması. En büyük dosyaların birleştirilmesi sırasında mevcut tablonun boyutu kadar geçici ek disk alanına (%50 boş disk payı) ihtiyaç duyulur. Ayrıca aynı anahtar birden fazla dosyada bulunabileceğinden okuma gecikmesi yüksektir.

Leveled Compaction Strategy (LCS)

RocksDB ve LevelDB mimarisinin kalbinde yer alan bu modelde veriler katmanlara (Level 0, Level 1, Level 2...) ayrılır:

  • Seviye 0 doğrudan MemTable dökümlerini barındırır ve anahtar aralıkları çakışabilir.
  • Seviye 1 ve sonrasındaki her katmanda SSTable dosyaları kesinlikle çakışmayan (non-overlapping) anahtar aralıklarına bölünür.
  • Her katmanın toplam boyutu bir öncekinin 10 katı olacak şekilde ayarlanır (L1: 10 MB, L2: 100 MB, L3: 1 GB).
  • Bir katman kapasitesini aştığında bir dosya seçilir ve alt katmandaki kesişen dosyalarla birleştirilip yeni katmana yazılır.
  • Avantajı: Çok düşük okuma amplifikasyonu. Bir anahtar L1 ve sonrasındaki her katmanda en fazla tek bir SSTable içinde bulunabilir. Disk alanı verimliliği %90 üzerindedir.
  • Dezavantajı: Yüksek Yazma Amplifikasyonu (Write Amplification Factor). Tek bir baytlık kullanıcı verisi katmanlar arasında ilerlerken diske 10 ila 30 kez yeniden yazılabilir. Bu durum SSD sürücülerinin yazma ömrünü (TBW) tüketir.

Okuma Cezası ve Bloom Filtreleri

LSM-Tree mimarisinde bir anahtarı okumak için önce MemTable incelenir. Bulunamazsa sırasıyla L0 ve alt seviyelerdeki SSTable bloklarına bakılır. Olmayan bir anahtarı aramak tüm katmanları tek tek diskten okuma cezasına (Read Amplification) yol açabilir.

Bu maliyeti önlemek için her SSTable başlığına bir Bloom Filtresi (Bloom Filter) yerleştirilir. Bloom filtresi olasılıksal bir veri yapısıdır:

  • Bir anahtarın o dosyada kesinlikle bulunmadığını tek bir bellek içi bit işlemiyle doğrular.
  • Eğer filtre negatif dönerse SSTable dosyası diskten okunmadan atlanır.
  • Filtre pozitif dönerse dosya diskten okunur. Nadiren yalancı pozitif (false positive) oluşsa da gereksiz disk G/Ç operasyonlarının %98'i engellenir.

Üretim Ortamında Parametre Ayarları

RocksDB ve Cassandra sistemlerinde compaction kaynaklı G/Ç darboğazlarını dengelemek için kullanılan temel ayarlar şunlardır:

TEXT
RocksDB Yapılandırma İlkeleri:
write_buffer_size = 64MB (MemTable boyutu)
max_write_buffer_number = 4
target_file_size_base = 64MB (L1 dosya boyutu)
max_bytes_for_level_base = 256MB (L1 toplam tavan)
max_bytes_for_level_multiplier = 10

Yazma trafiği aşırı yükseldiğinde arka plan compaction iş parçacıkları yetişemezse motor yazma duraklatması (write stall) tetikler. İstemci gecikmeleri aniden milisaniyelerden saniyelere fırlar. Bu sebeple compaction iş parçacığı sayısı (max_background_jobs) CPU çekirdek sayısıyla dengelenmelidir.

LSM-Tree ağır yazma iş yüklerinde B+ Tree sistemlerine kıyasla çok daha yüksek yazma bant genişliği sağlar. Ancak bu kazanım işlemci gücü, birleştirme G/Ç yükü ve bellek tabanlı Bloom filtrelerinin dikkatli yönetilmesini gerektirir.

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...