İçeriğe geç

LSM Ağacı — Yazmayı Ekleyerek Hızlanan Veritabanları

İleri 10 dk Sık karşılaşılır

Ö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?

  1. Bayt: Kart işlemleri saniyede binlerce satır. Veritabanı yazmaya yetişemiyor!

  2. Sen: Okumalar az: genelde son işlemlere bakılıyor. Asıl yük yazma.

  3. Bayt: Her yazmada diskte doğru yeri arıyoruz. Ya hiç aramasak?

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

Hızlı kontrolOrta

B-tree bir yazmayı nasıl yapar?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

LSM ağacında memtable dolunca ne olur?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

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.

Ara ara kutuları tek kutuda birleştir.
Adım adım oku
  1. Her değişiklikte defterin doğru sayfasını bul.
  2. Bunun yerine not kâğıdına yaz.
  3. Not dolunca etiketli bir kutuya kaldır.
  4. 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.

Hızlı kontrolİleri

LSM'de Bloom filtresi okumaya nasıl yardım eder?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

Sıkıştırma (compaction) neyi takas eder?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

Kendin gör

Sekiz yazma, üç okuma

Tohum 63066

Oynat ya da adımla: önce sekiz yazma, sonra üç okuma.

Hız
Adım 0

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

  1. Varsayılanla oynat. B-tree: sekiz yazmanın hepsi rastgele, okumalar tek sayfa.
  2. “LSM” seç. Rastgele yazma yok, iki sıralı yazma. Ama okumalar dört dosyaya baktı; olmayan k9 için iki dosyanın ikisine de.
  3. Bloom filtresini aç. Okunan dosya bire indi; k9 için hiç dosya açılmadı.
  4. Sıkıştırmayı da aç. Bir sıralı yazma daha, ama dosyalar teke indi.
Hızlı kontrolİleri

Bloom filtresi olmayan bir LSM'de hiç yazılmamış bir anahtar aranırsa ne olur?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

LSM'de bir anahtar hem bellekte hem eski bir dosyada varsa okuma hangisini döner?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

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

Hızlı kontrolİleri

LSM'de bir satırı silmek neden hemen yer kazandırmaz?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.
Derinleş · Kart işlemleri: Cassandra'da zaman pencereli tablo 4 dosya · ~66 satır · ilk okumada atlayabilirsin
Proje dosyaları

src/main/resources/cassandra/ V1__card_events.cql Şema: işlemler kart ve güne göre bölünüyor; zaman pencereli sıkıştırma ve Bloom filtresi oranı tabloda ayarlı.

src/main/resources/cassandra/V1__card_events.cql
-- One partition per card per day; rows inside are sorted newest first.
CREATE TABLE IF NOT EXISTS card_events (
card_id text,
day date,
occurred_at timestamp,
event_id uuid,
amount decimal,
merchant text,
PRIMARY KEY ((card_id, day), occurred_at, event_id)
) WITH CLUSTERING ORDER BY (occurred_at DESC, event_id ASC)
AND compaction = {'class': 'TimeWindowCompactionStrategy', 'compaction_window_unit': 'DAYS', 'compaction_window_size': 1}
AND bloom_filter_fp_chance = 0.01
AND default_time_to_live = 31536000;

src/main/java/com/bank/cards/ CardEvent.java Entity: bölüm anahtarı kart ve gün, sıralama anahtarı işlem zamanı.

src/main/java/com/bank/cards/CardEvent.java
@Table("card_events")
record CardEvent(
@PrimaryKeyColumn(name = "card_id", type = PrimaryKeyType.PARTITIONED, ordinal = 0) String cardId,
@PrimaryKeyColumn(name = "day", type = PrimaryKeyType.PARTITIONED, ordinal = 1) LocalDate day,
@PrimaryKeyColumn(name = "occurred_at", type = PrimaryKeyType.CLUSTERED, ordinal = 2, ordering = Ordering.DESCENDING) Instant occurredAt,
@PrimaryKeyColumn(name = "event_id", type = PrimaryKeyType.CLUSTERED, ordinal = 3) UUID eventId,
BigDecimal amount,
String merchant) {
}

src/main/java/com/bank/cards/ CardEventLog.java Yazma yolu: işlemler yalnızca ekleniyor, güncellenmiyor ve silinmiyor; eskileri TTL ile kendiliğinden düşüyor.

src/main/java/com/bank/cards/CardEventLog.java
interface CardEventRepository extends CassandraRepository<CardEvent, MapId> {
List<CardEvent> findByCardIdAndDay(String cardId, LocalDate day);
}
@Service
class CardEventLog {
private static final ZoneId ISTANBUL = ZoneId.of("Europe/Istanbul");
private final CardEventRepository events;
CardEventLog(CardEventRepository events) {
this.events = events;
}
// Append only: a correction is a new event, never an update or a delete (deletes are tombstones).
void record(String cardId, Instant at, BigDecimal amount, String merchant) {
events.insert(new CardEvent(cardId, LocalDate.ofInstant(at, ISTANBUL), at, UUID.randomUUID(), amount, merchant));
}
List<CardEvent> today(String cardId, Clock clock) {
return events.findByCardIdAndDay(cardId, LocalDate.now(clock.withZone(ISTANBUL)));
}
}

src/test/java/com/bank/cards/ CardEventLogIT.java Test: aynı karttaki işlemler en yeniden eskiye geliyor; gerçek bir Cassandra ile.

src/test/java/com/bank/cards/CardEventLogIT.java
@DataCassandraTest
@Testcontainers
class CardEventLogIT {
@Container
@ServiceConnection
static CassandraContainer cassandra = new CassandraContainer("cassandra:5.0");
@Autowired CardEventRepository repository;
@Test
void eventsOfACardComeBackNewestFirst() {
CardEventLog log = new CardEventLog(repository);
Instant morning = Instant.parse("2026-10-03T07:00:00Z");
log.record("C1", morning, new BigDecimal("245.90"), "Migros");
log.record("C1", morning.plusSeconds(3600), new BigDecimal("60.00"), "Kahveci");
Clock clock = Clock.fixed(morning.plusSeconds(7200), ZoneOffset.UTC);
assertThat(log.today("C1", clock)).extracting(CardEvent::merchant).containsExactly("Kahveci", "Migros");
}
}

Kendini sına

Şimşek turu1/4

LSM ağacı her yazmada diskteki doğru sayfayı bulup günceller.

Soru 1/3İleri

Hangi yük LSM için en uygundur?

Cevabı biliyor musun?Önce birini seç. Tekrar zamanlaması buna göre ayarlanıyor.

Aklında kalacak üç şey

  1. 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. 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. 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.
Sonraki kapı Ekstrenin son sayfasında yalnızca üç hareket var. Uygulama yine de hesabın bütün geçmişini veritabanından çekiyor. Neden? Pencere Fonksiyonları — Ekstrede Yürüyen Bakiye Nasıl Hesaplanır? · 8 dk

4 kart sonraki derste seni bekliyor

0/4 kart bu dersten toplandı