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.

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)

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-treeLSM-tree
Kiểu ghiTại chỗ, ngẫu nhiênAppend, tuần tự
Write amplificationTrung bình (đè page + WAL)Cao hơn (compaction), nhưng tuần tự
Read amplificationThấp, ổn định (~log n)Cao hơn (nhiều tầng + Bloom filter)
Range scanRất tốtPhải merge nhiều SSTable
Hợp tảiĐọc-nhiều, range queryGhi-nặng, ingest lớn
Ví dụPostgreSQL, MySQLCassandra, RocksDB