Dalam sistem terdistribusi, ada sejumlah masalah mendasar: transaksi terdistribusi yang efisien, pemrosesan data yang tepat sekali, sinkronisasi jam fisik yang akurat. Untuk mengatasi masalah yang terakhir , berbagai jenis jam logika diciptakan .
Namun demikian, jam vektor memiliki sifat yang tidak menyenangkan: mereka memperkenalkan ketergantungan bersyarat antara peristiwa di mana itu tidak ada, dan kehilangan itu di tempat yang sebenarnya.
Namun, Anda dapat menemukan sesuatu yang lebih dapat diandalkan - Kronos. Dalam artikel ini, kita akan melihat algoritma akuntansi hubungan sebab-akibat dan aplikasinya untuk membangun repositori Key-Value dengan transaksi terdistribusi.
Masalahnya
Seperti yang telah disebutkan, ada sejumlah masalah dengan jam logis:
Ketergantungan tidak ada muncul karena jam logis memperkenalkan urutan lengkap pada peristiwa - yaitu, salah satu dari dua peristiwa dapat dikatakan lebih awal bersyarat dan yang bersyarat nanti. Kontrak tersebut bersifat kondisional, karena tidak mungkin untuk menentukan secara tepat hubungan antara peristiwa-peristiwa dalam waktu, termasuk karena Teori Relativitas Khusus.
Di sisi lain, jam logika hanya mempertimbangkan interkoneksi melalui pesan di dalam sistem. Jika beberapa dua peristiwa terhubung, tetapi di luar sistem, misalnya, melalui pengguna (menambahkan barang ke keranjang di satu bagian sistem -> pembayaran untuk pesanan), maka jam logis mungkin melewatkan hubungan semacam itu.
Jam logis tidak dapat diakses dari luar, dan juga sulit untuk menghubungkan beberapa komponen independen (sistem file terdistribusi, layanan pemrosesan permintaan, analitik).
Solusi
Artikel 2014 oleh Kronos: Desain dan Implementasi Layanan Pemesanan Acara mengusulkan solusi - layanan mandiri yang akan memperhitungkan hubungan sebab-akibat dalam acara.
Abstraksi utama di dalam Kronos adalah peristiwa di mana pemesanan sebagian diperkenalkan. Hubungan sebab akibat adalah transitif - yaitu, jika, misalnya, kita tahu bahwa pembuatan file mendahului perubahannya, dan perubahan mendahului penghapusan, kita dapat membuat kesimpulan logis bahwa penciptaan terjadi sebelum penghapusan.
API minimum dapat didefinisikan dengan serangkaian metode berikut:
| Metode | Hasil | Komentar |
|---|
create_event() | e | Membuat acara baru di Kronos |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | Untuk setiap pasangan permintaan, ia mengembalikan arah hubungan sebab-akibat, atau simultanitas peristiwa |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | Untuk setiap pasangan permintaan, tetapkan arah penyebabnya |
acquire_ref(e) | OK | Meningkatkan penghitung referensi untuk acara ini. |
release_ref(e) | OK | Mengurangi jumlah referensi untuk acara ini. |
Implementasi
Adalah logis bahwa sistem didasarkan pada grafik peristiwa yang berorientasi, dengan pencarian luas pertama yang efektif untuk memeriksa hubungan peristiwa, mekanisme stabilitas jika terjadi kegagalan, dan pengumpulan sampah.
Seperti dapat dilihat dari API, permintaan assign_order menerima jenis hubungan kausal: must atau prefer . must sesuai dengan invarian ketat - misalnya, _->_ , prefer tidak dapat diterapkan jika konflik dengan hubungan must . Contoh menggunakan prefer adalah bahwa permintaan yang datang lebih awal lebih baik dibungkus sebelumnya, tetapi ini tidak mempengaruhi kebenaran.
BFS efektif
Dalam kasus kami, grafik mungkin besar, tetapi acara yang permintaan verifikasi akan dieksekusi biasanya akan ditutup. Oleh karena itu, Anda harus menjalankan BFS lebih cepat untuk kasus seperti itu.
Dalam implementasi standar, tempat terpanjang adalah inisialisasi array dari simpul yang dikunjungi, yang selalu membutuhkan waktu yang sama dengan jumlah simpul dalam grafik. Sebagai gantinya, Anda bisa menggunakan tabel hash atau menerapkan trik lain.
Pengumpulan sampah
Seperti yang dapat Anda lihat dari tabel, ada dua metode lagi: acquire_ref dan release_ref .
Di dalam Kronos, penghitung referensi disimpan untuk setiap acara. Sementara beberapa layanan memproses acara, atau cadangan kemampuan untuk menambahkan acara baru yang terjadi setelah acara saat ini, ia menyimpan tautan. Ketika kebutuhan ini hilang, layanan memanggil release_ref .
Kronos akan menghapus acara ketika semua kondisi terpenuhi:
- Jumlah tautan mencapai nol
- Semua peristiwa sebelum ini sudah dihapus dari grafik.
Pendekatan ini tidak membatasi kemungkinan pertanyaan, tetapi menyimpan memori di dalam Kronos.
Aplikasi
Pertimbangkan penggunaan sistem menggunakan contoh penyimpanan nilai-kunci dengan transaksi yang didistribusikan.
Misalkan ada beberapa server, setiap server bertanggung jawab atas serangkaian kunci.
Setiap transaksi berhubungan dengan suatu peristiwa di Kronos. Untuk setiap kunci, server harus menyimpan jumlah transaksi terakhir di mana kunci ini berpartisipasi. Klien membuat acara dan mengirimkan nomornya ke semua server yang kunci-kuncinya dipengaruhi oleh transaksi ini. Server sedang mencoba membuat ketergantungan di Kronos antara nomor transaksi saat ini dan peristiwa sebelumnya yang disimpan untuk kunci ini. Jika Anda tidak dapat membuat ketergantungan, maka transaksi diakui sebagai tidak berhasil (perhatikan bahwa sampai sekarang belum ada interaksi dengan data).
Jika semua operasi ketergantungan add selesai dengan sukses - ini berarti bahwa transaksi akan terjadi dan itu dapat dilakukan. Server mempelajari hal ini dari klien dan mulai mengeksekusi bagian dari transaksi.
Perhatikan bahwa transaksi tersebut akan ACID :
- Atomicity : transaksi tidak akan dijadwalkan di Kronos, atau akan dijadwalkan untuk dieksekusi di semua node.
- Konsistensi : secara otomatis dalam repositori KV.
- Isolasi : jika dua transaksi berpotongan menurut data, maka mereka akan dihubungkan oleh hubungan sebab akibat di Kronos, yang berarti bahwa satu akan dieksekusi sebelum yang lain.
- Daya tahan : karena Kronos tahan jatuh dan mengasumsikan setiap replika lemari besi juga stabil, satu-satunya hal untuk membuktikan adalah kegigihan data transaksi yang tertunda. Memang, jika transaksi ditandai oleh klien sebagai berhasil, tetapi catatan belum selesai di server, maka fakta ini mudah dibuat, karena server juga melacak bagian yang selesai dari transaksi.
Performa
Menerapkan penyimpanan KV semacam itu memang bisa efektif. Artikel asli mengutip data bahwa implementasi KV-storage yang dideskripsikan adalah 4 kali lebih cepat daripada transaksi berdasarkan kunci.
Selain itu, dibandingkan dengan MongoDB, sistem di atas Kronos hanya 6% di belakang, meskipun fakta bahwa MongoDB tidak menggunakan transaksi terdistribusi.
Analisis
Namun, pengoperasian Kronos memiliki beberapa kelemahan.
- Pertama, ada overhead mengakses Kronos - setiap permintaan akan membutuhkan setidaknya satu panggilan.
- Kronos juga akan menjadi titik kegagalan tunggal - penulis artikel tidak menawarkan cara untuk membagi grafik acara.
- Akan menyenangkan untuk menambahkan sejumlah metode ke sistem. Sebagai contoh, dalam contoh dengan penyimpanan KV akan lebih baik untuk memiliki panggilan balik yang akan menginformasikan server tentang status transaksi - itu berhasil ditambahkan ke grafik dengan semua dependensi yang diperlukan - atau, sebaliknya, transaksi tidak dapat diselesaikan.
Namun demikian, sistem yang dijelaskan memungkinkan kontrol yang fleksibel dari hubungan kausal antara peristiwa, memastikan kepatuhan yang dapat diprediksi dengan invarian yang diperlukan.
Kesimpulan
Tentang ini, kami di GoTo School mengajarkan siswa dan anak sekolah ke arah Sistem Terdistribusi.
Dan ada Algoritma dan Aplikasi , Pemrograman Terapan, Bioinformatika dan Analisis Data
Datanglah ke sekolah musim gugur kami pada tanggal 27 Oktober - 4 November atau sekolah musim dingin di awal Januari.
Dan jika Anda bukan lagi pelajar atau pelajar - datanglah untuk mengajar .