Distributed Systems Concepts

drafted

CAP/PACELC, consistency models, consensus (Raft), idempotency, retries/backoff/jitter, timeouts, circuit breaker, bulkhead, 2PC vs saga, distributed locks & fencing, clocks, consistent hashing.

0/45 rated · mastery 0%

Practice this track Random câu hỏi Jump to questions (45)

Bài học

11 bài · ~156 phút đọc. Học theo thứ tự, rồi làm câu hỏi.

01~16 phút· 4 câuverify
Mô hình lỗi: mạng, đồng hồ và process pause
Tám fallacies of distributed computing, partial failure, bài toán Two Generals, mô hình synchronous/asynchronous/partial synchrony, failure detector bằng heartbeat (fixed timeout vs phi accrual), delivery semantics, và cách test một hệ phân tán dưới lỗi bằng fault injection — tái hiện bằng Toxiproxy 2.12 và một simulation Node 24.
02~14 phút· 4 câuverify
CAP và PACELC: phát biểu chính xác
CAP đúng nghĩa (linearizability và availability khi có network partition), vì sao 'chọn 2 trong 3' và 'hệ CA' là sai, PACELC và cái giá latency khi mạng khoẻ, phân loại các hệ thật kèm sắc thái, và cách vạch ranh giới strong/eventual cho một sàn e-commerce — đo trên PostgreSQL 17 primary + replica với Toxiproxy cắt mạng.
03~12 phút· 4 câuverify
Consistency models: từ linearizable tới eventual
Thang consistency models (linearizable, sequential, causal, session guarantees như read-your-writes và monotonic reads, eventual), cách kiểm một history có linearizable không, và cách đạt read-your-writes khi đọc từ async replica: đọc primary sau khi ghi, LSN token, sticky routing — đo trên PostgreSQL 17 với hai replica lag khác nhau.
04~14 phút· 4 câuverify
Replication, quorum và consistent hashing
Single-leader, multi-leader và leaderless replication; quorum N/R/W và vì sao R + W > N chưa phải linearizable (partial write, sloppy quorum, read repair); mất write khi failover async như Redis Sentinel và cách giới hạn bằng min-replicas-to-write; chia dữ liệu bằng hash % N, consistent hashing, virtual nodes và hash slot — đo bằng simulation Node 24 và Redis 8.10.
05~15 phút· 4 câuverify
Đồng hồ, thứ tự sự kiện và xung đột
Wall clock vs monotonic clock, NTP và clock skew (đo thật trên máy dev), quan hệ happens-before, Lamport clock và vector clock, Hybrid Logical Clock và TrueTime, vì sao last-write-wins theo timestamp âm thầm làm mất edit, và CRDT (G-Counter, PN-Counter, OR-Set) cùng giới hạn của chúng — mỗi phần có simulation Node 24 chạy thật.
06~15 phút· 4 câuverify
Consensus và Raft
Consensus giải bài toán gì, kết quả FLP và vì sao Raft/Paxos vẫn chạy được (safety luôn đúng, liveness nhờ partial synchrony), Raft từng bước: term, leader election, log replication, commit rule, election restriction; split brain, quorum và vì sao cluster dùng số node lẻ — chạy etcd 3.6.5 ba node thật, cô lập leader, đọc log bầu cử và thử ghi ở phía thiểu số.
07~12 phút· 5 câuverify
Leader election, lease, lock và fencing token
Lock phân tán thực chất là lease có hạn; vì sao leader bị GC pause tỉnh dậy vẫn tưởng mình là leader; fencing token được storage kiểm tra; các cách bầu leader trong thực tế (Kubernetes Lease, etcd, lease trong DB); sửa job Redis lease xử lý trùng batch; và thiết kế job chạy đúng một lần mỗi phút trên 10 replica — tái hiện bằng Redis 8.10 và PostgreSQL 17.
08~13 phút· 5 câuverify
Idempotency và exactly-once
Idempotent theo HTTP semantics, vì sao mọi retry an toàn đều dựa trên idempotency, thiết kế Idempotency-Key với unique constraint (request hash, trạng thái in_progress/done, khoá có hạn, scope theo tenant, TTL), at-least-once + dedupe = exactly-once processing, sự cố trừ tiền hai lần, và payment API có trạng thái UNKNOWN + reconciliation — chạy thật với hai pod Node 24 dùng chung PostgreSQL 17 và một payment provider giả lập.
09~14 phút· 7 câuverify
Timeout, deadline, retry, backoff và jitter
Vì sao mọi network call cần timeout và chọn giá trị thế nào, deadline propagation qua nhiều hop trong Node, retry chỉ cho lỗi transient và thao tác idempotent, exponential backoff + full jitter, retry budget, retry lồng nhiều tầng, retry storm sau outage (metastable failure) và hedged requests — đo bằng ba service Node 24 thật và các simulation deterministic.
10~14 phút· 6 câuverify
Circuit breaker, bulkhead, backpressure và load shedding
Cascading failure qua tài nguyên dùng chung (connection pool), bulkhead trong Node bằng pool riêng và giới hạn concurrency, ba trạng thái circuit breaker và vì sao granularity sai làm một endpoint phụ tắt cả dependency, backpressure vs load shedding, và rate limiter phân tán bằng Redis Lua cùng hành vi fail-open khi store lỗi — đo thật trên Node 24, PostgreSQL 17 và Redis 8.10.
11~15 phút· 4 câuverify
2PC, saga và compensation
Vì sao một transaction không thể trải qua nhiều service như trong một database, two-phase commit hoạt động ra sao và vì sao nó blocking (tái hiện bằng PREPARE TRANSACTION trên hai PostgreSQL 17), saga choreography vs orchestration, thiết kế compensation và pivot transaction, xử lý compensation thất bại, saga bị kẹt, và outbox — kèm một orchestrator lưu trạng thái trong Postgres chạy thật.

Tóm tắt & cheat sheet của track

TL;DR

Hệ phân tán = nhiều máy giao tiếp qua mạng không tin cậy, không có đồng hồ chung, và có thể pause bất kỳ lúc nào. Mọi pattern trong track này là cách sống chung với 3 sự thật đó.
CAP chỉ nói về lúc có network partition: chọn Consistency (từ chối) hay Availability (trả lời có thể sai). PACELC bổ sung: khi không partition, vẫn phải đổi Latency lấy Consistency.
Resilience cơ bản: timeout ở mọi network call, retry có backoff + jitter chỉ cho thao tác idempotent, circuit breaker, bulkhead, load shedding.
Transaction xuyên service: tránh 2PC (blocking, coupling) → saga với compensating actions + outbox.
Lock phân tán cần lease + fencing token; consensus (Raft) cho leader election và metadata; consistent hashing để chia dữ liệu mà ít phải di chuyển khi đổi số node.

Khái niệm cốt lõi

Khái niệm	Một câu	Ví dụ ngắn
Network partition	Một nhóm node không nói chuyện được với nhóm khác	AZ-a mất kết nối AZ-b
Linearizability	Mọi thao tác như xảy ra tức thời tại một điểm, theo thời gian thực	Đọc sau khi write được ack luôn thấy giá trị mới
Eventual consistency	Không có write mới thì cuối cùng mọi replica hội tụ	DNS, read replica
Read-your-writes	Một client luôn thấy write của chính mình	Sửa profile xong reload thấy ngay
Quorum	R + W > N ⇒ tập đọc và tập ghi giao nhau	N=3, W=2, R=2
Idempotency	Thực hiện nhiều lần = một lần	`PUT /users/1`, `Idempotency-Key` cho POST
Circuit breaker	Ngừng gọi dependency đang hỏng một thời gian	Closed → Open → Half-open
Bulkhead	Chia tài nguyên riêng cho từng dependency	Pool 20 connection cho payment, 10 cho search
Saga	Chuỗi local transaction + compensation	Reserve stock → charge → (fail) → release stock
Fencing token	Số tăng đơn điệu kèm lock; storage từ chối token cũ	Lock #34 bị từ chối sau khi #35 đã ghi
Lamport clock	Counter logic cho thứ tự happens-before	`max(local, received) + 1`
Consistent hashing	Hash node và key lên vòng; thêm node chỉ chuyển ~1/N key	Vnodes cân bằng tải

Cơ chế hoạt động

Retry an toàn

Saga orchestration (happy path + compensation)

Raft (tóm tắt)

Mỗi node là follower/candidate/leader; thời gian chia thành term. Follower hết election timeout (ngẫu nhiên) mà không nghe heartbeat → thành candidate, tăng term, xin vote; đạt đa số → leader.
Leader nhận lệnh, append vào log, replicate; entry được commit khi đa số đã ghi. Chỉ node có log đủ mới nhất mới được bầu (election restriction).
Cluster 2f+1 node chịu được f node lỗi (3 → 1, 5 → 2).

Trade-offs

Lựa chọn	Được	Mất	Khi nào
CP (từ chối khi partition)	Không bao giờ trả dữ liệu sai	Availability khi partition	Tiền, tồn kho, lock, metadata
AP (trả lời khi partition)	Luôn phản hồi	Có thể stale/xung đột → cần merge	Giỏ hàng, feed, counter
2PC	Atomic xuyên resource	Blocking khi coordinator chết, latency, coupling	Trong một hệ DB/XA có kiểm soát
Saga choreography	Loose coupling, không điểm trung tâm	Khó theo dõi flow, dễ vòng event	Ít bước, ít team
Saga orchestration	Flow tường minh, dễ timeout/retry/observe	Orchestrator là thành phần thêm	Nhiều bước, long-running
Retry	Vượt lỗi tạm thời	Khuếch đại tải (retry storm), trùng	Chỉ với idempotent + backoff + budget

Pitfalls

Retry ở mọi tầng (client, gateway, service, SDK) → một request thành 3×3×3 = 27 request khi downstream chậm.
Timeout của caller ngắn hơn tổng timeout+retry của callee → callee vẫn làm việc cho request đã bị bỏ.
Retry POST không có idempotency key → trừ tiền hai lần.
Dùng wall clock (Date.now()) để sắp thứ tự sự kiện giữa các máy hoặc đo khoảng thời gian (dùng monotonic clock: performance.now(), process.hrtime.bigint()).
Tin rằng lock có TTL đảm bảo mutual exclusion khi process có thể bị GC pause.
Circuit breaker dùng chung cho mọi endpoint của một dependency → một endpoint hỏng làm "tắt" cả dependency.
Nói "chúng tôi chọn CA" — không có lựa chọn bỏ P trong hệ phân tán thật.

Cheat sheet

CAP: khi partition, chọn C hoặc A. PACELC: Else → Latency vs Consistency.
Quorum: R + W > N; N=3, W=2, R=2 phổ biến; quorum ≠ linearizable tuyệt đối (sloppy quorum, clock).
Retry: max 2–3 lần, exponential backoff + full jitter, retry budget (vd ≤ 10% traffic), chỉ lỗi transient, tôn trọng Retry-After.
Timeout: đặt theo p99.9 của dependency, deadline propagation qua các hop.
Circuit breaker: failure-rate threshold trên sliding window + minimum calls, open → half-open probe.
Idempotency key: client sinh UUID; server lưu (key → response) với unique constraint; so sánh payload hash.
Lock đúng: lease (TTL) + fencing token kiểm tra ở storage; consensus store (etcd/ZooKeeper) cho correctness.
Clocks: wall clock có thể nhảy lùi; monotonic cho duration; Lamport/vector clock cho thứ tự nhân quả; LWW theo timestamp = mất write.

References

Personal notes (Notion)

Ghi chú cá nhân — có thể sai hoặc lỗi thời, dùng để tham khảo.

Principles and Theorems ↗

Interview Questions

Showing 45 / 45

const delay = (attempt: number, base = 100, cap = 5_000) =>
  Math.random() * Math.min(cap, base * 2 ** attempt); // full jitter

import pLimit from "p-limit";
const reportsLimit = pLimit(5);   // slow reporting API
const paymentsLimit = pLimit(50); // critical path
const getReport = (id: string) => reportsLimit(() => reportsClient.get(id));

const remaining = Math.floor(Number(req.header("x-deadline")) - Date.now()); // ms, epoch-based header
if (remaining < 50) return res.status(504).end();
const r = await fetch(url, { signal: AbortSignal.timeout(remaining - 20),
  headers: { "x-deadline": req.header("x-deadline")! } });

UPDATE jobs SET result = $1, fence = $2
WHERE id = $3 AND fence < $2;  -- 0 rows => stale lock holder

async function withRetry<T>(fn: () => Promise<T>, retries = 5): Promise<T> {
  try {
    return await fn();
  } catch (e) {
    if (retries === 0) throw e;
    await sleep(1000);
    return withRetry(fn, retries - 1);
  }
}
// usage
await withRetry(() => http.post("/payments", body));
await withRetry(() => http.get(`/inventory/${sku}`));

Gateway -> A : timeout 3s
A -> B       : timeout 5s, retries 2
B -> C       : timeout 10s, retries 3
C -> DB      : statement_timeout none

async function tick() {
  const ok = await redis.set("lease:batch", podId, "PX", 10_000, "NX");
  if (!ok) return;
  const batch = await db.claimNextBatch();       // ~100ms
  for (const item of batch) await processItem(item); // usually 2s, sometimes 20s (GC, slow API)
  await redis.del("lease:batch");
}
setInterval(tick, 1000);

INSERT INTO job_runs (job_name, slot) VALUES ('sync-prices', date_trunc('minute', now()))
ON CONFLICT (job_name, slot) DO NOTHING
RETURNING slot; -- a row back => this replica runs the job