Tapi mari kita mulai lagi.
Pada tahun 2010, saya bekerja di Google Wave, di mana kami mencoba membuat ruang kolaboratif yang dapat diedit untuk menggantikan email, Google Docks, forum, perpesanan instan, dan banyak aplikasi tugas tunggal lainnya. Di antara alat saya, saya terutama menyukai lingkungan tujuan umum, tidak di tempat lain seperti di Wave, fungsinya tidak dirumuskan pada saat itu. Tidak seperti kebanyakan alat lainnya, lingkungan serba guna tidak memaksakan alur kerjanya sendiri, sehingga Anda dapat menggunakannya untuk merencanakan liburan, membuat wiki, bermain permainan papan dengan teman, menjadwalkan rapat kerja, dan banyak lagi.
Secara internal, pengeditan bersama Wave bekerja di atas Transformasi Operasional (OT), dan digunakan selama berhari-hari pada saat itu: algoritme kami didasarkan pada pembicaraan Jupiter tahun 1995. Untuk setiap dokumen, algoritme menyimpan daftar kronologis terpisah dari perubahan, "Ketik H di posisi 0", "Ketik i di posisi 1", dan seterusnya. Dalam kebanyakan kasus, pengguna mengubah versi terbaru dokumen, dan log tampak seperti urutan perubahan, namun, saat penulisan bersama, kami dihadapkan pada pengeditan bersamaan.
Dalam hal ini, pengeditan pertama yang masuk ke server dicatat seperti biasa, dan selanjutnya, jika ternyata sudah usang, dibandingkan dengan log peristiwa untuk menentukan tujuan awal pengguna. (Lebih sering daripada tidak, semuanya bermuara pada memperbarui posisi karakter.) Kemudian algoritme, yang seharusnya "ini adalah hasil yang diinginkan pengguna", menambahkan operasi baru, seperti git-rebase secara real time.
Dengan penutupan Google Wave, saya memindahkan model OT ke ShareJS . Pada saat itu, node terasa baru dan aneh, dan jika saya ingat dengan benar, saya memulai ShareJS bahkan sebelum npm dirilis. Seorang editor bersama sederhana hanya membutuhkan seribu baris kode, dan dalam demo saya mengedit bersama dokumen di browser dan dalam aplikasi.
Pada intinya, OT adalah loop for () yang dihiasidengan beberapa fungsi bantuan untuk memperbarui offset karakter. Dalam praktiknya, PL itu sederhana, mudah dipahami, cepat dioperasikan, dan berfungsi dengan baik. (10-100 ribu operasi per detik dalam javascript yang tidak dioptimalkan, 1-20 juta dalam C yang dioptimalkan ). Log peristiwa dapat menggunakan lebih banyak memori daripada biasanya, tetapi Anda dapat menguranginya jika diinginkan, meskipun Anda tidak dapat menggabungkan pengeditan yang terutama yang lama. Operasi penetapan secara global akan membutuhkan server terpusat, tetapi sebagian besar sistem sudah memiliki server atau database seperti itu, bukan?
Server terpusat
Masalah OT yang signifikan adalah ketergantungannya pada server terpusat. Pernahkah Anda bertanya-tanya mengapa, ketika mengizinkan akses ke dokumen Google Docs melalui jejaring sosial, Anda dihadapkan pada pesan aneh seperti "Dokumen ini kelebihan beban dan pengeditannya dinonaktifkan"? Alasannya (menurut saya) adalah sebagai berikut: ketika Anda membuka dokumen, satu server tertentu dipilih untuk memproses semua pengeditannya, dan ketika sekumpulan pengguna menerkam dokumen, sistem harus berusaha keras untuk tidak membebani server.
Ada beberapa cara untuk mengatasi masalah ini: selain sub dokumen sharding (seperti di Google Docks), Anda dapat melakukan pengeditan melalui retry loop dengan melewati transaksi database, sehingga masalah serialisasi dipikul oleh database yang sama ( begitulah Firepad bekerjadan ShareDB ).
Namun, OT tidaklah sempurna. Kami ingin mengganti email dengan Wave, tetapi email mendukung penggabungan, satu rangkaian surat dapat tersebar di banyak perusahaan, dan entah bagaimana semuanya berhasil dengan sukses. Selain itu, tidak seperti pesan Facebook, email dapat dikirim ke perusahaan yang disebutkan di kolom "salin". Jika kita ingin Wave mengganti surat, itu juga akan membutuhkan fungsionalitas pengiriman pesan tanpa akses ke jaringan eksternal, misalnya, ketika saya mengirim surat ke kolega saya di tabel berikutnya. Tapi bagaimana Anda bisa menerapkan semua ini di atas OT? Kami entah bagaimana berhasil menyiapkan proses seperti itu, tetapi ternyata terlalu rumit dan penuh kesalahan: kami membuat diagram, di mana setiap protokol gelombang mengatur pohon server gelombang untuk mentransfer operasi di kedua arah, tetapi tidak pernah bekerja sepenuhnya. Kurang dari sepuluh tahun yang lalu, di Wave Protocol Summit, saya memberikan presentasi tentang cara membuat dan mengkonfigurasi jaringan semacam itu, tetapi terlepas dari semua persiapan saya dan semua pemeriksaan awal, kepatuhan ketat pada setiap langkah pada presentasi itu sendiri gagal, dan jaringan tidak pernah berfungsi. Saya masih tidak tahu mengapa ini terjadi, tetapi apa pun bugnya, hampir tidak pernah diperbaiki dalam versi publik, semuanya terlalu sulit.
Lepas landas CRTD
Seperti yang telah saya sebutkan, algoritma Wave utama dibuat cukup lama, pada tahun 1995, dan saya bahkan tidak ingat memiliki Internet di rumah pada saat itu. Sejak itu, para peneliti telah bekerja tanpa lelah untuk meningkatkan kinerja OT, dan ke arah yang paling menjanjikan mereka menggunakan CRTD (tipe data yang Direplikasi Bebas Konflik). Pendekatan ini agak berbeda dari biasanya dan memungkinkan Anda untuk mengedit file secara real time tanpa memerlukan server pusat. Presentasi Martin menggambarkan pekerjaan mereka lebih baik daripada yang bisa saya gambarkan, jadi saya akan melewatkan detailnya.
Orang-orang telah menanyakan pendapat saya tentang CRTD selama bertahun-tahun, dan jawaban saya selalu terdengar seperti ini:
Mereka rapi dan saya senang orang-orang mengerjakannya, namun:
- . . , 100 Delta-CRTD . (: B4.)
- - CRTD , , 100 automerge master 83 . , , , , . ( automerge 1.1 .)
- Selama bertahun-tahun, fungsionalitas yang ada di OT tidak ada di CRDT, misalnya, belum ada yang membuat CRDT dengan dukungan untuk / object move / (mentransfer sesuatu dari satu bagian pohon JSON ke yang lain). Prosedur seperti itu diperlukan untuk aplikasi seperti Workflowy, dan OT bekerja dengan baik .
- CRDT sangat kompleks dan sulit untuk dipikirkan.
- Kemungkinan besar Anda sudah memiliki server / database terpusat.
Untuk semua kritik saya, saya mengabaikan CRDT, tetapi dengan melakukan itu mengabaikan literatur yang relevan, dan yang mengejutkan saya, saya merindukan peningkatan CRDT yang diam-diam dan tidak terlihat. Dalam presentasinya (yang lebih dari menarik perhatian Anda) Martin membahas poin-poin utama:
- : CRDT (Automerge / RGA Y.js / YATA) [log(n)] . ( .)
- : - , 54- . automerge , Y.js, Y.js 100 160 3 . .
- : , .
- : , CRDT OT. , automerge .
Alasan kecepatan tidak meyakinkan saya, jadi untuk menguji idenya, saya secara independen mengimplementasikan dan menguji CRDT di Rust melalui B-tree menggunakan ide dari automerge. Itu tidak memiliki fungsionalitas (menghapus karakter, konflik), tetapi mampu menangani 6 juta pengeditan per detik . (Setiap iterasi melakukan 2000 pengeditan ke dokumen kosong oleh dua pengguna bergantian, yang membutuhkan total 330 mikrodetik, atau 6,06 juta pengeditan per detik.) Jadi CRDT benar-benar meningkat dan perbedaan kecepatan antara mereka dan OT sekarang bahkan lebih kecil daripada antara Rust dan Javascript.
Semua perbaikan ini telah lama berada di bagian "segera hadir" dari cabang kinerja automerge, tetapi bagaimanapun juga, automerge bukanlah satu-satunya CRDT. Y.js membuktikan dirinya layak dan dengan mudah melewati versi automerge saat ini dalam pengujiannya . Ini tidak memiliki fungsionalitas yang saya minati, tetapi secara umum tentu lebih mudah untuk memperbaiki implementasi yang ada daripada membuat algoritma baru.
Menciptakan masa depan
Saya sangat prihatin tentang membuat kemajuan. Apa yang aneh jika tidak digunakan dalam seratus tahun? Tentunya, kami akan memiliki pengeditan waktu nyata, tetapi saya tidak lagi yakin tentang penerapannya melalui OT dan semua pekerjaan yang telah saya lakukan dalam hal ini, yang tidak bisa tidak membuat saya sedih.
JSON dan REST ada di mana-mana saat ini. Katakanlah dalam 15 tahun, pengeditan bersama secara real-time akan ada di mana-mana. Apa yang akan menjadi mitra JSON dalam hal penulisan bersama untuk memudahkan transfer ke proyek Anda? Di masa depan yang gemilang ini, kami memerlukan implementasi CRDT berkualitas tinggi, karena untuk beberapa aplikasi OT tidak akan berfungsi, membuat versi GIt real-time atau variasi sederhana dari Google Wave tidak akan berfungsi lagi. Namun jika kita sudah memiliki implementasi CRDT yang baik, apakah kita juga membutuhkan implementasi OT? Saya kira tidak, karena mentransfer semua fungsi dari OT ke CRDT tidak akan sulit (termasuk, omong-omong, operasi pemangkasan), sedangkan sebaliknya tidak benar. Orang pintar tidak setuju dengan saya, tetapi menurut saya, mengingat kami memiliki CRDT yang bagus dan cepat untuk setiap bahasa,kebutuhan akan OT akan hilang sama sekali.
Salah satu keuntungan OT adalah dapat dengan mudah diimplementasikan dalam sistem terpusat - seperti kebanyakan aplikasi modern - tetapi algoritme terdistribusi juga diterapkan dengan baik. (Lihat Github misalnya.) Menurut pendapat saya, CRDT berkualitas tinggi pada wasm lebih cepat daripada implementasi OT di JS. Dan jika Anda hanya peduli tentang sistem terpusat, ingat: Pembatasan OT menyebabkan Google mengalami masalah penskalaan di Google Docs.
Jadi menurut saya sekarang adalah waktunya untuk beralih ke CRDT yang kecil dan cepat. Sebagian besar, pekerjaan akademis telah selesai, masalahnya tetap untuk implementasi yang sukses.
Apa berikutnya
Saya semakin kurang peduli dengan dunia aplikasi terpusat. Aplikasi berinteraksi dengan data saya, di perangkat saya, dan ini akan menjadi waktu yang tepat bagi aplikasi ini untuk bereaksi sesuai dengan koneksi tersebut. Saya ingin laptop dan ponsel saya dapat saling mentransfer data melalui wifi, dan bukan dengan mengunggah data saya ke server di negara lain. Terutama jika server ini didanai oleh raksasa iklan yang bersaing untuk mendapatkan perhatian saya .
Secara filosofis, ketika saya mengedit dokumen di Google Docs, komputer saya meminta izin Google untuk mengedit file (karena jika karena alasan tertentu server mengatakan tidak, saya kehilangan semua editan saya). Sebagai perbandingan, saat
git pushdi github, saya baru saja memberitahugithub tentang pengeditan di kode saya. Repositori saya masih milik saya, seperti halnya setiap bit data dan perangkat keras yang ada, dan begitulah seharusnya aplikasi saya bekerja. Terima kasih kepada orang-orang seperti Martin, kami sekarang tahu bagaimana membuat CRDT yang baik. Namun, sebelum aplikasi lokal pertama diterima sebagai dasar, lebih banyak baris kode harus ditulis.
Secara keseluruhan, saatnya mengucapkan selamat tinggal pada transformasi operasional. Kami bersenang-senang bersama, dari semua yang saya tulis, kode transformasi operasional adalah salah satu yang paling sulit dan menarik. Anda pintar dan luar biasa, OT, tapi CRDT bisa melakukan sesuatu yang tidak pernah bisa Anda lakukan. Dan saya membutuhkan CRDT. Saya pikir dengan beberapa penerapan yang baik kita dapat mencapai sesuatu yang sangat istimewa.
Saya berduka atas semua pekerjaan yang saya lakukan di PL selama bertahun-tahun, tetapi PL tidak lagi sesuai dengan visi saya di masa depan. CRDT akan memungkinkan kami untuk membangun kembali Wave dengan lebih mudah dan lebih cepat serta membuat aplikasi yang memperlakukan pengguna seperti warga digital daripada petani digital. Dan ini penting.
Saatnya membuat.