Distributed Systems: Interview và Big Picture

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

Q: Raft đảm bảo safety như thế nào khi leader crash?

Raft dùng Election Restriction: candidate chỉ được vote nếu log của nó "at least as up-to-date" như voter. So sánh: lastLogTerm cao hơn thắng; nếu bằng thì lastLogIndex dài hơn thắng. Vì committed entry phải được majority accept, và new leader phải nhận votes từ majority → overlap ít nhất 1 node có entry đó → new leader chắc chắn có tất cả committed entries. Uncommitted entries có thể bị overwrite bởi leader mới.

Q: Lamport Clock và Vector Clock khác nhau như thế nào? Khi nào dùng gì?

Lamport Clock: single integer, O(1) space. Property: a→b ⟹ L(a)<L(b) nhưng ngược lại không đúng. Dùng cho total ordering events khi không cần detect concurrency. Vector Clock: array of N integers (N=số processes), O(N) space. Property: a→b ⟺ V(a)<V(b). Có thể detect concurrent events. Dùng khi cần conflict detection (Dynamo, Git merge). Trade-off: Lamport nhỏ gọn hơn nhưng kém expressive; Vector Clock chính xác hơn nhưng size tăng theo cluster size → trong large-scale systems dùng Version Vectors hoặc HLC thay thế.

Q: Tại sao Raft có thể có stale reads từ leader?

Raft chỉ đảm bảo linearizability nếu leader confirm mình vẫn là leader trước khi serve read. Nếu network partition tách leader khỏi majority → old leader vẫn think it's leader → serve stale reads. Giải pháp: ReadIndex (leader hỏi majority về current commitIndex trước khi read) hoặc Lease-based reads (leader giữ lease từ majority, đảm bảo không có new leader trong lease period → safe to read locally). etcd, CockroachDB implement một trong hai approaches này.

Q: Distributed lock với Redis Redlock có đảm bảo mutual exclusion tuyệt đối không?

Không. Redlock không đảm bảo tuyệt đối vì: (1) GC pause dài hơn TTL → lock expire trong khi holder vẫn active; (2) clock jump trên Redis nodes → TTL expire sớm hơn. Redlock phù hợp cho efficiency (tránh duplicate work, occasional overlap OK). Cho correctness (zero tolerance cho overlap): dùng ZooKeeper/etcd với fencing token — resource server reject operations với token nhỏ hơn last-seen token, đảm bảo mutual exclusion kể cả khi lock expire sớm.

Q: FLP Impossibility ảnh hưởng như thế nào đến Raft/Paxos?

FLP nói: không có deterministic algorithm nào đảm bảo terminate trong fully asynchronous system với 1 failure. Raft/Paxos không vi phạm FLP vì: (1) Randomized timeout (Raft): với probability 1, eventually một candidate wins election; không guaranteed terminate trong finite steps nhưng probabilistically terminates. (2) Partial synchrony assumption: real network có upper bounds trên latency (không fully async). Practical implication: Raft/Paxos có thể livelock (dueling candidates, network partition) nhưng trong practice converges nhanh. Safety (correctness) không bao giờ vi phạm; Liveness (progress) là probabilistic.

Q: Vector Clock size là O(N) — vấn đề với large clusters?

Trong cluster 1000 nodes, mỗi message mang vector clock 1000 integers (~8KB). Giải pháp: (1) Version Vectors: chỉ track nodes thực sự modify data, không phải tất cả nodes; (2) Dotted Version Vectors: thêm "dot" để eliminate false concurrency, dùng trong Riak; (3) HLC (Hybrid Logical Clocks): single (physical_time, counter) tuple — O(1) size, capture causality, correlate với physical time. CockroachDB, YugabyteDB dùng HLC vì scale tốt hơn vector clocks trong large distributed DB.

Q: Tại sao Kafka không dùng Raft từ đầu mà dùng ZooKeeper?

Kafka được thiết kế trước khi Raft paper (2014). ZooKeeper (2010, dùng Zab protocol) là consensus system phổ biến nhất lúc đó. Vấn đề với ZooKeeper dependency: separate system cần manage, bottleneck cho metadata, controller phải sync qua ZooKeeper (latency). KRaft mode (Kafka 3.x, fully production 3.3+): Kafka tự implement Raft internally, loại bỏ ZooKeeper dependency. Benefits: simpler operations, faster failover, scale đến millions of partitions (ZooKeeper bottleneck ở ~200k partitions).

🗺️ Bức tranh tổng thể

Distributed Systems Challenges
         │
         ├── Fundamental Problems
         │      ├── Partial Failures (cannot distinguish crash vs slow)
         │      ├── Unreliable Timing (no global clock)
         │      └── FLP Impossibility (no perfect consensus in async system)
         │
         ├── Ordering Events
         │      ├── Lamport Clock     → total order, O(1), no concurrency detect
         │      ├── Vector Clock      → causal order, O(N), detect concurrent
         │      └── HLC               → causal + physical time, O(1)
         │
         ├── Consensus
         │      ├── Paxos → correct but hard to implement fully
         │      └── Raft  → correct + understandable
         │             ├── Leader Election (randomized timeout)
         │             ├── Log Replication (AppendEntries)
         │             ├── Safety (Election Restriction)
         │             └── Membership Change (joint consensus)
         │
         ├── Coordination Primitives
         │      ├── Leader Election (Bully, Ring, ZooKeeper sequential nodes)
         │      └── Distributed Locks
         │             ├── Redis Redlock  → efficiency, not correctness
         │             ├── etcd/ZooKeeper → correctness + fencing token
         │             └── Fencing Token  → TRUE mutual exclusion
         │
         ├── Reliability
         │      ├── Delivery Semantics: At-most / At-least / Exactly-once
         │      ├── Idempotency: Idempotency Key, conditional updates
         │      └── Exactly-once: idempotent producer + transactional consumer
         │
         └── Membership & Discovery
                └── Gossip Protocol → scalable, eventual, O(log N) convergence

Tài liệu dành cho Senior / Staff Distributed Systems Engineer Interview Preparation Covers: Consensus · Paxos · Raft · Leader Election · Distributed Locks · Lamport · Vector Clocks · HLC · Idempotency · Exactly-Once · Gossip