Database: MVCC và Locking

9. MVCC — Multi-Version Concurrency Control

9.1 Ý tưởng cốt lõi

"Writers không block readers, readers không block writers."

Trước MVCC, database dùng locking thuần: reader phải đợi writer xong, writer phải đợi reader xong — concurrency thấp. MVCC giải quyết bằng cách giữ nhiều versions của cùng một row. Mỗi transaction thấy snapshot nhất quán tại một thời điểm — như chụp ảnh database lúc transaction bắt đầu.

9.2 PostgreSQL MVCC Implementation

PostgreSQL lưu nhiều versions của row ngay trong table, dùng hidden fields để track visibility:

Mỗi row (tuple) có:
  xmin: transaction ID đã INSERT row này
  xmax: transaction ID đã DELETE/UPDATE row này (0 = vẫn live)
  ctid:  physical location (page_number, offset)

Timeline:
  txn_id=100: INSERT → Row: (xmin=100, xmax=0, name='Alice')
  txn_id=200: UPDATE → Old: (xmin=100, xmax=200, name='Alice') ← dead
                       New: (xmin=200, xmax=0,   name='Alicia') ← live
  txn_id=300: DELETE → (xmin=200, xmax=300, name='Alicia') ← dead

Visibility check (transaction T với txn_id=250):
  Row visible nếu: xmin < 250 AND xmin committed
                   AND (xmax = 0 OR xmax >= 250 OR xmax aborted)
  → T thấy 'Alicia' (xmin=200 < 250, xmax=300 >= 250)

9.3 InnoDB MVCC Implementation

InnoDB lưu MVCC khác hơn: không lưu old versions trong table mà lưu trong Undo Log.

Mỗi row có:
  DB_TRX_ID:   ID của transaction cuối cùng update row
  DB_ROLL_PTR: pointer đến undo log record (old version)

Undo Log Chain (traverse để tìm version phù hợp):
  Current: (TRX_ID=300, name='Carol', ROLL_PTR→)
      ↓ undo log
  Version 2: (TRX_ID=200, name='Alicia', ROLL_PTR→)
      ↓ undo log
  Version 1: (TRX_ID=100, name='Alice', ROLL_PTR=NULL)

Read View: được tạo khi transaction bắt đầu (Repeatable Read)
  hoặc mỗi statement (Read Committed)
  → Chứa {active_txn_ids, min_txn_id, max_txn_id}
  → Traverse undo chain đến khi tìm được version phù hợp

9.4 VACUUM — PostgreSQL's MVCC Garbage Collection

Old versions tích lũy theo thời gian làm table phình to (table bloat), index scan chậm hơn.

VACUUM (autovacuum chạy tự động): quét table, tìm dead tuples (xmax committed), mark space là reusable. Không xóa ngay mà để reuse dần.

VACUUM FULL: rewrite toàn bộ table để compact storage. Cần exclusive lock → không dùng trên production thường xuyên.

Lưu ý đặc biệt: PostgreSQL dùng 32-bit transaction ID (~2 tỉ transactions). Nếu không VACUUM lâu ngày → transaction ID wraparound → database từ chối accept transactions mới. Đây là sự cố production nghiêm trọng.

InnoDB ít vấn đề hơn vì undo log được purge tự động bởi background purge thread.

10. Locking — Pessimistic vs Optimistic

10.1 Lock Types

Shared Lock (S): "Tôi đang đọc — người khác có thể đọc, không write"
Exclusive Lock (X): "Tôi đang write — không ai được đọc hoặc write"

Compatibility:
         S      X
  S    [ ✅  |  ❌ ]   S-S compatible, S-X không
  X    [ ❌  |  ❌ ]   X với ai cũng không compatible

Intention Locks (InnoDB): khi muốn lock row, trước tiên phải set intention lock ở table level. Điều này cho phép check conflict nhanh ở table level mà không cần scan từng row.

IS (Intention Shared): muốn set S lock trên row
IX (Intention Exclusive): muốn set X lock trên row

Full compatibility:
         IS     IX     S      X
  IS   [ ✅  |  ✅  |  ✅  |  ❌ ]
  IX   [ ✅  |  ✅  |  ❌  |  ❌ ]
  S    [ ✅  |  ❌  |  ✅  |  ❌ ]
  X    [ ❌  |  ❌  |  ❌  |  ❌ ]

10.2 Row Locks vs Gap Locks vs Next-Key Locks (InnoDB)

InnoDB có nhiều loại lock granularity để cân bằng giữa concurrency và isolation:

Record Lock: lock một index record cụ thể. Dùng khi FOR UPDATE hay LOCK IN SHARE MODE.

Gap Lock: lock khoảng giữa hai records (không include records). Mục đích: ngăn INSERT vào khoảng đó, tránh Phantom Reads ở Repeatable Read.

Next-Key Lock: Record Lock + Gap Lock phía trước. Đây là default của InnoDB.

Index có values: [10, 20, 30]
Next-key locks:  (-∞,10], (10,20], (20,30], (30,+∞)

SELECT * FROM t WHERE id BETWEEN 15 AND 25 FOR UPDATE;
→ Lock: (10,20], (20,30]
→ Không thể INSERT id=18 hay id=22 → không phantom!

10.3 Deadlock

Deadlock xảy ra khi có circular wait: T1 chờ T2 giải phóng lock, T2 chờ T1.

T1: Lock row A → chờ lock row B
T2: Lock row B → chờ lock row A
→ Không ai tiến được!

InnoDB tự detect deadlock bằng wait-for graph. Khi phát hiện cycle → abort transaction có ít undo nhất (rollback ít tốn kém hơn). Application nhận Error 1213: Deadlock found → phải retry.

Cách phòng tránh:

• Luôn acquire locks theo cùng thứ tự trong mọi transaction
• Giữ transaction ngắn
• Tránh user interaction trong transaction

10.4 Optimistic Locking

Thay vì lock ngay khi read (pessimistic), optimistic locking giả định rằng conflicts hiếm xảy ra — không lock gì khi đọc, chỉ detect conflict lúc write.

Implementation phổ biến nhất: thêm cột version:

-- Read
SELECT id, balance, version FROM users WHERE id=1
-- Giả sử trả về: version=5, balance=1000

-- Write (optimistic check)
UPDATE users
SET balance=900, version=6
WHERE id=1 AND version=5
-- Nếu affected_rows = 0 → version đã thay đổi → conflict → retry

Ưu điểm: không có lock overhead trong happy path — tốt cho read-heavy, low-contention workloads.

Nhược điểm: retry logic phức tạp hơn. Nếu contention cao, nhiều retries → throughput giảm.