Tuan-Bonus-Consistency-Models-Isolation

Tuần Bonus: Consistency Models & Isolation Levels

“Một kỹ sư bình thường nói ‘database của tôi consistent’. Một kỹ sư senior hỏi ‘consistent ở mức nào?‘. Một architect chỉ vào dòng READ COMMITTED trong config và nói: ‘đây là chỗ Stripe đã từng mất 3.6 triệu đô vì write skew vào năm 2019’.”

Tags: system-design consistency isolation mvcc linearizability serializability jepsen bonus Student: Hieu (Backend Dev → Architect) Prerequisite: Tuan-07-Database-Sharding-Replication · Tuan-Bonus-Consensus-Raft-Paxos Liên quan: Case-Design-Payment-System · Case-Design-Hotel-Reservation-System · Case-Design-Stock-Exchange · Case-Design-Digital-Wallet

---

1. Context & Why

Analogy đời thường — Tài khoản ngân hàng dùng chung

Hieu, tưởng tượng em và vợ cùng dùng một tài khoản ngân hàng có 1,000,000 VND. Cả hai cùng lúc rút 800,000 VND từ 2 ATM khác nhau:

Scenario nguy hiểm:

T=0ms:   Em đọc balance = 1,000,000 VND  → ATM A
T=1ms:   Vợ đọc balance = 1,000,000 VND  → ATM B
T=2ms:   Em rút 800,000 → ATM A trừ: 1,000,000 - 800,000 = 200,000
T=3ms:   Vợ rút 800,000 → ATM B trừ: 1,000,000 - 800,000 = 200,000
T=4ms:   Cuối cùng balance = 200,000 (mất 600,000 VND của ngân hàng!)

Bug này gọi là Lost Update. Đây là một trong 5 anomaly mà mọi kỹ sư backend phải biết. Database isolation levels được phát minh chính xác để giải quyết các bug như vậy.

Tệ hơn nữa: nếu em đặt phòng khách sạn và vợ cũng đặt phòng đó cùng lúc, có thể cả hai đều thành công — đây là Write Skew, một bug subtle hơn không bị phát hiện bởi nhiều DB.

Tại sao Backend Dev cần hiểu Consistency Models?

Lý do	Hậu quả nếu không hiểu
Mặc định DB không safe	PostgreSQL default = READ COMMITTED → có Lost Update, Write Skew
CAP/PACELC chỉ là khởi đầu	”Eventual consistency” có 100 biến thể, mỗi cái khác nhau
Race condition không reproducible	Bug chỉ xảy ra 1/10K lần, lúc traffic cao → nightmare debug
Distributed system khuếch đại lỗi	Replication lag biến bug từ 1ms thành 10s
Auditor sẽ hỏi	”Tại sao 2 transaction cùng commit nhưng total wrong?”
Stripe, GitHub, MongoDB đã từng outage vì cái này	Real-world incident, không phải lý thuyết

Key insight: Em không cần thuộc lòng paper. Nhưng em bắt buộc phải nhớ: “default isolation level của DB tôi dùng là gì? Anomaly nào nó cho phép? Tôi đã code defensive cho anomaly đó chưa?”

Tại sao Alex Xu không đi sâu vào isolation levels?

Alex Xu vol 1+2 nói về CAP/PACELC ở mức bề mặt — đủ cho interview “Cassandra là AP, MongoDB là CP”. Nhưng trong production:

• PostgreSQL không chỉ là “CP”. Nó có 4 isolation levels khác nhau, mỗi level cho phép anomaly khác.
• Cassandra không phải “eventual consistency” thuần. Nó có Tunable Consistency (ONE, QUORUM, ALL).
• MongoDB đổi default từ “available, may lose writes” sang “majority writeConcern” sau khi bị Jepsen tố cáo.

Đây là kiến thức từng thời gian dài tin sai vì interview-prep books over-simplify.

Tham chiếu chính (đọc song song)

• DDIA Chapter 7 (Transactions) & Chapter 9 (Consistency and Consensus) — Martin Kleppmann — bible của topic này
• Jepsen.io — Kyle Kingsbury — https://jepsen.io/analyses — empirical testing của 30+ databases
• A Critique of ANSI SQL Isolation Levels (Berenson et al., 1995) — https://www.microsoft.com/en-us/research/publication/a-critique-of-ansi-sql-isolation-levels/ — paper tố cáo bug trong SQL standard
• Generalized Isolation Level Definitions (Adya, Liskov, O’Neil 2000) — http://pmg.csail.mit.edu/papers/icde00.pdf — định nghĩa mới chuẩn xác hơn
• Highly Available Transactions (Bailis et al. 2013) — http://www.bailis.org/papers/hat-vldb2014.pdf

---

2. Deep Dive — Khái niệm cốt lõi

2.1 Hai chiều của Consistency

Bất kỳ ai nói “tôi cần strong consistency” đều đang nói mơ hồ. Có 2 chiều khác biệt:

Chiều	Câu hỏi	Mô hình
Single-object	”Khi tôi read sau write, tôi thấy gì?”	Linearizability, Sequential, Causal, Eventual
Multi-object	”Khi tôi update nhiều row trong 1 transaction, isolation thế nào?”	Serializability, Snapshot Isolation, Read Committed…

Hierarchy:

                         STRONGEST ↑
   ┌────────────────────────────────────────────────┐
   │ Strict Serializability (Linearizable + Serial.) │  ← Spanner, FoundationDB
   ├────────────────────────────────────────────────┤
   │ Linearizable (single-object, real-time order)   │  ← etcd, ZooKeeper
   ├────────────────────────────────────────────────┤
   │ Serializable (multi-object, equiv to serial)    │  ← PostgreSQL SERIALIZABLE
   ├────────────────────────────────────────────────┤
   │ Snapshot Isolation                              │  ← Oracle, PostgreSQL REPEATABLE READ
   ├────────────────────────────────────────────────┤
   │ Sequential Consistency (program order)          │
   ├────────────────────────────────────────────────┤
   │ Read Committed (no dirty read)                  │  ← PostgreSQL default, MySQL InnoDB w/o flag
   ├────────────────────────────────────────────────┤
   │ Causal Consistency                              │  ← MongoDB causal session
   ├────────────────────────────────────────────────┤
   │ Read-your-writes / Monotonic reads              │
   ├────────────────────────────────────────────────┤
   │ Eventual Consistency                            │  ← Cassandra default, DynamoDB eventual
   └────────────────────────────────────────────────┘
                         WEAKEST ↓

Quy tắc: Càng strong → an toàn hơn nhưng chậm hơn và scale kém hơn. Càng weak → fast & scale tốt nhưng anomaly nhiều hơn.

2.2 Linearizability — Mạnh nhất cho single-object

Định nghĩa formal (Herlihy & Wing, 1990):

Mọi operation (read/write) atomically xảy ra tại một thời điểm giữa lúc nó được invoke và lúc trả response. Order tổng thể của các operation phải tôn trọng real-time order.

Ý nghĩa thực tế:

1. Sau khi write thành công, tất cả read sau đó (ở bất kỳ replica nào) phải thấy giá trị mới
2. Không có “stale read”
3. Nhìn từ ngoài, system hoạt động như chỉ có 1 copy duy nhất

2.2.1 Ví dụ minh hoạ

Có linearizable:

Client A: write(x=1) ──────────┐
                               ├─→ commit at T=10ms
Client B: read(x) ──────────────────→ T=15ms → returns 1 ✓
Client C: read(x) ──────────────────→ T=20ms → returns 1 ✓

Không linearizable (anomaly):

Client A: write(x=1) ──────────────→ commit at T=10ms
Client B: read(x) ──────────────────→ T=15ms → returns 0 ✗
                                                   ▲
                                  Stale read từ replica chưa replicate

2.2.2 Cost của Linearizability

Linearizability đắt vì:

• Read phải confirm với leader (ReadIndex protocol trong Raft) → 1 RTT
• Write phải đợi quorum ack → 1 RTT
• Single-DC: ~5-10ms per op
• Cross-region: ~50-150ms per op

Throughput: 5K-50K ops/s/cluster cho 5-node Raft.

2.2.3 Hệ thống cung cấp Linearizability

Hệ thống	Linearizable?
etcd	✅ (default)
ZooKeeper	✅ (write); reads chỉ sequential trừ khi dùng sync()
Spanner	✅ (external consistency = linearizability + serializability)
CockroachDB	✅
FoundationDB	✅
PostgreSQL	❌ (single-node strong, multi-replica not linearizable mặc định)
MongoDB	⚠️ (chỉ với readConcern: linearizable + write majority)
Cassandra	❌ (chỉ với LWT — lightweight transactions dùng Paxos)
DynamoDB	❌ (chỉ với strongly consistent read)
Redis	❌ (Redis Sentinel không linearizable; Redis Cluster cũng không)

Cảnh báo Redis: Mặc dù nhiều người dùng Redis làm “single source of truth”, Redis Sentinel/Cluster không linearizable. Distributed lock dùng Redlock có thể bị broken — đọc Kleppmann’s critique: https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

2.3 Sequential Consistency

Định nghĩa (Lamport, 1979):

Mọi process thấy operations trong cùng order, và order đó tôn trọng program order của mỗi process. Nhưng KHÔNG cần tôn trọng real-time order.

Khác biệt với Linearizability:

• Linearizable: real-time order (T=10 trước T=15 → mọi observer đều thấy như vậy)
• Sequential: chỉ cần consistent order, có thể “delay” toàn bộ system

Ví dụ: Wall clock có thể không sync, nhưng mỗi observer đều thấy: “A’s write trước B’s read trước C’s write”. Họ chỉ cần thống nhất một order.

Use case: Hiếm khi gặp trong DB hiện đại. Phổ biến hơn trong memory consistency model (CPU cache).

2.4 Causal Consistency

Định nghĩa:

Operations có causal relationship (ví dụ: read X rồi write Y dựa trên X) phải được thấy theo đúng thứ tự nhân quả ở mọi replica. Operations không có causal relationship có thể được thấy theo thứ tự khác nhau.

Ví dụ Facebook comment:

1. Alice posts: "I'm getting married!"
2. Bob comments: "Congrats!"  ← nhân quả: Bob phải thấy post trước
3. Charlie comments: "Where?"  ← nhân quả: phải thấy post trước

Causal consistency đảm bảo Charlie không thấy “Where?” trước khi thấy “I’m getting married!” — vì comment causally depends on post.

2.4.1 Cách implement: Vector Clocks

class VectorClock:
    """Mỗi node giữ một vector counter cho TẤT CẢ node."""
    def __init__(self, num_nodes, my_id):
        self.clock = [0] * num_nodes
        self.my_id = my_id
 
    def tick(self):
        self.clock[self.my_id] += 1
 
    def update(self, other_clock):
        # Pointwise max + tăng counter của mình
        for i in range(len(self.clock)):
            self.clock[i] = max(self.clock[i], other_clock[i])
        self.tick()
 
    def happens_before(self, other):
        """A happens-before B nếu mọi A[i] <= B[i] và có ít nhất 1 A[i] < B[i]."""
        return all(a <= b for a, b in zip(self.clock, other)) and \
               any(a < b for a, b in zip(self.clock, other))

Vấn đề Vector Clock: Kích thước O(N) với N = số node. Với cluster 1000 node → mỗi event mang theo 1000 counter → quá nặng.

2.4.2 Hybrid Logical Clock (HLC)

HLC = wall clock (physical) + logical counter, kết hợp ưu điểm cả 2:

• Physical: liên kết với real time (gần đúng)
• Logical: đảm bảo causality

HLC = (physical_time, logical_counter)

On send: HLC.physical = max(local_clock.physical, current_wall_time)
         HLC.logical = local_clock.logical + 1 (if physical unchanged) else 0

On receive(remote_HLC):
  HLC.physical = max(local.physical, remote.physical, wall_time)
  HLC.logical = ...

Ưu điểm: Kích thước cố định (16 bytes), gần với wall clock → debug dễ.

Hệ thống dùng HLC:

• CockroachDB — primary timestamp source
• YugabyteDB — same
• MongoDB (4.0+) — cluster time

Tham chiếu: Kulkarni et al., Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (2014) — https://cse.buffalo.edu/tech-reports/2014-04.pdf

2.4.3 Hệ thống Causal Consistency

• MongoDB — causal consistent sessions (4.0+): client.start_session(causal_consistency=True)
• CockroachDB — provide causal cho read after write trong same session
• COPS, Eiger (research) — causal+ consistency cho geo-replicated

2.5 Eventual Consistency

Định nghĩa:

Nếu ngừng update, eventually mọi replica sẽ converge về cùng state.

Đó là tất cả những gì nó hứa hẹn. Trong khi đang update:

• Read có thể trả stale data (vài ms — vài giờ)
• Order không guarantee
• Concurrent write → conflict (resolve sau bằng LWW, vector clock, hoặc CRDT)

Hệ thống:

• Cassandra (default consistency=LOCAL_ONE)
• DynamoDB (eventual read mode)
• Riak
• CouchDB

Pitfall thường gặp: Developer nghĩ “eventual consistency = data sẽ đúng sau vài giây”. Sai. Ngày 1 trong production: thấy data sai. Replication lag có thể 30 phút khi node lag, ngang với “vĩnh viễn” với user.

2.6 Session Guarantees (mid-tier consistency)

Giữa Eventual và Linearizability có nhiều mid-tier guarantees, đặc biệt cho session (1 user):

Guarantee	Định nghĩa
Read Your Writes (RYW)	Sau khi user write X, user đó phải thấy X
Monotonic Reads	User không bao giờ thấy time go backwards (đã thấy v=10, không thấy v=5)
Monotonic Writes	Write của user được apply theo program order
Writes Follow Reads	Nếu user read X=10 rồi write Y=20 → Y luôn được apply sau X

Use case thực tế — Avatar upload:

1. User upload avatar (write to master)
2. User refresh page (read from replica) — replica chưa nhận avatar mới
3. User thấy avatar cũ → tưởng upload fail → upload lại

Fix: Read-your-writes — sau write, đọc từ master trong N giây (gọi là sticky session hoặc read pinning).

def get_avatar(user_id):
    # Nếu vừa write trong 5 giây → đọc từ master
    if time.time() - last_write_time[user_id] < 5:
        return master.get(user_id)
    return replica.get(user_id)

2.7 Database Isolation Levels — SQL Standard

SQL-92 định nghĩa 4 isolation levels dựa trên 3 anomaly:

Level	Dirty Read	Non-repeatable Read	Phantom
READ UNCOMMITTED	✗ Có thể	✗ Có thể	✗ Có thể
READ COMMITTED	✓ Không	✗ Có thể	✗ Có thể
REPEATABLE READ	✓ Không	✓ Không	✗ Có thể
SERIALIZABLE	✓ Không	✓ Không	✓ Không

2.7.1 Anomaly #1 — Dirty Read

Transaction T1 read data chưa commit của T2. Nếu T2 rollback → T1 đã thấy data “bẩn” (không tồn tại thật).

-- T1                          T2
                              BEGIN;
                              UPDATE accounts SET balance = 200 WHERE id = 1;
SELECT balance FROM accounts; -- ← READ UNCOMMITTED: thấy 200
WHERE id = 1;                 ROLLBACK;  -- balance lại về 100
                              -- Nhưng T1 đã decide dựa trên 200!

Phổ biến trong: chỉ READ UNCOMMITTED (rất hiếm dùng).

2.7.2 Anomaly #2 — Non-repeatable Read

Trong cùng transaction T1, đọc cùng row 2 lần nhưng nhận 2 giá trị khác nhau (vì T2 commit ở giữa).

-- T1                                       T2
BEGIN;
SELECT balance FROM accounts WHERE id=1;    -- returns 100
                                             BEGIN;
                                             UPDATE accounts SET balance=200 WHERE id=1;
                                             COMMIT;
SELECT balance FROM accounts WHERE id=1;    -- returns 200 (??)
COMMIT;

Cho phép trong: READ UNCOMMITTED, READ COMMITTED.

2.7.3 Anomaly #3 — Phantom Read

T1 query với điều kiện 2 lần, nhận 2 set kết quả khác nhau (vì T2 INSERT/DELETE row mới match điều kiện).

-- T1                                       T2
BEGIN;
SELECT * FROM bookings WHERE date='2026-05-01';
-- Returns 5 rows
                                             BEGIN;
                                             INSERT INTO bookings (date) VALUES ('2026-05-01');
                                             COMMIT;
SELECT * FROM bookings WHERE date='2026-05-01';
-- Returns 6 rows — phantom!
COMMIT;

Cho phép trong: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ (theo SQL standard — nhưng PostgreSQL/MySQL InnoDB không có phantom ở RR vì dùng MVCC).

2.8 Critique of ANSI SQL — Còn nhiều anomaly khác

Berenson et al. 1995 chỉ ra: SQL standard bỏ sót nhiều anomaly nguy hiểm. Quan trọng nhất:

2.8.1 Lost Update

Hai T cùng read X, cùng update X → một update bị mất.

T1: read x = 100              T2: read x = 100
T1: write x = 100 + 50 = 150  T2: write x = 100 + 30 = 130
T1: commit                    T2: commit
                              ↑
                        Final x = 130 — mất +50 của T1!

Cho phép trong: READ COMMITTED, REPEATABLE READ (theo standard). PostgreSQL REPEATABLE READ detect và abort 1 trong 2.

Fix:

• SELECT ... FOR UPDATE (pessimistic lock)
• Atomic increment: UPDATE x SET v = v + 50 (không read trước)
• Optimistic CAS với version column
• SERIALIZABLE level

2.8.2 Write Skew (đặc biệt nguy hiểm)

Hai T đọc cùng tập rows, mỗi T update rows khác nhau dựa trên điều kiện. Cá nhân từng T thấy hợp lý, nhưng kết hợp vi phạm invariant.

Ví dụ kinh điển — Doctor on-call:

-- Invariant: phải có ít nhất 1 doctor on-call
 
-- T1 (Alice quitting on-call)         T2 (Bob quitting on-call)
BEGIN;                                  BEGIN;
SELECT COUNT(*) FROM doctors            SELECT COUNT(*) FROM doctors
  WHERE on_call = true;                   WHERE on_call = true;
-- returns 2 (Alice, Bob)              -- returns 2 (Alice, Bob)
 
-- "OK, có 2 người, mình quit cũng ok"  -- "OK, có 2 người, mình quit cũng ok"
 
UPDATE doctors SET on_call = false      UPDATE doctors SET on_call = false
  WHERE name = 'Alice';                   WHERE name = 'Bob';
COMMIT;                                 COMMIT;
 
-- Final: cả Alice và Bob đều quit → on-call = 0 → INVARIANT BROKEN

Cho phép trong: tất cả level trừ SERIALIZABLE. SI (Snapshot Isolation) cũng cho phép write skew.

Fix: SERIALIZABLE hoặc materialize conflict (lock 1 sentinel row).

2.8.3 Phantom Write Skew — Booking system

-- Hotel: phải max 1 booking per phòng per đêm
 
-- T1 (Hieu booking)                    T2 (Vợ Hieu booking)
BEGIN;                                  BEGIN;
SELECT * FROM bookings                  SELECT * FROM bookings
  WHERE room=101 AND date='2026-05-01';   WHERE room=101 AND date='2026-05-01';
-- returns empty                       -- returns empty
 
INSERT INTO bookings(room, date, user)  INSERT INTO bookings(room, date, user)
  VALUES (101, '2026-05-01', 'Hieu');     VALUES (101, '2026-05-01', 'Vo');
COMMIT;                                 COMMIT;
 
-- Cả 2 đều commit → DOUBLE BOOKING!

Cho phép trong: tất cả level (kể cả Snapshot Isolation) trừ SERIALIZABLE.

Fix:

• SERIALIZABLE
• Unique index trên (room, date) → DB tự reject 1
• Materialize lock (SELECT FOR UPDATE trên parent record)

2.9 MVCC — Multi-Version Concurrency Control

Hầu hết DB hiện đại (PostgreSQL, MySQL InnoDB, Oracle) implement isolation thông qua MVCC:

Nguyên lý: Thay vì lock, mỗi write tạo version mới. Read thấy version phù hợp với “snapshot” của transaction.

Time →

Initial:
  row(id=1): {value=A, txn_id=10, deleted=false}

T1 starts at T=100:
  reads snapshot → {value=A}

T2 at T=120:
  UPDATE row(1) SET value=B
  → tạo version mới: {value=B, txn_id=120, deleted=false}
  → version cũ vẫn còn: {value=A, txn_id=10}
  → COMMIT

T1 (still at snapshot T=100):
  reads → vẫn thấy {value=A} (snapshot không thay đổi)
  → no non-repeatable read

Implementation chi tiết (PostgreSQL):

• Mỗi row có 2 hidden cols: xmin (insert txn id), xmax (delete/update txn id)
• Transaction có snapshot = list of active txn IDs khi start
• Visibility check: row visible nếu xmin đã commit + chưa được delete bởi committed txn trong snapshot

Trade-off:

• ✅ Read không lock write, write không lock read → high concurrency
• ✅ Snapshot guarantee → no non-repeatable read
• ❌ Bloat: nhiều version cũ → cần VACUUM (PostgreSQL) hoặc purge (Oracle)
• ❌ Tăng disk usage tạm thời
• ❌ Vẫn cho phép Write Skew — đây là Snapshot Isolation, không phải Serializable

2.10 Snapshot Isolation (SI)

Snapshot Isolation = MVCC với 2 quy tắc:

1. T đọc từ snapshot tại lúc start
2. Khi T commit, check First-Committer-Wins (FCW): nếu có T’ đã commit và update cùng row → abort T

Hệ thống cung cấp SI:

• Oracle (mặc định)
• SQL Server (READ COMMITTED SNAPSHOT hoặc SNAPSHOT ISOLATION)
• PostgreSQL với REPEATABLE READ (note: SI mạnh hơn SQL standard RR)

Lưu ý quan trọng: PostgreSQL REPEATABLE READ thật sự là Snapshot Isolation (mạnh hơn SQL standard’s RR). Vẫn có Write Skew. Nếu cần thật sự serializable → dùng SERIALIZABLE (PostgreSQL implement bằng SSI từ 9.1+).

2.11 Serializable Snapshot Isolation (SSI)

Vấn đề SI: Vẫn có Write Skew + Phantom Write Skew.

SSI (Cahill et al., 2008) = SI + detect read-write conflicts dynamically:

Cách hoạt động:

• Track SIREAD locks (lightweight, không block) cho read operation
• Detect “dangerous structures”: 2 RW dependencies tạo cycle
• Abort 1 transaction trong cycle khi detect

Performance:

• ~10-20% overhead so với SI
• Nhưng có thể abort transaction → cần retry logic ở application
• Throughput thường tốt hơn 2PL serializable

Hệ thống:

• PostgreSQL 9.1+ — SERIALIZABLE mode dùng SSI
• CockroachDB — SSI variant
• FoundationDB — strict serializable

Tham chiếu: Cahill, Röhm, Fekete, Serializable Isolation for Snapshot Databases (SIGMOD 2008) — https://drkp.net/papers/ssi-vldb12.pdf

2.12 Real-world DB Isolation — Bảng tham khảo

DB	Default Level	Highest Available	MVCC?	Notes
PostgreSQL	READ COMMITTED	SERIALIZABLE (SSI từ 9.1)	✅	RR thật sự là SI; SERIALIZABLE = SSI
MySQL InnoDB	REPEATABLE READ	SERIALIZABLE (2PL)	✅	RR + gap locks → no phantom (extension)
Oracle	READ COMMITTED	SERIALIZABLE (SI thực ra)	✅	“Serializable” thật ra là SI — vẫn có write skew
SQL Server	READ COMMITTED	SNAPSHOT (SI) hoặc SERIALIZABLE (2PL)	Optional	Phải bật READ COMMITTED SNAPSHOT cho MVCC
MongoDB	local read	snapshot read concern + majority write	✅ (4.0+)	Multi-doc transactions từ 4.0
Cassandra	LOCAL_ONE	LOCAL_QUORUM (eventual)	❌	LWT dùng Paxos cho linearizable single-row
DynamoDB	Eventual read	Strong read + transactions	❌	Transactions = TransactWriteItems (2PC-like)
CockroachDB	SERIALIZABLE (SSI)	—	✅	Mặc định SSI
Spanner	External Consistency	—	✅ (TrueTime)	Linearizable + serializable

Pitfall: Oracle “SERIALIZABLE” mode thực ra là Snapshot Isolation — vẫn có write skew. Đây là source của nhiều bug financial trong production. Tham chiếu: Berenson critique 1995.

2.13 Mapping: Anomaly ↔ Real-world Bug

Anomaly	Real-world Example	Cost
Lost Update	2 ATM cùng rút → mất tiền của ngân hàng	$$
Dirty Read	Hệ thống ledger thấy số tạm thời, decide sai	$
Non-repeatable Read	Report tài chính thấy 2 số khác nhau cùng row	Reputation
Phantom Read	COUNT(*) trả 2 giá trị khác nhau	Logic bug
Write Skew (Doctor on-call)	Mất medical safety invariant	Lawsuit
Write Skew (Booking)	Hotel double-booking → khách hàng nổi giận	Customer churn
Write Skew (Wallet)	Withdraw từ joint account vượt limit	Financial fraud

2.14 Cassandra Tunable Consistency

Cassandra (và DynamoDB tương tự) cho phép per-query consistency:

Level	Read	Write
ONE	1 replica respond	1 replica ack
QUORUM	majority respond	majority ack
ALL	all respond	all ack
LOCAL_QUORUM	majority trong local DC	majority local DC

Quy tắc: Nếu R + W > N (replication factor) → strong consistency cho operation đó.

R	W	N	Strong?	Use case
1	1	3	❌ (R+W=2 ≤ 3)	Eventual; fastest
2	2	3	✅ (R+W=4 > 3)	Quorum; balanced
3	1	3	✅	Read-heavy: write fast
1	3	3	✅	Write-heavy: read fast

Pitfall: R+W > N chỉ đảm bảo “có overlap” — KHÔNG đảm bảo linearizability. Cassandra LWT (lightweight transaction) dùng Paxos để có linearizability cho compare-and-set.

2.15 Jepsen — Empirical Testing

Jepsen (Kyle Kingsbury) test consistency của database trong network partition. Findings nổi tiếng:

DB	Năm	Vấn đề phát hiện
MongoDB	2013	Mất “majority writes” trong partition; default config không safe
Riak	2013	Eventual consistency không chống split-brain trong concurrent updates
Cassandra	2013	LWT với CL.SERIAL có thể vi phạm linearizability
Elasticsearch	2014	Mất write trong partition; phù hợp search, không phù hợp source-of-truth
etcd / Consul	2014	Pass — Raft implementation đúng
VoltDB	2017	Phát hiện stale read trong network partition
CockroachDB	2017+	Pass nhiều round, phát hiện vài bug nhỏ đã fix
MongoDB 4.x	2020	Causal consistency có vài bug edge case
YugabyteDB	2019	Pass với caveat về CDC

Bài học: Marketing claim của vendor (e.g., “ACID compliant”, “linearizable”) không bằng test empirical. Nếu em build payment system → đọc Jepsen analysis của DB em chọn TRƯỚC.

Tham chiếu: https://jepsen.io/analyses (50+ analyses, free)

---

3. Estimation — Cost của Strong Consistency

3.1 Latency Cost của Linearizability

Setup: 5-node cluster, intra-DC RTT 0.5ms, NVMe SSD fsync 1ms.

Operation	Eventual	Causal	Linearizable	Strict Serializable
Read	0.5 ms (local)	1 ms	5 ms (ReadIndex)	10 ms (commit-wait)
Write	1 ms (async)	5 ms (quorum)	5 ms (quorum + fsync)	15 ms (TrueTime + quorum)
Throughput	100K+ ops/s	30K ops/s	10K ops/s	5K ops/s

Scaling cross-region (RTT 100ms):

Operation	Single-region linearizable	Multi-region linearizable
Read	5 ms	100-200 ms
Write	5 ms	100-200 ms
Throughput	10K ops/s	100-1K ops/s

Key insight: Linearizable cross-region gần như không scale. Đó là lý do Spanner dùng TrueTime (atomic clock) — để có thể commit local mà vẫn đảm bảo consistency.

3.2 Cost của SSI vs SI vs READ COMMITTED

Benchmark (PostgreSQL 14, 32-core, OLTP workload):

Level	Throughput	P99 Latency	Abort Rate
READ COMMITTED	100K txn/s	5 ms	<0.01%
REPEATABLE READ (SI)	95K txn/s	5 ms	0.5%
SERIALIZABLE (SSI)	80K txn/s	7 ms	2-5%

Quan sát:

• SSI overhead ~20% throughput
• Abort rate cao hơn → app cần retry logic
• Hot row (e.g., counter) → SSI abort cực cao → cần atomic increment

3.3 Khi nào chọn level nào?

Use case	Khuyến nghị	Lý do
User profile update	READ COMMITTED	Conflict hiếm, performance > correctness
Inventory deduction	SERIALIZABLE hoặc atomic SQL	Race condition = oversold
Wallet balance	SERIALIZABLE + retry hoặc per-user lock	Lost update = mất tiền
Doctor on-call check	SERIALIZABLE	Write skew = invariant broken
Hotel booking	SERIALIZABLE + unique index	Phantom write skew = double-book
Analytics dashboard	READ COMMITTED hoặc snapshot	Performance > recency
Audit log	append-only, READ COMMITTED	Immutable

---

4. Security First — Anomaly = Attack Vector

4.1 TOCTOU (Time-Of-Check, Time-Of-Use) Bug

Pattern:

# BAD — race condition
def withdraw(account_id, amount):
    balance = db.execute("SELECT balance FROM accounts WHERE id = %s", account_id)
    if balance >= amount:
        db.execute("UPDATE accounts SET balance = balance - %s WHERE id = %s",
                   amount, account_id)
        return "OK"
    return "Insufficient funds"

Attack: 2 parallel requests → 2 SELECT cùng thấy balance đủ → 2 UPDATE → balance âm.

Fix:

# GOOD — atomic check + update
def withdraw(account_id, amount):
    rows = db.execute("""
        UPDATE accounts
        SET balance = balance - %s
        WHERE id = %s AND balance >= %s
        RETURNING balance
    """, amount, account_id, amount)
 
    if not rows:
        return "Insufficient funds"
    return "OK"

4.2 Session-based attack — Read-after-write

Attack scenario:

• User upload bằng chứng thanh toán (image)
• App write to master, return “uploaded”
• User refresh, app read from replica → chưa replicate → “no proof”
• App auto-cancel order → user mất tiền

Mitigation:

• Read-your-writes guarantee
• Sticky session cho user vừa write
• Eventual write idempotency

4.3 Financial Write Skew Attack

Real-world example: 2 user joint account chuyển tiền cùng lúc → bypass daily limit.

-- T1 (Husband transferring)
BEGIN;
SELECT SUM(amount) FROM transfers WHERE account_id=1 AND DATE=TODAY;
-- = 5M VND (under 10M limit)
INSERT INTO transfers VALUES (1, 4M, ...);
COMMIT;
 
-- T2 (Wife transferring) — concurrent
BEGIN;
SELECT SUM(amount) FROM transfers WHERE account_id=1 AND DATE=TODAY;
-- = 5M VND (chưa thấy T1)
INSERT INTO transfers VALUES (1, 4M, ...);
COMMIT;
 
-- Total = 13M, exceed 10M limit!

Fix:

• SERIALIZABLE level
• Hoặc materialize lock: SELECT ... FOR UPDATE trên account row trước check
• Hoặc enforce ở app layer với distributed lock

4.4 SQL Injection vẫn là #1

Isolation không bảo vệ khỏi injection. Phải combine:

• Parameterized queries (always)
• Least privilege DB user
• Application-level validation
• Audit log

Tham chiếu Tuan-07-Database-Sharding-Replication section 4 Security.

---

5. DevOps — Vận hành Isolation Levels

5.1 Detect Anomaly trong Production

PostgreSQL: enable log_lock_waits để detect lock contention:

-- postgresql.conf
log_lock_waits = on
deadlock_timeout = 1s
log_min_duration_statement = 100ms

Detect serialization conflicts:

-- Track serialization failure rate
SELECT
    classid,
    objid,
    COUNT(*)
FROM pg_locks
WHERE NOT granted
GROUP BY classid, objid
ORDER BY count DESC LIMIT 10;

5.2 Prometheus Metrics cho PostgreSQL Isolation

groups:
  - name: postgres_isolation_alerts
    rules:
      # Tỉ lệ serialization conflict cao
      - alert: PostgresHighSerializationFailures
        expr: |
          rate(pg_stat_database_conflicts_total{conflicts_on='serialization'}[5m]) > 10
        for: 5m
        labels: { severity: warning }
        annotations:
          summary: "{{ $value }}/s SERIALIZABLE aborts on {{ $labels.datname }}"
          description: "Need application retry logic. Check hot rows."
 
      # Deadlock rate
      - alert: PostgresHighDeadlockRate
        expr: |
          rate(pg_stat_database_deadlocks[5m]) > 1
        for: 5m
        labels: { severity: warning }
 
      # Replication lag (cause RYW violation)
      - alert: PostgresHighReplicationLag
        expr: |
          pg_replication_lag_seconds > 10
        for: 5m
        labels: { severity: critical }
        annotations:
          summary: "Replication lag {{ $value }}s — read-your-writes broken"
 
      # Long-running transactions hold locks
      - alert: PostgresLongRunningTransaction
        expr: |
          pg_stat_activity_max_tx_duration > 600
        for: 5m
        labels: { severity: warning }

5.3 Application-side Retry Logic

SSI và SI có thể abort → app phải retry. Pattern chuẩn:

import psycopg2
from psycopg2 import errors
import time
import random
 
def execute_with_retry(conn, operation, max_retries=3):
    """Retry on serialization failure with exponential backoff."""
    for attempt in range(max_retries):
        try:
            with conn.cursor() as cur:
                conn.autocommit = False
                cur.execute("SET TRANSACTION ISOLATION LEVEL SERIALIZABLE")
                result = operation(cur)
                conn.commit()
                return result
        except errors.SerializationFailure as e:
            conn.rollback()
            if attempt == max_retries - 1:
                raise
            # Exponential backoff with jitter
            wait = (2 ** attempt) * 0.1 + random.uniform(0, 0.1)
            time.sleep(wait)
        except Exception:
            conn.rollback()
            raise
 
    raise RuntimeError(f"Failed after {max_retries} retries")
 
 
# Usage
def transfer(cur):
    cur.execute("UPDATE accounts SET balance = balance - 100 WHERE id = 1")
    cur.execute("UPDATE accounts SET balance = balance + 100 WHERE id = 2")
 
execute_with_retry(conn, transfer)

5.4 Test Isolation Bugs Locally

Tool: pgTAP for PostgreSQL anomaly tests.

-- Test: ensure write skew prevented
BEGIN;
SELECT plan(1);
 
-- T1 và T2 chạy parallel (dùng pgbench với scripts)
-- ...
 
SELECT is(
    (SELECT COUNT(*) FROM doctors WHERE on_call = true),
    1::bigint,
    'At least 1 doctor must remain on-call'
);
 
SELECT * FROM finish();
ROLLBACK;

Tool: Jepsen-Maelstrom cho distributed system. Local testing với simulated partitions.

5.5 Monitor Replication Consistency

PostgreSQL:

-- Trên primary
SELECT pg_current_wal_lsn();
 
-- Trên replica
SELECT pg_last_wal_replay_lsn();
 
-- Lag (bytes)
SELECT pg_wal_lsn_diff(primary_lsn, replica_lsn);
 
-- Lag (seconds) — chỉ chính xác khi có write
SELECT EXTRACT(EPOCH FROM (now() - pg_last_xact_replay_timestamp()));

5.6 Choose isolation: decision tree

Q: Bạn có **multi-row update** với invariant không?
├─ Yes → SERIALIZABLE
└─ No
   ├─ Q: Bạn có **lost update** risk (read-modify-write)?
   │  ├─ Yes → REPEATABLE READ + retry, hoặc atomic SQL
   │  └─ No → READ COMMITTED OK
   └─ Q: Cross-region read?
      ├─ Strong → linearizable read (etcd, Spanner)
      └─ OK eventual → eventual với read-your-writes session

---

6. Code Implementation

6.1 Demo: 5 Anomaly trong Python + PostgreSQL

"""
demo_anomalies.py — Reproduce 5 isolation anomalies với PostgreSQL.
Run: docker run -d -e POSTGRES_PASSWORD=test -p 5432:5432 postgres:15
"""
 
import psycopg2
import threading
import time
from contextlib import contextmanager
 
 
CONN_STRING = "host=localhost user=postgres password=test dbname=postgres"
 
 
@contextmanager
def conn(isolation: str = "READ COMMITTED"):
    c = psycopg2.connect(CONN_STRING)
    c.autocommit = False
    with c.cursor() as cur:
        cur.execute(f"SET TRANSACTION ISOLATION LEVEL {isolation}")
    try:
        yield c
    finally:
        c.close()
 
 
def setup():
    c = psycopg2.connect(CONN_STRING)
    c.autocommit = True
    with c.cursor() as cur:
        cur.execute("DROP TABLE IF EXISTS accounts, doctors, bookings")
        cur.execute("""
            CREATE TABLE accounts (id INT PRIMARY KEY, balance INT);
            CREATE TABLE doctors (id INT PRIMARY KEY, name TEXT, on_call BOOL);
            CREATE TABLE bookings (id SERIAL PRIMARY KEY, room INT, day DATE);
        """)
        cur.execute("INSERT INTO accounts VALUES (1, 100), (2, 100)")
        cur.execute("""
            INSERT INTO doctors VALUES
                (1, 'Alice', true),
                (2, 'Bob', true)
        """)
    c.close()
 
 
# === Anomaly 1: Lost Update ===
 
def demo_lost_update():
    print("\n=== Anomaly 1: Lost Update (READ COMMITTED) ===")
 
    def transfer(amount, label):
        with conn("READ COMMITTED") as c:
            cur = c.cursor()
            cur.execute("SELECT balance FROM accounts WHERE id = 1")
            balance = cur.fetchone()[0]
            print(f"  T{label} read balance = {balance}")
 
            time.sleep(0.5)  # Simulate think time
 
            new_balance = balance + amount
            cur.execute("UPDATE accounts SET balance = %s WHERE id = 1",
                       (new_balance,))
            c.commit()
            print(f"  T{label} write balance = {new_balance}")
 
    setup()
    t1 = threading.Thread(target=transfer, args=(50, "1"))
    t2 = threading.Thread(target=transfer, args=(30, "2"))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
 
    with conn() as c:
        cur = c.cursor()
        cur.execute("SELECT balance FROM accounts WHERE id = 1")
        final = cur.fetchone()[0]
        print(f"  Final balance = {final} (expected 180, got {final})")
        if final != 180:
            print("  ❌ LOST UPDATE detected!")
 
 
# === Anomaly 2: Write Skew ===
 
def demo_write_skew():
    print("\n=== Anomaly 2: Write Skew (REPEATABLE READ — SI) ===")
 
    def quit_oncall(name, label):
        with conn("REPEATABLE READ") as c:
            cur = c.cursor()
            cur.execute("SELECT COUNT(*) FROM doctors WHERE on_call = true")
            count = cur.fetchone()[0]
            print(f"  T{label}: {name} sees {count} doctors on-call")
 
            time.sleep(0.5)
 
            if count >= 2:
                cur.execute(
                    "UPDATE doctors SET on_call = false WHERE name = %s",
                    (name,)
                )
                c.commit()
                print(f"  T{label}: {name} quit on-call")
            else:
                c.rollback()
                print(f"  T{label}: {name} cannot quit (only {count} left)")
 
    setup()
    t1 = threading.Thread(target=quit_oncall, args=("Alice", "1"))
    t2 = threading.Thread(target=quit_oncall, args=("Bob", "2"))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
 
    with conn() as c:
        cur = c.cursor()
        cur.execute("SELECT COUNT(*) FROM doctors WHERE on_call = true")
        final = cur.fetchone()[0]
        print(f"  Final on-call count = {final}")
        if final == 0:
            print("  ❌ WRITE SKEW: invariant broken (no doctor on-call)!")
 
 
# === Anomaly 3: Phantom Write Skew (Booking) ===
 
def demo_phantom_write_skew():
    print("\n=== Anomaly 3: Phantom Write Skew — Hotel Booking ===")
 
    def book_room(user, label):
        with conn("REPEATABLE READ") as c:
            cur = c.cursor()
            cur.execute(
                "SELECT COUNT(*) FROM bookings WHERE room=101 AND day='2026-05-01'"
            )
            count = cur.fetchone()[0]
            print(f"  T{label}: {user} sees {count} existing bookings")
 
            time.sleep(0.5)
 
            if count == 0:
                cur.execute(
                    "INSERT INTO bookings (room, day) VALUES (101, '2026-05-01')"
                )
                c.commit()
                print(f"  T{label}: {user} booked successfully")
            else:
                c.rollback()
 
    setup()
    t1 = threading.Thread(target=book_room, args=("Hieu", "1"))
    t2 = threading.Thread(target=book_room, args=("Wife", "2"))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
 
    with conn() as c:
        cur = c.cursor()
        cur.execute(
            "SELECT COUNT(*) FROM bookings WHERE room=101 AND day='2026-05-01'"
        )
        final = cur.fetchone()[0]
        print(f"  Final bookings = {final}")
        if final > 1:
            print(f"  ❌ DOUBLE BOOKING: {final} bookings for same room/day!")
 
 
# === Fix: SERIALIZABLE ===
 
def demo_serializable_prevents():
    print("\n=== Fix: SERIALIZABLE prevents write skew ===")
 
    aborted = []
 
    def quit_oncall(name, label):
        try:
            with conn("SERIALIZABLE") as c:
                cur = c.cursor()
                cur.execute("SELECT COUNT(*) FROM doctors WHERE on_call = true")
                count = cur.fetchone()[0]
                print(f"  T{label}: {name} sees {count} doctors on-call")
 
                time.sleep(0.5)
 
                if count >= 2:
                    cur.execute(
                        "UPDATE doctors SET on_call = false WHERE name = %s",
                        (name,)
                    )
                    c.commit()
                    print(f"  T{label}: {name} quit successfully")
        except psycopg2.errors.SerializationFailure:
            aborted.append(name)
            print(f"  T{label}: {name} ABORTED (serialization failure) — would retry in real app")
 
    setup()
    t1 = threading.Thread(target=quit_oncall, args=("Alice", "1"))
    t2 = threading.Thread(target=quit_oncall, args=("Bob", "2"))
    t1.start()
    t2.start()
    t1.join()
    t2.join()
 
    with conn() as c:
        cur = c.cursor()
        cur.execute("SELECT COUNT(*) FROM doctors WHERE on_call = true")
        final = cur.fetchone()[0]
        print(f"  Final on-call = {final}, aborted = {aborted}")
        if final >= 1:
            print("  ✅ SAFE: at least 1 doctor on-call")
 
 
if __name__ == "__main__":
    demo_lost_update()
    demo_write_skew()
    demo_phantom_write_skew()
    demo_serializable_prevents()

6.2 Mini MVCC Implementation

"""
Mini MVCC — educational implementation.
Demonstrates: snapshot isolation via versioned rows.
"""
 
from dataclasses import dataclass, field
from typing import Optional
 
 
@dataclass
class Version:
    value: any
    txn_id: int
    is_deleted: bool = False
 
 
@dataclass
class Row:
    """Multi-version row."""
    versions: list[Version] = field(default_factory=list)
 
 
class MVCCStore:
    def __init__(self):
        self.next_txn_id = 1
        self.committed_txns: set[int] = set()
        self.active_txns: set[int] = set()
        self.data: dict[str, Row] = {}
 
    def begin_transaction(self) -> "Transaction":
        txn_id = self.next_txn_id
        self.next_txn_id += 1
        self.active_txns.add(txn_id)
        # Snapshot = currently committed txns
        snapshot = self.committed_txns.copy()
        return Transaction(self, txn_id, snapshot)
 
 
class Transaction:
    def __init__(self, store: MVCCStore, txn_id: int, snapshot: set[int]):
        self.store = store
        self.txn_id = txn_id
        self.snapshot = snapshot
        self.read_set: set[str] = set()
        self.write_set: dict[str, any] = {}
        self.committed = False
 
    def read(self, key: str) -> Optional[any]:
        # Check own writes first
        if key in self.write_set:
            return self.write_set[key]
 
        self.read_set.add(key)
 
        if key not in self.store.data:
            return None
 
        # Find latest version visible to this snapshot
        for v in reversed(self.store.data[key].versions):
            if v.txn_id == self.txn_id:
                return None if v.is_deleted else v.value
            if v.txn_id in self.snapshot:
                return None if v.is_deleted else v.value
 
        return None
 
    def write(self, key: str, value: any):
        self.write_set[key] = value
 
    def commit(self) -> bool:
        # Snapshot Isolation: First-Committer-Wins check
        for key in self.write_set:
            if key not in self.store.data:
                continue
            for v in self.store.data[key].versions:
                # Conflict: someone wrote this key after our snapshot
                if v.txn_id not in self.snapshot and v.txn_id != self.txn_id:
                    if v.txn_id in self.store.committed_txns:
                        # Abort
                        self.store.active_txns.discard(self.txn_id)
                        return False
 
        # Apply writes
        for key, value in self.write_set.items():
            if key not in self.store.data:
                self.store.data[key] = Row()
            self.store.data[key].versions.append(
                Version(value=value, txn_id=self.txn_id)
            )
 
        self.store.committed_txns.add(self.txn_id)
        self.store.active_txns.discard(self.txn_id)
        self.committed = True
        return True
 
    def rollback(self):
        self.store.active_txns.discard(self.txn_id)
 
 
# === Demo ===
 
def demo_mvcc():
    store = MVCCStore()
 
    # Initial state
    t0 = store.begin_transaction()
    t0.write("x", 100)
    t0.commit()
 
    # T1 starts
    t1 = store.begin_transaction()
    print(f"T1 reads x = {t1.read('x')}")  # 100
 
    # T2 commits update
    t2 = store.begin_transaction()
    t2.write("x", 200)
    t2.commit()
    print(f"T2 committed x = 200")
 
    # T1 still sees old value (snapshot isolation)
    print(f"T1 reads x = {t1.read('x')}")  # Still 100!
 
    # T1 tries to write x → conflict with T2
    t1.write("x", 150)
    success = t1.commit()
    print(f"T1 commit: {'success' if success else 'ABORTED (FCW conflict)'}")
 
 
if __name__ == "__main__":
    demo_mvcc()

6.3 Atomic Increment Pattern

"""
Pattern: avoid lost update with atomic SQL.
"""
 
# BAD — race condition
def increment_bad(conn, account_id, amount):
    balance = conn.execute(
        "SELECT balance FROM accounts WHERE id = %s", account_id
    ).fetchone()[0]
    new_balance = balance + amount
    conn.execute(
        "UPDATE accounts SET balance = %s WHERE id = %s",
        new_balance, account_id
    )
 
# GOOD — atomic
def increment_good(conn, account_id, amount):
    conn.execute(
        "UPDATE accounts SET balance = balance + %s WHERE id = %s",
        amount, account_id
    )
 
# GOOD — with conditional check (CAS)
def withdraw_safe(conn, account_id, amount):
    rows = conn.execute("""
        UPDATE accounts
        SET balance = balance - %s
        WHERE id = %s AND balance >= %s
        RETURNING balance
    """, amount, account_id, amount).fetchall()
 
    if not rows:
        raise InsufficientFunds()
    return rows[0][0]

---

7. System Design Diagrams

7.1 Consistency Models Hierarchy

graph TD
    StrictSerial["Strict Serializable<br/>(Linearizable + Serializable)<br/>Spanner, FoundationDB"]
    Linear["Linearizable<br/>(single-object real-time)<br/>etcd, ZooKeeper"]
    Serial["Serializable<br/>(multi-object equiv to serial)<br/>PostgreSQL SSI"]
    SI["Snapshot Isolation<br/>Oracle, PostgreSQL RR"]
    Sequential["Sequential Consistency<br/>(program order)"]
    RC["Read Committed<br/>PostgreSQL default"]
    Causal["Causal Consistency<br/>MongoDB causal session"]
    RYW["Read-your-writes<br/>Monotonic reads"]
    Eventual["Eventual<br/>Cassandra, DynamoDB"]

    StrictSerial --> Linear
    StrictSerial --> Serial
    Linear --> Sequential
    Serial --> SI
    SI --> RC
    Sequential --> Causal
    RC --> Causal
    Causal --> RYW
    RYW --> Eventual

    style StrictSerial fill:#1b5e20,color:#fff
    style Linear fill:#2e7d32,color:#fff
    style Serial fill:#388e3c,color:#fff
    style SI fill:#43a047,color:#fff
    style Sequential fill:#66bb6a,color:#fff
    style RC fill:#81c784,color:#fff
    style Causal fill:#a5d6a7,color:#000
    style RYW fill:#c8e6c9,color:#000
    style Eventual fill:#e8f5e9,color:#000

7.2 Linearizable vs Eventual — Timeline

sequenceDiagram
    participant A as Client A
    participant L as Leader
    participant R1 as Replica 1
    participant R2 as Replica 2
    participant B as Client B

    Note over A,B: Linearizable
    A->>L: write(x=1)
    L->>R1: replicate
    L->>R2: replicate
    R1-->>L: ack
    R2-->>L: ack
    L-->>A: 200 OK
    Note right of L: Now visible everywhere
    B->>R1: read(x)
    R1-->>B: 1 ✓

    Note over A,B: Eventual (vs)
    A->>L: write(x=1)
    L-->>A: 200 OK (return immediately)
    L-->>R1: replicate (async)
    Note right of L: Replica still has old value
    B->>R2: read(x)
    R2-->>B: 0 ✗ (stale!)
    L-->>R2: replicate (eventually)

7.3 Write Skew Visualization

flowchart TB
    subgraph T1["Transaction 1 (Alice)"]
        T1A["Read: 2 doctors on-call"]
        T1B["Decide: safe to quit"]
        T1C["Update: Alice.on_call = false"]
        T1D["Commit"]
    end

    subgraph T2["Transaction 2 (Bob)"]
        T2A["Read: 2 doctors on-call"]
        T2B["Decide: safe to quit"]
        T2C["Update: Bob.on_call = false"]
        T2D["Commit"]
    end

    State1["Initial:<br/>Alice=on, Bob=on<br/>Total: 2"]
    State2["After T1 commit:<br/>Alice=off, Bob=on<br/>Total: 1"]
    State3["After T2 commit:<br/>Alice=off, Bob=off<br/>Total: 0 ❌ INVARIANT BROKEN"]

    State1 -->|T1 reads at SI snapshot| T1A
    State1 -->|T2 reads at SI snapshot| T2A
    T1A --> T1B --> T1C --> T1D
    T2A --> T2B --> T2C --> T2D
    T1D -->|"Both T1, T2 update<br/>DIFFERENT rows<br/>→ no conflict at SI"| State2
    T2D --> State3

    style State3 fill:#ffcdd2,color:#000
    style State1 fill:#c8e6c9,color:#000

7.4 MVCC Visualization

flowchart LR
    subgraph T1["Transaction T1<br/>snapshot at T=100"]
        T1R["Read: x = ?"]
        T1R -.snapshot.-> V1
    end

    subgraph T2["Transaction T2<br/>snapshot at T=120"]
        T2W["Write: x = B at T=120"]
        T2C["Commit at T=125"]
    end

    subgraph T3["Transaction T3<br/>starts at T=130"]
        T3R["Read: x = ?"]
        T3R -.snapshot.-> V2
    end

    subgraph Versions["Row x — versions"]
        V1["{value: A,<br/>xmin: 50,<br/>xmax: 120}"]
        V2["{value: B,<br/>xmin: 120,<br/>xmax: ∞}"]
        V1 --> V2
    end

    style V1 fill:#fff9c4
    style V2 fill:#c8e6c9

7.5 Isolation Level Decision Tree

flowchart TD
    Start[Need transaction]
    Q1{Multi-row update<br/>with invariant?}
    Q2{Read-modify-write<br/>pattern?}
    Q3{Cross-region read?}

    Start --> Q1
    Q1 -->|Yes| SERIAL[SERIALIZABLE<br/>+ retry logic]
    Q1 -->|No| Q2
    Q2 -->|Yes| RR[REPEATABLE READ<br/>+ retry,<br/>or atomic SQL]
    Q2 -->|No| Q3
    Q3 -->|Strong| LIN[Linearizable<br/>etcd / Spanner]
    Q3 -->|Eventual OK| RC[READ COMMITTED<br/>+ session sticky]

    style SERIAL fill:#1b5e20,color:#fff
    style RR fill:#388e3c,color:#fff
    style LIN fill:#0d47a1,color:#fff
    style RC fill:#81c784,color:#000

---

8. Aha Moments & Pitfalls

Aha Moments

#1: “Strong consistency” là từ vô nghĩa. Phải hỏi: linearizable? serializable? cả hai? Hai khái niệm khác nhau hoàn toàn — linearizable nói về single-object real-time order, serializable nói về multi-object equivalent to serial execution. Spanner cung cấp cả hai (strict serializability), PostgreSQL SERIALIZABLE chỉ cung cấp serializable.

#2: PostgreSQL “REPEATABLE READ” thật ra là Snapshot Isolation — mạnh hơn SQL standard’s RR, nhưng vẫn có Write Skew. Nếu app cần invariant chặt → phải dùng SERIALIZABLE (PostgreSQL implement bằng SSI từ 9.1+).

#3: Oracle “SERIALIZABLE” mode thực ra là SI — không phải serializable thật. Đây là source của nhiều bug financial trong production. Khi audit Oracle code → kiểm tra Write Skew patterns.

#4: MVCC ≠ Serializability. MVCC chỉ là mechanism (multi-version storage). Nó giải quyết Non-repeatable Read và Phantom (qua snapshot), nhưng không giải quyết Write Skew. SSI thêm runtime detection cho RW conflicts để đạt full serializability.

#5: Eventual consistency không có upper bound. “Eventually” có thể là 5ms, 5 phút, hoặc 5 giờ tuỳ network/load. Đừng hứa với business “data sẽ consistent sau 1 giây” — vì khi node lag, lag có thể vô hạn.

#6: Read-your-writes là minimum cho UX tốt. Mọi user-facing app cần ít nhất guarantee này. Không có nó, user upload xong refresh không thấy → tưởng bug → upload lại → duplicate.

#7: Atomic SQL > application-level locking. UPDATE accounts SET balance = balance - 100 luôn atomic, không cần SI/SSI. Khi có thể viết operation thành atomic SQL → đừng read-modify-write trong app.

#8: Jepsen analysis trumps marketing. Mọi vendor đều claim “ACID compliant”. Đọc Jepsen analysis trước khi tin: https://jepsen.io/analyses

Pitfalls — Sai lầm thường gặp

Pitfall 1: Không biết default level

Sai: Dùng PostgreSQL nhưng không biết default = READ COMMITTED → có Lost Update + Write Skew. Đúng: Luôn check SHOW transaction_isolation ở connection. Set explicit nếu cần: SET TRANSACTION ISOLATION LEVEL REPEATABLE READ.

Pitfall 2: Tin “Serializable” của Oracle

Sai: Code financial system trên Oracle SERIALIZABLE → tin rằng “no anomaly”. Bị Write Skew trong production. Đúng: Hiểu Oracle SERIALIZABLE = SI thực ra. Cần materialize lock hoặc dùng explicit SELECT FOR UPDATE cho invariant chặt.

Pitfall 3: Read-modify-write trong application

# BAD
balance = db.read(...)
new_balance = balance + amount
db.write(...)  # Race condition!
 
# GOOD — atomic SQL
db.execute("UPDATE accounts SET balance = balance + %s WHERE id = %s", ...)

Pitfall 4: SSI không có retry logic

Sai: Đặt SET TRANSACTION ISOLATION LEVEL SERIALIZABLE xong forget. Khi traffic cao → 5% transaction abort → user thấy error “could not serialize access”. Đúng: Wrap mọi SERIALIZABLE transaction với retry logic + exponential backoff (xem section 5.3).

Pitfall 5: Linearizable everywhere

Sai: “Strong consistency cho mọi read” → mọi read đi qua leader → throughput cap ở 10K/s. Đúng: Phân loại read. User profile, analytics → eventual OK. Wallet balance, inventory → linearizable. Mix tuỳ use case.

Pitfall 6: Cross-region linearizable

Sai: Multi-region cluster với linearizable read → mỗi read = RTT 100ms → user complain chậm. Đúng: Dùng causal consistency hoặc bounded staleness cho geo-distributed. Nếu thật cần linearizable cross-region → Spanner với TrueTime, hoặc accept latency cost.

Pitfall 7: MongoDB default config

Sai: MongoDB cũ với default writeConcern=1 → write có thể bị mất khi primary fail. Tham chiếu Jepsen 2013. Đúng: MongoDB 4.x trở lên: dùng writeConcern: { w: "majority" } và readConcern: "majority" hoặc "linearizable".

Pitfall 8: Cassandra LWT cho mọi thứ

Sai: Dùng Cassandra LWT (lightweight transaction) cho mọi write để “đảm bảo consistency” → throughput giảm 10x. Đúng: LWT chỉ dùng khi thật sự cần CAS (compare-and-set). Cho normal write → QUORUM consistency là đủ.

Pitfall 9: Phantom Write Skew không có unique constraint

Sai: Booking system dựa solely vào application-level check IF NOT EXISTS THEN INSERT. Đúng: Luôn có unique index ở DB level — defense in depth. Application check + DB constraint.

Pitfall 10: Not testing under partition

Sai: Test consistency trên local dev với 1 node → “all good”. Production multi-region → discover bug. Đúng: Dùng Jepsen-Maelstrom hoặc tc/iptables để simulate partition. Test write/read behavior khi 1 replica isolated.

---

9. Internal Links — Liên kết kiến thức

Consistency & Isolation trong các tuần

Tuần	Liên hệ
Tuan-07-Database-Sharding-Replication	CAP/PACELC; replication consistency; PostgreSQL config
Tuan-08-Message-Queue	Kafka exactly-once = idempotent producer + transactional commit (similar concepts)
Tuan-Bonus-Consensus-Raft-Paxos	Raft cung cấp linearizability; etcd dùng cho config
Tuan-20-Design-Key-Value-Store	Tunable consistency (R+W>N), vector clocks, LWW
Case-Design-Payment-System	SERIALIZABLE cho ledger; idempotency key; double-entry
Case-Design-Hotel-Reservation-System	Phantom write skew → unique index + SERIALIZABLE
Case-Design-Stock-Exchange	Linearizable order book; matching engine cần serial order
Case-Design-Digital-Wallet	Lost update prevention; atomic balance update
Case-Design-Distributed-Message-Queue	Kafka transactional producer

Tham khảo bắt buộc đọc

Books:

• Martin Kleppmann, Designing Data-Intensive Applications — Ch.7 (Transactions), Ch.9 (Consistency and Consensus) — https://dataintensive.net/
• Alex Petrov, Database Internals — Part II — https://www.databass.dev/
• Roberto Vitillo, Understanding Distributed Systems — Part on Replication — https://understandingdistributed.systems/

Papers:

• Berenson et al., A Critique of ANSI SQL Isolation Levels (1995) — https://www.microsoft.com/en-us/research/publication/a-critique-of-ansi-sql-isolation-levels/
• Adya, Liskov, O’Neil, Generalized Isolation Level Definitions (2000) — http://pmg.csail.mit.edu/papers/icde00.pdf
• Cahill, Röhm, Fekete, Serializable Isolation for Snapshot Databases (SIGMOD 2008) — https://drkp.net/papers/ssi-vldb12.pdf
• Bailis et al., Highly Available Transactions (VLDB 2014) — http://www.bailis.org/papers/hat-vldb2014.pdf
• Herlihy & Wing, Linearizability: A Correctness Condition for Concurrent Objects (1990) — https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
• Lamport, How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs (1979) — sequential consistency
• Kulkarni et al., Logical Physical Clocks (HLC, 2014) — https://cse.buffalo.edu/tech-reports/2014-04.pdf

Engineering blogs & Jepsen:

• Jepsen analyses — https://jepsen.io/analyses (50+ DBs)
• Martin Kleppmann, How to do distributed locking — https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
• Peter Bailis, Linearizability vs Serializability — http://www.bailis.org/blog/linearizability-versus-serializability/
• CockroachDB blog on serializable — https://www.cockroachlabs.com/blog/serializable-lockless-distributed-isolation-cockroachdb/
• PostgreSQL Wiki — Serializable Snapshot Isolation — https://wiki.postgresql.org/wiki/SSI

Courses:

• MIT 6.5840 — Lab on linearizability testing
• CMU 15-445 — Lectures on concurrency control & MVCC

---

File tiếp theo (Batch A3): Tuan-Bonus-Outbox-Pattern — Outbox + CDC + Debezium + Saga choreography vs orchestration.

File trước trong loạt bonus: Tuan-Bonus-Consensus-Raft-Paxos — Linearizability của Raft là foundation cho external consistency.