Algoritma konsensus yang sistem teragih mesti tahu: Rakit

1. Gambaran Keseluruhan Rakit

​​Raft 算法​​​​ adalah pilihan pertama untuk pembangunan sistem teragih​共识算法​​. Contohnya, Etcd dan Consul popular sekarang.

Jika ​​掌握​​​algoritma ini dilaksanakan, ia boleh menjadi lebih mudah untuk mengendalikan ​​容错​​​ dan ​​一致性​​ keperluan kebanyakan senario. Contohnya, sistem konfigurasi teragih, storan NoSQL teragih, dsb. dengan mudah boleh menembusi had mesin tunggal sistem.

Algoritma Raft mencapai konsensus pada siri nilai dan ketekalan log setiap nod melalui semua kaedah berdasarkan ketua.

2. Peranan Rakit

2.1 Peranan

Pengikut : ​​普通群众​​, secara senyap menerima mesej daripada pemimpin Apabila mesej degupan jantung pemimpin tamat, dia akan mengambil inisiatif untuk bangkit dan mengesyorkan dirinya sebagai calon.

Calon (Calon) : ​​候选人​​ akan meminta mesej RPC undian daripada nod lain dan memberitahu nod lain untuk mengundi Jika ia memenangi majoriti undian mengundi, ia akan dinaikkan pangkat kepada pemimpin yang.

Pemimpin : ​​霸道总裁​​, semuanya terpulang kepada saya. Proses permintaan tulis, urus replikasi log dan hantar maklumat degupan jantung secara berterusan untuk memberitahu nod lain bahawa "Saya ketua, saya masih hidup dan anda tidak mahu" memulakan pilihan raya baharu tanpa perlu mencari pemimpin baharu untuk menggantikan saya.

Seperti yang ditunjukkan dalam rajah di bawah, tiga jenis tokoh digunakan untuk mewakili pengikut, calon dan pemimpin.

Peranan

3. Sistem Nod Tunggal

3.1 Pelayan Pangkalan Data

Sekarang mari bayangkan, Di sana ialah sistem nod tunggal Nod ini berfungsi sebagai pelayan pangkalan data dan menyimpan nilai X.

Pelayan Pangkalan Data

3.2 Pelanggan

Bulatan pepejal hijau di sebelah kiri ialah klien, dan bulatan pepejal biru di sebelah kanan ialah Nod a (Nod a ). Penggal mewakili tempoh jawatan, yang akan dibincangkan kemudian.

Pelanggan

3.3 Pelanggan menghantar data ke pelayan

Pelanggan menghantar data ke satu- pelayan nod Operasi kemas kini menetapkan nilai yang disimpan dalam pangkalan data kepada 8. Dalam persekitaran yang berdiri sendiri (nod pelayan tunggal), nilai yang diperoleh klien daripada pelayan juga adalah 8. Konsistensi sangat mudah untuk dipastikan.

Pelanggan menghantar data ke pelayan

3.4 Bagaimanakah berbilang nod memastikan konsistensi?

Tetapi jika terdapat berbilang nod pelayan, bagaimana untuk memastikan konsistensi? Sebagai contoh, terdapat tiga nod: a, b, c. Seperti yang ditunjukkan di bawah. Ketiga-tiga nod ini membentuk kluster pangkalan data. Apabila pelanggan melakukan operasi kemas kini pada ketiga-tiga nod ini, bagaimana untuk memastikan bahawa nilai yang disimpan dalam tiga nod adalah konsisten? Ini adalah isu konsistensi yang diedarkan. Algoritma Raft ada di sini untuk menyelesaikan masalah ini. Sudah tentu, terdapat protokol lain yang juga boleh menjamin ini Artikel ini hanya memfokuskan pada algoritma Raft.

Dalam kluster berbilang nod, dalam keadaan tidak normal seperti kegagalan nod, ralat partition, dsb., bagaimanakah algoritma Raft memastikan bahawa hanya terdapat satu ketua dalam kluster di masa yang sama? Mari kita mulakan untuk menerangkan proses pemilihan pemimpin oleh algoritma Raft.

4. Proses pemilihan pemimpin

4.1 Keadaan awal

Dalam keadaan awal, semua nod dalam kelompok adalah pengikut status.

Seperti yang ditunjukkan dalam rajah di bawah, terdapat tiga nod (Nod) a, b, dan c, dan istilah (Terma) ialah 0.

Keadaan awal

4.2 Menjadi calon

Algoritma Raft melaksanakan ciri tamat masa rawak, setiap satu masa Selang masa tamat untuk setiap nod menunggu maklumat degupan jantung daripada nod pendahulu adalah rawak. Sebagai contoh, selang masa tamat menunggu nod A ialah 150 ms, nod B ialah 200 ms, dan nod C ialah 300 ms. Kemudian tamat masa dahulu, ia tamat masa kerana ia tidak menunggu maklumat degupan jantung pemimpin. Seperti yang ditunjukkan dalam rajah di bawah, pemasa tamat masa untuk tiga nod mula berjalan.

Tempoh tamat masa

Apabila tempoh tamat masa nod A tamat, nod A menjadi calon dan meningkatkan nombor jangka masanya dikemas kini daripada 0 kepada 1. Dan hantar undi untuk diri saya sendiri.

• Nod A: Penggal = 1, Kiraan Undi = 1.
• Nod B: Jangka = 0.
• Nod C: Jangka = 0.

Jadi calon

4.3 Undi

Mari kita lihat bagaimana calon menjadi pemimpin .

Pemilihan pemimpin

• Langkah 1: Selepas nod A menjadi calon, hantar permintaan untuk mengundi RPC kepada yang lain mesej nod dan minta mereka memilih diri mereka sebagai pemimpin.
• Langkah 2: Selepas menerima maklumat permintaan undian yang dihantar oleh nod A, nod B dan nod C akan mengundi tanpa mengundi dalam tempoh bernombor 1. Undian dibuang ke nod A dan nodnya bilangan penggal sendiri ditambah.
• Langkah ketiga: Nod A menerima 3 undi dan menerima undian daripada majoriti nod, menjadi calon daripada calon kepada pemimpin baharu dalam penggal ini.
• Langkah 4: Nod A, sebagai ketua, menghantar maklumat degupan jantung ke nod B dan nod C pada selang masa tetap, memberitahu nod B dan C bahawa saya adalah ketua dan mengatur orang lain untuk mengikuti untuk memulakan pilihanraya baru.
• Langkah 5: Nod B dan nod C menghantar maklumat respons ke nod A, memberitahu nod A bahawa saya normal.

4.4 Istilah

Perkataan Inggeris ialah term, dan leaders have tenure.

• Autokenaikan: Selepas pengikut tamat masa menunggu maklumat degupan jantung pemimpin, ia mengesyorkan dirinya sebagai calon dan akan menambah bilangan penggalnya seperti yang ditunjukkan dalam rajah di atas, istilah itu nod A ialah 0. Apabila mencalonkan diri anda sebagai calon, istilah nombor meningkat kepada 1.
• Kemas kini kepada nilai yang lebih besar: Apabila nod mendapati bahawa nombor sebutannya lebih kecil daripada nod lain, ia akan mengemas kini kepada nilai nombor yang lebih besar. Contohnya, istilah nod A ialah 1 dan meminta undian Mesej undian mengandungi nombor istilah nod A, dan nombornya ialah 1. Selepas nod B menerima mesej, ia akan mengemas kini nombor istilahnya kepada 1.
• Berbalik kepada status pengikut: Jika calon atau pemimpin mendapati bahawa nombor istilahnya lebih kecil daripada nod lain, ia akan segera kembali kepada status pengikut. Senario ini berlaku apabila ralat partition dipulihkan dan pemimpin dengan istilah 3 menerima mesej degupan jantung dengan istilah 4, maka yang pertama akan segera kembali ke keadaan pengikut.
• Mesej penolakan: Jika nod menerima permintaan untuk nilai nombor jangka yang lebih kecil, ia akan menolak permintaan secara langsung Contohnya, nod A dengan nombor 6 menerima nombor Nod Permintaan B mengundi untuk 5 mesej RPC, kemudian nod A akan menolak mesej tersebut.

4.5 Peraturan Pilihan Raya

• Dalam sesuatu penggal, pemimpin akan sentiasa menjadi ketua sehingga berlaku masalah (seperti downtime) atau masalah rangkaian (kelewatan), nod lain memulakan pusingan pilihan raya baharu.
• Dalam pilihan raya, setiap nod pelayan akan membuang paling banyak satu undi untuk nombor penggal dan ia akan hilang selepas undian selesai.

4.6 Kebanyakan

Dengan mengandaikan gugusan terdiri daripada N nod, maka majoriti sekurang-kurangnya N/2+1. Sebagai contoh: untuk gugusan 3 nod, kebanyakannya adalah 2.

4.7 Tempoh Denyutan Jantung

Untuk mengelakkan berbilang nod daripada memulakan pengundian pada masa yang sama, setiap nod akan diberikan tamat masa pilihan raya rawak. Pada masa ini, nod tidak boleh menjadi calon dan hanya boleh menunggu sehingga tamat masa. Contohnya, dalam contoh di atas, nod A tamat masa dahulu dan menjadi calon dahulu. Dengan reka bentuk yang bijak ini, dalam kebanyakan kes hanya satu nod pelayan memulakan pilihan raya terlebih dahulu dan bukannya memulakan pilihan raya pada masa yang sama, yang mengurangkan bilangan kegagalan pilihan raya akibat pembahagian undi.

Menjadi calon

5. pusingan baru pilihan raya. Seperti yang ditunjukkan dalam rajah di bawah, jika nod pemimpin A gagal, nod B dan nod C akan memilih semula ketua.

Kegagalan Pemimpin

Langkah 1

: Nod A
• kegagalan berlaku, nod B Dan nod C tidak menerima maklumat degupan jantung daripada nod pendahulu A, dan masa menunggu tamat. Langkah kedua
: Nod C tamat masa dahulu, dan nod C menjadi
• calon. Langkah 3
: Nod C memulakan permintaan untuk maklumat undian ke nod A dan nod B.
• Langkah 4
: Nod C membalas undian dan mengundi C, manakala nod A tidak dapat membalas permintaan pengundian C kerana kegagalan.
• Langkah 5
: Nod C menerima dua undi (majoriti undi) dan menjadi
• pemimpin. Langkah 6
: Nod C menghantar maklumat degupan jantung ke nod A dan B. Nod B bertindak balas kepada maklumat degupan jantung kerana A rosak.
Ringkasan

Algoritma Raft menggunakan kaedah berikut untuk menjalankan pemilihan kepimpinan, memastikan hanya ada seorang pemimpin dalam satu penggal, sekali gus mengurangkan peluang untuk Kegagalan pilihan raya.

Penggal

Maklumat degupan jantung pemimpin
• Tamat masa pilihan raya rawak
• Prinsip pengundian siapa cepat dia dapat
• Prinsip Undi Majoriti Besar
• Artikel ini menggunakan grafik animasi untuk menerangkan cara algoritma Raft memilih pemimpin, menjadikannya lebih mudah untuk difahami dan dihadam.

Atas ialah kandungan terperinci Algoritma konsensus yang sistem teragih mesti tahu: Rakit. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!