Kucing Schrodinger tanpa kotak: masalah konsensus dalam sistem terdistribusi

Jadi, bayangkan. 5 kucing dikunci di dalam ruangan, dan untuk membangunkan pemiliknya, mereka harus menyetujui ini bersama-sama, karena mereka dapat membuka pintu hanya dengan bersandar padanya lima di antaranya. Jika salah satu kucing adalah kucing Schrodinger, dan kucing lainnya tidak tahu solusinya, muncul pertanyaan: "Bagaimana mereka bisa melakukan ini?"

Dalam artikel ini, saya akan memberi tahu Anda dalam bahasa yang sederhana tentang komponen teoretis dari dunia sistem terdistribusi dan prinsip-prinsip operasi mereka. Dan juga secara dangkal mempertimbangkan gagasan utama yang mendasari Paxos'a.



Ketika pengembang menggunakan infrastruktur cloud, berbagai database, bekerja dalam kelompok dari sejumlah besar node, mereka yakin bahwa data akan lengkap, aman dan selalu dapat diakses. Tapi di mana jaminannya?

Bahkan, jaminan yang kami miliki adalah jaminan dari pemasok. Mereka dijelaskan dalam dokumentasi dengan cara sebagai berikut: "Layanan ini cukup dapat diandalkan, memiliki SLA yang telah ditentukan, jangan khawatir, semuanya akan bekerja secara terdistribusi, seperti yang Anda harapkan."

Kami cenderung percaya pada yang terbaik, karena paman pintar dari perusahaan besar telah meyakinkan kami bahwa semuanya akan baik-baik saja. Kita tidak bertanya pada diri sendiri: mengapa itu bisa berhasil? Apakah ada justifikasi formal untuk operasi yang benar dari sistem seperti itu?

Baru-baru ini saya pergi ke sekolah komputer terdistribusi dan sangat terinspirasi oleh topik ini. Kuliah di sekolah lebih mirip kelas dalam analisis matematika daripada sesuatu yang berkaitan dengan sistem komputer. Tapi beginilah tepatnya algoritma terpenting yang kita gunakan setiap hari tanpa menyadarinya 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 keberadaan algoritma ini dapat dibuktikan dengan pena dan kertas. Namun, dalam praktiknya, algoritma ini digunakan dalam sistem besar yang beroperasi pada sejumlah besar node di awan.

Kami memperkenalkan konsep sistem terdistribusi

Sistem terdistribusi adalah sekelompok komputer (selanjutnya disebut sebagai node) yang dapat bertukar pesan. Setiap node individu adalah beberapa entitas otonom. Sebuah node dapat secara mandiri memproses tugas, tetapi untuk berinteraksi dengan node lain, perlu mengirim dan menerima pesan.

Seberapa spesifik pesan diimplementasikan, protokol mana yang digunakan - ini tidak menarik bagi kita dalam konteks ini. Adalah penting bahwa node dari sistem terdistribusi dapat bertukar data satu sama lain dengan mengirim pesan.

Definisi itu sendiri tidak terlihat sangat rumit, tetapi Anda perlu mempertimbangkan bahwa sistem terdistribusi memiliki sejumlah atribut yang akan penting bagi kami.

Atribut Sistem Terdistribusi

1. Concurrency - kemungkinan acara simultan atau kompetitif dalam sistem. Selain itu, kami akan mempertimbangkan bahwa peristiwa yang terjadi pada dua node berbeda berpotensi bersaing selama kami tidak memiliki urutan kejadian yang jelas dari peristiwa ini. Dan, sebagai suatu peraturan, kami tidak memilikinya.
2. Kurangnya jam global . Kami tidak memiliki urutan acara yang jelas karena kurangnya jam global. Dalam dunia orang biasa, kita terbiasa dengan kenyataan bahwa kita memiliki waktu dan jam sepenuhnya. Semuanya berubah ketika datang ke sistem terdistribusi. Bahkan jam atom ultra-presisi memiliki penyimpangan, dan mungkin ada situasi di mana kita tidak bisa mengatakan yang mana dari dua peristiwa yang terjadi sebelumnya. Karena itu, kami juga tidak dapat mengandalkan waktu.
3. Kegagalan independen node sistem . Ada masalah lain: sesuatu mungkin tidak sesederhana itu karena simpul kita tidak abadi. Hard drive mungkin gagal, mesin virtual di cloud akan reboot, jaringan mungkin berkedip dan pesan akan hilang. Selain itu, situasi mungkin terjadi ketika node bekerja, tetapi pada saat yang sama bekerja melawan sistem. Kelas masalah yang terakhir bahkan menerima nama yang terpisah: masalah para jenderal Bizantium . Contoh paling populer dari sistem terdistribusi dengan masalah seperti itu adalah Blockchain. Tetapi hari ini kita tidak akan mempertimbangkan kelas masalah khusus ini. Kami akan tertarik pada situasi di mana hanya satu node atau lebih yang bisa gagal.
4. Model komunikasi (model pesan) antar node . Kami telah menemukan bahwa node berkomunikasi melalui pesan. Ada dua model perpesanan terkenal: sinkron dan asinkron.

Model komunikasi antar node dalam sistem terdistribusi

Model sinkron - kami tahu pasti bahwa ada batas waktu yang dikenal terbatas untuk pesan yang dijamin untuk menjangkau dari satu simpul ke simpul lainnya. Jika waktu ini telah berlalu, tetapi pesan belum tiba, kita dapat dengan aman mengatakan bahwa simpul telah gagal. Dalam model seperti itu, kami memiliki waktu tunggu yang dapat diprediksi.

Model asinkron - dalam model asinkron, kami percaya bahwa waktu tunggu terbatas, tetapi tidak ada waktu delta setelah itu dapat dijamin bahwa node tidak sesuai pesanan. Yaitu waktu tunggu untuk pesan dari simpul bisa panjang secara sewenang-wenang. Ini adalah definisi penting, dan kami akan membicarakan ini lebih lanjut.

Konsep konsensus dalam sistem terdistribusi

Sebelum secara resmi mendefinisikan konsep konsensus, mari kita pertimbangkan contoh situasi ketika kita membutuhkannya, yaitu, Replikasi Mesin Negara .

Kami memiliki beberapa log yang didistribusikan. Kami ingin itu konsisten dan berisi data identik pada semua node dari sistem terdistribusi. Ketika salah satu node menemukan nilai baru yang akan ditulis ke log, tugasnya adalah menawarkan nilai ini ke semua node lain sehingga log diperbarui pada semua node dan sistem beralih ke keadaan konsisten baru. Adalah penting bahwa node-node tersebut sepakat di antara mereka sendiri: semua node setuju bahwa nilai baru yang diusulkan sudah benar, semua node menerima nilai ini, dan hanya dalam hal ini setiap orang dapat menulis nilai baru ke log.

Dengan kata lain: tidak ada node yang keberatan memiliki informasi yang lebih relevan, dan nilai yang diusulkan salah. Perjanjian antara node dan perjanjian pada nilai tunggal yang benar diterima adalah konsensus dalam sistem terdistribusi. Selanjutnya kita akan berbicara tentang algoritma yang memungkinkan sistem terdistribusi untuk mencapai konsensus dengan jaminan.

Secara lebih formal, kita dapat mendefinisikan algoritma konsensus (atau hanya algoritma konsensus) sebagai beberapa fungsi yang mentransfer sistem terdistribusi dari negara A ke negara B. Selain itu, keadaan ini diterima oleh semua node, dan semua node dapat mengonfirmasinya. Ternyata, tugas ini sama sekali tidak sepele seperti yang terlihat pada pandangan pertama.

Properti Algoritma Konsensus

Algoritma konsensus harus memiliki tiga properti sehingga sistem tetap ada dan memiliki beberapa jenis kemajuan dalam transisi dari negara ke negara:

1. Perjanjian - semua node yang bekerja dengan benar harus memiliki nilai yang sama (dalam artikel properti ini juga ditemukan sebagai properti keamanan). Semua node yang sekarang berfungsi (tidak rusak dan tidak kehilangan kontak dengan yang lain) harus mencapai kesepakatan dan mengambil semacam makna umum akhir.
   
   Penting untuk dipahami di sini bahwa simpul dalam sistem terdistribusi yang kami pertimbangkan ingin disepakati. Artinya, kita sekarang berbicara tentang sistem yang mungkin saja gagal (misalnya, gagal node), tetapi pasti tidak ada node dalam sistem ini yang sengaja bekerja melawan orang lain (tugas para jenderal Bizantium). Karena properti ini, sistem tetap konsisten.
2. Integritas - jika semua simpul yang bekerja dengan benar menawarkan nilai v yang sama , maka setiap simpul yang bekerja dengan benar harus menerima nilai v ini .
3. Termination - semua node yang bekerja dengan benar pada akhirnya akan mengambil beberapa nilai (properti liveness), yang memungkinkan algoritma untuk memiliki kemajuan dalam sistem. Setiap node individu yang bekerja dengan benar harus cepat atau lambat harus menerima nilai akhir dan mengkonfirmasi ini: "Bagi saya, nilai ini benar, saya setuju dengan seluruh sistem."

Contoh Algoritma Konsensus

Sejauh ini, sifat-sifat algoritma mungkin tidak sepenuhnya jelas. Oleh karena itu, kami mengilustrasikan dengan contoh tahap apa algoritma konsensus paling sederhana berjalan dalam sistem dengan model pesan sinkron, di mana semua node berfungsi seperti yang diharapkan, pesan tidak hilang dan tidak ada yang putus (apakah ini benar-benar terjadi?).

1. Semuanya dimulai dengan proposal pernikahan (Propose). Misalkan klien terhubung ke simpul yang disebut "Node 1" dan memulai transaksi, meneruskan nilai baru ke node - O. Mulai sekarang, "Node 1" kita akan memanggil pengusul . Sebagai pengusul, "Node 1" sekarang harus memberi tahu seluruh sistem bahwa ia memiliki data baru, dan itu akan mengirim pesan ke semua node lainnya: "Lihat! Saya mendapat nilai "O" dan saya ingin menuliskannya! Harap konfirmasi bahwa Anda juga akan menulis "O" di log Anda. "
   
   
2. Tahap selanjutnya adalah memilih nilai yang diusulkan (Voting). Untuk apa ini? Mungkin saja node lain menerima informasi yang lebih baru, dan mereka memiliki data pada transaksi yang sama.
   
   
   
   Ketika node "Node 1" mengirim pesannya sendiri, node yang tersisa memeriksa data untuk peristiwa ini dalam log mereka. Jika tidak ada kontradiksi, simpul mengumumkan: “Ya, saya tidak punya data lain tentang acara ini. Nilai "O" adalah informasi terbaru yang pantas kami dapatkan. "
   
   Dalam kasus lain, node dapat menjawab "Node 1": "Dengar! Saya memiliki data terbaru tentang transaksi ini. Bukan "Oh," tetapi sesuatu yang lebih baik. "
   
   Pada tahap pemungutan suara, simpul-simpul itu mengambil keputusan: apakah setiap orang menerima nilai yang sama, atau salah satu dari mereka memberikan suara menentang, yang menunjukkan bahwa ia memiliki data yang lebih baru.
3. Jika putaran pemungutan suara berhasil, dan semua orang mendukung, maka sistem pindah ke tahap baru - penerimaan nilai (Terima). “Node 1” mengumpulkan semua respons dari node dan laporan lain: “Semua orang setuju dengan nilai“ O ”! Sekarang saya secara resmi menyatakan bahwa "O" adalah makna baru kami, sama untuk semua! Tulis diri Anda di buku kecil, jangan lupa. Tulis ke log Anda! "
   
   
4. Node yang tersisa mengirimkan konfirmasi (Diterima) bahwa mereka menuliskan nilai "O", tidak berhasil melakukan sesuatu yang baru selama waktu ini (semacam komitmen dua fase). Setelah peristiwa penting ini, kami percaya bahwa transaksi yang didistribusikan telah selesai.
   

Dengan demikian, algoritma konsensus dalam kasus sederhana terdiri dari empat langkah: mengusulkan, memilih, menerima, konfirmasi penerimaan.

Jika pada beberapa langkah kami tidak dapat mencapai kesepakatan, maka algoritma dimulai kembali, dengan mempertimbangkan informasi yang diberikan oleh node yang menolak untuk mengkonfirmasi nilai yang diusulkan.

Algoritma Konsensus dalam Sistem Asinkron

Sebelum itu, semuanya lancar, karena itu tentang model pesan yang sinkron. Tetapi kita tahu bahwa di dunia modern kita terbiasa melakukan semuanya secara serempak. Bagaimana cara kerja algoritme yang serupa dalam sistem dengan model pesan asinkron, di mana kami percaya bahwa waktu untuk menunggu respons dari sebuah node dapat panjang secara sewenang-wenang (omong-omong, kegagalan sebuah node juga dapat dianggap sebagai contoh ketika sebuah node dapat merespons untuk waktu yang lama secara sewenang-wenang) )

Sekarang kita tahu bagaimana algoritma konsensus pada dasarnya bekerja, pertanyaannya adalah bagi pembaca yang ingin tahu yang telah mencapai titik ini: berapa banyak node dalam sistem N node dengan model pesan asinkron yang dapat gagal sehingga sistem masih dapat mencapai konsensus?

Kita sekarang berbicara tentang teori, tentang matematika. Apa artinya "konsensus tidak dapat dicapai", menerjemahkan dari bahasa matematika ke bahasa kita - teknik? Ini berarti bahwa "tidak selalu dapat dicapai", yaitu ada kasus di mana konsensus tidak dapat dicapai. Dan apa masalahnya?

Ini hanyalah pelanggaran terhadap properti liveness yang dijelaskan di atas. Kami tidak memiliki perjanjian umum, dan sistem tidak dapat maju (tidak dapat menyelesaikan dalam waktu yang terbatas) dalam kasus ketika kami tidak memiliki jawaban dari semua node. Karena dalam sistem asinkron, kami tidak memiliki waktu respons yang dapat diprediksi, dan kami tidak bisa tahu apakah simpulnya down atau hanya membutuhkan waktu lama untuk merespons.

Namun dalam praktiknya, kita bisa menemukan solusinya. Biarkan algoritme kami bekerja untuk waktu yang lama jika terjadi kegagalan (berpotensi gagal tanpa henti). Tetapi dalam kebanyakan situasi, ketika sebagian besar node berfungsi dengan benar, kita akan mengalami kemajuan dalam sistem.

Dalam praktiknya, kita berhadapan dengan model komunikasi yang sebagian sinkron. Sinkronisasi parsial dipahami sebagai berikut: dalam kasus umum, kami memiliki model asinkron, tetapi secara resmi kami memperkenalkan konsep "waktu stabilisasi global" tertentu pada saat tertentu dalam waktu.

Titik waktu ini mungkin tidak datang selama yang Anda inginkan, tetapi suatu hari harus datang. Alarm virtual akan berdering, dan mulai sekarang kita dapat memprediksi delta waktu untuk mencapai pesan mana. Dari saat ini, sistem berubah dari asinkron ke sinkron. Dalam praktiknya, kita berhadapan dengan sistem yang tepat seperti itu.

Algoritma Paxos Memecahkan Masalah Konsensus

Paxos adalah keluarga algoritma yang memecahkan masalah konsensus untuk sistem sinkron parsial, asalkan beberapa node mungkin gagal. Penulis Paxos adalah Leslie Lamport . Dia mengusulkan bukti formal tentang keberadaan dan kebenaran algoritma pada tahun 1989.

Tapi buktinya sama sekali tidak sepele. Publikasi pertama dirilis hanya pada tahun 1998 (33 halaman) dengan deskripsi algoritma. Ternyata, itu sangat sulit untuk dipahami, dan pada tahun 2001 sebuah penjelasan diterbitkan untuk artikel tersebut, yang membutuhkan 14 halaman. Volume publikasi diberikan untuk menunjukkan bahwa, pada kenyataannya, masalah konsensus sama sekali tidak sederhana, dan algoritma seperti itu tunduk pada pekerjaan besar dari orang-orang terpintar.

Sangat menarik bahwa Leslie Lamport sendiri dalam ceramahnya mencatat bahwa dalam artikel-penjelasan kedua ada satu pernyataan, satu baris (tidak menentukan yang mana), yang dapat diartikan berbeda. - Paxos .

Paxos' , . .

Paxos

Paxos . ( ):

1. Proposers ( : ) . , - . . Paxos .
2. Acceptors (Voters) . , . , : ( ) .
3. Learners . , , . , .

.

, N . F . F , , 2F + 1 acceptor'.

, , «», . F + 1 «» , , . , . , .

Paxos

Paxos , :

1. Phase 1a: Prepare . (proposer) : « . . – n. ». , . . , , . , . , , .
2. Phase 1b: Promise . -acceptor' , :
   
   • n , , acceptor. acceptor , , n. acceptor - (.. - ), , .
   • , acceptor , .
3. Phase 2a: Accept . ( ) , , :
   
   • acceptor' , . c . x, : «Accept (n, x)», – Propose, – , .. , , .
   • acceptor' , , , , . y. : «Accept (n, y)», .
4. Phase 2b: Accepted . , -acceptor', «Accept(...)», ( , ) , - () n' > n , .
   
   , , . ! , , .

Paxos. , , , .

, Paxos — , , , Raft , .

«»:

• How Does Distributed Consensus Works? , Preethi Kasireddy, blog article on Medium
• Paxos made simple. For real , Adi Kancherla, blog article on Medium
• Decentralized Thoughts , Ittai Abraham, blog
• Synchrony, Asynchrony and Partial synchrony , Ittai Abraham, blog article

« »:

• Impossibility of Distributed Consensus with One Faulty Process (FLP impossibility) , Fischer, Lynch and Paterson, research paper, 1985
• The Part-Time Parliament , Leslie Lamport, research paper, 1998
• Paxos made simple , Leslie Lamport, research paper, 2001