cola: Teknologi CRDT Teks untuk Penyuntingan Kolaboratif Real-Time

• cola adalah CRDT teks untuk penyuntingan kolaboratif real-time yang ditulis dalam Rust, berfokus pada membuat dokumen yang diedit serentak oleh beberapa peer berkonvergensi ke status yang sama tanpa koordinator pusat
• Posisi dokumen ditetapkan bukan sebagai offset sederhana, melainkan sebagai Anchor berbentuk ReplicaId.n, sehingga menghindari masalah makna posisi yang berubah akibat penyuntingan serentak
• Konflik penyisipan ditangani secara konsisten dengan pengurutan Lamport timestamp dan ReplicaId, sementara penghapusan mengelola kondisi integrasi dengan tombstone dan version vector alih-alih benar-benar menghapus data
• Dari sisi implementasi, cola menggunakan RLE berbasis EditRun dan G-tree yang direpresentasikan dengan indeks Vec, menargetkan pencarian dan penyisipan waktu logaritmik di dalam model ownership Rust yang aman
• Dalam benchmark, cola dibandingkan dengan diamond-types, automerge, dan yrs; pada jalur upstream cola 1,4–2 kali lebih cepat daripada diamond-types, dan juga menunjukkan performa yang sangat cepat pada downstream

---

Masalah penyuntingan kolaboratif yang ditangani cola

• cola adalah CRDT teks yang ditulis dalam Rust, dirancang agar beberapa replika dalam penyuntingan kolaboratif real-time berkonvergensi ke status yang sama tanpa otoritas pusat
• Pada lapisan jaringan, cola hanya membuat asumsi minimum bahwa semua edit pada akhirnya akan sampai ke semua peer
  • Edit dapat dikirim beberapa kali
  • Edit dapat tiba dalam urutan acak
  • Semua peer pada akhirnya harus menerima semua edit
• Tujuannya bukan hanya agar status dokumen menjadi sama setelah semua edit diterima, tetapi juga agar dokumen hasilnya masuk akal dari sudut pandang pengguna

Menetapkan posisi dengan Anchor, bukan offset

• Edit berbasis offset seperti insert "abc" at offset 8 dapat berubah maknanya jika peer lain secara serentak mengubah area di bagian depan, sehingga replika bisa bercabang
• cola merujuk posisi dokumen menggunakan identifier yang stabil, bukan konten karakter atau offset
  • Setiap peer memberi nomor yang terus meningkat pada karakter yang disisipkannya
  • Peer memiliki identifier unik bernama ReplicaId
  • Pasangan ReplicaId.n menjadi Anchor, identifier posisi unik sebuah karakter
• Nilai n dapat dijamin unik melalui kenaikan counter lokal, tetapi sulit menjamin keunikan global ReplicaId tanpa server pusat
  • cola berasumsi penggunaan integer acak besar seperti UUID, sehingga probabilitas tabrakannya dapat diabaikan
• Penyisipan menentukan posisi dengan satu Anchor, sementara penghapusan menentukan rentang dengan dua Anchor: awal dan akhir

Mengurutkan konflik penyisipan dalam urutan yang sama

• Jika beberapa penyisipan masuk pada Anchor yang sama, cola menentukan urutannya dengan Lamport timestamp
• Lamport clock diperbarui dengan aturan berikut
  • Saat menyisipkan teks secara lokal, clock dinaikkan 1
  • Saat menerima penyisipan jarak jauh, clock diatur menjadi max(current, remote_timestamp) + 1
• Jika suatu penyisipan A dibuat dalam lingkungan yang sudah mengintegrasikan penyisipan B, Lamport timestamp milik A menjadi lebih besar daripada B
• Penyisipan yang berkonflik diurutkan berdasarkan Lamport timestamp secara menurun
• Untuk penyisipan serentak yang Anchor dan Lamport timestamp-nya sama, tidak ada urutan yang lebih benar dari sudut pandang pengguna, sehingga cola mengurutkannya berdasarkan ReplicaId secara menaik agar konsisten antar-peer

Penghapusan ditangani dengan tombstone dan version vector

• Penghapusan mengubah offset awal dan akhir menjadi Anchor lalu menyebarkannya ke peer lain
• Jika dua peer menghapus area yang sama secara serentak, selama tidak mempertimbangkan undo, hasilnya sama seperti menghapusnya satu kali
  • cola saat ini tidak mendukung undo untuk penghapusan
• Ada tiga kesulitan dalam menangani penghapusan
  • Jika teks yang dihapus benar-benar dibuang, Anchor dari edit yang belum tiba mungkin berada di dalam area tersebut
  • Jika penghapusan jarak jauh diintegrasikan terlalu dini, konten yang dilihat peer pembuat penghapusan dan konten pada peer penerima bisa berbeda, sehingga replika dapat bercabang
  • Bahkan di dalam rentang penghapusan, karakter yang belum pernah dilihat peer pembuat penghapusan tidak boleh ikut dihapus
• Masalah pertama diselesaikan dengan tombstone
  • Karakter yang dihapus tetap berada di dokumen, tetapi ditandai sebagai terhapus
  • Pendekatan ini meningkatkan penggunaan memori
• Masalah lainnya diselesaikan dengan menyertakan version vector dalam pesan penghapusan
  • Kuncinya adalah ReplicaId, dan nilainya adalah timestamp karakter terakhir yang dilihat peer pembuat penghapusan pada saat itu
  • Peer penerima menunggu integrasi penghapusan sampai version vector miliknya setidaknya sama dengan version vector dalam pesan penghapusan
  • Karakter dengan timestamp lebih besar daripada timestamp di version vector penghapusan dilewati dari target penghapusan
• Di cola, version vector disebut version map

Pemisahan Replica dan buffer teks

• Status dokumen lokal tiap peer direpresentasikan di cola sebagai Replica
• Algoritme CRDT cola tidak perlu mengetahui isi string sebenarnya
  • Fungsi API tidak menerima string sebagai argumen
  • cola hanya menangani blok numerik, bukan konten dokumen
• Desain ini memisahkan mekanisme CRDT dari implementasi buffer teks sebenarnya

Mengurangi metadata dengan RLE dan EditRun

• Karena sulit membuat implementasi berperforma baik jika metadata ditempelkan ke setiap karakter, cola mengelompokkan blok dengan timestamp berurutan menggunakan run-length encoding
• Misalnya, jika seluruh halaman Manhattan Project di Wikipedia ditempelkan, ia dapat direpresentasikan sebagai satu blok, bukan 107.000 blok
• Saat pengguna mengetik kalimat karakter demi karakter tanpa memindahkan kursor atau menghapus, cola juga dapat merepresentasikannya sebagai satu run, bukan membuat blok pada setiap ketukan tombol
• Di cola, blok berurutan seperti ini disebut EditRun
  • EditRun yang sudah terpecah akan tetap demikian selama masa hidup dokumen dan tidak lagi diperluas
  • Run yang belum terpecah berada dalam status active
• Jika teks disisipkan di tengah EditRun yang sudah ada, run tersebut dibagi dua dan teks baru dimasukkan di antaranya
• Jika teks dihapus, bagian tersebut dipisahkan dari run dan ditandai sebagai tombstone
  • Run yang terhapus juga dapat di-RLE dengan cara yang sama, sehingga mengurangi beban memori tombstone

Dari linked list ke B-tree

• Jalur upstream untuk edit lokal adalah proses mengubah edit berbasis offset menjadi edit yang dapat dikirim ke peer lain
  • Baik penyisipan maupun penghapusan harus menemukan run yang memuat offset, lalu membuat Anchor
  • Jika diperlukan, run dibagi menjadi maksimal 2 bagian untuk penyisipan dan maksimal 3 bagian untuk penghapusan
• Dalam linked list, pemecahan run adalah O(1), tetapi untuk menemukan run yang memuat offset harus memindai dari awal, sehingga memerlukan waktu linear
• Jika run active saat ini dan offset-nya di-cache, penyuntingan berulang di posisi yang sama menjadi cepat, tetapi kasus terburuk tetap linear
• cola mempertimbangkan struktur B-tree untuk performa kasus terburuk waktu logaritmik
  • Run direpresentasikan sebagai leaf B-tree
  • inode menyimpan anak-anak dan jumlah panjang anak-anaknya
  • Run tombstone berkontribusi dengan panjang 0
  • Panjang root sama dengan panjang keseluruhan dokumen
• B-tree dapat melakukan pencarian dan penyisipan dalam O(log n), sehingga edit lokal dapat diproses dalam waktu logaritmik
• Namun, agar konversi Anchor -> run pada edit jarak jauh dapat dilakukan secara efisien, leaf yang memuat Anchor harus ditemukan

G-tree: B-tree yang direpresentasikan dengan indeks Vec

• Dengan hanya menggunakan pointer ke leaf B-tree biasa, sulit mengetahui cara turun sampai leaf dalam proses penyisipan top-down
• Operasi bottom-up membutuhkan pointer parent untuk setiap node, dan dalam model ownership aman Rust, ini memerlukan struktur seperti Rc<RefCell<_>> yang bisa menjadi lambat dan kompleks
• cola menyimpan semua node dalam array dinamis seperti Vec, dan merepresentasikan referensi antar-node bukan dengan pointer melainkan dengan indeks
  • Vector memiliki semua node
  • Setiap node dapat menyimpan indeks parent
  • Traversal dua arah dapat dilakukan tanpa kode unsafe
• Struktur ini bergantung pada asumsi bahwa indeks node tidak berubah
  • Node baru di-append ke akhir vector
  • Karena cola tidak menghapus run dan menandainya sebagai tombstone, masalah invalidasi indeks tidak muncul
• Struktur grow-only tree-in-a-vector ini disebut G-tree di cola
• Kode Rust G-tree adalah bentuk yang mempertahankan struktur parent-child B-tree sambil hanya mengubah representasi memorinya

Karakteristik performa yang dihasilkan G-tree

• Seperti B-tree, G-tree melakukan pencarian dan penyisipan top-down dalam waktu logaritmik
• LeafIdx, yaitu indeks vector leaf, dapat digunakan sebagai identifier leaf yang stabil
• Run active saat ini dapat di-cache sebagai LeafIdx, bukan pointer
  • Jika penyuntingan berulang dilakukan di posisi kursor yang sama, run active diperluas dan hanya panjang ancestor yang diperbarui sampai root
  • Ini dapat diproses hanya dengan beberapa perbandingan integer dan 2–4 penjumlahan integer, tanpa traversal tree atau alokasi baru
• G-tree cola menggunakan branching factor 32, dengan tingkat keterisian rata-rata inode sekitar 20 anak
  • Dengan hanya 4 level, biasanya dapat menyimpan sekitar 160 ribu EditRun berbeda
  • Setelah memproses trace edit automerge-paper, G-tree cola memiliki sekitar 15 ribu EditRun
  • Trace tersebut berisi 260 ribu edit dan direkam selama beberapa hari
• Karena node G-tree sudah tersimpan dalam memori linear, serialisasi dan deserialisasi juga sederhana

Mengubah Anchor menjadi LeafIdx

• Jalur downstream untuk edit jarak jauh adalah proses mengubah edit berbasis Anchor seperti insert 2.3..7 at 1.2 atau delete between 3.4 and 2.2 menjadi edit offset pada dokumen lokal
• Karena G-tree dapat ditelusuri ke atas dan ke bawah, jika LeafIdx dari run yang memuat Anchor diketahui, offset terkait dapat dihitung
• Kuncinya adalah konversi Anchor -> LeafIdx
• Desain sederhana adalah memiliki G-tree atau B-tree tambahan, lalu menyimpan ReplicaId, temporal range, dan LeafIdx dari G-tree utama pada leaf
  • Leaf diurutkan sepenuhnya berdasarkan ReplicaId dan temporal range
  • Tree dapat dituruni berdasarkan Anchor untuk menemukan LeafIdx yang diinginkan
  • Pencarian dan penyisipan sama-sama O(log n)
• Kode sumber cola sebenarnya tidak menggunakan pendekatan G-tree tambahan ini apa adanya
  • Implementasi aktual memiliki pencarian dan penyisipan O(log f)
  • f adalah jumlah fragment hasil pemecahan EditRun yang memuat Anchor selama waktu berjalan
  • f selalu tidak lebih besar dari n dan biasanya jauh lebih kecil

Tingkat kematangan saat ini dan pekerjaan tersisa

• Desain cola memiliki fondasi yang menargetkan konvergensi, pelestarian intensi, dan performa
• Agar siap produksi, dukungan undo/redo dan beberapa pekerjaan tambahan masih diperlukan

Benchmark CRDT Rust

• cola dibandingkan dengan 3 CRDT berbasis Rust
  • diamond-types
  • automerge
  • yrs
• Benchmark mengukur waktu pemrosesan trace edit nyata yang dilakukan karakter demi karakter
  • Menggunakan library benchmarking Rust criterion
  • Mengukur kedua arah, upstream dan downstream
  • Kode benchmark ada di crdt-benches
• Grafik menetapkan 100 kali performa cola sebagai baseline, dan tidak menampilkan pengukuran yang lebih dari 100 kali lebih lambat daripada cola
• Lingkungan eksekusi adalah MacBook Pro 2018, Intel Core i7 6-Core 2,2 GHz
  • Angka dapat berbeda di mesin lain, tetapi performa relatif diperkirakan serupa

Hasil benchmark

• Pada arah upstream, yrs dan automerge melewati baseline
• Pada upstream, cola 1,4–2 kali lebih cepat daripada diamond-types
• Pada arah downstream, diamond-types crash pada semua trace sehingga tidak ada hasil pengukuran
  • Disertai catatan bahwa hasil akan diperbarui jika ternyata library tersebut digunakan secara keliru
• Pada downstream, cola sekitar 2 kali lebih lambat daripada sebelumnya
  • Ini adalah hasil yang diperkirakan karena integrasi edit jarak jauh umumnya lebih mahal daripada pembuatan edit lokal
• cola berjalan pada tingkat yang mirip atau lebih cepat daripada library rope yang cepat di kedua arah, dan saat ini dinilai sebagai implementasi CRDT teks tercepat

[GN⁺]

Komentar Hacker News

• Saya tetap melihat G-tree sebagai B-tree dengan pointer induk yang ditambahkan
  Fakta bahwa ia disimpan dalam array hanyalah soal cara representasi, tidak mengubah strukturnya secara fundamental
  Ia tetap menyimpan pointer, hanya saja satuannya ukuran node, bukan byte, dan posisinya relatif terhadap elemen array pertama, bukan terhadap awal ruang alamat
  Misalnya, pohon biner lengkap yang disimpan dalam array tanpa referensi eksplisit pun tetap disebut pohon biner, hanya saja merupakan representasi implisit di mana anak dari indeks x berada di 2x + 1 dan 2x + 2

  • Meski begitu, membahas cara representasi tetap berguna
    Terutama dalam bahasa yang mendorong referensi yang relatif dan dikelola sendiri dibanding referensi absolut
    Salah satu cara representasi pohon yang menurut saya menarik adalah menyimpan node dalam array datar menurut urutan penelusuran depth-first
    Jika bersifat read-only dan pembaca memang akan menelusurinya secara depth-first, ini bisa cukup efisien
    Saya teringat S-expression dan HTML

• Kecuali ada yang saya lewatkan di API, tampaknya ini tidak mendukung rentang pemformatan seperti tebal dan miring
  Setahu saya, dalam algoritme CRDT untuk rich text, Peritext masih yang paling mutakhir https://www.inkandswitch.com/peritext/
  Akan bagus jika proyek ini juga mengadopsi kemampuan rich text dari algoritme Peritext

  • Sebagai orang yang cukup mengikuti bidang CRDT, saya selalu penasaran apakah mungkin membuat CRDT data terstruktur yang lebih umum
    Maksudnya, pengguna mendefinisikan model atau skema yang menjelaskan state yang valid secara semantik
    Misalnya, jika JSON digabungkan begitu saja, hasilnya bisa valid secara sintaksis tetapi tidak masuk akal secara semantik
    Seperti algoritme Peritext yang mengetahui bahwa tebal, miring, dan garis bawah adalah operasi yang dapat ditambahkan, sedangkan warna highlight tidak demikian, saya membayangkan akan bagus jika pengguna bisa menyatakan dalam skema bahwa state: notStarted dan completionDate: 2023-09-04 tidak bisa berlaku bersamaan
  • Pertanyaan: artikel mengatakan bahwa Cola hanya menangani pengeditan bebas konflik untuk tipe data yang tidak diketahuinya, dan pada dasarnya hanya menangani stream karakter dan posisi
    Kalau begitu, bukankah pemformatan itu sendiri bisa direpresentasikan di dalam teks, seperti HTML?
    Saya tidak terlalu memahami representasi rich text lain, jadi tidak yakin
    Selain itu, setelah membaca dokumen Peritext yang ditautkan di atas, ternyata dokumen itu memang membahas kesulitan khas RTF seperti ini, dan cukup menarik untuk dibaca

• Apakah ada perbedaan performa atau fitur dibanding Automerge atau Y.js/Yrs?

  • “Bagian ketiga” artikel dimulai dengan “kami membenchmark cola bersama tiga CRDT lain yang diimplementasikan dalam Rust: diamond-types, automerge, dan yrs”
    Pustaka cola ini tampaknya cukup unggul dalam hal kecepatan operasi
    Saya juga penasaran dengan penggunaan memorinya

• Jangan sampai tertukar dengan karya Ian Piumarta yang bernama sama
  https://www.piumarta.com/software/cola/
  https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

  • Atau ada juga Cache Oblivious Lookahead Arrays, yang dulu pernah dianggap sebagai alternatif MergeTree (LSM) tetapi kini tidak digunakan https://github.com/giannitedesco/cola
  • Ada juga aplikasi bergaya klon Notion bernama coda.io

• Ini karya yang dibuat dengan baik, tetapi tidak terlihat seperti benchmark yang adil
  Ia tidak menghitung dan menyimpan operasi, dan juga tidak menyimpan teks sebenarnya
  Untuk membuat CRDT teks yang mendukung pembaruan delta dengan ini, pengguna harus menyimpan OpID => Text di struktur terpisah, dan biayanya tidak murah

• Dengan memakai crate slotmap (https://docs.rs/slotmap/latest/slotmap/), penghapusan bisa didukung tanpa perlu khawatir indeks berpindah atau “indeks” menunjuk ke nilai lain
  Dalam slotmap, ini disebut key, dan key juga menyertakan nomor versi

  • Apakah ini juga bekerja dalam konteks CRDT?
    Saya penasaran karena pengurutan sulit dilakukan dan versi mungkin hanya bermakna secara lokal

• Saya berpikir untuk mencoba ini pada proyek yang tidak mampu ditangani Etherpad dan Word

• Jika diasumsikan semua klien yang terhubung menerima semua edit, mengapa tidak menaruh hash yang diharapkan dari state teks lama di depan perintah offset dan insert/delete/replace?
  Dengan begitu, hampir bisa dijamin bahwa edit hanya diterapkan pada state yang sesuai, dan perubahan berikutnya bisa dikumpulkan dalam dictionary dengan key berupa “hash state data yang diharapkan untuk diterapkan”
  Tentu biayanya besar karena harus menghitung operasi hash berulang pada data yang sama, tetapi ini sangat sederhana untuk dipahami dan diimplementasikan

  • Dengan cara itu, edit asinkron tidak akan pernah diterapkan
    Jika saya melakukan edit lokal pada dokumen, lalu Anda melakukan edit jarak jauh, hash “state yang diharapkan” dari Anda tidak akan pernah cocok dengan state dokumen saya
    Karena saya sudah membuat perubahan lokal
    Agar CRDT menjamin konvergensi, memang benar semua klien harus menerima semua edit, tetapi sifat bahwa pembaruan tidak perlu diterapkan dalam urutan tertentu penting dalam use case terdistribusi di dunia nyata

• Saya penasaran apakah ada cara mudah untuk mengaktifkan kolaborasi pengeditan form di browser
  Kalau dua orang membuka halaman atau form yang sama, akan bagus jika terlihat field input mana yang sedang diedit orang lain, dan field input teks memakai CRDT teks
  Saya pernah mencoba mengimplementasikan sesuatu yang mirip dengan Yjs, tetapi cukup sulit dan tidak berjalan dengan baik

  • Saya penasaran mengapa Yjs tidak cocok
    Untuk kebutuhan itu, kelihatannya justru sangat pas