Chương 5 — Replication

🎯 Mục tiêu chương: Hiểu ba mô hình replication chính (single-leader, multi-leader, leaderless), các trade-off giữa synchronous và asynchronous, những bất thường do replication lag gây ra, và cách hệ thống phát hiện/giải quyết concurrent writes.

Tổng quan: Replication là gì và để làm gì?

Replication = giữ bản sao của cùng một dữ liệu trên nhiều máy nối mạng. Ba lý do chính: - Giảm latency: đặt dữ liệu gần người dùng về mặt địa lý. - Tăng availability: hệ thống vẫn chạy khi một số phần bị hỏng. - Tăng read throughput: scale out số máy phục vụ đọc.

Chương này giả định dataset đủ nhỏ để mỗi máy chứa được toàn bộ (partitioning để sang chương 6). Nếu dữ liệu không bao giờ thay đổi thì replication rất dễ — chỉ copy một lần. Toàn bộ độ khó nằm ở việc xử lý thay đổi (changes). Gần như mọi distributed database dùng một trong ba cách: single-leader, multi-leader, leaderless.

Nguyên lý replication đã được nghiên cứu từ những năm 1970 và không đổi nhiều vì các giới hạn cơ bản của mạng vẫn vậy; nhưng dev thì mới làm quen nên hay hiểu lầm các khái niệm như eventual consistency.

Leaders and Followers

Mỗi node lưu một bản sao gọi là replica. Cách phổ biến nhất để đảm bảo mọi write đến được mọi replica là leader-based replication (còn gọi active/passive, master–slave): 1. Một replica là leader (master/primary). Mọi write phải gửi tới leader; leader ghi vào storage local trước. 2. Các replica còn lại là followers (read replicas, slaves, secondaries, hot standbys). Leader gửi thay đổi cho followers qua replication log / change stream; follower áp dụng đúng theo thứ tự như leader. 3. Đọc có thể từ leader hoặc bất kỳ follower nào; nhưng chỉ leader nhận write.

Được dùng trong: PostgreSQL (từ 9.0), MySQL, Oracle Data Guard, SQL Server AlwaysOn; MongoDB, RethinkDB, Espresso; cả message broker như Kafka và RabbitMQ HA queues; DRBD.

Synchronous vs Asynchronous Replication

• Synchronous: leader đợi follower xác nhận đã nhận write rồi mới báo thành công cho client.
  • ✅ Follower chắc chắn có bản mới nhất; leader chết thì dữ liệu vẫn còn.
  • ❌ Nếu follower sync không phản hồi (crash, lỗi mạng), leader phải block mọi write.
• Asynchronous: leader gửi rồi đi tiếp, không đợi.
  • ✅ Leader tiếp tục nhận write ngay cả khi mọi follower tụt lại.
  • ❌ Nếu leader chết không phục hồi được, các write chưa replicate bị mất — write đã confirm cho client vẫn không đảm bảo durable.

Bình thường lag < 1 giây, nhưng không có giới hạn trên: follower có thể tụt vài phút khi đang recover, hệ thống gần max capacity, hoặc mạng có vấn đề.

Cho mọi follower đều synchronous là phi thực tế — một node chết là cả hệ thống đứng. Thực tế dùng semi-synchronous: một follower sync, còn lại async; nếu follower sync chậm/chết thì đẩy một follower async lên làm sync → luôn có ít nhất 2 node có bản mới nhất.

Nhiều hệ thống cấu hình fully async — hi sinh durability đổi lấy khả năng tiếp tục ghi, đặc biệt khi có nhiều follower hoặc phân tán địa lý.

Setting Up New Followers

Copy file dữ liệu đơn thuần không đủ vì DB liên tục thay đổi; khoá DB thì mất availability. Quy trình không downtime: 1. Chụp consistent snapshot của leader (không lock toàn DB — cũng là tính năng cần cho backup; MySQL có thể cần innobackupex). 2. Copy snapshot sang follower mới. 3. Follower kết nối leader và xin mọi thay đổi kể từ vị trí chính xác của snapshot trong replication log (PostgreSQL: log sequence number; MySQL: binlog coordinates). 4. Xử lý xong backlog → follower đã caught up, tiếp tục nhận stream bình thường.

Handling Node Outages

Node có thể chết bất ngờ hoặc do bảo trì có kế hoạch (reboot vá kernel). Mục tiêu: reboot từng node mà không downtime.

Follower failure — catch-up recovery: follower giữ log các thay đổi đã nhận. Khi khởi động lại, nó biết transaction cuối cùng đã xử lý → xin leader phần thiếu → catch up. Đơn giản.

Leader failure — failover: phức tạp hơn nhiều. Phải promote một follower thành leader mới, cấu hình lại client gửi write tới leader mới, và các follower khác chuyển sang theo leader mới. Có thể làm manual hoặc tự động. Quy trình tự động: 1. Xác định leader đã chết: không có cách chắc chắn; thường dùng timeout (ví dụ 30 giây không phản hồi). 2. Chọn leader mới: qua bầu chọn (đa số replica) hoặc do một controller node chỉ định. Ứng viên tốt nhất là replica có dữ liệu mới nhất. Đây là bài toán consensus. 3. Reconfigure hệ thống: client gửi write tới leader mới; nếu leader cũ quay lại, phải buộc nó trở thành follower.

Những thứ có thể sai khi failover: - Mất write với async replication: leader mới có thể chưa nhận hết write của leader cũ. Khi leader cũ quay lại, cách phổ biến là bỏ luôn các write chưa replicate → vi phạm kỳ vọng durability. - Sự cố GitHub: một MySQL follower bị lag được promote thành leader. Counter autoincrement của nó tụt sau leader cũ nên tái sử dụng primary key đã cấp. Các key này cũng được dùng trong Redis → MySQL và Redis lệch nhau → một số dữ liệu private bị lộ cho sai người dùng. Bài học: bỏ write rất nguy hiểm khi có hệ thống bên ngoài phối hợp với DB. - Split brain: hai node cùng tin mình là leader, cùng nhận write → dữ liệu mất/hỏng. Cơ chế an toàn là tắt một node (fencing, hay STONITH — "Shoot The Other Node In The Head"), nhưng nếu thiết kế kém có thể tắt cả hai. - Chọn timeout: dài → recovery chậm; ngắn → failover không cần thiết (load spike, network glitch) và làm tình hình tệ hơn khi hệ thống đã đang quá tải.

Vì không có giải pháp dễ, nhiều đội vận hành chọn failover thủ công dù phần mềm hỗ trợ tự động.

Implementation of Replication Logs

Điểm quan trọng về WAL shipping: nếu protocol cho phép follower chạy version mới hơn leader, ta có thể zero-downtime upgrade — nâng cấp follower trước rồi failover. WAL shipping thường không cho phép điều này.

Statement-based vẫn còn dùng vì gọn; MySQL hiện tự chuyển sang row-based nếu câu lệnh có yếu tố nondeterministic. Logical log là nền tảng của change data capture (chương 11).

Problems with Replication Lag

Với workload đọc nhiều, ghi ít (phổ biến trên web), kiến trúc read-scaling rất hấp dẫn: thêm nhiều follower và chia read cho chúng. Nhưng chỉ khả thi với async — sync với tất cả sẽ cực kỳ kém tin cậy (càng nhiều node càng dễ có node chết).

Đọc từ follower async → có thể thấy dữ liệu cũ. Nếu ngừng ghi và đợi, followers sẽ bắt kịp → eventual consistency. Chữ "eventually" cố tình mơ hồ: không có giới hạn lag. Bình thường lag là phần nhỏ của giây; khi quá tải hoặc lỗi mạng có thể lên vài giây đến vài phút → thành vấn đề thật cho ứng dụng. (Lưu ý: không chỉ NoSQL mới eventual consistent — follower async của RDBMS cũng vậy.)

Ba bất thường điển hình:

Reading Your Own Writes

Tình huống: user gửi comment (ghi vào leader), reload trang ngay (đọc từ follower chưa có) → tưởng dữ liệu bị mất. Cần read-after-write consistency (read-your-writes): user luôn thấy update của chính mình; không hứa gì về update của người khác.

Kỹ thuật: - Đọc thứ user có thể đã sửa từ leader, còn lại từ follower. Ví dụ: profile của chính mình đọc từ leader, profile người khác từ follower. - Nếu hầu hết dữ liệu đều có thể bị user sửa → dùng tiêu chí khác: trong 1 phút sau lần update cuối thì đọc từ leader; hoặc theo dõi lag và không truy vấn follower lag quá 1 phút. - Client nhớ timestamp write gần nhất (logical timestamp như log sequence number, hoặc system clock — khi đó đồng bộ đồng hồ rất quan trọng); replica phục vụ phải cập nhật ít nhất tới timestamp đó, nếu không thì chuyển replica khác hoặc đợi. - Multi-datacenter: request cần leader phải route tới datacenter chứa leader.

Cross-device read-after-write (desktop + mobile): metadata timestamp phải được tập trung hoá vì thiết bị này không biết thiết bị kia đã ghi gì; và các thiết bị có thể route tới datacenter khác nhau (wifi nhà vs mạng di động) → có thể phải route mọi thiết bị của một user về cùng datacenter.

Monotonic Reads

Tình huống: user refresh, lần 1 đọc từ follower ít lag (thấy comment mới), lần 2 đọc từ follower lag nhiều (comment biến mất) → thời gian chạy lùi.

Monotonic reads: yếu hơn strong consistency, mạnh hơn eventual consistency. Không đảm bảo thấy giá trị mới nhất, chỉ đảm bảo không đọc dữ liệu cũ hơn cái đã thấy trước đó.

Cách làm: mỗi user luôn đọc từ cùng một replica, ví dụ chọn replica theo hash của user ID. Nếu replica đó chết thì phải reroute.

Consistent Prefix Reads

Tình huống (ví dụ Mr. Poons & Mrs. Cake): câu hỏi đi qua partition lag nhiều, câu trả lời đi qua partition lag ít → người quan sát thấy câu trả lời trước câu hỏi — vi phạm quan hệ nhân quả.

Consistent prefix reads: nếu các write xảy ra theo một thứ tự, ai đọc cũng thấy chúng theo đúng thứ tự đó.

Đây là vấn đề đặc thù của partitioned (sharded) DB: các partition hoạt động độc lập, không có thứ tự ghi toàn cục. Giải pháp: ghi các write có liên hệ nhân quả vào cùng partition (không phải lúc nào cũng hiệu quả), hoặc dùng thuật toán theo dõi causal dependencies (happens-before).

Solutions for Replication Lag

Câu hỏi thiết kế cần tự hỏi: nếu lag tăng lên vài phút, thậm chí vài giờ, ứng dụng sẽ ra sao? Nếu trải nghiệm tệ thì cần guarantee mạnh hơn. Giả vờ replication là synchronous trong khi thực tế async là công thức cho rắc rối.

Xử lý ở tầng application thì phức tạp và dễ sai → đó là lý do tồn tại transactions. Nhiều hệ phân tán bỏ transactions với lý do hiệu năng/availability và cho rằng eventual consistency là bất khả kháng — Kleppmann cho rằng quan điểm này quá đơn giản (sẽ bàn ở chương 7, 9).

Multi-Leader Replication

Nhược điểm lớn của single-leader: mọi write phải đi qua một leader; không kết nối được leader là không ghi được. Mở rộng tự nhiên: cho nhiều node nhận write → multi-leader (master–master, active/active). Mỗi leader đồng thời là follower của các leader khác.

Use Cases for Multi-Leader Replication

Hiếm khi đáng dùng trong một datacenter vì độ phức tạp vượt lợi ích. Các trường hợp hợp lý:

Multi-datacenter operation: mỗi datacenter có một leader; trong datacenter dùng leader–follower bình thường; giữa các datacenter, leader replicate cho nhau.

Công cụ: Tungsten Replicator (MySQL), BDR (PostgreSQL), GoldenGate (Oracle). Nhược điểm lớn: write conflicts. Ngoài ra multi-leader thường là tính năng "gắn thêm" nên tương tác xấu với autoincrement key, trigger, integrity constraint → thường được coi là vùng nguy hiểm nên tránh nếu có thể.

Clients with offline operation: ví dụ app lịch trên điện thoại/laptop — phải đọc và ghi được khi offline, sync khi online. Mỗi thiết bị là một leader với local DB; replication lag có thể hàng giờ, hàng ngày. Về kiến trúc, đây là multi-DC đẩy đến cực đoan: mỗi thiết bị là một "datacenter" với mạng cực kém tin cậy. Lịch sử đầy những bản calendar sync lỗi cho thấy việc này khó. CouchDB được thiết kế cho mô hình này.

Collaborative editing (Etherpad, Google Docs): thay đổi áp dụng ngay vào local replica (trình duyệt), replicate async. Nếu muốn không conflict thì lock document — tương đương single-leader. Muốn cộng tác nhanh (đơn vị thay đổi là một phím gõ, không lock) → đối mặt mọi thách thức của multi-leader, gồm conflict resolution.

Handling Write Conflicts

Ví dụ: wiki page, user 1 đổi title A→B, user 2 đổi A→C đồng thời trên hai leader khác nhau → conflict phát hiện khi replicate async.

Sync vs async conflict detection: single-leader thì write thứ hai bị block hoặc abort ngay. Multi-leader thì cả hai thành công, conflict chỉ phát hiện sau — lúc đó có thể quá muộn để hỏi user. Làm detection đồng bộ thì mất luôn lợi thế của multi-leader → vậy dùng single-leader cho rồi.

Conflict avoidance: chiến lược đơn giản và được khuyến nghị nhất — đảm bảo mọi write cho một record đi qua cùng một leader. Ví dụ: user luôn được route về "home datacenter" của mình → từ góc nhìn user, hệ thống là single-leader. Vỡ khi phải đổi leader (DC chết, user chuyển vùng).

Converging toward a consistent state: multi-leader không có thứ tự write xác định. Nếu mỗi replica áp dụng theo thứ tự nó nhận, leader 1 kết thúc với C, leader 2 với B — không chấp nhận được. Conflict resolution phải convergent: mọi replica cuối cùng về cùng giá trị. Các cách: - Gán ID duy nhất cho mỗi write (timestamp, UUID, hash…), chọn ID cao nhất thắng. Dùng timestamp gọi là last write wins (LWW) — phổ biến nhưng dễ mất dữ liệu. - Replica có ID cao hơn luôn thắng — cũng mất dữ liệu. - Merge giá trị (ví dụ nối theo alphabet → "B/C"). - Lưu conflict vào cấu trúc dữ liệu riêng giữ đủ thông tin, để code ứng dụng (hoặc hỏi user) giải quyết sau.

Custom conflict resolution logic: - On write: DB phát hiện conflict trong log thì gọi handler (Bucardo cho viết đoạn Perl). Chạy nền, phải nhanh, không hỏi user được. - On read: lưu mọi phiên bản xung đột; lần đọc sau trả hết về cho app để app/user giải quyết rồi ghi lại (CouchDB). - Lưu ý: resolution thường ở mức từng row/document, không phải cả transaction.

Automatic conflict resolution: logic tuỳ chỉnh dễ sai — ví dụ giỏ hàng Amazon từng giữ item được thêm nhưng không giữ thao tác xoá → item đã xoá lại xuất hiện. Hướng nghiên cứu: - CRDTs (Conflict-free replicated datatypes): set, map, list, counter tự merge hợp lý (Riak 2.0). - Mergeable persistent data structures: theo dõi lịch sử như Git, three-way merge. - Operational transformation: thuật toán sau Etherpad/Google Docs, cho danh sách có thứ tự (ký tự trong văn bản).

What is a conflict? Có loại hiển nhiên (hai write cùng field). Có loại tinh vi: hệ thống đặt phòng họp — hai booking chồng giờ cho cùng phòng tạo trên hai leader khác nhau là conflict, dù app có kiểm tra trước khi đặt.

Multi-Leader Replication Topologies

Replication topology = đường truyền write giữa các node. Với >2 leader: - All-to-all: mọi leader gửi cho mọi leader. Chịu lỗi tốt (nhiều đường đi) nhưng link nhanh chậm khác nhau → message có thể "vượt mặt" nhau. - Circular: mỗi node nhận từ một node và chuyển tiếp cho node kế (MySQL mặc định). - Star/tree: một root chuyển write cho mọi node khác.

Với circular/star, để tránh vòng lặp vô hạn, mỗi write được gắn ID của các node đã đi qua; node thấy ID của mình thì bỏ qua. Nhược điểm: một node chết có thể cắt dòng replication, reconfigure thường phải làm thủ công.

Vấn đề all-to-all: client A insert row ở leader 1, client B update row đó ở leader 3; leader 2 có thể nhận update trước insert → update một row chưa tồn tại. Đây là vấn đề causality giống consistent prefix reads. Gắn timestamp không đủ vì đồng hồ không đồng bộ tin cậy được; cần version vectors. Thực tế nhiều hệ thống làm kém: PostgreSQL BDR không đảm bảo causal ordering, Tungsten Replicator thậm chí không phát hiện conflict → phải đọc kỹ docs và test.

Leaderless Replication

Bỏ khái niệm leader, bất kỳ replica nào cũng nhận write trực tiếp. Trở lại thịnh hành sau Amazon Dynamo; Riak, Cassandra, Voldemort là các open source lấy cảm hứng → gọi là Dynamo-style. (Lưu ý: AWS DynamoDB dùng kiến trúc khác hẳn — single-leader.) Client gửi write tới nhiều replica, hoặc qua một coordinator — nhưng coordinator không áp đặt thứ tự ghi.

Writing to the Database When a Node Is Down

Với 3 replica, 1 node đang reboot: leaderless không có failover. Client gửi write song song tới cả 3; 2 node nhận OK là coi thành công. Khi node chết quay lại, nó thiếu dữ liệu → đọc từ nó ra stale value. Giải pháp: đọc cũng gửi song song tới nhiều node, dùng version number để chọn giá trị mới hơn.

Hai cơ chế catch-up: - Read repair: khi đọc thấy replica trả version cũ (ví dụ replica 3 trả version 6, replica 1–2 trả version 7), client ghi giá trị mới vào replica đó. Tốt cho dữ liệu được đọc thường xuyên. - Anti-entropy process: tiến trình nền liên tục so sánh và copy dữ liệu thiếu giữa replica; không theo thứ tự, có thể trễ đáng kể. - Không phải hệ nào cũng có cả hai (Voldemort không có anti-entropy) → dữ liệu hiếm khi đọc có thể thiếu trên một số replica, giảm durability.

Quorums for Reading and Writing

Với n replica, write cần w node xác nhận, read truy vấn ít nhất r node. Nếu w + r > n thì tập node ghi và tập node đọc phải giao nhau ít nhất một node → kỳ vọng đọc được giá trị mới nhất. Đây là quorum reads/writes (strict quorum).

• Cấu hình phổ biến: n lẻ (3 hoặc 5), w = r = (n+1)/2 (làm tròn lên).
• n=3, w=2, r=2 → chịu được 1 node chết.
• n=5, w=3, r=3 → chịu được 2 node chết.
• Đọc nhiều ghi ít: w = n, r = 1 → đọc nhanh, nhưng chỉ 1 node chết là mọi write fail.
• w < n thì vẫn ghi được khi có node chết; r < n thì vẫn đọc được.
• Thực tế request luôn gửi tới cả n node song song; w, r chỉ quyết định đợi bao nhiêu phản hồi.
• Cluster có thể có nhiều hơn n node; mỗi giá trị chỉ lưu trên n node (liên quan partitioning).
• Không đủ w/r node phản hồi → trả lỗi; không cần phân biệt loại lỗi (crash, disk đầy, mạng...).

Limitations of Quorum Consistency

Quorum không nhất thiết là đa số — chỉ cần tập đọc và ghi giao nhau. Có thể chọn w + r ≤ n: dễ đọc stale hơn nhưng latency thấp hơn, availability cao hơn.

Ngay cả khi w + r > n, vẫn có edge case trả giá trị cũ: - Dùng sloppy quorum → w node ghi và r node đọc có thể không giao nhau. - Hai write đồng thời: không rõ cái nào trước; nếu dùng LWW có thể mất write do clock skew. - Write đồng thời với read: write mới có ở một số replica → không xác định đọc ra cũ hay mới. - Write thành công ở một số replica nhưng tổng < w → báo fail nhưng không rollback trên replica đã ghi → read sau có thể thấy hoặc không thấy. - Node giữ giá trị mới chết, được restore từ replica có giá trị cũ → số replica có giá trị mới < w. - Các vấn đề timing (linearizability, chương 9).

→ Dynamo-style DB tối ưu cho use case chịu được eventual consistency. w, r điều chỉnh xác suất đọc stale, không phải đảm bảo tuyệt đối. Thường không có read-your-writes, monotonic reads, consistent prefix reads.

Monitoring staleness: với leader-based, đo lag dễ = vị trí log của leader − vị trí của follower. Với leaderless không có thứ tự ghi cố định → khó đo; nếu chỉ có read repair thì giá trị hiếm đọc có thể cũ tuỳ ý. Nên định lượng được "eventual".

Sloppy Quorums and Hinted Handoff

Leaderless hấp dẫn cho use case cần high availability, low latency, chịu được thỉnh thoảng đọc stale (không cần failover, không phải đợi node chậm).

Nhưng khi network interruption cắt client khỏi nhiều node, có thể không gom đủ w/r trong n "home nodes" của giá trị. Trong cluster lớn, client vẫn liên lạc được một số node khác. Trade-off: trả lỗi, hay nhận write vào các node không thuộc n? - Sloppy quorum: vẫn cần w/r phản hồi, nhưng có thể từ node ngoài n home nodes. (Ví von: quên chìa khoá, xin ngủ nhờ sofa hàng xóm.) - Hinted handoff: khi mạng phục hồi, node tạm giữ gửi write về đúng home node. (Tìm lại chìa khoá, hàng xóm mời về nhà.) - Tăng write availability (chỉ cần bất kỳ w node), nhưng ngay cả w + r > n cũng không chắc đọc được giá trị mới nhất cho tới khi handoff xong → sloppy quorum thực chất chỉ là đảm bảo durability (dữ liệu nằm trên w node ở đâu đó), không phải quorum truyền thống. - Riak: bật mặc định; Cassandra, Voldemort: tắt mặc định.

Multi-datacenter: leaderless cũng phù hợp multi-DC. - Cassandra/Voldemort: n tính cả node ở mọi DC, cấu hình số replica mỗi DC; write gửi tới mọi replica nhưng client thường chỉ đợi quorum ở DC local; ghi sang DC khác async. - Riak: giao tiếp client–node nằm trong một DC, n là số replica trong một DC; replication liên DC chạy nền kiểu multi-leader.

Detecting Concurrent Writes

Dynamo-style cho phép nhiều client ghi cùng key đồng thời → conflict ngay cả với strict quorum (và cả khi read repair / hinted handoff). Ví dụ: client A và B cùng ghi key X; node 1 chỉ nhận A, node 2 nhận A rồi B, node 3 nhận B rồi A → nếu mỗi node chỉ ghi đè thì vĩnh viễn không nhất quán (node 2 = B, node khác = A). Phần lớn implementation xử lý kém → dev phải hiểu nội bộ conflict handling của DB.

Last Write Wins (LWW)

Mỗi replica chỉ giữ giá trị "mới nhất", ghi đè cái "cũ hơn". Nhưng với write concurrent, không có "trước/sau" thật sự. LWW áp đặt thứ tự tuỳ ý bằng timestamp: lớn nhất thắng. - Là phương pháp duy nhất trong Cassandra, tuỳ chọn trong Riak. - Đạt convergence nhưng hi sinh durability: nhiều write đều báo thành công (đủ w) nhưng chỉ một cái sống sót, còn lại bị âm thầm bỏ. Thậm chí có thể bỏ write không concurrent (do clock). - Chấp nhận được cho caching; không chấp nhận khi mất dữ liệu là không được. - Cách an toàn duy nhất: mỗi key chỉ ghi một lần, coi là immutable — ví dụ Cassandra khuyến nghị dùng UUID làm key.

Happens-before và concurrency

• A happens before B nếu B biết về A, phụ thuộc A, hoặc xây trên A (ví dụ: insert rồi increment chính row đó → B causally dependent on A).
• Hai thao tác concurrent nếu không cái nào happens-before cái kia — tức không biết về nhau, bất kể thời gian vật lý có chồng lấn hay không.
• Ba khả năng: A→B, B→A, hoặc concurrent. Nếu có happens-before thì cái sau ghi đè cái trước; nếu concurrent thì có conflict cần giải quyết.
• Liên hệ với thuyết tương đối: hai sự kiện không thể ảnh hưởng nhau nếu thông tin chưa kịp truyền. Trong hệ thống máy tính, hai thao tác cách nhau một khoảng vẫn có thể concurrent nếu mạng chậm/gián đoạn.

Capturing the happens-before relationship

Ví dụ giỏ hàng với một replica, hai client: 1. Client 1 thêm milk → version 1. 2. Client 2 thêm eggs (không biết milk) → server giữ cả [milk] và [eggs] như hai giá trị riêng, version 2. 3. Client 1 gửi [milk, flour] kèm version 1 → ghi đè [milk], nhưng concurrent với [eggs] → version 3, còn [milk, flour] và [eggs]. 4. Client 2 merge [milk] + [eggs] + ham → gửi [eggs, milk, ham] kèm version 2 → ghi đè [eggs], concurrent với [milk, flour] → version 4. 5. Client 1 gửi [milk, flour, eggs, bacon] kèm version 3 → ghi đè [milk, flour], còn giữ [eggs, milk, ham].

Thuật toán: - Server giữ version number cho mỗi key, tăng mỗi lần ghi. - Khi đọc: server trả mọi giá trị chưa bị ghi đè + version mới nhất. Client phải đọc trước khi ghi. - Khi ghi: client gửi kèm version từ lần đọc trước và phải merge mọi giá trị đã nhận. - Server nhận write với version v: ghi đè mọi giá trị có version ≤ v, giữ các giá trị có version > v (vì concurrent). - Write không kèm version → concurrent với mọi write khác, không ghi đè gì.

Server không cần hiểu nội dung giá trị — chỉ nhìn version number.

Merging concurrently written values

Không mất dữ liệu, nhưng client phải merge các giá trị concurrent — Riak gọi là siblings. Giỏ hàng: lấy union → [milk, flour, eggs, bacon, ham]. Nhưng nếu cho xoá item, union sẽ làm item đã xoá xuất hiện lại → cần đánh dấu xoá bằng tombstone kèm version. Merge thủ công dễ sai → dùng CRDTs (Riak datatypes) để tự merge hợp lý, kể cả deletion.

Version vectors

Với nhiều replica không leader, một version number là không đủ → cần version number cho mỗi replica, cho mỗi key. Mỗi replica tăng version của mình khi xử lý write và theo dõi version đã thấy từ replica khác. Tập hợp này gọi là version vector. Biến thể đáng chú ý: dotted version vector (Riak 2.0). Version vector được gửi cho client khi đọc và gửi lại khi ghi (Riak gọi là causal context) → DB phân biệt được ghi đè vs concurrent write. Cho phép an toàn đọc từ replica này rồi ghi sang replica khác (có thể tạo siblings, nhưng không mất dữ liệu nếu merge đúng).

Version vector vs vector clock: hay bị gọi lẫn nhưng khác nhau tinh tế; khi so sánh trạng thái giữa các replica, version vector là cấu trúc đúng.

Tổng kết: So sánh ba mô hình

Bốn mục đích của replication: high availability, disconnected operation, latency, scalability.

⚠️ Hiểu lầm & cạm bẫy thường gặp

• "Write đã confirm là không mất" — sai với async replication: leader chết trước khi replicate thì write mất.
• "Eventual consistency là chuyện của NoSQL" — follower async của PostgreSQL/MySQL cũng eventual consistent.
• "Replication lag luôn nhỏ" — bình thường < 1s, nhưng không có giới hạn trên; khi quá tải có thể vài phút.
• Tin automatic failover tuyệt đối: timeout sai gây failover thừa, split brain, mất write, lệch ID với hệ bên ngoài (sự cố GitHub).
• Statement-based replication với NOW()/RAND()/autoincrement → replica khác nhau.
• Nghĩ w + r > n là strong consistency — vẫn có nhiều edge case (sloppy quorum, concurrent write, write fail không rollback, restore từ replica cũ).
• Sloppy quorum không phải quorum — chỉ đảm bảo durability, không đảm bảo đọc được giá trị mới.
• LWW "an toàn vì có timestamp" — thực tế âm thầm bỏ write đã báo thành công; clock skew còn làm mất write không concurrent.
• Concurrent = cùng thời điểm — sai; concurrent là không biết về nhau.
• Union siblings khi có thao tác xoá → item "hồi sinh" (giỏ hàng Amazon); cần tombstone.
• Dùng multi-leader trong một datacenter — hầu như không đáng với độ phức tạp.
• Nhầm DynamoDB với Dynamo — DynamoDB là single-leader.
• Dùng timestamp để sắp thứ tự write trong multi-leader — đồng hồ không đủ tin cậy; cần version vectors.

💼 Áp dụng thực tế & phỏng vấn

• Read replicas (RDS/Aurora, MySQL/Postgres replica) là mẫu read-scaling kinh điển. Phỏng vấn thường hỏi: "user vừa update profile nhưng reload không thấy" → trả lời bằng read-after-write (đọc từ leader cho dữ liệu của chính user, hoặc trong N giây sau khi ghi; dùng LSN/GTID để chờ replica catch up).
• Monotonic reads → sticky routing theo hash user ID / session.
• Thiết kế multi-region: chọn giữa single-leader (write latency cao, dễ reasoning) và multi-leader/leaderless (write local, phải xử lý conflict). Chiến lược thực dụng: conflict avoidance — mỗi user có "home region".
• Cassandra/DynamoDB-style: biết giải thích n/w/r, consistency level (ONE, QUORUM, LOCAL_QUORUM, ALL), trade-off latency vs staleness; LWW nên dùng key immutable/UUID.
• Offline-first app / collaborative editing (Notion, Figma, Google Docs): nhắc tới CRDTs và Operational Transformation.
• Failover: nói về heartbeat timeout, fencing/STONITH, epoch/term number để tránh split brain, và rủi ro mất write khi promote replica async. Tham chiếu sự cố GitHub.
• Change data capture (Debezium đọc MySQL binlog/Postgres logical decoding) dựa trên logical log — hay dùng để sync DB sang search index, cache, data warehouse.
• Zero-downtime upgrade: nâng follower trước rồi failover — cần replication protocol hỗ trợ khác version (logical log).
• Monitoring: luôn có metric replication lag và alert.

❓ Câu hỏi ôn tập