Hai người cùng sửa một danh sách mua sắm trên điện thoại. Cả hai đang mất mạng — một người trong thang máy, một người trên máy bay. Lan thêm "sữa", Minh thêm "trứng". Nửa tiếng sau cả hai có mạng trở lại.
Kết quả đúng phải là danh sách có cả sữa lẫn trứng. Nhưng để máy tự làm được điều đó mà không hỏi ai, cần một cách thiết kế dữ liệu khác hẳn thông thường. Đó là CRDT.
Vì sao cách quen thuộc lại làm mất dữ liệu
Cách phổ biến nhất là để máy chủ phân xử: bản nào gửi lên sau thì thắng. Nghe hợp lý, nhưng hãy xem chuyện gì xảy ra với danh sách mua sắm.
Máy của Lan gửi lên trước, máy của Minh gửi sau. Máy chủ lưu bản của Minh và xoá bản của Lan. Mục "sữa" biến mất, mà không ai được báo gì cả.
Cách thứ hai là hỏi người dùng: "có xung đột, bạn chọn bản nào?". An toàn hơn nhưng đẩy việc khó sang cho người dùng, và với những thứ sửa liên tục như tài liệu chung thì hỏi suốt ngày.
CRDT chọn hướng thứ ba: thiết kế cấu trúc dữ liệu sao cho việc gộp luôn có một đáp án đúng duy nhất, tính được bằng máy, không cần trọng tài cũng không cần hỏi ai.
Ba tính chất làm nên phép màu
Muốn gộp mà không cần phân xử, phép gộp phải thoả ba điều kiện. Nghe rất toán học nhưng ý nghĩa thực tế thì đơn giản.
Đổi chỗ được nghĩa là gộp bản của Lan vào bản của Minh, hay ngược lại, đều ra cùng kết quả. Thực tế quan trọng vì trên mạng bạn không kiểm soát được gói tin nào tới trước.
Gộp nhóm được nghĩa là ba máy trở lên thì gộp cặp nào trước cũng vậy. Không cần một thứ tự toàn cục — thứ mà hệ phân tán rất khó có.
Lặp lại vô hại nghĩa là nhận trùng cùng một gói tin hai lần cũng không sai. Điều này cứu bạn khỏi cả một lớp lỗi, vì mạng thật luôn gửi trùng khi thử lại.
Có đủ ba tính chất, các bản sao chắc chắn hội tụ về cùng một trạng thái — bất kể ai gửi trước, gói nào lạc, gói nào tới hai lần.
Ví dụ dễ nhất: đếm lượt thích
Giả sử một bài viết được thích trên ba máy chủ khác nhau, và chúng đồng bộ chậm. Nếu mỗi máy giữ một con số rồi lấy số lớn nhất khi gộp, bạn sẽ mất lượt thích. Nếu cộng dồn mù quáng, bạn sẽ đếm trùng.
Lời giải là mỗi máy chỉ được ghi vào ô của chính nó.
Máy A đếm 5 lượt, máy B đếm 3, máy C đếm 2. Khi gộp, ta lấy giá trị lớn nhất ở từng ô rồi cộng lại: 5 + 3 + 2 = 10.
Vì sao lấy giá trị lớn nhất mà không cộng? Vì ô của máy A chỉ do máy A ghi, nên con số ở đó luôn tăng. Nhận được bản cũ hơn thì bỏ qua, nhận bản mới hơn thì cập nhật. Nhận trùng cũng không sao — lấy số lớn nhất hai lần vẫn ra số đó.
Muốn đếm cả tăng lẫn giảm thì dùng hai bộ đếm như trên, một cho tăng một cho giảm, kết quả là hiệu của hai tổng.
Tập hợp: thêm thì dễ, xoá mới khó
Quay lại danh sách mua sắm. Chỉ thêm phần tử thì quá dễ: gộp là phép hợp hai tập, và phép hợp thoả cả ba tính chất ở trên.
Rắc rối bắt đầu khi có xoá.
Lan xoá "sữa" khỏi danh sách. Máy Minh chưa biết chuyện đó nên vẫn còn "sữa". Khi gộp bằng phép hợp, "sữa" quay trở lại — vì với máy tính, "tôi không có sữa" và "tôi đã xoá sữa" trông giống hệt nhau.
Cách chữa là ghi lại dấu vết: khi xoá, ta không bỏ phần tử đi mà đánh dấu nó đã bị xoá. Dấu này thường gọi là bia mộ. Lúc gộp, dấu xoá thắng phần tử còn sống, nên kết quả đúng ý người dùng.
Cái giá là danh sách bia mộ cứ dài mãi. Một tài liệu sửa nhiều năm có thể mang theo lượng dấu vết lớn hơn cả nội dung thật. Hệ thống thực tế phải dọn định kỳ, và chỉ dọn được khi chắc chắn mọi bản sao đều đã nhận tin về lần xoá đó.
Văn bản: bài toán khó nhất
Soạn thảo cộng tác là chỗ CRDT được biết đến nhiều nhất, cũng là chỗ khó nhất. Vấn đề nằm ở chỗ vị trí trong văn bản không đứng yên.
Giả sử văn bản đang là "MEO". Lan chèn "C" vào đầu, Minh chèn "O" vào cuối. Nếu mô tả thao tác bằng số thứ tự — "chèn vào vị trí 3" — thì sau khi thao tác của Lan được áp dụng, vị trí 3 đã trỏ vào chỗ khác. Chữ của Minh rơi sai chỗ.
Lời giải là bỏ hẳn số thứ tự. Mỗi ký tự được gán một định danh bền vững không bao giờ đổi, và thao tác chèn được mô tả theo quan hệ: "nằm giữa ký tự có mã X và ký tự có mã Y".
Chi tiết hay ở đây là giữa hai mã bất kỳ luôn tạo được mã mới nằm giữa — giống như giữa hai số thực bất kỳ luôn có một số thực khác. Nhờ vậy không bao giờ hết chỗ chèn, dù người ta gõ chen vào cùng một điểm bao nhiêu lần.
Khi hai người chèn vào đúng cùng một khe, cần một quy tắc phá hoà — thường là so sánh mã định danh của máy. Quy tắc nào cũng được, miễn mọi máy dùng chung một quy tắc, vì mục tiêu là tất cả ra cùng kết quả.
Kết quả: mọi bản sao gặp nhau
Đây là điều CRDT hứa và giữ được: cho các máy nhận thay đổi theo thứ tự bất kỳ, lặp bao nhiêu lần cũng được, miễn cuối cùng ai cũng nhận đủ thì tất cả sẽ có cùng một trạng thái. Không cần máy chủ trung tâm, không cần khoá, không cần hỏi người dùng.
Hai cách hiện thực
Gửi trạng thái. Mỗi máy định kỳ gửi toàn bộ trạng thái của mình đi, bên nhận gộp vào. Đơn giản, chịu được mất gói, nhưng tốn băng thông nếu dữ liệu lớn. Các bản hiện đại gửi phần chênh lệch thay vì toàn bộ.
Gửi thao tác. Mỗi máy chỉ gửi thao tác vừa làm. Rất tiết kiệm, nhưng đòi hỏi tầng vận chuyển bảo đảm mọi thao tác đều tới, không mất, và không bị áp dụng trùng.
Điều CRDT không hứa
Đây là chỗ dễ hiểu lầm nhất. CRDT bảo đảm mọi bản sao hội tụ về cùng một kết quả. Nó không bảo đảm kết quả đó hợp ý người dùng.
Hai người cùng sửa một câu theo hai hướng khác nhau, kết quả có thể là một câu lai tạp vô nghĩa. CRDT chỉ hứa rằng ai cũng nhìn thấy đúng cái câu lai tạp ấy, chứ không hứa nó hay.
Với những thao tác cần bất biến toàn cục — như "số dư không được âm" hay "chỉ một người giữ chỗ này" — CRDT không giải quyết được. Những chỗ đó vẫn cần đồng thuận thật sự.
Khi nào nên dùng
- Hợp: ghi chú, danh sách việc, bảng vẽ, soạn thảo cộng tác, cấu hình đồng bộ nhiều thiết bị — nơi mất mạng là chuyện thường và trộn tự động tốt hơn bắt người dùng chọn
- Không hợp: giao dịch tiền bạc, đặt chỗ, tồn kho — nơi một kết quả sai là sai thật chứ không chỉ khó coi
- Cân nhắc: dữ liệu rất lớn hoặc sửa liên tục nhiều năm, vì lượng siêu dữ liệu đi kèm có thể vượt cả dữ liệu thật
Nếu bạn đang định tự hiện thực, hãy dùng thư viện có sẵn thay vì viết từ đầu. Phần khó không nằm ở ý tưởng — ý tưởng thì như bài này — mà nằm ở nén siêu dữ liệu, dọn bia mộ, và giữ hiệu năng khi tài liệu lớn dần.
Thảo luận