ฉันทามติและการประสานงาน
ฉันทามติและการประสานงานกล่าวถึงวิธีการที่กระบวนการอิสระซึ่งสื่อสารกันด้วยข้อความเท่านั้น สามารถตกลงร่วมกันในค่าหรือการกระทำร่วมกันได้ แม้จะมีความล่าช้าและความล้มเหลวเกิดขึ้น
Definition
ฉันทามติคือปัญหาที่ชุดของกระบวนการ ซึ่งแต่ละกระบวนการเสนอค่าหนึ่งค่า จะต้องตัดสินใจเลือกค่าร่วมกันเพียงค่าเดียว โดยที่การตัดสินใจนั้นถูกต้อง กระบวนการที่ถูกต้องทั้งหมดเห็นด้วย และทุกกระบวนการที่ถูกต้องจะตัดสินใจในที่สุด แม้ว่าบางกระบวนการจะล้มเหลวก็ตาม
Scope
ขอบเขตนี้ครอบคลุมปัญหาฉันทามติและรูปแบบต่างๆ (การตกลงร่วมกัน, การแพร่ภาพแบบอะตอมมิค, ความถูกต้อง, การสิ้นสุด), ผลลัพธ์ที่เป็นไปไม่ได้ของ FLP สำหรับฉันทามติแบบอะซิงโครนัสเชิงกำหนด, โปรโตคอลฉันทามติเชิงปฏิบัติ เช่น Paxos และ Raft, การตกลงร่วมกันที่ทนทานต่อความผิดพลาดแบบไบแซนไทน์, และปัญหาการประสานงานแบบคลาสสิกของการกีดกันร่วมกันและการเลือกผู้นำ นี่คือแกนหลักทางทฤษฎีและปฏิบัติของการประมวลผลแบบกระจายที่ทนทานต่อความผิดพลาด
Sub-topics
Core questions
- ภายใต้แบบจำลองเวลาและความล้มเหลวใดที่ฉันทามติสามารถแก้ไขได้ และเมื่อใดที่ไม่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ไขได้?
- โปรโตคอลเชิงปฏิบัติหลีกเลี่ยงความเป็นไปไม่ได้ของ FLP ได้อย่างไรในขณะที่ยังคงรักษาความปลอดภัยไว้?
- ต้องมีการจำลองแบบเท่าใดจึงจะทนทานต่อความล้มเหลวแบบหยุดทำงานเทียบกับความล้มเหลวแบบไบแซนไทน์?
- กระบวนการต่างๆ สามารถประสานงานการเข้าถึงทรัพยากรที่ใช้ร่วมกันหรือเลือกผู้นำได้อย่างน่าเชื่อถือได้อย่างไร?
Key theories
- ความเป็นไปไม่ได้ของ FLP
- ในระบบอะซิงโครนัสเต็มรูปแบบ ไม่มีโปรโตคอลเชิงกำหนดใดที่สามารถรับประกันฉันทามติได้ หากแม้แต่กระบวนการเดียวอาจหยุดทำงาน เนื่องจากกระบวนการที่ช้าไม่สามารถแยกแยะได้จากกระบวนการที่ล้มเหลว ผลลัพธ์นี้กระตุ้นให้เกิดการซิงโครนัสบางส่วน การสุ่ม และตัวตรวจจับความล้มเหลว
- ฉันทามติแบบอิงโควรัม
- โปรโตคอลเช่น Paxos บรรลุข้อตกลงโดยการกำหนดให้เสียงข้างมากที่ทับซ้อนกัน (โควรัม) ยอมรับข้อเสนอ เพื่อให้แน่ใจว่าการตัดสินใจสองครั้งใดๆ จะตัดกันที่กระบวนการที่ถูกต้อง และด้วยเหตุนี้จึงยังคงสอดคล้องกันตลอดรอบและการเปลี่ยนแปลงผู้นำ
- ขอบเขตข้อตกลงแบบไบแซนไทน์
- ในการบรรลุข้อตกลงเมื่อมีกระบวนการสูงสุด f กระบวนการอาจทำงานผิดปกติ จะต้องมีกระบวนการอย่างน้อย 3f+1 ในการตั้งค่าแบบซิงโครนัสแบบคลาสสิก ซึ่งเป็นขอบเขตที่แน่นหนาซึ่งกำหนดรูปแบบการออกแบบของระบบที่ทนทานต่อความผิดพลาดแบบไบแซนไทน์ทั้งหมด
Clinical relevance
ฉันทามติเป็นกระดูกสันหลังของโครงสร้างพื้นฐานที่เชื่อถือได้: บริการประสานงาน, ฐานข้อมูลจำลอง, การล็อกแบบกระจาย, และบล็อกเชน ล้วนใช้โปรโตคอลฉันทามติเพื่อรักษาความสอดคล้องของสำเนา ทำให้พื้นที่นี้รับผิดชอบโดยตรงต่อการรับประกันความทนทานและความพร้อมใช้งานของระบบคลาวด์สมัยใหม่
History
บทความเรื่องนายพลไบแซนไทน์ในปี 1982 และผลลัพธ์ที่เป็นไปไม่ได้ของ FLP ในปี 1985 ได้กำหนดขีดจำกัดของการตกลงร่วมกัน; Paxos ของ Lamport (เผยแพร่ในปี 1989, ตีพิมพ์ในปี 1998) ได้นำเสนอโปรโตคอลที่ปลอดภัยแบบอะซิงโครนัสที่ใช้งานได้จริง และงานต่อมาเกี่ยวกับความทนทานต่อความผิดพลาดแบบไบแซนไทน์และ Raft ทำให้ฉันทามติมีความทนทานต่อความผิดพลาดที่เป็นอันตรายและเข้าถึงได้สำหรับผู้ใช้งาน
Debates
- ความเป็นไปไม่ได้ของ FLP ทำให้ฉันทามติไม่สามารถบรรลุผลได้ในทางปฏิบัติหรือไม่?
- FLP ตัดโปรโตคอลเชิงกำหนดที่ปลอดภัยและมีชีวิตชีวาเสมอในแบบจำลองอะซิงโครนัสเต็มรูปแบบออกไป แต่ระบบเชิงปฏิบัติจะหลีกเลี่ยงปัญหานี้โดยการสมมติการซิงโครนัสในที่สุดหรือใช้การสุ่ม โดยรักษาความปลอดภัยแบบไม่มีเงื่อนไขและบรรลุการมีชีวิตชีวาเมื่อใดก็ตามที่เครือข่ายทำงานได้ดี
Key figures
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
Related topics
Seminal works
- fischer1985
- lamport1998
- lamport1982byz
Frequently asked questions
- ทำไมฉันทามติจึงถูกพิจารณาว่าเป็นปัญหาที่ยากที่สุดในระบบแบบกระจาย?
- เนื่องจากงานประสานงานอื่นๆ อีกมากมาย เช่น การแพร่ภาพแบบอะตอมมิค, เครื่องสถานะจำลอง, การล็อกแบบกระจาย ล้วนลดทอนลงเหลือเพียงฉันทามติ และฉันทามติเองก็ไม่สามารถพิสูจน์ได้ว่าไม่สามารถแก้ไขได้แบบเชิงกำหนดในแบบจำลองความล้มเหลวแบบหยุดทำงานแบบอะซิงโครนัส ดังนั้นโซลูชันใดๆ จะต้องตั้งสมมติฐานเกี่ยวกับเวลาหรือการสุ่มอย่างระมัดระวัง
- ฉันทามติเกี่ยวข้องกับฐานข้อมูลจำลองอย่างไร?
- ฐานข้อมูลจำลองจะรักษาความสอดคล้องของสำเนาโดยการตกลงลำดับการดำเนินการ ซึ่งเป็นลำดับของการตัดสินใจฉันทามติอย่างแม่นยำ นี่คือเหตุผลที่ระบบเช่นที่เก็บข้อมูลคีย์-ค่าแบบกระจายฝังโปรโตคอลฉันทามติไว้ที่แกนหลัก