Kebohongan tentang Penyuntingan Kolaboratif, Bagian 1: Algoritme untuk Penyuntingan Offline
(moment.dev)- Dari evaluasi Moment terhadap penyuntingan kolaboratif untuk editor teks intinya, algoritme keluarga CRDT dan OT dapat menghasilkan hasil penggabungan yang oleh pengguna dianggap sebagai kerusakan data dalam konflik langsung offline
- Bahkan dalam contoh sederhana ketika Alice menghapus seluruh kalimat dan Bob mengubah
ColormenjadiColour, dapat muncul hasil yang tidak dimaksudkan manusia, seperti dokumen akhir yang hanya menyisakan hurufu - Dalam kasus penggunaan Moment, sekitar 20–30% konflik langsung yang dicoba menghasilkan hasil yang sulit diterima, dan karena frekuensi serta reaksi negatifnya, Moment menilai sulit untuk membelanya sebagai pengalaman produk
- Yjs, ShareJS, dan Peritext mengklaim mendukung penyuntingan offline, kolaborasi dengan latensi lama, atau penggabungan otomatis salinan independen, tetapi algoritmenya tidak dapat mengetahui maksud dan urutan pengguna sehingga bergantung pada heuristic
- Penyuntingan kolaboratif offline bukan sekadar masalah algoritme, melainkan lebih dekat ke masalah UI/UX; dibutuhkan pengalaman penggabungan yang dapat dibaca dan dinilai manusia, seperti UI merge git atau collaborative history dari Ink & Switch
Keterbatasan yang Terungkap dalam Evaluasi Penyuntingan Kolaboratif Moment
- Pada awal 2024, Moment mulai meneliti sistem penyuntingan kolaboratif untuk digunakan pada editor teks intinya
- Berbagai algoritme mengklaim dapat menangani bukan hanya penyuntingan simultan online, tetapi juga kasus offline, yaitu ketika pengguna mengedit secara offline selama waktu yang tidak dibatasi lalu perubahan digabungkan otomatis saat kembali online
- Setelah melihat makalah dan presentasi pada tahap awal, Moment berharap komunitas penyuntingan kolaboratif telah mencapai “jawaban yang benar” untuk keseluruhan masalah ini
- Dalam proses evaluasi, algoritme keluarga CRDT dan OT menyelesaikan konflik penyuntingan langsung dengan cara yang tidak intuitif, dan pengguna menerima hasilnya sebagai kerusakan data
- Karena penyuntingan offline sangat meningkatkan kemungkinan konflik langsung, sulit bagi Moment untuk menciptakan pengalaman penyuntingan offline yang diinginkan hanya dengan algoritme seperti ini
Contoh Sederhana Konflik antara Penghapusan dan Koreksi Ejaan
- Alice dan Bob sama-sama mengedit dokumen yang sama dalam keadaan offline
- Dokumen berisi teks
The Color of Pomegranates - Bob mengubah ejaan
Colormenjadi gaya InggrisColour, sementara Alice menghapus seluruh teks - Saat keduanya kemudian online, kedua penyuntingan itu berkonflik, dan sistem harus menyesuaikannya tanpa mengetahui penyuntingan mana yang terjadi lebih dulu
- Dalam contoh ini, Alice dan Bob akhirnya mendapatkan dokumen yang hanya berisi huruf
u- Ini bukan kalimat yang valid, juga bukan kata yang valid
- Pengguna akan menganggap hasil seperti ini sebagai Moment yang merusak data mereka
Hasil Aneh dari Konflik Langsung Tidak Jarang Terjadi
- Konflik ini adalah konflik penyuntingan yang sepele dan langsung, tetapi masih berada dalam cakupan yang bisa dikatakan didukung oleh algoritme penyuntingan kolaboratif populer
- Hasil nyatanya adalah dokumen yang tidak akan ditulis sendiri oleh manusia, dan ditafsirkan sebagai produk Moment yang merusak data
- Tergantung kasus penggunaannya, tetapi dari konflik langsung yang dicoba Moment, kira-kira 20–30% menghasilkan hasil yang sulit diterima untuk kasus penggunaan penyuntingan offline
- Dengan melihat umpan balik negatif dan frekuensi kemunculannya bersama-sama, Moment menilai hasil seperti ini sulit dijelaskan dan dipertahankan kepada pengguna
Dukungan Penyuntingan Offline yang Diklaim Berbagai Alat
- Pada awalnya, ketika hasil seperti ini muncul, Moment mengira mereka salah memahami makna dukungan yang diberikan alat-alat tersebut
- Namun deskripsi tiap proyek dapat dibaca bahwa skenario tersebut berada dalam cakupan dukungan
- Yjs secara eksplisit menyatakan di README bahwa ia mendukung
offline editing - ShareJS menjelaskan bahwa pengguna dapat berkolaborasi pada latensi apa pun, mulai dari latensi nol hingga setingkat liburan panjang
- Peritext menjelaskan bahwa pengguna dapat mengedit salinan independen dari dokumen dan menggabungkannya otomatis dengan cara yang sebisa mungkin mempertahankan maksud pengguna
- Yjs secara eksplisit menyatakan di README bahwa ia mendukung
- Moment masih mencari solusi untuk masalah ini, tetapi menilai sulit menyelaraskan frekuensi dan jenis kesalahan yang benar-benar dilihat dengan klaim-klaim tersebut
Keterbatasan Mendasar Algoritme Tanpa Koordinasi
- Seiring evaluasi berjalan, Moment sampai pada kesimpulan bahwa algoritme-algoritme tersebut tidak berperilaku seperti yang Moment inginkan
- Pertanyaan yang tersisa adalah apakah masalah ini bisa diperbaiki melalui kontribusi, atau merupakan keterbatasan mendasar dari algoritmenya
- Ada tiga alasan mengapa ini dipandang sebagai masalah mendasar
- Algoritme tidak dapat mengetahui maksud Alice dan Bob, dan tidak dapat menanyakannya lewat email atau meninjaunya seperti UI GitHub Pull Request
- Algoritme harus menerima usulan penghapusan menyeluruh dari Alice dan koreksi ejaan dari Bob, lalu menentukan hasil dengan heuristic
- Algoritme bekerja pada tingkat karakter dan hanya memberikan jaminan yang sangat lemah atas keluarannya
- Alice dan Bob mungkin akan memutuskan untuk mengedit secara berbeda jika mereka tahu apa yang sedang dilakukan pihak lain
- Algoritme semacam ini juga terkait dengan masalah bahwa ia tidak dapat mengikuti urutan kausal
Penyuntingan Offline Lebih Dekat ke Masalah UI/UX
- Moment berharap bahwa dengan mengimplementasikan algoritme yang rumit, dukungan penyuntingan offline sejati akan ikut tersedia sebagai efek samping, tetapi setelah evaluasi, pandangan itu menjadi sulit dipertahankan
- Pengguna wajar melihat hasil algoritme sebagai kerusakan data; hasil-hasil aneh itu melekat pada algoritme itu sendiri dan dapat terjadi cukup sering hingga menjadi masalah nyata
- Interpretasi lainnya adalah bahwa penyuntingan kolaboratif membutuhkan investasi sumber daya UI/UX yang signifikan
- Algoritme tidak dapat menyelesaikan masalah sepenuhnya, tetapi dapat menjadi bagian dari solusinya
UI Merge git dan Arah Riset
- Sudah ada UI penggabungan dokumen yang diadopsi luas, yaitu
git - Pertanyaan risetnya lebih dekat ke bagaimana membuat pengalaman ini lebih mudah diakses, lebih mudah dipahami, dan lebih otomatis
- Sekitar tahun 2009, ada banyak diskusi tentang algoritme yang digunakan git untuk menggabungkan perubahan secara otomatis
- git mengadopsi Myers O(ND) diff algorithm, algoritme yang terutama digunakan biolog untuk analisis sekuens jenis BLAST
- Bram Cohen menilai hasil diff tidak intuitif dan membuat patience diff algorithm, yang kemudian diadopsi oleh bzr, alat pesaing git yang kini sudah dihentikan
- Diskusi saat itu berfokus pada pembuatan diff yang dapat dibaca manusia, tetapi diskusi saat ini lebih dekat pada apakah algoritme dapat mencapai hasil tersebut tanpa campur tangan manusia
- Riset yang memperlakukan penyuntingan kolaboratif sebagai masalah UI/UX sedang berjalan, seperti collaborative history dari Ink & Switch
1 komentar
Komentar Hacker News
Saya adalah penulis Eg-walker dan ShareJS. Tulisan ini mungkin terlihat seperti bernada menentang pekerjaan saya, tetapi sebenarnya saya sepenuhnya setuju dan sudah mengatakan hal yang sama di HN sejak beberapa tahun lalu
Alat kolaborasi real-time saat ini cocok ketika semua orang mengedit bersama secara online, tetapi jika pengguna mengedit secara offline atau di branch yang dipertahankan lama, saat merge diperlukan penanda konflik dan opsi peninjauan manual. Terutama untuk kode
Untungnya, algoritma seperti egwalker menyimpan jejak edit tingkat karakter dari semua pengguna serta urutan kausalnya, yakni urutan perubahan seperti Git DAG, sehingga memiliki jauh lebih banyak informasi daripada Git. Jadi seharusnya mungkin membuat CRDT yang dapat mendeteksi dan menandai rentang konflik saat merge branch, lalu membiarkan pengguna menyelesaikannya secara manual
Secara algoritmik ini menarik, tetapi tampak seperti masalah yang cukup bisa diselesaikan, dan anehnya sejauh ini hampir tidak ada yang mencoba di ranah pengeditan teks. Jika ingin memberi kontribusi yang orisinal dan bernilai di bidang ini, ini adalah potongan penting yang hilang dari ekosistem CRDT, jadi saya berharap ada yang mencobanya
[1] Bagian bawah komentar ini: https://news.ycombinator.com/item?id=19889174
Tantangan menarik berikutnya adalah ketika muncul konflik seputar penyelesaian konflik itu sendiri
Mengevaluasi sistem seperti ini sendiri sudah merupakan masalah teknis yang cukup sulit, jadi saya kira banyak tim akan kesulitan. Karena itu mereka berhak mendapatkan saran praktis, dan saya juga merasa kami seharusnya mengetahui ini lebih awal
Bagian yang sulit adalah menandai bahwa konflik sudah diselesaikan. Bisa saja sesederhana menambahkan satu field ke CRDT, tetapi saya tidak tahu apakah itu harus dianggap sebagai solusi algoritmik juga
[1] https://josephg.com/blog/crdts-go-brrr/
Kalau yang diedit adalah kode program, ini menjadi lubang kelinci yang jauh lebih dalam karena kita mengharapkan hasil merge tetap berupa program yang valid. Saya pernah mendengar ada proyek di JetBrains yang mencoba menyelesaikan ini dengan merge berbasis AST, tetapi setelah menggali jauh lebih dalam mereka menilai itu tidak sepadan untuk dikerjakan
“Pengeditan offline” yang diperbolehkan dalam dokumen yang ditulis manusia hanyalah menambahkan komentar. Bukan mengedit, dan tidak ada merge otomatis
Untuk “pengeditan offline” pada source code yang menjadi sasaran otomatisasi, kita memakai Git; Git tidak berpura-pura menyelesaikan merge, hanya menampilkan revisi. Merge adalah pekerjaan yang diawasi manusia atau dilakukan otomatisasi khusus dengan perkiraan terbaik, dan untuk memastikan keberhasilannya tetap diperlukan review dan test
Algoritma merge mekanis bisa lebih baik atau lebih buruk tergantung jenis konfliknya, tetapi pada akhirnya CRDT mana pun tidak bisa menilai apakah teks hasil merge adalah hal yang ingin dikatakan pengguna
Makalah Upwelling membahas lebih rinci perbedaan yang dalam penulisan disebut konflik semantik dan konflik tata bahasa: https://inkandswitch.com/upwelling/
Saya merasa kolaborasi serius pada akhirnya juga merupakan masalah review dokumen. Dalam jurnalisme atau publikasi ilmiah terutama begitu, sementara untuk notulen rapat biasanya mungkin bisa diabaikan
Saya juga ingin menautkan Upwelling, tetapi tidak ingat namanya dan karena tenggat saya menggantinya dengan tautan lain
Sisi gelap lain dari implementasi CRDT adalah beban infrastruktur. Dulu saya pernah menulis cukup mendalam tentang ini[0], dan saya senang mengetahui bahwa Supabase juga mencapai kesimpulan yang sama dengan temuan empiris saya dalam tulisan mereka beberapa tahun lalu tentang ekstensi CRDT untuk Postgres[1]
Jika akan menggunakan CRDT, lebih baik gunakan sesuatu seperti Redis, atau meski penggunaan memorinya menyakitkan untuk dibayangkan, gunakan basis MyRocks[2] atau RocksDB/LevelDB. Apa pun yang Anda lakukan, jangan jadikan RDBMS, terutama Postgres, sebagai backend
[0]: https://news.ycombinator.com/item?id=40834759
[1]: https://supabase.com/blog/postgres-crdt
[2]: http://myrocks.io
Pengamatan dalam tulisan ini akurat. CRDT adalah model formal yang sangat baik untuk struktur data terdistribusi, tetapi saya selalu merasa kurang nyaman dengan gagasan bahwa semua konflik harus diselesaikan otomatis, sesuai namanya: tipe data tereplikasi bebas konflik
Seperti yang ditunjukkan tulisan ini, menurut saya itu upaya yang tidak punya harapan. Yang dibutuhkan adalah representasi struktural yang tepat agar konflik bisa dibagikan dan diselesaikan secara kolaboratif, mengembalikan kendali kepada pengguna, dan mendukung proses penyelesaiannya. Salah satu makalah favorit saya, “Turning Conflicts into Collaboration” [1], membahas ide ini dengan meyakinkan
Dalam riset doktoral saya yang sedang berjalan, saya mengembangkan “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2], sebuah model formal untuk representasi konflik struktural berbasis teori lattice. Secara kebetulan ini juga CRDT, tetapi tidak mencoba menyelesaikan konflik secara otomatis; konflik direpresentasikan di dalam dokumen kolaboratif. Dengan pendekatan matematis, saya bisa sampai pada model konseptual sederhana yang menjamin sifat-sifat kuat seperti kelengkapan, minimalitas, dan keunikan merge bahkan setelah konflik lama di-merge berulang kali, dan perhitungan merge-nya juga sangat mudah
[1] https://doi.org/10.1007/s10606-012-9172-4
[2] https://doi.org/10.14279/tuj.eceasst.82.1226
Konflik adalah konsep yang rumit, dan meskipun “conflict-free” secara teknis benar sebagai deskripsi hasil, seperti terlihat dari tulisan ini dan pembahasan di atas, istilah itu bisa menimbulkan salah paham
Komutativitas adalah sifat bahwa meskipun Bob menerapkan perubahan dalam urutan [Bob, Alice] dan Alice menerapkannya dalam urutan [Alice, Bob], keduanya tetap sampai pada dokumen yang sama. Itu bukan berarti dokumen tersebut “bebas konflik” dalam pengertian yang bermakna pada tingkat abstraksi yang lebih tinggi
Menurut saya, konsep bahwa beberapa pihak berbeda secara bersamaan memiliki otoritas atas satu potongan data tanpa koordinasi real-time pada dasarnya tidak bisa diselesaikan secara umum. Ini adalah pelajaran yang sudah kita dapat dari sistem terdistribusi, dan terlihat jelas juga dalam tulisan ini jika memikirkan penyuntingan dokumen terdistribusi
Prinsip yang sama tampaknya berlaku juga pada contoh-contoh lain yang berbeda, seperti input ganda di kokpit pesawat, pengasuhan anak, dan apa pun lagi yang bisa terpikirkan
Dan menyebut ini “bisa diselesaikan” pun terasa lucu, karena saat ini tampaknya sebagian besar dunia menganggap keluaran LLM yang kacau sebagai sesuatu yang hampir menentukan hasil akhir komputasi
Algoritma yang umum dipakai untuk penyuntingan teks kolaboratif, yaitu CRDT dan OT, memiliki persyaratan aljabar yang ketat tentang apa yang dilakukan operasi penyuntingan dan bagaimana operasi itu saling berinteraksi
Jadi meskipun server cukup pintar untuk menangani contoh “Colour” secara masuk akal dari sisi UX, merancang CRDT/OT padanan untuk penyuntingan optimistis di sisi klien sangatlah sulit
Ini bisa dihindari jika tidak menggunakan CRDT/OT. Misalnya, server memproses operasi sesuai urutan penerimaan dan menerapkan logika UX yang diinginkan, sementara klien menggunakan strategi rebase/prediksi di atasnya agar penyuntingan optimistis tetap dimungkinkan. Referensi: https://doc.replicache.dev/concepts/how-it-works
Menerapkannya pada penyuntingan teks juga punya kesulitan tersendiri, tetapi itu terpisah dari masalah CRDT/OT yang dibahas di sini
Menurut saya ini terjadi karena konsep konflik yang matematis, kausal, dan entropis tercampur dengan konflik semantik. Saya juga dulu pernah melakukan kesalahan yang sama dari arah sebaliknya, lalu diberi tahu dengan tegas bahwa saya tidak tahu apa yang saya bicarakan
Begitu mulai mempertimbangkan tree, semuanya menjadi jauh lebih berantakan. Misalnya yJS bekerja pada dokumen JSON. Jika UI hanya menampilkan level dangkal dan level yang lebih dalam tidak dibuka, pengguna mungkin bahkan tidak melihat penyuntingan yang telah dihapus
Kelas CRDT yang mempertahankan konflik—kalau saya ingat, kasus register yang bisa memiliki banyak nilai—tampaknya paling menjanjikan. Pengguna harus disajikan konflik semacam itu, dan konflik tersebut bahkan bisa ditampilkan sepenuhnya secara visual. Memberi kemampuan menelusuri riwayat juga tampak sebagai alternatif praktis agar pengguna bisa memahami bagaimana hal-hal aneh terjadi, atau bagaimana perubahan mereka menghilang
Saya ingat Torvalds sendiri cukup pesimistis tentang apa yang bisa dicapai dengan merge otomatis. Dan penilaian itu benar
Ia mengatakan bahwa Git menolak gagasan bahwa sistem version control bisa atau seharusnya “menyelesaikan masalah merge” dengan cara algoritma yang cukup pintar otomatis melakukan hal yang benar
Saya setuju bahwa pengeditan offline adalah masalah UI/UX. Penyebab yang lebih dalam adalah kebiasaan industri komputasi meniru solusi lama, dan keyakinan bahwa “karena karung 5 pon umumnya lebih mudah ditangani daripada karung 10 pon, maka barang seberat 10 pon harus dimasukkan ke dalam satu karung 5 pon”
Gambaran dasar tentang “editor teks” adalah Mosaic textarea, MacWrite, atau sesuatu di antaranya, sehingga biasanya orang mencoba menambahkan merge di atasnya dengan perubahan minimal. Misalnya lewat item menu atau beberapa opsi di dialog kecil. Bahkan jika ada dukungan merge GUI jauh di dalam menu, biasanya itu setingkat horor diff/merge untuk programmer, atau hanya tampilan berbasis coretan yang rapuh seperti mengemudikan kapal di tengah kabut
Namun dalam editor teks dengan kolaborasi offline, merge sebagian secara manual adalah inti prosesnya, dan juga harus menjadi inti desain editornya. Sayangnya, MacWrite adalah optimum lokal yang sulit ditinggalkan
Misalnya, orang yang berbicara tentang “peniruan ala cargo cult” dan “solusi lama” sering kali berikutnya berkata “jangan edit kode sebagai teks, editlah sebagai pohon sintaks”, tetapi masalahnya tetap sama. Cukup ganti “karakter” dengan “kalimat”
Jika Bob menambahkan satu baris ke cabang
elsedari pernyataanif, dan Alice menghapus seluruh pernyataan beserta cabangelse-nya, apa yang harus dilakukan sistem yang pintar?Secara keseluruhan, sepertinya saya setuju bahwa pendekatan ini benar
Saya terbuka untuk pertanyaan atau masukan. Saya akan rapat selama satu-dua jam, tetapi saya suka membicarakan hal seperti ini. Kirim saja lewat sini atau email, mana yang nyaman: alex@moment.dev
Git tidak otomatis mencampurkan perubahan lokal tanpa persetujuan eksplisit. bzr juga mungkin tidak pernah bermimpi melakukan hal seperti itu. Namun hal-hal seperti Google Docs dengan senang hati melakukannya
Kemajuan sejauh ini keren, dan semoga program akses awalnya juga berjalan baik
Saya mengimplementasikan differential sync(https://neil.fraser.name/writing/sync/). Alasannya, saya tidak memahami yang lain, dan untuk aplikasi grugnotes.com ini tampak paling sederhana
Aplikasinya cukup kasar dan tidak sepenuhnya real-time, tetapi merge pada contoh ditangani dengan benar siapa pun yang lebih dulu kembali online. Jika penghapusan lebih dulu online, versi
colourdibuang dan bahkan tidak disimpan dalam riwayat editPasti ada lebih banyak masalah, dan saya juga belum tahu bagaimana jika penggunanya lebih dari dua orang, tetapi untuk kebutuhan saya ini memuaskan