CRDT (Conflict-free Replicated Data Type) là một kiểu cấu trúc dữ liệu được nhân bản trên nhiều máy trong cùng một mạng, cho phép mỗi bản sao cập nhật độc lập và tự động hòa giải mọi xung đột để cuối cùng hội tụ về cùng một trạng thái. Khái niệm này được hình thức hóa vào năm 2011 bởi nhóm nghiên cứu gồm Marc Shapiro, Nuno Preguiça, Carlos Baquero và Marek Zawirski.
Vấn đề mà CRDT giải quyết rất rõ ràng. Khi hai người dùng cùng soạn thảo một tài liệu trong khi một người đang ngoại tuyến, hai bản sao sẽ tạo ra các thay đổi xung đột. Cách truyền thống là khóa (lock) hoặc hợp nhất thủ công, và cả hai đều dẫn tới trải nghiệm tệ: người dùng phải chờ, hoặc phải tự quyết định giữ phiên bản nào. CRDT đảo ngược bài toán: cho phép mọi cập nhật đi qua và tự động hợp nhất chúng về sau.
Ba tính chất bắt buộc
Theo định nghĩa chính thống, một CRDT phải thỏa mãn ba yêu cầu: ứng dụng có thể cập nhật bất kỳ bản sao nào một cách độc lập và đồng thời, không cần bất kỳ cơ chế phối hợp nào giữa các bản sao; thuật toán bên trong kiểu dữ liệu tự động giải quyết mọi bất nhất có thể phát sinh; và dù các bản sao có trạng thái khác nhau tại một thời điểm bất kỳ, chúng được bảo đảm sẽ hội tụ về cùng một trạng thái.
Điểm mấu chốt nằm ở chữ “tất định”. Một hệ thống chỉ hội tụ được nếu kết quả hợp nhất không phụ thuộc vào thứ tự đến của các thông điệp và không phụ thuộc vào việc thông điệp có bị lặp lại hay không. Đây chính là lý do các giao thức mạng thực tế vốn không bảo đảm thứ tự vẫn có thể chạy CRDT mà không cần thay đổi hạ tầng.
Hai họ kiểu dữ liệu
CRDT theo trạng thái
CRDT theo trạng thái, còn gọi là convergent replicated data type, được định nghĩa bởi một hàm tạo trạng thái ban đầu, một hàm merge nhận hai trạng thái và trả về trạng thái hợp nhất, cùng một hàm update áp dụng hành động của người dùng lên trạng thái cục bộ. Mỗi lần có thay đổi, bản sao gửi toàn bộ trạng thái của nó đi, và các bản sao nhận được trạng thái mới thì hợp nhất vào trạng thái cục bộ.
Hàm merge bắt buộc phải thỏa mãn ba tính chất toán học: giao hoán, kết hợp và lũy thừa. Ba tính chất này một lần nữa quy về cùng một ý tưởng: kết quả hợp nhất phải bất biến trước việc sắp xếp lại và lặp lại thông điệp. Nhánh delta CRDT là biến thể tối ưu, chỉ truyền đi phần thay đổi gần đây thay vì toàn bộ trạng thái, giúp giảm băng thông đáng kể khi trạng thái lớn.
CRDT theo thao tác
CRDT theo thao tác không định nghĩa hàm merge mà thay vào đó truyền chính các thao tác cập nhật tới các bản sao khác để áp dụng. Một bộ đếm theo thao tác đơn giản có thể chỉ cần phát tán các lệnh tăng hoặc giảm một giá trị cụ thể. Các thao tác phải giao hoán và kết hợp, và hệ thống bắt buộc phải bảo đảm không thao tác nào bị thất lạc hoặc lặp lại khi truyền.
Trên lý thuyết hai cách tiếp cận này tương đương nhau, mỗi cách có thể mô phỏng cách còn lại. Về thực tế, CRDT theo trạng thái dễ thiết kế và dễ triển khai hơn, chỉ cần một cơ chế phát tán kiểu gossip là đủ. Đổi lại, nó phải truyền cả trạng thái, tốn băng thông khi dữ liệu lớn. CRDT theo thao tác nhẹ hơn nhiều về mặt dữ liệu gửi đi nhưng đòi hỏi tầng truyền thông phải bảo đảm tính toàn vẹn, nếu không sẽ dễ dẫn tới sai lệch dữ liệu.
Ví dụ kinh điển: cờ sự kiện một chiều
Ví dụ đơn giản nhất về CRDT là một cờ boolean một chiều chỉ có một bit. Giá trị true nghĩa là sự kiện đã xảy ra ít nhất một lần, false nghĩa là sự kiện chưa xảy ra. Nguyên tắc bất biến: một khi cờ được đặt thành true thì không thể quay lại false, vì sự kiện đã xảy ra thì không thể chưa xảy ra.
Khi hợp nhất hai bản sao, nếu một bản sao có cờ true và bản sao kia có cờ false, kết quả là true. Quy tắc này gọi là “true thắng”. Nhờ tính chất lũy thừa, việc hợp nhất cờ true một trăm lần vẫn cho kết quả true, nên thông điệp lặp lại không gây hại.
Những ứng dụng thực tế
- Soạn thảo văn bản cộng tác: nền tảng cộng tác trực tuyến dùng CRDT để nhiều người cùng gõ một tài liệu mà không mất dữ liệu ai, kể cả khi có người đang offline.
- Cơ sở dữ liệu NoSQL phân tán: các sản phẩm như Riak và Azure Cosmos DB cung cấp sẵn các kiểu dữ liệu theo mô hình CRDT để ứng dụng không phải tự viết lại thuật toán hợp nhất.
- Ứng dụng nhắn tin và cấu hình cục bộ: danh sách tin nhắn, danh sách thiết bị và cài đặt ứng dụng được hợp nhất không cần can thiệp của máy chủ trung tâm.
- Ứng dụng di động và thời gian thực: các ứng dụng có nhiều thiết bị cùng chỉnh sửa một tài liệu, ví dụ ghi chú trên iPad và iPhone, là miền ứng dụng rất hợp lý của CRDT.
Điểm cộng tác của nhiều thư viện mã nguồn mở như Automerge và Yjs là chúng cung cấp sẵn thuật toán CRDT đã được kiểm chứng, giúp đội phát triển tập trung vào giao diện thay vì phải tự giải quyết bài toán hợp nhất xung đột.
Đánh đổi và giới hạn
CRDT không phải lúc nào cũng là lựa chọn đúng. Với CRDT theo trạng thái, kích thước trạng thái có thể tăng theo thời gian vì dữ liệu đã xóa vẫn phải được giữ lại để bảo đảm khả năng hợp nhất với các bản sao đã không đồng bộ. Với CRDT theo thao tác, tầng truyền thông phải bảo đảm không lặp thao tác, điều mà nhiều hệ thống phân tán hiện tại không cung cấp sẵn.
Ngoài ra, CRDT chỉ giải quyết xung đột ở cấp dữ liệu, không tự quyết định xem thay đổi nào là ý định thật sự của người dùng. Với những trường hợp cần “ý nghĩa” chứ không chỉ cần hợp nhất, như chỉnh sửa đồng thời cùng một câu văn, các ứng dụng vẫn phải bổ sung thêm lớp xử lý xung đột ở tầng ứng dụng.
Kết luận
CRDT đổi cách chúng ta nghĩ về tính nhất quán trong hệ thống phân tán: thay vì ngăn chặn xung đột, nó thiết kế để mọi xung đột đều có thể được hợp nhất một cách tự động và xác định. Với sự bùng nổ của ứng dụng cộng tác trên di động và edge computing, CRDT ngày càng trở thành một kỹ năng bắt buộc của lập trình viên backend.
Bạn có thể đọc thêm chi tiết về mô hình này trong bài viết tiếng Anh trên Wikipedia về Conflict-free replicated data type, hoặc tham khảo thư viện triển khai thực tế tại trang chủ Automerge.
