cola: Công nghệ CRDT văn bản cho chỉnh sửa cộng tác thời gian thực

 (nomad.foo)
1 điểm bởi GN⁺ 2023-09-04 | 1 bình luận | Chia sẻ qua WhatsApp
  • cola là một CRDT văn bản dành cho chỉnh sửa cộng tác thời gian thực, được viết bằng Rust, tập trung vào việc đưa tài liệu do nhiều peer chỉnh sửa đồng thời về cùng một trạng thái mà không cần bộ điều phối trung tâm
  • Thay vì dùng offset đơn giản, cola cố định vị trí trong tài liệu bằng Anchor dạng ReplicaId.n, tránh vấn đề ý nghĩa vị trí bị thay đổi do chỉnh sửa đồng thời
  • Xung đột chèn được xử lý nhất quán bằng Lamport timestamp và sắp xếp theo ReplicaId; thao tác xóa không loại bỏ thật mà dùng tombstone và version vector để quản lý điều kiện hợp nhất
  • Về triển khai, cola dùng RLE dựa trên EditRun và G-tree biểu diễn bằng chỉ mục Vec, nhằm đạt tìm kiếm/chèn thời gian log trong mô hình ownership an toàn của Rust
  • Trong benchmark, cola được so sánh với diamond-types, automerge, yrs; ở upstream, cola nhanh hơn diamond-types 1,4–2 lần và cũng cho hiệu năng rất nhanh ở downstream

Vấn đề chỉnh sửa cộng tác mà cola xử lý

  • cola là một CRDT văn bản viết bằng Rust, được thiết kế để nhiều bản sao hội tụ về cùng một trạng thái trong chỉnh sửa cộng tác thời gian thực mà không cần quyền lực trung tâm
  • Với tầng mạng, cola chỉ giả định tối thiểu rằng mọi chỉnh sửa cuối cùng sẽ đến được mọi peer
    • Chỉnh sửa có thể được gửi nhiều lần
    • Chỉnh sửa có thể đến theo thứ tự bất kỳ
    • Mọi peer cuối cùng phải nhận được mọi chỉnh sửa
  • Mục tiêu không chỉ là trạng thái tài liệu giống nhau sau khi nhận mọi chỉnh sửa, mà còn là tài liệu kết quả phải hợp lý từ góc nhìn người dùng

Cố định vị trí bằng Anchor thay vì offset

  • Chỉnh sửa dựa trên offset như insert "abc" at offset 8 có thể đổi nghĩa nếu peer khác đồng thời sửa vùng phía trước, khiến các bản sao bị tách trạng thái
  • cola tham chiếu vị trí tài liệu bằng định danh ổn định, không phải bằng nội dung ký tự hay offset
    • Mỗi peer gắn số tăng dần cho các ký tự mà nó chèn
    • Peer có định danh duy nhất là ReplicaId
    • Cặp ReplicaId.n trở thành định danh vị trí duy nhất của ký tự, gọi là Anchor
  • Giá trị n có thể đảm bảo tính duy nhất bằng cách tăng bộ đếm cục bộ, nhưng khó đảm bảo tính duy nhất toàn cục của ReplicaId nếu không có máy chủ trung tâm
    • cola giả định cách dùng số nguyên ngẫu nhiên rất lớn, tương tự UUID, sao cho xác suất va chạm có thể bỏ qua
  • Thao tác chèn chỉ định vị trí bằng một Anchor, còn thao tác xóa chỉ định phạm vi bằng hai Anchor bắt đầu và kết thúc

Sắp xếp xung đột chèn theo cùng một thứ tự

  • Khi nhiều thao tác chèn vào cùng một Anchor, cola quyết định thứ tự bằng Lamport timestamp
  • Lamport clock được cập nhật theo các quy tắc sau
    • Khi chèn văn bản cục bộ, tăng clock thêm 1
    • Khi nhận thao tác chèn từ xa, đặt thành max(current, remote_timestamp) + 1
  • Nếu một thao tác chèn A được tạo trong môi trường đã hợp nhất thao tác chèn B, Lamport timestamp của A sẽ lớn hơn B
  • Các thao tác chèn xung đột được sắp xếp theo Lamport timestamp giảm dần
  • Với các thao tác chèn đồng thời có cùng Anchor và cùng Lamport timestamp, không có thứ tự nào đúng hơn từ góc nhìn người dùng, nên cola sắp xếp theo ReplicaId tăng dần để đảm bảo nhất quán giữa các peer

Xóa được xử lý bằng tombstone và version vector

  • Thao tác xóa chuyển offset bắt đầu/kết thúc thành Anchor rồi truyền cho các peer khác
  • Nếu hai peer đồng thời xóa cùng một vùng, miễn là không xét undo, kết quả giống như chỉ xóa một lần
    • Hiện tại cola không hỗ trợ undo thao tác xóa
  • Xử lý xóa có ba điểm khó
    • Nếu loại bỏ hoàn toàn văn bản đã xóa, Anchor của những chỉnh sửa chưa đến có thể nằm trong vùng đó
    • Nếu hợp nhất thao tác xóa từ xa quá sớm, nội dung mà peer tạo thao tác xóa đã thấy có thể khác với nội dung của peer nhận, khiến các bản sao bị tách trạng thái
    • Ngay cả trong phạm vi xóa, không được xóa những ký tự mà peer tạo thao tác xóa chưa từng thấy
  • Vấn đề đầu tiên được giải quyết bằng tombstone
    • Ký tự đã xóa vẫn còn trong tài liệu nhưng được đánh dấu là đã xóa
    • Cách này làm tăng mức sử dụng bộ nhớ
  • Các vấn đề còn lại được giải quyết bằng cách đưa version vector vào thông điệp xóa
    • Khóa là ReplicaId, giá trị là timestamp của ký tự cuối cùng mà peer tạo thao tác xóa đã thấy tại thời điểm đó
    • Peer nhận chờ hợp nhất thao tác xóa cho đến khi version vector của nó lớn hơn hoặc bằng version vector trong thông điệp xóa
    • Những ký tự có timestamp lớn hơn timestamp trong version vector của thao tác xóa sẽ bị bỏ qua, không bị xóa
  • Trong cola, version vector được gọi là version map

Tách Replica khỏi bộ đệm văn bản

  • Trạng thái tài liệu cục bộ của mỗi peer được biểu diễn trong cola bằng Replica
  • Thuật toán CRDT của cola không cần biết nội dung chuỗi thực tế
    • Các hàm API không nhận chuỗi làm tham số
    • cola chỉ xử lý các khối số, không xử lý nội dung tài liệu
  • Thiết kế này tách cơ chế CRDT khỏi phần triển khai bộ đệm văn bản thực tế

Giảm metadata bằng RLE và EditRun

  • Vì gắn metadata cho từng ký tự khiến khó tạo triển khai hiệu năng cao, cola gom các khối có timestamp liên tiếp bằng run-length encoding
  • Ví dụ, nếu dán toàn bộ trang Manhattan Project của Wikipedia, nó có thể được biểu diễn dưới dạng một khối duy nhất thay vì 107.000 khối
  • Trường hợp nhập từng chữ một trong một câu mà không di chuyển con trỏ hay xóa cũng có thể được biểu diễn thành một run duy nhất, thay vì tạo một khối cho mỗi lần gõ phím
  • Trong cola, các khối liên tiếp này được gọi là EditRun
    • Một EditRun đã bị tách sẽ cố định trong suốt vòng đời tài liệu và không còn được mở rộng nữa
    • Run chưa bị tách vẫn ở trạng thái active
  • Nếu chèn văn bản vào giữa một EditRun hiện có, cola tách run đó thành hai và đưa văn bản mới vào giữa
  • Nếu xóa văn bản, cola tách phần tương ứng khỏi run và đánh dấu là tombstone
    • Run đã xóa cũng có thể được RLE theo cùng cách, giúp giảm gánh nặng bộ nhớ của tombstone

Từ linked list sang B-tree

  • Đường upstream của chỉnh sửa cục bộ là quá trình chuyển chỉnh sửa dựa trên offset thành chỉnh sửa có thể gửi cho peer khác
    • Cả chèn và xóa đều phải tìm run chứa offset để tạo Anchor
    • Nếu cần, run được tách tối đa thành 2 phần khi chèn và tối đa thành 3 phần khi xóa
  • Với linked list, việc tách run là O(1), nhưng để tìm run chứa offset phải quét từ đầu, nên mất thời gian tuyến tính
  • Cache run active hiện tại và offset của nó giúp nhanh hơn khi chỉnh sửa lặp lại ở cùng vị trí, nhưng trường hợp xấu nhất vẫn là tuyến tính
  • cola cân nhắc cấu trúc B-tree để đạt hiệu năng xấu nhất theo thời gian log
    • Run được biểu diễn như leaf của B-tree
    • inode lưu các con và tổng độ dài của các con
    • Tombstone run đóng góp độ dài 0
    • Độ dài của root bằng tổng độ dài tài liệu
  • B-tree có thể tìm kiếm và chèn trong O(log n), giúp xử lý chỉnh sửa cục bộ trong thời gian log
  • Tuy nhiên, để chuyển đổi Anchor -> run hiệu quả trong chỉnh sửa từ xa, cần tìm leaf chứa Anchor

G-tree: B-tree biểu diễn bằng chỉ mục Vec

  • Chỉ dùng con trỏ tới leaf của B-tree thông thường thì khó biết phải đi xuống leaf như thế nào trong quá trình chèn top-down
  • Các thao tác bottom-up cần con trỏ cha của từng node; trong mô hình ownership an toàn của Rust, điều này có thể cần cấu trúc như Rc<RefCell<_>>, khiến hệ thống chậm và phức tạp hơn
  • cola lưu mọi node trong một mảng động như Vec và biểu diễn tham chiếu giữa các node bằng chỉ mục thay vì con trỏ
    • Vector sở hữu toàn bộ node
    • Mỗi node có thể lưu chỉ mục cha
    • Có thể duyệt hai chiều mà không cần code unsafe
  • Cấu trúc này dựa trên giả định rằng chỉ mục node không thay đổi
    • Node mới được append vào cuối vector
    • Vì cola không loại bỏ run mà đánh dấu tombstone, nên không phát sinh vấn đề chỉ mục mất hiệu lực
  • Trong cola, cấu trúc tree-in-a-vector chỉ tăng trưởng này được gọi là G-tree
  • Mã Rust của G-tree là một dạng vẫn giữ cấu trúc cha-con của B-tree nhưng thay đổi biểu diễn bộ nhớ

Đặc tính hiệu năng do G-tree tạo ra

  • Giống B-tree, G-tree thực hiện tìm kiếm và chèn top-down trong thời gian log
  • LeafIdx, tức chỉ mục vector của leaf, có thể được dùng làm định danh leaf ổn định
  • Run active hiện tại có thể được cache bằng LeafIdx thay vì con trỏ
    • Khi chỉnh sửa lặp lại ở cùng vị trí con trỏ, cola mở rộng run active và chỉ cập nhật độ dài của các ancestor lên tới root
    • Việc này có thể được xử lý bằng vài phép so sánh số nguyên và 2–4 phép cộng số nguyên, không cần duyệt tree hay cấp phát mới
  • G-tree của cola dùng branching factor 32, với mức lấp đầy trung bình của inode khoảng 20 node con
    • Chỉ 4 cấp thường đã có thể lưu khoảng 160k EditRun khác nhau
    • Sau khi xử lý trace chỉnh sửa automerge-paper, G-tree của cola có khoảng 15k EditRun
    • Trace đó chứa 260k chỉnh sửa và được ghi lại trong vài ngày
  • Vì các node của G-tree đã được lưu trong bộ nhớ tuyến tính, việc serialize và deserialize cũng đơn giản

Chuyển Anchor thành LeafIdx

  • Đường downstream của chỉnh sửa từ xa là quá trình chuyển chỉnh sửa dựa trên Anchor như insert 2.3..7 at 1.2, delete between 3.4 and 2.2 thành chỉnh sửa theo offset trên tài liệu cục bộ
  • Vì G-tree có thể duyệt lên xuống, nếu biết LeafIdx của run chứa một Anchor thì có thể tính được offset tương ứng
  • Điểm cốt lõi là chuyển đổi Anchor -> LeafIdx
  • Một thiết kế đơn giản là có thêm G-tree hoặc B-tree phụ, trong đó leaf lưu ReplicaId, temporal range và LeafIdx của G-tree chính
    • Leaf được sắp xếp hoàn toàn theo ReplicaId và temporal range
    • Có thể đi xuống tree theo Anchor để tìm LeafIdx mong muốn
    • Cả tìm kiếm và chèn đều là O(log n)
  • Mã nguồn cola thực tế không dùng nguyên xi cách G-tree phụ này
    • Triển khai thực tế có tìm kiếm và chèn là O(log f)
    • f là số fragment mà EditRun chứa Anchor đã bị tách ra theo thời gian
    • f luôn nhỏ hơn hoặc bằng n và thường nhỏ hơn rất nhiều

Mức độ hoàn thiện hiện tại và việc còn lại

  • Thiết kế của cola có nền tảng hướng đến hội tụ, bảo toàn ý định và hiệu năng
  • Để sẵn sàng cho production, vẫn còn cần hỗ trợ undo/redo và một số công việc bổ sung

Benchmark CRDT Rust

  • cola được so sánh với 3 CRDT nền Rust
  • Benchmark đo thời gian xử lý trace chỉnh sửa thực tế theo từng ký tự
    • Dùng thư viện benchmark Rust criterion
    • Đo cả hai hướng upstream và downstream
    • Mã benchmark nằm ở crdt-benches
  • Đồ thị lấy 100 lần hiệu năng của cola làm đường cơ sở, và không hiển thị các giá trị đo chậm hơn cola từ 100 lần trở lên
  • Môi trường chạy là MacBook Pro 2018, Intel Core i7 6 nhân 2,2GHz
    • Trên máy khác, số liệu có thể thay đổi nhưng hiệu năng tương đối được cho là sẽ tương tự

Kết quả benchmark

  • Ở hướng upstream, yrs và automerge vượt qua đường cơ sở
  • Ở upstream, cola nhanh hơn diamond-types 1,4–2 lần
  • Ở hướng downstream, diamond-types crash trên tất cả trace nên không thu được số liệu đo
    • Có ghi chú rằng kết quả sẽ được cập nhật nếu nguyên nhân là do dùng thư viện sai cách
  • Ở downstream, cola chậm hơn trước khoảng 2 lần
    • Đây là kết quả được dự đoán, vì hợp nhất chỉnh sửa từ xa thường tốn kém hơn tạo chỉnh sửa cục bộ
  • Ở cả hai hướng, cola hoạt động ở mức tương đương hoặc nhanh hơn các thư viện rope nhanh, và hiện được đánh giá là triển khai CRDT văn bản nhanh nhất

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-04
Ý kiến trên Hacker News

  • Tôi vẫn xem G-tree là B-tree có thêm con trỏ cha
    Việc nó được lưu trong mảng chỉ là vấn đề cách biểu diễn, không làm thay đổi căn bản cấu trúc
    Nó vẫn lưu con trỏ, chỉ là theo đơn vị kích thước nút thay vì byte, và là vị trí tương đối so với phần tử đầu tiên của mảng thay vì điểm bắt đầu của không gian địa chỉ
    Ví dụ, một cây nhị phân hoàn chỉnh được lưu trong mảng mà không có tham chiếu tường minh, trong đó các con của chỉ mục x nằm ở 2x + 1 và 2x + 2, cũng chỉ là biểu diễn ngầm định, và ta vẫn gọi nó là cây nhị phân

    • Dù vậy, nói về cách biểu diễn vẫn hữu ích
      Đặc biệt là trong các ngôn ngữ khuyến khích dùng tham chiếu tương đối và tự quản lý thay vì tham chiếu tuyệt đối
      Một cách biểu diễn cây mà tôi thấy thú vị là lưu các nút vào một mảng phẳng theo thứ tự duyệt theo chiều sâu
      Nếu là dữ liệu chỉ đọc và người đọc dù sao cũng định duyệt theo chiều sâu, cách này có thể khá hiệu quả
      Làm tôi nghĩ đến S-expression và HTML

  • Nếu tôi không bỏ sót gì trong API, có vẻ nó không hỗ trợ phạm vi định dạng như in đậm, in nghiêng
    Theo tôi biết, trong các thuật toán CRDT cho văn bản giàu định dạng, Peritext hiện vẫn là hiện đại nhất https://www.inkandswitch.com/peritext/
    Sẽ rất hay nếu dự án này cũng lấy được các tính năng văn bản giàu định dạng của thuật toán Peritext

    • Với tư cách là người có theo dõi đôi chút lĩnh vực CRDT, tôi luôn tự hỏi liệu có thể tạo ra một CRDT dữ liệu có cấu trúc tổng quát hơn không
      Tức là một cách để người dùng định nghĩa mô hình hoặc schema mô tả các trạng thái hợp lệ về mặt ngữ nghĩa
      Ví dụ, nếu chỉ hợp nhất JSON thì có thể tạo ra trạng thái hợp lệ về cú pháp nhưng vô nghĩa về ngữ nghĩa
      Giống như thuật toán Peritext biết rằng in đậm, in nghiêng, gạch chân là các phép toán có thể cộng dồn còn màu highlight thì không, tôi nghĩ sẽ tốt nếu người dùng có thể khai báo trong schema rằng state: notStarted và completionDate: 2023-09-04 không thể cùng tồn tại
    • Câu hỏi: bài viết nói Cola chỉ xử lý chỉnh sửa không xung đột đối với các kiểu dữ liệu mà nó không biết, thực chất chỉ xử lý luồng ký tự và vị trí
      Vậy chẳng phải có thể biểu diễn chính phần định dạng bên trong văn bản như HTML sao?
      Tôi không quá rành các cách biểu diễn văn bản giàu định dạng khác nên cũng không chắc
      Ngoài ra, khi xem tài liệu Peritext được liên kết ở trên, tôi thấy nó xử lý đúng các khó khăn riêng của RTF như vậy, và đọc khá thú vị

  • Có khác biệt gì về hiệu năng hay tính năng so với Automerge hoặc Y.js/Yrs không?

    • “Phần thứ ba” của bài viết bắt đầu bằng câu “chúng tôi đã benchmark cola với ba CRDT khác được triển khai bằng Rust là diamond-types, automerge, yrs”
      Thư viện cola này có vẻ khá có lợi thế về tốc độ thao tác
      Tôi cũng tò mò về mức dùng bộ nhớ

  • Đừng nhầm với công trình cùng tên của Ian Piumarta
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • Hoặc còn có Cache Oblivious Lookahead Arrays, từng được xem là lựa chọn thay thế cho MergeTree(LSM) nhưng hiện không còn được dùng https://github.com/giannitedesco/cola
    • Cũng có một ứng dụng kiểu bản sao Notion tên là coda.io

  • Công trình được làm tốt, nhưng không giống một benchmark công bằng
    Nó không tính rồi lưu các thao tác, cũng không lưu văn bản thực tế
    Nếu muốn tạo một CRDT văn bản hỗ trợ cập nhật delta trên nền này, người dùng sẽ phải lưu OpID => Text trong một cấu trúc riêng, và chi phí này không hề rẻ

  • Dùng crate slotmap (https://docs.rs/slotmap/latest/slotmap/) có thể hỗ trợ xóa mà không phải lo chỉ mục bị dịch chuyển hay “chỉ mục” trỏ sang giá trị khác
    Trong slotmap, chúng được gọi là khóa, và khóa cũng chứa cả số phiên bản

    • Liệu nó có hoạt động trong ngữ cảnh CRDT không?
      Tôi tò mò vì việc xác định thứ tự khó, và phiên bản có thể chỉ có ý nghĩa cục bộ

  • Tôi đang định thử dùng cái này cho một dự án mà Etherpad và Word không kham nổi

  • Nếu giả định rằng mọi client đã kết nối đều nhận mọi chỉnh sửa, chẳng phải có thể đặt hash dự kiến của trạng thái văn bản hiện tại trước offset và các lệnh chèn/xóa/thay thế sao?
    Như vậy gần như có thể đảm bảo chỉnh sửa chỉ được áp dụng vào trạng thái phù hợp, và các thay đổi sau đó có thể được tích lũy trong một dictionary dùng “hash của trạng thái dữ liệu được kỳ vọng sẽ áp dụng” làm khóa
    Tất nhiên chi phí sẽ lớn vì phải tính hash lặp lại trên cùng dữ liệu, nhưng cách này rất đơn giản để hiểu và triển khai

    • Với cách đó, chỉnh sửa bất đồng bộ sẽ không bao giờ được áp dụng
      Nếu tôi chỉnh sửa cục bộ tài liệu, còn bạn thực hiện chỉnh sửa từ xa, thì hash “trạng thái dự kiến” của bạn từ đó trở đi sẽ không bao giờ khớp với trạng thái tài liệu của tôi
      Vì tôi đã thực hiện thay đổi cục bộ rồi
      Để CRDT đảm bảo hội tụ, đúng là mọi client phải nhận mọi chỉnh sửa, nhưng thuộc tính không cần áp dụng cập nhật theo một thứ tự cụ thể mới là điều quan trọng trong các trường hợp sử dụng phân tán thực tế

  • Tôi tò mò liệu có cách nào dễ dàng bật cộng tác chỉnh sửa biểu mẫu trong trình duyệt không
    Sẽ rất hay nếu hai người mở cùng một trang hoặc biểu mẫu thì có thể thấy người kia hiện đang chỉnh sửa trường nhập nào, và các trường nhập văn bản dùng CRDT văn bản
    Tôi đã thử triển khai thứ tương tự bằng Yjs, nhưng khá khó và không hoạt động tốt

    • Tôi tò mò vì sao Yjs không phù hợp
      Nó trông rất hợp cho mục đích đó mà