Jadi, mari kita bayangkan. Terdapat 5 kucing yang dikunci di dalam bilik, dan untuk membangunkan pemiliknya, mereka semua perlu bersetuju mengenai perkara ini di antara mereka, kerana mereka hanya boleh membuka pintu dengan lima daripada mereka bersandar di atasnya. Jika salah satu kucing adalah kucing Schrödinger, dan kucing lain tidak tahu tentang keputusannya, persoalan timbul: "Bagaimana mereka boleh melakukannya?"
Dalam artikel ini, saya akan memberitahu anda secara ringkas tentang komponen teori dunia sistem teragih dan prinsip operasinya. Saya juga akan mengkaji secara cetek idea utama yang mendasari Paxos.
Apabila pembangun menggunakan infrastruktur awan, pelbagai pangkalan data dan bekerja dalam kelompok sejumlah besar nod, mereka yakin bahawa data itu akan lengkap, selamat dan sentiasa tersedia. Tetapi di manakah jaminannya?
Pada asasnya, jaminan yang kami ada adalah jaminan pembekal. Mereka diterangkan dalam dokumentasi seperti berikut: "Perkhidmatan ini agak boleh dipercayai, ia mempunyai SLA yang diberikan, jangan risau, semuanya akan berfungsi secara teragih seperti yang anda jangkakan."
Kami cenderung untuk mempercayai yang terbaik, kerana lelaki pintar dari syarikat besar memberi jaminan kepada kami bahawa semuanya akan baik-baik saja. Kami tidak bertanya soalan: mengapa, sebenarnya, ini boleh berfungsi sama sekali? Adakah terdapat sebarang justifikasi rasmi untuk operasi yang betul bagi sistem sedemikian?
Saya baru-baru ini pergi ke dan sangat terinspirasi dengan topik ini. Kuliah di sekolah lebih seperti kelas kalkulus daripada sesuatu yang berkaitan dengan sistem komputer. Tetapi ini betul-betul bagaimana algoritma paling penting yang kami gunakan setiap hari, tanpa mengetahuinya, telah dibuktikan pada satu masa.
Kebanyakan sistem teragih moden menggunakan algoritma konsensus Paxos dan pelbagai pengubahsuaiannya. Perkara yang paling menarik ialah kesahihan dan, pada dasarnya, kemungkinan kewujudan algoritma ini boleh dibuktikan hanya dengan pen dan kertas. Dalam amalan, algoritma digunakan dalam sistem besar yang berjalan pada sejumlah besar nod di awan.
Ilustrasi ringan tentang apa yang akan dibincangkan seterusnya: tugas dua jeneralMari kita lihat untuk memanaskan badan .
Kami mempunyai dua tentera - merah dan putih. Tentera putih berpangkalan di bandar yang dikepung. Pasukan merah yang diketuai oleh jeneral A1 dan A2 terletak di dua sisi bandar. Tugas si berambut merah adalah menyerang kota putih dan menang. Walau bagaimanapun, tentera setiap jeneral merah secara individu adalah lebih kecil daripada tentera putih.
Syarat kemenangan untuk yang merah: kedua-dua jeneral mesti menyerang pada masa yang sama untuk mempunyai kelebihan berangka berbanding pasukan putih. Untuk melakukan ini, jeneral A1 dan A2 perlu mencapai persetujuan antara satu sama lain. Jika semua orang menyerang secara berasingan, si rambut merah akan kalah.
Untuk mencapai persetujuan, jeneral A1 dan A2 boleh menghantar utusan antara satu sama lain melalui wilayah kota putih. Utusan itu mungkin berjaya mencapai jeneral bersekutu atau mungkin dipintas oleh musuh. Soalan: adakah terdapat urutan komunikasi sedemikian antara jeneral berambut merah (urutan menghantar utusan dari A1 ke A2 dan sebaliknya dari A2 ke A1), di mana mereka dijamin bersetuju untuk menyerang pada jam X. Di sini, jaminan bermakna kedua-dua jeneral akan mendapat pengesahan yang jelas bahawa sekutu (jeneral lain) pasti akan menyerang pada masa yang ditetapkan X.
Katakan A1 menghantar utusan ke A2 dengan mesej: "Mari kita serang hari ini pada tengah malam!" Jeneral A1 tidak boleh menyerang tanpa pengesahan daripada Jeneral A2. Jika utusan dari A1 telah tiba, maka Jeneral A2 menghantar pengesahan dengan mesej: "Ya, mari kita bunuh orang kulit putih hari ini." Tetapi kini Jeneral A2 tidak tahu sama ada utusannya telah tiba atau tidak, dia tidak mempunyai jaminan sama ada serangan itu akan berlaku serentak. Kini General A2 lagi memerlukan pengesahan.
Menghuraikan komunikasi mereka selanjutnya mendedahkan perkara berikut: tidak kira berapa banyak kitaran mesej yang ada, tidak ada cara untuk menjamin bahawa kedua-dua jeneral telah dimaklumkan bahawa mesej mereka telah diterima (dengan mengandaikan bahawa salah satu utusan boleh dipintas).
Masalah Dua Jeneral ialah ilustrasi hebat sistem teragih yang sangat mudah di mana terdapat dua nod dengan komunikasi yang tidak boleh dipercayai. Ini bermakna kami tidak mempunyai jaminan 100% bahawa ia disegerakkan. Masalah yang sama dibincangkan hanya pada skala yang lebih besar kemudian dalam artikel.
Kami memperkenalkan konsep sistem teragih
Sistem teragih ialah sekumpulan komputer (selepas ini kita akan memanggilnya nod) yang boleh bertukar-tukar mesej. Setiap nod individu ialah sejenis entiti autonomi. Nod boleh memproses tugas dengan sendirinya, tetapi untuk berkomunikasi dengan nod lain, ia perlu menghantar dan menerima mesej.
Bagaimana sebenarnya mesej dilaksanakan, protokol apa yang digunakan - ini tidak menarik minat kami dalam konteks ini. Adalah penting bahawa nod sistem teragih boleh bertukar-tukar data antara satu sama lain dengan menghantar mesej.
Definisi itu sendiri tidak kelihatan sangat rumit, tetapi kita mesti mengambil kira bahawa sistem teragih mempunyai beberapa atribut yang akan menjadi penting kepada kita.
Atribut sistem teragih
- Penyelesaian – kemungkinan kejadian serentak atau serentak berlaku dalam sistem. Selain itu, kami akan menganggap peristiwa yang berlaku pada dua nod berbeza berpotensi serentak selagi kami tidak mempunyai susunan kejadian yang jelas bagi peristiwa ini. Tetapi, sebagai peraturan, kami tidak memilikinya.
- Tiada jam global. Kami tidak mempunyai susunan acara yang jelas kerana kekurangan jam global. Dalam dunia manusia biasa, kita sudah terbiasa dengan fakta bahawa kita mempunyai jam dan masa secara mutlak. Segala-galanya berubah apabila ia datang kepada sistem yang diedarkan. Malah jam atom ultra-tepat telah hanyut, dan mungkin terdapat situasi di mana kita tidak dapat memberitahu yang mana antara dua peristiwa berlaku dahulu. Oleh itu, kita juga tidak boleh bergantung pada masa.
- Kegagalan bebas nod sistem. Terdapat satu lagi masalah: sesuatu boleh berlaku hanya kerana nod kami tidak kekal selama-lamanya. Pemacu keras mungkin gagal, mesin maya dalam awan mungkin but semula, rangkaian mungkin berkelip dan mesej akan hilang. Selain itu, mungkin terdapat situasi di mana nod berfungsi, tetapi pada masa yang sama berfungsi melawan sistem. Kelas terakhir masalah walaupun menerima nama berasingan: masalah . Contoh sistem teragih yang paling popular dengan masalah ini ialah Blockchain. Tetapi hari ini kita tidak akan menganggap kelas masalah istimewa ini. Kami akan berminat dengan situasi di mana hanya satu atau lebih nod mungkin gagal.
- Model komunikasi (model pemesejan) antara nod. Kami telah menetapkan bahawa nod berkomunikasi dengan bertukar-tukar mesej. Terdapat dua model pemesejan yang terkenal: segerak dan tak segerak.
Model komunikasi antara nod dalam sistem teragih
Model segerak – kita tahu pasti bahawa terdapat delta masa yang diketahui terhingga semasa mesej dijamin untuk sampai dari satu nod ke nod yang lain. Jika masa ini telah berlalu dan mesej belum tiba, kita boleh mengatakan dengan selamat bahawa nod telah gagal. Dalam model ini kita mempunyai masa menunggu yang boleh diramal.
Model tak segerak – dalam model tak segerak kami menganggap bahawa masa menunggu adalah terhad, tetapi tiada delta masa sedemikian selepas itu kami boleh menjamin bahawa nod telah gagal. Itu. Masa menunggu untuk mesej daripada nod boleh sewenang-wenangnya panjang. Ini adalah definisi penting, dan kita akan membincangkannya dengan lebih lanjut.
Konsep konsensus dalam sistem teragih
Sebelum mentakrifkan secara rasmi konsep konsensus, mari kita pertimbangkan contoh situasi di mana kita memerlukannya, iaitu - Replikasi Mesin Negeri.
Kami mempunyai beberapa log yang diedarkan. Kami ingin ia konsisten dan mengandungi data yang sama pada semua nod sistem yang diedarkan. Apabila salah satu nod mempelajari nilai baharu yang akan ditulis pada log, tugasnya adalah untuk menawarkan nilai ini kepada semua nod lain supaya log dikemas kini pada semua nod dan sistem bergerak ke keadaan konsisten baharu. Dalam kes ini, adalah penting bahawa nod bersetuju antara mereka sendiri: semua nod bersetuju bahawa nilai baharu yang dicadangkan adalah betul, semua nod menerima nilai ini, dan hanya dalam kes ini semua orang boleh menulis nilai baharu pada log.
Dalam erti kata lain: tiada nod yang membantah bahawa ia mempunyai maklumat yang lebih berkaitan, dan nilai yang dicadangkan adalah salah. Perjanjian antara nod dan perjanjian pada satu nilai yang betul diterima adalah konsensus dalam sistem teragih. Seterusnya, kita akan bercakap tentang algoritma yang membolehkan sistem yang diedarkan dijamin untuk mencapai konsensus.
Secara lebih formal, kita boleh mentakrifkan algoritma konsensus (atau ringkasnya algoritma konsensus) sebagai fungsi tertentu yang memindahkan sistem teragih dari keadaan A ke keadaan B. Selain itu, keadaan ini diterima oleh semua nod, dan semua nod boleh mengesahkannya. Ternyata, tugas ini sama sekali tidak sepele seperti yang dilihat pada pandangan pertama.
Sifat Algoritma Konsensus
Algoritma konsensus mesti mempunyai tiga sifat agar sistem terus wujud dan mempunyai sedikit kemajuan dalam bergerak dari negeri ke negeri:
- Perjanjian – semua nod yang beroperasi dengan betul mesti mengambil nilai yang sama (dalam artikel harta ini juga dirujuk sebagai harta keselamatan). Semua nod yang sedang berfungsi (tidak gagal atau terputus hubungan dengan yang lain) mesti mencapai persetujuan dan menerima beberapa nilai bersama akhir.
Adalah penting untuk memahami di sini bahawa nod dalam sistem teragih yang kami pertimbangkan mahu bersetuju. Iaitu, kita kini bercakap tentang sistem di mana sesuatu boleh gagal (contohnya, beberapa nod gagal), tetapi dalam sistem ini pasti tidak ada nod yang sengaja bekerja melawan yang lain (tugas jeneral Byzantine). Disebabkan oleh sifat ini, sistem kekal konsisten.
- Integriti — jika semua nod yang berfungsi dengan betul menawarkan nilai yang sama v, yang bermaksud setiap nod yang beroperasi dengan betul mesti menerima nilai ini v.
- Penamatan – semua nod yang beroperasi dengan betul akhirnya akan mengambil nilai tertentu (sifat liveness), yang membolehkan algoritma membuat kemajuan dalam sistem. Setiap individu yang beroperasi dengan betul nod mesti lambat laun menerima nilai akhir dan mengesahkannya: "Bagi saya, nilai ini adalah benar, saya bersetuju dengan keseluruhan sistem."
Contoh cara algoritma konsensus berfungsi
Walaupun sifat algoritma mungkin tidak jelas sepenuhnya. Oleh itu, kami akan menggambarkan dengan contoh apakah peringkat yang dilalui oleh algoritma konsensus paling mudah dalam sistem dengan model pemesejan segerak, di mana semua nod berfungsi seperti yang diharapkan, mesej tidak hilang dan tiada apa-apa yang pecah (adakah ini benar-benar berlaku?).
- Semuanya bermula dengan peminangan (Cadang). Mari kita anggap bahawa pelanggan disambungkan ke nod yang dipanggil "Nod 1" dan memulakan transaksi, menghantar nilai baharu kepada nod - O. Mulai sekarang, kita akan memanggil "Nod 1" tawaran. Sebagai pencadang, "Nod 1" kini mesti memberitahu seluruh sistem bahawa ia mempunyai data baharu, dan ia menghantar mesej kepada semua nod lain: "Lihat! Maksud "O" datang kepada saya dan saya mahu menulisnya! Sila sahkan bahawa anda juga akan merekodkan "O" dalam log anda."
- Peringkat seterusnya adalah mengundi untuk nilai yang dicadangkan (Pengundian). Untuk apa itu? Ia mungkin berlaku bahawa nod lain telah menerima lebih banyak maklumat terkini, dan mereka mempunyai data pada transaksi yang sama.
Apabila nod "Nod 1" menghantar cadangannya, nod lain menyemak log mereka untuk data tentang acara ini. Jika tiada percanggahan, nod mengumumkan: "Ya, saya tidak mempunyai data lain untuk acara ini. Nilai "O" ialah maklumat terkini yang patut kami terima."Dalam sebarang kes lain, nod boleh bertindak balas kepada "Nod 1": "Dengar! Saya mempunyai lebih banyak data terkini tentang transaksi ini. Bukan 'O', tetapi sesuatu yang lebih baik."
Pada peringkat pengundian, nod membuat keputusan: sama ada mereka semua menerima nilai yang sama, atau salah seorang daripada mereka mengundi menentang, menunjukkan bahawa dia mempunyai data yang lebih terkini.
- Jika pusingan pengundian berjaya dan semua orang memihak, maka sistem bergerak ke peringkat baharu - Menerima nilai. "Nod 1" mengumpul semua respons daripada nod lain dan melaporkan: "Semua orang bersetuju dengan nilai "O"! Sekarang saya secara rasmi mengisytiharkan bahawa "O" ialah makna baharu kami, sama untuk semua orang! Tulis dalam buku kecil anda, jangan lupa. Tulis dalam log anda!”
- Nod yang selebihnya menghantar pengesahan (Diterima) bahawa mereka telah mencatatkan nilai "O"; tiada yang baharu telah tiba pada masa ini (sejenis komit dua fasa). Selepas peristiwa penting ini, kami menganggap bahawa transaksi yang diedarkan telah selesai.
Oleh itu, algoritma konsensus dalam kes mudah terdiri daripada empat langkah: mencadangkan, mengundi (mengundi), menerima (menerima), mengesahkan penerimaan (diterima).
Jika pada beberapa langkah kami tidak dapat mencapai persetujuan, maka algoritma bermula semula, dengan mengambil kira maklumat yang diberikan oleh nod yang enggan mengesahkan nilai yang dicadangkan.
Algoritma konsensus dalam sistem tak segerak
Sebelum ini, semuanya lancar, kerana kami bercakap tentang model pemesejan segerak. Tetapi kita tahu bahawa dalam dunia moden kita sudah biasa melakukan segala-galanya secara tidak segerak. Bagaimanakah algoritma serupa berfungsi dalam sistem dengan model pemesejan tak segerak, di mana kami percaya bahawa masa menunggu untuk respons daripada nod boleh sewenang-wenangnya panjang (dengan cara ini, kegagalan nod juga boleh dianggap sebagai contoh apabila nod boleh bertindak balas untuk masa yang lama dengan sewenang-wenangnya).
Sekarang kita tahu bagaimana algoritma konsensus berfungsi pada dasarnya, soalan untuk pembaca yang ingin tahu yang telah mencapai sejauh ini: berapa banyak nod dalam sistem nod N dengan model mesej tak segerak boleh gagal supaya sistem masih boleh mencapai konsensus?
Jawapan dan justifikasi yang betul adalah di sebalik spoiler.Jawapan yang betul ialah: 0. Jika walaupun satu nod dalam sistem tak segerak gagal, sistem tidak akan dapat mencapai konsensus. Kenyataan ini dibuktikan dalam teorem FLP, yang terkenal dalam kalangan tertentu (1985, Fischer, Lynch, Paterson, pautan ke asal pada akhir artikel): "Kemustahilan untuk mencapai konsensus teragih jika sekurang-kurangnya satu nod gagal .”
Lelaki, kemudian kita mempunyai masalah, kita sudah biasa dengan segala-galanya tidak segerak. Dan inilah dia. Bagaimana untuk meneruskan hidup?
Kami hanya bercakap tentang teori, tentang matematik. Apakah yang dimaksudkan dengan "konsensus tidak boleh dicapai", menterjemah daripada bahasa matematik ke bahasa kita - kejuruteraan? Ini bermakna bahawa "tidak boleh selalu dicapai", i.e. Terdapat kes di mana konsensus tidak dapat dicapai. Apakah jenis kes ini?
Ini betul-betul pelanggaran harta hidup yang diterangkan di atas. Kami tidak mempunyai perjanjian bersama, dan sistem tidak boleh mempunyai kemajuan (tidak dapat diselesaikan dalam masa yang terhad) dalam kes di mana kami tidak mempunyai respons daripada semua nod. Kerana dalam sistem tak segerak kita tidak mempunyai masa tindak balas yang boleh diramal dan kita tidak dapat mengetahui sama ada nod telah ranap atau hanya mengambil masa yang lama untuk bertindak balas.
Tetapi dalam amalan kita boleh mencari penyelesaian. Biarkan algoritma kami dapat berfungsi untuk masa yang lama sekiranya berlaku kegagalan (berpotensi ia boleh berfungsi selama-lamanya). Tetapi dalam kebanyakan situasi, apabila kebanyakan nod berfungsi dengan betul, kita akan mempunyai kemajuan dalam sistem.
Dalam amalan, kami berurusan dengan model komunikasi separa segerak. Penyegerakan separa difahami seperti berikut: dalam kes umum, kami mempunyai model tak segerak, tetapi konsep tertentu "masa penstabilan global" pada titik masa tertentu diperkenalkan secara rasmi.
Detik masa ini mungkin tidak akan datang untuk jangka masa yang panjang, tetapi ia mesti datang satu hari nanti. Jam penggera maya akan berdering, dan mulai saat itu kita boleh meramalkan delta masa yang mesej akan tiba. Mulai saat ini, sistem bertukar daripada tak segerak kepada segerak. Dalam amalan, kami berurusan dengan sistem sedemikian dengan tepat.
Algoritma Paxos menyelesaikan masalah konsensus
ialah keluarga algoritma yang menyelesaikan masalah konsensus untuk sistem separa segerak, tertakluk kepada kemungkinan beberapa nod mungkin gagal. Pengarang Paxos ialah . Beliau mencadangkan bukti rasmi tentang kewujudan dan ketepatan algoritma pada tahun 1989.
Tetapi buktinya ternyata jauh dari kata remeh. Penerbitan pertama dikeluarkan hanya pada tahun 1998 (33 halaman) yang menerangkan algoritma. Ternyata, ia sangat sukar untuk difahami, dan pada tahun 2001 penjelasan artikel itu diterbitkan, yang mengambil 14 halaman. Jumlah penerbitan diberikan untuk menunjukkan bahawa sebenarnya masalah konsensus tidak sama sekali mudah, dan di sebalik algoritma sedemikian terdapat sejumlah besar kerja oleh orang yang paling bijak.
Adalah menarik bahawa Leslie Lamport sendiri menyatakan dalam kuliahnya bahawa dalam artikel penjelasan kedua terdapat satu pernyataan, satu baris (dia tidak menyatakan yang mana satu), yang boleh ditafsirkan dengan cara yang berbeza. Dan kerana ini, sebilangan besar pelaksanaan Paxos moden tidak berfungsi dengan betul sepenuhnya.
Analisis terperinci tentang kerja Paxos memerlukan lebih daripada satu artikel, jadi saya akan cuba menyampaikan secara ringkas idea utama algoritma. Dalam pautan di penghujung artikel saya, anda akan menemui bahan untuk menyelam lebih lanjut ke dalam topik ini.
Peranan di Paxos
Algoritma Paxos mempunyai konsep peranan. Mari kita pertimbangkan tiga yang utama (terdapat pengubahsuaian dengan peranan tambahan):
- Pencadang (istilah juga boleh digunakan: pemimpin atau penyelaras). Ini adalah mereka yang belajar tentang beberapa nilai baharu daripada pengguna dan mengambil peranan sebagai pemimpin. Tugas mereka adalah untuk melancarkan satu pusingan cadangan untuk nilai baharu dan menyelaraskan tindakan selanjutnya nod. Selain itu, Paxos membenarkan kehadiran beberapa pemimpin dalam situasi tertentu.
- Penerima (Pengundi). Ini adalah nod yang mengundi untuk menerima atau menolak nilai tertentu. Peranan mereka sangat penting, kerana keputusan bergantung kepada mereka: keadaan sistem yang akan (atau tidak) pergi selepas peringkat seterusnya algoritma konsensus.
- Pelajar. Nod yang hanya menerima dan menulis nilai baru yang diterima apabila keadaan sistem telah berubah. Mereka tidak membuat keputusan, mereka hanya menerima data dan boleh memberikannya kepada pengguna akhir.
Satu nod boleh menggabungkan beberapa peranan dalam situasi yang berbeza.
Konsep kuorum
Kami menganggap bahawa kami mempunyai sistem N nod Dan daripada mereka maksimum F nod mungkin gagal. Jika nod F gagal, maka kita mesti mempunyai sekurang-kurangnya 2F+1 nod penerima.
Ini adalah perlu supaya kita sentiasa mempunyai majoriti, walaupun dalam keadaan paling teruk, nod "baik" yang berfungsi dengan betul. Itu dia F+1 nod "baik" yang bersetuju, dan nilai akhir akan diterima. Jika tidak, mungkin terdapat situasi di mana kumpulan tempatan kita yang berbeza mengambil makna yang berbeza dan tidak boleh bersetuju sesama mereka. Oleh itu, kita memerlukan majoriti mutlak untuk memenangi undi.
Idea umum bagaimana algoritma konsensus Paxos berfungsi
Algoritma Paxos melibatkan dua fasa besar, yang seterusnya dibahagikan kepada dua langkah setiap satu:
- Fasa 1a: Sediakan. Semasa fasa penyediaan, ketua (pencadang) memaklumkan semua nod: “Kami memulakan fasa pengundian baharu. Kita ada pusingan baru. Nombor pusingan ini ialah n. Sekarang kita akan mula mengundi." Buat masa ini, ia hanya melaporkan permulaan kitaran baharu, tetapi tidak melaporkan nilai baharu. Tugas peringkat ini adalah untuk memulakan pusingan baharu dan memaklumkan semua nombor uniknya. Nombor bulat itu penting, ia mestilah nilai yang lebih besar daripada semua nombor undian sebelumnya daripada semua pemimpin terdahulu. Kerana ia adalah terima kasih kepada nombor bulat bahawa nod lain dalam sistem akan memahami betapa terkini data pemimpin. Ada kemungkinan bahawa nod lain sudah mempunyai keputusan pengundian dari pusingan yang lebih lama dan hanya akan memberitahu ketua bahawa dia ketinggalan zaman.
- Fasa 1b: Janji. Apabila nod penerima menerima bilangan peringkat pengundian baharu, dua keputusan adalah mungkin:
- Bilangan n undian baharu adalah lebih besar daripada bilangan undian sebelumnya yang mana penerima mengambil bahagian. Kemudian penerima menghantar janji kepada pemimpin bahawa ia tidak akan mengambil bahagian dalam sebarang undian lagi dengan nombor lebih rendah daripada n. Jika penerima telah mengundi untuk sesuatu (iaitu, ia telah menerima beberapa nilai dalam fasa kedua), maka ia melampirkan nilai yang diterima dan bilangan undi di mana ia mengambil bahagian pada janjinya.
- Jika tidak, jika penerima sudah mengetahui tentang undi yang lebih tinggi, ia boleh mengabaikan langkah persediaan dan tidak memberi respons kepada pemimpin.
- Fasa 2a: Terima. Pemimpin perlu menunggu jawapan daripada kuorum (majoriti nod dalam sistem) dan, jika bilangan respons yang diperlukan diterima, maka dia mempunyai dua pilihan untuk pembangunan acara:
- Beberapa penerima menghantar nilai yang telah mereka undi. Dalam kes ini, pemimpin memilih nilai daripada undian dengan bilangan maksimum. Mari kita panggil nilai ini x, dan ia menghantar mesej kepada semua nod seperti: "Terima (n, x)", di mana nilai pertama ialah nombor undian daripada langkah Cadangnya sendiri, dan nilai kedua ialah tujuan semua orang berkumpul, i.e. nilai yang sebenarnya kita undi.
- Jika tiada penerima menghantar apa-apa nilai, tetapi mereka hanya berjanji untuk mengundi dalam pusingan ini, pemimpin boleh menjemput mereka untuk mengundi nilai mereka, nilai yang dia menjadi pemimpin pada mulanya. Mari kita panggil y. Ia menghantar mesej kepada semua nod seperti: "Terima (n, y)", serupa dengan hasil sebelumnya.
- Fasa 2b: Diterima. Selanjutnya, nod penerima, apabila menerima mesej "Terima(...)" daripada ketua, bersetuju dengannya (hantar pengesahan kepada semua nod bahawa mereka bersetuju dengan nilai baharu) hanya jika mereka tidak menjanjikan beberapa (yang lain) ) pemimpin untuk mengambil bahagian dalam pengundian dengan nombor bulat n' > n, jika tidak, mereka mengabaikan permintaan pengesahan.
Jika majoriti nod bertindak balas kepada ketua, dan kesemuanya mengesahkan nilai baharu, maka nilai baharu itu dianggap diterima. Hooray! Jika majoriti tidak tercapai atau terdapat nod yang enggan menerima nilai baru, maka semuanya bermula semula.
Beginilah cara algoritma Paxos berfungsi. Setiap peringkat ini mempunyai banyak kehalusan, kami secara praktikal tidak menganggap pelbagai jenis kegagalan, masalah berbilang pemimpin dan banyak lagi, tetapi tujuan artikel ini hanya untuk memperkenalkan pembaca kepada dunia pengkomputeran teragih pada tahap yang tinggi.
Perlu juga diperhatikan bahawa Paxos bukan satu-satunya seumpamanya, terdapat algoritma lain, sebagai contoh, , tetapi ini adalah topik untuk artikel lain.
Pautan kepada bahan untuk kajian lanjut
Tahap pemula:
- , Preethi Kasireddy, artikel blog di Medium
- , Adi Kancherla, artikel blog di Medium
- , Ittai Abraham, blog
- , Ittai Abraham, artikel blog
Tahap Leslie Laport:
- , Fischer, Lynch dan Paterson, kertas penyelidikan, 1985
- , Leslie Lamport, kertas penyelidikan, 1998
- , Leslie Lamport, kertas penyelidikan, 2001
Sumber: www.habr.com