Nền tảng — data sống ở đâu và tại sao disk I/O là bottleneck

Trước khi nói index hay lock, cần hiểu một sự thật nền tảng mà mọi quyết định thiết kế trong database đều xoay quanh:

Bộ nhớ phân tầng

Database không đọc/ghi thẳng xuống disk từng byte. Nó hoạt động qua các tầng cache:

Database đọc data theo đơn vị page (thường 8KB), không phải từng row. Khi mày query 1 row, DB đọc cả page chứa row đó vào buffer pool. Lần query tiếp theo cùng page → cache hit, không cần đụng disk. Đây là lý do hot data nên fit vào RAM — nếu working set lớn hơn RAM, performance sụp đổ.

B-Tree — trái tim của mọi index

Hầu hết index của PostgreSQL và MySQL đều là B-Tree (chính xác là B+Tree). Trước khi nói index là gì, cần hiểu tại sao lại chọn B-Tree.

Tại sao không phải Binary Search Tree?

BST có thể mất cân bằng → O(n) worst case. Nhưng vấn đề lớn hơn: BST node chứa 1 key, mỗi node = 1 disk read. Tìm kiếm trong 1 triệu records → ~20 disk reads → ~200ms. Không chấp nhận được.

B-Tree giải quyết bằng cách

Index là gì và hoạt động thế nào thực sự

Index là một B-Tree riêng biệt, song song với table. Nó không phải magic — chỉ là một cấu trúc dữ liệu phụ được maintain song song với data thật.

Cấu trúc leaf node của index

Leaf node của index không chứa full row. Nó chứa: index key value + pointer (ctid) về vị trí row thực sự trong heap (table file). Pointer này gồm: page number + slot number trong page đó.

Trade-off của index

Các loại index và khi nào dùng

Composite index — Leftmost Prefix Rule

Index trên nhiều cột. Rule quan trọng nhất phải nhớ: leftmost prefix rule. Index (a, b, c) chỉ dùng được khi query có filter bắt đầu từ a.

-- Index: (last_name, first_name, age)
WHERE last_name = 'Nguyen'                         -- ✓ dùng được (prefix: last_name)
WHERE last_name = 'Nguyen' AND first_name = 'An'  -- ✓ dùng được (prefix: last_name, first_name)
WHERE first_name = 'An'                             -- ✗ không dùng được (bỏ qua last_name)
WHERE last_name = 'Nguyen' AND age = 25            -- ✓ last_name dùng, age bị skip
WHERE last_name LIKE 'Ng%' AND first_name = 'An'  -- ✓ cả hai dùng được (prefix match)

Quy tắc chọn thứ tự cột trong composite index: cột nào có equality filter thì đứng trước, cột nào có range filter thì đứng sau.

Partial index — index một subset

Chỉ index rows thỏa mãn một điều kiện. Kết quả: index nhỏ hơn rất nhiều, nhanh hơn, tốn ít bộ nhớ hơn.

-- Chỉ index orders đang pending — thay vì index toàn bộ 100 triệu orders
CREATE INDEX idx_pending_orders ON orders(created_at)
  WHERE status = 'pending';

-- Index này chỉ dùng được cho query có WHERE status='pending'
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2024-01-01'; -- ✓

Covering index — tránh heap lookup

Nếu query chỉ cần các cột đã có trong index, DB không cần đọc heap page — tiết kiệm được 1 disk read mỗi row. Với query trả về hàng nghìn rows đây là sự khác biệt rất lớn.

-- Query này cần: user_id (filter) + email, name (select)
SELECT email, name FROM users WHERE user_id = 123;

-- Index thường: chỉ có user_id → phải fetch heap để lấy email, name
CREATE INDEX idx_user_id ON users(user_id);

-- Covering index: chứa luôn email, name → index-only scan
CREATE INDEX idx_user_covering ON users(user_id) INCLUDE (email, name);

Functional index — index trên expression

-- Nếu mày hay query case-insensitive
CREATE INDEX idx_email_lower ON users(lower(email));

-- Giờ query này mới dùng được index
WHERE lower(email) = 'alice@example.com'   -- ✓
WHERE email = 'Alice@example.com'           -- ✗ không match functional index

Khi nào index không được dùng

Đây là phần quan trọng nhất cho senior. Có index mà query vẫn chậm — đây là những lý do phổ biến nhất:

1. Selectivity quá thấp

Query planner tính toán rằng nếu index chỉ lọc được ít rows (ví dụ gender chỉ có 2 giá trị → 50% rows mỗi value), đọc full table scan còn nhanh hơn vì tránh được overhead của index lookup + random heap fetch.

-- Planner tự động chọn seq scan vì quá nhiều rows match
WHERE gender = 'male'          -- 50% rows → seq scan thường nhanh hơn
WHERE country = 'VN'           -- nếu 80% users ở VN → seq scan
WHERE status = 'active'        -- nếu 95% active → chắc chắn seq scan

2. Function / Transform trên cột

WHERE YEAR(created_at) = 2024           -- ✗ full scan — function phá vỡ index
WHERE created_at >= '2024-01-01'
  AND created_at <  '2025-01-01'        -- ✓ range scan dùng được index

WHERE UPPER(name) = 'ALICE'             -- ✗ full scan
WHERE name = 'Alice'                    -- ✓ nếu data đồng nhất case

3. Implicit type cast

-- user_id column là VARCHAR
WHERE user_id = 123      -- ✗ DB phải cast mọi row: CAST(user_id AS INT)
WHERE user_id = '123'    -- ✓ đúng type

-- phone column là VARCHAR, query dùng integer → full scan
-- Hay xảy ra khi ORM/driver tự động chuyển type

4. LIKE với leading wildcard

WHERE name LIKE '%nguyen'   -- ✗ full scan — không biết bắt đầu từ đâu trên B-Tree
WHERE name LIKE 'nguyen%'   -- ✓ prefix scan — traverse B-Tree từ 'nguyen'

5. OR across different columns

-- Planner thường không thể dùng index hiệu quả cho OR cross-column
WHERE email = 'x@x.com' OR phone = '0123'

-- Rewrite bằng UNION — mỗi nhánh dùng index riêng của mình
SELECT * FROM users WHERE email = 'x@x.com'
UNION
SELECT * FROM users WHERE phone = '0123'

WAL — Write-Ahead Log và Durability

WAL là cơ chế đảm bảo Durability trong ACID. Rule đơn giản: ghi log trước khi ghi data.

Tại sao cần WAL?

Vấn đề: khi update một row, DB sửa page trong buffer pool (RAM). Nếu server crash trước khi page được flush xuống disk → data mất. Giải pháp naive: fsync data file sau mỗi write → cực kỳ chậm vì random I/O.

WAL giải quyết: thay vì ghi thẳng vào data file, ghi một log record mô tả thay đổi vào WAL file trước. WAL là sequential write (append-only) → rất nhanh. Client nhận OK ngay sau khi WAL được fsync. Data file được flush sau bởi background checkpoint.

WAL còn dùng cho gì nữa?

MVCC — tại sao đọc không block ghi

Một trong những điểm mạnh nhất của PostgreSQL/MySQL là SELECT không bị block bởi concurrent UPDATE. Cơ chế đằng sau là Multi-Version Concurrency Control.

Cơ chế

Thay vì lock row khi update, DB giữ nhiều version của cùng một row. Mỗi version có metadata:

• xmin — transaction ID tạo ra version này
• xmax — transaction ID xóa/thay thế version này (null = current)

VACUUM — dọn dead versions

MVCC sinh ra dead row versions — rows với xmax đã set, không còn transaction nào cần nhìn thấy nữa. Nếu không dọn → table bloat → performance degradation dần dần.

VACUUM của PostgreSQL chạy tự động (autovacuum) để reclaim space. Nếu autovacuum không kịp chạy (write load quá cao) → bloat tích tụ. Monitor bằng pg_stat_user_tables.n_dead_tup.

Locking — Row lock, Table lock, Deadlock

Lock modes và compatibility

MVCC đã xử lý reader/writer conflict. Locks chỉ cần thiết cho writer vs writer.

Nhờ MVCC, SELECT thông thường không acquire Shared lock → reader không block writer, writer không block reader. Chỉ SELECT FOR UPDATE/SHARE mới acquire lock.

SELECT FOR UPDATE — pessimistic locking

Kịch bản kinh điển: deduct inventory — hai transaction cùng check stock > 0, cùng thấy stock = 1, cùng deduct → stock âm.

-- WRONG: race condition
BEGIN;
SELECT stock FROM products WHERE id = 1;  -- thấy stock=1
UPDATE products SET stock = stock - 1 WHERE id = 1;
COMMIT;

-- CORRECT: pessimistic lock
BEGIN;
SELECT stock FROM products WHERE id = 1 FOR UPDATE;
-- Transaction thứ 2 sẽ BLOCK ở đây, đợi txn 1 commit/rollback
UPDATE products SET stock = stock - 1 WHERE id = 1 WHERE stock > 0;
COMMIT;

Deadlock — và cách tránh

Deadlock xảy ra khi hai transaction chờ nhau theo vòng tròn. DB tự detect bằng wait-for graph (tìm cycle) và kill một transaction.

-- Txn A          -- Txn B
LOCK row 1        LOCK row 2
LOCK row 2 ← wait  LOCK row 1 ← wait
-- → circular wait → DEADLOCK

-- Solution: luôn acquire locks theo cùng thứ tự
-- Cả Txn A lẫn Txn B đều lock row 1 trước, row 2 sau
-- → không bao giờ có circular wait

Advisory locks — application-level

PostgreSQL cung cấp pg_try_advisory_lock(key) — lock theo một số nguyên tùy ý, không gắn với row nào. Dùng cho distributed locking trong ứng dụng khi muốn dùng DB thay Redis làm lock manager.

SELECT pg_try_advisory_lock(12345);  -- non-blocking, return true/false
SELECT pg_advisory_lock(12345);      -- blocking
SELECT pg_advisory_unlock(12345);   -- release

Isolation Levels và Transaction Anomalies

ACID đảm bảo Isolation — nhưng isolation có nhiều mức độ. Higher isolation = fewer anomalies = more locking = lower concurrency.

Các loại anomaly

Isolation levels

* MySQL InnoDB Repeatable Read dùng gap locks để ngăn phantom reads. PostgreSQL Repeatable Read dùng snapshot isolation nên không có phantom trong practice.

EXPLAIN ANALYZE — đọc query plan thực tế

Đây là kỹ năng thiết yếu nhưng ít được dạy. Mọi performance tuning đều bắt đầu từ đây.

EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT u.name, o.total
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.email = 'alice@example.com'
  AND o.created_at > '2024-01-01';

-- Output mẫu
Hash Join  (cost=8.27..16.54 rows=1 width=36)
           (actual time=0.082..0.086 rows=3 loops=1)
  Buffers: shared hit=6
  ->  Index Scan using idx_users_email on users u
        (cost=0.28..8.30 rows=1 width=16)
        (actual time=0.015..0.016 rows=1 loops=1)
        Index Cond: (email = 'alice@example.com')
        Buffers: shared hit=2
  ->  Index Scan using idx_orders_user_date on orders o
        (cost=0.28..8.14 rows=3 width=24)
        (actual time=0.012..0.018 rows=3 loops=1)
        Filter: (created_at > '2024-01-01')
        Buffers: shared hit=4

Cách đọc output

Dấu hiệu cần điều tra

-- Dấu hiệu BAD trong EXPLAIN ANALYZE
Seq Scan on orders  (rows=5000000)        -- full scan table lớn
Hash Join           (actual rows=1000000)  -- join nhiều rows
cost=0.00..89234.56                         -- cost cao bất thường
rows=1 (actual rows=50000)                 -- estimate sai nghiêm trọng
Buffers: shared read=8000                  -- quá nhiều disk read

Demo tương tác — MVCC và Lock Visualizer

Mô phỏng hai transactions concurrent để thấy MVCC và locking hoạt động như thế nào. Mỗi transaction có một isolation level riêng.

Câu hỏi phỏng vấn hay gặp

System Design level

Câu hỏi nâng cao — staff level