CRDT nhanh hơn gấp 5000 lần (2021)

CRDT nhanh hơn gấp 5000 lần: cuộc phiêu lưu tối ưu hóa

Mở đầu

• Vài năm trước, các nhà nghiên cứu Pháp đã công bố một bài báo so sánh các thuật toán chỉnh sửa cộng tác theo thời gian thực
• Họ đã triển khai nhiều thuật toán và benchmark hiệu năng
• Một số thuật toán mất hơn 3 giây chỉ cho một thao tác dán đơn giản
• Thuật toán có vấn đề là thuật toán từng được dùng trong ShareJS

Nguyên nhân của vấn đề

• Trong bài báo, khi dán văn bản lớn, họ đã chia nó thành 1000 thao tác riêng lẻ để xử lý
• Đây không phải vấn đề của bản thân thuật toán mà là vấn đề của cách triển khai

Sức hấp dẫn của CRDT

• CRDT (Conflict-Free Replicated Data Types) cho phép nhiều người dùng cùng lúc chỉnh sửa dữ liệu
• Có thể làm việc cục bộ mà không có độ trễ, và khi đồng bộ thì tự động duy trì tính nhất quán
• Có thể hoạt động ngay cả khi không có máy chủ trung tâm

Vấn đề của Automerge

• Automerge là một thư viện cho chỉnh sửa cộng tác, dựa trên thuật toán RGA
• Mỗi ký tự trong tài liệu được quản lý bằng một ID duy nhất, và khi chèn thì chỉ định mục cha
• Vì vấn đề hiệu năng, việc xử lý 260.000 thao tác chỉnh sửa mất tới 5 phút
• Mức sử dụng bộ nhớ cũng rất cao

Tối ưu hóa hiệu năng

• Vấn đề hiệu năng của Automerge đến từ cấu trúc dữ liệu dựa trên cây phức tạp và việc dùng Immutablejs
• Yjs sử dụng một danh sách phẳng duy nhất để cải thiện hiệu năng đáng kể
• Yjs dùng bộ nhớ đệm để tìm vị trí chèn, và dùng danh sách liên kết đôi để xử lý việc chèn hiệu quả
• Yjs nhanh hơn 30 lần và cũng dùng ít bộ nhớ hơn

Chuyển sang Rust

• Rust cho phép kiểm soát bố cục bộ nhớ, nhờ đó có thể cải thiện hiệu năng hơn nữa
• Thông qua một triển khai CRDT mới có tên Diamond types, tác giả đạt hiệu năng nhanh hơn Yjs 5 lần
• Diamond được triển khai bằng Rust xử lý 260.000 thao tác chỉnh sửa chỉ trong 56 mili giây

Kết luận

• Có thể cải thiện mạnh hiệu năng của CRDT bằng cấu trúc dữ liệu được tối ưu hóa và quản lý bộ nhớ hiệu quả
• Dùng ngôn ngữ mức thấp như Rust có thể đạt hiệu năng còn cao hơn

Tóm tắt của GN⁺

• CRDT là tương lai của chỉnh sửa cộng tác, một công cụ mạnh có thể duy trì tính nhất quán mà không cần máy chủ trung tâm
• Vấn đề hiệu năng của Automerge bắt nguồn từ cấu trúc dữ liệu phức tạp và việc sử dụng bộ nhớ kém hiệu quả
• Yjs và Diamond types cải thiện hiệu năng đáng kể nhờ dùng các cấu trúc dữ liệu đơn giản và hiệu quả
• Dùng ngôn ngữ mức thấp như Rust có thể đạt hiệu năng nhanh hơn nữa
• Khi phát triển công cụ chỉnh sửa cộng tác, đáng để cân nhắc Yjs và Diamond types

[GN⁺]

Ý kiến trên Hacker News

• Lý do 32 entry là hiệu quả nhất là vì cache line có kích thước 64 byte

  • Nếu dùng số nguyên 2 byte, 32 entry sẽ vừa khít đúng một cache line, giúp giảm truyền tải từ bộ nhớ chính

• Rất khó tìm được ví dụ về các ứng dụng thực tế dùng CRDTs mà mang lại trải nghiệm tốt

  • Notion kém tiện dụng hơn Google Docs khi hai người cùng viết ghi chú đồng thời

• CRDTs rất mạnh, nhưng có nhược điểm là để lại các thao tác lịch sử (hoặc phần tử)

  • Ngay cả khi dùng nén, đây vẫn là một nhược điểm và gây lo ngại cho việc áp dụng
  • Dù vậy, vẫn thấy hứng thú với khả năng các nhà cung cấp lưu trữ dựa trên tệp (Dropbox, Syncthing, v.v.) có thể triển khai thuật toán không xung đột

• Trích dẫn Readme hiện tại trên GitHub:

  • Hiệu năng đã tăng 10-80 lần kể từ bài đăng blog đó

• Bài viết này dù nội dung khó nhưng được viết rất hay, đến mức không thể ngừng đọc

• Thấy họ dùng cấu trúc phân cấp nên tự hỏi tại sao không dùng nested sets thay thế

  • Không rõ lợi ích ở thao tác đọc có thể bù lại tổn thất ở thao tác chèn hay không

• Đã tình cờ phát hiện bài đăng này vài năm trước

  • Đây là một trong những bài viết thú vị nhất từng đọc trong vài năm gần đây

• Tò mò vì sao WASM lại chậm hơn thực thi native 4 lần

  • Nghĩ là vì mọi thao tác với chuỗi đều phải sao chép vào bộ nhớ WASM, rồi sau khi tính toán xong lại sao chép ngược về JS
  • Không chắc mình có đang hiểu sai ngữ cảnh này hay không

• Vì bản triển khai Automerge bằng Rust đã hoàn thành, sẽ rất thú vị nếu được xem benchmark đã cập nhật