Log-Structured Merge-tree (LSM-tree) — write’larni avval xotirada tartiblab, keyin immutable sorted fayllarga ketma-ket yozadigan va background compaction orqali ularni birlashtiradigan storage tuzilmasi. U random disk write’ni sequential write’ga aylantirib yuqori write throughput beradi.
Yozish yo‘li
Client write avval Write-Ahead Logga durability uchun qo‘shiladi, so‘ng mutable memtable’ga kiritiladi. Memtable odatda key bo‘yicha tartiblangan tree yoki skip list. U limitga yetganda immutable holatga o‘tib, diskka sorted run/SSTable sifatida flush qilinadi.
Flush’dan keyin tegishli WAL qismi eski bo‘lishi mumkin, ammo retention replica va recovery ehtiyojiga bog‘liq. Crash’da WAL replay qilib memtable qayta quriladi.
SSTable
Sorted String Table key orderida immutable yozuvlarni saqlaydi. Index block kerakli data blockni topadi, Bloom filter esa faylda kalit albatta yo‘qligini tez aytishi mumkin. Compression block darajasida storage va IOni kamaytiradi.
Immutable file concurrency va crash consistency’ni soddalashtiradi. Update eski recordni joyida o‘zgartirmaydi; yangi value yuqoriroq/yangi run’da yoziladi. Delete tombstone bilan ifodalanadi.
O‘qish yo‘li
Point lookup avval memtable va recent fayllarni, keyin LSM level/runlarni tekshirishi mumkin. Bir keyning bir nechta versiyasi mavjud bo‘lsa eng yangi sequence/timestamp tanlanadi. Ko‘p fayl read amplification yaratadi.
Bloom filter negative lookupda keraksiz disk readni kamaytiradi. Block cache hot data’ni saqlaydi. Range scan sorted fayllardan bir nechta iterator oqimini merge qiladi; overlapping runlar ko‘p bo‘lsa CPU va IO ortadi.
Compaction
Compaction bir nechta sorted faylni o‘qib, yangi tartiblangan faylga birlashtiradi. Eski shadowed qiymat va yetarlicha eski tombstone olib tashlanadi. Leveled compaction level ichida overlapni cheklab read amplificationni kamaytiradi, ammo write amplification yuqori bo‘lishi mumkin.
Size-tiered compaction o‘xshash hajmdagi runlarni birlashtiradi, write throughput yaxshi, lekin read paytida ko‘proq overlapping file tekshirilishi mumkin. Universal va hybrid strategiyalar ham mavjud.
Amplification muvozanati
LSM dizayni write, read va space amplification o‘rtasida trade-off qiladi. Kichik size ratio ko‘proq compaction, kamroq read; katta ratio aksincha. Workload point lookup, range scan, update churn va storage endurance bo‘yicha sozlanadi.
Compaction production IO bilan raqobatlashadi. Backlog ortsa L0 filelar ko‘payib write stall yuz berishi mumkin. Throttling va compaction worker capacity write rate’dan uzoq muddatda yuqori bo‘lishi kerak.
Snapshot va tombstone
MVCC snapshot eski versionlarni saqlashni talab qiladi. Compaction faqat hech bir snapshot/replica uchun kerak bo‘lmagan versionni olib tashlaydi. Tombstone’ni juda erta yo‘qotish eski fayldagi o‘chirilgan qiymatni “tiriltirishi” mumkin.
Distributed LSM storage’da compaction natijasi replica’larda mustaqil bo‘lishi yoki fayl ko‘chirilishi mumkin. Consistency protokoli storage formatdan alohida qatlam.
Qo‘llanish
Cassandra, RocksDB, LevelDB va ko‘plab key-value/database engine’lar LSM oilasidan foydalanadi. Ularning memtable, compaction va consistency xulqi aynan bir xil emas. LSM yuqori write workloadga mos, lekin juda latency-sensitive point read yoki keng range scan uchun cache va tuning muhim.
Monitoring flush rate, compaction backlog, L0 file count, write stall, cache hit, Bloom false positive, read/write amplification va disk space’ni kuzatadi.
Bog‘liq tushunchalar
Memtable, SSTable, Compaction, Bloom filter, Tombstone, Write amplification, Read amplification, Write-Ahead Log