ลองจินตนาการดู มีแมว 5 ตัวถูกขังอยู่ในห้อง และเพื่อที่จะปลุกเจ้าของได้ พวกเขาทั้งหมดต้องตกลงกันเอง เพราะพวกเขาเปิดประตูได้โดยมีแมว XNUMX ตัวพิงอยู่บนนั้นเท่านั้น หากแมวตัวหนึ่งเป็นแมวของชโรดิงเงอร์ และแมวตัวอื่นไม่รู้เกี่ยวกับการตัดสินใจของเขา คำถามก็จะเกิดขึ้น: “พวกมันทำได้อย่างไร”
ในบทความนี้ ฉันจะบอกคุณด้วยเงื่อนไขง่ายๆ เกี่ยวกับองค์ประกอบทางทฤษฎีของโลกของระบบแบบกระจายและหลักการทำงานของระบบเหล่านั้น นอกจากนี้ ฉันจะตรวจสอบแนวคิดหลักที่เป็นรากฐานของ Paxos อย่างเผินๆ ด้วย
เมื่อนักพัฒนาใช้โครงสร้างพื้นฐานคลาวด์ ฐานข้อมูลที่หลากหลาย และทำงานในกลุ่มโหนดจำนวนมาก พวกเขามั่นใจว่าข้อมูลจะสมบูรณ์ ปลอดภัย และพร้อมใช้งานอยู่เสมอ แต่หลักประกันอยู่ที่ไหน?
โดยพื้นฐานแล้ว การรับประกันที่เรามีคือการรับประกันจากซัพพลายเออร์ มีการอธิบายไว้ในเอกสารดังต่อไปนี้: “บริการนี้ค่อนข้างเชื่อถือได้ มี SLA ที่กำหนด ไม่ต้องกังวล ทุกอย่างจะทำงานแบบกระจายตามที่คุณคาดหวัง”
เรามักจะเชื่อในสิ่งที่ดีที่สุด เพราะคนฉลาดจากบริษัทใหญ่ๆ รับรองกับเราว่าทุกอย่างจะเรียบร้อยดี เราไม่ถามคำถาม: เพราะเหตุใดในความเป็นจริงจึงสามารถใช้งานได้เลย? มีเหตุผลอย่างเป็นทางการสำหรับการทำงานที่ถูกต้องของระบบดังกล่าวหรือไม่?
ฉันเพิ่งไป และได้รับแรงบันดาลใจจากหัวข้อนี้มาก การบรรยายที่โรงเรียนเป็นเหมือนชั้นเรียนแคลคูลัสมากกว่าสิ่งที่เกี่ยวข้องกับระบบคอมพิวเตอร์ แต่นี่คือวิธีการพิสูจน์อัลกอริธึมที่สำคัญที่สุดที่เราใช้ทุกวันโดยไม่รู้ตัวในคราวเดียว
ระบบแบบกระจายสมัยใหม่ส่วนใหญ่ใช้อัลกอริธึมฉันทามติของ Paxos และการดัดแปลงต่างๆ สิ่งที่ยอดเยี่ยมที่สุดคือความถูกต้องและโดยหลักการแล้วความเป็นไปได้ของการมีอยู่ของอัลกอริทึมนี้สามารถพิสูจน์ได้ง่ายๆ ด้วยปากกาและกระดาษ ในทางปฏิบัติ อัลกอริธึมถูกใช้ในระบบขนาดใหญ่ที่ทำงานบนโหนดจำนวนมากในระบบคลาวด์
ภาพประกอบสั้นๆ ของสิ่งที่จะกล่าวถึงต่อไป: ภารกิจของนายพลสองคนมาดูการอุ่นเครื่องกันดีกว่า .
เรามีสองกองทัพ - แดงและขาว กองทหารขาวประจำการอยู่ในเมืองที่ถูกปิดล้อม กองทหารแดงที่นำโดยนายพล A1 และ A2 ตั้งอยู่สองฝั่งของเมือง ภารกิจของคนผมแดงคือโจมตีเมืองสีขาวและคว้าชัยชนะ อย่างไรก็ตาม กองทัพของแม่ทัพแดงแต่ละคนมีขนาดเล็กกว่ากองทัพสีขาว
เงื่อนไขชัยชนะของฝ่ายแดง: นายพลทั้งสองจะต้องโจมตีพร้อมกันเพื่อที่จะได้เปรียบเชิงตัวเลขเหนือฝ่ายขาว ในการดำเนินการนี้ นายพล A1 และ A2 จำเป็นต้องมีข้อตกลงร่วมกัน หากทุกคนโจมตีแยกกัน พวกผมแดงจะแพ้
เพื่อให้บรรลุข้อตกลง นายพล A1 และ A2 สามารถส่งผู้สื่อสารถึงกันผ่านอาณาเขตของเมืองสีขาว ผู้ส่งสารอาจเข้าถึงนายพลพันธมิตรได้สำเร็จหรืออาจถูกศัตรูสกัดกั้นได้ คำถาม: มีลำดับการสื่อสารระหว่างนายพลผมแดงหรือไม่ (ลำดับการส่งผู้ส่งสารจาก A1 ถึง A2 และในทางกลับกันจาก A2 ถึง A1) ซึ่งรับประกันว่าจะเห็นด้วยกับการโจมตีในชั่วโมง X ที่นี่ การรับประกันหมายความว่านายพลทั้งสองจะได้รับการยืนยันอย่างชัดเจนว่าพันธมิตร (นายพลอีกคน) จะโจมตีตามเวลาที่กำหนดอย่างแน่นอน X
สมมติว่า A1 ส่งผู้ส่งสารไปที่ A2 พร้อมข้อความ: "มาโจมตีวันนี้ตอนเที่ยงคืนกันเถอะ!" นายพล A1 ไม่สามารถโจมตีได้หากไม่มีการยืนยันจากนายพล A2 หากผู้ส่งสารจาก A1 มาถึงแล้ว นายพล A2 จะส่งคำยืนยันพร้อมข้อความ: "ใช่ วันนี้มาฆ่าคนผิวขาวกันเถอะ" แต่ตอนนี้นายพล A2 ไม่รู้ว่าผู้ส่งสารของเขามาถึงหรือไม่ เขาไม่รับประกันว่าการโจมตีจะเกิดขึ้นพร้อมกันหรือไม่ ตอนนี้นายพล A2 ต้องการการยืนยันอีกครั้ง
หากเราอธิบายการสื่อสารของพวกเขาเพิ่มเติม จะเห็นได้ชัดว่าไม่ว่าจะมีการแลกเปลี่ยนข้อความกี่รอบก็ตาม ก็ไม่มีทางรับประกันได้ว่านายพลทั้งสองจะได้รับข้อความของพวกเขา (สมมติว่าผู้ส่งสารคนใดคนหนึ่งสามารถดักจับได้)
ปัญหา Two Generals เป็นตัวอย่างที่ดีของระบบแบบกระจายที่เรียบง่ายซึ่งมีสองโหนดที่มีการสื่อสารที่ไม่น่าเชื่อถือ ซึ่งหมายความว่าเราไม่รับประกัน 100% ว่าจะซิงโครไนซ์ข้อมูลเหล่านั้น ปัญหาที่คล้ายกันจะกล่าวถึงในวงกว้างในบทความเท่านั้น
เราแนะนำแนวคิดของระบบแบบกระจาย
ระบบแบบกระจายคือกลุ่มของคอมพิวเตอร์ (ต่อไปนี้เราจะเรียกว่าโหนด) ที่สามารถแลกเปลี่ยนข้อความได้ แต่ละโหนดเป็นเอนทิตีอิสระบางประเภท โหนดสามารถประมวลผลงานได้ด้วยตัวเอง แต่เพื่อที่จะสื่อสารกับโหนดอื่น โหนดจำเป็นต้องส่งและรับข้อความ
มีการใช้ข้อความอย่างไร โปรโตคอลใดที่ใช้ - สิ่งนี้ไม่เป็นที่สนใจของเราในบริบทนี้ สิ่งสำคัญคือโหนดของระบบแบบกระจายสามารถแลกเปลี่ยนข้อมูลระหว่างกันได้โดยการส่งข้อความ
คำจำกัดความนั้นดูไม่ซับซ้อนมากนัก แต่เราต้องคำนึงว่าระบบแบบกระจายนั้นมีคุณลักษณะหลายประการที่จะมีความสำคัญต่อเรา
คุณลักษณะของระบบแบบกระจาย
- เห็นพ้องด้วย – ความเป็นไปได้ของเหตุการณ์ที่เกิดขึ้นพร้อมกันหรือเกิดขึ้นพร้อมกันในระบบ นอกจากนี้ เราจะพิจารณาเหตุการณ์ที่เกิดขึ้นบนสองโหนดที่แตกต่างกันว่าอาจเกิดขึ้นพร้อมกัน ตราบใดที่เราไม่มีลำดับเหตุการณ์ที่ชัดเจน แต่ตามกฎแล้วเราไม่มีมัน
- ไม่มีนาฬิกาทั่วโลก. เราไม่มีลำดับเหตุการณ์ที่ชัดเจนเนื่องจากขาดนาฬิกาทั่วโลก ในโลกธรรมดาๆ ของผู้คน เราคุ้นเคยกับความจริงที่ว่า เรามีนาฬิกาและเวลาอย่างแน่นอน ทุกอย่างเปลี่ยนแปลงไปเมื่อพูดถึงระบบแบบกระจาย แม้แต่นาฬิกาอะตอมที่มีความแม่นยำเป็นพิเศษก็ยังมีการเคลื่อนตัว และอาจมีสถานการณ์ที่เราไม่สามารถบอกได้ว่าเหตุการณ์ใดในสองเหตุการณ์เกิดขึ้นก่อน ดังนั้นเราจึงไม่สามารถพึ่งพาเวลาได้เช่นกัน
- ความล้มเหลวของโหนดระบบโดยอิสระ. มีปัญหาอีกอย่างหนึ่ง: มีบางอย่างผิดพลาดเพียงเพราะโหนดของเราไม่สามารถคงอยู่ตลอดไป ฮาร์ดไดรฟ์อาจล้มเหลว เครื่องเสมือนในระบบคลาวด์อาจรีบูต เครือข่ายอาจกะพริบ และข้อความจะหายไป ยิ่งไปกว่านั้น อาจมีบางสถานการณ์ที่โหนดทำงาน แต่ในขณะเดียวกันก็ทำงานกับระบบด้วย ปัญหาระดับสุดท้ายยังได้รับชื่อแยกต่างหาก: ปัญหา . ตัวอย่างที่ได้รับความนิยมมากที่สุดของระบบแบบกระจายที่มีปัญหานี้คือ Blockchain แต่วันนี้เราจะไม่พิจารณาปัญหาประเภทพิเศษนี้ เราจะสนใจในสถานการณ์ที่โหนดหนึ่งหรือหลายโหนดอาจล้มเหลว
- โมเดลการสื่อสาร (โมเดลการส่งข้อความ) ระหว่างโหนด. เราได้กำหนดไว้แล้วว่าโหนดสื่อสารโดยการแลกเปลี่ยนข้อความ มีสองรูปแบบการส่งข้อความที่รู้จักกันดี: ซิงโครนัสและอะซิงโครนัส
แบบจำลองการสื่อสารระหว่างโหนดในระบบแบบกระจาย
โมเดลซิงโครนัส – เรารู้แน่ว่ามีเวลาจำกัดที่ทราบในระหว่างที่ข้อความรับประกันว่าจะเข้าถึงจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง หากเวลานี้ผ่านไปแล้วและข้อความยังไม่มาถึง เราสามารถพูดได้อย่างปลอดภัยว่าโหนดล้มเหลว ในแบบจำลองนี้ เรามีเวลารอคอยที่คาดการณ์ได้
โมเดลอะซิงโครนัส – ในโมเดลอะซิงโครนัส เราพิจารณาว่าเวลาในการรอมีจำกัด แต่ไม่มีเดลต้าของเวลาดังกล่าวหลังจากนั้นเราสามารถรับประกันได้ว่าโหนดจะล้มเหลว เหล่านั้น. ระยะเวลารอข้อความจากโหนดอาจใช้เวลานานโดยพลการ นี่เป็นคำจำกัดความที่สำคัญและเราจะพูดถึงเรื่องนี้ต่อไป
แนวคิดเรื่องฉันทามติในระบบแบบกระจาย
ก่อนที่จะกำหนดแนวคิดฉันทามติอย่างเป็นทางการ ลองพิจารณาตัวอย่างสถานการณ์ที่เราต้องการก่อน กล่าวคือ - การจำลองเครื่องสถานะ.
เรามีบันทึกการแจกจ่ายบางส่วน เราต้องการให้มีความสอดคล้องและมีข้อมูลที่เหมือนกันบนโหนดทั้งหมดของระบบแบบกระจาย เมื่อโหนดใดโหนดหนึ่งเรียนรู้ค่าใหม่ที่จะเขียนลงในบันทึก หน้าที่ของโหนดนั้นจะต้องเสนอค่านี้ให้กับโหนดอื่นๆ ทั้งหมด เพื่อให้บันทึกได้รับการอัปเดตบนโหนดทั้งหมด และระบบจะย้ายไปยังสถานะใหม่ที่สอดคล้องกัน ในกรณีนี้ สิ่งสำคัญคือโหนดต้องตกลงกันเอง: โหนดทั้งหมดยอมรับว่าค่าใหม่ที่เสนอนั้นถูกต้อง โหนดทั้งหมดยอมรับค่านี้ และเฉพาะในกรณีนี้เท่านั้นที่ทุกคนสามารถเขียนค่าใหม่ลงในบันทึกได้
กล่าวอีกนัยหนึ่ง: ไม่มีโหนดใดคัดค้านว่ามีข้อมูลที่เกี่ยวข้องมากกว่า และค่าที่เสนอนั้นไม่ถูกต้อง ข้อตกลงระหว่างโหนดและข้อตกลงเกี่ยวกับค่าที่ถูกต้องที่ยอมรับเพียงค่าเดียวถือเป็นเอกฉันท์ในระบบแบบกระจาย ต่อไป เราจะพูดถึงอัลกอริธึมที่รับประกันว่าระบบแบบกระจายจะบรรลุข้อตกลงร่วมกัน
อย่างเป็นทางการมากขึ้น เราสามารถกำหนดอัลกอริธึมฉันทามติ (หรือเพียงอัลกอริธึมฉันทามติ) ให้เป็นฟังก์ชันบางอย่างที่ถ่ายโอนระบบแบบกระจายจากสถานะ A ไปยังสถานะ B ยิ่งไปกว่านั้น สถานะนี้ได้รับการยอมรับจากทุกโหนด และโหนดทั้งหมดสามารถยืนยันได้ ปรากฎว่างานนี้ไม่ใช่เรื่องเล็กน้อยอย่างที่คิดเมื่อเห็นแวบแรก
คุณสมบัติของอัลกอริทึมฉันทามติ
อัลกอริธึมฉันทามติจะต้องมีคุณสมบัติสามประการเพื่อให้ระบบยังคงมีอยู่และมีความคืบหน้าในการย้ายจากรัฐหนึ่งไปอีกรัฐหนึ่ง:
- ข้อตกลง – โหนดที่ทำงานอย่างถูกต้องทั้งหมดจะต้องใช้ค่าเดียวกัน (ในบทความคุณสมบัตินี้เรียกอีกอย่างว่าคุณสมบัติด้านความปลอดภัย) โหนดทั้งหมดที่กำลังทำงานอยู่ (ไม่ล้มเหลวหรือขาดการติดต่อกับโหนดอื่น) จะต้องบรรลุข้อตกลงและยอมรับค่าร่วมสุดท้ายบางส่วน
สิ่งสำคัญคือต้องเข้าใจที่นี่ว่าโหนดในระบบแบบกระจายที่เรากำลังพิจารณาต้องการยอมรับ นั่นคือเรากำลังพูดถึงระบบที่บางสิ่งสามารถล้มเหลวได้ (ตัวอย่างเช่นบางโหนดล้มเหลว) แต่ในระบบนี้ไม่มีโหนดใดที่จงใจทำงานกับผู้อื่นโดยเจตนา (งานของนายพลไบเซนไทน์) เนื่องจากคุณสมบัตินี้ ระบบจึงยังคงความสม่ำเสมอ
- ความสมบูรณ์ — หากโหนดที่ทำงานอย่างถูกต้องทั้งหมดมีค่าเท่ากัน vซึ่งหมายความว่าทุกโหนดที่ทำงานอย่างถูกต้องจะต้องยอมรับค่านี้ v.
- การสิ้นสุด – โหนดที่ทำงานอย่างถูกต้องทั้งหมดจะใช้ค่าที่แน่นอนในที่สุด (คุณสมบัติความมีชีวิตชีวา) ซึ่งช่วยให้อัลกอริทึมมีความคืบหน้าในระบบ แต่ละโหนดที่ทำงานได้อย่างถูกต้องไม่ช้าก็เร็วจะต้องยอมรับค่าสุดท้ายและยืนยัน: “สำหรับฉัน ค่านี้เป็นจริง ฉันเห็นด้วยกับทั้งระบบ”
ตัวอย่างวิธีการทำงานของอัลกอริทึมที่เป็นเอกฉันท์
แม้ว่าคุณสมบัติของอัลกอริธึมอาจไม่ชัดเจนทั้งหมด ดังนั้น เราจะแสดงด้วยตัวอย่างว่าขั้นตอนใดที่อัลกอริธึมฉันทามติที่ง่ายที่สุดต้องผ่านในระบบที่มีโมเดลการส่งข้อความแบบซิงโครนัส ซึ่งโหนดทั้งหมดทำงานตามที่คาดไว้ ข้อความจะไม่สูญหายและไม่มีอะไรเสียหาย (สิ่งนี้เกิดขึ้นจริงหรือ)
- ทุกอย่างเริ่มต้นด้วยการขอแต่งงาน (Propose) สมมติว่าไคลเอนต์เชื่อมต่อกับโหนดที่เรียกว่า "โหนด 1" และเริ่มต้นธุรกรรมโดยส่งค่าใหม่ไปยังโหนด - O จากนี้ไป เราจะเรียก "โหนด 1" เสนอ. ในฐานะผู้เสนอ ตอนนี้ “โหนด 1” จะต้องแจ้งให้ทั้งระบบทราบว่ามีข้อมูลใหม่ และจะส่งข้อความไปยังโหนดอื่นๆ ทั้งหมด: “ดูสิ! ความหมาย "O" มาถึงฉันและฉันก็อยากจะเขียนมันลงไป! โปรดยืนยันว่าคุณจะบันทึก "O" ไว้ในบันทึกของคุณด้วย"
- ขั้นต่อไปคือการลงคะแนนเสียงตามมูลค่าที่เสนอ (Voting) มีไว้เพื่ออะไร? อาจเกิดขึ้นที่โหนดอื่นๆ ได้รับข้อมูลล่าสุด และมีข้อมูลในธุรกรรมเดียวกัน
เมื่อโหนด “โหนด 1” ส่งข้อเสนอ โหนดอื่นๆ จะตรวจสอบบันทึกเพื่อดูข้อมูลเกี่ยวกับเหตุการณ์นี้ หากไม่มีข้อขัดแย้ง โหนดจะประกาศว่า: “ใช่ ฉันไม่มีข้อมูลอื่นสำหรับเหตุการณ์นี้ ค่า “O” คือข้อมูลล่าสุดที่เราสมควรได้รับ”ในกรณีอื่น ๆ โหนดสามารถตอบสนองต่อ "โหนด 1": "ฟัง! ฉันมีข้อมูลล่าสุดเกี่ยวกับธุรกรรมนี้ ไม่ใช่ 'O' แต่เป็นสิ่งที่ดีกว่า "
ในขั้นตอนการโหวต โหนดต่างๆ จะต้องตัดสินใจ: ไม่ว่าโหนดทั้งหมดจะยอมรับค่าเดียวกัน หรือโหนดใดโหนดหนึ่งลงคะแนนคัดค้าน ซึ่งบ่งชี้ว่าเขามีข้อมูลที่ใหม่กว่า
- หากรอบการโหวตสำเร็จและทุกคนเห็นชอบ ระบบจะย้ายไปยังขั้นตอนใหม่ - การยอมรับมูลค่า “โหนด 1” รวบรวมคำตอบทั้งหมดจากโหนดและรายงานอื่นๆ: “ทุกคนเห็นด้วยกับค่า “O”! ตอนนี้ฉันประกาศอย่างเป็นทางการว่า "O" คือความหมายใหม่ของเราเหมือนกันสำหรับทุกคน! เขียนลงในหนังสือเล่มเล็กๆ ของคุณ อย่าลืม เขียนมันลงในบันทึกของคุณ!”
- โหนดที่เหลือส่งการยืนยัน (ยอมรับแล้ว) ว่าพวกเขาได้เขียนค่า "O" แล้ว ไม่มีอะไรใหม่เข้ามาในช่วงเวลานี้ (ชนิดของการคอมมิตแบบสองเฟส) หลังจากเหตุการณ์สำคัญนี้ เราจะพิจารณาว่าธุรกรรมแบบกระจายเสร็จสมบูรณ์แล้ว
ดังนั้นอัลกอริทึมที่เป็นเอกฉันท์ในกรณีง่าย ๆ ประกอบด้วยสี่ขั้นตอน: เสนอ ลงคะแนน (ลงคะแนน) ยอมรับ (ยอมรับ) ยืนยันการยอมรับ (ยอมรับ)
หากเราไม่สามารถบรรลุข้อตกลงในขั้นตอนใดขั้นตอนหนึ่งได้ อัลกอริธึมจะเริ่มต้นอีกครั้ง โดยคำนึงถึงข้อมูลที่ได้รับจากโหนดที่ปฏิเสธที่จะยืนยันค่าที่เสนอ
อัลกอริธึมฉันทามติในระบบอะซิงโครนัส
ก่อนหน้านี้ ทุกอย่างราบรื่น เนื่องจากเรากำลังพูดถึงโมเดลการส่งข้อความแบบซิงโครนัส แต่เรารู้ว่าในโลกสมัยใหม่เราคุ้นเคยกับการทำทุกอย่างแบบอะซิงโครนัส อัลกอริธึมที่คล้ายกันทำงานอย่างไรในระบบที่มีโมเดลการส่งข้อความแบบอะซิงโครนัส โดยที่เราเชื่อว่าเวลารอสำหรับการตอบกลับจากโหนดอาจใช้เวลานานโดยพลการ (โดยวิธีการนั้น ความล้มเหลวของโหนดก็ถือได้ว่าเป็นตัวอย่างเมื่อ โหนดสามารถตอบสนองเป็นเวลานานโดยพลการ)
ตอนนี้เรารู้แล้วว่าอัลกอริธึมฉันทามติทำงานอย่างไรในหลักการ คำถามสำหรับผู้อ่านที่อยากรู้อยากเห็นและทำมาถึงขนาดนี้: มีกี่โหนดในระบบของโหนด N ที่มีโมเดลข้อความแบบอะซิงโครนัสที่สามารถล้มเหลวเพื่อให้ระบบยังคงสามารถเข้าถึงฉันทามติได้
คำตอบและเหตุผลที่ถูกต้องอยู่เบื้องหลังสปอยเลอร์ถูกต้องคำตอบ: 0. หากโหนดเดียวในระบบอะซิงโครนัสล้มเหลว ระบบจะไม่สามารถบรรลุข้อตกลงร่วมกันได้ ข้อความนี้ได้รับการพิสูจน์แล้วในทฤษฎีบท FLP ซึ่งเป็นที่รู้จักในบางแวดวง (1985, Fischer, Lynch, Paterson, ลิงก์ไปยังต้นฉบับที่ท้ายบทความ): “ความเป็นไปไม่ได้ที่จะบรรลุฉันทามติแบบกระจาย หากอย่างน้อยหนึ่งโหนดล้มเหลว ”
เพื่อน ๆ เรามีปัญหา เราคุ้นเคยกับทุกสิ่งที่ไม่ตรงกัน และนี่คือ จะอยู่ต่อไปได้อย่างไร?
เราแค่พูดถึงทฤษฎี เกี่ยวกับคณิตศาสตร์ “ไม่สามารถบรรลุฉันทามติได้” หมายความว่าอย่างไร การแปลจากภาษาคณิตศาสตร์เป็นภาษาของเรา - วิศวกรรมศาสตร์ ซึ่งหมายความว่า “ไม่สามารถทำได้เสมอไป” เช่น มีกรณีที่ไม่สามารถบรรลุข้อตกลงร่วมกันได้ นี่เป็นกรณีประเภทใด?
นี่เป็นการละเมิดคุณสมบัติความมีชีวิตชีวาที่อธิบายไว้ข้างต้นอย่างแน่นอน เราไม่มีข้อตกลงร่วมกัน และระบบไม่สามารถมีความคืบหน้าได้ (ไม่สามารถดำเนินการให้เสร็จสิ้นภายในระยะเวลาอันจำกัด) ในกรณีที่เราไม่ได้รับการตอบกลับจากทุกโหนด เนื่องจากในระบบอะซิงโครนัส เราไม่มีเวลาตอบสนองที่คาดการณ์ได้ และเราไม่สามารถรู้ได้ว่าโหนดขัดข้องหรือใช้เวลานานในการตอบสนอง
แต่ในทางปฏิบัติเราสามารถหาวิธีแก้ปัญหาได้ ปล่อยให้อัลกอริทึมของเราสามารถทำงานได้เป็นเวลานานในกรณีที่เกิดความล้มเหลว (อาจสามารถทำงานได้อย่างไม่มีกำหนด) แต่ในสถานการณ์ส่วนใหญ่ เมื่อโหนดส่วนใหญ่ทำงานอย่างถูกต้อง เราก็จะมีความคืบหน้าในระบบ
ในทางปฏิบัติ เราจัดการกับโมเดลการสื่อสารแบบซิงโครนัสบางส่วน การซิงโครไนซ์บางส่วนเป็นที่เข้าใจดังนี้: ในกรณีทั่วไป เรามีแบบจำลองอะซิงโครนัส แต่มีการนำแนวคิดบางอย่างของ "เวลาการรักษาเสถียรภาพทั่วโลก" ของจุดเวลาหนึ่งอย่างเป็นทางการมาใช้
ช่วงเวลานี้อาจไม่มาเป็นระยะเวลานาน แต่สักวันหนึ่งมันจะต้องมาถึง นาฬิกาปลุกเสมือนจริงจะดังขึ้น และจากช่วงเวลานั้น เราก็สามารถคาดเดาเวลาที่ข้อความจะมาถึงได้ จากนี้ไป ระบบจะเปลี่ยนจากอะซิงโครนัสเป็นซิงโครนัส ในทางปฏิบัติ เราจัดการกับระบบดังกล่าวอย่างชัดเจน
อัลกอริธึม Paxos แก้ปัญหาที่เป็นเอกฉันท์
เป็นตระกูลอัลกอริธึมที่แก้ปัญหาฉันทามติสำหรับระบบซิงโครนัสบางส่วน โดยมีความเป็นไปได้ที่บางโหนดอาจล้มเหลว ผู้เขียน Paxos คือ . เขาเสนอหลักฐานอย่างเป็นทางการของการมีอยู่และความถูกต้องของอัลกอริทึมในปี 1989
แต่การพิสูจน์กลับกลายเป็นเรื่องไม่สำคัญ สิ่งพิมพ์ครั้งแรกเผยแพร่เฉพาะในปี 1998 (33 หน้า) ที่อธิบายอัลกอริทึม เมื่อปรากฎว่าเป็นเรื่องยากมากที่จะเข้าใจและในปี 2001 มีการตีพิมพ์คำอธิบายของบทความนี้ซึ่งมีความยาว 14 หน้า มีการระบุปริมาณสิ่งพิมพ์เพื่อแสดงให้เห็นว่าในความเป็นจริงแล้วปัญหาฉันทามตินั้นไม่ใช่เรื่องง่ายเลย และเบื้องหลังอัลกอริธึมดังกล่าวนั้นมีงานจำนวนมากโดยคนที่ฉลาดที่สุด
เป็นที่น่าสนใจที่ Leslie Lamport ตั้งข้อสังเกตในการบรรยายของเขาว่าในบทความอธิบายที่สองมีข้อความหนึ่งบรรทัดหนึ่งบรรทัด (เขาไม่ได้ระบุว่าข้อความใด) ซึ่งสามารถตีความได้หลายวิธี และด้วยเหตุนี้ การใช้งาน Paxos สมัยใหม่จำนวนมากจึงทำงานไม่ถูกต้องทั้งหมด
การวิเคราะห์โดยละเอียดเกี่ยวกับงานของ Paxos จะใช้เวลามากกว่าหนึ่งบทความ ดังนั้นฉันจะพยายามถ่ายทอดแนวคิดหลักของอัลกอริทึมโดยย่อ ในลิงก์ท้ายบทความของฉัน คุณจะพบเอกสารสำหรับการดำน้ำเพิ่มเติมในหัวข้อนี้
บทบาทที่ Paxos
อัลกอริธึม Paxos มีแนวคิดเกี่ยวกับบทบาท ลองพิจารณาสามสิ่งหลัก (มีการแก้ไขที่มีบทบาทเพิ่มเติม):
- ผู้เสนอ (อาจใช้คำนี้: ผู้นำหรือผู้ประสานงาน). คนเหล่านี้คือผู้ที่เรียนรู้เกี่ยวกับคุณค่าใหม่ๆ จากผู้ใช้และรับบทบาทเป็นผู้นำ หน้าที่ของพวกเขาคือการเปิดตัวข้อเสนอรอบหนึ่งสำหรับค่านิยมใหม่และประสานงานการดำเนินการเพิ่มเติมของโหนด ยิ่งไปกว่านั้น Paxos ยังอนุญาตให้มีผู้นำหลายคนได้ในบางสถานการณ์
- ผู้ตอบรับ (ผู้มีสิทธิเลือกตั้ง). เหล่านี้เป็นโหนดที่ลงคะแนนให้ยอมรับหรือปฏิเสธค่าใดค่าหนึ่ง บทบาทของพวกเขามีความสำคัญมาก เพราะการตัดสินใจขึ้นอยู่กับพวกเขา: ระบบจะ (หรือไม่) สถานะอะไรหลังจากขั้นตอนถัดไปของอัลกอริธึมที่เป็นเอกฉันท์
- ผู้เรียน. โหนดที่ยอมรับและเขียนค่าที่ยอมรับใหม่เมื่อสถานะของระบบเปลี่ยนไป พวกเขาไม่ได้ทำการตัดสินใจ พวกเขาเพียงแค่ได้รับข้อมูลและสามารถมอบให้กับผู้ใช้ปลายทางได้
โหนดเดียวสามารถรวมหลายบทบาทในสถานการณ์ที่แตกต่างกันได้
แนวคิดเรื่ององค์ประชุม
เราถือว่าเรามีระบบของ N โหนด และในจำนวนนั้นสูงสุด F โหนดอาจล้มเหลว ถ้าโหนด F ล้มเหลว เราก็ต้องมีอย่างน้อย 2F+1 โหนดตัวรับ
นี่เป็นสิ่งจำเป็นเพื่อที่เราจะได้โหนด "ดี" ส่วนใหญ่ที่ทำงานได้อย่างถูกต้อง แม้ในสถานการณ์ที่เลวร้ายที่สุด นั่นคือ ฉ+1 โหนด "ดี" ที่ตกลงกัน และค่าสุดท้ายจะได้รับการยอมรับ มิฉะนั้นอาจมีสถานการณ์ที่กลุ่มท้องถิ่นต่าง ๆ ของเราใช้ความหมายต่างกันและไม่สามารถตกลงกันเองได้ ดังนั้นเราจึงต้องมีเสียงข้างมากจึงจะชนะการลงคะแนนเสียง
แนวคิดทั่วไปเกี่ยวกับวิธีการทำงานของอัลกอริทึมฉันทามติของ Paxos
อัลกอริธึม Paxos เกี่ยวข้องกับสองขั้นตอนใหญ่ ซึ่งจะแบ่งออกเป็นสองขั้นตอนในแต่ละขั้นตอน:
- ระยะที่ 1a: เตรียมพร้อม. ในระหว่างขั้นตอนการเตรียมการ ผู้นำ (ผู้เสนอ) แจ้งให้โหนดทั้งหมดทราบ: “เรากำลังเริ่มขั้นตอนการลงคะแนนเสียงใหม่ เรามีรอบใหม่นะ จำนวนรอบนี้คือ n ตอนนี้เราจะเริ่มลงคะแนนเสียง” ในตอนนี้ รายงานการเริ่มต้นรอบใหม่เท่านั้น แต่จะไม่รายงานค่าใหม่ ภารกิจของขั้นตอนนี้คือการเริ่มต้นรอบใหม่และแจ้งให้ทุกคนทราบถึงหมายเลขเฉพาะของมัน เลขรอบเป็นสิ่งสำคัญ โดยจะต้องเป็นค่าที่มากกว่าตัวเลขการลงคะแนนครั้งก่อนๆ จากผู้นำคนก่อนๆ ทั้งหมด เพราะต้องขอบคุณเลขกลมที่โหนดอื่นๆ ในระบบจะเข้าใจว่าข้อมูลของผู้นำมีความทันสมัยเพียงใด มีแนวโน้มว่าโหนดอื่นจะมีผลการโหวตจากรอบต่อๆ ไปอยู่แล้ว และจะบอกผู้นำว่าเขาล้าหลัง
- ระยะที่ 1b: คำสัญญา. เมื่อโหนดตัวรับได้รับหมายเลขของขั้นตอนการลงคะแนนใหม่ ผลลัพธ์ที่เป็นไปได้สองประการ:
- จำนวนการลงคะแนนใหม่ n มากกว่าจำนวนการลงคะแนนครั้งก่อนๆ ที่ผู้ตอบรับเข้าร่วม จากนั้นผู้ตอบรับจะส่งสัญญากับผู้นำว่าจะไม่มีส่วนร่วมในการลงคะแนนเสียงอีกต่อไปโดยมีจำนวนต่ำกว่า n หากผู้ยอมรับได้ลงคะแนนให้กับบางสิ่งบางอย่างแล้ว (นั่นคือ ได้ยอมรับมูลค่าบางส่วนแล้วในระยะที่สอง) จากนั้นจะแนบมูลค่าที่ยอมรับและจำนวนการลงคะแนนที่ตนเข้าร่วมกับคำมั่นสัญญา
- มิฉะนั้น หากผู้ตอบรับรู้อยู่แล้วเกี่ยวกับคะแนนเสียงที่สูงกว่า ก็สามารถเพิกเฉยต่อขั้นตอนการเตรียมการ และไม่ตอบสนองต่อผู้นำได้
- ระยะที่ 2a: ยอมรับ. ผู้นำต้องรอการตอบกลับจากองค์ประชุม (โหนดส่วนใหญ่ในระบบ) และหากได้รับคำตอบตามจำนวนที่ต้องการ ผู้นำจะมีสองทางเลือกสำหรับการพัฒนากิจกรรม:
- ผู้ตอบรับบางคนส่งค่าที่พวกเขาโหวตไปแล้ว ในกรณีนี้ผู้นำจะเลือกค่าจากการโหวตด้วยจำนวนสูงสุด ลองเรียกค่านี้ว่า x และมันจะส่งข้อความไปยังโหนดทั้งหมดเช่น: “ยอมรับ (n, x)” โดยที่ค่าแรกคือหมายเลขการลงคะแนนจากขั้นตอนการเสนอของตัวเอง และค่าที่สองคือสิ่งที่ทุกคนรวบรวมมา เช่น. คุณค่าที่เราลงคะแนนจริงๆ
- หากไม่มีผู้ตอบรับส่งค่าใด ๆ มาให้ แต่พวกเขาเพียงสัญญาว่าจะลงคะแนนในรอบนี้ ผู้นำสามารถเชิญพวกเขาให้ลงคะแนนตามคุณค่าของตนเอง ซึ่งเป็นค่าที่เขากลายเป็นผู้นำตั้งแต่แรก ลองเรียกมันว่า y มันจะส่งข้อความไปยังโหนดทั้งหมดเช่น: “ยอมรับ (n, y)” คล้ายกับผลลัพธ์ก่อนหน้า
- ระยะที่ 2b: ยอมรับแล้ว. นอกจากนี้ โหนดตัวรับเมื่อได้รับข้อความ “ยอมรับ(...)” จากผู้นำ ให้เห็นด้วยกับมัน (ส่งการยืนยันไปยังโหนดทั้งหมดว่าพวกเขาเห็นด้วยกับค่าใหม่) เฉพาะในกรณีที่พวกเขาไม่ได้สัญญาไว้บางส่วน (อื่นๆ) ) เป็นผู้นำในการมีส่วนร่วมในการลงคะแนนเสียงเป็นจำนวนรอบ ไม่มี > ไม่มีไม่เช่นนั้นพวกเขาจะเพิกเฉยต่อคำขอยืนยัน
หากโหนดส่วนใหญ่ตอบสนองต่อผู้นำ และโหนดทั้งหมดยืนยันค่าใหม่ ค่าใหม่จะถือว่าได้รับการยอมรับ ไชโย! หากไปไม่ถึงคนส่วนใหญ่หรือมีโหนดที่ปฏิเสธที่จะยอมรับค่าใหม่ ทุกอย่างจะเริ่มต้นใหม่
นี่คือวิธีการทำงานของอัลกอริทึม Paxos แต่ละขั้นตอนเหล่านี้มีรายละเอียดปลีกย่อยมากมาย ในทางปฏิบัติเราไม่ได้พิจารณาความล้มเหลวประเภทต่างๆ ปัญหาของผู้นำหลายคน และอื่นๆ อีกมากมาย แต่จุดประสงค์ของบทความนี้มีไว้เพื่อแนะนำผู้อ่านให้รู้จักกับโลกแห่งการคำนวณแบบกระจายในระดับสูงเท่านั้น
เป็นที่น่าสังเกตว่า Paxos ไม่ใช่เพียงชนิดเดียวเท่านั้น ยังมีอัลกอริธึมอื่น ๆ เช่น แต่นี่เป็นหัวข้อสำหรับบทความอื่น
ลิงค์เอกสารสำหรับการศึกษาต่อ
ระดับเริ่มต้น:
- , Preethi Kasireddy บทความบล็อกเกี่ยวกับสื่อ
- , Adi Kancherla บทความบล็อกบนสื่อ
- , อิตไต อับราฮัม, บล็อก
- , Ittai Abraham บทความในบล็อก
ระดับเลสลี่ แลมพอร์ต:
- , Fischer, Lynch และ Paterson, บทความวิจัย, 1985
- , เลสลี แลมพอร์ต, เอกสารวิจัย, 1998
- , เลสลี แลมพอร์ต, เอกสารวิจัย, 2001
ที่มา: will.com