เวลาและสถานะส่วนกลาง
เวลาและสถานะส่วนกลางเกี่ยวข้องกับวิธีที่ระบบกระจายจัดลำดับเหตุการณ์และให้เหตุผลเกี่ยวกับสภาพโดยรวมของระบบเมื่อไม่มีนาฬิกาที่ใช้ร่วมกันและไม่มีมุมมองส่วนกลางแบบทันทีทันใด
Definition
ในระบบกระจาย เหตุการณ์ต่างๆ เกิดขึ้นที่กระบวนการแยกกันโดยไม่มีนาฬิกาที่ใช้ร่วมกัน การศึกษาเรื่องเวลาและสถานะส่วนกลางให้ความสัมพันธ์และอัลกอริทึม—นาฬิกาเชิงตรรกะและเวกเตอร์ สแนปช็อต และการส่งมอบตามลำดับ—ที่ช่วยให้ระบบจัดลำดับเหตุการณ์ตามหลักเหตุและผล และบันทึกสถานะส่วนกลางที่สอดคล้องกันได้
Scope
ขอบเขตนี้ครอบคลุมถึงนาฬิกาเชิงตรรกะและความสัมพันธ์แบบ 'เกิดขึ้นก่อน' (happened-before relation) การซิงโครไนซ์นาฬิกาทางกายภาพ นาฬิกาแบบเวกเตอร์และการตรวจจับความเป็นเหตุเป็นผลและความพร้อมกัน การกำหนดสแนปช็อตส่วนกลางที่สอดคล้องกัน และการรับประกันการจัดลำดับ (FIFO, เชิงสาเหตุ, ทั้งหมด) ที่จำเป็นสำหรับการส่งแบบหลายผู้รับที่เชื่อถือได้ เครื่องมือเหล่านี้ร่วมกันช่วยให้ระบบกระจายสามารถกล่าวถึง 'เมื่อใด' และ 'สถานะใด' ได้อย่างมีความหมาย แม้จะไม่มีนาฬิกาส่วนกลางก็ตาม
Sub-topics
Core questions
- เหตุการณ์ที่เกิดขึ้นในกระบวนการที่แตกต่างกันสามารถจัดลำดับได้อย่างไรโดยไม่มีนาฬิกาทางกายภาพที่ใช้ร่วมกัน?
- กระบวนการสามารถพิจารณาได้อย่างไรว่าเหตุการณ์สองเหตุการณ์มีความสัมพันธ์เชิงสาเหตุหรือเกิดขึ้นพร้อมกัน?
- สแนปช็อตส่วนกลางที่สอดคล้องกันสามารถบันทึกได้อย่างไรในขณะที่การคำนวณยังคงดำเนินต่อไป?
- การรับประกันการจัดลำดับการส่งข้อความแบบใดที่จำเป็นต่อการรักษาสาเหตุ?
Key theories
- ความสัมพันธ์แบบ 'เกิดขึ้นก่อน' และนาฬิกาเชิงตรรกะ
- ความสัมพันธ์แบบ 'เกิดขึ้นก่อน' ของ Lamport กำหนดลำดับเชิงสาเหตุบางส่วนของเหตุการณ์ และนาฬิกาเชิงตรรกะ (สเกลาร์) กำหนดการประทับเวลาที่สอดคล้องกับความสัมพันธ์ดังกล่าว ซึ่งให้แนวคิดเรื่องลำดับที่ไม่ต้องใช้นาฬิกาที่เพียงพอต่อการสร้างลำดับทั้งหมดสำหรับหลายโปรโตคอล
- นาฬิกาแบบเวกเตอร์และความเป็นเหตุเป็นผล
- นาฬิกาแบบเวกเตอร์ขยายนาฬิกาเชิงตรรกะเพื่อให้การเปรียบเทียบการประทับเวลาสองรายการสามารถระบุได้อย่างแม่นยำว่าเหตุการณ์หนึ่งเกิดขึ้นก่อนอีกเหตุการณ์หนึ่งในเชิงสาเหตุหรือไม่ หรือทั้งสองเหตุการณ์เกิดขึ้นพร้อมกัน ซึ่งช่วยให้สามารถติดตามความเป็นเหตุเป็นผลได้อย่างแม่นยำ
- สแนปช็อตส่วนกลางที่สอดคล้องกัน
- อัลกอริทึมสแนปช็อตของ Chandy-Lamport บันทึกสถานะส่วนกลางที่สอดคล้องกัน—สถานะกระบวนการรวมถึงข้อความที่อยู่ระหว่างการส่ง—โดยไม่ต้องหยุดระบบ โดยการส่งเครื่องหมายไปตามช่องทางต่างๆ
Clinical relevance
นาฬิกาเชิงตรรกะและเวกเตอร์เป็นพื้นฐานของความสอดคล้องเชิงสาเหตุ การตรวจจับความขัดแย้งในที่เก็บข้อมูลแบบจำลอง และการดีบักการทำงานแบบกระจาย สแนปช็อตที่สอดคล้องกันเป็นพื้นฐานของการทำเช็คพอยต์แบบกระจาย การตรวจจับภาวะชะงักงันและการสิ้นสุด และการกู้คืนความผิดพลาดในการประมวลผลสตรีม
History
บทความของ Lamport ในปี 1978 ได้นำเสนอแนวคิดเรื่องเวลาเชิงตรรกะและความสัมพันธ์แบบ 'เกิดขึ้นก่อน' ซึ่งเป็นหนึ่งในผลงานที่มีการอ้างอิงมากที่สุดในวิทยาการคอมพิวเตอร์ Chandy และ Lamport ได้กำหนดสแนปช็อตส่วนกลางที่สอดคล้องกันอย่างเป็นทางการในปี 1985 และ Fidge กับ Mattern ได้พัฒนานาฬิกาแบบเวกเตอร์แยกกันในช่วงปลายทศวรรษ 1980 ซึ่งเป็นการเติมเต็มชุดเครื่องมือพื้นฐานสำหรับการให้เหตุผลเกี่ยวกับเวลาและสถานะ
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- ทำไมระบบกระจายจึงไม่สามารถใช้นาฬิกาทางกายภาพที่ซิงโครไนซ์ได้?
- นาฬิกาทางกายภาพมีการคลาดเคลื่อนและไม่สามารถซิงโครไนซ์ได้อย่างสมบูรณ์ทั่วทั้งเครือข่ายที่มีความล่าช้าผันแปร ดังนั้นลำดับเวลาจริงของเหตุการณ์สองเหตุการณ์จึงอาจคลุมเครือได้ นาฬิกาเชิงตรรกะและเวกเตอร์จะบันทึกลำดับเชิงสาเหตุที่สำคัญต่อความถูกต้องแทน
- อะไรที่ทำให้สแนปช็อตส่วนกลาง 'สอดคล้องกัน'?
- สแนปช็อตจะสอดคล้องกันก็ต่อเมื่อเมื่อใดก็ตามที่สแนปช็อตนั้นรวมการรับข้อความ สแนปช็อตนั้นก็จะต้องรวมการส่งข้อความนั้นด้วย สถานะดังกล่าวอาจเกิดขึ้นระหว่างการดำเนินการได้ แม้ว่าจะไม่เคยมีการสังเกตช่วงเวลาเดียวพร้อมกันทั่วโลกก็ตาม