การเลือกผู้นำในระบบแบบกระจาย

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

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

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

ในบทความนี้ เราได้พูดคุยถึงข้อดีและข้อเสียของการเลือกผู้นำโดยรวม และวิธีที่ Amazon จัดการกับการเลือกผู้นำในระบบแบบกระจายของเรา รวมถึงข้อมูลเชิงลึกเกี่ยวกับความล้มเหลวของผู้นำ

มีวิธีเลือกผู้นำหลายวิธีด้วยกัน ตั้งแต่อัลกอริทึมอย่าง Paxos ไปจนถึงซอฟต์แวร์อย่าง Apache Zookeeper หรือฮาร์ดแวร์ที่กำหนดเอง หรือการเช่า การเช่าเป็นกลไกการเลือกผู้นำที่ใช้กันมากที่สุดที่ Amazon การเช่าทำความเข้าใจและนำมาใช้ได้ง่าย รวมถึงมอบความทนทานต่อความเสียหายในตัว การเช่าทำงานด้วยการมีฐานข้อมูลเดี่ยวที่จัดเก็บข้อมูลของผู้นำปัจจุบัน จากนั้น การเช่าจะต้องใช้สัญญาณของผู้นำเพื่อแสดงว่ายังคงเป็นผู้นำอยู่ หากผู้นำที่มีอยู่ไม่สามารถส่งสัญญาณเมื่อเวลผ่านไป ผู้นำรายอื่นก็สมารถลองเข้าควบคุมแทนได้

เราหลีกเลี่ยงการขึ้นอยู่กับเวลาในระบบแบบกระจาย แม้จะมีคุณสมบัติการซิงค์เวลาที่ยอดเยี่ยมใน Amazon Elastic Compute Cloud (Amazon EC2) การตรวจสอบให้แน่ใจว่านาฬิการะบบทั่วทั้งคลัสเตอร์ถได้รับการซิงโครไนซ์เพียงพอต่อการจัดลำดับการประสานงานที่แยกตามการทำงานไม่ใช่เรื่องง่าย ที่ Amazon ระบบแบบแยกใช้เวลาเพื่อการบริโภคของมนุษย์เท่านั้น การเช่าต้องอาศัยเวลา อย่างไรก็ตาม การเช่าจะขึ้นอยู่กับระยะเวลาที่ผ่านไปของตัวเครื่อง มากกว่าเวลาที่ได้รับการซิงโครไนซ์และต้องมีการตกลงกันโดยเซิร์ฟเวอร์หลายเครื่อง

ซอร์สโค้ด DynamoDB Lock Client มอบตัวอย่างที่เกี่ยวกับการเลือกผู้นำ แต่เราก็พบว่า แม้การเช่าจะล็อกอยู่และควรทำได้ง่ายดาย การนำมาใช้อย่างถูกต้องก็อาจทำได้ยาก การนำมาใช้ต้องอาศัยความเข้าใจวิธีที่เซิร์ฟเวอร์วัดระยะเวลาตัวเครื่อง ตัวอย่างเช่น หากเซิร์ฟเวอร์หรือคลังที่วัดเวลาคิดว่าเวลาย้อนกลับหลังเป็นระยะ ก็อาจเกิดการอนุมานระยะเวลาที่สร้างขึ้นสำหรับการเช่า ปัญหาการเลี่ยงระยะเวลากับการซิงโครไนซ์สัญญาณนาฬิกาทั่วโลกที่ทำให้เซิร์ฟเวอร์หยุดการยอมรับเวลาที่กำหนด ไม่ว่าจะเป็นการเพิ่มวินาทีไปจนถึงการคลาดเคลื่อนของนาฬิกาในตัวเครื่องเมื่อเวลาผ่านไปจากการใช้งาน CPU สูงอย่างต่อเนื่อง

ปัญหาที่ใหญ่กว่าสำหรับการเช่าและการล็อกแบบกระจายทุกประเภท ก็คือการทำให้แน่ใจว่าผู้นำกำลังทำงานในขณะที่ล็อกอยู่ การตรวจดูให้แน่ใจว่าผู้นำมีล็อกอยู่ถือเป็นเรื่องยาก เราพบว่าการตรวจสอบว่าผู้นำใช้เครือข่ายที่ช้าหรือไม่มั่นคงทำให้ระบบไม่เชื่อว่าถือล็อกนานกว่าที่เป็นจริง ในทางเดียวกัน การเก็บขยะจะหยุดชั่วคราวระหว่างการตรวจสอบล็อกและงานที่ทำให้เสร็จก็อาจนำไปสู่พฤติกรรมที่ไม่ถูกต้อง ในทางปฏิบัติแล้ว การฝืนทนปัญหาเหล่านี้มักจะเป็นอุปสรรคที่ใหญ่ที่สุด

DynamoDB และ ZooKeeper มอบไคลเอ็นต์การล็อกที่มีการเช่าเป็นพื้นฐาน ซึ่งมอบการเลือกผู้นำที่ทนทานต่อความผิดพลาด เราเลือกใช้ไคลเอ็นต์เหล่านี้เนื่องจากช่วยมอบวิธีที่ง่ายที่สุดและผ่านการทดสอบมาแล้วสำหรับการใช้การเลือกผู้นำ เว้นแต่ว่าจะมีความจำเป็นเฉพาะ ทีม Amazon เลือกที่จะเลี่ยงการสร้างการใช้การเลือกผู้นำแบบกำหนดเอง เรามักจะใช้ไคลเอ็นต์ที่มีอยู่แทน ซึ่งผ่านการทดสอบและทนต่อการใช้งาน

การเลือกผู้นำเป็นรูปแบบที่ใช้กันในวงกว้างทั่วทั้ง Amazon ตัวอย่างเช่น:

• ระบบแทบทั้งหมดที่ใช้ระบบการจัดการฐานข้อมูลเชิงสัมพันธ์แบบดั้งเดิม (RDBMSs) ต้องอาศัยการเลือกผู้นำเพื่อเลือกฐานข้อมูลผู้นำที่จะจัดการกับการเขียนทั้งหมด รวมถึงการอ่านทั้งหมดในบางเวลา การเลือกอาจทำงานโดยอัตโนมัติในระบบเหล่านี้ แต่ส่วนใหญ่แล้วจะดำเนินการโดยมนุษย์
• Amazon EBS กระจายการอ่านและการเขียนสำหรับไดรฟ์ข้อมูลไปในเซิร์ฟเวอร์จัดเก็บข้อมูลหลายเครื่อง เพื่อให้เกิดความสม่ำเสมอ Amazon EBS จะใช้การเลือกผู้นำเพื่อเลือกพื้นที่จัดเก็บหลักสำหรับแต่ละพื้นที่ของไดรฟ์ข้อมูล ซึ่งจะสั่งการอ่านและการเขียน หากพื้นที่จัดเก็บหลักไม่ทำงาน สำเนาผู้ตามก็จะก้าวเข้ามาแทนโดยใช้กลไกการเลือกผู้นำเดียวกัน ใน Amazon EBS การเลือกผู้นำช่วยให้เกิดความสม่ำเสมอ ในขณะที่ปรับปรุงประสิทธิภาพด้วยการหลีกเลี่ยงการประสานงานบน Data Plane DynamoDB, Amazon Quantum Ledger Database (Amazon QLDB) และ Amazon Kinesis (Kinesis) ใช้วิธีที่คล้ายกันด้วยเหตุผลเดียวกัน
• Kinesis Client Library (KCL) ใช้การเช่าเพื่อตรวจสอบว่าชิ้นส่วน Kinesis ได้รับการประมวลผลโดยเจ้าของรายเดียว ซึ่งช่วยให้ทำการประมวลผลสตรีม Kinesis แบบปรับขยายออกได้ง่าย

อีกหนึ่งสิ่งที่ควรคำนึงถึงก็คือสิ่งที่จะเกิดขึ้นกับงานของผู้นำเมื่อล้มเหลว หากผู้นำล้มเหลวระหว่างงาน ผู้นำใหม่จะทำงานให้สำเร็จอย่างไร หากผู้นำล้มเหลวก่อนที่จะทำงานให้ยั่งยืน ระบบยังคงถูกต้องหรือไม่ ระบบหลายประเภทมีการแยก "ทำให้งานยั่งยืน" และ "บอกผู้อื่นว่าเป็นขั้นตอนที่สมบูรณ์" ที่ Amazon ระบบจะทำสิ่งที่มาก่อนก่อนสิ่งที่ตามหลังเสมอ (หรือทนทานต่อการสูญเสียข้อมูล) การเป็นค่าเดิมเสมอมีประโยชน์อีกครั้งในที่นี้ โดยช่วยให้ผู้นำใหม่ขับเคลื่อนงานที่ผู้นำก่อนหน้าอาจทำเสร็จไปแล้วบางส่วนหรือเสร็จแล้วแต่ไม่ได้บอกผู้อื่นอีกครั้งได้อย่างมั่นใจ

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

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

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

ที่ Amazon เราทำตามแนวทางปฏิบัติที่ดีที่สุดสำหรับการเลือกผู้นำดังนี้

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

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

ระบบของ Amazon มักจะใช้การเลือกผู้นำเพื่อตรวจสอบว่ามีการทนทานต่อความผิดพลาดในตัว เมื่อระบบใช้การเลือกผู้นำเพื่อให้มั่นใจว่ามีอย่างน้อยหนึ่งเซิร์ฟเวอร์ประมวลผลอยู่ ระบบจะใช้กลไกแยกต่างหากสำหรับการการรักษาการแก้ไขในผู้นำที่มีหลายคนพร้อมกัน ตัวอย่างเช่น ระบบอาจใช้ฐานข้อมูลพื้นฐานนเพื่อให้มั่นใจว่าผู้นำสองคนคิดว่ามีการเช่า และไม่แทรกแซงกัน แทนที่จะตั้งสมมติฐานเกี่ยวกับการรับประกันที่ได้รับจากการดำเนินการตามการเช่า เรามุ่งเน้นความถูกต้องในระบบเหล่านี้บด้วยการสร้างแบบจำลองด้วยเทคนิคเช่น TLA +

แม้จะมีความแตกต่าง การเลือกผู้นำยังคงเป็นเครื่องมือที่มีประโยชน์ในชุดเครื่องมือระบบแบบแจกจ่ายของเราที่ Amazon ควบคู่ไปกับรูปแบบต่างๆ เช่น การเป็นค่าเดิมเสมอและการล็อกเชิงบวก

สำหรับข้อมูลเพิ่มเติมเกี่ยวกับวิธีการทำงานของการเช่า ให้ดูที่:

• วิธีการล็อกแบบแจกจ่าย
• Burrows, The Chubby Lock Service for Loosely-coupled Distributed Systems
• Gray and Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency