Hành trình tối ưu hóa giúp CRDT nhanh hơn 5.000 lần (2021)

 (josephg.com)
3 điểm bởi GN⁺ 2024-08-28 | 1 bình luận | Chia sẻ qua WhatsApp
  • Việc CRDT trong chỉnh sửa cộng tác thường bị đánh giá là chậm là kết quả của việc trộn lẫn bản thân thuật toán với cách triển khai; chỉ riêng cấu trúc dữ liệu và cách bố trí bộ nhớ cũng có thể làm hiệu năng khác biệt rất lớn
  • Automerge v1.0.0-preview2 dùng 291 giây và 880MB RAM để xử lý trace 260.000 lần chỉnh sửa, trong khi Diamond types native xử lý cùng tác vụ bằng 56ms và 1,1MB RAM
  • Yjs dùng danh sách phẳng thay vì cây, cache vị trí, danh sách liên kết hai chiều và lưu span để giảm cùng trace xuống 0,97 giây và 3,3MB RAM
  • Diamond types dùng cấu trúc dựa trên range tree/B-tree trong Rust để xử lý tra cứu vị trí, chèn và xóa trong thời gian log(n), và ngay cả trên WebAssembly cũng đạt 193ms theo chuẩn Node.js
  • Benchmark này chỉ xem xét việc phát lại chỉnh sửa cục bộ của một người dùng và mức dùng RAM, nên khi lựa chọn thực tế cần xem xét thêm thời gian lưu/tải, kích thước mạng/đĩa, binary encoding, giao thức, presence và editor binding

Thuật toán và hiệu năng triển khai là hai chuyện riêng

  • Một so sánh học thuật đã triển khai chỉnh sửa cộng tác thời gian thực kiểu Google Docs bằng nhiều thuật toán CRDT và OT rồi benchmark; một số thuật toán mất hơn 3 giây để xử lý thao tác paste đơn giản
  • Cách chậm là thuật toán từng được dùng trong ShareJS và Google Wave, nhưng triển khai đó xử lý việc paste 1.000 ký tự bằng cách tách thành 1.000 operation riêng lẻ
  • Trường hợp này cho thấy cần tách biệt hành vi chỉnh sửa đồng thời và cách triển khai khi xem xét
    • Hành vi nghĩa là khi các chỉnh sửa đồng thời đi vào cùng một vùng thì chúng được hợp nhất theo thứ tự và quy tắc nào
    • Triển khai bao gồm ngôn ngữ lập trình, cấu trúc dữ liệu và mức độ tối ưu hóa
  • Cùng một hàm text OT transform chạy khoảng 100.000 lần/giây trong JavaScript, nhưng 20M lần/giây trong C, tạo ra chênh lệch khoảng 200 lần
  • Một triển khai chậm không phải bằng chứng rằng mọi triển khai của hệ thống đó đều chậm; hoàn toàn có thể có triển khai nhanh hơn

Mô hình cơ bản của CRDT và Automerge

  • CRDT cho phép nhiều người dùng chỉnh sửa cùng một dữ liệu đồng thời, làm việc cục bộ không độ trễ rồi đồng bộ sau để đạt eventual consistency
  • Automerge là thư viện chỉnh sửa cộng tác do Martin Kleppmann tạo ra, dựa trên thuật toán RGA
  • Các CRDT như Automerge và Yjs xem tài liệu chia sẻ là danh sách ký tự, và gán ID duy nhất cho từng ký tự
    • Nếu nhập abc vào tài liệu trống, chúng sẽ được gán các ID như (seph, 0), (seph, 1), (seph, 2)
    • Ký tự mới cũng ghi lại “được chèn sau mục nào”
  • Automerge/RGA thêm sequence number cho mỗi mục
    • Mục mới nhận giá trị lớn hơn 1 so với sequence number lớn nhất đã thấy cho đến lúc đó
    • Nếu có nhiều mục con, chúng được sắp xếp theo sequence number giảm dần; nếu bằng nhau thì sắp xếp theo agent ID
  • Hành vi của Automerge/RGA có thể nhìn thành ba bước
    • Nối từng mục vào parent để tạo cây
    • Với mục có nhiều con, sắp xếp theo sequence number và ID
    • Làm phẳng cây bằng depth-first traversal để tạo danh sách hoặc tài liệu văn bản cuối cùng

Benchmark Automerge và nút nghẽn

  • Benchmark dùng trace chỉnh sửa của automerge-perf
    • Đây là trace ghi lại theo từng ký tự nội dung Martin Kleppmann gõ cho một bài báo học thuật
    • Trace có 260.000 lần chỉnh sửa và kích thước tài liệu cuối cùng khoảng 100.000 ký tự
    • Không bao gồm chỉnh sửa đồng thời
    • Bài test chỉ đo thời gian áp dụng trace cục bộ
    • Môi trường là workstation Ryzen 5800x, Nodejs v16.1, Rust 1.52
  • Automerge v1.0.0-preview2 mất 291 giây để xử lý trace này, và RAM tại thời điểm hoàn tất là 880MB
    • Tương đương khoảng 10KB RAM cho mỗi lần gõ phím
    • RAM peak là 2,6GB
    • Ở các spike chậm, xử lý một lần chỉnh sửa mất 1,8 giây
  • Baseline splice trực tiếp trên chuỗi JavaScript xử lý cùng các chỉnh sửa trong 0,61 giây và 0,1MB RAM, nhưng đây chỉ là baseline để so sánh vì nó vứt bỏ toàn bộ thông tin cần cho chỉnh sửa cộng tác
  • Có vài lý do về mặt triển khai khiến Automerge chậm
    • Khi tài liệu lớn hơn, cấu trúc dữ liệu dựa trên cây cũng lớn và chậm hơn
    • Sử dụng nhiều Immutablejs, khiến V8 optimizer và GC khó tối ưu
    • Mỗi ký tự được chèn được xem là một mục riêng, nên paste cũng bị xử lý thành nhiều mục
  • Nhóm Automerge khi đó đang phát triển một triển khai thay thế dùng automerge-rs viết bằng Rust qua WASM
    • Vào thời điểm đó, xét theo master branch, hiệu năng trung bình trong bài test này chưa nhanh hơn, nhưng mức dùng bộ nhớ giảm một nửa và biến động hiệu năng trở nên nhẹ hơn

Triển khai danh sách phẳng kiểu Yjs

  • Yjs là triển khai CRDT mã nguồn mở do Kevin Jahns tạo ra, lưu mọi mục trong một danh sách phẳng duy nhất thay vì cây
  • Cách tiếp cận danh sách phẳng tìm vị trí chèn bằng cách quét từ ngay sau parent của mục mới, tức là triển khai list CRDT dưới dạng danh sách
  • reference-crdts thử nghiệm triển khai YATA của Yjs và RGA của Automerge theo cùng một cách
    • Hàm insert, trừ một vài khác biệt nhỏ, xử lý hành vi của Yjs và Automerge gần như trên cùng một codepath
    • Kiểm chứng tính tương đương về ngữ nghĩa bằng fuzzer
  • Cách tiếp cận này có ba ưu điểm
    • Dùng flat array thay vì cây mất cân bằng nên nhỏ hơn và nhanh hơn
    • Mã đơn giản
    • Có thể áp dụng cho nhiều list CRDT như Yjs, Automerge, Sync9
  • Về lý thuyết, nếu có nhiều chèn đồng thời vào cùng một vị trí thì có thể chậm, nhưng trong chỉnh sửa thực tế, phần lớn được chèn ngay sau parent
  • Triển khai reference-crdts nhanh hơn Automerge khoảng 10 lần và dùng ít RAM hơn khoảng 30 lần
Bài test Thời gian xử lý Mức dùng RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Chỉnh sửa chuỗi thuần trong JS 0.61s 0.1MB

Giảm chi phí quét và chèn

  • Triển khai array phẳng vẫn còn hai nút thắt cổ chai
    • Phải quét tài liệu để tìm vị trí cần chèn
    • Khi chèn vào giữa array bằng doc.content.splice(destIdx, 0, newItem), phải dịch chuyển các phần tử phía sau
  • Các mục đã bị xóa vẫn có thể được các lần chèn khác tham chiếu, nên không thể loại bỏ khỏi array và phải để lại dấu hiệu như isDeleted
    • Ngay cả khi tài liệu hiện tại có 100.000 ký tự, array vẫn có thể có 150.000 item nếu tính cả các mục trong quá khứ
    • Để chèn tại vị trí 50.000 của tài liệu, có thể phải quét khoảng 75.000 item trong khi bỏ qua các mục đã xóa
  • Với cấu trúc này, khi chèn vào một tài liệu từng có n mục sẽ cần khoảng n bước, và nếu chèn n ký tự thì sẽ thành O(n²)
  • Yjs cache cặp (index, position) của vị trí chỉnh sửa cuối cùng, phù hợp với cách con người chỉnh sửa tài liệu
    • Lần chỉnh sửa tiếp theo nhiều khả năng ở gần vị trí chỉnh sửa trước đó, nên chỉ quét ngắn về trước hoặc sau
    • Lưu một tập các vị trí đã cache để xử lý trường hợp nhiều người dùng chỉnh sửa ở các vị trí khác nhau
  • Yjs dùng danh sách liên kết đôi thay vì array, nên sau khi tìm được vị trí thì có thể chèn trong thời gian hằng số
  • Ngoài ra, tận dụng việc con người thường gõ các ký tự liên tiếp, hello được lưu thành một span duy nhất thay vì 5 mục ký tự
    • Chỉ có thể collapse khi ID và parent nối tiếp nhau theo thứ tự
    • Trong dataset này, số array entry giảm từ 180.000 xuống 12.000, tức giảm 14 lần
Bài kiểm thử Thời gian xử lý Mức dùng RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB

Rust và cách tiếp cận range tree của Diamond types

  • Object JavaScript dễ trở thành cấu trúc trong đó content, deletion flag, ID, seq, parent... nằm rải rác qua các con trỏ, làm tăng chi phí phân mảnh bộ nhớ và cache miss
  • Rust cho phép kiểm soát trực tiếp bố trí bộ nhớ, và có thể dùng trên web thông qua WebAssembly
  • Diamond types là một triển khai CRDT viết bằng Rust; gần như giống Yjs nhưng bên trong dùng range tree thay vì danh sách liên kết
  • Range tree nội bộ là một B-tree được chỉnh sửa nhẹ
    • Thay vì lưu key như BTreeMap thông thường, các node bên trong lưu tổng số ký tự có trong các node con
    • Xử lý truy vấn vị trí bất kỳ trong tài liệu, chèn và xóa trong thời gian log(n)
  • Trace 260.000 lần chỉnh sửa được lưu trong tree này với khoảng 3 tầng leaf node, nên hầu như item nào cũng có thể được tìm bằng khoảng 3 lần đọc bộ nhớ
  • Để merge remote edit, còn có một index nhỏ tìm B-tree theo ID, nhưng codepath đó không nằm trong benchmark này
  • Leaf node lưu chặt chẽ các khối 32 entry bằng array kích thước cố định
    • Tác giả cho biết bucket size 32 hoạt động tốt sau khi benchmark nhiều kích thước khác nhau, nhưng không rõ vì sao đó là tối ưu
  • Khi biên dịch Diamond sang WASM bằng diamond-js và gọi từ Node.js, cùng trace đó được xử lý trong 193ms
    • Nhanh hơn Yjs khoảng 5 lần
    • Nhanh hơn baseline chuỗi JavaScript khoảng 3 lần
  • Chạy Rust native đạt 56ms trong benchmark
    • Nhanh hơn Automerge hơn 5.000 lần
    • Xử lý 4,6M operation mỗi giây
    • Trong toàn bộ quá trình xử lý 260.000 lần chỉnh sửa, malloc được gọi 1394 lần
Bài kiểm thử Thời gian xử lý Mức dùng RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB
Diamond WASM via Node.js 0.19s không rõ
Diamond native 0.056s 1.1MB

Tách Ropey và tradeoff

  • Triển khai Diamond không đặt trực tiếp nội dung văn bản của tài liệu vào danh sách item CRDT, mà lưu trong một cấu trúc dữ liệu riêng
  • Với nội dung văn bản, nó dùng thư viện Rust Ropey; Ropey cũng triển khai B-tree để quản lý văn bản
  • Cách này có tradeoff về kỹ thuật
    • Ropey thực hiện byte packing chuyên biệt cho văn bản, nên có thể giảm mức dùng RAM
    • Khi chèn, phải cập nhật hai cấu trúc dữ liệu, khiến tốc độ chậm hơn hơn 2 lần và WASM bundle cũng tăng từ 60KB lên 120KB
    • Khi kết nối với editor như VS Code, editor sẽ giữ một bản sao tài liệu, nên có thể không cần lưu nội dung tài liệu trong cấu trúc CRDT
  • Nếu chỉ dùng Ropey để xử lý trace thì mất 29ms
  • Khi tắt cập nhật document content trong Diamond native, kết quả là 23ms và 0.96MB RAM
    • Nhanh hơn Automerge khoảng 14.000 lần
    • Xử lý 11M operation mỗi giây
    • Kết quả này gần với một thử nghiệm để xem giới hạn xử lý metadata CRDT hơn là tính hữu dụng thực tế
Bài kiểm thử Thời gian xử lý Mức dùng RAM Cấu trúc dữ liệu
automerge v1.0.0-preview2 291s 880MB naive tree
reference-crdts Automerge/Yjs 31s 28MB array
Yjs v13.5.5 0.97s 3.3MB linked list
Plain string edits in JS 0.61s 0.1MB không có
Diamond WASM via Node.js 0.20s không rõ B-tree
Diamond native 0.056s 1.1MB B-tree
Ropey Rust baseline 0.029s 0.2MB không có
Diamond native, no doc content 0.023s 0.96MB B-tree

Tiêu chí chọn thư viện thực tế

  • Nếu hiện tại xây dựng một ứng dụng cộng tác dựa trên tài liệu, dùng Yjs sẽ có lợi hơn
    • Yjs có hiệu năng tốt, mức dùng bộ nhớ thấp và hệ sinh thái hỗ trợ tốt
    • Kevin Jahns cũng cung cấp hỗ trợ tích hợp Yjs có trả phí
  • Nhóm Automerge cũng xem hiệu năng là vấn đề ưu tiên hàng đầu trong năm 2021, và đã có kế hoạch làm Automerge nhanh hơn bằng nhiều kỹ thuật
  • Diamond rất nhanh, nhưng vẫn còn nhiều việc phải làm để đạt mức parity tính năng như Yjs và Automerge
    • Ngoài tốc độ operation, thư viện CRDT còn cần binary encoding, network protocol, cấu trúc dữ liệu ngoài list, presence, editor binding...
  • Nếu cần semantics kiểu cơ sở dữ liệu, tác giả không biết triển khai nào tốt trên CRDT; có thể dùng ShareDB dựa trên OT
  • Redwood là một dự án hỗ trợ P2P editing và đang lên kế hoạch full CRDT support

Hạn chế của phương pháp đo

  • Benchmark này chỉ đo thời gian phát lại trace chỉnh sửa cục bộ và mức sử dụng RAM
  • Đầu vào từ người dùng cục bộ chỉ cần đủ nhanh; nếu CRDT xử lý một lần chỉnh sửa local trong khoảng 1ms trở xuống thì tốc độ nhanh hơn có thể không quá quan trọng
    • Automerge nhìn chung cũng đạt mức này, trừ những lần GC pause không may
  • Trên thực tế, có những chỉ số quan trọng hơn
    • Số byte mà tài liệu chiếm trên đĩa hoặc mạng
    • Thời gian lưu và tải
    • Thời gian cập nhật tài liệu đã lưu bên trong cơ sở dữ liệu
  • Trace được dùng chỉ gồm chỉnh sửa của một người dùng, nên vẫn có thể còn các pathological case với nhiều chỉnh sửa đồng thời
  • Hiện nay, để cập nhật một đối tượng đơn lẻ trong cơ sở dữ liệu bằng Yjs hoặc Automerge, thông thường phải tải toàn bộ tài liệu vào RAM, thay đổi, rồi lưu lại toàn bộ tài liệu, nên có thể chậm
    • Kevin nói rằng nếu điều chỉnh Yjs provider phù hợp thì có thể triển khai theo cách hợp lý
  • list CRDT về cơ bản sẽ tiếp tục phình to do tombstone của các mục đã xóa, còn pruning là một hướng tiếp cận riêng
    • Thuật toán GC của Yjs và Antimatter được nêu làm ví dụ
    • Pruning là vấn đề trực giao với tối ưu hóa cấu trúc dữ liệu được bàn trong bài

Đây không phải là thí nghiệm so sánh được kiểm soát hoàn toàn

  • Mỗi bước tối ưu hóa thay đổi nhiều biến cùng lúc, nên không tách riêng nguyên nhân chính xác của mức tăng tốc
  • Khi chuyển từ Automerge sang reference-crdts, có nhiều yếu tố đã thay đổi
    • Cấu trúc dữ liệu lõi chuyển từ cây sang danh sách
    • Immutablejs bị loại bỏ
    • Automerge frontend/backend protocol và nhiều cấu trúc Uint8Array biến mất
    • Phong cách JavaScript chuyển từ functional sang imperative
  • Khi chuyển từ reference-crdts sang Yjs, rồi từ Yjs sang Diamond, các thay đổi cũng không được tách thành một nguyên nhân duy nhất
  • Việc automerge-rs không nhanh hơn Automerge trong bài test này là bằng chứng cho thấy hiệu năng của Diamond không chỉ nhờ Rust, nhưng không thể biết chính xác mức đóng góp
  • Việc so sánh RGA và YATA trong cùng một kiểu triển khai cũng dựa trên tiền đề rằng “hành vi merge đồng thời trên thực tế khá giống nhau, và dù thay đổi hành vi thì hiệu năng triển khai vẫn được giữ nguyên”
    • Trong reference CRDT implementation, hành vi của Yjs và Automerge cho thấy gần như cùng codepath và cùng hiệu năng
    • Với trace nhiều conflict có thể có khác biệt hiệu năng, nhưng thực tế được xem là trường hợp rất hiếm
  • Yjs không lưu thời điểm từng item bị xóa, chỉ lưu trạng thái đã xóa hay chưa
    • Nếu lưu thời điểm xóa trong Diamond, mức dùng bộ nhớ tăng từ 1.12MB lên 2.34MB và chậm đi khoảng 5%
    • Tất cả benchmark Diamond trong bài này dùng yjs-style branch, được điều chỉnh theo cách của Yjs

Mã benchmark và tài liệu tái hiện

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-08-28
Ý kiến trên Hacker News

  • Nếu họ dùng số nguyên 2 byte thì rất có khả năng là vì cache line 64 byte
    32 entry vừa khít thành đúng một cache line, nên mỗi cache line sẽ chứa trọn một bucket và giảm các lần truyền dữ liệu đắt đỏ từ bộ nhớ chính

    • Tôi thích cách Knuth benchmark các chương trình về sau
      Về cơ bản là thêm bộ đếm để đếm xem phải đọc thứ gì đó từ bộ nhớ bao nhiêu lần; tôi tự hỏi liệu có thể xấp xỉ tương tự số lần phải flush cache line hay không
    • Khi benchmark theo kích thước batch, thường thấy các bước nhảy lớn liên quan đến phân cấp bộ nhớ
      Nó nhảy ở các ranh giới như kích thước word (64-bit), kích thước fetch căn chỉnh cache (thường là 64 byte như nói ở trên), kích thước page của OS (4~16KB), kích thước L1 (khoảng 80KB mỗi core), L2 (cỡ vài MB)

  • Tôi tò mò có những ứng dụng nào dùng CRDT trong dịch vụ thực tế mà trải nghiệm rất tốt
    Tôi nhớ Notion từng là một trong số đó, nhưng thực tế thì việc hai người cùng ghi chú trong Notion gần như khó dùng so với Google Docs

    • Thymer[1] dùng CRDT cho mọi thứ
      Đây là một IDE cho công việc và lập kế hoạch, là ứng dụng đa người dùng, hỗ trợ mã hóa đầu cuối, offline-first, tùy chọn tự host, và toàn bộ workspace là một graph nên CRDT là lựa chọn tự nhiên
      Mọi thao tác trong Thymer được rút gọn thành một số ít biến đổi CRDT. Di chuyển/sao chép văn bản, thay đổi thuộc tính "frontmatter", kéo thẻ, tải tệp lên, thêm tag đều được xử lý bằng cùng vài phép toán CRDT
      Ban đầu việc tự triển khai mà không có thư viện khá vất vả, nhưng nếu trạng thái ứng dụng là một graph duy nhất thì có thể xây dựng các tính năng như di chuyển văn bản giữa các trang, liên kết trang có backlink, transclusion mà không phải lo chuyện đồng bộ, nên hoàn toàn xứng đáng
      CRDT đảm bảo mọi client sẽ hội tụ về cùng một trạng thái, và vì về bản chất là chỉ thêm vào nên có luôn versioning theo từng thời điểm
      Tuy vậy, vì hiệu năng nên chúng tôi đã có vài thỏa hiệp. Lịch sử phiên bản có quá nhiều dữ liệu nên không cung cấp offline, và trong một số trường hợp dùng cơ chế giải quyết xung đột last-writer-wins
      Nhìn chung nó rất đáng giá, nhất là nếu thiết kế ứng dụng với CRDT ngay từ đầu. Nếu là tình huống thêm tính năng đa người dùng về sau vào một ứng dụng AJAX truyền thống hơn thì có lẽ tôi sẽ không dùng CRDT
      Các thay đổi của CRDT trước hết được áp dụng một cách lạc quan; khi thứ tự sự kiện có thẩm quyền được xác định, mọi client phải quay lại trạng thái chia sẻ cuối cùng rồi áp dụng lại tất cả sự kiện theo đúng thứ tự
      Nếu đã offline lâu, có thể phải hoàn tác và áp dụng lại các thay đổi của vài ngày. Người dùng không biết phía sau có bao nhiêu phép biến đổi cây đang diễn ra, nhưng CRDT ảnh hưởng đến toàn bộ thiết kế ứng dụng
      Phần lớn ứng dụng phổ biến ngày nay được thiết kế vào thời điểm các biến đổi CRDT vẫn chưa được hiểu rõ
      [1] https://thymer.com (gần như đã sẵn sàng beta)
    • Notion ngày nay là một hệ thống last-writer-wins, chỉ có giới hạn một số phép toán bảo toàn ý định như thứ tự block trong dữ liệu dạng danh sách
      Văn bản là last-writer-wins, và văn bản hay thuộc tính của từng block là một thanh ghi last-writer-wins. Họ đang phát triển một định dạng CRDT mới cho văn bản trong block
    • Theo tôi biết, phần lớn dịch vụ của iCloud dùng CRDT nội bộ
      Bao gồm Notes, Reminders, và Photos cũng có thể như vậy. Tôi nghe từ một cựu Apple SRE say rượu trong quán bar rằng FoundationDB cũng được dùng như một phần của backend
    • Linear: https://linear.app/
      Bài trình bày tại Local First Conf cũng đáng tham khảo: https://youtu.be/VLgmjzERT08
    • Nghĩ thêm một chút thì còn một ví dụ nữa mà mọi người không nghĩ ra ngay
      Tất cả game mạng có rollback hoặc hiệu chỉnh dưới hình thức nào đó đều gần với trường hợp này. Cách đặt rollback làm đường dự phòng trên nền best-effort có thể là dạng CRDT phổ biến nhất xét về trải nghiệm người dùng
      Nó không phải CRDT theo nghĩa học thuật nghiêm ngặt. Về mặt kỹ thuật, trạng thái game không được sao chép đầy đủ sang mọi client, và mỗi client chỉ nhận một phần trạng thái game
      Ngoài ra client game cần đồng bộ độ trễ thấp, và về mặt học thuật có thể xem việc này là "phối hợp". Trong thực tế, client chấp nhận và render cục bộ kết quả input theo xác suất trước khi cơ chế giải quyết xung đột hoặc hiệu chỉnh rollback quay về
      Có thể sẽ có người soi xét khắt khe, nhưng đến ví dụ thứ ba thì hẳn có thể thấy chủ đề chung. Những CRDT phổ biến nhất, dễ dùng nhất và được triển khai tốt nhất thực ra đang phá vỡ các quy tắc học thuật
      Đây là cái bẫy điển hình của mô hình tư duy quá thiên về học thuật. Thuật toán và kiểu dữ liệu trong thực tế thường sáng tạo hơn nhiều so với "sổ quy tắc" học thuật. Ví dụ như Timsort
      Nếu đang làm sản phẩm cho người dùng thực, chứ không phải để phản biện bài báo, thì đừng rơi vào cái bẫy over-engineering/học thuật. Hãy học các quy tắc học thuật nhưng phá vỡ chúng một cách có chủ đích, và thay vì cố triển khai hoàn hảo một khái niệm được định nghĩa nghiêm ngặt đến mức chỉ hữu ích giữa các học giả, hãy tạo ra giá trị thực và làm cho nó dễ dùng

  • CRDT rất mạnh, nhưng điều đáng tiếc là dù dựa trên operation hay dựa trên state thì chúng vẫn để lại dấu vết của các operation hoặc phần tử trong quá khứ
    Ngay cả khi nén thì đây vẫn là nhược điểm, và là điểm khiến người ta phải đắn đo khi áp dụng
    Dù vậy, nhờ cuộc thảo luận này mà tôi thấy hứng thú với khả năng triển khai các thuật toán không xung đột hoặc thuật toán giải quyết xung đột chi tiết trên các kho lưu trữ dựa trên tệp như Dropbox, Syncthing

    • Tôi là tác giả bài viết. Tôi đã có rất nhiều cuộc trao đổi kiểu này, và phía CRDT cũng thường nói về nó, nhưng trên thực tế, ít nhất là trong chỉnh sửa văn bản, overhead nhỏ đến mức tôi không nghĩ nó sẽ trở thành vấn đề trong thực tế
      Dự án hậu-CRDT của tôi, Diamond Types, về cơ bản sẽ lớn vô hạn theo thời gian, nhưng overhead thường dưới 1 byte cho mỗi ký tự đã nhập cho đến hiện tại
      Nếu bật nén LZ4 cho văn bản lưu trữ, tài liệu được chỉnh sửa bằng Diamond Types dù lưu toàn bộ lịch sử chỉnh sửa vẫn thường nhỏ hơn trạng thái tài liệu cuối cùng
      Về mặt kỹ thuật, tôi biết nhiều cách để giải quyết việc này, nhưng tôi không chắc đây có phải là vấn đề thực tế trong hầu hết hệ thống hay không
      Tôi có nghe chuyện một người dùng yjs cho công cụ dựng mô hình 3D đã gặp vấn đề. Lý do là trong lúc kéo một object, mỗi lần chuột di chuyển theo từng pixel lại tạo ra một chỉnh sửa bền vững
      Với các tác vụ như vậy, tôi nghĩ khôn ngoan hơn là dùng các chỉnh sửa tạm thời, thứ mà phần lớn thư viện CRDT không hỗ trợ
      Nhân tiện, Git cũng có cùng vấn đề. Repository lớn dần theo thời gian, và lớn nhanh hơn rất nhiều so với khi dùng các thư viện CRDT hiện đại. Nhưng dường như không ai quá bận tâm
      Git có thể shallow clone, nhưng gần như không ai làm vậy. Nếu muốn thì CRDT cũng có thể làm tương tự
    • Nếu không tạo một hệ thống phi tập trung hoàn toàn, ta có thể nới lỏng một phần các ràng buộc mà CRDT yêu cầu
      Ví dụ, nếu có thể đảm bảo mọi client đã nhận các thay đổi sau ngày X, thì có thể an toàn loại bỏ các operation trước ngày đó
    • Toàn bộ operation log và merge tất định rất hợp với immutable block store, đồng thời cũng có thể có lợi ích về bảo mật, hiệu năng và chi phí
      Chúng tôi đang xây dựng Fireproof[1] để tận dụng các nghiên cứu mới nhất trong lĩnh vực này
      Khi dùng content addressing cho dữ liệu bất biến, mỗi operation còn có lợi ích bổ sung là quy về một bằng chứng hoặc diff được bảo đảm bằng mật mã. Có thể cưỡng chế causal consistency và tạo tham chiếu ổn định tới snapshot
      Nói cách khác, ta có thể chạy một database tương tác được, hoạt động offline và merge không mất dữ liệu ở edge hoặc trong trình duyệt, nhưng vẫn có tính toàn vẹn mà trước đây ta kỳ vọng ở database trung tâm hoặc blockchain
      Ví dụ, có thể đưa snapshot CID vào PDF để ký hoặc smart contract, loại bỏ sự mơ hồ về trạng thái được tham chiếu
      [1] https://github.com/fireproof-storage/fireproof
    • Bản thân khái niệm CRDT không có yêu cầu phải để lại dấu vết của các operation hoặc phần tử trong quá khứ
      Rốt cuộc, thay vì nói bao quát về tập hợp các quy luật toán học mà một kiểu dữ liệu hay database cụ thể tuân theo, phê phán một triển khai cụ thể sẽ đúng hơn
    • Nếu có thể xóa lịch sử thì tôi tò mò không biết còn lo điều gì

  • Đây là bài năm 2021 và có vẻ cũng đã bao gồm bản triển khai Rust của Automerge, nên xem benchmark cập nhật chắc sẽ thú vị

    • Tôi là tác giả bài viết. Yjs cũng có yrs được viết lại bằng Rust, nhanh hơn nhiều so với bản JavaScript
      Tôi cũng có một cách tiếp cận mới hoàn toàn khác để giải quyết vấn đề này
      Cập nhật benchmark chắc chắn sẽ tốt. Tất cả đều đã nhanh hơn

  • Tôi khó hiểu được khá nhiều nội dung, nhưng đây là một bài hiếm hoi được viết quá hay đến mức khiến tôi đọc một mạch không dừng

  • Đây là các thảo luận liên quan trước đó
    https://news.ycombinator.com/item?id=28017204 (3 năm trước, 151 bình luận)
    https://news.ycombinator.com/item?id=33903563 (2 năm trước, 22 bình luận)
    https://news.ycombinator.com/item?id=41372833 (bài đăng hiện tại)
    https://news.ycombinator.com/item?id=41373288 (bình luận hiện tại)

  • Trích README GitHub hiện tại[0], có vẻ sau bài blog đó hiệu năng lại còn được cải thiện thêm 10~80 lần
    [0] https://github.com/josephg/diamond-types

  • Giá mà có ai giải thích được vì sao CRDT chậm
    Bài này có vẻ cho thấy tương lai: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    Xem cái này rồi so với Y.js hoặc Automerge chắc sẽ hay: https://github.com/canvasxyz/okra-js

    • Tôi là tác giả bài viết. Lý do chính là nhiều thư viện CRDT được viết bởi các học giả, và họ thiếu thời gian, kỹ năng hoặc sự quan tâm để tối ưu hóa
      Kể từ khi tôi viết bài này vài năm trước, các thư viện CRDT lớn đều đã nhanh hơn ở mức vài bậc độ lớn

  • Tôi nhớ đã tình cờ thấy bài này vài năm trước
    Đây là một bài thực sự thú vị, và là một trong những bài tôi thích nhất trong vài năm gần đây

    • Tôi nhớ tiêu đề có lẽ là CRDTs go brrr

  • Về câu hỏi “Tại sao WASM chậm hơn thực thi native 4 lần?”, tôi từng nghĩ đó là vì mọi thao tác chuỗi đều phải được sao chép vào bộ nhớ WASM, rồi khi tính xong kết quả lại phải sao chép ngược về JS.
    Tôi sai à? Hay tôi đã hiểu nhầm ngữ cảnh? Thật sự tò mò

    • Tôi là tác giả bài viết. Bài này đã từ vài năm trước, nhưng theo trí nhớ thì phần đó đã được kiểm soát. Vì vậy vấn đề không phải FFI.
      Trước khi đo thời gian, tôi đã nạp toàn bộ bản ghi vào trong wasm, rồi xử lý bằng vòng lặp nội bộ viết bằng Rust chạy ngay trong ngữ cảnh wasm. Số lần gọi wasm chỉ khoảng hai lần.
      Nguyên nhân chậm hơn 4 lần không phải FFI, mà là bản thân mã thuật toán thực sự chạy chậm hơn 4 lần.
      Nếu chạy lại benchmark bây giờ thì chắc sẽ thú vị. Đầu ra wasm của compiler cũng đã tốt hơn, và runtime wasm hẳn cũng đã nhanh hơn. Mã benchmark có lẽ vẫn còn ở đâu đó.
    • Nghe có vẻ là một nguyên nhân hợp lý.
      Một vấn đề vẫn hay vướng ở lĩnh vực khác là câu chuyện đa luồng không hề dễ, và hỗ trợ từ thư viện lẫn công cụ cũng chưa hoàn chỉnh.
      Tôi đã thử chạy trong trình duyệt các binary tiện ích như game engine, ffmpeg hay zip, và vì lý do này mà chúng rất chậm.
    • Có lẽ câu hỏi hay hơn là tại sao lại kỳ vọng hai thứ đó sẽ giống nhau.
      Tôi chưa từng làm với trình thông dịch WASM hay JIT, nhưng có bao nhiêu trường hợp mà đi qua nhiều lớp dịch lại tốt hơn đi qua một lớp dịch?
      Khi dịch mã bậc cao sang WASM hay một ngôn ngữ assembly nào đó, ta mất đi rất nhiều ý đồ có trong mã bậc cao.
      Trong mã bậc thấp, ta thường thấy một chuỗi các idiom theo từng ngôn ngữ để đạt mục tiêu; có thể có hoặc không có thứ tương ứng trực tiếp với máy thực tế.
      x86-64 hiện đại có rất nhiều lệnh mạnh hơn nhiều so với những gì WASM có thể làm.
      Tất nhiên cũng có decompiler, và có thể WASM JIT có một danh sách các macro-op fusion có thể tạo ra mã native tốt bằng pattern matching tương đối đơn giản. Có lẽ không phải vậy, và tối ưu hóa đa nền tảng sẽ còn khó hơn.
      LLVM cũng không hoàn hảo, nên chắc chắn có những chỗ dễ mà một bộ tối ưu hậu xử lý có thể cải thiện. Vì vậy về mặt lý thuyết, làm cho WASM nhanh hơn đầu ra native của LLVM không phải là bất khả thi.
      Nhưng nếu không có một kế hoạch được thiết kế rất kỹ, hoặc không tạo ra một tập lệnh trên thực tế là siêu tập của những gì kiến trúc tập lệnh đích hỗ trợ, thì tôi nghĩ rất khó đạt kết quả ngang bằng.
      Theo tôi, WASM gần với một tập con hơn, nên việc chuẩn hóa các phép toán rồi ghép chúng lại theo thời gian thực là không dễ. Dù không hoàn toàn bất khả thi, nó đòi hỏi một thành tựu kỹ thuật đáng kể.
      Nói trực giác thì, nếu dịch một cuốn sách tiếng Anh sang một ngôn ngữ rất khác và bị giới hạn chỉ vài nghìn từ, rồi dịch ngược lại sang tiếng Anh, bạn sẽ không nhận được đúng văn bản ban đầu.
      Sẽ có những trường hợp một khái niệm vốn chỉ cần một từ trong tiếng Anh lại phải giải thích bằng cả đoạn văn. Để khôi phục lại tiếng Anh gốc, bạn cần bản dịch 1:1 cho mọi thứ, hoặc một danh sách dịch từ “đoạn văn → một từ” mà cả hai người dịch đều đã thống nhất.