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.
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.
Thử: crash trước khi flush data page — WAL replay dựng lại thay đổi: ghi log tuần tự rẻ hơn nhiều so với ghi trang ngẫu nhiên.
📒 WAL trên đĩa (tuần tự, bền)
💾 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 |