Paxos และ Raft

Paxos และ Raft เป็นโปรโตคอลฉันทามติเชิงปฏิบัติที่มีอิทธิพลมากที่สุดสองโปรโตคอล ซึ่งให้ข้อตกลงที่ทนทานต่อความผิดพลาดจากการขัดข้องบนบันทึกที่จำลองแบบ ซึ่งเป็นรากฐานของระบบการประสานงานในโลกแห่งความเป็นจริง

Definition

Paxos และ Raft เป็นโปรโตคอลที่ใช้โควรัม ซึ่งช่วยให้ชุดของสำเนาสามารถตกลงกันในลำดับคำสั่ง (บันทึกที่จำลองแบบ) แม้จะเกิดความล้มเหลวจากการขัดข้อง โดยรับประกันว่ารายการที่ยืนยันแล้วจะไม่สูญหายหรือจัดเรียงใหม่ ตราบใดที่สำเนาส่วนใหญ่ยังคงพร้อมใช้งาน

Scope

หัวข้อนี้ครอบคลุมตระกูล Paxos ได้แก่ Paxos แบบคำสั่งเดียว (single-decree Paxos), Multi-Paxos และการปรับปรุงทางวิศวกรรม รวมถึงโปรโตคอล Raft ซึ่งจัดระเบียบการรับประกันแบบเดียวกันโดยมีผู้นำที่ชัดเจน การจำลองบันทึก และการเปลี่ยนแปลงสมาชิกภาพเพื่อให้เข้าใจง่ายขึ้น โดยครอบคลุมบทบาทของผู้เสนอ/ผู้ยอมรับ (proposers/acceptors) และผู้นำ/ผู้ตาม (leaders/followers), การตัดกันของโควรัม (quorum intersection), การเลือกผู้นำและวาระ (leader election and terms), การจับคู่บันทึก (log matching) และข้อกังวลเชิงปฏิบัติเกี่ยวกับการสร้างสแนปช็อตและการกำหนดค่าใหม่

Core questions

• การตัดกันของโควรัมและการกำหนดหมายเลขข้อเสนอช่วยให้ Paxos ปลอดภัยได้อย่างไรในแต่ละรอบและการเปลี่ยนแปลงผู้นำ?
• Raft แยกย่อยฉันทามติออกเป็นการเลือกผู้นำ การจำลองบันทึก และความปลอดภัยได้อย่างไร?
• ความท้าทายทางวิศวกรรมใดบ้างที่เกิดขึ้นเมื่อเปลี่ยนโปรโตคอลเหล่านี้ให้เป็นระบบที่ใช้งานจริง?

Key theories

Single-decree และ Multi-Paxos

Paxos บรรลุข้อตกลงในค่าเดียวผ่านขั้นตอนการเตรียม (prepare) และการยอมรับ (accept) ซึ่งควบคุมโดยหมายเลขข้อเสนอแบบโมโนโทนิก (monotonic proposal numbers) และโควรัมเสียงข้างมาก (majority quorums); Multi-Paxos จะเฉลี่ยขั้นตอนการเตรียมผ่านกระแสของการตัดสินใจที่นำโดยผู้นำที่เสถียรเพื่อสร้างบันทึกที่จำลองแบบ

การแยกย่อยของ Raft

Raft บรรลุความปลอดภัยเช่นเดียวกับ Paxos โดยการเลือกผู้นำคนเดียวต่อวาระ โดยให้ผู้นำเพิ่มรายการที่ผู้ตามจำลองแบบ และบังคับใช้คุณสมบัติการจับคู่บันทึก (log-matching property) โดยจงใจแลกเปลี่ยนความเรียบง่ายกับการทำความเข้าใจและการนำไปใช้งานที่ง่ายขึ้น

จากข้อกำหนดสู่ระบบที่ทำงานได้จริง

การนำ Paxos ไปใช้งานจริงจำเป็นต้องจัดการกับความล้มเหลวของดิสก์ การเช่าผู้นำ (leader leases) การบีบอัดบันทึก (log compaction) และการกำหนดค่าใหม่ ซึ่งเป็นรายละเอียดที่มักถูกมองข้ามในอัลกอริทึมดั้งเดิม แต่มีความสำคัญต่อความถูกต้องและประสิทธิภาพ

Clinical relevance

Paxos และ Raft ทำงานภายในบริการประสานงาน ฐานข้อมูลแบบกระจาย และที่เก็บการกำหนดค่าที่ใช้กันอย่างแพร่หลาย การทำความเข้าใจโปรโตคอลเหล่านี้จึงเป็นสิ่งจำเป็นสำหรับการสร้างหรือการดำเนินงานระบบใดๆ ที่ต้องรักษาความสอดคล้องที่แข็งแกร่งของสำเนาผ่านความล้มเหลว

History

แลมพอร์ต (Lamport) ได้อธิบาย Paxos ในบทความ 'part-time parliament' ของเขาในปี 1998 และชี้แจงให้ชัดเจนใน 'Paxos made simple' (2001); จันทรา (Chandra) และเพื่อนร่วมงานได้รายงานความเป็นจริงของการทำให้โปรโตคอลนี้ใช้งานได้ในขนาดใหญ่ในปี 2007; และองกาโร (Ongaro) กับออสเตอร์เฮาต์ (Ousterhout) ได้นำเสนอ Raft ในปี 2014 เพื่อให้การรับประกันที่เทียบเท่ากันนั้นง่ายต่อการสอนและนำไปใช้งานมากขึ้น

Debates

ความเข้าใจง่ายเทียบกับความเรียบง่ายในโปรโตคอลฉันทามติ

Raft ได้รับการออกแบบมาอย่างชัดเจนเพื่อให้เข้าใจง่ายกว่า Paxos ซึ่งก่อให้เกิดการถกเถียงว่าโครงสร้างเพิ่มเติม (ผู้นำที่แข็งแกร่ง) ของ Raft นั้นลดความยืดหยุ่นหรือไม่; ผู้สนับสนุนโต้แย้งว่าความเข้าใจง่ายช่วยลดข้อผิดพลาดในการนำไปใช้งาน ในขณะที่คนอื่นๆ ตั้งข้อสังเกตว่า Paxos เวอร์ชันต่างๆ อาจมีความเป็นสากลมากกว่า

Key figures

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

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos และ Raft เป็นอัลกอริทึมที่แตกต่างกันโดยพื้นฐานหรือไม่?

ไม่—ทั้งสองแก้ปัญหาเดียวกันด้วยแกนหลักโควรัมเสียงข้างมากเดียวกันและมีการรับประกันความปลอดภัยที่เทียบเท่ากัน Raft ส่วนใหญ่จัดระเบียบ Paxos ใหม่โดยมีผู้นำที่แข็งแกร่งและบันทึกที่ชัดเจน เพื่อให้โปรโตคอลเข้าใจและนำไปใช้งานได้ง่ายขึ้น