- Giới thiệu một cách tiếp cận mới để giải quyết bài toán chỉnh sửa văn bản cộng tác, có thể hiện thực mà không cần thuật toán phức tạp
- Tránh độ phức tạp và các ràng buộc của CRDT và OT truyền thống, sử dụng cách chèn đơn giản dựa trên ID
- Cách này có độ linh hoạt cao vì máy chủ xử lý bằng cách được chỉ định trực tiếp "chèn gì vào đâu"
- Giải quyết vấn đề đồng bộ trạng thái bằng chiến lược server reconciliation để hỗ trợ cập nhật cục bộ lạc quan
- Với khả năng mở rộng và dễ hiểu, cách làm này đưa ra một phương án thay thế có thể triển khai trực tiếp cho việc phát triển ứng dụng cộng tác hiện có
Collaborative Text Editing without CRDTs or OT
Đặt vấn đề
- Chỉnh sửa văn bản cộng tác là một tính năng rất khó, đặc biệt khi chỉnh sửa đồng thời sẽ phát sinh vấn đề lệch chỉ mục văn bản (index rebasing)
- Hai cách tiếp cận hiện có là CRDT (kiểu dữ liệu sao chép không xung đột) và OT (operational transformation), mỗi cách đều dựa trên các mô hình toán học riêng
- CRDT: theo dõi từng ký tự bằng ID và sắp xếp dựa trên cây
- OT: điều chỉnh động chỉ mục để phản ánh thao tác nhập của người dùng khác
- Cả hai cách đều phụ thuộc nhiều vào thư viện và khó tùy biến theo nhu cầu riêng của nhà phát triển
Cách tiếp cận mới
Ý tưởng cốt lõi
- Mỗi ký tự được gắn một ID duy nhất (UUID), và client gửi cho server lệnh “hãy chèn ký tự nào đó sau ID nào đó”
- Ví dụ: "insert ' the' after
f1bdb70a" → f1bdb70a là ID của ký tự dùng làm mốc chèn
- Server diễn giải và chèn đúng theo chỉ định đó, nhờ vậy tránh được xung đột
Xử lý xóa
- Khi xóa ký tự, ID tương ứng vẫn được giữ lại trong danh sách nội bộ và được đánh dấu bằng cờ isDeleted
- Nó không còn hiển thị trong văn bản người dùng nhìn thấy, nhưng tham chiếu vẫn được giữ để có thể thao tác về sau
Xử lý phía client và cập nhật lạc quan
- Người dùng cần thấy kết quả ngay sau khi nhập, vì vậy thay đổi sẽ được áp dụng cục bộ trước khi có phản hồi từ server (cập nhật lạc quan)
- Sử dụng chiến lược server reconciliation để:
- Hoàn tác toàn bộ các thao tác cục bộ chưa xác nhận
- Áp dụng thao tác từ server
- Áp dụng lại các thao tác cục bộ để đảm bảo trạng thái đồng bộ cuối cùng
Khác biệt với các cách tiếp cận hiện có
- CRDT bao hàm thuật toán tự động sắp xếp ID, còn cách này chỉ truyền cho server vị trí chèn được chỉ định tường minh
- Kết quả là đơn giản hơn và có được cơ chế hoạt động rõ ràng hơn
Xử lý chèn đồng thời
- Ví dụ: trong “My name is”, hai người dùng cùng lúc chèn “ Charlie” và “ Dave” vào cùng một vị trí
- Tùy theo thứ tự server nhận được, kết quả có thể là “My name is Dave Charlie”
- Điều này được xem là tự nhiên, và không xảy ra hiện tượng xen kẽ theo từng ký tự (interleaving) như ở một số cách làm CRDT
Hỗ trợ thao tác linh hoạt
- Ngoài insert/delete cơ bản còn có thể hỗ trợ nhiều thao tác khác:
- insert-before
- chèn có điều kiện (chỉ thêm “u” nếu tồn tại “color”)
- điều chỉnh vị trí khi drag & drop, v.v.
- Sự linh hoạt này không bị ràng buộc bởi các tính chất toán học cố định
Hỗ trợ rich text (văn bản có định dạng)
- Có thể áp dụng định dạng bằng cách định nghĩa phạm vi dựa trên ID (“in đậm từ ID X đến ID Y”, v.v.)
- Khi tích hợp với editor như ProseMirror, có thể xử lý xung đột theo cách đơn giản
- Có thể bổ sung tính năng rich text mà vẫn giữ nguyên cấu trúc cơ bản
Phiên bản phân tán (Decentralized)
- Ngay cả khi không có server trung tâm, nếu xác định thứ tự thao tác bằng dấu thời gian Lamport thì vẫn có thể hoạt động theo cùng cách
- Trong trường hợp này, kết quả tương tự các CRDT như RGA, Peritext, Fugue
- Ngay cả khi không có cây hay chứng minh toán học, vẫn có thể đạt được mức nhất quán tương đương CRDT
Thư viện hỗ trợ: Articulated
- Thư viện để xử lý hiệu quả cấu trúc
Array<{ id, isDeleted }>
- Dùng cấu trúc
{ bunchId, counter } thay cho UUID để tối ưu bộ nhớ
- Cấu trúc dựa trên B+Tree hỗ trợ tìm ID và chèn nhanh
- Là cấu trúc dữ liệu persistent nên rất phù hợp với server reconciliation
Kết luận
- Cách tiếp cận này dễ hiểu và có thể tự triển khai hơn so với CRDT/OT
- Có thể tự do áp dụng nhiều tính năng chỉnh sửa, quyền hạn, ràng buộc và định dạng, nên phù hợp hơn cho việc xây dựng editor cộng tác thực tế
- Thư viện Articulated được cung cấp như một công cụ giúp hiện thực hóa cách tiếp cận này
1 bình luận
Ý kiến trên Hacker News
Thuật toán này trông khá hay. Nó mô tả cách gắn một ID duy nhất toàn cục cho từng ký tự, chẳng hạn UUID, để có thể tham chiếu nhất quán bất kỳ lúc nào; client báo cho server rằng cần chèn ký tự sau một ID cụ thể, rồi server xử lý việc chèn tại vị trí đó; việc xóa chỉ bị ẩn khỏi màn hình nhưng vẫn được giữ lại nội bộ để phục vụ tham chiếu vị trí; cũng có thể hình dung cách này được áp dụng không chỉ cho chỉnh sửa văn bản mà còn cho các lĩnh vực khác như đồng bộ hóa thế giới game
Có quan điểm cho rằng điểm khác với CRDT nằm ở chỗ server trung tâm đảm nhận việc đồng bộ như sắp thứ tự, nên không cần gán sẵn thứ tự vào cấu trúc dữ liệu thực tế; vì chỉ có giao tiếp giữa client và server, server có thể xử lý toàn bộ phép toán cục bộ của client trước rồi mới gửi cập nhật từ xa
Có ý kiến ngạc nhiên vì không thấy nói gì về các cấu trúc dữ liệu khác như dict/map hay mảng của kiểu tùy ý; trên thực tế, ứng dụng thường cần nhiều cấu trúc dữ liệu cộng tác đa dạng hơn là chỉ chỉnh sửa văn bản thuần túy; có nhiều ví dụ thú vị như xác thực dữ liệu, tải từng phần, hay các thao tác mức cao hơn, và họ cho rằng lý do những tính năng đó chưa có trong Yjs, v.v. không hẳn do bản thân CRDT mà vì vốn dĩ chúng đã khó triển khai
Có người rất đồng tình với chuyện nhiều cấu trúc dữ liệu; khi tạo mảng các object “atomic”, nếu không thể thay đổi thuộc tính của object thì chỉ cần đổi kiểu thay vì dùng string, còn thay đổi bên trong object chỉ là bài toán duyệt/lưu cây nên phức tạp hơn một chút; họ cũng kỳ vọng phía người dùng thư viện helper có thể gắn logic “semantic model” riêng như hook để ngăn các trạng thái sai, ví dụ một todo vừa có
isDone: truevừa cóstate: inProgress; bối cảnh này tương tự phần rich text formatting được nhắc trong bài viết được liên kếtCRDT hợp nhất bằng cách chọn một phía theo phương thức nhất quán khi có xung đột, nhưng vấn đề là kết quả có thể gây mất dữ liệu hoặc tạo ra dữ liệu không hợp lệ; hãy tưởng tượng conflict khi
git mergeluôn được giải quyết bằng cách chỉ chọn một bên, thì phần lớn sẽ cho ra kết quả sai hoặc lỗi biên dịch; họ chỉ ra rằng chỉ dựa vào giải quyết tự động thì tính nguyên bản và ý nghĩa của dữ liệu có thể không được bảo toàn đầy đủ, và nghĩ đó là lý do CRDT vẫn chưa được dùng rộng rãiCó người nói họ thấy bài giải thích về cách tiếp cận này rất thú vị, bản thân cũng đã dùng cách tương tự từ lâu và thấy lạ vì gần như không được nhắc đến trong học thuật; họ cho biết mình đã triển khai nó thành CRDT trong môi trường phi tập trung để giữ được các thuộc tính như kết hợp, bất biến và hoán đổi được
Có người thử tóm tắt thông điệp của bài gốc là: chỉ khi không có server trung tâm thì mới thực sự cần đến CRDT/OT phức tạp phải không
Có ý kiến cho rằng ngay cả khi không có server trung tâm, nếu trong mô hình phân tán vẫn có cách thống nhất và áp dụng thứ tự toàn cục của các thao tác thì vẫn có thể tránh được độ phức tạp của CRDT/OT; họ giới thiệu bài viết được liên kết; tất nhiên đây cũng là một dạng CRDT, theo nghĩa tổng quát hơn, nhưng việc triển khai undo/replay không hề dễ, và khi cảm thấy cấu trúc CRDT/OT truyền thống quá phức tạp thì đây là một lựa chọn đáng cân nhắc
Có nhắc rằng OT (Operational Transformation) cần một server trung tâm
Về bản chất thì nó vẫn là CRDT, chỉ khác ở chỗ server trung tâm quyết định thứ tự các thao tác áp dụng lên tài liệu; Google Docs và Zoho Writer cũng dùng OT + server trung tâm; người này thừa nhận cách tiếp cận được nêu mang phong cách CRDT nhưng trên thực tế lại thực dụng hơn đối với các dịch vụ dựa trên server trung tâm
Có ý kiến cho rằng khác biệt chính với các CRDT như Automerge nằm ở cách server điều phối; Automerge sắp xếp các lần chèn đồng thời theo thứ tự đã xác định của sequence number và agent ID, còn cách tiếp cận này thì server xử lý theo đúng thứ tự nhận được; họ trích ý trong bài viết được dẫn: “không cần các thuật toán fancy nên đơn giản hơn”; nhiều dịch vụ đằng nào cũng dùng server trung tâm nên cách này có vẻ thực tế, nhưng vì khi server điều phối thì cần undo/replay các chỉnh sửa cục bộ nên khó chắc nó có thực sự đơn giản hơn bao nhiêu
Có bình luận rằng “rewind/replay” cũng là một cách tiếp cận fancy, và Persistent B+Tree cũng đâu có đơn giản đến thế
Có giải thích rằng Automerge rốt cuộc cũng có thể tạo ra thứ tự toàn cục ở bên trong, nhưng trên thực tế vẫn xử lý thao tác văn bản theo kiểu CRDT truyền thống như RGA; lý do là undo/replay không hề đơn giản
Có cảm giác đây là một CRDT chưa được tối ưu, kiểu như đặt max set size=1 rồi cứ thế dùng, như một câu đùa
Có lo ngại rằng nếu dùng server reconciliation thì bài toán merge ở phía client có thể trở nên khó; họ hỏi làm sao giữ UX của editor mượt mà khi cập nhật từ server đến tuần tự, ví dụ nếu yêu cầu chèn thất bại thì có retry không, và nếu trong lúc đó đã có cập nhật khác tới thì phải làm sao; phương án được gợi ý là tua ngược lịch sử chỉnh sửa rồi áp dụng lại, hoặc chờ rồi flush queue; từ góc nhìn frontend, có vẻ tồn tại khá nhiều edge case UI/UX chưa được nêu rõ, và vì thế CRDT đôi khi lại có thể đơn giản hơn; họ đặc biệt tò mò trải nghiệm người dùng sẽ ra sao trong môi trường mạng không ổn định, chẳng hạn trên tàu điện ngầm
Có người đề xuất thử dùng LLM, chẳng hạn model 4b, để giải quyết các xung đột merge vượt ra ngoài những trường hợp đơn giản mà không cần dùng CRDT hay OT phức tạp; tuy có thể kém hiệu quả về năng lượng, nhưng biết đâu lại hoạt động tốt hơn mong đợi
CharlievàDavesauistrong câuMy name is, có người thắc mắc LLM sẽ hợp nhất như thế nào