นาฬิกาเชิงตรรกะและนาฬิกาเชิงกายภาพ

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมนาฬิกาเชิงตรรกะ (สเกลาร์) ของ Lamport และความสัมพันธ์แบบเกิดขึ้นก่อน (happened-before) ที่นาฬิกาเหล่านี้เคารพ การสร้างลำดับรวม (total order) จากการประทับเวลาเชิงตรรกะ และการซิงโครไนซ์นาฬิกาเชิงกายภาพ—การจำกัดการคลาดเคลื่อน การแลกเปลี่ยนการประทับเวลาเพื่อประมาณค่าออฟเซ็ต และอัลกอริทึม (วิธีของ Cristian, อัลกอริทึม Berkeley, NTP) ที่ใช้ในทางปฏิบัติ นอกจากนี้ยังเปรียบเทียบว่าเมื่อใดที่เวลาเชิงตรรกะเชิงสาเหตุเพียงพอ และเมื่อใดที่เวลาจริงมีความจำเป็นอย่างแท้จริง

Core questions

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

Key theories

นาฬิกาเชิงตรรกะของ Lamport

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

การซิงโครไนซ์แบบความน่าจะเป็นและแบบไปกลับ

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

โปรโตคอลเวลาเครือข่าย (Network Time Protocol)

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

Clinical relevance

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

History

บทความเกี่ยวกับนาฬิกาเชิงตรรกะของ Lamport ในปี 1978 ได้ปรับแนวคิดเรื่องเวลาในระบบกระจายให้เป็นแนวคิดเชิงสาเหตุมากกว่าเชิงกายภาพ ในขณะเดียวกัน Cristian และคนอื่นๆ ได้พัฒนาการซิงโครไนซ์แบบความน่าจะเป็น และ NTP ของ Mills ได้กลายเป็นกลไกมาตรฐานสำหรับการรักษานาฬิกาอินเทอร์เน็ตให้สอดคล้องกัน

Debates

เวลาเชิงตรรกะเทียบกับเวลาเชิงกายภาพสำหรับการจัดลำดับการทำงาน

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

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

ถ้า a มีการประทับเวลา Lamport ที่น้อยกว่า b แสดงว่า a เกิดขึ้นก่อน b หรือไม่?

ไม่จำเป็นเสมอไป การประทับเวลาที่น้อยกว่าสอดคล้องกับความสัมพันธ์แบบเกิดขึ้นก่อน แต่ไม่ได้หมายความถึงสิ่งนั้น เพราะเหตุการณ์ที่เกิดขึ้นพร้อมกันอาจได้รับการประทับเวลาที่จัดลำดับแล้ว หากต้องการตัดสินความเป็นเหตุเป็นผลอย่างแม่นยำ คุณต้องใช้นาฬิกาแบบเวกเตอร์ (vector clocks) ไม่ใช่นาฬิกาเชิงตรรกะแบบสเกลาร์ (scalar logical clocks)