mufassall

Konspekt · Ma'lumot va saqlash

Saqlash dvigatellari: B-tree va LSM

15 daq · Yuqori · mufassall.dtwin.uz/uz/l/storage-engines/

← Darsni ochish

Muammo

Sensorlar soniyasiga 50 000 ko'rsatkich yuboradi va B-tree jadval ulgurmaydi. Bir yozuvning LSM-tree dvigatel ichidagi yo'lini kuzatamiz: WAL, memtable, SSTable va compaction — va bu o'qishga qancha tushishini ko'ramiz.

Nimani o'rganasiz

  • Nega B-tree butun sahifani qayta yozadi va kichik yozuvlarni diskdagi tasodifiy IO'ga aylantiradi
  • LSM-tree yozuvni qanday qo'shib yozishga aylantiradi: WAL, memtable, SSTable'ga flush
  • O'qish kuchayishi (read amplification), Bloom filtr va nega compaction yozishni to'xtatib qo'yishi mumkin
  • Qachon B-tree yutadi, qachon LSM-tree
Yakuniy sahna
30%60%25%40%45%20%75%

Diagramma kod sifatida

Darsdagi yakuniy sxemani matn ko'rinishida oling va Jira, GitLab, GitHub, Notion yoki hujjatga qo'ying: Mermaid u yerlarda o'zi chiziladi. D2 va PlantUML (Confluence, IntelliJ) uchun alohida variantlar bor.

Mermaid: sxema

flowchart LR
  n_sensors(["Sensorlar"])
  n_ingest["Qabul servisi"]
  n_wal[["WAL"]]
  n_memtable{{"Memtable"}}
  n_l0[("SSTable L0")]
  n_dash["Dashboard API"]
  n_compact("Compaction")
  n_l1[("SSTable L1")]
  n_sensors --> n_ingest
  n_ingest --> n_wal
  n_ingest --> n_memtable
  n_memtable --> n_l0
  n_dash --> n_memtable
  n_dash --> n_l0
  n_l0 --> n_compact
  n_compact --> n_l1
  n_dash --> n_l1

Mermaid: so'rovlar ketma-ketligi

sequenceDiagram
  participant n_ingest as Qabul servisi
  participant n_table as B-tree jadval
  participant n_wal as WAL
  participant n_memtable as Memtable
  participant n_l0 as SSTable L0
  participant n_dash as Dashboard API
  participant n_compact as Compaction
  participant n_l1 as SSTable L1
  Note over n_ingest,n_table: Yozuv B-tree sahifasiga tushadi
  n_ingest->>n_table: INSERT INTO readings (sensor_id, ts, value)
  n_table-->>n_ingest: INSERT 0 1
  Note over n_ingest,n_table: Soniyasiga 50 000 yozuvda disk taslim bo'ladi
  n_ingest->>n_table: LOG: checkpoint complete
  Note over n_ingest,n_wal: LSM-tree: logga qo'shib yoz, xotirada sarala
  n_ingest->>n_wal: APPEND 000412.log offset=88123904 len=64
  n_wal-->>n_ingest: fsync: 0.4 ms
  Note over n_memtable,n_l0: To'lgan memtable SSTable'ga aylanadi
  n_memtable->>n_l0: flush memtable #35;57
  Note over n_dash,n_l0: Bitta o'qish 31 joyni tekshiradi
  n_dash->>n_l0: GET s_1093/latest
  n_l0-->>n_dash: memtable: miss
  Note over n_dash,n_l0: Bloom filtr noto'g'ri fayllarni o'tkazib yuboradi
  n_dash->>n_l0: GET s_1093/latest
  n_l0-->>n_dash: memtable: miss
  Note over n_compact,n_l1: Compaction fayllarni 1-darajaga birlashtiradi
  n_compact->>n_l1: compact L0 -#62; L1
  Note over n_ingest,n_memtable: Compaction ortda qoladi va yozish to'xtaydi
  n_ingest->>n_memtable: WARN write stall
  Note over n_l0,n_compact: Compaction'ga joy ber, kirishni chegarala
  n_l0->>n_compact: compaction threads: 6 (was 2)
  Note over n_dash,n_l1: Oraliqni o'qish: bu yerda B-tree yutadi
  n_dash->>n_l1: SCAN s_1093 from 09:00 to 10:00
  n_l1-->>n_dash: merge iterators: memtable, 3 x L0, L1

D2

direction: right

n_sensors: "Sensorlar" {
  shape: rectangle
}
n_ingest: "Qabul servisi" {
  shape: rectangle
}
n_wal: "WAL" {
  shape: queue
}
n_memtable: "Memtable" {
  shape: hexagon
}
n_l0: "SSTable L0" {
  shape: stored_data
}
n_dash: "Dashboard API" {
  shape: rectangle
}
n_compact: "Compaction" {
  shape: rectangle
  style.multiple: true
}
n_l1: "SSTable L1" {
  shape: stored_data
}

n_sensors -> n_ingest
n_ingest -> n_wal
n_ingest -> n_memtable
n_memtable -> n_l0
n_dash -> n_memtable
n_dash -> n_l0
n_l0 -> n_compact
n_compact -> n_l1
n_dash -> n_l1

PlantUML: so'rovlar ketma-ketligi

@startuml
participant "Qabul servisi" as n_ingest
database "B-tree jadval" as n_table
queue "WAL" as n_wal
collections "Memtable" as n_memtable
database "SSTable L0" as n_l0
participant "Dashboard API" as n_dash
participant "Compaction" as n_compact
database "SSTable L1" as n_l1
note over n_ingest, n_table : Yozuv B-tree sahifasiga tushadi
n_ingest -> n_table : INSERT INTO readings (sensor_id, ts, value)
n_table --> n_ingest : INSERT 0 1
note over n_ingest, n_table : Soniyasiga 50 000 yozuvda disk taslim bo'ladi
n_ingest -> n_table : LOG: checkpoint complete
note over n_ingest, n_wal : LSM-tree: logga qo'shib yoz, xotirada sarala
n_ingest -> n_wal : APPEND 000412.log offset=88123904 len=64
n_wal --> n_ingest : fsync: 0.4 ms
note over n_memtable, n_l0 : To'lgan memtable SSTable'ga aylanadi
n_memtable -> n_l0 : flush memtable #57
note over n_dash, n_l0 : Bitta o'qish 31 joyni tekshiradi
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_dash, n_l0 : Bloom filtr noto'g'ri fayllarni o'tkazib yuboradi
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_compact, n_l1 : Compaction fayllarni 1-darajaga birlashtiradi
n_compact -> n_l1 : compact L0 -> L1
note over n_ingest, n_memtable : Compaction ortda qoladi va yozish to'xtaydi
n_ingest -> n_memtable : WARN write stall
note over n_l0, n_compact : Compaction'ga joy ber, kirishni chegarala
n_l0 -> n_compact : compaction threads: 6 (was 2)
note over n_dash, n_l1 : Oraliqni o'qish: bu yerda B-tree yutadi
n_dash -> n_l1 : SCAN s_1093 from 09:00 to 10:00
n_l1 --> n_dash : merge iterators: memtable, 3 x L0, L1
@enduml

PlantUML: komponentlar

@startuml
left to right direction
agent "Sensorlar" as n_sensors
component "Qabul servisi" as n_ingest
queue "WAL" as n_wal
stack "Memtable" as n_memtable
storage "SSTable L0" as n_l0
component "Dashboard API" as n_dash
collections "Compaction" as n_compact
storage "SSTable L1" as n_l1
n_sensors --> n_ingest
n_ingest --> n_wal
n_ingest --> n_memtable
n_memtable --> n_l0
n_dash --> n_memtable
n_dash --> n_l0
n_l0 --> n_compact
n_compact --> n_l1
n_dash --> n_l1
@enduml

Xulosa

B-tree ma'lumotni joyida yangilaydi: tez va oldindan aytsa bo'ladigan o'qish va oraliq so'rovlar, lekin har kichik yozuv tasodifiy joydagi sahifani qayta yozadi. LSM-tree qo'shib yozadi va keyin saralaydi: juda tez yozish, evaziga o'qish kuchayishi va compaction.

O'qish ko'p, tranzaksion va oraliq so'rovlari ko'p ma'lumot uchun B-tree tanlang. Yozish ko'p oqimlar uchun — hodisalar, metrikalar, loglar — LSM-tree. LSM'da uchta sonni kuzating: L0 fayllar soni, kutilayotgan compaction va write stall'lar.

Ko'rsatkichlar: boshida va oxirida

Ko'rsatkichBoshidaOxirida
Qabul qilingan yozuvlar8 000/s50 000/s
Yozish kuchayishi10 x12 x
Bir o'qishda tekshirilgan joylar15
O'qish p993 ms45 ms

Qadamlar

  1. Holat Yozuv B-tree sahifasiga tushadi

    Har sensor bir necha soniyada ko'rsatkich yuboradi.

  2. Muammo Soniyasiga 50 000 yozuvda disk taslim bo'ladi

    Sensorlar soniyasiga 50 000 yozuvgacha ko'paydi.

  3. Yechim LSM-tree: logga qo'shib yoz, xotirada sarala

    LSM-tree dvigateliga o'tamiz.

  4. Holat To'lgan memtable SSTable'ga aylanadi

    Memtable 64 MB ga yetganda u muzlatiladi, yozuvlarni yangi bo'sh memtable oladi, muzlatilgani esa diskka SSTable sifatida yoziladi: boshqa hech qachon o'zgarmaydigan saralangan fayl.

  5. Muammo Bitta o'qish 31 joyni tekshiradi

    Dashboard s_1093 sensorining oxirgi ko'rsatkichini so'raydi.

  6. Yechim Bloom filtr noto'g'ri fayllarni o'tkazib yuboradi

    Har SSTable'ga Bloom filtr beriladi: har kalitga bir necha bit, xotirada saqlanadi.

  7. Yechim Compaction fayllarni 1-darajaga birlashtiradi

    L0 o'sishda davom etadi: har bir necha soniyada yangi fayl.

  8. Muammo Compaction ortda qoladi va yozish to'xtaydi

    Bo'ron bo'ladi, hamma sensor bir vaqtda xabar beradi, yozuvlar soniyasiga 80 000 ga sakraydi.

  9. Yechim Compaction'ga joy ber, kirishni chegarala

    Compaction ikkita emas, oltita oqim oladi.

  10. Holat Oraliqni o'qish: bu yerda B-tree yutadi

    Dashboard bitta sensorning oxirgi bir soatini so'raydi.

  11. Xulosa Xulosa

    B-tree ma'lumotni joyida yangilaydi: tez va oldindan aytsa bo'ladigan o'qish va oraliq so'rovlar, lekin har kichik yozuv tasodifiy joydagi sahifani qayta yozadi.

Atamalar

B-tree
Ma'lumotni saralangan sahifalarda saqlab, joyida yangilaydigan tuzilma. O'qish va oraliq so'rovlar tez, lekin har kichik yozuv tasodifiy joydagi butun sahifani qayta yozadi.
LSM-tree
Yozuvni WAL'ga qo'shib yozib, xotiradagi memtable'da saralaydigan va keyin diskka SSTable fayl qilib tushiradigan ombor. Yozish juda tez, evaziga o'qish kuchayishi va compaction keladi.
WAL (write-ahead log)
Har o'zgarish avval faqat oxiriga qo'shib yoziladigan log faylga tushadi, keyin asosiy tuzilmaga. Server yiqilsa, ma'lumot shu logdan tiklanadi.