Konspekt · Ma'lumot va saqlash
Saqlash dvigatellari: B-tree va LSM
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
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_l1Mermaid: 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, L1D2
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_l1PlantUML: 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
@endumlPlantUML: 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
@endumlXulosa
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'rsatkich | Boshida | Oxirida |
|---|---|---|
| Qabul qilingan yozuvlar | 8 000/s | 50 000/s |
| Yozish kuchayishi | 10 x | 12 x |
| Bir o'qishda tekshirilgan joylar | 1 | 5 |
| O'qish p99 | 3 ms | 45 ms |
Qadamlar
- Holat Yozuv B-tree sahifasiga tushadi
Har sensor bir necha soniyada ko'rsatkich yuboradi.
- Muammo Soniyasiga 50 000 yozuvda disk taslim bo'ladi
Sensorlar soniyasiga 50 000 yozuvgacha ko'paydi.
- Yechim LSM-tree: logga qo'shib yoz, xotirada sarala
LSM-tree dvigateliga o'tamiz.
- 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.
- Muammo Bitta o'qish 31 joyni tekshiradi
Dashboard
s_1093sensorining oxirgi ko'rsatkichini so'raydi. - Yechim Bloom filtr noto'g'ri fayllarni o'tkazib yuboradi
Har SSTable'ga Bloom filtr beriladi: har kalitga bir necha bit, xotirada saqlanadi.
- Yechim Compaction fayllarni 1-darajaga birlashtiradi
L0 o'sishda davom etadi: har bir necha soniyada yangi fayl.
- Muammo Compaction ortda qoladi va yozish to'xtaydi
Bo'ron bo'ladi, hamma sensor bir vaqtda xabar beradi, yozuvlar soniyasiga 80 000 ga sakraydi.
- Yechim Compaction'ga joy ber, kirishni chegarala
Compaction ikkita emas, oltita oqim oladi.
- Holat Oraliqni o'qish: bu yerda B-tree yutadi
Dashboard bitta sensorning oxirgi bir soatini so'raydi.
- 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.