Linearizability — Mô hình đồng nhất dữ liệu mạnh nhất (DDIA) | Blog

Mở đầu

Ảnh: Daniel — Pexels

Khi làm việc với distributed systems, một trong những câu hỏi khó nhất là: dữ liệu mình đang đọc có phải là dữ liệu mới nhất không? Trong thế giới lý tưởng, mọi node trong hệ thống luôn có cùng một dữ liệu tại cùng một thời điểm. Nhưng thực tế thì không đơn giản như vậy — network delay, node failure, và replication lag khiến việc đảm bảo tính đồng nhất của dữ liệu trở nên cực kỳ phức tạp.

DDIA Chapter 9 bắt đầu bằng việc giới thiệu các consistency guarantees (cơ chế đảm bảo đồng nhất dữ liệu), và đi sâu vào một trong những mô hình mạnh nhất — Linearizability. Đây là khái niệm nền tảng giúp bạn hiểu được sự đánh đổi giữa consistency và performance, cũng như lý do tại sao nhiều hệ thống phân tán lại chọn các mô hình yếu hơn.

Consistency Guarantees — Tại sao cần?

Ảnh: Pixabay — Pexels

Trong một hệ thống distributed, dữ liệu được sao chép qua nhiều node để đảm bảo độ tin cậy và khả năng chịu lỗi. Nhưng việc replication này tạo ra một vấn đề: các replica có thể không đồng bộ với nhau tại một thời điểm nhất định.

Nếu bạn đọc dữ liệu từ một replica chưa kịp nhận bản cập nhật mới nhất, bạn sẽ thấy dữ liệu cũ — hay còn gọi là stale read. Các consistency guarantees là những "lời hứa" mà hệ thống đưa ra về cách dữ liệu được đồng bộ giữa các node. Chúng giúp lập trình viên hiểu được hành vi của database khi có nhiều client đọc/ghi đồng thời.

Có nhiều mức consistency khác nhau, từ yếu đến mạnh:

Eventual Consistency — dữ liệu cuối cùng cũng sẽ đồng bộ, nhưng không hứa hẹn khi nào
Causal Consistency — các thao tác có quan hệ nhân quả được thấy theo đúng thứ tự
Linearizability — mạnh nhất, làm cho hệ thống trông như chỉ có một bản sao dữ liệu duy nhất

Linearizability — Mô hình mạnh nhất

Ảnh: Pixabay — Pexels

Linearizability (còn gọi là atomic consistency, strong consistency, hay external consistency) là mô hình consistency mạnh nhất trong distributed systems. Một hệ thống được gọi là linearizable nếu nó hoạt động như thể chỉ có một bản copy duy nhất của dữ liệu, và mọi thao tác trên dữ liệu đó đều diễn ra một cách nguyên tử (atomic) — nghĩa là không thể quan sát được trạng thái trung gian.

Nói cách khác, linearizability tạo ra ảo giác rằng dữ liệu chỉ tồn tại trên một máy, dù thực tế nó được replicated trên nhiều máy. Tất cả các client đều thấy dữ liệu giống nhau, và mỗi thao tác dường như được thực hiện tại một thời điểm duy nhất — gọi là linearization point.

Tính chất của Linearizability

Thứ tự toàn cục (total order): Mọi thao tác đều có thể sắp xếp thành một thứ tự tuyến tính duy nhất, và thứ tự này phải khớp với thời gian thực của các thao tác
Atomicity: Một khi write hoàn tất, mọi read sau đó (từ bất kỳ client nào) đều phải thấy giá trị mới — hoặc giá trị mới hơn
Recency: Nếu một read trả về giá trị cũ, thì mọi read trước đó cũng chỉ có thể thấy giá trị đó hoặc cũ hơn — không thể "thấy về quá khứ"

Một cách để kiểm tra linearizability là dùng bài toán "hệ thống có lừa dối được một external observer hay không". Nếu observer có thể nhìn thấy dữ liệu không nhất quán giữa các replica, hệ thống không phải linearizable.

Khi nào Linearizability hữu ích?

Không phải hệ thống nào cũng cần linearizability, nhưng có một số trường hợp nó gần như bắt buộc:

Leader election — trong cluster, cần đảm bảo chỉ có một leader tại một thời điểm. Các hệ thống như ZooKeeper, etcd sử dụng linearizability để bầu chọn leader
Distributed locks — nếu lock không linearizable, hai tiến trình có thể cùng nghĩ mình đang giữ lock
Unique constraints — ví dụ: đăng ký username, không thể có hai người dùng cùng nhận được username giống nhau
Cross-channel dependencies — khi thông tin từ một kênh (ví dụ: email "đơn hàng đã thanh toán") ảnh hưởng đến hành vi ở kênh khác (ví dụ: web hiển thị trạng thái đơn hàng)
Banking & Finance — balance account cần chính xác tuyệt đối, không thể có stale read

Cái giá của Linearizability

Linearizability không phải là "miễn phí". Nó đi kèm với những chi phí đáng kể:

Performance — vì mọi thao tác đều phải thông qua một "điểm" duy nhất (linearization point), hệ thống trở nên chậm hơn dưới network delay
Availability — theo định lý CAP, trong trường hợp network partition, bạn phải chọn giữa consistency (C) và availability (A). Linearizability thuộc phe consistency, nên khi mạng bị chia cắt, hệ thống sẽ từ chối phục vụ thay vì trả về dữ liệu không nhất quán
Geo-distribution cost — các datacenter cách nhau hàng trăm km có network latency vài trăm ms. Nếu mọi write đều phải chờ xác nhận từ tất cả replica, throughput sẽ giảm mạnh

Đây là lý do tại sao các hệ thống như Cassandra, DynamoDB, hoặc CouchDB lại chọn eventual consistency thay vì linearizability — họ ưu tiên availability và performance hơn.

Linearizability vs Causal Consistency

Điều thú vị là giữa linearizability và eventual consistency có một mức trung gian: causal consistency. Nó yếu hơn linearizability nhưng mạnh hơn eventual consistency, và là một lựa chọn tốt cho nhiều ứng dụng thực tế.

Ví dụ: nếu bạn post một câu hỏi trên forum và sau đó post câu trả lời, thì bất kỳ ai thấy câu trả lời cũng phải thấy câu hỏi — đó là causal consistency. Nhưng nếu Alice và Bob cùng chỉnh sửa một document, không có quan hệ nhân quả giữa các thao tác của họ, thì hệ thống có thể hiển thị chúng theo thứ tự bất kỳ.

Causal consistency thực tế "đủ" cho hầu hết ứng dụng, và có thể được triển khai hiệu quả hơn linearizability. Nó là chủ đề chính của phần 9.2 trong DDIA, nhưng đã được giới thiệu ở Chapter 5 và sẽ được phân tích sâu hơn trong phần sau.

Key Takeaways

Linearizability là mô hình consistency mạnh nhất — nó làm cho distributed database trông như chỉ có một bản copy dữ liệu duy nhất
Linearizability đảm bảo total order của operations dựa trên real-time — mọi client đều thấy dữ liệu giống nhau tại cùng thời điểm
Linearizability có chi phí cao: throughput thấp, latency cao dưới network delay, và không thể hoạt động trong network partition
Các ứng dụng cần leader election, distributed locking, hoặc unique constraints thường yêu cầu linearizability
Causal consistency là một lựa chọn trung gian: mạnh hơn eventual consistency nhưng yếu hơn linearizability, và đủ mạnh cho nhiều ứng dụng thực tế
Theo định lý CAP, linearizability và availability không thể cùng tồn tại trong network partition — đây là trade-off cốt lõi của distributed systems

📋 Phụ lục thuật ngữ

Linearizability — mô hình consistency mạnh nhất, đảm bảo mọi thao tác được sắp xếp theo thứ tự tuyến tính dựa trên thời gian thực
Linearization point — điểm thời gian tại đó một thao tác được coi là đã hoàn tất, tất cả replica đều đồng ý về thời điểm này
Total order — thứ tự toàn cục; mọi thao tác đều có thể so sánh được với nhau về mặt thứ tự
Stale read — đọc phải dữ liệu cũ, không phải bản mới nhất
CAP theorem — định lý chỉ ra rằng distributed system chỉ có thể đảm bảo 2 trong 3: Consistency, Availability, Partition tolerance
Causal consistency — mô hình yếu hơn linearizability, chỉ đảm bảo thứ tự của các thao tác có quan hệ nhân quả
Atomic register — khái niệm cốt lõi trong distributed computing, register có thể đọc/ghi với tính chất atomic
Eventual consistency — mô hình yếu nhất, dữ liệu sẽ đồng bộ "cuối cùng" nhưng không có cam kết về thời gian

Kết

Hiểu về linearizability giúp bạn trả lời được câu hỏi quan trọng: hệ thống của mình cần consistency ở mức nào? Câu trả lời phụ thuộc vào use case cụ thể. Nếu bạn đang xây dựng một hệ thống đặt vé máy bay, bạn chắc chắn cần linearizability — hai người không thể cùng đặt chỗ cuối cùng. Nhưng nếu là hệ thống hiển thị bài đăng trên social network, eventual consistency là hoàn toàn chấp nhận được.

Bài tiếp theo trong series (9.2) sẽ đi sâu vào Causal Consistency — một mô hình thú vị nằm giữa eventual consistency và linearizability, và cách nó được triển khai trong các hệ thống thực tế.