เวกเตอร์คล็อกและภาวะเชิงสาเหตุ

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

Definition

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

Scope

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

Core questions

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

Key theories

การจำแนกภาวะเชิงสาเหตุด้วยเวกเตอร์คล็อก

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

เวกเตอร์เวอร์ชันสำหรับการตรวจจับความขัดแย้งของสำเนา

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

ความสัมพันธ์กับนาฬิกาเชิงตรรกะ

เวกเตอร์คล็อกปรับปรุงนาฬิกาเชิงตรรกะแบบสเกลาร์ของ Lamport อย่างเคร่งครัด: การประทับเวลาแบบสเกลาร์รับประกันเพียงว่าลำดับสอดคล้องกับภาวะเชิงสาเหตุ ในขณะที่การประทับเวลาแบบเวกเตอร์กำหนดภาวะเชิงสาเหตุได้อย่างแม่นยำโดยมีค่าใช้จ่ายพื้นที่ O(n) ต่อการประทับเวลา

Clinical relevance

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

History

ต่อยอดจากเวลาเชิงตรรกะของ Lamport, Fidge และ Mattern ได้นำเสนอเวกเตอร์คล็อกอย่างอิสระในปี 1988-1989; เวกเตอร์เวอร์ชันที่เกี่ยวข้องอย่างใกล้ชิดได้ปรากฏขึ้นแล้วในปี 1983 สำหรับการตรวจจับความไม่สอดคล้องกันระหว่างสำเนา และโครงสร้างเหล่านี้ยังคงเป็นหัวใจสำคัญของระบบข้อมูลจำลองที่ทันสมัย

Debates

ต้นทุนพื้นที่ของการติดตามภาวะเชิงสาเหตุที่แม่นยำ

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

Key figures

• Colin Fidge
• Friedemann Mattern
• Leslie Lamport

Seminal works

• fidge1988
• mattern1989
• parker1983

Frequently asked questions

เวกเตอร์คล็อกปรับปรุงนาฬิกา Lamport อย่างไร?

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