[Big-tech interview] Ôn tập key-value kèm các kiến trúc resolution khi inconsistency khi interview

1. 📖 Dàn Ý (Outline)

• Bản Chất Vấn Đề: Khái niệm Key-Value Store, định lý CAP.
• Kiến Trúc & Hoạt Động: Data Partition, Replication, Quorum Consensus, Inconsistency Resolution (Vector Clock).
• Failure Handling: Gossip Protocol, Sloppy Quorum, Merkle Tree.
• Luồng Dữ Liệu: Write-path & Read-path, Compaction.
• Phân Tích Thực Chiến (STAR): Bài toán Shopping Cart (Giỏ hàng).
• Ưu Nhược Điểm & So Sánh: Khi nào nên dùng, các công nghệ thay thế.
• Câu Hỏi Phỏng Vấn (FAQ).

2. 🧠 Bản Chất Vấn Đề (What & Why)

• What (Nó là gì?): Key-Value (KV) Store là một dạng cơ sở dữ liệu phi quan hệ (NoSQL). Nó lưu trữ dữ liệu dưới dạng các cặp key-value, trong đó mỗi key là định danh duy nhất (có thể là plain text hoặc chuỗi hash) trỏ đến một value (có thể là string, JSON, binary data). Trực quan nhất, hãy tưởng tượng nó như một cấu trúc HashMap hay cuốn từ điển siêu lớn.
• Why (Tại sao cần nó?): Các cơ sở dữ liệu quan hệ (RDBMS) thường gặp nút thắt cổ chai khi phải scale out lên hàng triệu requests với latency cực thấp. KV Store ra đời để cung cấp khả năng đọc/ghi với độ phức tạp O(1) trong bộ nhớ (in-memory) hoặc trên đĩa, khả năng tự động Scale ngang (Horizontal Scaling) linh hoạt, và phù hợp với các cấu trúc dữ liệu linh động (không cần schema).

3. ⚙️ Kiến Trúc & Cách Hoạt Động (How it works)

Một KV Store phân tán (như Dynamo, Cassandra) thường dùng kiến trúc Decentralized (Phi tập trung) - mọi node đều bình đẳng (leaderless).

3.1. Các thành phần cốt lõi:

1. Data Partition (Phân mảnh dữ liệu): Sử dụng Consistent Hashing (Băm nhất quán) để chia đều keys lên một vòng Hash Ring. Giúp tự động scale-in/out mà chỉ phải di chuyển một lượng dữ liệu nhỏ nhất.
2. Data Replication (Nhân bản dữ liệu): Để đạt High Availability, dữ liệu được nhân bản ra N server khác nhau (ví dụ $N=3$). Từ vị trí của key trên Hash Ring, hệ thống sẽ chọn $N$ server đầu tiên đi theo chiều kim đồng hồ để lưu copy dữ liệu.
3. Consistency (Tính nhất quán) - Quorum Consensus: Kiểm soát sự nhất quán thông qua thông số $N, W, R$:
   • $N$: Số lượng replicas.
   • $W$: Số lượng ACK cần thiết cho một lệnh Ghi (Write) thành công.
   • $R$: Số lượng ACK cần thiết cho một lệnh Đọc (Read) thành công.
   • Nếu $W + R > N$: Hệ thống đạt Strong Consistency (Nhất quán mạnh).
   • Nếu $W + R \le N$: Hệ thống có Eventual Consistency (Nhất quán cuối). Tối ưu cho tốc độ.
4. Inconsistency Resolution (Xử lý xung đột): Vì Eventual Consistency, 2 client có thể ghi đè lên cùng 1 key, tạo ra conflict.
   • Last-write wins (LWW): Request nào đến sau sẽ thắng (dùng Timestamp). Dễ mất data.
   • Vector Clock: Gắn cặp [Server, Version] vào mỗi bản ghi để theo dõi quan hệ nhân quả. Khi client đọc ra nhiều phiên bản xung đột, client phải gom (reconcile) lại rồi ghi đè version mới nhất xuống server.

3.2. Xử lý Lỗi (Handling Failures):

• Phát hiện node chết: Dùng Gossip Protocol (mỗi node đếm heartbeat, gửi thông tin ngẫu nhiên cho nhau). Nếu heartbeat của 1 node không tăng sau thời gian dài -> Node chết.
• Chết tạm thời (Temporary Failure): Áp dụng Sloppy Quorum (Bỏ qua node hỏng, mượn tạm node khỏe khác trên Ring để lưu) và Hinted Handoff (Khi node hỏng sống lại, các node giữ hộ sẽ trả lại dữ liệu).
• Chết vĩnh viễn (Permanent Failure): Dùng cơ chế Anti-entropy để đối chiếu và đồng bộ replicas. Để làm điều này hiệu quả, hệ thống dùng Merkle Tree (Cây Băm) giúp nhanh chóng tìm ra đoạn data bị lệch mà không cần gửi toàn bộ dữ liệu qua mạng.

3.3. Nhiệm vụ của từng Node (Read & Write Path):

• Write Path (Luồng ghi):
  1. Ghi request vào Commit Log (trên đĩa) để đảm bảo không mất data nếu sập.
  2. Ghi dữ liệu vào Memory Cache (MemTable).
  3. Khi Cache đầy, flush xuống đĩa và tạo thành một file SSTable (Sorted String Table).
• Read Path (Luồng đọc):
  1. Tìm trong Memory Cache. Nếu có -> Trả về ngay.
  2. Nếu không có (Cache miss), check qua Bloom Filter (giải thuật xác suất để biết key chắc chắn có trong disk hay không, giúp tránh check ổ cứng vô ích).
  3. Tìm trong SSTable tương ứng và trả về.
• Compaction: Theo thời gian, SSTables sẽ sinh ra nhiều file nhỏ và các file chứa bản ghi cũ/bị xóa (tombstone). Quá trình Compaction chạy ngầm để gộp các SSTables lại, xóa data thừa, giúp tiết kiệm dung lượng đĩa và tăng tốc độ đọc.

4. 🌟 Phân Tích Thực Chiến (Áp dụng STAR Method)

Mô phỏng bài toán: Thiết kế hệ thống Giỏ hàng (Shopping Cart) cho sàn thương mại điện tử vào ngày Flash Sale.

• S - Situation (Tình huống): Hệ thống có DAU lên tới hàng chục triệu người. Trong sự kiện Flash Sale, lưu lượng thêm đồ vào giỏ hàng tăng vọt. Cơ sở dữ liệu RDBMS hiện tại liên tục bị lock-table khi thao tác ghi (write) diễn ra quá dồn dập, dẫn đến Timeout.
• T - Task (Nhiệm vụ): Thiết kế lại hạ tầng lưu trữ giỏ hàng, đảm bảo High Availability (Hệ thống không được sập, không bao giờ chặn request thêm hàng của user), Low Latency (độ trễ < 10ms) và chịu được tải đột biến.
• A - Action (Hành động):
  • Sử dụng Dynamo-style KV Store: Bản chất giỏ hàng là key (user_id) - value (list các items). Ta lưu vào KV Store.
  • Đánh đổi CAP (Trade-off): Giữa Consistency và Availability trong lúc mạng giật lag (Partition Tolerance), tôi chọn Availability (AP System). Tức là thà để user thấy giỏ hàng bị thiếu đồ trong giây lát, còn hơn là hiện thông báo lỗi hệ thống. Ta cấu hình $W=1, R=1, N=3$ cho tốc độ nhanh nhất.
  • Resolving Conflicts: Vì là AP System, nếu user thao tác nhanh trên cả Web và Mobile, sẽ có conflict giỏ hàng. Tôi sử dụng Vector Clock [Server, Version] trong Database. Khi Get giỏ hàng, nếu có conflict, KV Store trả về cả 2 version, Application logic của Cart Service sẽ tự merge 2 giỏ hàng lại (hợp nhất đồ) và ghi lại version mới nhất xuống DB.
• R - Result (Kết quả): Latency ghi vào giỏ hàng đạt dưới 5ms. Hệ thống dễ dàng scale out bằng cách thêm node mới vào Hash Ring. Không có request nào bị drop dù database có 1 vài node bị sập do quá tải phần cứng (nhờ Sloppy Quorum & Hinted Handoff).

5. ⚖️ Ưu Điểm & Nhược Điểm (Pros & Cons)

Ưu điểm:

• Performance tối thượng: Truy xuất $O(1)$ theo Key, latency tính bằng millisecond.
• Khả năng Scale-out hoàn hảo: Decentralized + Consistent Hashing giúp thêm bớt server tự động, không giới hạn.
• Flexibility: Value là Opaque (mờ đục, hệ thống không quan tâm bên trong là JSON hay String), dễ dàng thay đổi cấu trúc dữ liệu mà không cần alter bảng như SQL.
• High Availability: Data luôn có sẵn ở nhiều replica, có tự động fail-over.

Nhược điểm:

• Không hỗ trợ query phức tạp (Không có JOIN, GROUP BY hay filter theo nhiều cột). Chỉ query được qua Partition Key.
• Tính nhất quán (Consistency) yếu nếu cấu hình Eventual Consistency, rủi ro Stale data (dữ liệu cũ).
• Đẩy độ khó giải quyết conflict (như dùng Vector Clock) lên phía Client / Application Logic.

Khi nào NÊN và KHÔNG NÊN dùng?

• Nên: Session Management, Shopping Cart, User Preferences, Recommendation Engines, Caching, IoT Data.
• Không nên: Cần các giao dịch phức tạp liên quan nhiều bảng (ACID transactions chặt chẽ như Core Banking), cần tìm kiếm full-text search, hoặc các mối quan hệ (Relations) phức tạp.

6. 🔄 Các Công Nghệ Tiêu Biểu & So Sánh (Alternatives)

• Hệ thống phi tập trung (Decentralized/AP): Amazon DynamoDB, Cassandra, Riak.
• Hệ thống tập trung (Leader-based/CP): Etcd, Zookeeper (Dùng Raft/Paxos consensus để đạt Strong Consistency).
• In-memory cache KV: Redis, Memcached.

So sánh nhanh Redis vs Memcached:

• Memcached: Rất đơn giản, thuần in-memory string, dùng cho cache bay hơi, đa luồng hiệu năng rất cao ở read.
• Redis: Hỗ trợ Data Structures phong phú (List, Set, Hash, ZSet), có thể persist xuống đĩa (AOF/RDB), hỗ trợ mô hình pub/sub, Lua Scripting. Trở thành chuẩn mực công nghiệp hiện tại thay vì Memcached.

7. 🎯 Câu Hỏi Phỏng Vấn Thường Gặp (Interview FAQ)

1. Làm thế nào để hệ thống KV Store chống lại sự cố mất 1 Datacenter (Availability Zone)? Gợi ý: Thiết lập hệ số Replication $N=3$ và trải đều các replica (bản sao) ra các Datacenter khác nhau. Nếu 1 DC sập, Traffic được route sang các DC còn lại để đọc/ghi, dữ liệu vẫn an toàn. Sau đó Cross-datacenter replication sẽ đồng bộ lại sau khi DC khôi phục.

2. Khi một node bị quá tải (Hot spot - nhiều request đọc cùng 1 key ví dụ như id người nổi tiếng), Consistent hashing có giải quyết được không? Gợi ý: Consistent hashing chỉ chia đều không gian Key, chứ không giải quyết được Hot Key. Giải pháp là ở tầng Application phải thêm Random Suffix vào Key để băm nó ra các Node khác nhau, hoặc sử dụng Local Cache / In-memory Cache đặt trước KV Store để hấp thụ lượng read khổng lồ này.

3. Bloom Filter giải quyết vấn đề gì trong Read Path? Nhược điểm của nó? Gợi ý: Nó giúp check siêu nhanh xem 1 key "CHẮC CHẮN KHÔNG TỒN TẠI" hoặc "CÓ THỂ TỒN TẠI" trong đĩa, giúp tiết kiệm 1 vòng Disk I/O tốn kém nếu key thực sự không có. Nhược điểm: Nó có tỉ lệ "False Positive" (báo là có nhưng thực ra không có) nhưng không bao giờ có "False Negative" (báo không có tức là chắc chắn 100% không có).

4. Tại sao lại dùng Merkle Tree thay vì so sánh dữ liệu trực tiếp giữa 2 Replica khi Anti-entropy? Gợi ý: Hệ thống lưu hàng tỷ key. Gửi toàn bộ hash đi để so sánh rất tốn băng thông mạng. Merkle Tree gộp mã băm từ dưới lá lên gốc. Ta chỉ cần so Root Hash, nếu giống là toàn bộ data giống. Nếu khác, chỉ việc đi dần xuống nhánh bị khác và đồng bộ đúng Bucket dữ liệu nhỏ đó. Tối ưu cực độ Network Transfer.