Jadi, mari kita bayangkan. Ada 5 kucing yang terkunci di dalam ruangan, dan untuk membangunkan pemiliknya, mereka semua harus menyepakati hal ini di antara mereka sendiri, karena mereka hanya dapat membuka pintu jika mereka berlima bersandar padanya. Jika salah satu kucing tersebut adalah kucing Schrödinger, dan kucing lainnya tidak mengetahui keputusannya, muncul pertanyaan: “Bagaimana mereka dapat melakukannya?”
Pada artikel ini, saya akan memberi tahu Anda secara sederhana tentang komponen teoretis dunia sistem terdistribusi dan prinsip pengoperasiannya. Saya juga akan membahas secara dangkal ide utama yang mendasari Paxos.
Ketika pengembang menggunakan infrastruktur cloud, berbagai database, dan bekerja dalam cluster dengan node dalam jumlah besar, mereka yakin bahwa data akan lengkap, aman, dan selalu tersedia. Tapi di mana jaminannya?
Intinya, jaminan yang kami miliki adalah jaminan pemasok. Mereka dijelaskan dalam dokumentasi sebagai berikut: “Layanan ini cukup dapat diandalkan, memiliki SLA tertentu, jangan khawatir, semuanya akan bekerja secara terdistribusi seperti yang Anda harapkan.”
Kita cenderung percaya pada yang terbaik, karena orang-orang pintar dari perusahaan besar meyakinkan kita bahwa semuanya akan baik-baik saja. Kami tidak mengajukan pertanyaan: mengapa sebenarnya hal ini bisa berhasil? Apakah ada pembenaran formal untuk pengoperasian sistem seperti itu dengan benar?
Saya baru-baru ini pergi ke dan sangat terinspirasi oleh topik ini. Perkuliahan di sekolah lebih mirip kelas kalkulus daripada sesuatu yang berhubungan dengan sistem komputer. Namun dengan cara inilah algoritma terpenting yang kita gunakan setiap hari, tanpa kita sadari, terbukti pada satu waktu.
Sebagian besar sistem terdistribusi modern menggunakan algoritma konsensus Paxos dan berbagai modifikasinya. Yang paling keren adalah validitas dan, pada prinsipnya, kemungkinan besar keberadaan algoritma ini dapat dibuktikan hanya dengan pena dan kertas. Dalam praktiknya, algoritme ini digunakan dalam sistem besar yang berjalan pada sejumlah besar node di cloud.
Sedikit gambaran yang akan dibahas selanjutnya: tugas dua jenderalMari kita lihat pemanasannya .
Kami memiliki dua tentara - merah dan putih. Pasukan kulit putih bermarkas di kota yang terkepung. Pasukan Merah dipimpin oleh Jenderal A1 dan A2 terletak di dua sisi kota. Tugas si rambut merah adalah menyerang kota putih dan menang. Namun, pasukan masing-masing jenderal merah secara individual lebih kecil daripada tentara kulit putih.
Syarat kemenangan bagi pihak merah: kedua jenderal harus menyerang pada waktu yang sama untuk mendapatkan keunggulan numerik atas pihak kulit putih. Untuk melakukan ini, Jenderal A1 dan A2 harus mencapai kesepakatan satu sama lain. Jika semua orang menyerang secara terpisah, si rambut merah akan kalah.
Untuk mencapai kesepakatan, jenderal A1 dan A2 dapat saling mengirim utusan melalui wilayah kota putih. Utusan tersebut mungkin berhasil mencapai jenderal sekutu atau mungkin dicegat oleh musuh. Pertanyaan: apakah ada urutan komunikasi antara jenderal berambut merah (urutan pengiriman utusan dari A1 ke A2 dan sebaliknya dari A2 ke A1), di mana mereka dijamin akan menyepakati penyerangan pada jam X. Di sini, jaminan berarti kedua jenderal akan mendapat konfirmasi yang jelas bahwa sekutu (jenderal lain) pasti akan menyerang pada waktu yang ditentukan X.
Misalkan A1 mengirim utusan ke A2 dengan pesan: “Ayo serang tengah malam hari ini!” Jenderal A1 tidak dapat menyerang tanpa konfirmasi dari Jenderal A2. Jika utusan dari A1 sudah tiba, maka Jenderal A2 mengirimkan konfirmasi dengan pesan: “Ya, ayo kita bunuh orang kulit putih hari ini.” Namun kini Jenderal A2 tidak mengetahui apakah utusannya sudah tiba atau belum, ia tidak memiliki jaminan apakah penyerangan akan dilakukan secara serentak. Sekarang Jenderal A2 perlu konfirmasi lagi.
Jika kita menggambarkan lebih jauh komunikasi mereka, menjadi jelas bahwa tidak peduli berapa banyak siklus pertukaran pesan yang ada, tidak ada jaminan bahwa kedua jenderal telah menerima pesan mereka (dengan asumsi bahwa salah satu pengirim pesan dapat disadap).
Masalah Dua Jenderal adalah ilustrasi bagus dari sistem terdistribusi yang sangat sederhana di mana terdapat dua node dengan komunikasi yang tidak dapat diandalkan. Ini berarti kami tidak memiliki jaminan 100% bahwa keduanya tersinkronisasi. Masalah serupa hanya akan dibahas dalam skala yang lebih besar di artikel selanjutnya.
Kami memperkenalkan konsep sistem terdistribusi
Sistem terdistribusi adalah sekelompok komputer (selanjutnya kita menyebutnya node) yang dapat bertukar pesan. Setiap node individu adalah semacam entitas otonom. Sebuah node dapat memproses tugasnya sendiri, namun untuk berkomunikasi dengan node lain, node tersebut perlu mengirim dan menerima pesan.
Bagaimana tepatnya pesan diimplementasikan, protokol apa yang digunakan - ini tidak menarik bagi kami dalam konteks ini. Penting agar node dari sistem terdistribusi dapat bertukar data satu sama lain dengan mengirimkan pesan.
Definisinya sendiri tidak terlihat terlalu rumit, namun kita harus memperhitungkan bahwa sistem terdistribusi memiliki sejumlah atribut yang penting bagi kita.
Atribut sistem terdistribusi
- Concurrency – kemungkinan kejadian simultan atau bersamaan yang terjadi dalam sistem. Selain itu, kami akan menganggap peristiwa yang terjadi pada dua node berbeda berpotensi terjadi secara bersamaan selama kami tidak memiliki urutan kejadian yang jelas. Namun, sebagai aturan, kami tidak memilikinya.
- Tidak ada jam global. Kita tidak mempunyai urutan kejadian yang jelas karena tidak adanya jam global. Dalam dunia manusia biasa, kita terbiasa dengan kenyataan bahwa kita mempunyai jam dan waktu secara mutlak. Segalanya berubah ketika menyangkut sistem terdistribusi. Bahkan jam atom yang sangat presisi pun mengalami penyimpangan, dan mungkin ada situasi di mana kita tidak dapat membedakan peristiwa mana yang terjadi terlebih dahulu. Oleh karena itu, kita juga tidak bisa mengandalkan waktu.
- Kegagalan independen dari node sistem. Ada masalah lain: ada yang tidak beres hanya karena node kita tidak bertahan selamanya. Hard drive mungkin gagal, mesin virtual di cloud mungkin reboot, jaringan mungkin berkedip dan pesan akan hilang. Selain itu, mungkin ada situasi ketika node bekerja, tetapi pada saat yang sama bekerja melawan sistem. Kelas masalah terakhir bahkan mendapat nama tersendiri: masalah . Contoh paling populer dari sistem terdistribusi dengan masalah ini adalah Blockchain. Namun hari ini kami tidak akan mempertimbangkan kelompok masalah khusus ini. Kami akan tertarik pada situasi di mana satu atau lebih node mungkin gagal.
- Model komunikasi (messaging model) antar node. Kami telah menetapkan bahwa node berkomunikasi dengan bertukar pesan. Ada dua model perpesanan yang terkenal: sinkron dan asinkron.
Model komunikasi antar node dalam sistem terdistribusi
Model sinkron – kita mengetahui dengan pasti bahwa ada delta waktu terbatas yang diketahui dimana pesan dijamin akan sampai dari satu node ke node lainnya. Jika waktu ini telah berlalu dan pesan belum sampai, kita dapat mengatakan bahwa node telah gagal. Dalam model ini kami memiliki waktu tunggu yang dapat diprediksi.
Model asinkron – dalam model asynchronous kami menganggap bahwa waktu tunggunya terbatas, namun tidak ada delta waktu yang setelahnya kami dapat menjamin bahwa node telah gagal. Itu. Waktu tunggu untuk pesan dari sebuah node bisa sangat lama. Ini adalah definisi yang penting, dan kita akan membicarakannya lebih lanjut.
Konsep konsensus dalam sistem terdistribusi
Sebelum mendefinisikan secara formal konsep konsensus, mari kita perhatikan contoh situasi di mana kita membutuhkannya, yaitu - Replikasi Mesin Negara.
Kami memiliki beberapa log yang didistribusikan. Kami ingin ini konsisten dan berisi data yang identik di semua node sistem terdistribusi. Ketika salah satu node mempelajari nilai baru yang akan ditulisnya ke log, tugasnya adalah menawarkan nilai ini ke semua node lainnya sehingga log diperbarui di semua node dan sistem berpindah ke keadaan baru yang konsisten. Dalam hal ini, penting agar node-node tersebut sepakat satu sama lain: semua node setuju bahwa nilai baru yang diusulkan adalah benar, semua node menerima nilai ini, dan hanya dalam kasus ini setiap orang dapat menulis nilai baru ke log.
Dengan kata lain: tidak ada node yang keberatan karena memiliki informasi yang lebih relevan, dan nilai yang diusulkan salah. Kesepakatan antar node dan kesepakatan mengenai satu nilai yang diterima dengan benar adalah konsensus dalam sistem terdistribusi. Selanjutnya, kita akan membahas tentang algoritma yang memungkinkan sistem terdistribusi dijamin mencapai konsensus.
Secara lebih formal, kita dapat mendefinisikan algoritme konsensus (atau sekadar algoritme konsensus) sebagai fungsi tertentu yang mentransfer sistem terdistribusi dari status A ke status B. Selain itu, status ini diterima oleh semua node, dan semua node dapat mengonfirmasinya. Ternyata, tugas ini tidak sepele seperti yang terlihat pada pandangan pertama.
Properti Algoritma Konsensus
Algoritme konsensus harus memiliki tiga properti agar sistem dapat terus ada dan mengalami kemajuan dalam berpindah dari satu negara ke negara lain:
- Persetujuan – semua node yang beroperasi dengan benar harus memiliki nilai yang sama (dalam artikel, properti ini juga disebut sebagai properti keselamatan). Semua node yang saat ini berfungsi (belum mengalami kegagalan atau kehilangan kontak dengan node lain) harus mencapai kesepakatan dan menerima beberapa nilai akhir yang sama.
Penting untuk dipahami di sini bahwa node dalam sistem terdistribusi yang kami pertimbangkan ingin setuju. Artinya, kita sekarang berbicara tentang sistem di mana sesuatu bisa saja gagal (misalnya, beberapa node gagal), tetapi dalam sistem ini pasti tidak ada node yang dengan sengaja bekerja melawan node lain (tugas para jenderal Bizantium). Berkat properti ini, sistem tetap konsisten.
- Integritas — jika semua node yang berfungsi dengan benar menawarkan nilai yang sama v, yang berarti setiap node yang beroperasi dengan benar harus menerima nilai ini v.
- Penghentian – semua node yang beroperasi dengan benar pada akhirnya akan mengambil nilai tertentu (properti keaktifan), yang memungkinkan algoritme membuat kemajuan dalam sistem. Setiap node yang beroperasi dengan benar cepat atau lambat harus menerima nilai akhir dan mengonfirmasinya: “Bagi saya, nilai ini benar, saya setuju dengan keseluruhan sistem.”
Contoh cara kerja algoritma konsensus
Meskipun sifat-sifat algoritmanya mungkin tidak sepenuhnya jelas. Oleh karena itu, kami akan mengilustrasikan dengan contoh tahapan apa yang dilalui algoritma konsensus paling sederhana dalam sistem dengan model pesan sinkron, di mana semua node berfungsi seperti yang diharapkan, pesan tidak hilang dan tidak ada yang rusak (apakah ini benar-benar terjadi?).
- Semuanya dimulai dengan lamaran pernikahan (Propose). Mari kita asumsikan bahwa klien terhubung ke sebuah node bernama "Node 1" dan memulai transaksi, meneruskan nilai baru ke node tersebut - O. Mulai sekarang, kita akan memanggil "Node 1" tawaran. Sebagai pengusul, “Node 1” sekarang harus memberi tahu seluruh sistem bahwa ia memiliki data baru, dan mengirimkan pesan ke semua node lainnya: “Lihat! Arti “O” terlintas di benak saya dan saya ingin menuliskannya! Harap konfirmasi bahwa Anda juga akan mencatat “O” di log Anda.”
- Tahap selanjutnya adalah pemungutan suara terhadap nilai yang diusulkan (Voting). Untuk apa? Mungkin saja node lain telah menerima informasi yang lebih baru, dan mereka memiliki data tentang transaksi yang sama.
Ketika node “Node 1” mengirimkan usulannya, node lain memeriksa log mereka untuk data tentang peristiwa ini. Jika tidak ada kontradiksi, node mengumumkan: “Ya, saya tidak punya data lain untuk acara ini. Nilai “O” adalah informasi terkini yang layak kami dapatkan.”Dalam kasus lain, node dapat merespons “Node 1”: “Dengar! Saya memiliki data terbaru tentang transaksi ini. Bukan 'O', tapi sesuatu yang lebih baik."
Pada tahap pemungutan suara, node mengambil keputusan: apakah mereka semua menerima nilai yang sama, atau salah satu dari mereka memberikan suara menentang, yang menunjukkan bahwa ia memiliki data yang lebih baru.
- Jika putaran pemungutan suara berhasil dan semua orang mendukung, maka sistem akan berpindah ke tahap baru - Menerima nilai. “Node 1” mengumpulkan semua tanggapan dari node lain dan melaporkan: “Semua orang menyetujui nilai “O”! Sekarang saya secara resmi menyatakan bahwa “O” adalah arti baru kami, sama untuk semua orang! Tuliskan di buku kecilmu, jangan lupa. Tuliskan di catatanmu!”
- Node yang tersisa mengirimkan konfirmasi (Diterima) bahwa mereka telah menuliskan nilai “O”; tidak ada hal baru yang tiba selama waktu ini (semacam komitmen dua fase). Setelah peristiwa penting ini, kami menganggap bahwa transaksi distribusi telah selesai.
Dengan demikian, algoritma konsensus dalam kasus sederhana terdiri dari empat langkah: mengusulkan, memilih (voting), menerima (accept), mengkonfirmasi penerimaan (accepted).
Jika pada langkah tertentu kami tidak dapat mencapai kesepakatan, maka algoritme akan dimulai lagi, dengan mempertimbangkan informasi yang diberikan oleh node yang menolak untuk mengonfirmasi nilai yang diusulkan.
Algoritma konsensus dalam sistem asinkron
Sebelumnya, semuanya lancar, karena kita berbicara tentang model perpesanan yang sinkron. Namun kita tahu bahwa di dunia modern kita terbiasa melakukan segala sesuatu secara tidak sinkron. Bagaimana algoritma serupa bekerja dalam sistem dengan model perpesanan asinkron, di mana kami percaya bahwa waktu tunggu untuk respons dari sebuah node bisa sangat lama (omong-omong, kegagalan sebuah node juga dapat dianggap sebagai contoh ketika sebuah node dapat merespons untuk waktu yang sangat lama).
Sekarang kita tahu bagaimana algoritma konsensus bekerja pada prinsipnya, sebuah pertanyaan bagi pembaca yang ingin tahu yang telah sampai sejauh ini: berapa banyak node dalam sistem yang terdiri dari N node dengan model pesan asinkron yang bisa gagal sehingga sistem masih bisa mencapai konsensus?
Jawaban dan pembenaran yang benar ada di balik spoiler.Jawaban yang benar adalah: 0. Jika satu node dalam sistem asynchronous gagal, sistem tidak akan dapat mencapai konsensus. Pernyataan ini dibuktikan dalam teorema FLP yang terkenal di kalangan tertentu (1985, Fischer, Lynch, Paterson, link ke aslinya di akhir artikel): “Ketidakmungkinan mencapai konsensus terdistribusi jika setidaknya satu node gagal .”
Teman-teman, kalau begitu kita punya masalah, kita terbiasa dengan segala sesuatu yang tidak sinkron. Dan ini dia. Bagaimana cara terus hidup?
Kami baru saja berbicara tentang teori, tentang matematika. Apa yang dimaksud dengan “konsensus tidak dapat dicapai”, diterjemahkan dari bahasa matematika ke dalam bahasa kita - teknik? Artinya “tidak selalu dapat dicapai”, yaitu. Ada kasus di mana konsensus tidak dapat dicapai. Kasus macam apa ini?
Ini adalah pelanggaran terhadap properti keaktifan yang dijelaskan di atas. Kami tidak memiliki kesepakatan bersama, dan sistem tidak dapat mengalami kemajuan (tidak dapat selesai dalam waktu terbatas) jika kami tidak mendapat respons dari semua node. Karena dalam sistem asinkron kita tidak mempunyai waktu respons yang dapat diprediksi dan kita tidak dapat mengetahui apakah suatu node mengalami crash atau hanya membutuhkan waktu lama untuk merespons.
Namun dalam praktiknya kita bisa menemukan solusinya. Biarkan algoritme kami dapat bekerja dalam waktu lama jika terjadi kegagalan (berpotensi dapat bekerja tanpa batas waktu). Namun dalam sebagian besar situasi, ketika sebagian besar node berfungsi dengan benar, kita akan mendapatkan kemajuan dalam sistem.
Dalam praktiknya, kita berurusan dengan model komunikasi yang sebagian sinkron. Sinkronisasi parsial dipahami sebagai berikut: secara umum, kita memiliki model asinkron, tetapi konsep tertentu tentang "waktu stabilisasi global" pada titik waktu tertentu diperkenalkan secara formal.
Momen ini mungkin tidak akan terjadi dalam jangka waktu yang lama, namun harus terjadi suatu hari nanti. Jam alarm virtual akan berdering, dan sejak saat itu kita dapat memprediksi delta waktu kapan pesan akan sampai. Mulai saat ini, sistem berubah dari asinkron menjadi sinkron. Dalam praktiknya, kita justru menangani sistem seperti itu.
Algoritme Paxos memecahkan masalah konsensus
adalah keluarga algoritme yang memecahkan masalah konsensus untuk sistem yang sinkron sebagian, dengan kemungkinan beberapa node mungkin gagal. Penulis Paxos adalah . Dia mengusulkan bukti formal keberadaan dan kebenaran algoritma pada tahun 1989.
Namun buktinya ternyata jauh dari kata sepele. Publikasi pertama dirilis hanya pada tahun 1998 (33 halaman) yang menjelaskan algoritma tersebut. Ternyata sangat sulit untuk dipahami, dan pada tahun 2001 penjelasan artikel tersebut diterbitkan sepanjang 14 halaman. Volume publikasi diberikan untuk menunjukkan bahwa sebenarnya masalah konsensus sama sekali tidak sederhana, dan di balik algoritma semacam itu terdapat banyak sekali pekerjaan yang dilakukan oleh orang-orang paling cerdas.
Menariknya, Leslie Lamport sendiri dalam ceramahnya mencatat bahwa pada artikel penjelasan kedua terdapat satu pernyataan, satu baris (dia tidak merinci yang mana), yang dapat diartikan berbeda-beda. Oleh karena itu, sejumlah besar implementasi Paxos modern tidak berfungsi sepenuhnya dengan benar.
Analisis mendetail atas karya Paxos akan membutuhkan lebih dari satu artikel, jadi saya akan mencoba menyampaikan secara singkat gagasan utama algoritme tersebut. Di tautan di akhir artikel saya, Anda akan menemukan materi untuk mendalami topik ini lebih jauh.
Peran di Paxos
Algoritme Paxos memiliki konsep peran. Mari kita pertimbangkan tiga yang utama (ada modifikasi dengan peran tambahan):
- Pengusul (bisa juga digunakan istilah: pemimpin atau koordinator). Mereka adalah orang-orang yang belajar tentang beberapa nilai baru dari pengguna dan mengambil peran sebagai pemimpin. Tugas mereka adalah meluncurkan serangkaian proposal untuk nilai baru dan mengoordinasikan tindakan lebih lanjut dari node. Apalagi Paxos memungkinkan kehadiran beberapa pemimpin dalam situasi tertentu.
- Akseptor (Pemilih). Ini adalah node yang memilih untuk menerima atau menolak nilai tertentu. Peran mereka sangat penting, karena keputusan bergantung pada mereka: keadaan apa yang akan (atau tidak akan) dicapai oleh sistem setelah tahap berikutnya dari algoritma konsensus.
- Pembelajar. Node yang hanya menerima dan menulis nilai baru yang diterima ketika keadaan sistem berubah. Mereka tidak membuat keputusan, mereka hanya menerima data dan memberikannya kepada pengguna akhir.
Satu node dapat menggabungkan beberapa peran dalam situasi berbeda.
Konsep kuorum
Kami berasumsi bahwa kami memiliki sistem N node Dan jumlahnya maksimal F node mungkin gagal. Jika F node gagal, maka kita harus memiliki setidaknya 2F+1 node akseptor.
Hal ini diperlukan agar kita selalu memiliki mayoritas, bahkan dalam situasi terburuk, node “baik” yang berfungsi dengan benar. Itu adalah F+1 node "baik" yang setuju, dan nilai akhir akan diterima. Jika tidak, mungkin akan terjadi situasi di mana kelompok-kelompok lokal mempunyai pemahaman yang berbeda dan tidak bisa sepakat di antara mereka sendiri. Oleh karena itu, kita memerlukan mayoritas absolut untuk memenangkan suara.
Gagasan umum tentang cara kerja algoritma konsensus Paxos
Algoritme Paxos melibatkan dua fase besar, yang masing-masing dibagi menjadi dua langkah:
- Fase 1a: Persiapan. Selama fase persiapan, pemimpin (pengusul) menginformasikan semua node: “Kami memulai fase pemungutan suara baru. Kami memiliki babak baru. Jumlah putaran ini adalah n. Sekarang kita akan mulai memberikan suara." Untuk saat ini, ia hanya melaporkan permulaan siklus baru, namun tidak melaporkan nilai baru. Tugas tahap ini adalah memulai babak baru dan memberi tahu semua orang tentang nomor uniknya. Angka bulat itu penting, nilainya harus lebih besar dari semua angka pemungutan suara sebelumnya dari semua pemimpin sebelumnya. Karena berkat angka bulat inilah node lain dalam sistem akan memahami seberapa terkini data pemimpinnya. Kemungkinan besar node-node lain sudah mendapatkan hasil pemungutan suara dari putaran selanjutnya dan hanya akan memberi tahu pemimpinnya bahwa dia ketinggalan jaman.
- Fase 1b: Janji. Ketika node akseptor menerima nomor tahap pemungutan suara baru, ada dua hasil yang mungkin terjadi:
- Jumlah n suara baru lebih besar dari jumlah suara sebelumnya yang diikuti oleh akseptor. Kemudian akseptor mengirimkan janji kepada pemimpin bahwa ia tidak akan ikut serta dalam pemungutan suara lagi yang jumlahnya lebih rendah dari n. Jika akseptor telah memilih sesuatu (yaitu, ia telah menerima suatu nilai pada tahap kedua), maka ia melampirkan nilai yang diterima dan jumlah suara yang ia ikuti pada janjinya.
- Jika tidak, jika akseptor sudah mengetahui tentang jumlah suara yang lebih tinggi, ia dapat mengabaikan langkah persiapan dan tidak memberikan tanggapan kepada pemimpin.
- Fase 2a: Terima. Pemimpin perlu menunggu tanggapan dari kuorum (mayoritas node dalam sistem) dan, jika jumlah tanggapan yang diperlukan telah diterima, maka ia memiliki dua opsi untuk pengembangan acara:
- Beberapa akseptor mengirimkan nilai yang sudah mereka pilih. Dalam hal ini, pemimpin memilih nilai dari suara dengan jumlah maksimal. Sebut saja nilai ini x, dan nilai ini akan mengirimkan pesan ke semua node seperti: “Terima (n, x)”, dengan nilai pertama adalah nomor pemungutan suara dari langkah Usulannya sendiri, dan nilai kedua adalah tujuan semua orang berkumpul, yaitu nilai yang sebenarnya kita pilih.
- Jika tidak ada akseptor yang mengirimkan nilai apa pun, tetapi mereka hanya berjanji untuk memberikan suara pada putaran ini, pemimpin dapat mengundang mereka untuk memilih nilai mereka, nilai yang membuat dia menjadi pemimpin sejak awal. Sebut saja y. Ini mengirimkan pesan ke semua node seperti: “Terima (n, y)”, mirip dengan hasil sebelumnya.
- Fase 2b: Diterima. Selanjutnya, node akseptor, setelah menerima pesan “Terima(...)” dari pemimpin, menyetujuinya (mengirim konfirmasi ke semua node bahwa mereka setuju dengan nilai baru) hanya jika mereka belum menjanjikan beberapa (lainnya) ) pemimpin untuk ikut serta dalam pemungutan suara dengan nomor bulat n'> n, jika tidak, mereka akan mengabaikan permintaan konfirmasi.
Jika mayoritas node merespons pemimpin, dan semuanya mengkonfirmasi nilai baru, maka nilai baru dianggap diterima. Hore! Jika mayoritas tidak tercapai atau ada node yang menolak menerima nilai baru, maka semuanya dimulai dari awal.
Beginilah cara kerja algoritma Paxos. Masing-masing tahapan ini memiliki banyak kehalusan, kami praktis tidak mempertimbangkan berbagai jenis kegagalan, masalah banyak pemimpin, dan banyak lagi, namun tujuan artikel ini hanya untuk memperkenalkan pembaca pada dunia komputasi terdistribusi pada tingkat tinggi.
Perlu juga dicatat bahwa Paxos bukan satu-satunya dari jenisnya, ada algoritma lain, misalnya, , tapi ini adalah topik untuk artikel lain.
Tautan ke materi untuk studi lebih lanjut
Level pemula:
- , Preethi Kasireddy, artikel blog di Medium
- , Adi Kancherla, artikel blog di Medium
- , Ittai Abraham, blog
- , Ittai Abraham, artikel blog
Tingkat Leslie Lamport:
- , Fischer, Lynch dan Paterson, makalah penelitian, 1985
- , Leslie Lamport, makalah penelitian, 1998
- , Leslie Lamport, makalah penelitian, 2001
Sumber: www.habr.com