LSM-tree — yuqori write throughput uchun ma’lumotni avval memory’da tartibli strukturaga yozib, keyin diskdagi immutable sorted fayllarga bosqichma-bosqich birlashtiradigan storage data structure. Uning to‘liq nomi Log-Structured Merge-tree hisoblanadi.
LSM-tree key-value database, wide-column storage va ayrim embedded storage engine’larda ishlatiladi. U random disk write’larni sequential write va background compactionga aylantirishga intiladi.
Write path
Oddiy yozuv jarayoni:
- write-ahead logga yozish;
- memory table’ni yangilash;
- clientga tasdiq;
- memory table to‘lganda diskka flush;
- sorted fayllarni compaction qilish.
Bu foreground write’ni tez va ketma-ket qiladi.
Memtable
Yangi key va value’lar memory’dagi sorted structure’da saqlanadi.
Bu memtable.
Implementation:
- skip list;
- balanced tree;
- boshqa ordered map
bo‘lishi mumkin.
Memtable read querylarida disk fayllari bilan birga tekshiriladi.
Write-ahead log
Memory yo‘qolsa memtable’dagi confirmed write’larni tiklash uchun WAL saqlanadi.
Restartda WAL replay qilinib memtable qayta quriladi.
Memtable diskka xavfsiz flush qilingach tegishli log segmentlari o‘chirilishi mumkin.
Immutable memtable
Faol memtable limitga yetganda immutable holatga o‘tadi.
Yangi write boshqa memtable’ga davom etadi.
Immutable memtable background thread tomonidan diskka sorted fayl sifatida yoziladi.
SSTable
Diskdagi immutable sorted fayl ko‘pincha SSTable deb ataladi.
U:
saqlashi mumkin.
Immutable bo‘lgani sabab update yangi fayl yoki yangi entry sifatida yoziladi.
Read path
Keyni o‘qishda storage quyidagilarni tekshiradi:
- faol memtable;
- immutable memtable;
- yangi disk level va fayllar;
- eski level.
Eng yangi version topilishi kerak.
Ko‘p faylni tekshirish read amplificationga olib keladi.
Bloom filter
SSTable ichida key yo‘qligini tez taxmin qilish uchun Bloom filter ishlatiladi.
Filter “aniq yo‘q” deb ishonchli aytishi mumkin.
“Bor” javobi false positive bo‘lishi mumkin, shunda disk indexi tekshiriladi.
Bloom filter memory evaziga keraksiz disk readni kamaytiradi.
Sparse index
SSTable sorted bo‘lgani sabab har key uchun alohida to‘liq index shart emas.
Block boshlanish keylari bo‘yicha sparse index kerakli data blockni topadi.
Keyin block ichida qidiruv bajariladi.
Compaction
Background jarayon bir nechta SSTable’ni o‘qib, sorted tartibda yangi fayllarga birlashtiradi.
Compaction:
- eski versionlarni olib tashlaydi;
- delete markerlarni tozalaydi;
- file sonini kamaytiradi;
- range overlapni boshqaradi.
Bu CPU, disk va network I/O talab qiladi.
Leveled compaction
SSTable’lar level’larda saqlanadi.
Yuqori level kichik, past level kattaroq.
Bir leveldagi key range’lar kamroq overlap qilishi mumkin.
Afzalligi — read amplification pastroq.
Kamchiligi — bir write compactionda bir necha marta qayta yozilib, write amplification oshishi mumkin.
Size-tiered compaction
O‘xshash hajmdagi bir nechta fayl birlashtiriladi.
Afzalligi — write throughput yuqori va sequential merge.
Kamchiligi:
- ko‘proq overlap;
- ko‘proq read amplification;
- temporary disk hajmi;
- space amplification.
Write-heavy workload uchun qulay bo‘lishi mumkin.
Tombstone
Delete mavjud data’ni barcha eski SSTable’dan darhol olib tashlamaydi.
Yangi tombstone marker yoziladi.
Read tombstone’ni ko‘rsa eski value’ni qaytarmaydi.
Compaction xavfsiz bo‘lganda tombstone va eski versionlar fizik olib tashlanadi.
Tombstone muddati
Distributed replica’da eski data qayta paydo bo‘lmasligi uchun tombstone yetarli vaqt saqlanishi kerak.
Agar bir replica uzoq offline bo‘lib, tombstone allaqachon tozalangan bo‘lsa eski qiymat repair paytida qaytishi mumkin.
Retention va repair intervali bir-biriga mos bo‘ladi.
Read amplification
Bitta keyni topish uchun nechta structure va fayl tekshirilishi read amplification.
Uni kamaytirish vositalari:
Compaction ortda qolsa read amplification oshadi.
Write amplification
Bitta logical write diskda necha marta qayta yozilishini bildiradi.
WAL, flush va bir nechta compaction level sabab write amplification yuz beradi.
Bu SSD endurance va I/O capacity’ga ta’sir qiladi.
Space amplification
Eski version, tombstone va compaction vaqtinchalik outputi sabab storage’da logical data’dan ko‘proq joy ishlatiladi.
Compaction uchun qo‘shimcha bo‘sh disk kerak.
Disk deyarli to‘lsa compaction ishlay olmay, holat yanada yomonlashishi mumkin.
Block cache
Tez-tez o‘qiladigan SSTable blocklari memory cache’da saqlanadi.
Cache hit disk readni kamaytiradi.
Memtable, Bloom filter va block cache bir xil memory budgetni bo‘lishishi mumkin.
Range scan
SSTable sorted bo‘lgani sabab range scan mumkin.
Biroq natija ko‘p file va leveldan merge qilinadi.
Iteratorlar key tartibida birlashtirilib, faqat eng yangi visible version qaytariladi.
Hot key
Bir key juda tez-tez update qilinsa memtable va compactionda ko‘p version yaratadi.
Read eng yangi qiymatni tez topishi mumkin, ammo eski versionlar compactiongacha storage egallaydi.
Counter uchun maxsus merge operator yoki sharding kerak bo‘lishi mumkin.
Compaction backlog
Write tezligi compaction capacity’dan yuqori bo‘lsa fayllar soni va pending byte oshadi.
Natijada:
- read sekinlashadi;
- disk to‘ladi;
- write throttling;
- latency spike
yuz beradi.
Compaction metriclari storage healthining asosiy ko‘rsatkichidir.
LSM-tree va B-tree
| Jihat | LSM-tree | B-tree |
|---|---|---|
| Write | Avval memory va sequential flush | Sorted page’ga yozish |
| Background ish | Compaction | Split, vacuum yoki merge |
| Read | Bir necha level tekshirilishi mumkin | Rootdan leafgacha |
| Range | Sorted merge | Leaflar bo‘ylab scan |
| Write amplification | Compactionga bog‘liq | Page va logga bog‘liq |
Tanlov workload, storage va latency talabiga bog‘liq.
Bog‘liq tushunchalar
Log-Structured Merge-tree, Memtable, SSTable, Compaction, Bloom filter, Tombstone, Write amplification, Read amplification, WAL, B-tree