Storage Engine — cỗ máy lưu trữ
Ba mô-đun tương tác: (1) buffer pool + LRU, (2) WAL + crash recovery, (3) B-tree vs LSM-tree.
1 · Buffer pool & LRU — hit hay miss?
Pool có 3 frame trong RAM. Chạy chuỗi truy cập page; page đã nằm trong pool = hit, chưa có = miss (phải đọc đĩa). LRU đuổi page ít dùng gần đây nhất khi pool đầy.
Chuỗi A: A B C A D B E
Chuỗi B (có locality): A B A C A B C
Buffer pool (RAM) — trái = sẽ bị đuổi trước
Hit: 0
Miss: 0
Hit ratio: —
2 · WAL + crash recovery
Giao dịch T1 chuyển 30 từ A sang B. Quy tắc: ghi log ra đĩa TRƯỚC khi data page kịp flush. Bấm Crash bất cứ lúc nào để mất điện, rồi Recovery để replay log đưa về trạng thái nhất quán.
📒 WAL trên đĩa (tuần tự, bền)
Chưa có log.
💾 Data page trên đĩa
Bấm "Bước tiếp theo" để xem từng giai đoạn của giao dịch.
3 · B-tree (ghi tại chỗ) vs LSM-tree (ghi nối + compaction)
Cùng một loạt ghi SET k=v. Xem cách hai engine xử lý khác nhau.
🌳 B-tree — update tại chỗ
Tìm đúng page chứa khóa rồi ghi đè (random write).
🪵 LSM-tree — ghi nối + compaction
Append vào memtable → flush tuần tự thành SSTable; compaction dồn lại.
| B-tree | LSM-tree | |
|---|---|---|
| Kiểu ghi | Tại chỗ, ngẫu nhiên | Append, tuần tự |
| Write amplification | Trung bình (đè page + WAL) | Cao hơn (compaction), nhưng tuần tự |
| Read amplification | Thấp, ổn định (~log n) | Cao hơn (nhiều tầng + Bloom filter) |
| Range scan | Rất tốt | Phải merge nhiều SSTable |
| Hợp tải | Đọc-nhiều, range query | Ghi-nặng, ingest lớn |
| Ví dụ | PostgreSQL, MySQL | Cassandra, RocksDB |