Resolusi konflik otomatis dalam lingkungan dengan lebih dari satu simpul utama (dalam artikel ini, simpul utama mengacu pada simpul yang menerima permintaan perubahan data) adalah bidang penelitian yang sangat menarik. Ada beberapa pendekatan dan algoritma yang berbeda, tergantung pada aplikasinya, dan artikel ini akan membahas teknologi Transformasi Operasional (OT) untuk menyelesaikan konflik dalam aplikasi pengeditan kolaboratif seperti Google Docs dan Etherpad.

1. Pendahuluan

Kolaborasi sulit dari sudut pandang teknis, karena beberapa orang dapat membuat perubahan berbeda pada bagian teks yang sama pada titik waktu yang hampir sama. Karena pengiriman data melalui Internet tidak instan (kecepatan transfer data dalam serat memiliki keterbatasan), setiap klien bekerja dengan versi lokal (replika) dokumen yang diedit untuk mensimulasikan respons instan, yang mungkin berbeda dari versi peserta lain. Dan tujuan utamanya adalah memastikan konsistensi antara versi lokal, atau dengan kata lain, bagaimana memastikan bahwa semua versi lokal cepat atau lambat akan menyatu ke dalam versi dokumen yang sama dan benar (kami tidak dapat meminta semua klien untuk beberapa saat waktu secara bersamaan memiliki versi yang sama, karena proses pengeditan bisa tak ada habisnya).

Versi Google Docs yang lama

Awalnya, Google Documents, seperti banyak aplikasi pengeditan dokumen kolaboratif lainnya, menggunakan perbandingan sederhana dari isi berbagai versi dokumen. Misalkan kita memiliki dua klien - Petya dan Vasya, dan status dokumen saat ini disinkronkan di antara mereka. Di versi lama Google server Google, setelah menerima pembaruan dari Petya, ia menghitung perbedaan (beda) antara versi dan miliknya dan mencoba menggabungkan kedua versi menjadi satu dengan cara terbaik. Kemudian server mengirimkan versi yang diterima ke Vasya. Jika Vasya tidak memiliki perubahan yang dikirim ke server, maka prosesnya berulang - Anda harus menggabungkan versi dari server dengan Vasina lokal dan mengirimkannya kembali ke server.

Sangat sering, pendekatan ini tidak bekerja dengan baik. Sebagai contoh, misalkan Petya, Vasya dan server mulai dengan dokumen yang disinkronkan dengan teks " The quick brown fox ".


Petya menyoroti kata rubah cokelat dengan huruf tebal, sementara Vasya mengganti kata rubah dengan anjing . Biarkan Petina ganti dulu ke server dan dia mengirimkan versi Vasya yang diperbarui. Jelas bahwa hasil akhirnya adalah anjing cokelat cepat , tetapi tidak ada informasi yang cukup untuk algoritma penggabungan untuk memahami hal ini, opsi Anjing coklat rubah cepat , Anjing coklat cepat , Anjing coklat rubah cepat benar-benar benar. (Misalnya, dalam git dalam kasus seperti itu, Anda akan mendapatkan konflik gabungan dan Anda harus memerintah dengan tangan Anda). Ini adalah masalah utama dari pendekatan ini - Anda tidak akan dapat memastikan hasil merger jika Anda hanya mengandalkan konten dokumen.

Anda dapat mencoba memperbaiki situasi dan memblokir kemampuan peserta lain untuk mengedit bagian teks yang sudah dikuasai seseorang. Tapi ini bukan yang kita inginkan - pendekatan ini hanya berusaha menghindari penyelesaian masalah teknis dengan memperburuk pengalaman pengguna, dan mungkin juga ada situasi di mana dua peserta mulai mengedit kalimat yang sama pada saat yang sama - dan kemudian salah satu dari mereka akan kehilangan perubahan atau dia harus secara manual menggabungkan perubahan jika terjadi konflik di atas.

Versi baru Google Documents

Dalam versi baru Google Documents, pendekatan yang sama sekali berbeda digunakan: dokumen disimpan sebagai urutan perubahan dan alih-alih membandingkan konten, kami menggulung perubahan secara berurutan (selanjutnya disebut sebagai relasi urutan ). Mengetahui cara pengguna memodifikasi dokumen dan mempertimbangkan niatnya, kami dapat menentukan versi final dengan benar setelah menggabungkan semua suntingan.

Oke, sekarang kita perlu memahami kapan harus menerapkan perubahan - kita perlu protokol kolaborasi .

Di Google Documents, semua pengeditan dokumen direduksi menjadi tiga operasi berbeda:

• Penyisipan teks
• Hapus teks
• Menerapkan gaya ke teks

Dengan demikian, ketika Anda mengedit dokumen, semua tindakan Anda disimpan persis di set operasi ini, dan mereka ditambahkan ke akhir log perubahan. Ketika dokumen ditampilkan, log perubahan akan dieksekusi menggunakan operasi yang direkam.

Sebuah komentar kecil: produk Google pertama (publik) dengan dukungan OT, tampaknya, Google Wave. Dia mendukung berbagai operasi yang jauh lebih luas.

Contoh

Biarkan Petya dan Vasya memulai dari “HABR 2017” yang sama.
Petya mengubah 2017 hingga 2018, ini sebenarnya menciptakan 2 operasi:


Pada saat yang sama, Vasya mengubah teks menjadi "HELLO HABR 2017":


Vasya menerima operasi Petin untuk dihapus, jika ia hanya menerapkannya, maka teks yang salah akan diperoleh (angka 7 seharusnya telah dihapus):


Untuk menghindari hal ini, Vasya harus mengubah operasi Petin sesuai dengan perubahan lokalnya saat ini (dengan kata lain, operasi ini peka terhadap konteks):

$$

$$\ {Delete \ \ @ 8 \} \ rightarrow \ {Delete \ \ @ 15 \}$$

Berbicara sedikit lebih formal, pertimbangkan contoh ini:


Lalu:

$$

$$O1 ’(O2 (X)) = O2’ (O1 (X))$$

Voila! Algoritma yang dijelaskan ini disebut Transformasi Operasional.

2. Transformasi Operasional

Model Konsistensi

Untuk memastikan konsistensi, beberapa model konsistensi telah dikembangkan, pertimbangkan salah satunya - CCI.

Model CCI menyediakan tiga properti:

1. Konvergensi: Semua replika dokumen umum harus identik setelah semua operasi selesai:
   
   
   
   Dalam contoh ini, kedua pengguna mulai dengan replika identik. Kemudian mereka mengubah dokumen dan replika berbeda - dengan cara ini waktu respons minimum tercapai. Setelah mengirim perubahan lokal ke klien lain, properti konvergensi mensyaratkan kondisi akhir dokumen untuk semua klien menjadi identik.
2. Pelestarian niat: Maksud operasi harus disimpan pada semua replika, terlepas dari apakah tumpang tindih untuk melakukan beberapa operasi pada saat yang sama. Maksud dari suatu operasi didefinisikan sebagai efek dari pelaksanaannya pada salinan di mana ia dibuat.
   
   Pertimbangkan contoh di mana properti ini gagal:
   
   
   
   
   Kedua klien mulai dengan replika yang sama, kemudian keduanya melakukan perubahan. Untuk Petya, maksud operasinya adalah memasukkan '12' pada indeks pertama, dan untuk Vasya, hapus karakter dengan indeks 2 dan 3. Setelah sinkronisasi dengan Petya Vasino, niat dan dengan Vasya Petino niat dilanggar. Perhatikan juga bahwa replika telah menyimpang, tetapi ini bukan persyaratan untuk properti yang dimaksud. Versi final yang benar diusulkan untuk mengidentifikasi pembaca sebagai latihan kecil.
   
3. Pelestarian Kausalitas: Operasi harus dilakukan dalam urutan sebab akibat (berdasarkan hubungan yang terjadi sebelum-sebelumnya ).
   
   Pertimbangkan contoh di mana properti ini gagal:
   
   
   
   
   Seperti yang Anda lihat, Petya mengirim Vasya dan Agen Smith perubahan dokumennya, Vasya menerimanya terlebih dahulu dan menghapus karakter terakhir. Karena kelambatan jaringan, Smith menerima operasi pertama untuk Vasin untuk menghapus karakter yang belum ada.
   
   OT tidak dapat memastikan bahwa properti pelestarian kausalitas terpenuhi, oleh karena itu, algoritma seperti jam vektor digunakan untuk tujuan ini.
   

Desain PL

Salah satu strategi desain sistem PL adalah pembagian menjadi tiga bagian:

• Algoritma kontrol transformasi: menentukan kapan operasi (target) siap untuk berubah, mengenai operasi apa (referensi) transformasi yang harus dilakukan, dan dalam urutan apa untuk mengeksekusinya.
• Fungsi transformasi: Mengubah operasi target, dengan mempertimbangkan dampak operasi referensi.
• Persyaratan dan properti transformasi (properti dan kondisi): menyediakan koneksi antara komponen-komponen ini dan melakukan pemeriksaan untuk kebenaran.

Fungsi Konversi

Fungsi konversi dapat dibagi menjadi dua jenis:

• Inklusi / Penerusan Transformasi: Mengubah operasi $$$O_a$ sebelum operasi $$$O_b$ sehingga efek dari $$$O_b$ (mis. dua sisipan)
• Pengecualian / Transformasi Mundur: Transformasi suatu operasi $$$O_a$ sebelum operasi $$$O_b$ sehingga efek dari $$$O_b$ dikecualikan (mis. masukkan setelah penghapusan)

Contoh untuk operasi penyisipan / penghapusan simbolis (i - insert, d - delete):

Tii(Ins[p1, c1], Ins[p2, c2]) { if (p1 < p2) || ((p1 == p2) && (order() == -1)) // order() –   return Ins[p1, c1]; // Tii(Ins[3, 'a'], Ins[4, 'b']) = Ins[3, 'a'] else return Ins[p1 + 1, c1]; // Tii(Ins[3, 'a'], Ins[1, 'b']) = Ins[4, 'a'] } Tid(Ins[p1, c1], Del[p2]) { if (p1 <= p2) return Ins[p1, c1]; // Tid(Ins[3, 'a'], Del[4]) = Ins[3, 'a'] else return Ins[p1 – 1, c1]; // Tid(Ins[3, 'a'], Del[1]) = Ins[2, 'a'] } Tdi(Del[p1], Ins[p2, c1]) { //   ,    } Tdd(Del[p1], Del[p2]) { if (p1 < p2) return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3] else if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2] else return Id; // Id –   } 

3. Protokol interaksi di Google Documents

Mari kita lihat bagaimana protokol interaksi di Google Documents bekerja lebih detail. Misalkan kita memiliki server, Petya dan Vasya, dan mereka memiliki versi dokumen kosong yang disinkronkan.

Setiap klien mengingat informasi berikut:

• Versi (id, revisi) dari perubahan terakhir yang diterima dari server.
• Semua perubahan dilakukan secara lokal tetapi tidak dikirim ke server (pengiriman menunggu)
• Semua perubahan dilakukan secara lokal, dikirim ke server, tetapi tanpa konfirmasi dari server.
• Keadaan saat ini dari dokumen yang dilihat pengguna.

Server, pada gilirannya, mengingat:

• Daftar semua perubahan yang diterima tetapi tidak diproses (pending processing).
• Riwayat lengkap dari semua perubahan yang diproses (log revisi).
• Keadaan dokumen pada saat perubahan terakhir diproses.

Jadi, Petya mulai dengan kata "Halo" di awal dokumen:


Klien pertama-tama menambahkan perubahan ini ke daftar tunggu, dan kemudian mengirimkannya ke server dan memindahkan perubahan ke daftar yang dikirim.

Petya terus mengetik dan telah menambahkan kata "Habr". Pada saat yang sama, Vasya mengetik "!" dalam dokumennya yang kosong (dia belum menerima perubahan Petina).


Petino $$$\ {Masukkan \ \ 'Habr', \ @ 5 \}$ telah ditambahkan ke daftar yang tertunda, tetapi belum dikirim, karena kami tidak mengirim lebih dari satu perubahan pada satu waktu, dan yang sebelumnya belum dikonfirmasi . Kami juga mencatat bahwa server menyimpan perubahan Petit di log revisinya. Kemudian server mengirim mereka ke Vasya dan mengirimkan konfirmasi ke Petya (bahwa perubahan pertama Petina berhasil diproses)


Klien Vasya menerima perubahan Petina dari server dan menerapkan OT terkait pengirimannya yang tertunda ke server $$$\ {Sisipkan \ \ '!', \ @ 0 \}$ . Hasilnya adalah perubahan dalam indeks penyisipan dari 0 menjadi 5. Kami juga mencatat bahwa kedua klien memperbarui jumlah revisi terakhir yang disinkronkan dengan server menjadi 1. Akhirnya, klien Petin menghapus perubahan terkait dari daftar konfirmasi yang tertunda dari server.

Kemudian Petya dan Vasya mengirim perubahan mereka ke server.


Server menerima perubahan Petina sebelum (mengenai pesanan yang dimasukkan) Vasinykh, jadi ia pertama kali memprosesnya, dan mengirimkan konfirmasi ke Petya. Dia juga mengirim mereka ke Vasya, dan kliennya mengonversinya mengenai perubahan yang belum dikonfirmasi $$$\ {Masukkan \ \ '!', \ @ 5 \}$ .

Kemudian muncul poin penting. Server mulai memproses perubahan Vasya, yang menurut Vasya, memiliki revisi nomor 2. Tetapi server telah melakukan perubahan di nomor 2, jadi itu menerapkan konversi ke semua perubahan yang belum disadari oleh klien Vasya (dalam hal ini - $$$\ {Masukkan \ \ 'Habr', \ @ 5 \}$ ), dan menyimpan hasilnya di nomor 3.


Seperti yang bisa kita lihat, indeks perubahan Vasin meningkat sebesar 5 untuk mengakomodasi teks Petin.

Proses ini selesai untuk Petya, dan Vasya perlu menerima perubahan baru dari server dan mengirim konfirmasi.

4. Etherpad

Mari kita lihat aplikasi lain yang serupa di mana OT digunakan - proyek open source dari editor online dengan co-editing etherpad.org

Di Etherpad, fungsi konversi sedikit berbeda - perubahan dikirim ke server sebagai satu set perubahan (changeset) , didefinisikan sebagai

$$

$$(\ ell_1 \ rightarrow \ ell_2) [c_1, c_2, c_3, ...],$$

dimana

• $$$\ ell_1$ : panjang dokumen sebelum diedit.
• $$$\ ell_2$ : panjang dokumen setelah diedit.
• $$$c_1, c_2, c_3, ...$ - deskripsi dokumen setelah diedit. Jika $$$c_i$ Adalah angka (atau rentang angka), maka ini adalah indeks karakter dokumen asli yang akan tetap setelah diedit (dipertahankan), dan jika $$$c_i$ - karakter (atau string), maka ini adalah penyisipan.
  
  Contoh:
  
  
  1. $$$ inline $ `` "+ \ (0 \ rightarrow 6) [` `Hello”] = `` Hello "$ inline $
  2. $$$ inline $ `` Beaver ”+ (4 \ rightarrow 4) [` `Ha”, \ 2-3] = `` Habr '$ inline $
  
  

Seperti yang sudah Anda pahami, dokumen akhir dibentuk sebagai urutan perubahan yang diterapkan untuk dokumen kosong.

Perhatikan bahwa kami tidak dapat hanya menerapkan perubahan dari peserta lain (ini, pada prinsipnya, dimungkinkan di Google Documents), karena panjang total dokumen dapat berbeda.
Misalnya, jika dokumen sumber berukuran panjang n, dan kami memiliki dua perubahan:

$$

$$A = (n \ rightarrow n_a) [\ cdots] \\ B = (n \ rightarrow n_b) [\ cdots],$$

lalu $$$A (B)$ tidak mungkin, karena $$$A$ membutuhkan panjang dokumen $$$n$ dan sesudahnya $$$B$ dia akan panjang $$$n_b$ .
Untuk mengatasi situasi ini, Etherpad menggunakan mekanisme penggabungan : ini adalah fungsi yang dilambangkan dengan $$$m (A, B)$ , menerima dua perubahan pada input pada status dokumen yang sama (selanjutnya disebut $$$X$ ) dan membuat perubahan baru.

Diperlukan itu

$$

$$m (A, B) = m (B, A)$$

Perhatikan bahwa untuk pelanggan dengan perubahan $$$A$ yang menerima kembaliannya $$$B$ tidak masuk akal untuk menghitung $$$m (A, B)$ sejak itu $$$m (A, B)$ berlaku untuk $$$X$ , dan $$$A$ keadaan saat ini $$$A (X)$ . Padahal, kita perlu menghitung $$$A '$ dan $$$B $$ sedemikian rupa

$$

$$B ’(A (X)) = A’ (B (X)) = m (A, B) (X)$$

Menghitung fungsi $$$A '$ dan $$$B $$ disebut follow dan didefinisikan sebagai berikut:
$$$f (A, B) (A) = f (B, A) (B) = m (A, B) = m (B, A)$
Algoritma konstruksi $$$f (A, B)$ berikut ini:

• Sisipan dalam A menjadi indeks di $$$f (A, B)$
• Sisipan dalam B menjadi sisipan di $$$f (A, B)$
• Indeks yang cocok dalam A dan B dibawa ke $$$f (A, B)$

Contoh:

$$$$ menampilkan $$ X = (0 \ rightarrow 8) [`` baseball ”] \\ A = (8 \ rightarrow 5) [0 - 1,` `si”, 7] \ / \! \! / == `` basil ”\\ B = (8 \ rightarrow 5) [0,` `e", 6, `` ow "] \ / \! \! / ==` `di bawah" $$ menampilkan $$ $$

Kami menghitung:

$$

$$A '= f (B, A) = (5 \ rightarrow 6) [0, 1, `` si ", 3, 4] \\ B' = f (A, B) = (5 \ rightarrow 6) [ 0, “e”, 2, 3, `` ow "] \\ m (A, B) = m (B, A) = A (B ') = B (A') = (8 \ rightarrow 6) [ 0, `` esiow "] \\ $$

Hitung $$$m (A, B) (X)$ ditawarkan sebagai latihan.

Protokol interaksi pada dasarnya sama dengan Google Documents, kecuali jika perhitungannya sedikit lebih rumit.

5. Kritik terhadap PL

• Menerapkan OT adalah tugas yang sangat sulit dalam hal pemrograman. Mengutip dari Wikipedia : Joseph Gentle, pengembang perpustakaan Share.JS dan mantan insinyur Google Wave berkata, “Sayangnya, mengimplementasikan OT menyebalkan. Ada sejuta algoritma dengan pengorbanan yang berbeda, sebagian besar terperangkap dalam makalah akademis. Algoritma sangat sulit dan memakan waktu untuk diimplementasikan dengan benar. [...] Wave membutuhkan waktu 2 tahun untuk menulis dan jika kita menulis ulang hari ini, dibutuhkan waktu yang hampir lama untuk menulis kedua kalinya. "
  
  (Sayangnya, menulis PL sangat sulit. Ada sejuta algoritma dengan pro dan kontra mereka, tetapi kebanyakan dari mereka hanya studi akademis. Algoritma ini sebenarnya sangat kompleks dan membutuhkan banyak waktu untuk implementasi yang benar. [...] Kami menghabiskan 2 tahun untuk menulis Wave, dan jika kita harus menulisnya lagi hari ini, kita akan membutuhkan waktu yang sama)
  
• Anda harus benar-benar menyimpan setiap perubahan pada dokumen
  

6. Referensi

• Kontrol Concurrency dalam Sistem Groupware
• Apa yang berbeda dari Google Documents yang baru: Bekerja bersama, bahkan terpisah
• Apa yang berbeda dari Google Documents yang baru: Resolusi konflik
• Memahami dan Menerapkan Transformasi Operasional
• Wikipedia: Transformasi operasional
• Jendela latensi tinggi, bandwidth rendah dalam sistem kolaborasi Jupiter
• Apa yang berbeda tentang Google Documents baru: Membuat kolaborasi cepat
• Transformasi Operasional dalam Editor Grup Real-Time: Masalah, Algoritma, dan Prestasi
• Manual Teknis Etherpad dan EasySync
• Google TechTalks: Masalah dan Pengalaman dalam Merancang Sistem Pengeditan Kolaboratif Real-time
• Transformasi Operasional Pertanyaan dan Jawaban yang Sering Diajukan