[System design interview] CHƯƠNG 6: THIẾT KẾ KEY-VALUE STORE
Đây là bản dịch tiếng Việt của "System design interview" (Tác giả: Unknown Author). Bài được dịch tự động bởi Aha! Mind Interpreter — pipeline dịch sách kỹ thuật sử dụng Gemini Flash.
⚠️ Bản dịch tự động — có thể có lỗi. Vui lòng đối chiếu với bản gốc tiếng Anh khi cần độ chính xác cao.
CHƯ ƠNG 6: THIẾT KẾ KEY-VALUE STORE
Một kho dữ liệu key-value (tiếng Anh: key-value store), còn được gọi là cơ sở dữ liệu key-value (tiếng Anh: key-value database), là một cơ sở dữ liệu phi quan hệ (tiếng Anh: non-relational database). Mỗi định danh duy nhất (tiếng Anh: unique identifier) được lưu trữ dưới dạng một key với giá trị liên kết của nó. Cặp dữ liệu này được gọi là cặp "key-value".
Trong một cặp key-value, key phải là duy nhất, và giá trị liên kết với key có thể được truy cập thông qua key đó. Các key có thể là văn bản thuần túy (tiếng Anh: plain text) hoặc giá trị băm (tiếng Anh: hashed values). Vì lý do hiệu suất, một key ngắn sẽ hoạt động tốt hơn. Các key trông như thế nào? Dưới đây là một vài ví dụ:
-
Key văn bản thuần túy: “last_logged_in_at”
-
Key băm: 253DDEC4
Giá trị trong một cặp key-value có thể là chuỗi, danh sách, đối tượng, v.v. Giá trị thường được coi là một đối tượng mờ (tiếng Anh: opaque object) trong các kho dữ liệu key-value, chẳng hạn như Amazon Dynamo [1], Memcached [2], Redis [3], v.v.
Dưới đây là một đoạn dữ liệu trong một kho dữ liệu key-value:

Trong chương này, chúng ta sẽ thiết kế một kho dữ liệu key-value hỗ trợ các thao tác sau:
-
put(key, value) // chèn “value” liên kết với “key”
-
get(key) // lấy “value” liên kết với “key”
Hiểu vấn đề và thiết lập phạm vi thiết kế
Không có thiết kế nào là hoàn hảo. Mỗi thiết kế đạt được một sự cân bằng cụ thể về các đánh đổi giữa việc đọc, ghi và sử dụng bộ nhớ. Một đánh đổi khác phải được thực hiện là giữa Consistency và Availability. Trong chương này, chúng ta thiết kế một kho dữ liệu key-value bao gồm các đặc điểm sau:
-
Kích thước của một cặp key-value nhỏ: dưới 10 KB.
-
Khả năng lưu trữ Big Data.
-
High Availability: Hệ thống phản hồi nhanh chóng, ngay cả khi xảy ra lỗi.
-
High Scalability: Hệ thống có thể được mở rộng để hỗ trợ tập dữ liệu lớn.
-
Automatic Scaling: Việc thêm/xóa máy chủ phải tự động dựa trên lưu lượng truy cập.
-
Tunable Consistency.
-
Low Latency.
Kho dữ liệu key-value trên một máy chủ
Phát triển một kho dữ liệu key-value nằm trên một máy chủ duy nhất là điều dễ dàng. Một cách tiếp cận trực quan l à lưu trữ các cặp key-value trong một bảng băm (tiếng Anh: hash table), giữ mọi thứ trong bộ nhớ. Mặc dù truy cập bộ nhớ nhanh, nhưng việc chứa tất cả mọi thứ trong bộ nhớ có thể là không thể do ràng buộc về không gian. Hai tối ưu hóa có thể được thực hiện để chứa nhiều dữ liệu hơn trên một máy chủ duy nhất:
-
Nén dữ liệu (tiếng Anh: Data compression)
-
Chỉ lưu trữ dữ liệu thường xuyên được sử dụng trong bộ nhớ và phần còn lại trên đĩa
Ngay cả với những tối ưu hóa này, một máy chủ duy nhất có thể đạt đến dung lượng của nó rất nhanh chóng. Một kho dữ liệu key-value phân tán (tiếng Anh: distributed key-value store) là cần thiết để hỗ trợ Big Data.
Kho dữ liệu key-value phân tán
Một kho dữ liệu key-value phân tán còn được gọi là bảng băm phân tán (tiếng Anh: distributed hash table), phân tán các cặp key-value trên nhiều máy chủ. Khi thiết kế một hệ thống phân tán, điều quan trọng là phải hiểu CAP theorem (Consistency, Availability, Partition Tolerance).
CAP theorem
CAP theorem phát biểu rằng một hệ thống phân tán không thể đồng thời cung cấp nhiều hơn hai trong ba đảm bảo sau: Consistency, Availability và Partition Tolerance. Hãy cùng thiết lập một vài định nghĩa.
Consistency: Consistency có nghĩa là tất cả các client đều thấy cùng một dữ liệu tại cùng một thời điểm, bất kể chúng kết nối với nút nào.
Availability: Availability có nghĩa là bất kỳ client nào yêu cầu dữ liệu đều nhận được phản hồi ngay cả khi một số nút bị lỗi.
Partition Tolerance: Một phân vùng (tiếng Anh: partition) chỉ ra sự gián đoạn giao tiếp giữa hai nút. Partition Tolerance có nghĩa là hệ thống tiếp tục hoạt động bất chấp các phân vùng mạng.
CAP theorem phát biểu rằng một trong ba thuộc tính phải được đánh đổi để hỗ trợ 2 trong 3 thuộc tính còn lại như thể hiện trong Hình 6-1.

Ngày nay, các kho dữ liệu key-value được phân loại dựa trên hai đặc điểm CAP mà chúng hỗ trợ:
Hệ thống CP (Consistency và Partition Tolerance): Một kho dữ liệu key-value CP hỗ trợ Consistency và Partition Tolerance trong khi đánh đổi Availability.
Hệ thống AP (Availability và Partition Tolerance): Một kho dữ liệu key-value AP hỗ trợ Availability và Partition Tolerance trong khi đánh đổi Consistency.
Hệ thống CA (Consistency và Availability): Một kho dữ liệu key-value CA hỗ trợ Consistency và Availability trong khi đánh đổi Partition Tolerance. Vì lỗi mạng là không thể tránh khỏi, một hệ thống phân tán phải chịu đựng phân vùng mạng. Do đó, một hệ thống CA không thể tồn tại trong các ứng dụng thực tế.
Những gì chúng ta vừa đọc chủ yếu là phần định nghĩa. Để dễ hiểu hơn, hãy cùng xem xét một số ví dụ cụ thể. Trong các hệ thống phân tán, dữ liệu thường được sao chép nhiều lần. Giả sử dữ liệu được sao chép trên ba nút bản sao (tiếng Anh: replica nodes), n1, n2 và n3 như thể hiện trong Hình 6-2.
Tình huống lý tưởng Trong một thế giới lý tưởng, phân vùng mạng không bao giờ xảy ra. Dữ liệu được ghi vào n1 tự động được sao chép sang n2 và n3. Cả Consistency và Availability đều đạt được.
Hệ thống phân tán trong thế giới thực Trong một hệ thống phân tán, các phân vùng là không thể tránh khỏi, và khi một phân vùng xảy ra, chúng ta phải lựa chọn giữa Consistency và Availability. Trong Hình 6-3, n3 bị lỗi và không thể giao tiếp với n1 và n2. Nếu client ghi dữ liệu vào n1 hoặc n2, dữ liệu không thể được truyền tải đến n3. Nếu dữ liệu được ghi vào n3 nhưng chưa được truyền tải đến n1 và n2, thì n1 và n2 sẽ có dữ liệu cũ/lỗi thời (tiếng Anh: stale data).

Nếu chúng ta chọn Consistency thay vì Availability (hệ thống CP), chúng ta phải chặn tất cả các thao tác ghi vào n1 và n2 để tránh tính không nhất quán của dữ liệu (tiếng Anh: data inconsistency) giữa ba máy chủ này, điều này khiến hệ thống không khả dụng. Các hệ thống ngân hàng thường có yêu cầu nhất quán cực kỳ cao. Ví dụ, điều quan trọng đối với một hệ thống ngân hàng là phải hiển thị thông tin số dư cập nhật nhất. Nếu tính không nhất quán xảy ra do phân vùng mạng, hệ thống ngân hàng sẽ trả về lỗi trước khi tính không nhất quán được giải quyết.
Tuy nhiên, nếu chúng ta chọn Availability thay vì Consistency (hệ thống AP), hệ thống vẫn tiếp tục chấp nhận các yêu cầu đọc, mặc dù nó có thể trả về dữ liệu cũ/lỗi thời. Đối với các thao tác ghi, n1 và n2 sẽ tiếp tục chấp nhận các thao tác ghi, và dữ liệu sẽ được đồng bộ hóa (tiếng Anh: synced) với n3 khi phân vùng mạng được giải quyết.
Việc lựa chọn các đảm bảo CAP phù hợp với trường hợp sử dụng của bạn là một bước quan trọng trong việc xây dựng một kho dữ liệu key-value phân tán. Bạn có thể thảo luận điều này với người phỏng vấn và thiết kế hệ thống tương ứng.
Các thành phần hệ thống
Trong phần này, chúng ta sẽ thảo luận về các thành phần cốt lõi và kỹ thuật sau đây được sử dụng để xây dựng một kho dữ liệu key-value:
-
Phân vùng dữ liệu (tiếng Anh: Data partition)
-
Sao ch ép dữ liệu (tiếng Anh: Data replication)
-
Consistency
-
Giải quyết tính không nhất quán (tiếng Anh: Inconsistency resolution)
-
Xử lý lỗi (tiếng Anh: Handling failures)
-
Sơ đồ kiến trúc hệ thống (tiếng Anh: System architecture diagram)
-
Đường dẫn ghi (tiếng Anh: Write path)
-
Đường dẫn đọc (tiếng Anh: Read path)
Nội dung dưới đây phần lớn dựa trên ba hệ thống kho dữ liệu key-value phổ biến: Dynamo [4], Cassandra [5] và BigTable [6].
Phân vùng dữ liệu
Đối với các ứng dụng lớn, việc chứa toàn bộ tập dữ liệu (tiếng Anh: complete data set) trong một máy chủ duy nhất là không khả thi. Cách đơn giản nhất để thực hiện điều này là chia dữ liệu thành các phân vùng nhỏ hơn và lưu trữ chúng trên nhiều máy chủ. Có hai thách thức khi phân vùng dữ liệu:
-
Phân phối dữ liệu đều khắp các máy chủ.
-
Giảm thiểu việc di chuyển dữ liệu khi các nút được thêm hoặc xóa.
Băm nhất quán (tiếng Anh: Consistent hashing) đã được thảo luận trong Chương 5 là một kỹ thuật tuyệt vời để giải quyết những vấn đề này. Hãy cùng xem lại cách băm nhất quán hoạt động ở cấp độ cao.
-
Đầu tiên, các máy chủ được đặt trên một vòng băm (tiếng Anh: hash ring). Trong Hình 6-4, tám máy chủ, được đại diện bởi s0, s1, …, s7, được đặt trên vòng băm.
-
Tiếp theo, một key được băm lên cùng một vòng, và nó được lưu trữ trên máy chủ đầu tiên gặp phải khi di chuyển theo chiều kim đồng hồ. Ví dụ, key0 được lưu trữ trong s1 bằng cách sử dụng logic này.
Sử dụng băm nhất quán để phân vùng dữ liệu có những lợi ích sau:
Tự động mở rộng (tiếng Anh: Automatic scaling): Các máy chủ có thể được thêm và xóa tự động tùy thuộc vào tải.
