Bagaimana cara menghitung klik halaman google.com? Dan bagaimana cara menyimpan counter suka pengguna yang sangat populer? Artikel ini mengusulkan untuk mempertimbangkan penyelesaian masalah ini menggunakan CRDT (Jenis Data Replika Bebas Konflik, yang dalam bahasa Rusia diterjemahkan secara kasar sebagai Jenis Data Replikasi Bebas Konflik), dan dalam kasus yang lebih umum, tugas sinkronisasi replika dalam sistem terdistribusi dengan beberapa node terkemuka.

1. Pendahuluan

Kami telah lama terbiasa menggunakan aplikasi seperti kalender atau layanan catatan seperti Evernote. Mereka disatukan oleh fakta bahwa mereka memungkinkan Anda untuk bekerja offline, dari beberapa perangkat dan ke beberapa orang secara bersamaan (pada data yang sama). Tantangan yang dihadapi pengembang dari setiap aplikasi tersebut adalah bagaimana memastikan sinkronisasi data yang paling “lancar” berubah secara bersamaan pada beberapa perangkat. Idealnya, keterlibatan pengguna tidak diperlukan sama sekali untuk menyelesaikan konflik penggabungan.

Dalam artikel sebelumnya, kami telah mempertimbangkan pendekatan untuk menyelesaikan masalah seperti itu - Transformasi Operasional, itu juga akan menjelaskan metode yang sangat mirip yang memiliki kelebihan dan kekurangan (misalnya, CRDT untuk JSON belum ditemukan. Pembaruan: Terima kasih kepada msvn untuk tautannya, di sini di sini adalah proyek dari penulis artikel penelitian tentang implementasi JSON di CRDT)

2. Konsistensi akhirnya kuat

Baru-baru ini, banyak pekerjaan telah ditulis dan banyak penelitian telah dilakukan di bidang konsistensi akhirnya. Menurut pendapat saya, sekarang ada tren kuat menuju pergeseran dari konsistensi yang kuat ke berbagai pilihan untuk konsistensi, ke penelitian yang konsistensi di mana situasi / sistem lebih menguntungkan untuk diterapkan, untuk memikirkan kembali definisi yang ada. Ini mengarah pada beberapa kebingungan, misalnya, ketika penulis beberapa karya, berbicara tentang konsistensi, berarti konsistensi akhirnya dengan beberapa properti tambahan, dan penulis lain menggunakan terminologi tertentu untuk ini.

Pertanyaan yang diajukan oleh penulis salah satu artikel tersebut mengkritik definisi saat ini tentang konsistensi akhir: menurutnya, jika sistem Anda selalu menjawab "42" untuk semua permintaan, maka semuanya baik-baik saja, pada akhirnya konsisten.

Tanpa melanggar kebenaran artikel ini, saya, mengikuti penulis artikel asli, akan menggunakan terminologi berikut (harap dicatat, ini bukan definisi yang ketat, ini perbedaan):

Konsistensi kuat (SC): semua operasi penulisan diurutkan dengan ketat, permintaan baca pada replika apa pun menghasilkan hasil yang sama, yang terakhir direkam. Konsensus waktu nyata diperlukan untuk menyelesaikan konflik (dengan konsekuensi selanjutnya), dapat tahan terhadap penurunan ke n / 2 - 1 node.
Konsistensi akhirnya (EC): perbarui data secara lokal, kirim pembaruan lebih lanjut. Membaca berbagai replika dapat mengembalikan data basi. Jika terjadi konflik, kami mundur, atau entah bagaimana memutuskan apa yang harus dilakukan. T.O. masih diperlukan konsensus, tetapi tidak lagi secara real time .
Strong akhirnya konsistensi (SEC): EC + untuk menyelesaikan konflik, replika memiliki algoritma yang telah ditentukan. T.O. konsensus tidak diperlukan , dapat menahan penurunan ke n - 1 node.

Perhatikan bahwa SEC (seolah-olah) memecahkan masalah teorema CAP: ketiga properti terpenuhi.

Jadi, kami siap menyumbangkan SC dan ingin memiliki set tipe data dasar tertentu untuk sistem terdistribusi kami yang berpotensi tidak stabil yang secara otomatis akan menyelesaikan konflik tulis untuk kami (tidak diperlukan interaksi pengguna atau permintaan ke arbiter)

3. Tugas tentang suka dan hit

Tidak diragukan lagi, ada beberapa algoritma untuk menyelesaikan masalah seperti itu. CRDT menawarkan cara yang cukup elegan dan mudah.

Hitungan jumlah Google.com:

google.com memproses sekitar 150.000 permintaan per detik dari seluruh dunia. Jelas, penghitung perlu diperbarui secara tidak sinkron. Antrian menyelesaikan sebagian masalah - misalnya, jika kami menyediakan API eksternal untuk mendapatkan nilai ini, maka kami harus melakukan replikasi agar tidak menempatkan repositori dengan permintaan baca. Dan jika sudah ada replikasi, mungkin tanpa antrian global?

Menghitung suka pengguna:

Tugasnya sangat mirip dengan yang sebelumnya, hanya sekarang Anda perlu menghitung hit unik.

4. Terminologi

Untuk pemahaman yang lebih lengkap tentang artikel ini, Anda perlu tahu tentang ketentuan berikut:

Idempotensi
Mengatakan bahwa menerapkan operasi beberapa kali tidak mengubah hasilnya.
Contoh - DAPATKAN operasi atau penambahan dengan nol: $f (x) = x + 0$
Komutatif
$f (x, y) = f (y, x)$
Pesanan sebagian
Refleksivitas + Transitivitas + Antisimetri
Setengah kisi
Set sebagian dipesan dengan wajah bagian atas (bawah) yang tepat
Vektor versi
Vektor dimensi sama dengan jumlah node, dan setiap node, ketika peristiwa tertentu terjadi, akan meningkatkan nilainya dalam vektor. Selama sinkronisasi, data ditransmisikan dengan vektor ini dan ini memperkenalkan relasi pesanan, yang memungkinkan Anda untuk menentukan replika yang memiliki data lama / baru.

5. Sinkronkan model

Berbasis negara:

Juga disebut sinkronisasi pasif, ini membentuk Tipe Data Replika Konvergen - CvRDT.
Ini digunakan dalam sistem file seperti NFS, AFS, Coda dan di KV-storages Riak, Dynamo
Dalam hal ini, negara pertukaran replika secara langsung, replika penerima menggabungkan negara yang diterima dengan keadaan saat ini.

Untuk melakukan konvergensi replika menggunakan sinkronisasi ini, perlu bahwa:

Data membentuk semilattice
Fungsi gabungan menghasilkan batas atas yang tepat
Replika membentuk grafik terhubung.

Contoh:

Dataset: bilangan asli $\ mathbb {N}$
Item minimum: $- \ infty$
$merge (x, y) = maks (x, y)$

Persyaratan tersebut memberi kita fungsi penggabungan komutatif dan idempoten yang tumbuh secara monoton pada kumpulan data yang diberikan:

Ini memastikan bahwa replika konvergen cepat atau lambat dan memungkinkan Anda untuk tidak khawatir tentang protokol transfer data - kami dapat kehilangan pesan dengan status baru, mengirimnya beberapa kali, dan bahkan mengirimkannya dalam urutan apa pun .

Berbasis operasi:

Juga disebut Sinkronisasi Aktif, ini membentuk Tipe Data Replikasi Komutatif - CmRDT.
Digunakan dalam sistem kooperatif seperti Bayou, Rover, IceCube, Telex.

Dalam hal ini, operasi pembaruan keadaan pertukaran replika. Saat memperbarui data, replika asli:

Memanggil metode generate (), yang mengembalikan metode effector () untuk mengeksekusi pada replika yang tersisa. Dengan kata lain, efektor () adalah penutupan untuk mengubah keadaan replika yang tersisa.
Menerapkan efektor ke negara bagian setempat
Mengirim efektor ke semua replika lainnya

Untuk melakukan konvergensi replika, kondisi berikut harus dipenuhi:

Protokol Pengiriman yang Andal
Jika efektor dikirimkan ke semua replika sesuai dengan urutan yang dimasukkan (untuk jenis tertentu), maka efektor simultan bersifat komutatif, atau
Jika efektor dikirimkan ke semua replika tanpa memperhitungkan pesanan, maka semua efektor bersifat komutatif.
Jika efektor dapat dikirimkan beberapa kali, maka itu harus idempoten
Beberapa implementasi menggunakan antrian (Kafka) sebagai bagian dari protokol pengiriman.

Berbasis di Delta:

Mengingat keadaan / op berbasis, mudah untuk melihat bahwa jika pembaruan hanya mengubah sebagian dari negara, maka tidak masuk akal untuk mengirim seluruh negara, dan jika sejumlah besar perubahan mempengaruhi satu negara (misalnya, penghitung), maka Anda dapat mengirim satu, perubahan teragregasi, dan tidak semua operasi perubahan.

Sinkronisasi Delta menggabungkan kedua pendekatan dan mengirimkan delta-mutator yang memperbarui status menurut tanggal sinkronisasi terakhir. Pada sinkronisasi awal, perlu untuk mengirim negara sepenuhnya, dan beberapa implementasi dalam kasus seperti itu sudah memperhitungkan keadaan replika yang tersisa ketika membangun delta-mutators.

Metode pengoptimalan berikutnya adalah mengompresi log berbasis op, jika penundaan diizinkan.

Berbasis operasi murni:

Ada keterlambatan dalam membuat opector dalam sinkronisasi berbasis op. Dalam beberapa sistem ini mungkin tidak dapat diterima, maka Anda harus mengirimkan perubahan asli dengan biaya mempersulit protokol dan jumlah tambahan metadata.

Pendekatan penggunaan standar:

Jika pembaruan akan segera dikirim dalam sistem, maka berbasis negara akan menjadi pilihan yang buruk, karena mengirimkan seluruh negara lebih mahal daripada hanya operasi pembaruan. Berbasis Delta bekerja lebih baik, tetapi dalam kasus khusus ini, perbedaan dengan berbasis negara akan kecil.
Jika Anda perlu menyinkronkan replika setelah kegagalan , maka berbasis negara dan berbasis delta adalah pilihan yang sempurna. Jika Anda harus menggunakan berbasis op, maka opsinya adalah:

1) Gulung semua operasi yang terlewat sejak kegagalan
2) Salinan lengkap dari salah satu replika dan kembalikan operasi yang terlewat
Seperti disebutkan di atas, berbasis op mengharuskan pembaruan dikirimkan tepat satu kali ke setiap replika. Persyaratan pengiriman hanya sekali dapat dihilangkan jika efektor idempoten. Dalam praktiknya, jauh lebih mudah untuk menerapkan yang pertama daripada yang kedua.

Hubungan antara berbasis-op dan berbasis-negara:

Dua pendekatan dapat ditiru melalui satu sama lain, sehingga di masa depan kami akan mempertimbangkan CRDT tanpa mengacu pada model sinkronisasi tertentu.

6. CRDT

6.1 Penghitung

Integer yang mendukung dua operasi: inc dan dec. Sebagai contoh, pertimbangkan kemungkinan implementasi untuk sinkronisasi berbasis-op dan berbasis-negara:

Penghitung berbasis-op:

Cukup jelas, hanya mengirim pembaruan. Contoh untuk inc:

function generator() { return function (counter) { counter += 1 } }

Penghitung berbasis negara:

Implementasinya tidak lagi begitu jelas, karena tidak jelas seperti apa fungsi penggabungan seharusnya.

Pertimbangkan opsi berikut:

Penghitung yang meningkat secara monoton (Penghitung peningkatan saja, Penghitung-G):

Data akan disimpan sebagai vektor dimensi sama dengan jumlah node (vektor versi) dan setiap replika akan meningkatkan nilai pada posisinya dengan id.

Fungsi gabungan akan mengambil maksimum di posisi yang sesuai, dan nilai akhir adalah jumlah dari semua elemen vektor

\ begin {align} inc () &: V [id ()] = V [id ()] + 1 nilai \\ () &: \ sum_ {i = 0} ^ {n} V [i] \\ menggabungkan (C_1, C_2) &: i \ di [1..n] \ Hasil [i] = maks (C_1.V [i], C_2.V [i]) \ end {align}

$\ begin {align} inc () &: V [id ()] = V [id ()] + 1 nilai \\ () &: \ sum_ {i = 0} ^ {n} V [i] \\ menggabungkan (C_1, C_2) &: i \ di [1..n] \ Hasil [i] = maks (C_1.V [i], C_2.V [i]) \ end {align}$

Anda juga dapat menggunakan G-Set (lihat di bawah)

Aplikasi:

Menghitung klik / klik (sic!)

Counter dengan dukungan decrement (PN-counter)

Kami mulai dua G-counter - satu untuk operasi kenaikan, yang kedua - untuk penurunan

Aplikasi:

Jumlah pengguna yang masuk dalam jaringan p2p, seperti Skype

Penghitung non-negatif

Implementasi yang sederhana belum ada. Sarankan ide Anda di komentar, diskusikan.

6.2 Mendaftar

Sel memori dengan dua operasi - menetapkan (menulis) dan nilai (baca).
Masalahnya adalah bahwa penetapan tidak komutatif. Ada dua pendekatan untuk mengatasi masalah ini:

Registrasi Penulis Terakhir-Menang (LWW-Register):

Kami memasukkan pesanan penuh melalui pembuatan id unik untuk setiap operasi (stempel waktu, misalnya).

Contoh sinkronisasi adalah pertukaran pasangan (nilai, id):

Aplikasi:

Kolom dalam cassandra
NFS - file secara keseluruhan atau sebagian

Mendaftar dengan beberapa nilai (Daftar Multi-Nilai, Daftar-MV):

Pendekatannya mirip dengan G-counter - kami menyimpan set (nilai, vektor versi). Nilai register - semua nilai, saat digabung - LWW secara terpisah untuk setiap nilai dalam vektor.

Aplikasi:

Keranjang di Amazon. Bug yang terkenal dikaitkan dengan ini, ketika setelah menghapus item dari keranjang itu muncul lagi. Alasannya adalah bahwa meskipun register menyimpan sejumlah nilai, itu bukan set (lihat gambar di bawah). Omong-omong, Amazon bahkan tidak menganggap ini sebagai bug - bahkan, ini meningkatkan penjualan.
Riak. Dalam kasus yang lebih umum, kami menggeser masalah memilih Nilai aktual (catatan - tidak ada konflik!) Ke aplikasi.

Penjelasan bug di Amazon:

6.3 Banyak

Set adalah tipe dasar untuk membangun wadah, peta, dan grafik dan mendukung operasi - tambah dan rmv, yang tidak komutatif.

Pertimbangkan implementasi naif dari set berbasis op, di mana add dan rmv dieksekusi saat mereka tiba (add datang ke 1 dan 2 replika pada saat yang sama, kemudian rmv ke 1)

Seperti yang Anda lihat, replika akhirnya tersebar. Pertimbangkan berbagai opsi untuk membangun set bebas konflik:

Growing Set (G-Set):

Solusi termudah adalah mencegah barang dihapus. Yang tersisa hanyalah operasi add, yang komutatif. Fungsi gabungan adalah gabungan set.

Dua Fase Set (2P-Set):

Kami mengizinkan Anda menghapus, tetapi Anda tidak dapat menambahkannya lagi setelah dihapus. Untuk mengimplementasikan, kami membuat set elemen G-set jarak jauh yang terpisah (set seperti itu disebut set batu nisan)
Contoh untuk berbasis negara:

\ begin {align} lookup (e) &: e \ di A \ land e \ notin R \\ tambahkan (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ bergabung (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {align}

$\ begin {align} lookup (e) &: e \ di A \ land e \ notin R \\ tambahkan (e) &: A = A \ cup \ {e \} \\ rmv (e) &: R = R \ cup \ {e \} \\ bergabung (S_1, S_2) &: \\ Res & ult.A = S_1.A \ cup S_2.A \\ Res & ult.R = S_1.R \ cup S_2.R \ end {align}$

Set elemen LWW:

Cara selanjutnya untuk menerapkan set bebas konflik adalah dengan memperkenalkan pesanan lengkap, salah satu opsi adalah untuk menghasilkan cap waktu unik untuk setiap elemen.

Kami mendapatkan dua set - add-set dan hapus-set, ketika add () dipanggil, add (elemen, unique_id ()), ketika memeriksa apakah ada elemen di set - lihat di mana timestamp lebih besar - di hapus-set atau di add-set

PN-Set:

Variasi dengan pemesanan set - kita mulai penghitung untuk setiap elemen, ketika kita menambahkannya, kita menambahnya, ketika kita menghapusnya kita menguranginya. Elemen ada di set jika penghitungnya positif.

Perhatikan efek yang menarik - di replika ketiga, menambahkan elemen tidak mengarah ke penampilannya.

Amati-Hapus Set, AT-Set, Set Tambah-Menang:

Dalam jenis ini, tambahkan diutamakan daripada menghapus. Contoh implementasi: setiap elemen yang baru ditambahkan akan diberi tag unik (relatif terhadap elemen, dan bukan seluruh set). Rmv menghapus elemen dari set dan mengirimkan semua pasangan yang terlihat (elemen, tag) ke replika untuk dihapus.

Hapus-menang Set:

Mirip dengan yang sebelumnya, tetapi pada saat yang sama add / rmv rmv menang.

6.4 Grafik

Tipe ini dibangun atas dasar banyak. Masalahnya adalah ini: jika ada operasi simultan addEdge (u, v) dan removeVertex (u) - apa yang harus saya lakukan? Opsi berikut dimungkinkan:

Prioritas RemoveVertex, semua insiden tepi ke titik ini dihapus
Prioritas AddEdge, simpul yang dihapus dipulihkan
Kami menunda eksekusi removeVertex sampai semua addEdge simultan dijalankan.

Opsi termudah adalah yang pertama, untuk implementasinya (2P2P-Graph) cukup untuk mendapatkan dua 2P-Set, satu untuk simpul, yang kedua untuk tepi

6.5 Peta

Peta literal:

Dua masalah untuk dipecahkan:

Apa yang harus dilakukan dengan operasi put simultan? Dengan analogi dengan penghitung, Anda dapat memilih semantik LWW atau MV
Apa yang harus dilakukan dengan put / rmv simultan? Dengan analogi dengan set, Anda bisa menang-menang, atau menang-menang, atau semantik menang-terakhir.

Pemetaan CRDT (Peta CRDT):

Kasus yang lebih menarik, karena memungkinkan Anda untuk membangun pemetaan bersarang. Kami tidak mempertimbangkan kasus perubahan tipe bersarang - ini harus diputuskan oleh CRDT bersarang itu sendiri.

Hapus-sebagai-rekursif-reset peta

Operasi penghapusan "me-reset" nilai tipe ke kondisi awal tertentu. Misalnya, untuk penghitung, ini adalah nilai nol.

Pertimbangkan contoh - daftar belanja umum. Salah satu pengguna menambahkan tepung, dan yang kedua membuat checkout (ini mengarah pada panggilan ke operasi hapus pada semua elemen). Akibatnya, satu unit tepung tetap ada dalam daftar, yang tampaknya logis.

Hapus-menang peta

Operasi rmv diutamakan.

Contoh: dalam game online, pemain Alice memiliki 10 koin dan palu. Kemudian dua peristiwa secara bersamaan terjadi: pada replika A, ia menghasilkan paku, dan pada replika B, karakternya dihapus dengan menghilangkan semua objek:

Perhatikan bahwa saat menggunakan remove-as-recursive, paku pada akhirnya akan tetap, yang bukan keadaan yang benar ketika karakter dihilangkan.

Perbarui-menang peta

Pembaruan diutamakan, atau lebih tepatnya, membatalkan operasi sebelumnya untuk menghapus rmv simultan.

Contoh: dalam game online, karakter Alice pada replika B dihapus karena tidak aktif, tetapi aktivitas terjadi pada replika A pada saat yang sama. Jelas, operasi penghapusan harus dibatalkan.

Ada satu efek menarik ketika bekerja dengan implementasi seperti itu - misalkan kita memiliki dua replika, A dan B, dan mereka menyimpan set dengan beberapa kunci k. Kemudian, jika A menghapus nilai kunci k, dan B menghapus semua elemen set, maka pada akhirnya replika akan meninggalkan set kosong dengan kunci k.

Perhatikan bahwa implementasi naif tidak akan berfungsi dengan benar - Anda tidak bisa dengan mudah membatalkan semua operasi penghapusan sebelumnya. Dalam contoh berikut, dengan pendekatan ini, kondisi akhir akan menjadi kondisi awal, yang tidak benar:

Daftar

Masalah dengan jenis ini adalah bahwa indeks item pada replika yang berbeda akan berbeda setelah operasi penyisipan / penghapusan lokal. Untuk mengatasi masalah ini, pendekatan Transformasi Operasional diterapkan - ketika menerapkan perubahan yang diperoleh, indeks elemen dalam replika asli harus diperhitungkan.

7. Riak

Sebagai contoh, pertimbangkan CRDT di Riak:

Counter: PN-Counter
Atur: ATAU-Atur
Peta: Perbarui-menangkan Peta CRDT
(Boolean) Bendera: ATAU-Tetapkan di mana maksimum 1 elemen
Daftar: pasangan (nilai, cap waktu)

8. Siapa yang menggunakan CRDT

Bagian wiki berisi contoh-contoh bagus.

CRDT: Jenis Data Replikasi yang bebas konflik