- CRDT (Conflict-free Replicated Data Type, kiểu dữ liệu sao chép không xung đột) là cấu trúc dữ liệu phân tán cho phép hợp nhất dữ liệu nhất quán mà không cần điều phối ngay cả khi mạng bị phân mảnh hoặc có chỉnh sửa đồng thời
- Nếu việc hợp nhất dữ liệu thỏa mãn tính giao hoán, kết hợp và lũy đẳng, mọi bản sao cuối cùng sẽ hội tụ về cùng một trạng thái
- Các dạng tiêu biểu gồm G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot,... mỗi loại xử lý những yêu cầu khác nhau về thêm, xóa, thêm lại, duy trì thứ tự
- Delta CRDT tăng hiệu quả bằng cách chỉ truyền phần thay đổi thay vì toàn bộ trạng thái, còn Garbage Collection là bài toán then chốt để giải quyết vấn đề metadata tích lũy
- CRDT không phải lời giải hoàn hảo, nhưng được đánh giá là lựa chọn mạnh mẽ trong các hệ thống mà tính sẵn sàng quan trọng hơn tính nhất quán tức thời
Khái niệm cơ bản về CRDT
- CRDT là cấu trúc dữ liệu có thể hợp nhất mà không cần điều phối ngay cả khi có chỉnh sửa đồng thời trong môi trường phân tán
- Nếu phép hợp nhất là giao hoán (commutative), kết hợp (associative) và lũy đẳng (idempotent) thì mọi bản sao sẽ hội tụ về cùng một trạng thái
- Được thiết kế dựa trên khái niệm Lattice (mạng thứ tự), để trạng thái luôn chỉ dịch chuyển theo hướng “đi lên”
- Ví dụ: G-Counter hợp nhất số đếm của từng bản sao bằng
max để đảm bảo cộng dồn không mất dữ liệu
- CRDT có hai cách tiếp cận là State-based (CvRDT) và Operation-based (CmRDT)
- CvRDT hợp nhất toàn bộ trạng thái, còn CmRDT lan truyền các thao tác
Các loại CRDT chính
- G-Counter: bộ đếm chỉ có thể tăng, cộng tổng giá trị của từng bản sao
- PN-Counter: kết hợp G-Counter cho tăng và giảm để hỗ trợ đếm hai chiều
- G-Set: tập hợp chỉ có thể thêm
- 2P-Set: có thể thêm và xóa nhưng không thể thêm lại
- LWW-Element-Set: thao tác gần nhất thắng dựa trên timestamp
- OR-Set: dùng thẻ định danh duy nhất để hợp nhất mà không mất dữ liệu khi có thêm đồng thời, hoạt động theo kiểu add-wins
- LWW-Register / MV-Register: dùng để lưu một giá trị đơn; LWW có một giá trị thắng duy nhất, MV giữ lại tất cả các giá trị đồng thời
- OR-Map: cấu trúc map kết hợp OR-Set theo từng khóa
- RGA / WOOT / Logoot / LSEQ: CRDT cho dữ liệu chuỗi có thứ tự
- RGA dựa trên cây, WOOT dựa trên tham chiếu hai chiều, Logoot/LSEQ dựa trên định danh vị trí
Các khái niệm CRDT nâng cao
- Causal CRDTs: dùng vector phiên bản để theo dõi quan hệ nhân quả, cho phép phát hiện xung đột chính xác hơn
- Delta CRDTs: chỉ truyền phần thay đổi (delta) thay vì toàn bộ trạng thái để tăng hiệu quả mạng
- Tree CRDTs: hỗ trợ sao chép dữ liệu có cấu trúc phân cấp (như hệ thống tệp), cần duy trì quan hệ cha-con
- Observed-Remove Shopping Cart: ví dụ giỏ hàng thương mại điện tử kết hợp OR-Set và PN-Counter
Vấn đề Garbage Collection
- Để hội tụ, CRDT liên tục tích lũy metadata nên phát sinh vấn đề tăng trưởng vô hạn
- Ví dụ: thẻ của OR-Set, tombstone của RGA
- Có nhiều chiến lược như hết hạn theo thời gian, xóa dựa trên đồng thuận, theo dõi nhân quả dựa trên vector phiên bản, đặt giới hạn metadata, checkpoint/rebase
- Mỗi cách đều cần đánh đổi giữa độ an toàn (ngăn zombie phục hồi) và hiệu quả không gian
Hiệu năng và hướng dẫn lựa chọn
- Độ phức tạp thời gian và không gian của từng loại CRDT thay đổi theo số lượng bản sao, số phần tử, số thẻ,...
- G/PN-Counter tỷ lệ theo số bản sao, OR-Set tỷ lệ theo số thẻ, RGA tích lũy tombstone
- Delta CRDT cải thiện đáng kể hiệu năng hợp nhất
- Tiêu chí lựa chọn:
- Chỉ cần thêm → G-Counter, G-Set
- Cần xóa, không cần thêm lại → 2P-Set
- Chấp nhận LWW → LWW-Set/Register
- Cần giữ chỉnh sửa đồng thời → OR-Set, MV-Register
- Cần duy trì thứ tự → RGA, Logoot
- Cấu trúc lồng nhau → OR-Map
Kết luận
- CRDT đảm bảo hội tụ không cần điều phối, nhưng có nhược điểm là metadata tăng lên và độ phức tạp cao hơn
- Hữu ích trong các hệ thống ưu tiên tính sẵn sàng, và mỗi CRDT được tối ưu cho một loại bài toán cụ thể
- Trong thực tế thường được dùng song song với cơ sở dữ liệu truyền thống, và chiến lược garbage collection là bắt buộc
- Không có “CRDT hoàn hảo”; điều cốt lõi là chọn loại phù hợp với yêu cầu của ứng dụng
1 bình luận
Ý kiến trên Hacker News
Một trong những điểm thú vị của CRDT là nó không chỉ đơn thuần là một thư viện ghép từ nhiều CRDT cấp thấp
Ví dụ, Automerge tự nó đã là một CRDT hoàn chỉnh và đảm bảo tính nhất quán ngay cả dưới đồng thời thông qua chứng minh toán học
Nhóm Automerge xác minh thiết kế bằng các công cụ chứng minh định lý như Isabelle, đồng thời áp dụng các kỹ thuật hiệu năng mới nhất từ thế giới cơ sở dữ liệu để hướng tới một triển khai vừa nhanh vừa chính xác
Nếu xây dựng SaaS cần cộng tác thời gian thực (ví dụ: Notion, Figma), thì ngay cả khi không hiểu lý thuyết phức tạp, bạn vẫn có thể áp dụng ngay cấu trúc dữ liệu cộng tác
Backend chỉ cần một kho lưu trữ key-value đơn giản, còn frontend chỉ cần một thư viện
Tôi cũng từng tạo một thư viện automerge dựa trên Redis, và có thể triển khai một máy chủ đồng bộ liên tục hoàn chỉnh bằng pub/sub
Tôi cũng nhanh chóng hoàn thiện demo đồng bộ tài liệu giữa nhiều trình duyệt bằng cách tận dụng tính năng websocket của Webdis
Nếu muốn DX tốt hơn và một fullstack DB dựa trên CRDT, tôi khuyên dùng Triplit.dev. Tốc độ phát triển có chậm lại đôi chút nhưng tính năng thì đã khá hoàn thiện
Cá nhân tôi cũng thích Loro, nhưng nó vẫn là cấu trúc dựa trên tài liệu, nên thiếu query engine. Muốn lấy được dữ liệu mong muốn thì phải chỉ định trực tiếp các mục lồng nhau cụ thể
Đây là bài viết tổng hợp rất tốt từ những khái niệm cơ bản đến nâng cao của CRDT
Nhân tiện, Riak hiện vẫn đang được duy trì dưới dạng OpenRiak
Tôi đã tự phát triển CRDT trong 2 năm qua, nhưng rồi nhận ra có quá nhiều trade-off, nên cuối cùng đã chuyển sang framework OT dựa trên ID
Tôi dự định ra mắt Docnode.dev vào thứ Ba tuần này. Tôi muốn nghe phản hồi
Trong tương lai, tôi cũng có kế hoạch bổ sung chế độ CRDT cho các tình huống cần P2P
CRDT hay OT là các cấu trúc nhằm giải quyết tình huống mọi người cùng chỉnh sửa một đoạn văn cùng lúc, nhưng thực tế thì chuyện đó hầu như không xảy ra
OR-Set được nói đến trong bài này có vẻ tương tự với cách hợp nhất mà Monotone đã dùng từ năm 2005
Có thể xem tài liệu liên quan tại tài liệu MarkMerge
CRDT vẫn là lĩnh vực mà bạn phải tự tay triển khai
Hai tháng trước tôi cũng đã tạo một engine CRDT dựa trên sequence, lấy cảm hứng từ diamond types
Tôi đã nhờ AI hỗ trợ, nhưng với dạng bài toán thiên về logic như thế này thì nó hoàn toàn không giúp được gì
Tôi cảm thấy cần có các bài kiểm thử hộp đen để xác minh xem LLM có thực sự hiểu được logic mới hay không
Bài viết rất hay, nhưng tôi nghĩ phần thuật ngữ nhất định phải có chỉ mục (index)
Tôi có cảm giác CRDT rốt cuộc chỉ là đẩy xung đột hợp nhất từ DB sang logic ứng dụng
Nếu được viết đúng cách thì dù ở tầng nào, nó vẫn có thể tự động giải quyết hợp nhất
Vấn đề lớn nhất là xử lý xung đột UNIQUE/PRIMARY KEY
Có thể giải quyết bằng cách phân bổ namespace ID cho từng máy chủ, để bản tạo đầu tiên chiến thắng, rồi khi có xung đột thì đổi tên hoặc xóa
Nếu dùng schema EAV thì có thể dễ dàng triển khai duyệt đồ thị bằng CTE đệ quy trong SQL
Tuy nhiên, PostgreSQL không có kiểu ANY nên khó biểu diễn các đối tượng có thuộc tính đa dạng, và chức năng FOREIGN KEY cũng phải tự triển khai
Dù vậy, cấu trúc EAV vẫn có lợi cho thiết kế meta schema như kế thừa
Sẽ rất hay nếu có thể tự định nghĩa kiểu CRDT trực tiếp trong PostgreSQL, nhưng hiện tại chưa thể áp đặt ràng buộc lên phép toán monoid
Cuối cùng thì CRDT cho các cột không phải khóa vẫn phải được xử lý ở tầng ứng dụng
Tóm lại, CRDT có thể được triển khai bên trong cả RDBMS, nhưng cách tiếp cận sẽ khác nhau tùy vào việc đặt business logic ở đâu