Paxos dan Raft

Paxos dan Raft adalah dua protokol konsensus praktis paling berpengaruh, yang menyediakan kesepakatan toleran terhadap kegagalan (crash-fault-tolerant agreement) pada log tereplikasi yang mendasari sistem koordinasi dunia nyata.

Definition

Paxos dan Raft adalah protokol berbasis kuorum yang memungkinkan serangkaian replika untuk menyepakati urutan perintah (log tereplikasi) meskipun terjadi kegagalan sistem (crash failures), memastikan bahwa entri yang telah dikomit tidak pernah hilang atau diurutkan ulang selama mayoritas replika tetap tersedia.

Scope

Topik ini mencakup keluarga Paxos—Paxos satu keputusan (single-decree Paxos), Multi-Paxos, dan penyempurnaan tekniknya—serta protokol Raft, yang menata ulang jaminan yang sama di sekitar pemimpin eksplisit, replikasi log, dan perubahan keanggotaan untuk kemudahan pemahaman. Ini mencakup peran pengusul/penerima (proposers/acceptors) dan pemimpin/pengikut (leaders/followers), persimpangan kuorum (quorum intersection), pemilihan dan masa jabatan pemimpin, pencocokan log, serta masalah praktis snapshot dan rekonfigurasi.

Core questions

• Bagaimana persimpangan kuorum dan penomoran proposal menjaga Paxos tetap aman di seluruh putaran dan perubahan pemimpin?
• Bagaimana Raft menguraikan konsensus menjadi pemilihan pemimpin, replikasi log, dan keamanan?
• Tantangan rekayasa apa yang muncul saat mengubah protokol ini menjadi sistem produksi?

Key theories

Paxos satu keputusan (Single-decree) dan Multi-Paxos

Paxos mencapai kesepakatan pada satu nilai melalui fase persiapan dan penerimaan yang diatur oleh nomor proposal monoton dan kuorum mayoritas; Multi-Paxos mengamortisasi fase persiapan di seluruh aliran keputusan yang dipimpin oleh pemimpin yang stabil untuk membangun log tereplikasi.

Dekomposisi Raft

Raft mencapai keamanan yang sama dengan Paxos dengan memilih satu pemimpin per periode, meminta pemimpin menambahkan entri yang direplikasi oleh pengikut, dan menegakkan properti pencocokan log, secara sengaja menukar minimalitas dengan kemudahan pemahaman dan implementasi.

Dari spesifikasi ke sistem yang berjalan

Menerapkan Paxos dalam praktik memerlukan penanganan kegagalan disk, sewa pemimpin (leader leases), pemadatan log (log compaction), dan rekonfigurasi, detail yang sering diabaikan dalam algoritma asli tetapi penting untuk kebenaran dan kinerja.

Clinical relevance

Paxos dan Raft berjalan di dalam layanan koordinasi, basis data terdistribusi, dan penyimpanan konfigurasi yang banyak digunakan; memahaminya sangat penting untuk membangun atau mengoperasikan sistem apa pun yang harus menjaga konsistensi replika yang kuat melalui kegagalan.

History

Lamport menjelaskan Paxos dalam makalahnya tahun 1998 'part-time parliament' dan mengklarifikasinya dalam 'Paxos made simple' (2001); Chandra dan rekan-rekannya melaporkan realitas membuatnya hidup dalam skala besar pada tahun 2007; dan Ongaro serta Ousterhout memperkenalkan Raft pada tahun 2014 untuk membuat jaminan yang setara jauh lebih mudah diajarkan dan diimplementasikan.

Debates

Kemudahan pemahaman versus minimalitas dalam protokol konsensus

Raft secara eksplisit dirancang agar lebih mudah dipahami daripada Paxos, memicu perdebatan apakah struktur tambahannya (pemimpin yang kuat) mengorbankan fleksibilitas; para pendukung berpendapat bahwa kemudahan pemahaman mengurangi bug implementasi, sementara yang lain mencatat varian Paxos bisa lebih umum.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Apakah Paxos dan Raft adalah algoritma yang secara fundamental berbeda?

Tidak—keduanya memecahkan masalah yang sama dengan inti kuorum mayoritas yang sama dan jaminan keamanan yang setara. Raft terutama menata ulang Paxos di sekitar pemimpin yang kuat dan log eksplisit untuk membuat protokol lebih mudah dipahami dan diimplementasikan.