ภาพรวมสถานะและสถานะทั่วโลก

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมแนวคิดของสถานะทั่วโลกที่สอดคล้องกันและส่วนตัดที่กำหนดสถานะนั้น, อัลกอริทึมสแนปช็อตแบบใช้เครื่องหมายของ Chandy-Lamport และข้อสมมติฐาน (ช่องสัญญาณ FIFO, การส่งมอบที่เชื่อถือได้), และการประยุกต์ใช้สแนปช็อตในการตรวจจับคุณสมบัติที่เสถียร เช่น การตรวจจับการสิ้นสุดและการติดตาย และการทำเช็คพอยต์และการกู้คืนแบบกระจาย

Core questions

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

Key theories

ส่วนตัดที่สอดคล้องกัน

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

อัลกอริทึมสแนปช็อตของ Chandy-Lamport

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

การตรวจจับคุณสมบัติที่เสถียร

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

Clinical relevance

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

History

อัลกอริทึมของ Chandy และ Lamport ในปี 1985 ได้นำเสนอวิธีการปฏิบัติแรกในการบันทึกสถานะทั่วโลกที่สอดคล้องกันโดยไม่ต้องหยุดระบบ; Mattern และคนอื่นๆ ได้ขยายทฤษฎีส่วนตัดที่เป็นพื้นฐาน และเทคนิคนี้ต่อมาได้กลายเป็นรากฐานของการประมวลผลสตรีมที่ทนทานต่อความผิดพลาด

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

การถ่ายสแนปช็อตจำเป็นต้องหยุดระบบหรือไม่?

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