- Khi Moment đánh giá tính năng chỉnh sửa cộng tác cho trình soạn thảo văn bản cốt lõi, họ nhận thấy các thuật toán họ CRDT và OT có thể tạo ra kết quả hợp nhất mà người dùng dễ xem là hỏng dữ liệu trong các trường hợp xung đột trực tiếp khi ngoại tuyến
- Ngay cả trong tình huống đơn giản khi Alice xóa toàn bộ câu còn Bob đổi
ColorthànhColour, tài liệu cuối cùng vẫn có thể chỉ còn lại ký tựu, tức là một kết quả ngoài ý định của con người - Trong các trường hợp sử dụng của Moment, khoảng 20–30% các xung đột trực tiếp được thử cho ra kết quả khó chấp nhận, và do tần suất xuất hiện cùng phản ứng tiêu cực, họ cho rằng rất khó bảo vệ điều này trong trải nghiệm sản phẩm
- Yjs, ShareJS và Peritext đều quảng bá khả năng hỗ trợ chỉnh sửa ngoại tuyến, cộng tác với độ trễ dài, hoặc tự động hợp nhất các bản sao độc lập, nhưng các thuật toán này không thể biết ý định hay thứ tự của người dùng nên phải dựa vào heuristic
- Chỉnh sửa cộng tác ngoại tuyến không chỉ là vấn đề của thuật toán mà gần hơn với một vấn đề UI/UX, cần một trải nghiệm hợp nhất mà con người có thể đọc và tự đánh giá, như UI hợp nhất của git hay collaborative history của Ink & Switch
Giới hạn bộc lộ qua quá trình đánh giá chỉnh sửa cộng tác của Moment
- Đầu năm 2024, Moment bắt đầu khảo sát các hệ thống chỉnh sửa cộng tác để dùng cho trình soạn thảo văn bản cốt lõi
- Nhiều thuật toán tuyên bố không chỉ giải quyết việc chỉnh sửa đồng thời khi trực tuyến, mà còn cả trường hợp ngoại tuyến nơi người dùng chỉnh sửa không giới hạn thời gian khi mất kết nối rồi tự động hợp nhất thay đổi khi trở lại trực tuyến
- Khi mới đọc các bài báo và phần trình bày, họ từng kỳ vọng cộng đồng chỉnh sửa cộng tác đã đi đến “câu trả lời đúng” cho toàn bộ vấn đề này
- Trong quá trình đánh giá, các thuật toán họ CRDT và OT xử lý những xung đột chỉnh sửa trực tiếp theo cách thiếu trực quan, và người dùng xem kết quả đó là hỏng dữ liệu
- Vì chỉnh sửa ngoại tuyến làm tăng mạnh khả năng xảy ra xung đột trực tiếp, chỉ dùng các thuật toán như vậy khiến Moment khó có thể tạo ra trải nghiệm chỉnh sửa ngoại tuyến như mong muốn
Một ví dụ đơn giản: xóa và sửa chính tả xung đột với nhau
- Alice và Bob đều chỉnh sửa cùng một tài liệu trong trạng thái ngoại tuyến
- Tài liệu có đoạn văn bản
The Color of Pomegranates - Bob đổi cách viết
Colorsang kiểu Anh làColour, còn Alice xóa toàn bộ văn bản - Khi cả hai lên mạng trở lại, hai chỉnh sửa sẽ xung đột và hệ thống phải điều phối chúng mà không biết chỉnh sửa nào xảy ra trước
- Trong trường hợp này, Alice và Bob cuối cùng nhận được một tài liệu chỉ chứa ký tự
u- Đây không phải là một câu hợp lệ, cũng không phải là một từ hợp lệ
- Người dùng sẽ hiểu kết quả như vậy là Moment đã làm hỏng dữ liệu của họ
Kết quả kỳ lạ từ xung đột trực tiếp không hề hiếm
- Đây là một xung đột chỉnh sửa nhỏ và trực tiếp, nhưng vẫn nằm trong phạm vi mà các thuật toán chỉnh sửa cộng tác phổ biến có thể được xem là hỗ trợ
- Kết quả thực tế là một tài liệu mà con người sẽ không tự viết ra, và vì vậy bị hiểu là sản phẩm Moment đã làm hỏng dữ liệu
- Tùy từng trường hợp sử dụng, khoảng 20–30% các xung đột trực tiếp mà Moment thử tạo ra kết quả khó chấp nhận trong bối cảnh chỉnh sửa ngoại tuyến
- Xét cả phản hồi tiêu cực lẫn tần suất xảy ra, họ kết luận rất khó giải thích và bảo vệ những kết quả như vậy với người dùng
Những công cụ hiện có quảng bá hỗ trợ chỉnh sửa ngoại tuyến
- Ban đầu, khi thấy các kết quả như vậy, họ tưởng rằng mình đã hiểu sai ý nghĩa mà các công cụ này cung cấp
- Tuy nhiên, mô tả của từng dự án đều có thể được đọc theo hướng rằng kịch bản này nằm trong phạm vi hỗ trợ
- Yjs nêu rõ trong README rằng họ hỗ trợ
offline editing - ShareJS nói rằng có thể cộng tác ở mọi mức độ trễ, từ độ trễ bằng 0 cho tới những khoảng dài như một kỳ nghỉ dài
- Peritext nói rằng người dùng có thể chỉnh sửa các bản sao độc lập của tài liệu và tự động hợp nhất theo cách cố gắng bảo toàn tối đa ý định của người dùng
- Yjs nêu rõ trong README rằng họ hỗ trợ
- Moment vẫn đang tìm lời giải cho vấn đề này, nhưng họ thấy khó dung hòa tần suất và kiểu lỗi mình quan sát được với các tuyên bố đó
Giới hạn căn bản của các thuật toán không có bước điều phối
- Khi quá trình đánh giá tiếp diễn, họ đi đến kết luận rằng các thuật toán này không cho ra hành vi mà Moment mong muốn
- Câu hỏi còn lại là đây có phải vấn đề có thể sửa bằng cách đóng góp thêm, hay là giới hạn căn bản của chính thuật toán
- Họ cho rằng đây là vấn đề căn bản vì ba lý do
- Thuật toán không thể biết ý định của Alice và Bob, cũng không thể gửi email hỏi họ muốn gì hay cho họ xem xét như giao diện GitHub Pull Request
- Nó phải nhận đề xuất xóa toàn bộ của Alice và đề xuất sửa chính tả của Bob rồi quyết định kết quả bằng heuristic
- Nó hoạt động ở cấp ký tự và chỉ đưa ra những đảm bảo rất yếu cho đầu ra
- Nếu Alice và Bob biết người kia đang làm gì, họ có thể đã quyết định chỉnh sửa theo cách khác
- Những thuật toán này cũng gắn với vấn đề không thể tuân theo thứ tự nhân quả
Chỉnh sửa ngoại tuyến gần hơn với một bài toán UI/UX
- Moment từng kỳ vọng rằng nếu triển khai được một thuật toán đủ tinh vi thì có thể tiện thể hỗ trợ chỉnh sửa ngoại tuyến thực sự, nhưng sau quá trình đánh giá họ không còn thấy điều đó khả thi
- Việc người dùng xem kết quả thuật toán là hỏng dữ liệu là hoàn toàn hợp lý; các kết quả bất thường là một phần của chính thuật toán và xảy ra đủ thường xuyên để trở thành vấn đề thực tế
- Một cách diễn giải khác là chỉnh sửa cộng tác đòi hỏi đầu tư đáng kể về nguồn lực UI/UX
- Thuật toán không thể giải quyết trọn vẹn vấn đề, nhưng vẫn có thể là một phần của lời giải
UI hợp nhất của git và hướng nghiên cứu
gitlà một UI hợp nhất tài liệu đã được chấp nhận rộng rãi- Câu hỏi nghiên cứu gần hơn với việc làm sao để trải nghiệm này dễ tiếp cận hơn, dễ hiểu hơn và có thể tự động hóa hơn đến mức nào
- Vào khoảng năm 2009, đã có nhiều thảo luận về thuật toán mà git dùng để tự động hợp nhất thay đổi
- git sử dụng Myers O(ND) diff algorithm, một thuật toán vốn chủ yếu được các nhà sinh học dùng cho phân tích chuỗi kiểu BLAST
- Bram Cohen cho rằng kết quả diff không trực quan nên đã tạo ra patience diff algorithm, và thuật toán này được dùng trong bzr, công cụ cạnh tranh với git nay đã ngừng phát triển
- Khi đó, thảo luận tập trung vào việc tạo ra diff mà con người có thể đọc được; còn hiện nay, câu hỏi gần hơn với việc liệu thuật toán có thể đạt được kết quả đó mà không cần con người can thiệp hay không
- Các nghiên cứu như Ink & Switch với collaborative history đang tiếp cận chỉnh sửa cộng tác như một vấn đề UI/UX
1 bình luận
Ý kiến trên Hacker News
Tôi là tác giả của Eg-walker và ShareJS. Bài viết có vẻ như mang giọng điệu phản đối công việc của tôi, nhưng thật ra tôi hoàn toàn đồng ý và cũng đã nói điều tương tự trên HN từ vài năm trước
Các công cụ cộng tác thời gian thực hiện nay hoạt động tốt khi mọi người cùng chỉnh sửa trực tuyến, nhưng nếu người dùng chỉnh sửa ngoại tuyến hoặc trên các nhánh tồn tại lâu, thì khi merge cần có hiển thị xung đột và tùy chọn rà soát thủ công. Đặc biệt là với code
May mắn là các thuật toán như egwalker lưu lại dấu vết chỉnh sửa ở cấp ký tự của mọi người dùng cùng thứ tự nhân quả, tức thứ tự thay đổi giống như Git DAG, nên có nhiều thông tin hơn Git rất nhiều. Vì vậy, lẽ ra có thể tạo một CRDT phát hiện và hiển thị phạm vi xung đột khi merge nhánh, rồi để người dùng tự xử lý
Đây là một bài toán thú vị về mặt thuật toán nhưng có vẻ hoàn toàn giải được, và kỳ lạ là dường như trong mảng chỉnh sửa văn bản hầu như chưa ai thử làm. Nếu muốn có một đóng góp độc đáo và giá trị cho lĩnh vực này, đây là một mảnh ghép quan trọng còn thiếu trong hệ sinh thái CRDT, nên tôi mong ai đó sẽ thử
[1] Phần bên dưới của bình luận này: https://news.ycombinator.com/item?id=19889174
Thử thách thú vị tiếp theo là khi có xung đột xoay quanh chính việc giải quyết xung đột
Bản thân việc đánh giá các hệ thống như vậy đã là một vấn đề kỹ thuật đủ khó, nên tôi nghĩ nhiều nhóm sẽ gặp khó khăn. Vì thế họ xứng đáng nhận được lời khuyên thực dụng, và tôi cũng cảm thấy giá như chúng ta biết những điều này sớm hơn
Phần khó là đánh dấu rằng xung đột đã được giải quyết. Có thể chỉ đơn giản là thêm một trường vào CRDT, nhưng khi đó tôi không rõ có nên xem nó là giải pháp thuật toán hay không
[1] https://josephg.com/blog/crdts-go-brrr/
Nếu là chỉnh sửa mã chương trình, bạn sẽ kỳ vọng kết quả merge là một chương trình hợp lệ, nên câu chuyện sẽ đi sâu hơn rất nhiều. Tôi nghe nói JetBrains từng có một dự án cố giải quyết vấn đề này bằng merge dựa trên AST, nhưng sau khi đào sâu hơn rất nhiều, họ kết luận rằng nó không đáng làm
Với tài liệu do con người viết, “chỉnh sửa ngoại tuyến” được phép chỉ nên là thêm bình luận. Không phải chỉnh sửa, cũng không tự động merge
Với “chỉnh sửa ngoại tuyến” của mã nguồn, thứ là đối tượng của tự động hóa, ta dùng Git; Git không giả vờ rằng nó giải quyết merge, mà chỉ hiển thị các revision. Merge là việc do con người giám sát hoặc do tự động hóa chuyên biệt thực hiện theo ước đoán tốt nhất, và việc xác nhận thành công vẫn cần review và test
Các thuật toán merge cơ học có thể làm tốt hơn hoặc kém hơn tùy loại xung đột, nhưng rốt cuộc không CRDT nào có thể phán đoán văn bản đã merge có đúng là điều người dùng muốn nói hay không
Bài báo Upwelling bàn kỹ hơn về khác biệt giữa thứ mà họ gọi là xung đột ngữ nghĩa và xung đột ngữ pháp trong viết lách: https://inkandswitch.com/upwelling/
Tôi cảm thấy cộng tác nghiêm túc rốt cuộc cũng là một vấn đề review tài liệu. Điều này đặc biệt đúng trong báo chí hoặc xuất bản khoa học, còn với biên bản họp thì phần lớn có thể bỏ qua
Tôi cũng định liên kết tới Upwelling, nhưng không nhớ ra tên nên vì sát hạn tôi đã thay bằng liên kết khác
Một mặt tối khác của triển khai CRDT là tải hạ tầng. Trước đây tôi từng viết khá sâu về chuyện này[0], và tôi rất vui khi biết Supabase cũng đi đến kết luận giống các kết quả thực nghiệm của tôi trong bài viết về extension CRDT cho Postgres[1] vài năm trước
Nếu định dùng CRDT, tốt hơn nên dùng thứ gì đó như Redis, hoặc dù nghĩ đến mức dùng bộ nhớ cũng thấy đau đầu, hãy dùng MyRocks[2] hay nền tảng dựa trên RocksDB/LevelDB. Dù làm gì, đừng đặt RDBMS, đặc biệt là Postgres, làm backend
[0]: https://news.ycombinator.com/item?id=40834759
[1]: https://supabase.com/blog/postgres-crdt
[2]: http://myrocks.io
Nhận xét trong bài này là chính xác. CRDT là một mô hình hình thức tuyệt vời cho cấu trúc dữ liệu phân tán, nhưng tôi luôn thấy không thoải mái với ý tưởng rằng mọi xung đột phải được tự động giải quyết, đúng như cái tên kiểu dữ liệu sao chép không xung đột
Như bài viết cho thấy, tôi nghĩ đây là một nỗ lực không có triển vọng. Điều cần thiết là một biểu diễn cấu trúc đúng đắn để có thể chia sẻ xung đột và giải quyết bằng cộng tác, trao lại quyền kiểm soát cho người dùng và hỗ trợ quá trình giải quyết. Một trong những bài báo tôi thích, “Turning Conflicts into Collaboration” [1], bàn về ý tưởng này rất thuyết phục
Trong nghiên cứu tiến sĩ đang thực hiện, tôi đã phát triển “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2], một mô hình hình thức cho biểu diễn xung đột có cấu trúc dựa trên lý thuyết dàn. Tình cờ nó cũng là CRDT, nhưng không cố tự động giải quyết xung đột mà biểu diễn chúng bên trong tài liệu cộng tác. Khi tiếp cận bằng toán học, tôi đã đi đến một mô hình khái niệm đơn giản có thể bảo đảm các tính chất mạnh như tính đầy đủ, tối thiểu và duy nhất của phép merge, ngay cả sau các xung đột cũ đã được merge lặp lại; việc tính toán merge cũng rất dễ
[1] https://doi.org/10.1007/s10606-012-9172-4
[2] https://doi.org/10.14279/tuj.eceasst.82.1226
Xung đột là một khái niệm phức tạp, và “conflict-free” về mặt kỹ thuật là đúng để mô tả kết quả, nhưng như bài viết này và nội dung phía trên cho thấy, nó có thể gây hiểu lầm
Tính giao hoán là thuộc tính rằng Bob áp dụng thay đổi theo thứ tự [Bob, Alice] còn Alice áp dụng theo thứ tự [Alice, Bob] thì cả hai vẫn đi đến cùng một tài liệu. Nó không có nghĩa là tài liệu “không xung đột” theo một cách có ý nghĩa ở mức trừu tượng cao hơn
Tôi cho rằng khái niệm nhiều chủ thể khác nhau đồng thời có quyền trên cùng một mẩu dữ liệu mà không điều phối thời gian thực nhìn chung là không thể giải quyết được. Đây là bài học đã biết trong hệ thống phân tán, và khi nghĩ đến chỉnh sửa tài liệu phân tán thì bài này cũng thể hiện rất rõ điều đó
Có lẽ cùng nguyên lý cũng áp dụng cho nhập liệu kép trong buồng lái máy bay, nuôi dạy con cái và những ví dụ khác có thể nghĩ ra
Và gọi việc này là “có thể giải được” cũng buồn cười, vì ở thời điểm hiện tại có vẻ một phần lớn thế giới đang nghĩ rằng đầu ra hỗn độn của LLM có thể gần như quyết định kết quả cuối cùng của phép tính
CRDT và OT, các thuật toán thường dùng cho chỉnh sửa văn bản cộng tác, có những yêu cầu đại số nghiêm ngặt về việc các thao tác chỉnh sửa làm gì và tương tác với nhau ra sao
Vì vậy, ngay cả khi máy chủ đủ thông minh để xử lý ví dụ “Colour” theo cách hợp lý về UX, việc thiết kế CRDT/OT tương ứng cho chỉnh sửa phía client theo kiểu lạc quan vẫn rất khó
Có thể đi vòng bằng cách không dùng CRDT/OT. Ví dụ, máy chủ xử lý các thao tác theo thứ tự nhận được và áp dụng logic UX mong muốn, còn client dùng chiến lược rebase/dự đoán phía trên để cho phép chỉnh sửa lạc quan. Tham khảo: https://doc.replicache.dev/concepts/how-it-works
Áp dụng điều này cho chỉnh sửa văn bản cũng có khó khăn, nhưng đó là vấn đề riêng với các vấn đề CRDT/OT đang được bàn ở đây
Tôi nghĩ chuyện này xảy ra vì các khái niệm xung đột về mặt toán học, nhân quả và entropy bị trộn lẫn với xung đột ngữ nghĩa. Trước đây tôi cũng từng mắc sai lầm tương tự theo chiều ngược lại, rồi bị nói thẳng rằng tôi không biết mình đang nói gì
Khi bắt đầu xét đến cây thì mọi thứ còn lộn xộn hơn nhiều. Ví dụ yJS hoạt động trên tài liệu JSON. Nếu UI chỉ hiển thị mức nông và không mở rộng các mức sâu, người dùng có thể hoàn toàn không thấy phần chỉnh sửa đã bị xóa
Một loại CRDT bảo toàn xung đột — nếu tôi nhớ đúng thì trường hợp thanh ghi có thể có nhiều giá trị — có vẻ khả thi nhất. Người dùng cần được trình bày những xung đột như vậy, và thậm chí có thể hiển thị hoàn toàn bằng hình ảnh. Cho phép duyệt lịch sử cũng có vẻ là một phương án thực tế để người dùng hiểu chuyện kỳ lạ đã xảy ra như thế nào, hoặc thay đổi của họ đã biến mất ra sao
Tôi nhớ rằng bản thân Torvalds cũng khá bi quan về những gì có thể đạt được bằng tự động merge. Và nhận định đó là đúng
Git từng nói rằng họ bác bỏ ý tưởng rằng một hệ thống quản lý phiên bản có thể, hoặc nên, “giải quyết bài toán merge” theo kiểu một thuật toán đủ thông minh sẽ tự động làm đúng việc cần làm
Tôi đồng ý rằng chỉnh sửa ngoại tuyến là một vấn đề UI/UX. Nguyên nhân sâu xa hơn là thói quen của ngành điện toán trong việc đi theo các lời giải cũ, và niềm tin rằng “vì nói chung bao 5 pound dễ xử lý hơn bao 10 pound, nên ta phải nhét 10 pound đồ vào một bao 5 pound”
Hình mẫu cơ bản của “trình soạn thảo văn bản” là textarea của Mosaic, MacWrite, hoặc đâu đó ở giữa, nên thường người ta cố gắng gắn merge lên trên nó với ít thay đổi nhất. Kiểu như làm bằng một mục menu hoặc vài tùy chọn trong một hộp thoại nhỏ. Ngay cả khi có hỗ trợ merge bằng GUI nằm sâu trong menu, nó cũng chỉ ở mức câu chuyện kinh dị diff/merge dành cho lập trình viên, hoặc một view dựa trên gạch ngang đầy chông chênh như lái tàu trong sương mù
Nhưng trong trình soạn thảo văn bản có cộng tác ngoại tuyến, merge bán thủ công là trung tâm của quy trình, và cũng phải nằm ở trung tâm thiết kế của trình soạn thảo. Không may là MacWrite là một điểm tối ưu cục bộ rất khó thoát ra
Ví dụ, điều người nói về “bắt chước kiểu cargo cult” và “lời giải cũ” thường nói tiếp là “đừng chỉnh sửa code như văn bản, hãy chỉnh sửa nó như cây cú pháp”, nhưng vấn đề vẫn y nguyên. Chỉ cần thay “ký tự” bằng “câu” là xong
Nếu Bob thêm một dòng vào nhánh
elsecủa câu lệnhif, còn Alice xóa cả câu lệnh bao gồm cả nhánhelse, thì một hệ thống thông minh nên làm gì?Nhìn chung có vẻ là tôi đồng ý rằng cách tiếp cận này là đúng
Tôi sẵn sàng nhận câu hỏi hoặc phản hồi. Một hai tiếng tới tôi sẽ phải vào họp, nhưng tôi rất thích nói về những chuyện này. Gửi ở đây hoặc qua email, tùy cách nào tiện cho bạn: alex@moment.dev
Git không tự động trộn các thay đổi cục bộ vào nếu không có sự đồng ý rõ ràng. bzr hẳn cũng không mơ đến chuyện đó. Nhưng những thứ như Google Docs thì sẵn sàng làm vậy
Tiến triển đến giờ rất tuyệt, và tôi cũng chúc chương trình truy cập sớm diễn ra tốt đẹp
Tôi đã triển khai differential sync(https://neil.fraser.name/writing/sync/). Vì tôi không hiểu các cách khác, và với ứng dụng grugnotes.com thì cách này trông đơn giản nhất
Ứng dụng còn khá thô và cũng không hoàn toàn realtime, nhưng phần merge trong ví dụ được xử lý đúng bất kể ai online trở lại trước. Nếu thao tác xóa online trước, phiên bản
coloursẽ bị bỏ đi và cũng không được lưu trong lịch sử chỉnh sửaChắc còn nhiều vấn đề hơn, và tôi cũng không biết với hơn hai người dùng thì sẽ thế nào, nhưng với nhu cầu của tôi thì tôi hài lòng