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
  • Khi chỉnh sửa đồng thời cấu trúc phân cấp trong phần mềm cộng tác, có thể phát sinh xung đột cây như nút trùng lặp, vòng lặp, hoặc di chuyển nút con của tổ tiên đã bị xóa; Loro triển khai việc này bằng movable tree CRDT
  • Cách tiếp cận của Martin Kleppmann và cộng sự hợp nhất tạo, xóa, di chuyển thành Move t p m c, và xử lý xóa như một lần di chuyển vào nút TRASH, nhờ đó bảo toàn việc di chuyển đồng thời các nút con
  • Thứ tự toàn cục được tạo bằng Lamport Timestamp và Peer ID; khi thao tác từ xa được chèn vào giữa thứ tự hiện có, hệ thống dùng undo-do-redo để tránh tạo vòng lặp
  • Loro kết hợp Fractional Index để sắp xếp các nút cùng cấp; nếu chỉ mục bị trùng do chèn đồng thời vào cùng vị trí, hệ thống xử lý bằng PeerID, jitter và đặt lại chỉ mục
  • Trong benchmark, Loro Movable Tree tạo 1000 nút rồi thực hiện ngẫu nhiên 10000 lần di chuyển trong 28ms, cho thấy hiệu năng đủ cho cộng tác thời gian thực và checkout phiên bản trước đó

Xung đột phát sinh trong cây cộng tác

  • Khi quản lý quan hệ phân cấp trong hệ thống phân tán và phần mềm cộng tác, nếu mô hình hóa thao tác di chuyển như tổ hợp của xóa và chèn, kỳ vọng của người dùng và cách giải quyết xung đột rất dễ lệch nhau
  • Khi cùng một nút bị di chuyển đồng thời sang các nút cha khác nhau trên nhiều replica, một nút có thể bị xóa hai lần rồi được tạo lại dưới hai nút cha, dẫn đến các nút trùng lặp có cùng nội dung
  • Các thao tác cơ bản của cây có thể di chuyển gồm ba loại: tạo, xóa, di chuyển
  • Các tình huống thường gây vấn đề khi đồng bộ gồm:
    • cùng một nút bị xóa đồng thời với lúc bị di chuyển
    • cùng một nút bị di chuyển đến dưới các nút cha khác nhau
    • các lần di chuyển của những nút khác nhau kết hợp lại tạo thành vòng lặp
    • nút con bị di chuyển trong khi nút tổ tiên đang bị xóa

Cách xử lý theo từng loại xung đột

  • Khi xóa và di chuyển của cùng một nút xung đột, tùy theo timestamp của hệ thống phân tán hoặc yêu cầu của ứng dụng mà có thể áp dụng một thao tác và bỏ qua thao tác còn lại
  • Khi cùng một nút bị di chuyển đến dưới các nút cha khác nhau, lựa chọn sẽ khác nhau tùy ứng dụng
    • Xóa nút rồi tạo các bản sao dưới những nút cha khác nhau, sau đó xem chúng là độc lập
    • Có thể cho một nút trỏ tới hai nút cha, nhưng điều này phá vỡ cấu trúc cây nên nhìn chung khó chấp nhận
    • Nếu sắp xếp toàn bộ thao tác rồi áp dụng theo thứ tự, có thể tạo ra cùng một kết quả trên mọi peer
  • Khi các lần di chuyển của các nút khác nhau tạo thành vòng lặp, việc giải quyết xung đột của cây có thể di chuyển trở nên đặc biệt phức tạp
    • Matthew Weidner đã tổng hợp các cách như xử lý lỗi, render vùng “time-out”, từ chối dựa trên máy chủ, sắp xếp topo rồi bỏ qua thao tác tạo vòng lặp, ẩn một số edge khi render, hoặc khôi phục về nút cha trước đó
  • Tình huống nút con bị di chuyển trong lúc nút tổ tiên bị xóa cũng rất dễ bị bỏ sót
    • Nếu xóa ngay toàn bộ nút con của tổ tiên, người dùng có thể hiểu lầm rằng dữ liệu của mình đã bị mất

Cách tiếp cận của Dropbox và Figma

  • Ban đầu Dropbox xử lý việc di chuyển tệp như hai bước: xóa ở vị trí cũ rồi tạo ở vị trí mới
    • Nếu xảy ra mất điện hoặc crash hệ thống giữa hai bước xóa và tạo, sẽ có rủi ro mất dữ liệu
    • Hiện nay, khi nhiều người cùng lúc cố di chuyển và lưu cùng một tệp, hệ thống sẽ phát hiện xung đột, thường lưu một phiên bản của tệp gốc rồi tạo “conflicted copy” cho thay đổi của một người dùng
  • Figma xem cấu trúc cây là phần phức tạp nhất trong hệ thống cộng tác và gắn thuộc tính parent cho mỗi phần tử
    • Máy chủ trung tâm giám sát cập nhật từ nhiều người dùng, và nếu thao tác nào có thể tạo vòng lặp thì sẽ từ chối thao tác đó
    • Do độ trễ mạng, vòng lặp có thể tạm thời xuất hiện trước khi máy chủ từ chối
    • Trong trường hợp này, Figma sẽ tạm thời ẩn các phần tử nằm trong vòng lặp và giữ nguyên trạng thái cho đến khi máy chủ chính thức từ chối thao tác
    • Có thể xem thêm phần giải thích liên quan trong bài viết về công nghệ multiplayer của Figma

Hai hướng tiếp cận movable tree CRDT

  • Thay vì giải pháp tập trung, có thể dùng CRDT để xử lý cấu trúc cây cộng tác
  • Các thuật toán cây dựa trên CRDT ban đầu khó triển khai và có overhead lưu trữ lớn, nhưng qua tối ưu hóa và cải tiến, đã xuất hiện những thuật toán đồng bộ cây phù hợp với một số môi trường production
  • Có hai hướng tiếp cận tiêu biểu dựa trên CRDT

Cách của Kleppmann: hợp nhất mọi thao tác thành Move

  • A highly-available move operation for replicated trees hợp nhất tạo, xóa và di chuyển của cây thành một thao tác move duy nhất
  • Thao tác move được định nghĩa bằng bốn giá trị Move t p m c
    • t: timestamp duy nhất và có thể sắp xếp, như Lamport timestamp
    • p: ID nút cha
    • m: metadata gắn với nút
    • c: ID nút con
  • Nếu cây chưa có c, đây sẽ là thao tác tạo nút con c dưới nút cha p
  • Nếu c đã tồn tại, đây sẽ là thao tác di chuyển từ nút cha cũ sang nút cha mới p
  • Việc xóa được xử lý bằng cách di chuyển vào nút TRASH được chỉ định
    • Mọi nút con của TRASH được xem là đã bị xóa
    • Tuy vậy, chúng vẫn được giữ trong bộ nhớ để các chỉnh sửa đồng thời có thể di chuyển nút đó sang nơi khác
    • Đây là cơ chế để xử lý tình huống xóa nút tổ tiên và di chuyển nút con diễn ra đồng thời

Sắp thứ tự và unsafe operation

  • Vì xóa cũng được định nghĩa là một thao tác move, nên “xóa và di chuyển cùng một nút” trở thành xung đột giữa hai thao tác move
  • Hai vấn đề cốt lõi còn lại là:
    • di chuyển cùng một nút đến dưới các nút cha khác nhau
    • di chuyển các nút khác nhau để tạo vòng lặp
  • Nếu sắp toàn bộ thao tác theo thứ tự tuyến tính bằng Lamport timestamp và Peer ID, thì ngay cả việc di chuyển đồng thời cùng một nút cũng được biểu diễn thành hai thao tác có thứ tự
  • Khi mô hình hóa cây chỉ bằng thao tác move, các tình huống ngoại lệ trong chỉnh sửa đồng thời được thu gọn về việc tạo vòng lặp
  • Các thao tác tạo vòng lặp được xem là unsafe operation
    • Thuật toán sắp xếp toàn bộ thao tác move theo thứ tự timestamp
    • Phát hiện vòng lặp trước khi áp dụng từng thao tác
    • Nếu thao tác tạo vòng lặp, hệ thống sẽ bỏ qua unsafe operation đó để giữ cấu trúc cây hợp lệ

Lamport Timestamp và áp dụng thao tác từ xa

  • Lamport Timestamp giúp xác định thứ tự nhân quả của các sự kiện trong hệ thống phân tán
    • Mỗi peer có một bộ đếm bắt đầu từ 0
    • Khi có sự kiện cục bộ, bộ đếm tăng thêm 1 và giá trị đó được dùng làm timestamp
    • Khi peer A gửi thông điệp cho B, nó đính kèm timestamp
    • B so sánh timestamp nhận được với đồng hồ logic của mình và cập nhật lên giá trị lớn hơn
  • Việc sắp thứ tự toàn cục trước tiên so sánh Lamport Timestamp, và nếu bằng nhau thì dùng ID duy nhất của peer làm tie-breaker
  • Khi một cập nhật từ xa được chèn vào giữa chuỗi thao tác đã sắp xếp, cần dùng undo-do-redo
    • Hoàn tác các thao tác gần đây
    • Chèn và áp dụng thao tác mới
    • Áp dụng lại các thao tác đã hoàn tác
  • Để hoàn tác nhanh thao tác move, hệ thống cache old parent của nút đích trước khi áp dụng từng move
  • Với unsafe operation, dù hiệu ứng bị bỏ qua thì bản ghi vẫn phải được giữ lại
    • Tính an toàn của thao tác được quyết định động
    • Nếu về sau nhận được cập nhật mà trong đó một nút khác vốn gây ra vòng lặp bị xóa trước, thao tác trước đó từng là unsafe có thể trở thành safe
    • Trong quá trình undo, cần có đánh dấu ineffective để tìm nút cha đích của thao tác cuối cùng thực sự có hiệu lực

Ví dụ undo-do-redo

  • Nếu phép toán mới phụ thuộc vào một phép toán chưa có ở cục bộ, thì do bản cập nhật phiên bản trung gian vẫn còn thiếu, cần tạm lưu vào cache rồi áp dụng sau khi nhận được bản cập nhật còn thiếu
  • Nếu opId mới lớn hơn mọi phép toán hiện có thì có thể áp dụng ngay
    • nếu safe thì ghi parent hiện tại của nút đích làm old parent rồi áp dụng move
    • nếu unsafe thì đánh dấu là ineffective và bỏ qua hiệu ứng của nó
  • Nếu opId mới chèn vào giữa thứ tự hiện có, thì lần lượt lấy các phép toán phía sau ra để hoàn tác, áp dụng phép toán mới, rồi áp dụng lại các phép toán đã hoàn tác theo đúng thứ tự
  • Trong luồng ví dụ, Peer1 di chuyển C xuống dưới B ở cục bộ, sau đó nhận phép toán mà Peer0 đã di chuyển B xuống dưới C
    • Trong thứ tự Lamport timestamp, 0:3 đứng trước 1:3, nên trước tiên undo 1:3 để đưa C về old parent là A
    • Sau đó dùng 0:3 để di chuyển B xuống dưới C
    • Tiếp theo redo 1:3 để thử di chuyển C xuống dưới B, nhưng phát hiện vòng lặp nên không được áp dụng
    • Trạng thái cây không thay đổi và quá trình undo-do-redo hoàn tất

Cách của Evan Wallace: theo dõi parent trong quá khứ

  • CRDT: Mutable Tree Hierarchy của Evan Wallace để mỗi nút theo dõi toàn bộ các nút parent trong quá khứ
  • Mỗi parent được ghi lại sẽ có một counter đi kèm
    • Giá trị count của parent mới lớn hơn 1 so với mọi count của các parent trong quá khứ của nút đó
    • Parent có count cao nhất sẽ trở thành parent hiện tại
  • Khi đồng bộ, các bản ghi parent cũng được đồng bộ cùng nhau
  • Nếu xảy ra vòng lặp, thuật toán heuristic sẽ gắn lại nút gây ra vòng lặp vào parent trong quá khứ gần nhất mà không tạo vòng lặp và vẫn nối với root
  • Quá trình này được lặp lại cho đến khi mọi nút trong vòng lặp đều được gắn lại vào cây, từ đó đồng bộ cấu trúc cây giữa các replica
  • Cách này không cần quy trình undo-do-redo tốn kém, nhưng mỗi khi nhận một remote move, phải kiểm tra xem mọi nút có còn nối với root hay không và gắn lại các nút tạo vòng lặp, nên hiệu năng có thể giảm khi số lượng nút lớn
  • Một benchmark để so sánh hiệu năng đã được tạo riêng

Cách Loro triển khai Movable Tree

  • Loro triển khai thuật toán A highly-available move operation for replicated trees của Martin Kleppmann và các cộng sự
  • Thuật toán này cho hiệu năng cao trong phần lớn các kịch bản thực tế
  • Quy trình cốt lõi undo-do-redo trong Loro rất giống với cách Eg-walker (Event Graph Walker) áp dụng các cập nhật từ xa
  • Chỉ riêng movable tree thì không giải quyết được vấn đề thứ tự giữa các sibling node
    • Trong outline notes hay quản lý layer của phần mềm thiết kế đồ họa, cần sắp xếp các node con
    • Người dùng phải có thể điều chỉnh thứ tự node và đồng bộ điều đó với cộng tác viên hoặc thiết bị khác
  • Loro tích hợp thuật toán Fractional Index để có thể sắp xếp các node con trong movable tree

Fractional Index và xung đột khi chèn đồng thời

  • Fractional Index gán cho mỗi đối tượng một giá trị có thể sắp xếp được
    • Khi chèn mới giữa hai đối tượng, Fractional Index của đối tượng mới sẽ nằm giữa giá trị bên trái và bên phải
    • Có thể xem giải thích liên quan trong blog của Figma và blog của Evan
  • Trong môi trường phân tán, nếu nhiều peer chèn node mới vào cùng một vị trí, các node có nội dung khác nhau có thể được gán cùng một Fractional Index
  • Loro giữ nguyên cùng một Fractional Index, và thứ tự tương đối giữa các phần tử có cùng chỉ mục sẽ được quyết định bằng PeerID, tức ID duy nhất của từng peer
  • Nếu cùng một Fractional Index nằm ở cả hai phía, thì không thể tạo Fractional Index mới ở giữa chúng
  • Loro xử lý vấn đề này theo hai cách
    • Thêm một lượng jitter nhất định vào Fractional Index được tạo ra để giảm mạnh khả năng phát sinh chỉ mục trùng nhau
    • Ví dụ, nếu giá trị giữa 0 và 1 vốn là 0.5, thì với random jitter nó có thể trở thành các giá trị như 0.52712, 0.58312, 0.52834
    • Nếu cần chèn vào giữa 0.7@A và 0.7@B, có thể đặt lại bằng cách gán Fractional Index mới cho cả node mới lẫn node 0.7@B trong khoảng từ 0.7 đến 1

Kích thước mã hóa và thiết lập jitter

  • Loro dùng cách triển khai Fractional Index dựa trên Vec<u8> của drifting-in-space
  • Cách triển khai này dùng base 256
    • Với giá trị mặc định, phải liên tục chèn 128 giá trị về phía trước hoặc phía sau thì kích thước byte của Fractional Index mới tăng thêm 1
  • Overhead lưu trữ trong trường hợp xấu nhất xảy ra khi luôn chèn xen kẽ các giá trị mới
    • Ví dụ, trong ab chèn c vào giữa a và b, rồi tiếp tục chèn d vào giữa c và b, sau đó chèn e vào giữa c và d
    • Trong trường hợp như vậy, mỗi phép toán mới có thể cần thêm byte, nhưng đây là tình huống rất hiếm
  • Loro thêm một cách xử lý jitter đơn giản vào bản triển khai gốc
    • Nối thêm random bytes vào Fractional Index theo đúng độ dài của giá trị jitter
    • Trong JavaScript, có thể bật jitter bằng cách truyền số dương vào doc.setFractionalIndexJitter(number)
    • Kích thước mã hóa sẽ tăng nhẹ, với jitter bytes được thêm vào mỗi Fractional Index
  • Mối quan hệ giữa jitter để tránh xung đột với xác suất 99% khi tạo Fractional Index tại cùng một vị trí và số lượng chỉnh sửa đồng thời tối đa n như sau
jitter Số chỉnh sửa đồng thời tối đa
1 3
2 37
3 582
  • Nhiều Fractional Index đã sắp xếp sẽ có nhiều prefix chung
  • Khi mã hóa, Loro giảm tổng kích thước bằng tối ưu hóa prefix, chỉ lưu số bit prefix trùng với giá trị trước đó và các byte còn lại

Công trình liên quan và lý do lựa chọn

  • Ngoài Fractional Index, còn có movable list CRDT có thể sắp thứ tự các sibling node trong cây
  • Moving Elements in List CRDTs của Martin Kleppmann được dùng trong Movable List của Loro
  • Cách dùng Fractional Index có triển khai đơn giản hơn
  • Khi mô hình hóa tree node, nếu không cung cấp stable position representation cho các node con thì toàn bộ cấu trúc cây sẽ trở nên quá phức tạp
  • Fractional Index có vấn đề interleaving
    • Trong các trường hợp chỉ cần thứ tự tương đối, không cần ngữ nghĩa tuần tự nghiêm ngặt như item layer của Figma hay bookmark nhiều cấp, thì điều này có thể chấp nhận được

Kết quả benchmark

  • Loro đã benchmark phần triển khai Movable Tree về hiệu năng trong các điều kiện cực đoan như di chuyển nút ngẫu nhiên, chuyển đổi sang các phiên bản trong quá khứ và cấu trúc cây rất sâu
  • Kết quả đạt mức có thể hỗ trợ cộng tác thời gian thực và checkout mượt mà về các phiên bản trước đó
  • Môi trường kiểm thử là CPU M2 Max, mã benchmark nằm tại tree.rs
Tác vụ Thời gian Thiết lập
10000 lần di chuyển ngẫu nhiên 28ms Tạo trước 1000 nút
1000 lần chuyển sang các phiên bản khác nhau 153ms Tạo trước 1000 nút rồi di chuyển 1000 lần
1000 lần chuyển sang các phiên bản khác nhau trong cây sâu 300 mức 701ms Nút mới là nút con của nút trước đó

Ví dụ sử dụng và demo

  • LoroTree của loro-crdt cung cấp tạo nút, tạo tại vị trí chỉ định, di chuyển, di chuyển về root, di chuyển ra trước/sau nút khác, truy vấn index trong nút cha, truy vấn Fractional Index và truy cập data map của nút
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";

let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
  • Đã có một demo ứng dụng Todo mô phỏng đồng bộ dữ liệu giữa nhiều peer bằng Loro
    • Movable Tree biểu diễn quan hệ subtask
    • Map biểu diễn nhiều thuộc tính của task
    • Text biểu diễn tiêu đề task
    • Ngoài tạo, di chuyển, sửa và xóa, còn triển khai cả chuyển đổi phiên bản dựa trên Loro
    • Có thể kéo scrollbar để chuyển qua lại giữa tất cả các phiên bản trong quá khứ đã được tạo ra

Tổng kết

  • Việc triển khai CRDT cây có thể di chuyển là khó vì sự kết hợp của di chuyển đồng thời, xóa, vòng lặp, xóa tổ tiên và di chuyển nút con
  • Loro triển khai di chuyển trong phân cấp cây bằng thuật toán move có tính sẵn sàng cao của Kleppmann và các cộng sự
  • Việc di chuyển và sắp xếp giữa các nút con được xử lý bằng cách tích hợp triển khai Fractional Index của drifting-in-space
  • Sự kết hợp này có thể đáp ứng nhu cầu của nhiều kịch bản ứng dụng cộng tác khác nhau

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-30
Các ý kiến trên Hacker News

  • Tôi đang xây dựng một trình biên tập multiplayer mới [1] cho công việc/ghi chú, hỗ trợ cả thao tác văn bản lẫn outliner
    Nhìn bên ngoài nó hoạt động như một tài liệu văn bản phẳng, nhưng do có chức năng outliner nên bên trong là một cây lớn. Để đồng bộ thay đổi, chúng tôi dùng cách tương tự thao tác di chuyển có tính sẵn sàng cao. Thao tác duy nhất làm thay đổi cây là insmov; khi client online, nó đồng bộ tập thay đổi C với server. Nếu server có thay đổi từ xa, server trả về mọi thay đổi R kể từ lần đồng bộ cuối theo thứ tự tuyến tính toàn cục, rồi client hoàn tác các insmov trong thay đổi cục bộ C, sau đó áp dụng lại R và các thay đổi mới chưa đồng bộ
    Chúng tôi không dùng fractional indexing; trong tuple insmov có cả cha P lẫn guid A của sibling đứng trước. Vì mọi thao tác trên cây cuối cùng đều được áp dụng theo thứ tự tuyến tính toàn cục do server quyết định, việc sắp xếp được xử lý bởi chính thao tác insmov. Phần lớn trường hợp không cần hoàn tác; chỉ khi server có thay đổi insmov mà tôi chưa biết đồng thời tôi gửi một insmov mới thì mới cần phát lại theo đúng thứ tự. Điều này có thể xảy ra khi kết nối lại Wi-Fi sau một chuyến bay dài, nhưng ít phổ biến hơn khi đang online và nhận push thời gian thực qua WebSocket; cũng không cần cho các thao tác không phải insmov như cập nhật văn bản
    [1] https://thymer.com

    • Cách này có vẻ tương đương với RGA list CRDT [1], dùng thứ tự tuyến tính toàn cục của server làm timestamp logic
      Chẳng hạn là dạng dùng thứ tự của server thay vì timestamp Lamport
      [1] https://inria.hal.science/inria-00555588/
    • Hôm qua tình cờ đọc một thread cũ[0], thấy bài viết về Thymer nên thấy hứng thú
      Tìm Thymer trên HN thì thấy một Show HN[1] từ năm 2009, và có vẻ Thymer đã ở trạng thái beta kín trong 15 năm qua
      0. https://news.ycombinator.com/item?id=40786425
      1. https://news.ycombinator.com/item?id=518803
    • Tò mò không biết bạn đang dùng loại rich text nào

  • Chắc chắn tôi phải đọc bài này. Tôi đã open source React Table Library [0] từ một dự án làm cho khách hàng freelance, và nó tập trung vào các thao tác trên cây
    Họ xử lý cấu trúc cây thư mục/tệp ở quy mô 100.000 node, với việc di chuyển và sao chép thư mục/tệp, lazy loading ở cấp cao nhất và các cấp lồng nhau, tất cả trong cùng một cấu trúc bảng. Sau khi hoàn thành dự án, tôi mới hiểu vì sao Google Drive chỉ cho phép hiển thị và chỉnh sửa ở cùng một cấp phân cấp. Để triển khai việc này trong một view lồng nhau có nhiều node, có quá nhiều ràng buộc cần cân nhắc
    [0] https://react-table-library.com/

    • Trông hay đấy, nhưng không biết khi nào nó sẽ hoàn toàn headless

  • Tôi muốn xin lời khuyên. Đây không phải ứng dụng multiplayer, nhưng ở frontend chúng tôi có các cây phi chuẩn hóa lớn, liên kết lẫn nhau, dùng làm hồ sơ người dùng
    Có thể hình dung như một layout dạng ô: người dùng thêm/xóa/thay đổi kích thước các ô, thêm nhiều component vào từng slot của ô, và các component đó cũng có hồ sơ riêng. Có thể tồn tại nhiều layout với các cách sắp xếp ô khác nhau, và còn có độ phức tạp khi từng ô tham chiếu hoặc chia sẻ các mảnh khác nhau của trạng thái toàn cục
    Rất khó cập nhật an toàn bằng REST thông thường. Lý do là phải bảo đảm cùng một người dùng mở hai tab, cập nhật ở tab 1 rồi lại cập nhật ở tab 2, không làm toàn bộ hồ sơ rơi vào trạng thái không hợp lệ. Nhìn chung thứ tự cũng quan trọng. Nếu server bỏ qua một cập nhật đã được áp dụng đúng ở client thì có thể làm hỏng trạng thái
    Một giải pháp rất đơn giản mà chúng tôi dùng là gửi lượng dữ liệu tối thiểu đủ để ghi đè hoàn toàn một mảnh trạng thái cụ thể, rồi đưa vào cuối hàng đợi. Thường thì ổn, nhưng đôi khi lãng phí kiểu thay đổi thực tế chỉ vài byte mà lại gửi 50KB
    Chúng tôi không có các lý do thông thường để cần CRDT, nhưng ngay cả với một người dùng, tôi nghĩ việc quản lý trạng thái sẽ dễ hơn nhiều. Trước hết, nó đồng bộ được giữa các tab trình duyệt của người dùng; quan trọng hơn, tôi có thể tin rằng chỉ cần thay đổi trạng thái frontend thì CRDT sẽ phối hợp phù hợp với server. Không cần tự xử lý nữa. Tôi không biết điều này có hợp lý không, hay overhead khi gắn thứ như Yjs vào một tình huống không cần multiplayer và local-first là không đáng

    • Nếu ứng dụng chủ động dùng nhiều tab, dùng thứ như YJS có thể hợp lý, vì nó rất hiệu quả trong việc giải quyết loại vấn đề đó
      Tuy nhiên nếu việc chỉnh sửa hồ sơ chỉ dành cho một người dùng, đưa CRDT vào có vẻ hơi quá tay. Nhìn bề ngoài, kịch bản mở hai tab là nguồn lỗi lớn nhất, nên có thể dùng BroadcastChannel để thông báo sự kiện cập nhật cho tất cả các tab khác
    • Với use case này, CRDT có vẻ phù hợp
      Cách duy trì trạng thái chia sẻ bằng các lệnh gọi REST ghi đè một phần trạng thái server thực sự mong manh, và chỉ phù hợp ở mức ghi đè các field của những record dữ liệu phẳng. Ngoài ra, lúc nào cũng phải cân nhắc cẩn thận việc điều phối trạng thái server-client, và ở các luồng không bình thường thì rất dễ lệch đồng bộ
      Như bạn nói, nếu tạo một CRDT mô tả rõ cách các cập nhật được hợp nhất, gánh nặng nhận thức sẽ giảm đáng kể

  • Trong nội dung văn bản có định dạng như Google Docs hay Zoho Writer, các thao tác như di chuyển một mục trong danh sách xuống dưới hoặc thêm một cột mới, các phép toán trên bảng/danh sách về bản chất là thao tác trên cây.
    Xung đột đồng thời trong những trường hợp như vậy nổi tiếng là khó hội tụ nếu không có xử lý đặc thù theo ngữ cảnh [1]. Tôi tò mò liệu cách triển khai này có cung cấp một lời giải tổng quát cho các trường hợp sử dụng như thế không.
    Có lẽ có thể dùng CRDT dạng danh sách hoặc chuỗi cho các nút lá, tức các khối văn bản, rồi kết hợp CRDT cây này cho các nút cấu trúc như danh sách và bảng. Nhưng như vậy sẽ phải gắn địa chỉ hai chiều (parent-id, index_offset_into_that_parent) vào mọi thao tác.
    [1] https://github.com/inkandswitch/peritext/issues/27

    • Tôi vẫn luôn hình dung như vậy. Rich text là văn bản thuần được thêm hai thứ: phạm vi chú thích như đoạn được in đậm, và các phần tử phi ký tự như bảng hoặc ảnh nhúng.
      Text CRDT về cơ bản chỉ là list CRDT chứa dữ liệu ký tự. Vì vậy, phần tử nhúng có thể dễ dàng được mô hình hóa như một mục đặc biệt có kích thước 1 giống các mục khác trong chuỗi, tức một nút con được nhúng. Nếu dùng cách tiếp cận đúng, có thể trộn nhiều CRDT khác nhau trong cây khi cần. Ví dụ, có một bảng bên trong rich text, và một trong các ô của bảng đó có ảnh.
      Việc gắn trường parent-crdt-id vào mọi thao tác thì hơi tiếc, nhưng có vẻ khó tránh. May là trong hầu hết trường hợp sử dụng thực tế, các thao tác liên tiếp rất thường chia sẻ cùng một CRDT cha, nên các trường ID kiểu này có vẻ sẽ được nén tốt bằng mã hóa độ dài chạy.
    • Về mặt triển khai, thực sự có thể kết hợp nhiều loại CRDT. Trong triển khai nội bộ của Loro, mỗi thao tác phải lưu ID cha.
      Tuy nhiên, như Seph đã nói, các thao tác liên tiếp dưới cùng một cha có thể được nén hiệu quả, nên chi phí phụ trội bình quân của các ID cha này thường không lớn.

  • Tôi tò mò liệu đã có CRDT nào thực dụng cho các ứng dụng có mật độ dữ liệu cao như pixel của ảnh hay mô hình 3D chưa.

    • Trong ứng dụng cộng tác, trước hết cần xác lập khung khái niệm cho những chỉnh sửa mà người dùng sẽ thực hiện, và cách bảo toàn tốt nhất ý định của người dùng cũng như tính nhất quán của tài liệu kết quả khi các chỉnh sửa đó diễn ra bất đồng bộ.
      Dù biểu diễn cụ thể của tài liệu có nặng dữ liệu, cách mã hóa từng chỉnh sửa và thao tác của người dùng vẫn có thể nhỏ.
      Giả sử ta làm một trình chỉnh sửa ảnh như Photoshop: một ảnh không nén 102 triệu pixel với độ sâu màu 16 bit mỗi kênh, chẳng hạn ảnh Fujifilm GFX100, sẽ khoảng 610MB dưới dạng TIFF. Nếu biểu diễn mỗi pixel như một thanh ghi riêng biệt theo kiểu ghi cuối thắng thì overhead sẽ lớn, nhưng cách biểu diễn đó thực ra không phù hợp để bảo toàn ý định người dùng. Các chỉnh sửa người dùng sẽ làm là những thứ như “tăng tương phản ảnh thêm 15%” hoặc “tô spline [(0,0), (1500, 1500)] bằng bút Q và màu #000”. Nếu đồng bộ từng pixel bằng timestamp Lamport, thay đổi tương phản của người dùng 1 sẽ được áp dụng cho mọi pixel ngoại trừ các pixel mà người dùng 2 đã tô, khiến các pixel bị tô đè trông có thể rất lạc lõng.
      Thay vào đó, tốt hơn là biểu diễn ý định người dùng dưới dạng danh sách thao tác chỉnh sửa. Nó nhỏ hơn rất nhiều so với toàn bộ lưới pixel 102MB. Cấu trúc dữ liệu CRDT là một trong các cơ chế kỹ thuật khả dĩ để đồng bộ ý định người dùng đó, nhưng cấu trúc nên được chọn theo ngữ nghĩa của ý định người dùng, chứ không phải theo bố cục dữ liệu cụ thể của đầu ra.
      Dù vậy, vẫn có thể có các thao tác chỉnh sửa chứa lượng dữ liệu lớn như "add new layer named bgbelow layerfgwith pixelsdata:(10mb of pixels) at (1500, 1500)". Nhưng overhead đồng bộ của lệnh chỉnh sửa như vậy rất thấp, kích thước là O(1), chứ không phải O(pixels) tỷ lệ với số pixel bên trong lệnh chỉnh sửa.
    • Không hoàn toàn giống, nhưng tôi biết Figma hỗ trợ chỉnh sửa đồng thời và dùng cách tiếp cận tương tự CRDT (https://www.figma.com/blog/how-figmas-multiplayer-technology...)
    • Với chỉnh sửa ảnh, mọi chỉnh sửa xung đột đều có thể dễ dàng giải quyết theo kiểu người ghi cuối thắng, nên tôi không chắc có nhất thiết cần CRDT hay không.
      Mô hình 3D là một vấn đề khác, và tôi chưa thấy công cụ mô hình hóa 3D cộng tác nào trên thị trường. Tôi cũng chưa chủ động tìm kỹ.
    • Tôi từng phác thảo trong một bài viết lớn về CRDT rằng một CRDT dựa trên pixel có hiệu năng tốt có thể trông như thế nào: http://archagon.net/blog/2018/03/24/data-laced-with-history/...
      Tôi chưa tự làm thử, và cũng không chắc liệu nó có thực sự thực dụng không. Dù vậy, ít nhất nó có thể bảo tồn toàn bộ lịch sử của tài liệu.
    • Ví dụ thú vị tôi thấy là Modyfi, một trình chỉnh sửa phi phá hủy cho đồ họa raster.
      Họ biểu diễn dữ liệu bằng Yjs, nhưng thay vì lưu pixel thô, họ lưu toàn bộ lịch sử các phép biến đổi.
      https://digest.browsertech.com/archive/browsertech-digest-ho...

  • Tôi tò mò liệu bài viết có được kiểm tra bằng GPT không. Ngay đoạn đầu tiên tôi cảm nhận rất rõ giọng văn kiểu ChatGPT.

    • Có vẻ không phải. Lỗi ngữ pháp kiểu này không giống ChatGPT:
      This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.