CRDT cây có thể di chuyển và cách Loro triển khai

 (loro.dev)
2 điểm bởi GN⁺ 2024-07-30 | 1 bình luận | Chia sẻ qua WhatsApp

  • Movable tree CRDTs and Loro's implementation

  • Bối cảnh

    • Trong hệ thống phân tán và phần mềm cộng tác, việc quản lý các quan hệ phân cấp rất phức tạp
    • Khi mô hình hóa thao tác di chuyển bằng cách kết hợp xóa và chèn trong cấu trúc dữ liệu, rất khó để vừa giải quyết xung đột vừa đáp ứng kỳ vọng của người dùng
    • Ví dụ, nếu cùng một nút bị di chuyển đồng thời sang các nút cha khác nhau, có thể tạo ra các nút trùng lặp với cùng nội dung

  • Xung đột trong cây có thể di chuyển

    • Các thao tác chính của cây có thể di chuyển: tạo, xóa, di chuyển
    • Các xung đột có thể phát sinh khi đồng bộ các thao tác đồng thời:
      • Cùng một nút vừa bị xóa vừa bị di chuyển
      • Cùng một nút bị di chuyển xuống dưới các nút khác nhau
      • Các nút khác bị di chuyển gây ra vòng lặp
      • Nút tổ tiên bị xóa trong khi nút hậu duệ bị di chuyển
  • Xóa và di chuyển cùng một nút
    • Tương đối dễ giải quyết
    • Tùy theo dấu thời gian trong hệ thống phân tán hoặc các yêu cầu cụ thể của ứng dụng, có thể áp dụng một thao tác và bỏ qua thao tác còn lại
  • Di chuyển cùng một nút xuống dưới các nút cha khác nhau
    • Việc hợp nhất các thao tác di chuyển đồng thời phức tạp hơn
    • Tùy ứng dụng có thể áp dụng nhiều cách tiếp cận khác nhau:
      • Xóa nút rồi tạo một bản sao dưới nút cha khác
      • Cho phép nút được liên kết với hai nút cha (thường không được phép)
      • Sắp xếp tất cả thao tác và áp dụng tuần tự
  • Vòng lặp phát sinh do di chuyển các nút khác
    • Việc xử lý vòng lặp do các thao tác di chuyển đồng thời gây ra là bài toán phức tạp
    • Có nhiều cách giải quyết:
      • Phát sinh lỗi
      • Hiển thị các nút trong vòng lặp ở một vùng "timeout" đặc biệt
      • Xử lý thao tác di chuyển trên máy chủ
      • Dùng sắp xếp topo
      • Ẩn cạnh gây ra vòng lặp
  • Xóa nút tổ tiên và di chuyển nút hậu duệ
    • Việc di chuyển nút hậu duệ khi nút tổ tiên bị xóa là trường hợp dễ bị bỏ sót
    • Nếu xóa trực tiếp toàn bộ nút hậu duệ, người dùng có thể hiểu nhầm là mất dữ liệu

  • Cách các ứng dụng phổ biến xử lý xung đột

    • Dropbox: xử lý di chuyển tệp như xóa rồi tạo lại, nhưng có rủi ro mất dữ liệu
    • Figma: máy chủ trung tâm phát hiện vòng lặp và từ chối thao tác để giữ tính nhất quán

  • CRDT cây có thể di chuyển

    • Sử dụng CRDT thay vì giải pháp tập trung
    • Các thuật toán CRDT ban đầu khó triển khai và có overhead lưu trữ lớn
    • Nhờ tối ưu hóa liên tục, một số thuật toán đồng bộ cây dựa trên CRDT đã trở nên phù hợp cho môi trường production

  • Thao tác di chuyển có tính sẵn sàng cao cho cây được sao chép

    • Hợp nhất ba thao tác của cây (tạo, xóa, di chuyển) thành thao tác di chuyển
    • Thao tác di chuyển được định nghĩa là Move t p m c
    • Việc xóa nút được xử lý bằng cách di chuyển nó vào nút TRASH
  • Dấu thời gian logic được sắp thứ tự toàn cục
    • Sử dụng dấu thời gian Lamport để xác định thứ tự nhân quả của sự kiện trong hệ thống phân tán
    • Số nhỏ hơn biểu thị sự kiện xảy ra sớm hơn
  • Áp dụng thao tác từ xa
    • Tính an toàn của thao tác phụ thuộc vào trạng thái của cây tại thời điểm áp dụng
    • Khi xử lý cập nhật từ xa, hệ thống sẽ hoàn tác các thao tác gần đây, chèn thao tác mới rồi áp dụng lại các thao tác đã hoàn tác

  • CRDT: phân cấp cây có thể thay đổi

    • Mỗi nút theo dõi mọi nút cha trong lịch sử và gán bộ đếm cho chúng
    • Khi đồng bộ tạo ra vòng lặp, nút sẽ được gắn lại vào nút cha lịch sử gần nhất

  • Triển khai CRDT cây có thể di chuyển trong Loro

    • Triển khai thuật toán của Martin Kleppmann để cung cấp hiệu năng cao
    • Tích hợp thuật toán Fractional Index để sắp xếp các nút con

  • Xung đột tiềm ẩn khi sắp xếp nút con

    • Khi chèn nhiều nút vào cùng một vị trí, có thể chúng được gán cùng Fractional Index
    • Dùng PeerID để xác định thứ tự tương đối của các nút có cùng Fractional Index

  • Triển khai và kích thước mã hóa

    • Fractional Index cung cấp thứ tự cho các nút
    • Kích thước mã hóa trong trường hợp xấu nhất có thể cần thêm byte, nhưng đây là tình huống hiếm

  • Công việc liên quan

    • Ngoài Fractional Index còn có CRDT danh sách có thể di chuyển
    • Fractional Index đơn giản trong triển khai và hữu ích khi chỉ cần thứ tự tương đối

  • Benchmark

    • Đã thực hiện benchmark hiệu năng cho triển khai cây có thể di chuyển của Loro
    • Có thể hỗ trợ cộng tác thời gian thực và checkout mượt mà các phiên bản lịch sử

  • Tóm tắt

    • Giới thiệu độ khó trong việc triển khai CRDT cây có thể di chuyển và hai thuật toán đổi mới
    • Loro tích hợp thuật toán của Martin Kleppmann và Fractional Index để đáp ứng nhiều kịch bản ứng dụng khác nhau

  • Tổng kết của GN⁺

    • CRDT cây có thể di chuyển đóng vai trò quan trọng trong việc quản lý cấu trúc dữ liệu phân cấp trong hệ thống phân tán
    • Loro cung cấp hiệu năng cao và khả năng xử lý xung đột hiệu quả, phù hợp cho các ứng dụng cộng tác thời gian thực
    • Sử dụng Fractional Index để giải quyết bài toán sắp xếp nút con
    • Các dự án khác có tính năng tương tự gồm Figma và Dropbox

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-30
Ý kiến trên Hacker News

  • Đang phát triển một trình soạn thảo nhiều người chơi mới

    • Hỗ trợ làm việc với văn bản và outliner
    • Tài liệu được chuyển thành một cấu trúc cây lớn
    • Đồng bộ bằng thao tác insmov (di chuyển hoặc chèn)
    • Khi máy chủ gửi thay đổi, client áp dụng lại chúng
    • Trong hầu hết trường hợp không cần hoàn tác thao tác
    • Gần như không phát sinh vấn đề khi cập nhật thời gian thực

  • Cung cấp React Table Library dưới dạng mã nguồn mở

    • Xử lý cấu trúc cây thư mục/tệp
    • Hỗ trợ di chuyển, sao chép, tải lười cho thư mục/tệp, v.v.
    • Giờ đã hiểu vì sao Google Drive chỉ hiển thị và chỉnh sửa trong cùng một cấp phân cấp

  • Xin lời khuyên

    • Đang dùng một cây lớn đã phi chuẩn hóa ở frontend
    • Quản lý hồ sơ người dùng bằng bố cục dạng ô
    • Chỉ truyền lượng dữ liệu tối thiểu để cập nhật an toàn
    • Có vẻ việc quản lý trạng thái sẽ dễ hơn nhiều nếu dùng CRDT
    • Có thể đồng bộ giữa các tab trình duyệt

  • Khi làm việc với nội dung văn bản có định dạng như Google Docs/Zoho Writer, cần thao tác trên cây

    • Khó giải quyết vấn đề xung đột đồng thời
    • Có vẻ có thể kết hợp list CRDT và tree CRDT
    • Cần thêm địa chỉ 2 chiều cho mọi thao tác

  • Tò mò không biết có CRDT thực tiễn nào cho các ứng dụng đậm đặc dữ liệu như hình ảnh (pixel) và mô hình 3D hay không

  • Nghĩ rằng đoạn đầu tiên nghe giống giọng văn của ChatGPT