- Memperkenalkan pendekatan baru untuk menyelesaikan masalah penyuntingan teks kolaboratif, yang dapat diwujudkan tanpa algoritme rumit
- Menghindari kompleksitas dan keterbatasan pendekatan CRDT dan OT yang ada, dengan menggunakan metode penyisipan sederhana berbasis ID
- Pendekatan ini sangat fleksibel karena server memproses dengan menerima instruksi langsung tentang 'apa yang akan disisipkan dan di mana'
- Untuk pembaruan lokal optimistis, masalah sinkronisasi status diselesaikan dengan memanfaatkan strategi server reconciliation
- Dengan skalabilitas dan kemudahan dipahami, pendekatan ini menawarkan alternatif yang bisa langsung diimplementasikan untuk pengembangan aplikasi kolaboratif yang ada
Collaborative Text Editing without CRDTs or OT
Mengangkat masalah
- Penyuntingan teks kolaboratif adalah fitur yang sangat sulit, terutama saat penyuntingan simultan terjadi masalah indeks teks yang menjadi kacau (index rebasing)
- Pendekatan yang sudah ada, yaitu CRDT (Conflict-free Replicated Data Type) dan OT (Operational Transformation), masing-masing didasarkan pada model matematis yang kompleks
- CRDT: melacak setiap karakter dengan ID dan mengurutkannya berbasis pohon
- OT: menyesuaikan indeks secara dinamis untuk mencerminkan input dari pengguna lain
- Kedua pendekatan ini sama-sama sangat bergantung pada library dan sulit dikustomisasi sesuai kebutuhan pengembang
Pendekatan baru
Ide inti
- Setiap karakter diberi ID unik (UUID), dan klien mengirim perintah ke server: “sisipkan karakter apa setelah ID yang mana”
- Contoh: "insert ' the' after
f1bdb70a" → f1bdb70a adalah ID karakter target penyisipan
- Server menafsirkan dan menyisipkannya apa adanya, sehingga konflik dapat dihindari
Penanganan penghapusan
- Saat menghapus karakter, ID terkait tetap disimpan dalam daftar internal dan ditangani dengan flag isDeleted
- Tidak terlihat dalam teks yang dilihat pengguna, tetapi referensinya tetap dipertahankan sehingga operasi lanjutan tetap memungkinkan
Pemrosesan klien dan pembaruan optimistis
- Pengguna harus bisa melihat hasil segera setelah mengetik, jadi perubahan diterapkan secara lokal sebelum respons server datang (optimistic update)
- Dengan menggunakan strategi server reconciliation:
- Semua operasi lokal yang belum dikonfirmasi dibatalkan dulu
- Operasi dari server diterapkan
- Lalu operasi lokal diterapkan ulang untuk memastikan status akhir yang tersinkronisasi
Perbedaan dari pendekatan lama
- CRDT menyertakan algoritme pengurutan ID otomatis, sedangkan pendekatan ini hanya mengirim posisi penyisipan yang eksplisit ke server
- Hasilnya, pendekatan ini lebih sederhana dan memberikan perilaku yang lebih jelas
Penanganan penyisipan simultan
- Contoh: pada “My name is”, dua pengguna secara bersamaan menyisipkan “ Charlie” dan “ Dave” di posisi yang sama
- Bergantung pada urutan diterimanya di server, hasilnya menjadi “My name is Dave Charlie”
- Ini dianggap perilaku yang alami, dan tidak ada fenomena interleaving di level karakter seperti pada beberapa pendekatan CRDT
Dukungan operasi yang fleksibel
- Selain insert/delete dasar, berbagai operasi lain juga bisa didukung:
- insert-before
- penyisipan bersyarat (menambahkan “u” hanya jika “color” ada)
- penyesuaian posisi saat drag & drop, dan sebagainya
- Fleksibilitas ini berarti pendekatan tersebut tidak terikat pada sifat matematis yang sudah ditentukan
Dukungan rich text
- Pemformatan dapat diterapkan dengan mendefinisikan rentang berbasis ID (misalnya “bold dari ID X sampai ID Y”)
- Saat diintegrasikan dengan editor seperti ProseMirror, konflik bisa diselesaikan dengan cara yang sederhana
- Fitur rich text dapat ditambahkan tanpa mengubah struktur dasar
Versi terdesentralisasi (Decentralized)
- Bahkan tanpa server pusat, jika urutan operasi ditentukan dengan timestamp Lamport, pendekatan yang sama tetap bisa bekerja
- Dalam kasus ini, hasilnya serupa dengan CRDT seperti RGA, Peritext, Fugue
- Bahkan tanpa pohon atau pembuktian matematis, konsistensi setara tingkat CRDT dapat dicapai
Library pendukung: Articulated
- Library untuk menangani bentuk
Array<{ id, isDeleted }> secara efisien
- Menggunakan struktur
{ bunchId, counter } alih-alih UUID untuk optimasi memori
- Struktur berbasis B+Tree mendukung pencarian ID dan penyisipan yang cepat
- Sebagai struktur data persistent, ini cocok dipadukan dengan server reconciliation
Kesimpulan
- Pendekatan ini lebih mudah dipahami dan bisa diimplementasikan langsung dibanding CRDT/OT
- Karena berbagai fitur penyuntingan, izin, batasan, dan pemformatan bisa diterapkan dengan leluasa, pendekatan ini lebih menguntungkan untuk membangun editor kolaboratif yang realistis
- Library Articulated disediakan sebagai alat yang membantu mempraktikkan pendekatan ini
1 komentar
Komentar Hacker News
Algoritme ini tampak cukup keren. Dijelaskan pendekatan yang memberi setiap karakter ID unik global (misalnya UUID) sehingga selalu bisa dirujuk secara konsisten, klien memberi tahu server untuk menyisipkan karakter setelah ID tertentu, lalu server memproses penyisipan di posisi tersebut, penghapusan hanya disembunyikan dari tampilan tetapi secara internal tetap dipertahankan untuk keperluan referensi posisi, dan dibayangkan pendekatan ini bisa diterapkan bukan hanya untuk penyuntingan teks tetapi juga bidang lain seperti sinkronisasi dunia game.
Dibagikan pandangan bahwa perbedaannya dari CRDT bisa dilihat pada fakta bahwa server terpusat berperan untuk sinkronisasi seperti pengurutan, sehingga struktur data aktual tidak perlu diberi urutan yang sudah ditentukan sebelumnya. Karena komunikasi hanya terjadi antara klien dan server, server bisa memproses semua operasi lokal klien terlebih dahulu lalu mengirim pembaruan jarak jauh.
Ada pendapat bahwa mengejutkan tidak ada pembahasan tentang struktur data lain seperti dict/map atau array dengan tipe arbitrer. Dalam praktiknya, aplikasi sering lebih membutuhkan beragam struktur data kolaboratif daripada sekadar penyuntingan teks kolaboratif murni. Ada contoh menarik seperti validasi data, partial loading, dan operasi level lebih tinggi, tetapi dianggap alasan fitur seperti itu tidak ada di Yjs dan sejenisnya bukan karena CRDT itu sendiri, melainkan karena fitur-fitur tersebut memang sejak awal sulit diimplementasikan.
Sangat setuju dengan pembahasan tentang berbagai struktur data. Saat membuat array objek yang “atomik”, jika properti objek tidak bisa diubah maka kita tinggal mengganti tipenya alih-alih string, dan perubahan di dalam objek hanya sedikit lebih rumit karena masalah penelusuran/penyimpanan pohon. Disebut juga harapan agar di sisi pengguna library helper bisa dipasang logika 'model semantik' mereka sendiri seperti hook untuk mencegah state yang salah (misalnya satu todo memiliki isDone: true sekaligus state: inProgress), dalam konteks yang mirip dengan pemformatan rich text yang disebut di tulisan tertaut.
CRDT menggabungkan konflik dengan memilih salah satu sisi secara konsisten, tetapi masalahnya hasilnya bisa berupa kehilangan data atau data yang tidak valid. Ibarat konflik git merge selalu diselesaikan dengan memilih satu sisi saja, dalam banyak kasus hasilnya akan salah atau menyebabkan error kompilasi. Ditunjukkan bahwa penyelesaian otomatis saja mungkin tidak cukup menjaga keaslian dan makna data, dan itu dianggap sebagai alasan CRDT belum bisa digunakan secara luas.
Ada yang mengatakan senang membaca tulisan penjelasan tentang pendekatan seperti ini, dan bahwa ia sendiri sudah lama memakai cara serupa, serta merasa aneh hal ini hampir tidak dibahas di dunia akademik. Ia mengatakan dirinya bisa mengimplementasikan ini sebagai CRDT dalam lingkungan terdesentralisasi sambil tetap mempertahankan sifat seperti joinability, immutability, dan commutativity.
Upaya merangkum pesan utama artikel: apakah CRDT/OT yang rumit benar-benar hanya diperlukan saat tidak ada server terpusat?
Ada pendapat bahwa bahkan tanpa server terpusat pun, jika dalam pendekatan terdistribusi ada cara untuk menyepakati dan menerapkan urutan total operasi, kompleksitas CRDT/OT bisa dihindari. Dibagikan artikel tertaut, dan tentu ini juga merupakan salah satu bentuk CRDT (dalam bentuk yang lebih umum), tetapi ditekankan bahwa implementasi undo/replay tidak mudah, dan ini layak dipertimbangkan sebagai alternatif ketika struktur CRDT/OT tradisional terasa lebih rumit.
Disebutkan bahwa OT (Operational Transformation) membutuhkan server terpusat.
Pada dasarnya ini juga termasuk CRDT, hanya saja server terpusat yang menentukan urutan operasi yang diterapkan ke dokumen. Google Docs dan Zoho Writer juga memakai pendekatan OT + server terpusat. Diakui bahwa pendekatan yang diajukan bergaya CRDT, tetapi pada praktiknya lebih masuk akal untuk layanan yang memang berbasis server terpusat.
Ada pendapat bahwa perbedaan utamanya dengan CRDT seperti Automerge ada pada cara koordinasi server. Automerge mengurutkan penyisipan serentak dengan urutan yang ditentukan oleh nomor sekuens dan ID agen, sedangkan pendekatan ini memproses sesuai urutan kedatangan di server. Dikutip penjelasan dari artikel yang dirujuk: “tidak perlu berbagai algoritme fancy, jadi lebih sederhana”. Banyak layanan memang pada akhirnya memakai server terpusat, jadi pendekatan ini tampak praktis, tetapi karena koordinasi server mengharuskan pembatalan/pemutaran ulang edit lokal, sulit yakin seberapa jauh ini benar-benar lebih sederhana.
Ada komentar bahwa “rewind/replay” juga terasa sebagai pendekatan yang fancy, dan Persistent B+Tree juga tidak sesederhana itu.
Dijelaskan bahwa Automerge pada akhirnya juga bisa membentuk urutan total secara internal, tetapi dalam praktiknya tetap menangani operasi teks dengan cara CRDT tradisional (seperti RGA), karena undo/replay memang tidak mudah.
Ini terasa seperti CRDT yang belum dioptimalkan, seperti bercanda saja memakai set dengan max set size=1.
Jika memakai server reconciliation, ada risiko masalah merge di sisi klien menjadi sulit. Ditanyakan bagaimana UX editor bisa tetap mulus ketika pembaruan server datang secara berurutan; misalnya apakah permintaan penyisipan akan dicoba ulang jika gagal, dan apa yang harus dilakukan jika di sela-selanya datang pembaruan lain. Solusi yang diajukan misalnya memundurkan riwayat edit lalu menerapkannya ulang, atau menunggu sambil mengosongkan antrean. Dari sudut pandang frontend, tampaknya ada cukup banyak edge case UI/UX yang tidak dijelaskan, dan karena alasan seperti ini CRDT justru bisa lebih sederhana. Terutama muncul rasa penasaran seperti apa pengalaman pengguna dalam kondisi koneksi jaringan tidak stabil, misalnya di kereta bawah tanah.
Ada usulan agar seseorang mencoba memanfaatkan LLM (misalnya model 4b, dll.) untuk menyelesaikan konflik merge di luar kasus sederhana tanpa memakai CRDT atau OT yang rumit. Efisiensi energinya mungkin buruk, tetapi bisa saja ternyata bekerja cukup baik.