Tôi đã sai. CRDT mới là tương lai.

 (josephg.com)
24 điểm bởi xguru 2020-10-05 | 10 bình luận | Chia sẻ qua WhatsApp

Câu chuyện về Conflict-free Replicated Data Types do một nhà phát triển Google Wave kể lại

→ CRDT: cấu trúc dữ liệu hỗ trợ chỉnh sửa đồng thời trong các công cụ cộng tác thời gian thực

  • Wave dựa trên OT (Operational Transform): lưu danh sách theo thứ tự thời gian của mọi thay đổi. Giống như git rebase thời gian thực

  • Một trong những vấn đề của OT là cần máy chủ/DB tập trung

→ Có lẽ đây là lý do Google Docs (cũng dựa trên OT) hiện thông báo kiểu “Tài liệu này đang quá tải nên không thể chỉnh sửa” khi có quá nhiều người cùng vào một tài liệu?

Quảng cáo

→ Có thể né tránh bằng cách chia nhỏ tài liệu hoặc dùng vòng lặp retry cho DB transaction (tức là đẩy vấn đề serialization sang DB)

→ Nhưng vẫn không hoàn hảo. Wave cho phép nhiều người chỉnh sửa đồng thời và nhìn chung hoạt động được, nhưng có rất nhiều bug. Quá phức tạp

  • Sự trỗi dậy của CRDT

→ Thuật toán mà Wave dùng được phát minh từ năm 1995. Người ta đã tiếp tục nghiên cứu để OT hoạt động tốt hơn, nhưng CRDT có triển vọng hơn nhiều

→ CRDT chọn một cách tiếp cận khác, cho phép chỉnh sửa thời gian thực mà không cần DB trung tâm

→ Tốc độ/dung lượng/tính năng/độ phức tạp, những thứ từng bị xem là vấn đề, giờ đều đã được cải thiện

Quảng cáo

  • Tốc độ: các CRDT hiện nay (Automerge / RGA hoặc y.js / YATA) có thể truy vấn ở mức log(n)

  • Dung lượng: mã hóa Columnar của Martin có thể lưu ở kích thước khoảng 1.5~2 lần kích thước tài liệu

  • Tính năng: về mặt lý thuyết có thể rewinding và replaying. Tất nhiên, vẫn chưa có ai hiện thực hóa điều này

  • Độ phức tạp: kích thước implementation của CRDT có thể lớn hơn OT, nhưng chênh lệch không nhiều

→ Những cải tiến trên sẽ sớm được cung cấp trong Automerge

Quảng cáo
  • Trong chỉnh sửa thời gian thực, đáng tiếc nhưng các công việc liên quan đến OT có lẽ sẽ không còn cần thiết nữa

→ Mọi tính năng của OT đều có thể đưa vào CRDT, nhưng chiều ngược lại thì không thể

→ Ưu điểm của OT là phù hợp với phần mềm tập trung, nhưng thuật toán phân tán cũng hoạt động tốt ngay cả trong mô hình tập trung

→ Một CRDT chất lượng cao chạy trên WASM sẽ nhanh hơn implementation OT bằng JS

  • Đã đến lúc tạo ra những CRDT nhẹ và nhanh.

→ Phần học thuật gần như đã hoàn thiện, và giờ là lúc cần những implementation thật xuất sắc

Bài viết liên quan

10 bình luận

 
hackerwins 2020-10-05

Tôi là Hong Young-taek, đang phát triển dự án Yorkie.

Kho lưu trữ tài liệu Yorkie dành cho các ứng dụng chỉnh sửa cộng tác theo thời gian thực cũng được xây dựng dựa trên CRDT.

https://github.com/yorkie-team/yorkie
 
iolothebard 2020-10-05

Tôi đã sai. CRDT mới là tương lai.

Với OT thì có thể “ăn sẵn” undo/redo được... còn CRDT thì dường như chẳng có cách nào ngoài snapshot...
 
xguru 2020-10-05

Trong trường hợp như Automerge, bản thân thư viện cũng hỗ trợ undo/redo. Người triển khai thì có lẽ sẽ thấy khó, nhưng ở góc độ người dùng thư viện thì cũng ổn thôi haha
 
ffdd270 2020-10-05

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

Trước đó mình đã dịch toàn văn rồi mà quên đăng lên ;m; Mình đọc lại dựa trên bản của Papago và chỉ chỉnh những chỗ nghe chưa tự nhiên. Nếu ai muốn xem thử cảm giác tổng thể ra sao khi đọc thì hãy xem ở link bên trên nhé~

Đăng trực tiếp trong khung bình luận thì... dài quá ;m; nên mình cung cấp bằng link Notion.
 
ffdd270 2020-10-05

Nghĩ lại thì có lẽ Notion cũng đang dùng CRDT đấy nhỉ!
 
xguru 2020-10-05

Những thứ dùng OT là Google Wave/Google Docs/MS Office365

Những thứ dùng CRDT là Figma/Apple Notes cũng như Riak/Redis, v.v.
 
xguru 2020-10-05

Tôi đã sai. CRDT mới là tương lai.

Công nghệ đa người dùng của Figma hoạt động như thế nào https://vi.news.hada.io/topic?id=814
 
xguru 2020-10-05

Video "CRDTs: The Hard Parts" của Martin Kleppmann, một trong những nhà phát triển Automerge được liên kết trong bài, giải thích thực sự rất hay.

Ở phần đầu, video so sánh và giải thích rất tốt giữa OT và CRDT. Phần sau đi sâu vào câu chuyện triển khai CRDT.

https://www.youtube.com/watch?v=x7drE24geUw

Thư viện CRDT dùng khi tạo công cụ cộng tác bằng JS
 
xguru 2020-10-05

Tôi đã sai. CRDT mới là tương lai.

Hướng tới hệ thống cộng tác: từ thuật toán OT sang hệ thống CRDT

https://deview.kr/2013/detail.nhn?topicSeq=66

Trong số các bài thuyết trình trong nước, đây gần như là nội dung duy nhất đề cập đến CRDT.
 
hackerwins 2020-10-06

Ngài Hyun-geol, người đã thực hiện bài thuyết trình này, chính là người đã tạo ra RGA được nhắc đến trong bài.

Yorkie cũng đã triển khai kiểu dữ liệu dạng danh sách dựa trên RGA.

https://github.com/yorkie-team/yorkie/issues/2