- Penilaian bahwa CRDT lambat dalam penyuntingan kolaboratif sering kali merupakan hasil dari mencampuradukkan algoritme itu sendiri dengan cara implementasinya; performa dapat berubah drastis hanya dengan struktur data dan tata letak memori
- Automerge v1.0.0-preview2 menggunakan 291 detik dan RAM 880 MB untuk memproses trace 260.000 edit, sementara Diamond types native memproses pekerjaan yang sama dalam 56 ms dengan RAM 1,1 MB
- Yjs memanfaatkan daftar datar alih-alih pohon, cache posisi, linked list dua arah, dan penyimpanan span untuk menurunkan trace yang sama menjadi 0,97 detik dan RAM 3,3 MB
- Diamond types menggunakan struktur berbasis range tree/B-tree di Rust untuk menangani pencarian posisi, penyisipan, dan penghapusan dalam waktu
log(n), dan bahkan di WebAssembly mencatat 193 ms pada Node.js - Benchmark ini hanya melihat replay edit lokal pengguna tunggal dan penggunaan RAM, sehingga untuk pilihan nyata perlu juga mempertimbangkan waktu simpan/muat, ukuran jaringan/disk, binary encoding, protokol, presence, hingga editor binding
Algoritme dan performa implementasi adalah hal terpisah
- Sebuah perbandingan akademik mengimplementasikan penyuntingan kolaboratif real-time seperti Google Docs dengan beberapa algoritme CRDT dan OT lalu melakukan benchmark; sebagian algoritme membutuhkan lebih dari 3 detik hanya untuk memproses paste sederhana
- Pendekatan yang lambat adalah algoritme yang digunakan di ShareJS dan Google Wave, tetapi implementasi tersebut memecah paste 1.000 karakter menjadi 1.000 operation terpisah untuk diproses
- Kasus ini menunjukkan bahwa perilaku penyuntingan bersamaan dan cara implementasi harus dilihat secara terpisah
- Perilaku berarti urutan dan aturan penggabungan ketika edit bersamaan masuk ke area yang sama
- Implementasi mencakup bahasa pemrograman, struktur data, dan tingkat optimasi
- Fungsi text OT transform yang sama berjalan sekitar 100.000 kali per detik di JavaScript, sedangkan di C berjalan 20 juta kali per detik, menghasilkan selisih sekitar 200 kali
- Satu implementasi yang lambat bukanlah bukti bahwa semua implementasi sistem tersebut lambat; implementasi yang lebih cepat dimungkinkan
Model dasar CRDT dan Automerge
- CRDT memungkinkan banyak pengguna mengedit data yang sama secara bersamaan, bekerja secara lokal tanpa latensi, lalu melakukan sinkronisasi kemudian untuk mencapai eventual consistency
- Automerge adalah pustaka penyuntingan kolaboratif yang dibuat oleh Martin Kleppmann, dan berbasis algoritme RGA
- CRDT seperti Automerge dan Yjs melihat dokumen bersama sebagai daftar karakter, lalu memberi ID unik pada setiap karakter
- Jika mengetik
abcpada dokumen kosong, karakter diberi ID seperti(seph, 0),(seph, 1),(seph, 2) - Karakter baru juga mencatat “disisipkan setelah item yang mana”
- Jika mengetik
- Automerge/RGA menambahkan sequence number pada setiap item
- Item baru menerima nilai 1 lebih besar dari sequence number terbesar yang sudah dilihat sejauh ini
- Jika ada beberapa item anak, item diurutkan berdasarkan sequence number yang lebih besar terlebih dahulu; jika sama, diurutkan berdasarkan agent ID
- Perilaku Automerge/RGA dapat dilihat dalam tiga tahap
- Menghubungkan setiap item ke parent untuk membentuk pohon
- Untuk item yang memiliki beberapa anak, mengurutkan anak berdasarkan sequence number dan ID
- Meratakan pohon dengan depth-first traversal untuk membuat daftar akhir atau dokumen teks
Benchmark Automerge dan bottleneck
- Benchmark menggunakan trace edit dari automerge-perf
- Ini adalah trace yang merekam, per karakter, pengetikan makalah akademik oleh Martin Kleppmann
- Trace berisi 260.000 edit dan ukuran dokumen akhirnya sekitar 100.000 karakter
- Tidak mencakup edit bersamaan
- Pengujian hanya mengukur waktu untuk menerapkan trace secara lokal
- Lingkungannya adalah workstation Ryzen 5800x, Nodejs v16.1, Rust 1.52
- Automerge v1.0.0-preview2 membutuhkan 291 detik untuk memproses trace ini, dan RAM pada saat selesai adalah 880 MB
- Artinya sekitar 10 KB RAM digunakan per satu ketikan
- RAM puncak adalah 2,6 GB
- Pada spike yang lambat, pemrosesan satu edit membutuhkan 1,8 detik
- Baseline yang melakukan splice langsung pada string JavaScript memproses edit yang sama dalam 0,61 detik dengan RAM 0,1 MB, tetapi ini adalah baseline pembanding yang membuang semua informasi yang diperlukan untuk penyuntingan kolaboratif
- Ada beberapa alasan implementasi mengapa Automerge lambat
- Seiring dokumen membesar, struktur data berbasis pohon membesar dan melambat
- Penggunaan Immutablejs yang banyak membuat V8 optimizer dan GC sulit mengoptimalkan
- Setiap karakter yang disisipkan diperlakukan sebagai item terpisah, sehingga paste juga diproses sebagai banyak item
- Tim Automerge sedang mengerjakan implementasi alternatif yang memakai implementasi Rust automerge-rs melalui WASM
- Berdasarkan master branch saat itu, performa rata-rata pada pengujian ini belum menjadi lebih cepat, tetapi penggunaan memori berkurang setengah dan variasi performanya menjadi lebih halus
Implementasi daftar datar ala Yjs
- Yjs adalah implementasi CRDT open-source yang dibuat oleh Kevin Jahns, dan menyimpan semua item dalam satu daftar datar alih-alih pohon
- Pendekatan daftar datar bekerja dengan memindai dari tepat setelah parent untuk mencari posisi penyisipan item baru; ini adalah bentuk implementasi list CRDT sebagai daftar
- reference-crdts eksperimental mengimplementasikan YATA milik Yjs dan RGA milik Automerge dengan cara yang sama
- Fungsi insert memproses perilaku Yjs dan Automerge hampir melalui codepath yang sama, kecuali sedikit perbedaan
- Kesetaraan semantiknya diverifikasi dengan fuzzer
- Pendekatan ini memiliki tiga keunggulan
- Menggunakan flat array alih-alih pohon yang tidak seimbang, sehingga lebih kecil dan lebih cepat
- Kodenya sederhana
- Dapat diterapkan pada berbagai list CRDT seperti Yjs, Automerge, Sync9, dan lainnya
- Secara teoretis pendekatan ini bisa melambat jika ada banyak penyisipan bersamaan pada posisi yang sama, tetapi dalam penyuntingan nyata sebagian besar penyisipan terjadi tepat setelah parent
- Implementasi reference-crdts sekitar 10 kali lebih cepat daripada Automerge dan menggunakan RAM sekitar 30 kali lebih sedikit
| Pengujian | Waktu pemrosesan | Penggunaan RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Mengurangi biaya pemindaian dan penyisipan
- Implementasi array datar masih menyisakan dua bottleneck
- Harus memindai dokumen untuk menemukan posisi penyisipan
- Saat menyisipkan di tengah array dengan
doc.content.splice(destIdx, 0, newItem), item di belakangnya harus digeser
- Item yang dihapus bisa dirujuk oleh penyisipan lain, sehingga tidak dapat dihapus dari array dan harus diberi penanda seperti
isDeleted- Meski dokumen saat ini berisi 100.000 karakter, bisa ada 150.000 item array jika termasuk item historis
- Untuk menyisipkan di posisi dokumen 50.000, mungkin perlu memindai sekitar 75.000 item sambil melewati item yang dihapus
- Dalam struktur seperti ini, menyisipkan ke dokumen yang memiliki
nitem membutuhkan sekitarnlangkah, dan menyisipkannkarakter menjadi O(n²) - Yjs menyimpan cache pasangan
(index, position)dari posisi edit terakhir, menyesuaikan dengan cara manusia mengedit dokumen- Edit berikutnya kemungkinan besar berada di sekitar posisi edit sebelumnya, sehingga cukup memindai sedikit ke depan atau belakang
- Untuk kasus beberapa pengguna mengedit di posisi berbeda, Yjs menyimpan sekumpulan posisi yang di-cache
- Yjs menggunakan linked list dua arah alih-alih array, sehingga setelah posisi ditemukan, penyisipan dapat dilakukan dalam waktu konstan
- Yjs juga memanfaatkan fakta bahwa manusia mengetik karakter secara berurutan, sehingga
hellodisimpan sebagai satu span, bukan 5 item karakter- Collapse hanya dapat dilakukan ketika ID dan parent berurutan
- Pada dataset ini, jumlah entry array turun dari 180.000 menjadi 12.000, berkurang 14 kali
| Pengujian | Waktu pemrosesan | Penggunaan 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 |
Pendekatan range tree pada Rust dan Diamond types
- Objek JavaScript cenderung menjadi struktur dengan content, deletion flag, ID, seq, parent, dan lainnya tersebar sebagai pointer, sehingga biaya fragmentasi memori dan cache miss menjadi besar
- Rust memungkinkan pengendalian langsung atas tata letak memori, dan juga dapat digunakan di web melalui WebAssembly
- Diamond types adalah implementasi CRDT yang ditulis dalam Rust; hampir sama dengan Yjs, tetapi secara internal menggunakan range tree alih-alih linked list
- Range tree internalnya adalah B-tree yang sedikit dimodifikasi
- Alih-alih menyimpan key seperti
BTreeMapbiasa, node internal menyimpan jumlah total karakter yang terdapat pada child - Lookup posisi arbitrer dalam dokumen, penyisipan, dan penghapusan diproses dalam waktu
log(n)
- Alih-alih menyimpan key seperti
- Trace 260.000 edit disimpan dalam tree ini dengan sekitar 3 tingkat leaf node, sehingga item apa pun dapat ditemukan dengan kira-kira 3 kali memory read
- Untuk merge remote edit, ada juga index kecil yang mencari B-tree berdasarkan ID, tetapi codepath tersebut tidak termasuk dalam benchmark ini
- Leaf node menyimpan blok 32 entry secara rapat dalam array berukuran tetap
- Disebutkan bahwa bucket size 32 bekerja baik berdasarkan benchmark dengan berbagai ukuran, tetapi tidak diketahui mengapa ukuran itu optimal
- Jika Diamond di-compile ke WASM sebagai diamond-js dan dipanggil dari Node.js, trace yang sama diproses dalam 193ms
- Sekitar 5 kali lebih cepat daripada Yjs
- Sekitar 3 kali lebih cepat daripada baseline string JavaScript
- Eksekusi native Rust mencatat 56ms pada benchmark
- Lebih dari 5.000 kali lebih cepat daripada Automerge
- Memproses 4,6 juta operation per detik
- Selama pemrosesan total 260.000 edit, panggilan
mallochanya terjadi 1.394 kali
| Pengujian | Waktu pemrosesan | Penggunaan 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 | tidak diketahui |
| Diamond native | 0.056s | 1.1MB |
Pemisahan Ropey dan tradeoff
- Implementasi Diamond tidak menaruh isi teks dokumen langsung di daftar item CRDT, melainkan menyimpannya dalam struktur data terpisah
- Untuk isi teks, digunakan library Rust Ropey, dan Ropey juga mengimplementasikan B-tree untuk mengelola teks
- Pendekatan ini memiliki tradeoff rekayasa
- Karena Ropey melakukan byte packing khusus teks, penggunaan RAM dapat dikurangi
- Saat penyisipan, dua struktur data harus diperbarui, sehingga kecepatannya menjadi lebih dari 2 kali lebih lambat dan bundle WASM juga membesar dari 60KB menjadi 120KB
- Jika dihubungkan dengan editor seperti VS Code, editor mempertahankan salinan dokumen, sehingga mungkin tidak perlu menyimpan isi dokumen di dalam struktur CRDT
- Jika trace diproses hanya dengan Ropey, waktunya 29ms
- Jika pembaruan content dokumen dimatikan pada Diamond native, hasilnya 23ms dan RAM 0.96MB
- Sekitar 14.000 kali lebih cepat daripada Automerge
- Memproses 11 juta operation per detik
- Hasil ini lebih mendekati eksperimen untuk melihat batas pemrosesan metadata CRDT daripada kegunaan praktis
| Pengujian | Waktu pemrosesan | Penggunaan RAM | Struktur data |
|---|---|---|---|
| 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 | tidak ada |
| Diamond WASM via Node.js | 0.20s | tidak diketahui | B-tree |
| Diamond native | 0.056s | 1.1MB | B-tree |
| Ropey Rust baseline | 0.029s | 0.2MB | tidak ada |
| Diamond native, no doc content | 0.023s | 0.96MB | B-tree |
Kriteria memilih library nyata
- Jika membuat aplikasi kolaborasi berbasis dokumen saat ini, memakai Yjs lebih menguntungkan
- Yjs memiliki performa, penggunaan memori rendah, dan ekosistem dukungan yang baik
- Kevin Jahns juga menyediakan dukungan integrasi Yjs berbayar
- Tim Automerge juga menempatkan performa sebagai isu prioritas utama pada 2021, dan memiliki rencana membuat Automerge lebih cepat dengan berbagai teknik
- Diamond sangat cepat, tetapi masih banyak pekerjaan tersisa untuk mencapai parity fitur setingkat Yjs dan Automerge
- Selain kecepatan operation, library CRDT juga membutuhkan binary encoding, network protocol, struktur data non-list, presence, editor binding, dan lainnya
- Jika membutuhkan semantics database, belum diketahui implementasi yang bagus di atas CRDT; ShareDB berbasis OT dapat digunakan
- Redwood adalah proyek yang mendukung P2P editing dan berencana menyediakan full CRDT support
Keterbatasan metode pengukuran
- Benchmark ini hanya mengukur waktu replay trace edit lokal dan penggunaan RAM
- Input pengguna lokal cukup harus cepat; jika CRDT memproses satu local edit dalam sekitar 1 ms atau kurang, kecepatan yang lebih tinggi mungkin tidak terlalu penting
- Automerge juga umumnya memenuhi level ini, kecuali GC pause yang kurang beruntung
- Sebenarnya ada metrik lain yang lebih penting
- Jumlah byte yang ditempati dokumen di disk atau jaringan
- Waktu yang dibutuhkan untuk menyimpan dan memuat
- Waktu untuk memperbarui dokumen tersimpan di dalam database
- Trace yang digunakan hanya mencakup edit oleh satu pengguna, sehingga pathological case dengan banyak edit bersamaan mungkin masih ada
- Saat ini, untuk memperbarui satu objek database dengan Yjs atau Automerge, umumnya seluruh dokumen harus dimuat ke RAM, diubah, lalu seluruh dokumen disimpan kembali, sehingga bisa lambat
- Kevin mengatakan bahwa dengan penyesuaian Yjs provider yang tepat, ini bisa diimplementasikan dengan cara yang masuk akal
- list CRDT pada dasarnya terus membesar karena tombstone dari item yang dihapus, dan pruning adalah pendekatan terpisah
- Algoritme GC Yjs dan Antimatter muncul sebagai contoh
- Pruning adalah masalah yang ortogonal terhadap optimasi struktur data yang dibahas dalam tulisan ini
Perbandingan ini bukan eksperimen yang sepenuhnya terkontrol
- Setiap tahap optimasi mengubah beberapa variabel sekaligus, sehingga tidak memisahkan penyebab pasti peningkatan kecepatan
- Ada beberapa unsur yang berubah saat beralih dari Automerge ke reference-crdts
- Struktur data inti berubah dari tree menjadi list
- Immutablejs dihapus
- Automerge frontend/backend protocol dan berbagai struktur Uint8Array menghilang
- Gaya JavaScript berubah dari functional menjadi imperative
- Saat beralih dari reference-crdts ke Yjs, dan dari Yjs ke Diamond, perubahan juga tidak dipisahkan sebagai satu penyebab tunggal
- Fakta bahwa automerge-rs tidak lebih cepat daripada Automerge dalam pengujian ini menjadi dasar bahwa performa Diamond bukan semata-mata efek Rust, tetapi kontribusi persisnya tidak diketahui
- Membandingkan RGA dan YATA dengan cara implementasi yang sama juga bergantung pada premis bahwa “perilaku merge serentaknya pada dasarnya mirip, dan performa implementasi tetap terjaga meski perilakunya diubah”
- Dalam implementasi CRDT referensi, perilaku Yjs dan Automerge menunjukkan codepath yang hampir sama serta performa yang sama
- Pada conflict-heavy trace, bisa ada perbedaan performa, tetapi dalam praktiknya dianggap kasus yang sangat jarang
- Yjs tidak menyimpan kapan setiap item dihapus, hanya menyimpan apakah item tersebut dihapus atau tidak
- Jika Diamond menyimpan waktu penghapusan, penggunaan memori naik dari 1,12 MB menjadi 2,34 MB dan menjadi sekitar 5% lebih lambat
- Semua benchmark Diamond dalam tulisan ini menggunakan branch yjs-style yang disesuaikan dengan cara Yjs
Kode benchmark dan materi reproduksi
- Kode pengujian untuk baseline string JS, Yjs, Automerge, dan reference-crdts ada di GitHub gist
- Sebagian besar pengujian memerlukan
automerge-paper.json.gzdari josephg/crdt-benchmarks - Benchmark reference-crdts bergantung pada versi josephg/reference-crdts tersebut
- Benchmark Diamond dijalankan di versi josephg/diamond-types tersebut
- Perintah menjalankannya adalah
RUSTFLAGS='-C target-cpu=native' cargo criterion yjs - memory statistics diperiksa dengan
cargo run --release --features memusage --example stats
- Perintah menjalankannya adalah
- Diamond WASM wrapper menggunakan diamond-js, dan wasm bundle dioptimalkan dengan
wasm-opt - Grafik dibuat di ObservableHQ
1 komentar
Komentar Hacker News
Jika mereka memakai integer 2 byte, kemungkinan besar alasannya adalah cache line 64 byte
32 entri akan pas menjadi tepat satu cache line, sehingga tiap cache line memuat satu bucket utuh dan mengurangi transfer memori utama yang mahal
Pada dasarnya ia memasukkan counter untuk menghitung berapa kali sesuatu harus dibaca dari memori; saya penasaran apakah dengan cara serupa kita bisa memperkirakan berapa kali cache line harus dikosongkan
Lompatan itu muncul di batas-batas seperti ukuran word (64 bit), ukuran fetch yang selaras cache (biasanya 64 byte seperti disebut di atas), ukuran halaman OS (4–16KB), ukuran L1 (sekitar 80KB per core), dan L2 (di kisaran beberapa MB)
Saya penasaran aplikasi apa saja yang pengalaman nyatanya sangat baik saat memakai CRDT di layanan sungguhan
Saya ingat Notion termasuk salah satunya, tetapi secara realistis, dua orang mencatat bersama di Notion hampir tidak bisa dipakai dibandingkan Google Docs
Ini adalah IDE untuk tugas dan perencanaan, aplikasi multipengguna, mendukung enkripsi end-to-end, offline-first, self-hosting opsional, dan karena seluruh workspace adalah satu graph, CRDT menjadi pilihan yang alami
Semua tindakan di Thymer direduksi menjadi sejumlah kecil transformasi CRDT. Memindahkan/menyalin teks, mengubah properti "frontmatter", menyeret kartu, mengunggah file, menambahkan tag—semuanya ditangani oleh beberapa operasi CRDT yang sama
Di awal, mengimplementasikannya tanpa library memang banyak pekerjaan, tetapi jika state aplikasi adalah satu graph, fitur seperti memindahkan teks antarhalaman, tautan halaman dengan backlink, dan transclusion bisa dibuat tanpa khawatir soal sinkronisasi, jadi jelas sepadan
CRDT menjamin semua klien berkonvergensi ke state yang sama, dan karena pada dasarnya append-only, versioning pada titik waktu tertentu juga didapat gratis
Namun karena performa, kami membuat beberapa kompromi. Riwayat versi berisi terlalu banyak data sehingga tidak disediakan secara offline, dan dalam beberapa kasus kami memakai penyelesaian konflik last-writer-wins
Secara keseluruhan, ini sangat bernilai, terutama jika sejak awal aplikasi dirancang dengan CRDT dalam pikiran. Jika situasinya adalah menambahkan fitur multipengguna belakangan ke aplikasi AJAX yang lebih tradisional, saya mungkin tidak akan memakai CRDT
Perubahan CRDT pertama-tama diterapkan secara optimistis, lalu setelah urutan event yang otoritatif ditetapkan, semua klien harus kembali ke state bersama terakhir dan menerapkan ulang semua event dalam urutan yang benar
Jika sudah lama offline, mungkin perlu membatalkan dan menerapkan ulang perubahan selama beberapa hari. Pengguna tidak tahu berapa banyak transformasi tree yang terjadi di belakang layar, tetapi CRDT memengaruhi keseluruhan desain aplikasi
Sebagian besar aplikasi populer saat ini dirancang pada masa ketika transformasi CRDT belum dipahami dengan baik
[1] https://thymer.com (hampir siap beta)
Teks bersifat last-writer-wins, dan teks atau properti tiap blok adalah register last-writer-wins. Mereka sedang mengerjakan format CRDT baru untuk teks blok
Ini mencakup Notes dan Reminders, dan mungkin juga Photos. Saya mendengar dari mantan SRE Apple yang sedang mabuk di bar bahwa FoundationDB juga dipakai sebagai bagian dari backend
Presentasi Local First Conf ini juga layak dilihat: https://youtu.be/VLgmjzERT08
Semua game jaringan yang melakukan rollback atau koreksi dalam bentuk apa pun cukup dekat dengan ini. Bentuk yang menempatkan rollback sebagai jalur alternatif di atas pendekatan best-effort mungkin merupakan bentuk CRDT yang paling baik dari sisi pengalaman pengguna di antara yang banyak dipakai
Ini bukan CRDT dalam arti akademis yang ketat. Secara teknis, state game tidak direplikasi sepenuhnya ke semua klien, dan tiap klien hanya menerima sebagian state game
Selain itu, klien game membutuhkan sinkronisasi latensi rendah, dan secara akademis hal itu mungkin dianggap sebagai "koordinasi". Dalam praktiknya, klien secara probabilistik menerima dan merender hasil input secara lokal sebelum penyelesaian konflik atau koreksi rollback kembali
Mungkin ada yang akan mempermasalahkan detailnya, tetapi jika melihat sampai contoh ketiga, tema umumnya akan terlihat. CRDT yang paling populer, paling enak dipakai, dan paling baik implementasinya sebenarnya melanggar aturan akademis
Ini adalah jebakan klasik dari model berpikir yang terlalu akademis. Algoritma dan tipe data di dunia nyata sering kali jauh lebih kreatif daripada "buku aturan" akademis. Contohnya Timsort
Jika Anda membuat produk untuk pengguna nyata, bukan untuk peer review makalah, jangan terjebak dalam over-engineering/akademisme. Pelajari aturan akademis, tetapi langgarlah dengan sengaja; daripada mencoba mengimplementasikan secara sempurna konsep yang didefinisikan begitu ketat hingga hanya berguna bagi sesama akademisi, tambahkan nilai nyata dan buatlah nyaman digunakan
CRDT memang kuat, tetapi sayangnya, baik berbasis operasi maupun berbasis status, ia meninggalkan jejak operasi atau elemen masa lalu
Walau dikompresi, ini tetap menjadi kelemahan dan menjadi hal yang membuat orang ragu untuk mengadopsinya
Meski begitu, berkat diskusi ini saya jadi tertarik pada kemungkinan menerapkan algoritme tanpa konflik atau algoritme resolusi konflik yang lebih halus di atas penyimpanan berbasis berkas seperti Dropbox dan Syncthing
Proyek pasca-CRDT saya, Diamond Types, pada dasarnya memang tumbuh tanpa batas seiring waktu, tetapi overhead-nya biasanya kurang dari 1 byte per karakter yang pernah diketik sejauh ini
Jika kompresi LZ4 diaktifkan pada teks yang disimpan, dokumen yang diedit dengan Diamond Types sering kali lebih kecil daripada status akhir dokumen, meskipun menyimpan seluruh riwayat penyuntingan
Secara teknis saya tahu beberapa cara untuk mengatasi ini, tetapi saya tidak yakin bahwa ini adalah masalah nyata di kebanyakan sistem
Saya pernah mendengar seseorang yang menggunakan yjs untuk alat pemodelan 3D mengalami masalah. Penyebabnya adalah setiap kali mouse bergerak per piksel saat menyeret objek, ia membuat edit persisten
Untuk pekerjaan seperti itu, menurut saya lebih bijak memakai edit sementara, yang tidak didukung oleh kebanyakan pustaka CRDT
Sebagai catatan, Git juga punya masalah yang sama. Repositori membesar seiring waktu, dan membesar jauh lebih cepat dibanding saat memakai pustaka CRDT modern. Namun tampaknya tidak ada yang terlalu mempermasalahkannya
Di Git memang ada shallow clone, tetapi hampir tidak ada yang melakukannya. Jika mau, hal yang sama juga bisa dilakukan di CRDT
Misalnya, jika bisa dijamin bahwa semua klien sudah menerima perubahan setelah tanggal X, operasi sebelum tanggal itu bisa dibuang dengan aman
Saya sedang membuat Fireproof[1] untuk memanfaatkan riset terbaru di bidang ini
Dengan memberi alamat berbasis konten pada data imutabel, ada manfaat tambahan bahwa setiap operasi berujung pada bukti atau diff yang dijamin secara kriptografis. Ini bisa menegakkan konsistensi kausal dan membuat referensi yang stabil ke snapshot
Dengan kata lain, kita bisa menjalankan database yang bisa berinteraksi, bekerja offline, dan di-merge tanpa kehilangan data di edge atau browser, sambil tetap memiliki integritas yang dulu diharapkan dari database terpusat atau blockchain
Misalnya, snapshot CID bisa dimasukkan ke PDF untuk penandatanganan atau ke smart contract, sehingga tidak ada ambiguitas tentang status yang dirujuk
[1] https://github.com/fireproof-storage/fireproof
Pada akhirnya, daripada berbicara terlalu umum tentang sekumpulan hukum matematika yang diikuti suatu tipe data atau database tertentu, lebih tepat mengkritik implementasi konkretnya
Ini tulisan tahun 2021 dan sepertinya juga mencakup implementasi Rust Automerge, jadi akan menarik melihat benchmark yang diperbarui
Saya juga punya pendekatan baru yang sepenuhnya berbeda untuk memecahkan masalah ini
Akan sangat bagus kalau benchmark-nya diperbarui. Semuanya sudah menjadi lebih cepat
Banyak bagian isinya sulit saya pahami, tetapi tulisannya begitu bagus sehingga ini termasuk tulisan langka yang membuat saya terus membaca tanpa berhenti
Ini diskusi-diskusi terkait sebelumnya
https://news.ycombinator.com/item?id=28017204 (3 tahun lalu, 151 komentar)
https://news.ycombinator.com/item?id=33903563 (2 tahun lalu, 22 komentar)
https://news.ycombinator.com/item?id=41372833 (postingan saat ini)
https://news.ycombinator.com/item?id=41373288 (komentar saat ini)
Mengutip GitHub Readme[0] saat ini, katanya performanya kembali meningkat 10–80 kali sejak tulisan blog itu
[0] https://github.com/josephg/diamond-types
Akan bagus kalau ada yang bisa menjelaskan mengapa CRDT lambat
Tulisan ini sepertinya menunjukkan masa depan: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
Akan menarik membandingkan ini dengan Y.js atau Automerge: https://github.com/canvasxyz/okra-js
Sejak saya menulis artikel ini beberapa tahun lalu, semua pustaka CRDT utama sudah menjadi lebih cepat hingga beberapa orde magnitudo
Saya ingat pernah tidak sengaja menemukan tulisan ini beberapa tahun lalu
Benar-benar tulisan yang menarik, dan salah satu tulisan favorit saya dalam beberapa tahun terakhir
Mengenai “mengapa WASM 4 kali lebih lambat daripada eksekusi native?”, saya mengira itu karena semua operasi string harus disalin ke memori WASM, lalu setelah hasilnya dihitung harus disalin kembali ke JS
Apakah saya salah? Apakah saya salah memahami konteksnya? Saya benar-benar penasaran
Saya memuat seluruh riwayat ke dalam wasm sebelum mengukur waktu, lalu memprosesnya dalam loop internal yang ditulis dengan Rust dan berjalan di konteks wasm itu sendiri. Pemanggilan wasm hanya sekitar dua kali
Penyebab perlambatan 4 kali bukan FFI, melainkan kode algoritmanya sendiri memang berjalan 4 kali lebih lambat
Akan menarik kalau benchmark-nya dijalankan ulang sekarang. Output wasm dari compiler juga sudah membaik, dan runtime wasm juga mungkin sudah lebih cepat. Kode benchmark-nya sepertinya masih ada di suatu tempat
Masalah yang terus mengganjal di area terpisah adalah pembahasan soal multithreading tidak mudah, dan dukungan library serta tooling juga belum sepenuhnya matang
Saya pernah menjalankan binary utilitas seperti game engine, ffmpeg, atau zip di browser, dan karena hal ini hasilnya sangat lambat
Saya belum pernah menangani interpreter atau JIT WASM, tetapi seberapa sering melewati beberapa lapisan terjemahan bisa lebih baik daripada melewati satu lapisan saja?
Saat kode tingkat tinggi diterjemahkan ke WASM atau bahasa assembly apa pun, banyak intensi yang ada di kode tingkat tinggi hilang
Dalam kode tingkat rendah, kita sering melihat rangkaian idiom khusus bahasa untuk mencapai tujuan tertentu, yang bisa saja punya padanan langsung pada mesin sebenarnya, bisa juga tidak
x86-64 modern memiliki sangat banyak instruksi yang jauh lebih kuat daripada yang bisa dilakukan di WASM
Tentu saja ada decompiler, dan mungkin ada daftar macro-op fusion yang memungkinkan JIT WASM menghasilkan kode native yang bagus lewat pattern matching yang relatif sederhana. Mungkin tidak begitu, dan optimasi lintas platform tentu lebih sulit
LLVM juga tidak sempurna, jadi pasti ada bagian-bagian mudah yang bisa diperbaiki oleh optimizer pascaproses. Karena itu, secara teori bukan mustahil membuat WASM lebih cepat daripada output native LLVM
Namun tanpa rencana yang sangat matang, atau tanpa membuat instruction set yang pada dasarnya merupakan superset dari apa yang didukung arsitektur instruction set target, menurut saya sangat sulit mendapatkan hasil di level yang sama
Bagi saya, WASM lebih mendekati subset, sehingga menstandarkan operasi lalu menggabungkannya kembali secara real-time bukanlah hal mudah. Meski tidak sepenuhnya mustahil, itu membutuhkan pencapaian engineering yang besar
Secara intuitif, jika buku berbahasa Inggris diterjemahkan ke bahasa yang sangat berbeda dan dibatasi hanya beberapa ribu kata, lalu diterjemahkan kembali ke bahasa Inggris, teks yang persis sama tidak akan muncul
Ada kalanya konsep yang dalam bahasa Inggris cukup satu kata harus dijelaskan dengan satu paragraf. Untuk mendapatkan kembali bahasa Inggris aslinya, diperlukan terjemahan 1:1 untuk semuanya, atau daftar terjemahan paragraf→satu kata yang disepakati oleh kedua penerjemah