"เวลา" เป็นหัวข้อนิรันดร์ในช่วงเวลาที่เปลี่ยนแปลง การอภิปรายเกี่ยวกับช่วงเวลานั้นเกิดขึ้นในบล็อกเชนและระบบกระจายอื่นๆ เวลาเชื่อมโยงกระบวนการและโหนด และเรายังใช้ "ความละเอียด" ของเวลาเพื่อวัดเครือข่ายแบบกระจายศูนย์ที่เชื่อมต่อบล็อกเป็นห่วงโซ่

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

stakefish รวบรวมบทความโดยนักวิเคราะห์ Vac และนักพัฒนา ENS Dean Eigenmann โดยแนะนำการอภิปรายของ Lamport เกี่ยวกับเวลา นาฬิกา และคำสั่ง และเตือนให้ทุกคนเข้าใจบล็อกเชนและเวลาของระบบแบบกระจายจากมุมมองอื่น

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

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

เพื่อนที่ไม่คุ้นเคยกับ Leslie Lamport สามารถรับแนวคิดทั่วไปได้ เขามีชื่อเสียงในด้านการสร้าง LaTeX, TLA+, Paxos และยังกล่าวถึงปัญหาทั่วไปของ Byzantine และแน่นอนว่านาฬิกา Lamport (นาฬิกาแบบลอจิคัลตัวแรก) ซึ่งเราจะแนะนำแนวคิดพื้นฐานในบทความนี้ด้วย

ก่อนอื่นมาดูคำจำกัดความของระบบแบบกระจาย คำจำกัดความที่กำหนดโดย Lamport คือ:

"ระบบเรียกว่าระบบกระจาย หากความล่าช้าในการส่งข้อมูลภายในระบบนั้นไม่สำคัญเมื่อเทียบกับเวลาระหว่างเหตุการณ์ในกระบวนการเดียว"

ฉันชอบคำจำกัดความนี้เพราะเน้นที่ความล่าช้าระหว่างการส่งและรับข้อความ

ด้วยคำจำกัดความที่ชัดเจน เราจะเริ่มการแนะนำอย่างเป็นทางการ

ชื่อเรื่องรอง

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

แต่ปัญหานี้ยากกว่ามากในบริบทของระบบกระจาย ทำไม

ทั้งหมดเป็นเพราะลักษณะที่เรียบง่ายมากของระบบแบบกระจาย: หลังจากที่ข้อความถูกส่งระหว่างโหนด ข้อความนั้นอาจมาถึง 0, 1 หรือมากกว่านั้น ณ จุดใดก็ได้ในอนาคต ในกรณีนี้ โหนดต่างๆ ในระบบแบบกระจายไม่สามารถตกลงเวลาได้ ตัวอย่างเช่น:

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

แล้วจะแก้ปัญหานี้อย่างไร?

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

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

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

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

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

ชื่อเรื่องรอง

แต่ตอนนี้เรามีคำสั่งบางส่วนแล้ว เราสามารถเพิ่มนาฬิกาในระบบเพื่อรับลำดับเหตุการณ์ทั้งหมดในระบบ

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

ข้อความ

∀a,b a → b ⟹ C(a) < C(b)

นิพจน์ข้างต้นหมายความว่าอย่างไร

ลูกศร "→" หมายถึง "เกิดขึ้นก่อน (เกิดขึ้นก่อน)" และ C หมายถึงฟังก์ชันนาฬิกา ซึ่งสามารถเข้าใจได้ง่ายๆ ว่าเป็นเวลา เพื่อแสดงความหมายคือ: สำหรับแต่ละเหตุการณ์ a, b ถ้า a เกิดขึ้นก่อน b เวลาของ a จะน้อยกว่าเวลาของ b

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

ในภาพด้านบน เราจะเห็นว่าบนโหนด α มีเหตุการณ์หนึ่งเกิดขึ้นที่เวลา 1 และเวลา 2 ตามลำดับ โหนด β มีหนึ่งเหตุการณ์เกิดขึ้นที่เวลา 1 ของมันเอง เหตุการณ์ ณ เวลา 1 และเวลา 2 ที่โหนด α จะเกิดขึ้นพร้อมกันกับเหตุการณ์ ณ เวลา 1 ที่โหนด β และไม่มีการเชื่อมต่อเชิงสาเหตุ

• ถ้า a และ b เป็นสองเหตุการณ์ในโหนดเดียว และ a เกิดขึ้นก่อน b ดังนั้นเวลาของ a ควรน้อยกว่าเวลาของ b

• ถ้า a เป็นโหนดที่ส่งข้อความ และ b เป็นอีกโหนดที่รับข้อความ ดังนั้นเวลาของ a ควรจะน้อยกว่าเวลาของ b

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

ตัวอย่าง

ตัวอย่าง

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

• เงื่อนไขที่ 1: โหนดที่สามารถเข้าถึงทรัพยากรได้ต้องปล่อยทรัพยากรก่อน โหนดอื่นจึงจะเข้าถึงได้

• เงื่อนไข 2: คำขอทรัพยากรต้องได้รับสิทธิ์การเข้าถึงตามลำดับคำขอ

• เงื่อนไข 3: หากทุก ๆ โหนดที่ได้รับสิทธิ์ในการเข้าถึงปล่อยทรัพยากรในที่สุด ทุกคำขอจะได้รับในที่สุด

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

ดังนั้นเราจึงยังคงต้องสร้างเงื่อนไขเพื่อตอบสนองนาฬิกาตรรกะนี้ เข้าเงื่อนไขยังไง?

Lamport มอบโซลูชันแบบกระจายอำนาจให้กับเรา ขั้นแรก เราต้องการให้โหนดทั้งหมดจัดเก็บคิวคำขอ ประการที่สอง ต้องเป็นไปตามสมมติฐานง่ายๆ:

• สมมติฐานที่ 1: ได้รับข้อความทั้งหมดตามลำดับที่ส่ง

• สมมติฐานที่ 2: ข้อความทั้งหมดจะได้รับในที่สุด

• สมมติฐานที่ 3: ทุก ๆ โหนดสามารถส่งข้อความไปยังโหนดอื่น ๆ ทั้งหมดในระบบได้โดยตรง

หากมีอัลกอริธึมและโปรโตคอลที่ซับซ้อนกว่านี้ ก็สามารถละเว้นสมมติฐานข้างต้นได้

ตอนนี้เราสามารถกำหนดอัลกอริทึมที่ตรงตามเงื่อนไข 3 ข้อนี้และแสดงการทำงานของนาฬิกาในทางปฏิบัติ:

1. หากโหนดต้องการร้องขอทรัพยากร โหนดจะสร้างคำขอตามเวลาปัจจุบัน เพิ่มลงในคิว และส่งไปยังโหนดอื่นๆ ทุกโหนด

2. โหนดอื่นทั้งหมดวางคำขอนี้ไว้ในคิวและส่งข้อความตอบกลับ

3. โหนดที่ปล่อยรีซอร์สส่งข้อความรีลีสพร้อมเวลาปัจจุบันและลบคำขอดั้งเดิมออกจากคิว

4. เมื่อโหนดได้รับข้อความเผยแพร่ โหนดจะล้างคำขอที่เกี่ยวข้องออกจากคิวของตนเอง

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

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

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

ชื่อเดิม: เวลา นาฬิกา และระเบียบ

โดย Dean Eigenmann

ข้อความ