LSM Ağacı — Yazmayı Ekleyerek Hızlanan Veritabanları
Önce şunu oku: SQL İndeksleme ve EXPLAIN
30 saniyede özet
B-tree her değişikliği diskteki yerinde günceller. LSM ağacı değişiklikleri bellekte toplar, dolunca diske sıralı bir dosya olarak yazar. Yazma ucuzlar; okumanın bedelini Bloom filtresi ve sıkıştırma öder.
Yoğun bir bankoda çalışıyorsun ve her değişiklikte kalın defterin doğru sayfasını bulup eskisini silip yenisini yazıyorsun. Yorucu. Bunun yerine değişiklikleri bir not kâğıdına yazsan, kâğıt dolunca da onu sıralayıp etiketli bir kutuya kaldırsan?
-
Bayt: Kart işlemleri saniyede binlerce satır. Veritabanı yazmaya yetişemiyor!
-
Sen: Okumalar az: genelde son işlemlere bakılıyor. Asıl yük yazma.
-
Bayt: Her yazmada diskte doğru yeri arıyoruz. Ya hiç aramasak?
-
Bayt: Yazmaları biriktirip topluca, sırayla eklemek... Bir not defteri gibi!
Yerinde güncellemek mi, eklemek mi?
B-tree her yazmada diskteki doğru sayfayı bulur ve orada günceller: rastgele bir yazma. Okuma kolaydır, çünkü her anahtarın tek bir yeri vardır.
Bir LSM ağacıYazmaları bellekte toplayıp dolunca diske sıralı, değişmeyen dosyalar olarak ekleyen depolama yapısı. Cassandra ve RocksDB bunu kullanır.Sözlükte gör → yazmaları önce bellekteki bir tabloda, memtable’da toplar. Tablo dolunca onu sıralı ve bir daha değişmeyen bir dosya olarak diske ekler: tek bir sıralı yazma.
Kafam karıştı, daha basit anlat
B-tree her yazmada yerini bulup günceller. LSM yazmaları biriktirir ve topluca, sıralı ekler.
B-tree bir yazmayı nasıl yapar?
LSM ağacında memtable dolunca ne olur?
Okumanın bedeli
LSM'de iki dosya ve bir bellek tablosu var; Bloom filtresi yok. Hiç yazılmamış bir anahtarı arıyorsun. Kaç yere bakılır? Cevabı göster
Hepsine. Bellekte yok, en yeni dosyada yok, en eski dosyada da yok. Olmayan bir anahtar için LSM, her dosyaya bakmak zorundadır.
Adım adım oku
- Her değişiklikte defterin doğru sayfasını bul.
- Bunun yerine not kâğıdına yaz.
- Not dolunca etiketli bir kutuya kaldır.
- Ara ara kutuları tek kutuda birleştir.
Her dosyanın küçük bir Bloom filterBir şeyin kümede olup olmadığını az bellekle cevaplayan bit dizisi. "Kesinlikle yok" ya da "belki var" der; eklenmiş bir şeyi hiç kaçırmaz.Sözlükte gör → vardır: “bu anahtar bu dosyada kesin yok” diyebilir. Okuma, kesin olmayan dosyaları hiç açmaz.
sıkıştırmaLSM'de dosyaları arka planda birleştirip eski sürümleri ve mezar taşlarını atma işi. Ek yazma pahasına okumayı kısaltır.Sözlükte gör → ise arka planda dosyaları birleştirir ve eski sürümleri atar. Ek bir yazma pahasına, okumanın bakacağı dosya sayısını azaltır.
Kafam karıştı, daha basit anlat
Bloom filtresi gereksiz dosyaları atlatır. Sıkıştırma dosyaları birleştirip okumayı kısaltır.
LSM'de Bloom filtresi okumaya nasıl yardım eder?
Sıkıştırma (compaction) neyi takas eder?
Kendin gör
Sekiz yazma, üç okuma
Tohum 63066Oynat ya da adımla: önce sekiz yazma, sonra üç okuma.
Şu an ne oldu?
B-tree
Önce sekiz yazma, sonra k1, k5 ve hiç olmayan k9 okunuyor.
Görevler0/3
Sekiz yazmanın hiçbiri rastgele olmasınaçık
İpucu
Belleğe ekle, dolunca topluca yaz.
LSM ile okumalar en az dört dosyaya baksınaçık
İpucu
Filtre de sıkıştırma da olmasın.
Rastgele yazma olmasın, üç okuma toplam en fazla bir dosyaya baksınaçık
İpucu
İki yardımcı birden.
Olay günlüğü (0)
Henüz olay yok. Oynat veya adımla.
- Varsayılanla oynat. B-tree: sekiz yazmanın hepsi rastgele, okumalar tek sayfa.
- “LSM” seç. Rastgele yazma yok, iki sıralı yazma. Ama okumalar dört dosyaya baktı; olmayan k9 için iki dosyanın ikisine de.
- Bloom filtresini aç. Okunan dosya bire indi; k9 için hiç dosya açılmadı.
- Sıkıştırmayı da aç. Bir sıralı yazma daha, ama dosyalar teke indi.
Bloom filtresi olmayan bir LSM'de hiç yazılmamış bir anahtar aranırsa ne olur?
LSM'de bir anahtar hem bellekte hem eski bir dosyada varsa okuma hangisini döner?
Tuzaklar
Silmeyi ucuz sanmak. LSM’de silmek, bir mezar taşıLSM'de silinen bir anahtar için eklenen işaret. Veri sıkıştırmaya kadar diskte kalır; çok sayıda mezar taşı okumayı yavaşlatır.Sözlükte gör → eklemektir. Çok sık silinen bir tabloda okumalar bu işaretleri de taşır ve yavaşlar.
Sıkıştırmaya yer bırakmamak. Birleştirme sırasında eski ve yeni dosyalar bir süre birlikte durur. Disk tam doluysa sıkıştırma çalışamaz.
Her yüke LSM seçmek. Okuma ağırlıklı, sık güncellenen ve aralık sorgusu yapılan veride B-tree hâlâ iyi bir seçimdir. Seçim, yükün şekline bakılarak yapılır.
Kafam karıştı, daha basit anlat
Silmek de yazmadır, sıkıştırmaya disk bırak, yükün şekline göre seç.
LSM'de bir satırı silmek neden hemen yer kazandırmaz?
Derinleş · Kart işlemleri: Cassandra'da zaman pencereli tablo 4 dosya · ~66 satır · ilk okumada atlayabilirsin
Kendini sına
LSM ağacı her yazmada diskteki doğru sayfayı bulup günceller.
Hangi yük LSM için en uygundur?
Aklında kalacak üç şey
- 1 B-tree her yazmada diskteki doğru sayfayı bulup yerinde günceller. LSM ağacı yazmaları bellekte toplar ve dolunca tek bir sıralı dosya olarak diske ekler.
- 2 LSM'de okuma, anahtarı bulana kadar belleğe ve dosyalara yeniden eskiye bakar. Bloom filtresi anahtarı kesin içermeyen dosyaları atlatır, sıkıştırma da dosya sayısını azaltır.
- 3 LSM'de silmek de bir yazmadır: veri hemen silinmez, bir mezar taşı işareti eklenir ve sıkıştırmaya kadar okumalar onu da taşır.
4 kart sonraki derste seni bekliyor