They're funny things, Accidents. You never have them till you're having them.

A.A. Milne, The House at Pooh Corner (1928)

ดังที่ได้กล่าวถึงในหัวข้อ "Reliability and Fault Tolerance" การทำให้ระบบมีความน่าเชื่อถือหมายถึงการทำให้แน่ใจว่าระบบโดยรวมยังคงทำงานได้ต่อไปแม้จะมีสิ่งผิดพลาดเกิดขึ้น (เช่น เมื่อเกิด fault) อย่างไรก็ตาม การคาดการณ์ fault ที่เป็นไปได้ทั้งหมดและจัดการกับมันนั้นไม่ใช่เรื่องง่าย ในฐานะนักพัฒนา มักจะรู้สึกอยากโฟกัสกับ happy path เป็นหลัก (เพราะโดยส่วนใหญ่แล้วทุกอย่างก็ทำงานได้ดี!) และละเลย fault ต่างๆ เนื่องจากมันนำมาซึ่ง edge case มากมาย

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

การทำงานกับระบบกระจายนั้นแตกต่างโดยพื้นฐานจากการเขียนซอฟต์แวร์บนเครื่องเดียว ความแตกต่างหลักคือสิ่งต่างๆ สามารถผิดพลาดได้ในรูปแบบใหม่ๆ ที่น่าตื่นเต้นมากมาย 1 , 2 ]. ในบทนี้ คุณจะได้สัมผัสกับปัญหาที่เกิดขึ้นในทางปฏิบัติและเข้าใจว่าอะไรที่คุณพึ่งพาได้และพึ่งพาไม่ได้

เพื่อทำความเข้าใจความท้าทายที่เราต้องเผชิญ เราจะเพิ่มระดับการมองโลกในแง่ร้ายให้สูงสุดและสำรวจ สิ่งต่างๆ มากมายที่อาจผิดพลาดในระบบกระจาย รวมถึงปัญหาที่เกี่ยวกับเครือข่าย รวมถึง clock และ timing ผลที่ตามมาของปัญหาเหล่านี้ทำให้เกิดความสับสน ดังนั้นเราจะสำรวจวิธีคิดเกี่ยวกับสถานะของระบบกระจาย และวิธีใช้เหตุผลเกี่ยวกับสิ่งที่เกิดขึ้นแล้ว ใน Chapter 10 เราจะดูตัวอย่างบางส่วนเกี่ยวกับวิธีที่เราสามารถทำ fault tolerance เมื่อเผชิญกับเหตุการณ์เหล่านี้

Faults and Partial Failures (Fault และ Partial Failure)

เมื่อคุณเขียนโปรแกรมบนคอมพิวเตอร์เครื่องเดียว โดยปกติแล้วมันจะทำงานในลักษณะที่คาดเดาได้พอสมควร: ไม่ก็ทำงานได้ หรือไม่ก็ทำงานไม่ได้ ซอฟต์แวร์ที่มีบั๊กอาจทำให้ดูเหมือนว่าคอมพิวเตอร์บางครั้ง "มีวันที่แย่" (ปัญหาที่มักแก้ได้ด้วยการรีบูต) แต่นั่นเป็นเพียงผลจากซอฟต์แวร์ที่เขียนมาไม่ดีเท่านั้น

ไม่มีเหตุผลพื้นฐานใดๆ ที่ซอฟต์แวร์บนเครื่องเดียวจะต้องไม่เสถียร เมื่อฮาร์ดแวร์ทำงานถูกต้อง การดำเนินการเดียวกันจะให้ผลลัพธ์เดียวกันเสมอ (มันเป็น deterministic ) หากมีปัญหาฮาร์ดแวร์ (เช่น หน่วยความจำเสียหายหรือขั้วต่อหลวม) ผลที่ตามมามักจะเป็น ระบบล้มเหลวโดยสิ้นเชิง (เช่น kernel panic, "blue screen of death" หรือไม่สามารถเริ่มต้นระบบได้) คอมพิวเตอร์เครื่องเดียวที่มีซอฟต์แวร์ดีมักจะทำงานได้เต็มที่หรือพังไปเลย ไม่ใช่ครึ่งๆ กลางๆ

นี่คือการเลือกโดยเจตนาในการออกแบบคอมพิวเตอร์ หากเกิด fault ภายใน เราชอบให้คอมพิวเตอร์ crash ไปเลย มากกว่าที่จะคืนค่าผิดพลาด เพราะค่าที่ผิดพลาดนั้นยากและทำให้งงงวยในการจัดการ ดังนั้น คอมพิวเตอร์จึงซ่อนความเป็นจริงทางกายภาพที่เลือนลางที่มันทำงานอยู่ และนำเสนอ system model ในอุดมคติที่ทำงานด้วยความสมบูรณ์แบบทางคณิตศาสตร์ คำสั่ง CPU จะทำสิ่งเดิมเสมอ หากคุณเขียนข้อมูลลงในหน่วยความจำหรือดิสก์ ข้อมูลนั้นจะคงอยู่และไม่ถูกทำให้เสียหายแบบสุ่ม ดังที่ได้กล่าวถึงในหัวข้อ "Hardware and Software Faults" ที่จริงแล้วมันไม่เป็นความจริงนัก—ในความเป็นจริง ข้อมูลก็ถูกทำให้เสียหายโดยไม่มีใครรู้ได้ และ CPU บางครั้งก็คืนค่าผิดพลาดโดยไม่มีใครรู้—แต่มันเกิดขึ้นน้อยมากจนเราสามารถเมินเฉยได้

เมื่อคุณเขียนซอฟต์แวร์ที่ทำงานบนคอมพิวเตอร์หลายเครื่องที่เชื่อมต่อกันด้วยเครือข่าย สถานการณ์จะแตกต่างกันโดยพื้นฐาน ในระบบกระจาย fault เกิดขึ้นบ่อยกว่ามากจนเราไม่สามารถเมินเฉยได้อีกต่อไป เราไม่มีทางเลือกอื่นนอกจากต้องเผชิญหน้ากับความเป็นจริงที่ยุ่งเหยิงของโลกทางกายภาพ และในโลกทางกายภาพ มีสิ่งต่างๆ มากมายที่สามารถผิดพลาดได้ ดังที่แสดงในเรื่องเล่านี้ [ 3 ]:

จากประสบการณ์ที่จำกัดของผม ผมเคยเจอ network partition ที่ยาวนานใน data center (DC) เดียว, PDU [power distribution unit] ล้มเหลว, switch ล้มเหลว, การรีบูตทั้ง rack โดยไม่ได้ตั้งใจ, backbone ทั้ง DC ล้มเหลว, ไฟดับทั้ง DC, และคนขับรถที่น้ำตาลตกขับรถ Ford Pickup ชนเข้า ระบบ HVAC [ระบบทำความร้อน ระบายอากาศ และปรับอากาศ] ของ DC และผมก็ไม่ใช่คนดูแลระบบด้วยซ้ำ

Coda Hale

ในระบบกระจาย อาจมีบางส่วนของระบบที่เสียในลักษณะที่คาดเดาไม่ได้ ในขณะที่ส่วนอื่นๆ ของระบบยังทำงานได้ดี เราเรียกสิ่งนี้ว่า partial failure ความยากคือ partial failures นั้น nondeterministic : หากคุณพยายามทำอะไรก็ตามที่เกี่ยวข้องกับหลาย node และเครือข่าย บางครั้งมันก็อาจทำงานได้และบางครั้งก็ล้มเหลวอย่างคาดเดาไม่ได้ ดังที่เราจะได้เห็น คุณอาจไม่ รู้ ด้วยซ้ำว่าสิ่งไหนสำเร็จหรือไม่!

ความไม่แน่นอนและความเป็นไปได้ของ partial failures นี่เองที่ทำให้ระบบกระจายทำงานด้วยยาก [ 4 ]. ในทางกลับกัน หากระบบกระจายสามารถทนต่อ partial failures ได้ มันก็เปิดโอกาสอันทรงพลัง—เช่น เราสามารถทำ rolling upgrade โดยรีบูตทีละ node เพื่อติดตั้งอัปเดตซอฟต์แวร์ในขณะที่ระบบโดยรวมยังคงทำงานได้อย่างต่อเนื่อง ดังนั้น fault tolerance จึงช่วยให้เราสร้างระบบกระจายที่เชื่อถือได้มากกว่าระบบที่มี node เดียว เราสามารถสร้างระบบที่เชื่อถือได้จากส่วนประกอบที่ไม่น่าเชื่อถือ

แต่ก่อนที่เราจะ implement fault tolerance เราจำเป็นต้องรู้เพิ่มเติมเกี่ยวกับ fault ที่เราควรจะทน สิ่งสำคัญคือต้องพิจารณา fault ที่เป็นไปได้หลากหลาย—แม้กระทั่งที่ไม่น่าจะเกิดขึ้น— และสร้างสถานการณ์เหล่านั้นใน environment testing ของคุณเพื่อดูว่าจะเกิดอะไรขึ้น ในระบบกระจาย ความสงสัย การมองโลกในแง่ร้าย และความระแวง ให้ผลตอบแทนที่ดี

Unreliable Networks (เครือข่ายที่ไม่น่าเชื่อถือ)

ในอดีต คอมพิวเตอร์รุ่นเก่าอย่างเมนเฟรมถูกทำให้เชื่อถือได้โดยการทำให้ส่วนประกอบแต่ละส่วนมีความซ้ำซ้อน เช่น การใช้ RAID เพื่อรับมือกับความล้มเหลวของดิสก์แต่ละตัว ดังที่ได้กล่าวถึงในหัวข้อ "Shared-Memory, Shared-Disk, and Shared-Nothing Architectures" ระบบกระจายที่เรามุ่งเน้นในหนังสือเล่มนี้ส่วนใหญ่เป็น shared-nothing systems : กลุ่มของเครื่องที่เชื่อมต่อกันด้วยเครือข่าย แทนที่จะมีความซ้ำซ้อนของส่วนประกอบภายในเครื่องเดียว ระบบ shared-nothing ใช้การจำลองแบบ (replication) ข้ามเครื่องต่างๆ เพื่อความซ้ำซ้อน เครือข่ายเป็นวิธีเดียวที่เครื่องเหล่านี้จะสื่อสารกันได้ เราสมมติว่าแต่ละเครื่องมีหน่วยความจำและดิสก์ของตัวเอง และเครื่องหนึ่งไม่สามารถเข้าถึงหน่วยความจำหรือดิสก์ของอีกเครื่องได้ (ยกเว้นโดยการร้องขอบริการผ่านเครือข่าย) แม้แต่เมื่อมีการแชร์พื้นที่จัดเก็บ เช่น object storage เครื่องต่างๆ ก็สื่อสารกับบริการพื้นที่จัดเก็บที่แชร์กันผ่านเครือข่าย

อินเทอร์เน็ตและเครือข่ายภายใน datacenter ส่วนใหญ่ (มักเป็น Ethernet) เป็น asynchronous packet networks ในเครือข่ายประเภทนี้ node หนึ่งสามารถส่งข้อความ (packet) ไปยังอีก node ได้ แต่เครือข่ายไม่มีการรับประกันว่ามันจะไปถึงเมื่อไหร่หรือจะไปถึงหรือไม่ หากคุณส่งคำขอและคาดหวังการตอบกลับ มีหลายสิ่งที่อาจผิดพลาดได้ (บางส่วนแสดงใน Figure 9-1 ):

• คำขอของคุณอาจสูญหาย (อาจมีคนถอดสายเคเบิลเครือข่าย)

• คำขอของคุณอาจรออยู่ในคิวและจะถูกส่งในภายหลัง (เครือข่ายหรือผู้รับอาจ overloaded)

• node ระยะไกลอาจล้มเหลว (อาจ crash หรือถูกปิดเครื่อง)

• node ระยะไกลอาจหยุดตอบสนองชั่วคราว (อาจกำลังมี GC pause ยาวๆ ดู "Process Pauses" ) แต่จะเริ่มตอบสนองอีกครั้งในภายหลัง

• node ระยะไกลอาจประมวลผลคำขอของคุณแล้ว แต่การตอบกลับสูญหายบนเครือข่าย (อาจมีการตั้งค่า network switch ผิดพลาด)

• node ระยะไกลอาจประมวลผลคำขอของคุณแล้ว แต่การตอบกลับล่าช้าและจะถูกส่งในภายหลัง (เครือข่ายหรือเครื่องของคุณเองอาจ overloaded)

Figure 9-1. หากคุณส่งคำขอและไม่ได้รับการตอบกลับ เป็นไปไม่ได้ที่จะแยกแยะว่า (a) คำขอสูญหาย (b) node ระยะไกลล่ม หรือ (c) การตอบกลับสูญหาย

ผู้ส่งไม่สามารถรู้ได้ด้วยซ้ำว่า packet ถูกส่งถึงหรือไม่ ทางเลือกเดียวคือให้ผู้รับส่งข้อความตอบกลับ ซึ่งอาจสูญหายหรือล่าช้าได้เช่นกัน ปัญหาเหล่านี้แยกไม่ออกจากกันใน asynchronous network ข้อมูลเดียวที่คุณมีคือคุณยังไม่ได้รับการตอบกลับ หากคุณส่งคำขอไปยัง node อื่นและไม่ได้รับการตอบกลับ มันเป็นไป ไม่ได้ ที่จะรู้ว่าทำไม

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

The Limitations of TCP (ข้อจำกัดของ TCP)

Network packets มีขนาดสูงสุด (โดยทั่วไปไม่กี่กิโลไบต์) แต่หลายแอปพลิเคชันจำเป็นต้องส่งข้อความ (คำขอ, การตอบกลับ) ที่ใหญ่เกินกว่าจะใส่ใน packet เดียวได้ แอปพลิเคชันเหล่านี้ส่วนใหญ่ใช้ TCP หรือ Transmission Control Protocol เพื่อสร้าง connection ที่แบ่ง data stream ขนาดใหญ่ออกเป็น packet ย่อยๆ และประกอบกลับเข้าด้วยกันที่ฝั่งรับ

Note

ส่วน ใหญ่ของสิ่งที่เราพูดเกี่ยวกับ TCP ยังใช้ได้กับทางเลือกใหม่อย่าง QUIC รวมถึง Stream Control Transmission Protocol (SCTP) ที่ใช้ใน WebRTC, โปรโตคอล BitTorrent uTP และโปรโตคอล transport อื่นๆ สำหรับการเปรียบเทียบกับ UDP ดู "TCP Versus UDP" .

TCP มักถูกอธิบายว่าให้การส่งที่ "เชื่อถือได้" ในแง่ที่ว่ามันตรวจจับและส่ง packet ที่ตกหล่นซ้ำ ตรวจจับ packet ที่เรียงลำดับผิดและจัดเรียงกลับให้ถูกต้อง และตรวจจับความเสียหายของ packet โดยใช้ checksum อย่างง่าย นอกจากนี้มันยังคำนวณว่าสามารถส่งข้อมูลได้เร็วแค่ไหน เพื่อให้ถ่ายโอนได้เร็วที่สุดโดยไม่ทำให้เครือข่ายหรือ node รับ overloaded สิ่งนี้เรียกว่า congestion control , flow control หรือ backpressure [ 5 ].

เมื่อคุณ "ส่ง" ข้อมูลโดยการเขียนลงใน socket ข้อมูลจะไม่ถูกส่งทันที แต่มันจะถูกวางใน buffer ที่จัดการโดยระบบปฏิบัติการของคุณ เมื่อ congestion control algorithm ตัดสินใจว่ามีความจุพอที่จะส่ง packet ได้ มันจะนำข้อมูลขนาดเท่า packet ถัดไปจาก buffer นั้นและส่งต่อไปยัง network interface packet จะผ่าน switch และ router หลายตัว และในที่สุดระบบปฏิบัติการของ node รับ จะวางข้อมูลของ packet ลงใน receive buffer และส่ง acknowledgment packet กลับไปยังผู้ส่ง จากนั้นระบบปฏิบัติการฝั่งรับจึงแจ้งให้แอปพลิเคชันทราบว่ามีข้อมูลเพิ่มเติมมาถึงแล้ว [ 6 ].

ถ้า TCP ให้ "ความเชื่อถือได้" แล้ว นั่นหมายความว่าเราไม่ต้องกังวลเกี่ยวกับเครือข่ายที่ไม่น่าเชื่อถืออีกต่อไปใช่ไหม? โชคไม่ดีที่มันไม่ใช่แบบนั้น TCP จะตัดสินว่า packet ต้องสูญหายไปถ้าไม่มี acknowledgment มาถึงภายใน timeout ที่กำหนด แต่มันไม่สามารถบอกได้ว่าเป็น packet ขาออกหรือ acknowledgment ที่สูญหาย แม้ว่ามันจะสามารถส่ง packet ซ้ำได้ แต่มันก็ไม่สามารถรับประกันได้ว่า packet ใหม่จะถึงมือผู้รับ (เช่น ถ้าสายเคเบิลเครือข่ายถูกถอดออก TCP ก็เสียบสายคืนให้คุณไม่ได้) ในที่สุด หลังจาก timeout ที่ปรับแต่งได้ มันจะยอมแพ้และส่ง signal error ไปยังแอปพลิเคชัน ความสามารถในการ deduplication และ retransmission ของ TCP ใช้ได้กับ connection เดียวเท่านั้น ดังนั้นถ้าแอปพลิเคชัน reconnect และส่งซ้ำ ข้อมูลอาจถูก dupliated ได้

ถ้า TCP connection ถูกปิดด้วย error—อาจเพราะ node ระยะไกล crash หรือเครือข่ายถูกขัดจังหวะ— โชคไม่ดีที่คุณไม่มีทางรู้ได้ว่าข้อมูลเท่าไหร่ที่ถูกประมวลผลโดย node ระยะไกล [ 6 ]. แม้ว่าคุณจะได้รับ acknowledgment ว่า packet ถูกส่งถึงแล้ว นั่นก็หมายความแค่ว่า kernel ของระบบปฏิบัติการบน node ระยะไกลได้รับมันแล้ว แอปพลิเคชันอาจ crash ก่อนที่จะจัดการกับข้อมูลนั้น ถ้าคุณต้องการแน่ใจว่าคำขอสำเร็จ คุณต้องได้รับการตอบกลับในเชิงบวกจากตัวแอปพลิเคชันเอง [ 7 ].

อย่างไรก็ตาม TCP มีประโยชน์มากเพราะมันมีวิธีที่สะดวกในการส่งและรับข้อความที่มีขนาดใหญ่เกินไป สำหรับ packet เดียว เมื่อ TCP connection ถูกสร้างขึ้นแล้ว คุณยังสามารถใช้มันส่งคำขอและการตอบกลับหลายรายการได้ โดยทั่วไปทำได้โดยการส่ง header ที่ระบุความยาวของข้อความถัดไปเป็นไบต์ ตามด้วยข้อความจริง HTTP และโปรโตคอล RPC จำนวนมาก (ดู "Dataflow Through Services: REST and RPC" ) ทำงานในลักษณะนี้

Network Faults in Practice (Network Fault ในทางปฏิบัติ)

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

• การศึกษาหนึ่งใน datacenter ขนาดกลางพบ network fault ประมาณ 12 ครั้งต่อเดือน โดยครึ่งหนึ่งตัดการเชื่อมต่อเครื่องเดียว และอีกครึ่งหนึ่งตัดการเชื่อมต่อทั้ง rack [ 9 ].

• การศึกษาอีกชิ้นวัดอัตราความล้มเหลวของส่วนประกอบต่างๆ เช่น top-of-rack switch, aggregation switch และ load balancer [ 10 ]. พบว่าการเพิ่มอุปกรณ์เครือข่ายที่ซ้ำซ้อนไม่ได้ลด fault ลงมากเท่าที่คุณอาจคาดหวัง เพราะมันไม่ได้ป้องกันความผิดพลาดของมนุษย์ (เช่น การตั้งค่า switch ผิด) ซึ่งเป็นสาเหตุหลักของการหยุดให้บริการ

• การขัดจังหวะของ fiber link ระยะไกลถูกตำหนิว่าเกิดจากวัว [ 11 ], บีเวอร์ [ 12 ], และฉลาม [ 13 ] (แม้ว่าการกัดของฉลามจะพบน้อยลงเมื่อมีการป้องกันสายเคเบิลใต้ทะเลที่ดีขึ้น [ 14 ]) มนุษย์ก็มักเป็นสาเหตุเช่นกัน เช่น การตั้งค่าผิดพลาดโดยไม่ได้ตั้งใจ [ 15 ], การขโมย [ 16 ], หรือการก่อวินาศกรรม [ 17 ].

• ใน cloud regions ต่างๆ พบว่า round-trip time อาจสูงถึงหลาย นาที ที่เปอร์เซ็นไทล์สูง [ 18 , Table 3]. แม้แต่ใน datacenter เดียวกัน การดีเลย์ของ packet มากกว่าหนึ่งนาทีก็สามารถเกิดขึ้นได้ระหว่างการปรับโครงสร้างเครือข่ายใหม่ ซึ่งถูกกระตุ้นโดยปัญหาระหว่างการอัปเกรดซอฟต์แวร์ของ switch [ 19 ]. ดังนั้นเราจึงต้องสมมติว่าข้อความอาจถูกล่าช้าอย่างไม่มีกำหนด

• บางครั้งการสื่อสารถูกขัดจังหวะบางส่วน ขึ้นอยู่กับว่าคุณกำลังคุยกับใคร—เช่น A และ B สามารถสื่อสารกันได้ และ B และ C สามารถสื่อสารกันได้ แต่ A และ C ไม่สามารถ [ 20 , 21 ]. fault ที่น่าประหลาดใจอื่นๆ รวมถึง network interface ที่บางครั้ง drop inbound packets ทั้งหมด แต่ส่ง outbound packets ได้สำเร็จ [ 22 ]. แค่เพราะ network link ทำงานในทิศทางเดียว ไม่ได้รับประกันว่ามันจะทำงานในทิศทางตรงข้ามด้วย

• แม้แต่การขัดจังหวะเครือข่ายช่วงสั้นๆ ก็สามารถส่งผลกระทบที่ยาวนานกว่าปัญหาต้นเหตุ [ 8 , 20 , 23 ].

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

Network partitions (Network Partition)

คำว่า network partition หรือ netsplit บางครั้งใช้เมื่อส่วนหนึ่งของเครือข่ายถูกตัดขาดจากส่วนที่เหลือเนื่องจาก network fault อย่างไรก็ตาม สิ่งนี้ไม่ได้แตกต่างโดยพื้นฐานจากการขัดจังหวะเครือข่ายประเภทอื่น Network partition ไม่เกี่ยวข้องกับการ shard ของ storage system ซึ่งบางครั้งก็เรียกว่า partitioning (ดู Chapter 7 ).

ถ้าการจัดการ error ของ network fault ไม่ได้ถูกกำหนดและทดสอบ สิ่งที่เลวร้ายตามอำเภอใจอาจเกิดขึ้นได้—เช่น cluster อาจ deadlock และไม่สามารถให้บริการคำขอได้อย่างถาวร แม้ว่าเครือข่ายจะฟื้นตัวแล้ว [ 24 ] หรืออาจลบข้อมูลทั้งหมดของคุณ [ 25 ]. ถ้าซอฟต์แวร์ถูกวางในสถานการณ์ที่ไม่คาดคิด มันอาจทำสิ่งที่คาดไม่ถึงตามอำเภอใจ

การจัดการ network fault ไม่จำเป็นต้องหมายถึง การทน ต่อมัน ถ้าเครือข่ายของคุณปกติค่อนข้างเชื่อถือได้ วิธีการที่ใช้ได้อาจเป็นเพียงการแสดง error message ให้ผู้ใช้เห็นในขณะที่เครือข่ายมีปัญหา อย่างไรก็ตาม คุณจำเป็นต้องรู้ว่าซอฟต์แวร์ของคุณตอบสนองต่อปัญหาเครือข่ายอย่างไร และต้องแน่ใจว่าระบบสามารถกู้คืนจากปัญหาเหล่านั้นได้ การกระตุ้นปัญหาเครือข่ายโดยเจตนาและทดสอบการตอบสนองของระบบอาจเป็นความคิดที่ดี (ดู "Fault injection" ).

Fault Detection (การตรวจจับ Fault)

หลายระบบจำเป็นต้องตรวจหา node ที่มีปัญหาโดยอัตโนมัติ ตัวอย่างเช่น:

• Load balancer ต้องหยุดส่งคำขอไปยัง node ที่ตายแล้ว (เรียกว่า out of rotation ).

• ในฐานข้อมูลกระจายแบบ single-leader replication ถ้า leader ล้มเหลว follower คนใดคนหนึ่งต้องถูกเลื่อนเป็น leader ใหม่ (ดู "Handling Node Outages" ).

โชคไม่ดีที่ความไม่แน่นอนเกี่ยวกับเครือข่ายทำให้ยากที่จะบอกว่า node ทำงานอยู่หรือไม่ ในบางสถานการณ์ คุณอาจได้รับ feedback ที่บอกคุณอย่างชัดเจนว่าบางอย่างไม่ทำงาน:

• ถ้าคุณสามารถเข้าถึงเครื่องที่ node ควรรันอยู่ได้ แต่ไม่มี process ใดกำลังฟังที่ port ปลายทาง (เช่น เพราะ process crash) ระบบปฏิบัติการจะช่วยปิดหรือปฏิเสธ TCP connections โดยการส่ง RST หรือ FIN packet กลับมา

• ถ้า node process crash (หรือถูก kill โดยผู้ดูแลระบบ) แต่ระบบปฏิบัติการของ node ยังทำงานอยู่ สคริปต์สามารถแจ้ง node อื่นๆ เกี่ยวกับ crash เพื่อให้ node อื่นเข้ามาทำงานแทนได้อย่างรวดเร็ว โดยไม่ต้องรอให้ timeout หมดอายุ ตัวอย่างเช่น HBase ทำเช่นนี้ [ 26 ].

• ถ้าคุณสามารถเข้าถึง management interface ของ network switches ใน datacenter คุณสามารถสอบถามเพื่อตรวจจับ link failure ที่ระดับฮาร์ดแวร์ (เช่น ถ้าเครื่องระยะไกลถูกปิด) ตัวเลือกนี้ใช้ไม่ได้ถ้าคุณเชื่อมต่อผ่านอินเทอร์เน็ต อยู่ใน datacenter ที่แชร์กันโดยไม่สามารถเข้าถึง switch ได้ หรือไม่สามารถเข้าถึง management interface ได้เนื่องจากปัญหาเครือข่าย

• ถ้า router แน่ใจว่า IP address ที่คุณพยายามเชื่อมต่อนั้นไม่สามารถเข้าถึงได้ มันอาจตอบกลับด้วย ICMP Destination Unreachable packet อย่างไรก็ตาม router ก็ไม่มีความสามารถวิเศษในการตรวจจับความล้มเหลวเช่นกัน มันก็มีข้อจำกัดเดียวกันกับผู้เข้าร่วมอื่นๆ ในเครือข่าย

Feedback ที่รวดเร็วเกี่ยวกับ node ระยะไกลที่ล่มนั้นมีประโยชน์ แต่คุณไม่สามารถพึ่งพามันได้ทั้งหมด ถ้ามีอะไรผิดพลาด คุณอาจได้รับ error response ในบางระดับของ stack แต่โดยทั่วไปคุณต้องสมมติว่าคุณจะไม่ได้รับการตอบกลับเลย คุณสามารถลองอีกสองสามครั้ง รอให้ timeout ผ่านไป และในที่สุดก็ประกาศว่า node ตายแล้วถ้าคุณไม่ได้รับการตอบกลับภายใน timeout เนื่องจาก node อาจยังมีชีวิตอยู่ คุณต้องหาสมดุลระหว่าง false positives และ false negatives: timeout ที่สั้นเกินไปจะทำให้ node ที่ยังมีชีวิตถูกสงสัยว่าตายอย่างไม่ถูกต้อง และ timeout ที่ยาวเกินไปจะทำให้เกิดความล่าช้าโดยไม่จำเป็นในการรอ node ที่ตายแล้ว

Timeouts and Unbounded Delays (Timeout และความล่าช้าที่ไม่มีขอบเขต)

ถ้า timeout เป็นวิธีเดียวที่แน่นอนในการตรวจจับ fault แล้ว timeout ควรนานแค่ไหน? โชคไม่ดีที่ไม่มีคำตอบง่ายๆ

timeout ที่นานหมายถึงการรอนานจนกว่า node จะถูกประกาศว่าตาย (และในช่วงเวลานี้ ผู้ใช้อาจต้องรอหรือเห็น error messages) timeout ที่สั้นตรวจจับ fault ได้เร็ว แต่มีความเสี่ยงสูงที่จะประกาศว่า node ตายอย่างไม่ถูกต้อง ทั้งที่จริงแล้วมันแค่ช้าลงชั่วคราว (เช่น เพราะ load spike ที่ node หรือเครือข่าย)

การประกาศว่า node ตายก่อนเวลาอันควรเป็นปัญหา ถ้า node ยังมีชีวิตอยู่และกำลังดำเนินการบางอย่าง (เช่น ส่งอีเมล) และอีก node เข้ามาทำงานแทน การดำเนินการนั้นอาจถูกทำซ้ำสองครั้ง เราจะพูดถึงปัญหานี้โดยละเอียดใน "Knowledge, Truth, and Lies" และในบทที่ 10 และ 12 .

เมื่อ node ถูกประกาศว่าตาย ความรับผิดชอบของมันต้องถูกโอนไปยัง node อื่น ซึ่งทำให้เกิดโหลดเพิ่มเติมบน node เหล่านั้นและเครือข่าย ถ้าระบบกำลังดิ้นรนกับโหลดสูงอยู่แล้ว การประกาศ node ตายก่อนเวลาอันควรอาจทำให้ปัญหาแย่ลง โดยเฉพาะอย่างยิ่ง มันอาจเกิดขึ้นได้ที่ node จริงๆ แล้วไม่ได้ตาย แต่แค่ตอบสนองช้าเพราะ overload การโอนถ่ายโหลดไปยัง node อื่นอาจทำให้เกิด cascading failure (ในกรณีที่รุนแรงที่สุด node ทั้งหมดจะประกาศว่ากันและกันตาย และทุกอย่างหยุดทำงาน—ดู "When an Overloaded System Won't Recover" ).

ลองนึกภาพระบบสมมติที่มีเครือข่ายที่รับประกันการดีเลย์สูงสุดของ packet ทุก packet จะถูกส่งภายในเวลา d หรือสูญหาย และการส่งไม่เคยใช้เวลานานกว่า d . นอกจากนี้ สมมติว่าคุณสามารถรับประกันได้ว่า node ที่ไม่ล้มเหลวมักจะจัดการคำขอภายในเวลา r . ในกรณีนี้ คุณสามารถรับประกันได้ว่าทุกคำขอที่สำเร็จจะได้รับการตอบกลับภายในเวลา 2 d  +  r —และถ้าคุณไม่ได้รับการตอบกลับภายในเวลานั้น คุณรู้ว่าเครือข่ายหรือ node ระยะไกลไม่ทำงาน ถ้านี่เป็นจริง 2 d  +  r จะเป็น timeout ที่เหมาะสม

โชคไม่ดีที่ระบบส่วนใหญ่ที่เราทำงานด้วยไม่มีการรับประกันเหล่านั้น Asynchronous networks มี unbounded delays (พวกมันพยายามส่ง packet ให้เร็วที่สุด แต่ไม่มีขีดจำกัดสูงสุดของเวลาที่ packet อาจใช้ไป) และการ implement เซิร์ฟเวอร์ส่วนใหญ่ไม่สามารถรับประกันว่าพวกมันจะจัดการคำขอภายในเวลาสูงสุดได้ (ดู "Provididng response time guarantees" ). สำหรับการตรวจจับความล้มเหลว แค่ระบบส่วนใหญ่ทำงานเร็วไม่พอ: ถ้า timeout ของคุณต่ำ การเพิ่มขึ้นชั่วคราวของ round-trip time ก็พอที่จะทำให้ระบบเสียสมดุลได้

Network congestion and queueing (การจราจรคับคั่งในเครือข่ายและการเข้าคิว)

เวลาที่ใช้ในการขับรถบนถนนมักแปรผันมากที่สุดเนื่องจากปัญหาการจราจรติดขัด ในทำนองเดียวกัน ความแปรปรวนของการดีเลย์ของ packet ในเครือข่ายคอมพิวเตอร์ส่วนใหญ่มักเกิดจากการ queueing [ 27 ]:

• ถ้าหลาย node พยายามส่ง packet ไปยังปลายทางเดียวกันพร้อมกัน network switch ต้องจัดคิวและส่งไปยัง network link ของปลายทางทีละอัน (ดังแสดงใน Figure 9-2 ). ใน network link ที่ไม่ว่าง packet อาจต้องรอสักพักกว่าจะได้ช่องส่ง (สิ่งนี้เรียกว่า network congestion ). ถ้ามีข้อมูลขาเข้ามากจน switch queue เต็ม packet จะถูก drop ดังนั้นจึงต้องส่งใหม่—แม้ว่าเครือข่ายจะทำงานปกติก็ตาม

• เมื่อ packet ถึงเครื่องปลายทาง ถ้า CPU cores หรือ application threads ทั้งหมดกำลังยุ่งอยู่ คำขอขาเข้าจากเครือข่ายจะถูก queue โดยระบบปฏิบัติการจนกว่าแอปพลิเคชันจะพร้อมจัดการ ขึ้นอยู่กับโหลดบนเครื่อง สิ่งนี้อาจใช้เวลานานตามอำเภอใจ [ 28 ].

• ในสภาพแวดล้อม virtualized ระบบปฏิบัติการที่กำลังรันมักถูกหยุดชั่วคราวเป็นสิบๆ มิลลิวินาที ในขณะที่ virtual machine (VM) อื่นใช้ CPU core ในช่วงเวลานี้ VM ไม่สามารถรับข้อมูลจากเครือข่ายได้ ดังนั้นข้อมูลขาเข้าจะถูก queue (buffered) โดย VM monitor [ 29 ] ซึ่งยิ่งเพิ่มความแปรปรวนของการดีเลย์ของเครือข่าย

• ดังที่กล่าวไว้ก่อนหน้านี้ เพื่อหลีกเลี่ยงการทำให้เครือข่าย overloaded TCP จะจำกัดอัตราการส่งข้อมูล ซึ่งหมายถึงมีการ queueing เพิ่มเติมที่ฝั่งผู้ส่ง ก่อนที่ข้อมูลจะเข้าสู่เครือข่ายด้วยซ้ำ

Figure 9-2. ถ้าเครื่องหลายเครื่องส่ง traffic เครือข่ายไปยังปลายทางเดียวกัน switch queue ของมันอาจเต็ม ที่นี่พอร์ต 1, 2, และ 4 ต่างพยายามส่ง packet ไปยังพอร์ต 3

นอกจากนี้ เมื่อ TCP ตรวจจับและส่ง packet ที่สูญหายซ้ำโดยอัตโนมัติ แอปพลิเคชันจะไม่เห็นการสูญเสีย packet โดยตรง แต่จะเห็นการดีเลย์ที่เกิดขึ้น (รอ ให้ timeout หมดอายุ แล้วรอให้ packet ที่ส่งซ้ำได้รับการ ยืนยัน ).

TCP Versus UDP (TCP กับ UDP)

แอปพลิเคชันที่ไวต่อ latency บางประเภท เช่น videoconferencing และ Voice over IP (VoIP) ใช้ UDP แทน TCP ตัวเลือกนี้เป็นการแลกเปลี่ยนระหว่างความน่าเชื่อถือและความแปรปรวนของการดีเลย์: เนื่องจาก UDP ไม่ทำ flow control และไม่ส่ง packet ที่สูญหายซ้ำ มันจึงหลีกเลี่ยงสาเหตุบางประการของการดีเลย์ของเครือข่ายที่แปรปรวน (แม้ว่ามันจะยังคงได้รับผลกระทบจาก switch queues และ scheduling delays)

UDP เป็นตัวเลือกที่ดีเมื่อข้อมูลที่ล่าช้าไม่มีค่า ตัวอย่างเช่น ในการโทรศัพท์ VoIP อาจไม่มีเวลาเพียงพอที่จะส่ง packet ที่สูญหายซ้ำ ก่อนที่ข้อมูลจะต้องถูกเล่นผ่านลำโพง ในกรณีนี้ ไม่มีประโยชน์ที่จะส่ง packet ซ้ำ แอปพลิเคชันต้องเติมช่วงเวลาของ packet ที่หายไปด้วย silence (ทำให้เกิดการขัดจังหวะสั้นๆ ในเสียง) และดำเนินการต่อใน stream การลองใหม่เกิดขึ้นที่ชั้นมนุษย์แทน ("ช่วยพูดอีกครั้งได้ไหมคะ? เสียงขาดหายไปชั่วครู่")

Variability of network delays (ความแปรปรวนของการดีเลย์ของเครือข่าย)

ปัจจัยทั้งหมดเหล่านี้ส่งผลให้เกิดความแปรปรวนของการดีเลย์ของเครือข่าย การดีเลย์จากการ queueing มีช่วงที่กว้างเป็นพิเศษเมื่อระบบใกล้ความจุสูงสุด ระบบที่มีความจุเหลือเฟือสามารถระบาย queue ได้ง่าย ในขณะที่ระบบที่มีการใช้งานสูง queue ยาวสามารถสะสมได้อย่างรวดเร็ว

ใน public clouds และ multitenant datacenters ทรัพยากรถูกแชร์ระหว่างลูกค้าหลายราย network links และ switches รวมถึง network interface และ CPUs ของแต่ละเครื่อง (เมื่อรันบน VM) ถูกแชร์ การประมวลผลข้อมูลจำนวนมากสามารถใช้ความจุทั้งหมดของ network links (ทำให้มัน saturate ) เนื่องจากคุณไม่สามารถควบคุมหรือมองเห็นการใช้งานทรัพยากรที่แชร์ของลูกค้ารายอื่น การดีเลย์ของเครือข่ายจึงสามารถแปรผันได้สูงถ้ามีคนใกล้คุณ (noisy neighbor ) ใช้ทรัพยากรจำนวนมาก [ 30 , 31 ].

ในสภาพแวดล้อมเช่นนี้ คุณสามารถเลือก timeout ได้โดยการทดลองเท่านั้น: วัดการกระจายของ round-trip time ของเครือข่ายในช่วงเวลาที่ยาวนาน และบนเครื่องหลายๆ เครื่อง เพื่อกำหนดความแปรปรวนที่คาดหวังของการดีเลย์ จากนั้น เมื่อพิจารณาลักษณะของแอปพลิเคชันของคุณ คุณสามารถกำหนดการแลกเปลี่ยนที่เหมาะสมระหว่าง failure detection delay และความเสี่ยงของ premature timeout

ยิ่งไปกว่านั้น แทนที่จะใช้ timeout แบบคงที่ที่กำหนดค่าไว้ ระบบสามารถวัด response times และความแปรปรวนของมัน ( jitter ) อย่างต่อเนื่อง และปรับ timeout โดยอัตโนมัติตามการกระจายของ response time ที่สังเกตได้ Phi Accrual failure detector [ 32 ] (ที่ใช้ใน Akka และ Cassandra [ 33 ]) เป็นวิธีหนึ่งในการทำเช่นนี้ TCP retransmission timeouts ก็ทำงานคล้ายกัน [ 5 ].

Synchronous Versus Asynchronous Networks (เครือข่ายแบบ Synchronous กับ Asynchronous)

ระบบกระจายจะง่ายกว่ามากถ้าเราสามารถพึ่งพาเครือข่ายให้ส่ง packet ด้วยการดีเลย์สูงสุดคงที่ และไม่ drop packet ทำไมเราถึงไม่แก้ปัญหานี้ที่ระดับฮาร์ดแวร์ และทำให้เครือข่ายเชื่อถือได้เพื่อให้ซอฟต์แวร์ไม่ต้องกังวลเกี่ยวกับมัน?

เพื่อตอบคำถามนี้ เป็นเรื่องน่าสนใจที่จะเปรียบเทียบเครือข่าย datacenter กับเครือข่ายโทรศัพท์แบบ fixed-line แบบดั้งเดิม (non-cellular, non-VoIP) ซึ่งเชื่อถือได้อย่างมาก: audio frames ที่ล่าช้าและการโทรที่ขาดหายนั้นหายากมาก การโทรศัพท์ต้องการ latency ปลายทางถึงปลายทางที่ต่ำอย่างสม่ำเสมอและ bandwidth เพียงพอ ในการถ่ายโอนตัวอย่างเสียงของคุณ มันจะดีไม่ใช่เหรอถ้าเครือข่ายคอมพิวเตอร์ มีความน่าเชื่อถือและคาดเดาได้ในลักษณะเดียวกัน?

เมื่อคุณโทรผ่านเครือข่ายโทรศัพท์ มันจะสร้าง circuit : จำนวน bandwidth ที่คงที่และรับประกันถูกจัดสรรให้กับการโทรตลอดเส้นทางระหว่างผู้โทรสองคน circuit นี้ยังคงอยู่จนกว่าการโทรจะสิ้นสุด [ 34 ]. ตัวอย่างเช่น เครือข่าย ISDN ทำงานที่อัตราคงที่ 4,000 frames ต่อวินาที เมื่อมีการสร้างสาย จะถูกจัดสรรพื้นที่ 16 bits ภายในแต่ละ frame (ในแต่ละทิศทาง) ดังนั้น ตลอดระยะเวลาการโทร แต่ละฝ่ายรับประกันว่าจะสามารถส่งข้อมูลเสียง 16 bits ทุกๆ 250 ไมโครวินาที [ 35 ].

เครือข่ายประเภทนี้คือ synchronous : แม้ว่าข้อมูลจะผ่าน router หลายตัว มันก็ไม่ได้รับผลกระทบจากการ queueing เพราะพื้นที่ 16 bits สำหรับการโทรถูกจองไว้แล้วใน hop ถัดไปของเครือข่าย และเนื่องจากไม่มี queueing latency ปลายทางถึงปลายทางสูงสุดของเครือข่ายจึงคงที่ เราเรียกสิ่งนี้ว่า bounded delay .

Can we not simply make network delays predictable? (เราทำให้การดีเลย์ของเครือข่ายคาดเดาได้ไม่ได้หรือ?)

สังเกตว่า circuit ในเครือข่ายโทรศัพท์แตกต่างจาก TCP connection อย่างมาก circuit มีจำนวน bandwidth ที่ถูกจองไว้คงที่ซึ่งไม่มีใครอื่นสามารถใช้ได้ตราบเท่าที่มันถูกสร้างขึ้น ในขณะที่ packet ของ TCP connection ใช้ bandwidth ที่มีอยู่ตามโอกาส คุณสามารถให้ TCP มี block ของข้อมูลที่มีขนาดแปรผัน (เช่น อีเมลหรือหน้าเว็บ) และมันจะพยายามถ่ายโอนในเวลาที่สั้นที่สุดเท่าที่เป็นไปได้ ในขณะที่ TCP connection ไม่ได้ใช้งาน มันก็ไม่ใช้ bandwidth ใดๆ (ยกเว้น occasional keepalive packet)

ถ้าเครือข่าย datacenter และอินเทอร์เน็ตเป็นเครือข่าย circuit-switched มันจะเป็นไปได้ที่จะสร้างการรับประกัน round-trip time สูงสุดเมื่อมีการตั้ง circuit แต่มันไม่ใช่ Ethernet และ IP เป็นโปรโตคอล packet-switched ซึ่งประสบปัญหาการ queueing และทำให้เกิด unbounded delays ในเครือข่าย โปรโตคอลเหล่านี้ไม่มีแนวคิดของ circuit

ทำไมเครือข่าย datacenter และอินเทอร์เน็ตถึงใช้ packet switching? คำตอบคือพวกมันถูกปรับให้เหมาะสมสำหรับ bursty traffic . circuit เหมาะสำหรับการโทรด้วยเสียงหรือวิดีโอ ซึ่งต้องการถ่ายโอนจำนวน bits ต่อวินาทีที่ค่อนข้างคงที่ตลอดระยะเวลาการโทร ในทางกลับกัน การร้องขอหน้าเว็บ การส่งอีเมล หรือการถ่ายโอนไฟล์ ไม่มีความต้องการ bandwidth ที่เฉพาะเจาะจง—เราแค่ต้องการให้มันเสร็จโดยเร็วที่สุด

ถ้าคุณต้องการถ่ายโอนไฟล์ผ่าน circuit คุณต้องเดาการจัดสรร bandwidth ถ้าคุณเดาต่ำเกินไป การถ่ายโอนจะช้าโดยไม่จำเป็น ทำให้ความจุเครือข่ายไม่ได้ใช้ ถ้าคุณเดาสูงเกินไป circuit จะไม่สามารถตั้งได้ (เพราะเครือข่ายไม่อนุญาตให้สร้าง circuit ถ้าการจัดสรร bandwidth ไม่สามารถรับประกันได้) ในทางตรงกันข้าม TCP จะปรับอัตราการถ่ายโอนข้อมูลให้เข้ากับความจุเครือข่ายที่มีอยู่แบบไดนามิก

Latency and Resource Utilization (Latency และการใช้ทรัพยากร)

โดยทั่วไปแล้ว คุณสามารถคิดว่าการดีเลย์ที่แปรปรวนเป็นผลมาจากการแบ่งปันทรัพยากรแบบไดนามิก

สมมติว่าคุณมีสาย (หรือ fiber) ระหว่าง switch โทรศัพท์สองตัว ที่สามารถรองรับการโทรพร้อมกันได้ถึง 10,000 สาย แต่ละ circuit ที่ถูกสวิตซ์ผ่านสายนี้จะครอบครองหนึ่งในช่องสัญญาณเหล่านั้น ดังนั้นคุณสามารถคิดว่าสายเป็นทรัพยากรที่สามารถแชร์โดยผู้ใช้พร้อมกันสูงสุด 10,000 คน ทรัพยากรถูกแบ่งในลักษณะ static : แม้ว่าคุณจะเป็นสายโทรเดียวบนสายนี้ในตอนนี้ และอีก 9,999 ช่องไม่ได้ใช้ circuit ของคุณก็ยังได้รับการจัดสรร bandwidth คงที่เท่าเดิม เท่ากับเมื่อสายถูกใช้อย่างเต็มที่

ในทางตรงกันข้าม อินเทอร์เน็ตแชร์ bandwidth ของเครือข่ายแบบ dynamic . ผู้ส่งผลักและเบียดกันเพื่อส่ง packet ของตนผ่านสายโดยเร็วที่สุด และ network switches ตัดสินใจว่าจะส่ง packet ใด (นั่นคือการจัดสรร bandwidth) ในแต่ละขณะ วิธีการนี้มีข้อเสียคือการ queueing แต่ข้อดีคือมันใช้ประโยชน์จากสายได้สูงสุด สายมีต้นทุนคงที่ ดังนั้นถ้าคุณใช้มันได้ดีขึ้น แต่ละ byte ที่คุณส่งผ่านมันจะถูกลง

สถานการณ์คล้ายกันเกิดขึ้นกับ CPUs ถ้าคุณแชร์แต่ละ CPU core แบบไดนามิกระหว่างหลาย thread thread หนึ่งบางครั้งต้องรอใน run queue ของระบบปฏิบัติการในขณะที่อีก thread กำลังทำงาน ดังนั้น thread อาจถูกหยุดชั่วคราวเป็นระยะเวลาที่แตกต่างกัน [ 36 ]. อย่างไรก็ตาม สิ่งนี้ใช้ประโยชน์จากฮาร์ดแวร์ได้ดีกว่า การจัดสรรจำนวน CPU cycles แบบคงที่ให้แต่ละ thread (ดู "Provididng response time guarantees" ). การใช้ฮาร์ดแวร์ที่ดีขึ้นนี้ยังเป็นเหตุผลที่ cloud platforms รัน VM หลายเครื่องจากลูกค้าต่างกันบนเครื่องกายภาพเดียวกัน

การรับประกัน latency เป็นสิ่งที่ทำได้ในบางสภาพแวดล้อม ถ้าทรัพยากรถูกแบ่งส่วนแบบคงที่ (เช่น ฮาร์ดแวร์เฉพาะและการจัดสรร bandwidth แบบเอกสิทธิ์) อย่างไรก็ตาม การรับประกันเหล่านี้มาพร้อมกับต้นทุนของการใช้งานที่ลดลง —กล่าวคือมันแพงกว่า ในทางกลับกัน multitenancy ที่มีการแบ่งปันทรัพยากรแบบไดนามิกให้การใช้งานที่ดีกว่า ดังนั้นมันถูกกว่า แต่มีข้อเสียคือการดีเลย์ที่แปรปรวน

การดีเลย์ที่แปรปรวนในเครือข่ายไม่ใช่กฎของธรรมชาติ แต่เป็นเพียงผลลัพธ์ของการแลกเปลี่ยนระหว่างต้นทุนและประโยชน์

Combining circuit switching and packet switching (การรวม circuit switching และ packet switching)

มี ความพยายามบางอย่างในการสร้างเครือข่ายแบบไฮบริดที่รองรับทั้ง circuit switching และ packet switching Asynchronous Transfer Mode (ATM) เป็นคู่แข่งของ Ethernet ในยุค 1980 แต่มันไม่ได้รับการนำมาใช้มากนักนอกเหนือจาก switch หลักของเครือข่ายโทรศัพท์ InfiniBand มีความคล้ายคลึงกันบางอย่าง [ 37 ]: มัน implement end-to-end flow control ที่ link layer ซึ่งลดความจำเป็นในการ queueing ในเครือข่าย แม้ว่ามันยังคงประสบกับการดีเลย์เนื่องจาก link congestion [ 38 ].

ด้วยการใช้ quality of service (QoS) อย่างระมัดระวัง เช่น การจัดลำดับความสำคัญและการจัดตาราง packet และ admission control (การจำกัดอัตราผู้ส่ง) เป็นไปได้ที่จะจำลอง circuit switching บน packet networks หรือให้ statistically bounded delay [ 27 , 34 ]. อัลกอริทึมเครือข่ายใหม่เช่น Low Latency, Low Loss, and Scalable Throughput (L4S) พยายามบรรเทาปัญหา queueing และ congestion control ทั้งที่ระดับ client และ router Linux's traffic controller (TC) ยังช่วยให้แอปพลิเคชันจัดลำดับความสำคัญของ packet ใหม่เพื่อวัตถุประสงค์ QoS

อย่างไรก็ตาม กลไก QoS ดังกล่าวยังไม่ได้เปิดใช้งานใน multitenant datacenters และ public clouds หรือเมื่อสื่อสารผ่านอินเทอร์เน็ต เทคโนโลยีที่ใช้งานอยู่ในปัจจุบันไม่อนุญาตให้เราทำ การรับประกันใดๆ เกี่ยวกับการดีเลย์หรือความน่าเชื่อถือของเครือข่าย เราต้องสมมติว่า network congestion, queueing และ unbounded delays จะเกิดขึ้น ดังนั้นจึงไม่มีค่าที่ "ถูกต้อง" สำหรับ timeout —พวกมันจำเป็นต้องถูกกำหนดโดยการทดลอง

ข้อตกลง peering ระหว่างผู้ให้บริการอินเทอร์เน็ตและการสร้างเส้นทางผ่าน Border Gateway Protocol (BGP) มีความคล้ายคลึงกับ circuit switching มากกว่าการ route IP packet ทั่วไป ในระดับนี้ เป็นไปได้ที่จะซื้อ bandwidth โดยเฉพาะ อย่างไรก็ตาม การ route อินเทอร์เน็ตทำงานที่ระดับเครือข่าย ไม่ใช่การเชื่อมต่อระหว่างโฮสต์ และในมาตราส่วนเวลาที่ยาวกว่ามาก

Unreliable Clocks (Clock ที่ไม่น่าเชื่อถือ)

Clock และเวลามีความสำคัญ แอปพลิเคชันขึ้นอยู่กับ clock ในหลายวิธี เพื่อตอบคำถามเช่น:

1. คำขอนี้ timeout แล้วหรือยัง?

2. percentile ที่ 99 ของ response time ของบริการนี้คือเท่าไหร่?

3. บริการนี้จัดการ query ต่อวินาทีโดยเฉลี่ยเท่าไหร่ในห้านาทีที่ผ่านมา?

4. ผู้ใช้ใช้เวลาบนเว็บไซต์ของเรานานเท่าไหร่?

5. บทความนี้ถูกเผยแพร่เมื่อไหร่?

6. ควรส่งอีเมลเตือนความจำในวันและเวลาใด?

7. cache entry นี้หมดอายุเมื่อไหร่?

8. timestamp ใน error message ในไฟล์ log นี้คืออะไร?

คำถามข้อ 1–4 วัด duration (เช่น ช่วงเวลาระหว่างการส่งคำขอและการได้รับการตอบกลับ) ในขณะที่คำถามข้อ 5–8 อธิบาย จุดในเวลา (เหตุการณ์ที่เกิดขึ้นในวันที่และเวลาที่กำหนด)

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

ยิ่งไปกว่านั้น แต่ละเครื่องบนเครือข่ายมี clock ของตัวเอง ซึ่งเป็นอุปกรณ์ฮาร์ดแวร์—โดยทั่วไปคือ crystal oscillator แบบ quartz อุปกรณ์เหล่านี้ไม่แม่นยำสมบูรณ์แบบ ดังนั้นแต่ละเครื่องจึงมีแนวคิดเรื่องเวลาของตัวเอง ซึ่งอาจเร็วกว่าหรือช้ากว่าเครื่องอื่นเล็กน้อย เป็นไปได้ที่จะซิงโครไนซ์ clock ในระดับหนึ่ง กลไกที่ใช้กันมากที่สุดคือ Network Time Protocol (NTP) ซึ่งช่วยให้ clock ของคอมพิวเตอร์ถูกปรับตามเวลาที่รายงานโดยกลุ่มเซิร์ฟเวอร์ [ 39 ]. เซิร์ฟเวอร์เหล่านั้นได้รับเวลาจากแหล่งเวลาที่แม่นยำกว่า เช่น GPS receiver

Monotonic Versus Time-of-Day Clocks (Monotonic Clock กับ Time-of-Day Clock)

คอมพิวเตอร์สมัยใหม่มี clock อย่างน้อยสองประเภท: time-of-day clock และ monotonic clock แม้ว่าทั้งคู่วัดเวลา สิ่งสำคัญคือต้องแยกแยะระหว่างมัน เพราะมันมีวัตถุประสงค์ต่างกัน

Time-of-day clocks

Time-of-day clock ทำในสิ่งที่คุณคาดหวังโดยสัญชาตญาณจาก clock: มันคืนวันที่และเวลาปัจจุบันตาม ปฏิทิน (หรือที่เรียกว่า wall-clock time ). ตัวอย่างเช่น clock_gettime(CLOCK_REALTIME) บน Linux และ System.currentTimeMillis ใน Java คืนจำนวนวินาที (หรือมิลลิวินาที) ตั้งแต่ epoch ซึ่งกำหนดเป็นเที่ยงคืน UTC ของวันที่ 1 มกราคม 1970 ตามปฏิทิน Gregorian ไม่นับ leap seconds บางระบบใช้วันที่อื่นเป็นจุดอ้างอิง (แม้ว่า Linux clock จะถูกเรียกว่า real-time แต่มันไม่เกี่ยวข้องกับ real-time operating systems ดังที่กล่าวถึงใน "Provididng response time guarantees" .)

Time-of-day clocks มักถูกซิงโครไนซ์ด้วย NTP ซึ่งหมายความว่า timestamp จากเครื่องหนึ่ง (ในอุดมคติ) หมายถึงสิ่งเดียวกับ timestamp บนอีกเครื่องหนึ่ง อย่างไรก็ตาม time-of-day clocks ก็มีลักษณะแปลกๆ ต่างๆ ดังที่อธิบายในหัวข้อถัดไป โดยเฉพาะอย่างยิ่ง ถ้า local clock เร็วเกินไปเมื่อเทียบกับ NTP server มันอาจถูกรีเซ็ตแบบบังคับและดูเหมือนกระโดดกลับไปยังจุดในเวลาก่อนหน้า การกระโดดเหล่านี้ รวมถึงการกระโดดที่คล้ายกันที่เกิดจาก leap seconds ทำให้ time-of-day clocks ไม่เหมาะสำหรับการวัดเวลาที่ผ่านไป [ 40 ].

Time-of-day clocks ยังสามารถกระโดดได้เนื่องจากการเริ่มต้นและสิ้นสุดของ Daylight Saving Time (DST) แม้ว่าสิ่งนี้สามารถหลีกเลี่ยงได้โดยการใช้ UTC เป็น time zone เสมอ ซึ่งไม่มี DST ในอดีต clock เหล่านี้มีความละเอียดค่อนข้างหยาบ (เช่น เคลื่อนที่ไปข้างหน้าเป็นขั้นๆ ละ 10 ms บน Windows รุ่นเก่า [ 41 ]). ในระบบสมัยใหม่ ปัญหานี้มีน้อยลง

Monotonic clocks

Monotonic clock เหมาะสำหรับการวัด duration (ช่วงเวลา) เช่น timeout หรือ response time ของบริการ clock_gettime(CLOCK_MONOTONIC) หรือ clock_gettime(CLOCK_BOOTTIME) บน Linux [ 42 ] และ System.nanoTime ใน Java วัดเวลาโดยใช้ monotonic clock ชื่อนี้มาจากความจริงที่ว่า clock ประเภทนี้รับประกันว่าจะเดินไปข้างหน้าเสมอ (ในขณะที่ time-of-day clock อาจกระโดดกลับในเวลา)

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

บนเซิร์ฟเวอร์ที่มี CPU sockets หลายตัว อาจมี timer แยกต่อ CPU ซึ่งไม่จำเป็นต้องซิงโครไนซ์กับ CPU อื่น [ 43 ]. ระบบปฏิบัติการชดเชยความคลาดเคลื่อนใดๆ และพยายามนำเสนอมุมมองแบบ monotonic ของ clock ให้กับ application threads แม้ว่าพวกมันจะถูกจัดตารางข้ามหลาย CPU ก็ตาม อย่างไรก็ตาม ควรใช้การรับประกัน monotonicity นี้ด้วยความไม่ไว้ใจบ้าง [ 44 ].

NTP อาจปรับความถี่ที่ monotonic clock เดินไปข้างหน้า (เรียกว่า slewing clock) ถ้ามันตรวจพบว่า quartz ในเครื่องเดินเร็วหรือช้ากว่า NTP server โดยค่าเริ่มต้น NTP อนุญาตให้อัตรา clock ถูกเร่งหรือชะลอลงได้สูงสุด 0.05% แต่มันไม่สามารถทำให้ monotonic clock กระโดดไปข้างหน้าหรือถอยหลังได้ ความละเอียดของ monotonic clocks มักจะค่อนข้างดี: ในระบบส่วนใหญ่พวกมันสามารถวัดช่วงเวลาในระดับไมโครวินาทีหรือน้อยกว่า

ในระบบกระจาย การใช้ monotonic clock สำหรับวัดเวลาที่ผ่านไป (เช่น timeout) มักจะใช้ได้ดี เพราะมันไม่ได้สมมติการซิงโครไนซ์ระหว่าง clock ของ node ต่างๆ และไม่ไวต่อความไม่แม่นยำเล็กน้อยของการวัด

Clock Synchronization and Accuracy (การซิงโครไนซ์ Clock และความแม่นยำ)

Monotonic clocks ไม่ต้องการการซิงโครไนซ์ แต่ time-of-day clocks จำเป็นต้องถูกตั้งค่าตาม NTP server หรือแหล่งเวลาภายนอกอื่นเพื่อให้มีประโยชน์ โชคไม่ดีที่วิธีการของเราในการทำให้ clock บอกเวลาที่ถูกต้องนั้น ไม่น่าเชื่อถือหรือแม่นยำเท่าที่คุณอาจหวัง—hardware clocks และ NTP อาจเป็นสิ่งที่แปรปรวนได้ เพื่อยกตัวอย่างเพียงเล็กน้อย:

• Quartz clock ในคอมพิวเตอร์ทั่วไปไม่แม่นยำมากนัก มัน drift (เดินเร็วหรือช้ากว่าที่ควร) อัตรา clock drift ขึ้นอยู่กับอุณหภูมิของเครื่อง Google ประมาณการ clock drift สูงถึง 200 ppm (parts per million) สำหรับเซิร์ฟเวอร์ของมัน [ 45 ] ซึ่งเทียบเท่ากับการ drift 6 ms สำหรับ clock ที่ซิงค์กับเซิร์ฟเวอร์ทุก 30 วินาที หรือ drift 17 วินาทีสำหรับ clock ที่ซิงค์วันละครั้ง drift นี้จำกัดความแม่นยำที่ดีที่สุดที่คุณสามารถทำได้ แม้ว่าทุกอย่างจะทำงานถูกต้อง

• ถ้า clock ของคอมพิวเตอร์แตกต่างจาก NTP server มากเกินไป มันอาจปฏิเสธที่จะซิงโครไนซ์หรือถูกรีเซ็ตแบบบังคับ [ 39 ]. แอปพลิเคชันใดๆ ที่สังเกตเวลาก่อนและหลังการรีเซ็ตนี้อาจเห็นเวลาถอยหลัง หรือกระโดดไปข้างหน้าอย่างกะทันหัน

• ถ้า node ถูก firewalled จาก NTP servers โดยไม่ได้ตั้งใจ การตั้งค่าผิดพลาดนี้อาจไม่มีใครสังเกต ในช่วงเวลาหนึ่ง ซึ่งในระหว่างนั้น drift อาจสะสมจนเกิดความแตกต่างใหญ่หลวง ระหว่าง clock ของ node นั้นกับ node อื่น หลักฐานเชิงประจักษ์ชี้ว่าสิ่งนี้เกิดขึ้นในทางปฏิบัติ

• การซิงโครไนซ์ NTP จะดีได้เท่ากับ network delay เท่านั้น ดังนั้นความแม่นยำของมันจึงถูกจำกัดเมื่อคุณอยู่บนเครือข่ายที่คับคั่ง ด้วยการดีเลย์ของ packet ที่แปรปรวน การทดลองหนึ่งแสดงให้เห็นว่าข้อผิดพลาดขั้นต่ำ 35 ms สามารถทำได้เมื่อซิงโครไนซ์ผ่านอินเทอร์เน็ต [ 46 ] แม้ว่าการเพิ่มขึ้นของ network delay เป็นครั้งคราวอาจนำไปสู่ข้อผิดพลาดประมาณหนึ่งวินาที ขึ้นอยู่กับการกำหนดค่า network delay ที่มากอาจทำให้ NTP client ยอมแพ้โดยสิ้นเชิง

• NTP servers บางตัวผิดหรือถูกตั้งค่าผิดพลาด รายงานเวลาที่คลาดเคลื่อนเป็นชั่วโมง [ 47 , 48 ]. NTP clients ลดข้อผิดพลาดดังกล่าวโดยการสอบถามหลายเซิร์ฟเวอร์และไม่สนใจค่าที่ผิดปกติ อย่างไรก็ตาม มันค่อนข้างน่ากังวลที่จะวางความถูกต้องของระบบของคุณ กับเวลาที่คุณได้รับจากคนแปลกหน้าบนอินเทอร์เน็ต

• Leap seconds ส่งผลให้หนึ่งนาทียาว 59 วินาทีหรือ 61 วินาที ซึ่งทำให้สมมติฐาน timing ในระบบที่ไม่ได้ออกแบบมาเพื่อรองรับ leap seconds ผิดเพี้ยน [ 49 ]. ความจริงที่ว่า leap seconds ทำให้ระบบขนาดใหญ่หลายระบบ crash [ 40 , 50 ] แสดงให้เห็นว่าสมมติฐานที่ผิดเกี่ยวกับ clock สามารถแทรกซึมเข้าสู่ระบบได้ง่ายเพียงใด วิธีที่ดีที่สุดในการจัดการ leap seconds อาจเป็นการทำให้ NTP servers "โกหก" โดยการปรับ leap second แบบค่อยเป็นค่อยไปตลอดทั้งวัน (เรียกว่า smearing ) [ 51 , 52 ] แม้ว่าพฤติกรรมจริงของ NTP server จะแตกต่างกันในทางปฏิบัติ [ 53 ]. Leap seconds จะไม่ถูกใช้ตั้งแต่ปี 2035 เป็นต้นไป ดังนั้นปัญหานี้จะหมดไป

• ใน VMs ฮาร์ดแวร์ clock ถูก virtualized ซึ่งสร้างความท้าทายเพิ่มเติม สำหรับแอปพลิเคชันที่ต้องการการบอกเวลาที่แม่นยำ [ 54 ]. เมื่อ CPU core ถูกแชร์ระหว่าง VMs แต่ละ VM จะถูกหยุดชั่วคราวเป็นสิบๆ มิลลิวินาทีในขณะที่ VM อื่นกำลังทำงาน จากมุมมองของแอปพลิเคชัน การหยุดชั่วคราวนี้ปรากฏเป็น clock ที่กระโดดไปข้างหน้าอย่างกะทันหัน เมื่อ VM กลับมาทำงานต่อ [ 29 ]. NTP client ที่รันภายใน VM ไม่รู้ว่าเมื่อไหร่ที่มีการหยุดชั่วคราว ดังนั้นมันอาจรายงานความแม่นยำของ clock อย่างไม่ถูกต้อง [ 55 ].

• ถ้าคุณรันซอฟต์แวร์บนอุปกรณ์ที่คุณควบคุมไม่ได้ทั้งหมด (เช่น อุปกรณ์มือถือหรือ embedded) คุณอาจไม่สามารถเชื่อถือ hardware clock ของมันได้เลย ผู้ใช้บางคนจงใจตั้ง hardware clock ของอุปกรณ์เป็นวันที่และเวลาที่ไม่ถูกต้อง เช่น เพื่อโกงในเกม [ 56 ]. ผลที่ตามมาคือ clock อาจถูกตั้งเป็นเวลาที่คลาดเคลื่อนอย่างมาก

การบรรลุความแม่นยำของ clock ที่ดีมากเป็นไปได้ถ้าคุณใส่ใจมากพอที่จะลงทุนทรัพยากรจำนวนมาก ตัวอย่างเช่น กฎระเบียบ MiFID II ของยุโรปสำหรับสถาบันการเงินกำหนดให้ กองทุน high-frequency trading ทั้งหมดต้องซิงโครไนซ์ clock ของพวกเขาให้อยู่ใน 100 ไมโครวินาทีของ UTC เพื่อช่วยดีบักความผิดปกติของตลาดเช่น "flash crashes" และช่วยตรวจจับการปั่นตลาด [ 57 ].

ความแม่นยำ ดังกล่าวสามารถทำได้ด้วยฮาร์ดแวร์พิเศษ (GPS receivers และ/หรือ atomic clocks), Precision Time Protocol (PTP), และการปรับใช้และตรวจสอบอย่างระมัดระวัง [ 58 , 59 ]. การพึ่งพา GPS เพียงอย่างเดียวอาจเสี่ยงเพราะสัญญาณ GPS สามารถถูกรบกวนได้ง่าย ในบางสถานที่ (เช่น ใกล้กับสถานที่ทางทหาร) สิ่งนี้เกิดขึ้นบ่อยครั้ง [ 60 ]. ผู้ให้บริการ cloud บางรายเริ่มเสนอการซิงโครไนซ์ clock ที่มีความแม่นยำสูงสำหรับ virtual machines ของพวกเขา [ 61 ] แต่การซิงโครไนซ์ clock ยังคงต้องการความระมัดระวังอย่างมาก ถ้า NTP daemon ของคุณถูกตั้งค่าผิดหรือ firewall กำลังบล็อก NTP traffic clock error ที่เกิดจาก drift อาจใหญ่ขึ้นอย่างรวดเร็ว

Relying on Synchronized Clocks (การพึ่งพา Clock ที่ซิงโครไนซ์)

ปัญหาเกี่ยวกับ clock คือแม้ว่ามันจะดูง่ายและสะดวกในการใช้ แต่มันมีกับดักมากมายน่าประหลาดใจ หนึ่งวันอาจไม่มี 86,400 วินาทีพอดี time-of-day clocks อาจเดินถอยหลังในเวลา และเวลาตาม clock ของ node หนึ่งอาจแตกต่างอย่างมากจาก clock ของอีก node

ก่อนหน้านี้ในบทนี้เราได้พูดถึงเครือข่ายที่ drop และดีเลย์ packet ตามอำเภอใจ แม้ว่าเครือข่ายจะทำงานดีเป็นส่วนใหญ่ ซอฟต์แวร์ต้องถูกออกแบบบนสมมติฐานว่า เครือข่ายจะผิดพลาดเป็นครั้งคราว และซอฟต์แวร์ต้องจัดการ fault เหล่านั้นอย่างเหมาะสม เช่นเดียวกันกับ clock: แม้ว่ามันจะทำงานค่อนข้างดีเป็นส่วนใหญ่ ซอฟต์แวร์ที่ทนทานต้องเตรียมพร้อมที่จะจัดการกับ clock ที่ไม่ถูกต้อง

ส่วนหนึ่งของปัญหาคือ clock ที่ไม่ถูกต้องมักไม่มีใครสังเกตเห็นได้ง่าย ถ้า CPU ของเครื่องมีข้อบกพร่องหรือเครือข่ายถูกตั้งค่าผิด มันส่วนใหญ่จะไม่ทำงานเลย ดังนั้นปัญหาจะถูกพบและแก้ไขอย่างรวดเร็ว ในทางกลับกัน ถ้า quartz clock ของมันมีข้อบกพร่องหรือ NTP client ถูกตั้งค่าผิด ส่วนใหญ่แล้วทุกอย่างจะดูเหมือนทำงานได้ดี แม้ว่า clock ของมันจะค่อยๆ drift ห่างจากความเป็นจริงมากขึ้นเรื่อยๆ ถ้าซอฟต์แวร์ขึ้นอยู่กับ clock ที่ซิงโครไนซ์อย่างแม่นยำ ผลลัพธ์มักจะเป็นการสูญเสียข้อมูลที่เงียบและละเอียดอ่อน มากกว่าการ crash ที่รุนแรง [ 62 , 63 ].

ดังนั้น ถ้าคุณใช้ซอฟต์แวร์ที่ต้องการ clock ที่ซิงโครไนซ์กัน มันจำเป็นอย่างยิ่งที่จะต้องตรวจสอบ clock offset ระหว่างเครื่องทั้งหมดใน cluster ของคุณอย่างระมัดระวัง node ใดก็ตามที่ clock drift มากเกินไปจาก node อื่นควรถูกประกาศว่าตายและถูกเอาออก การตรวจสอบดังกล่าวทำให้แน่ใจว่าคุณสังเกตเห็น clock ที่มีปัญหาก่อนที่มันจะก่อให้เกิดความเสียหายมากเกินไป

Timestamps for ordering events (Timestamp สำหรับการเรียงลำดับเหตุการณ์)

ลองพิจารณาสถานการณ์หนึ่งที่มันน่าดึงดูดใจ แต่อันตราย ที่จะพึ่งพา clock: การเรียงลำดับเหตุการณ์ข้ามหลาย node [ 64 ]. ตัวอย่างเช่น ถ้า client สองรายเขียนลงในฐานข้อมูลกระจาย ใครมาถึงก่อน? การเขียนไหนเป็นข้อมูลล่าสุด?

Figure 9-3 แสดงให้เห็นการใช้ time-of-day clocks ที่อันตรายในฐานข้อมูลที่มี multi-leader replication (ตัวอย่างคล้ายกับ Figure 6-8 ). Client A เขียน x  = 1 บน node 1; การเขียนถูกจำลองไปยัง node 3; client B increment x บน node 3 (ตอนนี้เรามี x  = 2); และสุดท้าย การเขียนทั้งสองถูกจำลองไปยัง node 2 ดังที่รูปแสดง เมื่อการเขียนถูกจำลองไปยัง node อื่น มันจะถูกติดแท็กด้วย timestamp ตาม time-of-day clock บน node ที่การเขียนเกิดขึ้น การซิงโครไนซ์ clock ในตัวอย่างนี้ดีมาก ความแตกต่างระหว่าง node 1 และ node 3 น้อยกว่า 3 ms ซึ่งอาจดีกว่าที่คุณคาดหวังในทางปฏิบัติ

เนื่องจากการ increment ขึ้นอยู่กับการเขียนก่อนหน้าของ x  = 1 เราอาจคาดว่าการเขียน x  = 2 ควรมี timestamp ที่มากกว่า โชคไม่ดีที่มันไม่ใช่สิ่งที่เกิดขึ้นใน Figure 9-3 . การเขียน x  = 1 มี timestamp 42.004 วินาที แต่การเขียน x  = 2 มี timestamp 42.003 วินาที กล่าวคือ การเขียนโดย client B เกิดขึ้นทีหลังตาม causal กว่าการเขียนโดย client A แต่การเขียนของ B มี timestamp ที่เร็วกว่า

Figure 9-3. การพึ่งพา timestamp สำหรับการเรียงลำดับเหตุการณ์อาจก่อให้เกิดปัญหา เมื่อ time-of-day clocks ไม่ได้ซิงโครไนซ์กันอย่างสมบูรณ์แบบ

ดังที่ได้กล่าวถึงใน "Dealing with Conflicting Writes" วิธีหนึ่งในการแก้ไขความขัดแย้งระหว่างค่าที่ถูกเขียนพร้อมกันบน node ต่างๆ คือ last write wins (LWW) ซึ่งหมายถึงการเก็บการเขียนที่มี timestamp มากที่สุดสำหรับ key ที่กำหนด และทิ้งการเขียนทั้งหมดที่มี timestamp ที่เก่ากว่า ใน Figure 9-3 เมื่อ node 2 ได้รับสองเหตุการณ์นี้ มันจะสรุปผิดว่า x  = 1 เป็นค่าล่าสุดและทิ้งการเขียน x  = 2 ดังนั้น increment จึงสูญหาย

ปัญหานี้สามารถป้องกันได้โดยการทำให้แน่ใจว่าเมื่อค่าถูกเขียนทับ ค่าใหม่จะมี timestamp สูงกว่าค่าที่ถูกเขียนทับเสมอ แม้ว่า timestamp นั้นจะนำหน้า clock ท้องถิ่นของผู้เขียน อย่างไรก็ตาม สิ่งนี้ incur ต้นทุนของการอ่านเพิ่มเติมเพื่อหา timestamp ที่มีอยู่มากที่สุด บางระบบ รวมถึง Cassandra และ ScyllaDB ถูกออกแบบมาเพื่อหลีกเลี่ยงการเดินทางไปกลับเพิ่มเติมนี้ และใช้ timestamp จาก clock ของ client พร้อมกับนโยบาย LWW [ 62 ]. วิธีการนี้มีปัญหาที่ร้ายแรงบางประการ:

• การเขียนฐานข้อมูลสามารถหายไปอย่างลึกลับ node ที่มี clock ช้าจะไม่สามารถเขียนทับ ค่าที่ถูกเขียนก่อนหน้าโดย node ที่มี clock เร็วกว่าได้ จนกว่า clock skew ระหว่าง node จะหมดไป [ 63 , 65 ]. สถานการณ์นี้สามารถทำให้ข้อมูลจำนวนเท่าไหร่ก็ได้ ถูกทิ้งอย่างเงียบๆ โดยไม่มี error ใดๆ รายงานไปยังแอปพลิเคชัน

• LWW ไม่สามารถแยกแยะระหว่างการเขียนที่เกิดขึ้นตามลำดับอย่างรวดเร็วติดกัน (ใน Figure 9-3 การ increment ของ client B เกิดขึ้น หลังจาก การเขียนของ client A อย่างแน่นอน) และการเขียนที่เกิดขึ้นพร้อมกันจริงๆ (ไม่มีผู้เขียนคนใดรู้ถึงอีกคน) จำเป็นต้องมีกลไกการติดตาม causality เพิ่มเติม เช่น version vectors เพื่อป้องกันการละเมิด causality (ดู "Detecting Concurrent Writes" ).

• สอง node สามารถสร้างการเขียนที่มี timestamp เดียวกันได้อย่างอิสระ โดยเฉพาะอย่างยิ่งเมื่อ clock มีความละเอียดแค่มิลลิวินาที จำเป็นต้องมีค่า tiebreaker เพิ่มเติม (ซึ่งอาจเป็นเลขสุ่มขนาดใหญ่) เพื่อแก้ไขความขัดแย้งดังกล่าว แต่วิธีนี้ก็อาจนำไปสู่การละเมิด causality ได้เช่นกัน [ 62 ].

ดังนั้น แม้ว่ามันจะน่าดึงดูดใจที่จะแก้ไขความขัดแย้งโดยการเก็บค่าที่ "ล่าสุด" ที่สุด และทิ้งค่าอื่นๆ สิ่งสำคัญคือต้องตระหนักว่าคำจำกัดความของ "ล่าสุด" ขึ้นอยู่ กับ time-of-day clock ท้องถิ่น ซึ่งอาจไม่ถูกต้อง แม้จะมี clock ที่ซิงโครไนซ์ด้วย NTP อย่างแน่นหนา คุณอาจส่ง packet ที่ timestamp 100 ms (ตาม clock ของผู้ส่ง) และให้มันถึงที่ timestamp 99 ms (ตาม clock ของผู้รับ) —ดังนั้นดูเหมือนว่า packet มาถึงก่อนที่มันจะถูกส่ง ซึ่งเป็นไปไม่ได้

การซิงโครไนซ์ NTP จะทำให้แม่นยำพอที่การเรียงลำดับที่ไม่ถูกต้องเช่นนี้จะไม่เกิดขึ้นได้หรือไม่? อาจจะไม่ เพราะความแม่นยำในการซิงโครไนซ์ของ NTP ถูกจำกัดโดย round-trip time ของเครือข่าย นอกเหนือจากแหล่ง error อื่นๆ เช่น quartz drift เพื่อรับประกันการเรียงลำดับที่ถูกต้อง คุณจะต้องให้ clock error ต่ำกว่า network delay อย่างมีนัยสำคัญ ซึ่งเป็นไปไม่ได้

สิ่งที่เรียกว่า logical clocks [ 66 ] ซึ่งขึ้นอยู่กับการ increment counters แทน crystal oscillator แบบ quartz เป็นทางเลือกที่ปลอดภัยกว่าสำหรับการเรียงลำดับเหตุการณ์ (ดู "Detecting Concurrent Writes" ). Logical clocks ไม่ได้วัดเวลาของวันหรือจำนวนวินาทีที่ผ่านไป มีเพียงการเรียงลำดับสัมพัทธ์ของเหตุการณ์ (ว่าเหตุการณ์หนึ่งเกิดขึ้นก่อนหรือหลังอีกเหตุการณ์หนึ่ง) ในทางตรงกันข้าม time-of-day และ monotonic clocks ซึ่งวัดเวลาที่ผ่านไปจริง เรียกว่า physical clocks . เราจะดู logical clocks ในรายละเอียดเพิ่มเติมใน "ID Generators and Logical Clocks" .

Clock readings with a confidence interval (การอ่านค่า Clock ด้วยช่วงความเชื่อมั่น)

คุณ อาจสามารถอ่าน time-of-day clock ของเครื่องด้วยความละเอียดระดับไมโครวินาทีหรือนาโนวินาที แต่ถึงแม้คุณจะได้ค่าที่ละเอียดขนาดนั้น มันก็ไม่ได้หมายความว่าค่านั้นแม่นยำถึงระดับนั้น ในความเป็นจริง มันมักจะไม่แม่นยำ ดังที่กล่าวไว้ก่อนหน้านี้ drift ใน quartz clock ที่ไม่เที่ยงตรงอาจเป็นหลายมิลลิวินาทีได้ง่ายๆ แม้ว่าคุณจะซิงโครไนซ์กับ NTP server บนเครือข่ายท้องถิ่นทุกนาที ด้วย NTP server บนอินเทอร์เน็ตสาธารณะ ความแม่นยำที่ดีที่สุดน่าจะอยู่ที่ระดับสิบมิลลิวินาที และ error อาจพุ่งสูงเกิน 100 ms ได้ง่ายเมื่อมี network congestion

ดังนั้น การคิดว่าการอ่านค่า clock เป็นจุดในเวลาจึงไม่สมเหตุสมผล มันเหมือนกับช่วงของเวลามากกว่า ภายใน confidence interval —เช่น ระบบอาจมั่นใจ 95% ว่าตอนนี้เวลาอยู่ระหว่าง 10.3 ถึง 10.5 วินาทีของนาทีนั้น แต่มันไม่รู้ละเอียดไปกว่านั้น [ 67 ]. ถ้าเรารู้แค่เวลา +/– 100 ms หลักไมโครวินาทีใน timestamp ก็ไร้ความหมายโดยพื้นฐาน

ค่าขอบเขตความไม่แน่นอนสามารถคำนวณได้จากแหล่งเวลาของคุณ ถ้าคุณมี GPS receiver หรือ atomic clock ที่ต่อโดยตรงกับคอมพิวเตอร์ของคุณ ช่วง error ที่คาดหวังจะถูกกำหนดโดยอุปกรณ์ และในกรณีของ GPS โดยคุณภาพของสัญญาณจากดาวเทียม ถ้าคุณได้รับเวลาจากเซิร์ฟเวอร์ ความไม่แน่นอนขึ้นอยู่กับ quartz drift ที่คาดหวังนับตั้งแต่การซิงค์ครั้งล่าสุดกับเซิร์ฟเวอร์ บวกกับความไม่แน่นอนของ NTP server บวกกับ network round-trip time ไปยังเซิร์ฟเวอร์ (โดยประมาณ และสมมติว่าคุณเชื่อถือเซิร์ฟเวอร์)

โชคไม่ดีที่ระบบส่วนใหญ่ไม่เปิดเผยความไม่แน่นอนนี้ ตัวอย่างเช่น เมื่อคุณเรียก clock_gettime ค่าที่คืนมาไม่ได้บอกคุณถึง error ที่คาดหวังของ timestamp ดังนั้นคุณไม่รู้ว่า confidence interval ของมันคือห้ามิลลิวินาทีหรือห้าปี

มีข้อยกเว้น TrueTime API ใน Google Spanner [ 45 ] และ Amazon ClockBound รายงาน confidence interval บน local clock อย่างชัดเจน เมื่อคุณถามเวลาปัจจุบัน คุณจะได้ค่าสองค่า: [ _earliest_ , _latest_ ] ซึ่งคือ possible timestamp ที่เร็วที่สุด และ possible timestamp ที่ช้าที่สุด จากการคำนวณความไม่แน่นอน clock รู้ว่าเวลาจริงปัจจุบันอยู่ที่ไหนสักแห่งในช่วงนั้น ความกว้างของช่วงขึ้นอยู่กับปัจจัยอื่นๆ รวมถึงระยะเวลาตั้งแต่ local quartz clock ถูกซิงโครไนซ์กับแหล่ง clock ที่แม่นยำกว่าครั้งล่าสุด

Synchronized clocks for global snapshots (การซิงโครไนซ์ Clock สำหรับ Global Snapshot)

ใน "Snapshot Isolation and Repeatable Read" เราได้พูดถึง multiversion concurrency control (MVCC) ซึ่งเป็นฟีเจอร์ที่มีประโยชน์มากในฐานข้อมูลที่ต้องรองรับทั้ง read/write transactions ขนาดเล็กที่รวดเร็วและ read-only transactions ขนาดใหญ่ที่ทำงานนาน (เช่น สำหรับ backup หรือ analytics) มันช่วยให้ read-only transactions เห็น snapshot ของฐานข้อมูล ซึ่งเป็นสถานะที่สอดคล้องกัน ณ จุดเวลาใดเวลาหนึ่ง โดยไม่ต้อง lock และรบกวน read/write transactions

โดยทั่วไป MVCC ต้องการ transaction ID ที่เพิ่มขึ้นแบบ monotonic ถ้าการเขียนเกิดขึ้นหลังจาก snapshot (นั่นคือ write มี transaction ID มากกว่า snapshot) การเขียนนั้นจะมองไม่เห็นโดย snapshot transaction ในฐานข้อมูล node เดียว counter ธรรมดาก็เพียงพอสำหรับการสร้าง transaction IDs

อย่างไรก็ตาม เมื่อฐานข้อมูลกระจายอยู่บนหลายเครื่อง ซึ่งอาจอยู่ในหลาย datacenter การสร้าง transaction ID ระดับโลกที่เพิ่มขึ้นแบบ monotonic (ข้ามทุก shard) เป็นเรื่องยาก เพราะมันต้องการ coordination Transaction ID ต้องสะท้อน causality: ถ้า transaction B อ่านหรือเขียนทับค่าที่ถูกเขียนก่อนหน้าโดย transaction A แล้ว B ต้องมี transaction ID ที่มากกว่า A มิฉะนั้น snapshot จะไม่สอดคล้องกัน ด้วย transactions ขนาดเล็กและรวดเร็วจำนวนมาก การสร้าง transaction IDs ในระบบกระจายกลายเป็น bottleneck ที่รับไม่ได้ (เราจะพูดถึง ID generators ดังกล่าวใน "ID Generators and Logical Clocks" .)

เราสามารถใช้ timestamp จาก time-of-day clocks ที่ซิงโครไนซ์กันเป็น transaction IDs ได้หรือไม่? ถ้าเราสามารถทำให้การซิงโครไนซ์ดีพอได้ มันก็จะมีคุณสมบัติที่ถูกต้อง เพราะ transactions ที่เกิดทีหลังมี timestamp สูงกว่า ปัญหาคือความไม่แน่นอนเกี่ยวกับความแม่นยำของ clock

Spanner ทำ snapshot isolation ข้าม datacenter ด้วยวิธีนี้ [ 68 , 69 ]. มันใช้ confidence interval ของ clock ที่รายงานโดย TrueTime API และขึ้นอยู่กับการสังเกตต่อไปนี้: ถ้าคุณมีสอง confidence intervals แต่ละอันประกอบด้วย earliest และ latest possible timestamp (A = [ A earliest , A latest ] และ B = [ B earliest , B latest ]), และสองช่วงนั้นไม่ทับซ้อนกัน (นั่นคือ A earliest < A latest < B earliest < B latest ), ดังนั้น B เกิดขึ้นหลังจาก A อย่างแน่นอน—ไม่มีข้อสงสัย เฉพาะถ้าช่วงทับซ้อนกันเท่านั้นที่เราไม่แน่ใจว่า A และ B เกิดขึ้นในลำดับใด

เพื่อให้แน่ใจว่า transaction timestamps สะท้อน causality Spanner จงใจรอเป็นระยะเวลาเท่ากับความยาวของ confidence interval ก่อนที่จะ commit read/write transaction โดยการทำเช่นนี้ มันทำให้แน่ใจว่า transaction ใดๆ ที่อาจอ่านข้อมูลนั้น อยู่ในเวลาที่ช้าพอที่ confidence intervals จะไม่ทับซ้อนกัน เพื่อให้เวลารอสั้นที่สุด Spanner ต้องรักษา clock uncertainty ให้เล็กที่สุดเท่าที่เป็นไปได้ เพื่อจุดประสงค์นี้ Google ติดตั้ง GPS receiver หรือ atomic clock ในแต่ละ datacenter ทำให้ clock สามารถซิงโครไนซ์ได้ภายในประมาณ 7 ms [ 45 ].

Atomic clocks และ GPS receivers ไม่จำเป็นอย่างเคร่งครัดใน Spanner สิ่งสำคัญคือการมี confidence interval—แหล่ง clock ที่แม่นยำช่วยให้ช่วงนั้นเล็ก ระบบอื่นๆ เริ่มนำแนวทางที่คล้ายกันมาใช้—ตัวอย่างเช่น YugabyteDB สามารถใช้ ClockBound เมื่อรันบน AWS [ 70 ] และระบบอื่นๆ อีกหลายระบบก็พึ่งพาการซิงโครไนซ์ clock ในระดับต่างๆ [ 71 , 72 ].

Process Pauses (การหยุด Process ชั่วคราว)

ลองพิจารณาตัวอย่างอื่นของการใช้ clock ที่อันตรายในระบบกระจาย สมมติว่าคุณมีฐานข้อมูลที่มี leader หนึ่งตัวต่อ shard มีเพียง leader เท่านั้นที่อนุญาตให้รับ writes node จะรู้ได้อย่างไรว่ามันยังเป็น leader อยู่ (ว่ามันยังไม่ถูกประกาศว่าตายโดย node อื่น) และมันสามารถรับ writes ได้อย่างปลอดภัย?

ทางเลือกหนึ่งคือให้ leader ได้รับ lease จาก node อื่น ซึ่งคล้ายกับ lock ที่มี timeout [ 73 ]. มีเพียง node เดียวเท่านั้นที่สามารถถือ lease ได้ในเวลาใดเวลาหนึ่ง ดังนั้นเมื่อ node ได้รับ lease มันรู้ว่ามันเป็น leader ในช่วงเวลาหนึ่ง จนกว่า lease จะหมดอายุ เพื่อคงสภาพเป็น leader node ต้องต่ออายุ lease เป็นระยะก่อนที่มันจะหมดอายุ ถ้า node ล้มเหลว มันจะหยุดต่ออายุ lease ดังนั้น node อื่นสามารถเข้ามาแทนที่ได้เมื่อ lease หมดอายุ

คุณสามารถนึกภาพ loop การจัดการคำขอที่มีลักษณะแบบนี้:

while (true) {
    request = getIncomingRequest();

    // Ensure that the lease always has at least 10 seconds remaining
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

มีอะไรผิดปกติกับโค้ดนี้? ประการแรก มันขึ้นอยู่กับ clock ที่ซิงโครไนซ์: expiry time บน lease ถูกตั้งโดยเครื่องอื่น (ที่ expiry อาจถูกคำนวณเป็นเวลาปัจจุบันบวก 30 วินาที) และมันถูกเปรียบเทียบกับ local system clock ถ้า clock ไม่ตรงกันมากกว่าสองสามวินาที โค้ดจะเริ่มทำสิ่งที่แปลกประหลาด

ประการที่สอง แม้ว่าเราจะเปลี่ยนโปรโตคอลให้ใช้เฉพาะ local monotonic clock ก็ยังมีปัญหาอีกอย่าง: โค้ดสมมติว่าเวลาผ่านไปน้อยมาก ระหว่างจุดที่มันตรวจสอบเวลา ( System.currentTimeMillis() ) และเวลาที่คำขอถูกประมวลผล ( process(request) ). ปกติโค้ดนี้ทำงานเร็วมาก ดังนั้น buffer 10 วินาทีก็เกินพอที่จะรับประกันว่า lease ไม่หมดอายุระหว่างการประมวลผลคำขอ

อย่างไรก็ตาม จะเกิดอะไรขึ้นถ้ามีการหยุดชั่วคราวที่ไม่คาดคิดในการทำงานของโปรแกรม? เช่น ลองนึกภาพว่า thread หยุดไป 15 วินาที รอบๆ บรรทัดที่เรียก lease.isValid ก่อนที่จะดำเนินการต่อ ในกรณีนั้น lease อาจจะหมดอายุแล้วเมื่อคำขอถูกประมวลผล และอีก node จะเข้ามาเป็น leader แทนแล้ว อย่างไรก็ตาม ไม่มีอะไรบอก thread นี้ว่ามันถูกหยุดไปนานขนาดนั้น ดังนั้นโค้ดจะไม่สังเกตเห็นว่า lease หมดอายุแล้วจนกว่า iteration ถัดไปของ loop —ถึงตอนนั้นมันอาจทำสิ่งที่ไม่ปลอดภัยไปแล้วด้วยการประมวลผลคำขอ

มันสมเหตุสมผลไหมที่จะสมมติว่า thread อาจถูกหยุดนานขนาดนี้? โชคไม่ดีที่ใช่ มีหลายสาเหตุที่สิ่งนี้สามารถเกิดขึ้นได้:

• การแย่งชิงระหว่าง thread ที่เข้าถึงทรัพยากรที่ใช้ร่วมกัน เช่น lock หรือ queue อาจทำให้ thread ใช้เวลาส่วนใหญ่ไปกับการรอ ปัญหาเหล่านี้มักแย่ลง บนเครื่องที่มี CPU cores มากกว่า และปัญหา contention อาจวินิจฉัยได้ยาก [ 74 ].

• ภาษาโปรแกรมหลายภาษา (เช่น JVM) มี garbage collector ที่บางครั้งจำเป็นต้องหยุด thread ทั้งหมดที่กำลังทำงาน ในอดีต "stop-the-world" garbage collection pauses ดังกล่าวบางครั้งกินเวลานานหลายนาที [ 75 ]! ด้วยอัลกอริทึม GC สมัยใหม่ ปัญหานี้ลดลง แต่ GC pauses ยังคงสังเกตเห็นได้ (ดู "Limiting the impact of garbage collection" ).

• ในสภาพแวดล้อม virtualized VM สามารถถูก suspend (หยุดการทำงานของ process ทั้งหมดและบันทึกเนื้อหาหน่วยความจำลงดิสก์) และ resume (กู้คืนเนื้อหาหน่วยความจำและดำเนินการต่อ) การหยุดนี้สามารถเกิดขึ้นได้ทุกเมื่อในการทำงานของ process และอาจใช้เวลานานตามอำเภอใจ ฟีเจอร์นี้บางครั้ง ใช้สำหรับ live migration ของ VMs จากโฮสต์หนึ่งไปยังอีกโฮสต์หนึ่งโดยไม่ต้องรีบูต ในกรณีนี้ระยะเวลาของการหยุดขึ้นอยู่กับอัตราที่ process เขียนลงหน่วยความจำ [ 76 ].

• บนอุปกรณ์ผู้ใช้ปลายทางเช่นแล็ปท็อปและโทรศัพท์ การทำงานอาจถูกหยุดและดำเนินการต่อตามอำเภอใจ (เช่น เมื่อผู้ใช้ปิดฝาแล็ปท็อป)

• เมื่อระบบปฏิบัติการ context-switch ไปยัง thread อื่น หรือเมื่อ hypervisor สลับไปยัง VM อื่น (เมื่อรันใน VM) thread ที่กำลังรันอยู่สามารถถูกหยุด ณ จุดใดก็ได้ในโค้ด ในกรณีของ VM เวลา CPU ที่ใช้ใน VM อื่น เรียกว่า steal time . ถ้าเครื่องอยู่ภายใต้โหลดหนัก —นั่นคือถ้ามี queue ยาวของ thread ที่รอทำงาน —อาจต้องใช้เวลาสักพักกว่า thread ที่ถูกหยุดจะได้ทำงานอีกครั้ง

• ถ้าแอปพลิเคชันทำ synchronous disk access thread อาจถูกหยุดรอให้ disk I/O operation ที่ช้าเสร็จสมบูรณ์ [ 77 ]. ในหลายภาษา disk access อาจเกิดขึ้นอย่างน่าประหลาดใจ แม้ว่าโค้ดจะไม่ได้พูดถึงการเข้าถึงไฟล์อย่างชัดเจน —เช่น Java classloader โหลด class files แบบขี้เกียจเมื่อถูกใช้ครั้งแรก ซึ่งอาจเกิดขึ้นได้ทุกเมื่อในการทำงานของโปรแกรม I/O pauses และ GC pauses อาจสมคบกันรวมความล่าช้า [ 78 ]. ถ้าดิสก์เป็น network filesystem หรือ network block device (เช่น Amazon EBS) latency I/O จะขึ้นอยู่กับความแปรปรวนของการดีเลย์ของเครือข่าย [ 31 ].

• ถ้าระบบปฏิบัติการถูกกำหนดค่าให้อนุญาต swapping to disk ( paging ), การเข้าถึงหน่วยความจำธรรมดาอาจส่งผลให้เกิด page fault ที่ต้องโหลด page จากดิสก์เข้าสู่หน่วยความจำ thread จะถูกหยุดในขณะที่ I/O operation ช้าที่เกิดขึ้น ถ้าหน่วยความจำมีแรงดันสูง สิ่งนี้อาจทำให้ต้อง swap page อื่นออกไปยังดิสก์ ในสถานการณ์ที่รุนแรง ระบบปฏิบัติการอาจใช้เวลาส่วนใหญ่ไปกับการ swap pages เข้าและออกจากหน่วยความจำและได้งานจริงทำน้อยมาก (เรียกว่า thrashing ). เพื่อหลีกเลี่ยงปัญหานี้ paging มักถูกปิดใช้งานบนเซิร์ฟเวอร์ (ถ้าคุณอยากจะ kill process เพื่อ freeing หน่วยความจำมากกว่าเสี่ยงให้เกิด thrashing)

• กระบวนการ Unix สามารถถูกหยุดโดยการส่งสัญญาณ SIGSTOP —เช่น โดยการกด Ctrl-Z ใน shell สัญญาณนี้หยุด process ทันทีไม่ให้ได้รับ CPU cycles เพิ่ม จนกว่ามันจะถูกดำเนินการต่อด้วย SIGCONT ซึ่ง ณ จุดนั้นมันจะทำงานต่อจากจุดที่ค้างไว้ แม้ว่าสภาพแวดล้อมของคุณจะไม่ได้ใช้ SIGSTOP ปกติ แต่มันอาจถูกส่งโดยวิศวกรปฏิบัติการโดยไม่ได้ตั้งใจ

เหตุการณ์ทั้งหมดเหล่านี้สามารถ preempt thread ที่กำลังรัน ณ จุดใดก็ได้และดำเนินการต่อในเวลาต่อมา โดยที่ thread ไม่รู้ตัวด้วยซ้ำ ปัญหาคล้ายกับการทำให้ multithreaded code บนเครื่องเดียว thread-safe; คุณไม่สามารถสมมติอะไรเกี่ยวกับ timing เพราะ context switch และ parallelism ตามอำเภอใจอาจเกิดขึ้นได้

เมื่อเขียน multithreaded code บนเครื่องเดียว เรามีเครื่องมือที่ดีพอสมควร สำหรับทำให้มัน thread-safe: mutexes, semaphores, atomic counters, lock-free data structures, blocking queues และอื่นๆ โชคไม่ดีที่เครื่องมือเหล่านี้ไม่สามารถแปลตรงไปยังระบบกระจายได้ เพราะระบบกระจายไม่มี shared memory—มีเพียงข้อความที่ส่งผ่านเครือข่ายที่ไม่น่าเชื่อถือ

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

Provididng response time guarantees (การรับประกัน Response Time)

ดังที่เราได้พูดคุยกัน ในภาษาโปรแกรมและระบบปฏิบัติการหลายภาษา threads และ processes อาจหยุดชั่วคราวเป็นระยะเวลาที่ไม่มีขอบเขต อย่างไรก็ตาม สาเหตุเหล่านั้นของการหยุด สามารถ ถูกกำจัดได้ถ้าคุณพยายามมากพอ

ซอฟต์แวร์บางตัวทำงานในสภาพแวดล้อมที่การไม่ตอบสนองภายในเวลาที่กำหนด อาจก่อให้เกิดความเสียหายร้ายแรง คอมพิวเตอร์ที่ควบคุมการเคลื่อนไหวของเครื่องบิน จรวด หุ่นยนต์ รถยนต์ และวัตถุทางกายภาพอื่นๆ ต้องตอบสนองต่อ sensor inputs อย่างรวดเร็วและคาดเดาได้ ในระบบที่เรียกว่า hard real-time ซอฟต์แวร์ต้องตอบสนองภายใน deadline ที่กำหนด การไม่เป็นไปตาม deadline อาจทำให้ระบบทั้งหมดล้มเหลว

Note

ใน embedded systems real-time หมายความว่าระบบถูกออกแบบและทดสอบอย่างระมัดระวังเพื่อให้เป็นไปตาม timing guarantees ที่กำหนดในทุกสถานการณ์ ความหมายนี้ตรงกันข้ามกับการใช้คำว่า real-time แบบคลุมเครือบนเว็บ ที่อธิบายเซิร์ฟเวอร์ที่ push ข้อมูลไปยัง clients และ stream processing โดยไม่มีข้อจำกัด response-time ที่เข้มงวด (ดู Chapter 12 ).

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

การให้การรับประกัน real-time ในระบบต้องการการสนับสนุนจากทุกระดับของ software stack จำเป็นต้องมี real-time operating system (RTOS) ที่อนุญาตให้ process ถูกจัดตารางด้วยการจัดสรร CPU time ที่รับประกันในช่วงเวลาที่กำหนด ฟังก์ชัน library ต้องบันทึก worst-case execution times; dynamic memory allocation อาจถูกจำกัดหรือห้ามโดยสิ้นเชิง (real-time garbage collectors มีอยู่ แต่แอปพลิเคชันยังต้องแน่ใจว่ามันไม่ได้ให้งาน แก่ garbage collector มากเกินไป); และต้องมีการทดสอบและการวัดผลจำนวนมหาศาล เพื่อให้แน่ใจว่าการรับประกันเป็นไปตามที่กำหนด

ทั้งหมดนี้ต้องใช้งานเพิ่มเติมเป็นจำนวนมาก และจำกัดช่วงของภาษาโปรแกรม library และเครื่องมือที่สามารถใช้ได้อย่างรุนแรง (เพราะภาษาและเครื่องมือส่วนใหญ่ไม่ให้การรับประกันแบบ real-time) ด้วยเหตุผลเหล่านี้ การพัฒนาระบบ real-time จึงแพงมาก และมักใช้ใน safety-critical embedded devices เป็นหลัก นอกจากนี้ "real-time" ไม่เหมือนกับ "high-performance" —ในความเป็นจริง ระบบ real-time อาจมี throughput ต่ำกว่า เพราะพวกมันต้องให้ความสำคัญกับการตอบสนองที่ทันเวลามากกว่าสิ่งอื่นใด (ดู "Latency and Resource Utilization" ).

สำหรับระบบประมวลผลข้อมูลฝั่งเซิร์ฟเวอร์ส่วนใหญ่ การรับประกัน real-time ไม่คุ้มค่าทางเศรษฐกิจหรือไม่เหมาะสม ดังนั้น ระบบเหล่านี้จึงต้องทนทุกข์กับการหยุดชั่วคราวและความไม่เสถียรของ clock ที่มาจากการทำงานในสภาพแวดล้อมที่ไม่ใช่ real-time

Limiting the impact of garbage collection (การจำกัดผลกระทบของ Garbage Collection)

Garbage collection เคยเป็นหนึ่งในสาเหตุใหญ่ที่สุดของการหยุด process [ 79 ] แต่โชคดีที่อัลกอริทึม GC พัฒนาขึ้นมาก collector ที่ปรับแต่งอย่างเหมาะสมในปัจจุบันมักจะหยุด process ไม่เกินสองสามมิลลิวินาที Java runtime มี collector หลายตัวเช่น concurrent mark sweep (CMS), garbage-first (G1), Z garbage collector (ZGC), Epsilon, และ Shenandoah แต่ละตัวถูกปรับให้เหมาะสมสำหรับ memory profiles ที่แตกต่างกัน เช่น high-frequency object creation, large heaps และอื่นๆ ในทางตรงกันข้าม Go มี concurrent mark and sweep garbage collector ที่พยายามปรับแต่งตัวเอง

ถ้าคุณต้องหลีกเลี่ยง GC pauses โดยสิ้นเชิง ทางเลือกหนึ่งคือใช้ภาษาที่ไม่มี garbage collector ตัวอย่างเช่น Swift ใช้ automatic reference counting เพื่อกำหนดว่าเมื่อไหร่ที่หน่วยความจำ ถูกปล่อยได้ ในขณะที่ Rust และ Mojo ติดตามอายุของ object ผ่าน type system เพื่อให้ compiler สามารถกำหนดได้ว่าหน่วยความจำต้องถูกจัดสรรนานเท่าไหร่

นอกจากนี้ยังเป็นไปได้ที่จะใช้ภาษาแบบ garbage-collected ในขณะที่บรรเทาผลกระทบของการหยุดชั่วคราว ตัวอย่างเช่น object สามารถถูกเก็บและนำกลับมาใช้ใหม่ใน pools แทนที่จะทิ้ง หรือข้อมูลสามารถถูกจัดสรรแบบ off-heap วิธีการที่รุนแรงกว่าคือการปฏิบัติต่อ GC pauses เหมือนกับการหยุดให้บริการตามแผนของ node และให้ node อื่นจัดการคำขอจาก clients ในขณะที่ node หนึ่งกำลังเก็บขยะ ถ้า runtime สามารถเตือนแอปพลิเคชันว่า node ต้องการ GC pause ในเร็วๆ นี้ แอปพลิเคชันสามารถหยุดส่งคำขอใหม่ไปยัง node นั้น รอให้มันประมวลผลคำขอที่ค้างอยู่เสร็จ แล้วจึงทำ GC ในขณะที่ไม่มีคำขอที่กำลังดำเนินการ เทคนิคนี้ซ่อน GC pauses จาก clients และลดเปอร์เซ็นไทล์สูงของ response time [ 80 , 81 ].

รูปแบบหนึ่งของแนวคิดนี้คือการใช้ garbage collector สำหรับ object ที่มีอายุสั้นเท่านั้น (ซึ่งเก็บได้เร็ว) และ restart processes เป็นระยะ ก่อนที่พวกมันจะสะสม object ที่มีอายุยาวนานพอที่จะต้องทำ GC เต็มรูปแบบ [ 79 , 82 ]. สามารถ restart ทีละ node และเปลี่ยนเส้นทาง traffic ออกจาก node ก่อนการ restart ที่วางแผนไว้ เช่นเดียวกับ rolling upgrade (ดู Chapter 5 ).

มาตรการเหล่านี้ไม่สามารถป้องกัน GC pauses ได้อย่างสมบูรณ์ แต่มันสามารถลดผลกระทบต่อแอปพลิเคชันได้อย่างมีประโยชน์

Knowledge, Truth, and Lies (ความรู้ ความจริง และการโกหก)

จนถึงตอนนี้ในบทนี้เราได้สำรวจว่าระบบกระจายแตกต่างจากโปรแกรมที่ทำงานบนคอมพิวเตอร์เครื่องเดียวอย่างไร ระบบกระจายไม่มี shared memory มีเพียงการส่งข้อความผ่านเครือข่ายที่ไม่น่าเชื่อถือ และระบบอาจประสบกับ partial failures, clock ที่ไม่น่าเชื่อถือ และ processing pauses

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

การอภิปรายเกี่ยวกับระบบเหล่านี้ใกล้เคียงกับปรัชญา: เรารู้อะไรที่เป็นจริงหรือเท็จในระบบของเรา? เรามั่นใจในความรู้นั้นได้แค่ไหน ถ้ากลไกของการรับรู้และการวัดไม่น่าเชื่อถือ [ 83 ]? ระบบซอฟต์แวร์ควรปฏิบัติตามกฎที่เราคาดหวังจากโลกทางกายภาพ เช่นเหตุและผลหรือไม่?

โชคดีที่เราไม่ต้องไปไกลถึงขั้นหาความหมายของชีวิต ในระบบกระจาย เราสามารถระบุสมมติฐานที่เรากำลังทำเกี่ยวกับพฤติกรรม (system model ) และออกแบบระบบจริงในลักษณะที่ทำให้ตรงตามสมมติฐานเหล่านั้น อัลกอริทึมสามารถพิสูจน์ได้ว่าทำงานถูกต้องภายใน system model หนึ่งๆ ซึ่งหมายความว่าพฤติกรรมที่เชื่อถือได้นั้นสามารถบรรลุได้ แม้ว่า system model พื้นฐานจะให้การรับประกันน้อยมาก

อย่างไรก็ตาม แม้ว่ามันจะเป็นไปได้ที่จะทำให้ซอฟต์แวร์มีพฤติกรรมที่ดี ใน system model ที่ไม่น่าเชื่อถือ การทำเช่นนั้นก็ไม่ตรงไปตรงมา ในส่วนที่เหลือของบทนี้เราจะสำรวจแนวคิดของความรู้และความจริงในระบบกระจายเพิ่มเติม ซึ่งจะช่วยให้เราคิดเกี่ยวกับประเภทของสมมติฐานที่เราสามารถทำได้ และการรับประกันที่เราอาจต้องการให้ ใน Chapter 10 เราจะดำเนินการต่อไปเพื่อดูตัวอย่างของ distributed algorithms ที่ให้การรับประกันเฉพาะภายใต้สมมติฐานเฉพาะ

The Majority Rules (กฎของเสียงส่วนใหญ่)

ลองนึกภาพเครือข่ายที่มี asymmetric fault: node สามารถรับข้อความทั้งหมดที่ส่งถึงมันได้ แต่ข้อความขาออกจาก node นั้นถูก drop หรือดีเลย์ [ 22 ]. แม้ว่า node นั้นจะทำงานได้อย่างสมบูรณ์และได้รับคำขอจาก node อื่น node อื่นก็ไม่สามารถได้ยินการตอบกลับของมัน หลังจาก timeout node อื่นก็ประกาศว่ามันตาย เพราะพวกมันไม่ได้รับการตอบกลับจาก node สถานการณ์ดำเนินไปเหมือนฝันร้าย—node ที่ถูกตัดการเชื่อมต่อครึ่งๆ ถูก dragged ไปที่สุสาน เตะและกรีดร้อง "ฉันยังไม่ตาย!"—แต่เพราะไม่มีใครได้ยินเสียงกรีดร้องของมัน ขบวนแห่ศพก็ดำเนินต่อไปด้วยความมุ่งมั่น

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

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

ข้อคิดจากเรื่องเหล่านี้คือ node ไม่สามารถเชื่อถือการตัดสินใจของตัวเองเกี่ยวกับสถานการณ์ได้เสมอไป ระบบกระจายไม่สามารถพึ่งพา node เดียวแต่เพียงผู้เดียว เพราะ node อาจล้มเหลว ณ เวลาใดก็ได้ ซึ่งอาจทำให้ระบบติดขัดและไม่สามารถกู้คืนได้ แทนที่จะเป็นเช่นนั้น distributed algorithms หลายอันพึ่งพา quorum (นั่นคือการลงคะแนนระหว่าง node; ดู "Using quorums for reading and writing" ): การตัดสินใจต้องการคะแนนเสียงขั้นต่ำจากหลาย node เพื่อลดการพึ่งพา node ใด node หนึ่งโดยเฉพาะ

ซึ่งรวมถึงการตัดสินใจเกี่ยวกับการประกาศว่า node ตาย ถ้า quorum ของ node ประกาศว่า node อื่นตาย มันจะต้องถูกพิจารณาว่าตายแล้ว แม้ว่า node นั้นจะยังรู้สึกมีชีวิตอยู่มากก็ตาม แต่ละ node ต้องยอมรับการตัดสินใจของ quorum และถอยออก

โดยทั่วไปแล้ว quorum คือคะแนนเสียงข้างมากที่มากกว่าครึ่งหนึ่งของ node (แม้ว่า quorum ประเภทอื่นก็เป็นไปได้) quorum ข้างมากช่วยให้ระบบทำงานต่อไปได้ถ้า node ส่วนน้อยมีปัญหา (ด้วยสาม node สามารถทน node ที่มีปัญหาได้หนึ่งตัว; ด้วยห้า node สามารถทน node ที่มีปัญหาได้สองตัว) มันยังปลอดภัยเพราะมีเสียงข้างมากได้เพียงเสียงเดียวในระบบ— ไม่สามารถมีสองเสียงข้างมากที่มีการตัดสินใจขัดแย้งกันในเวลาเดียวกัน เราจะพูดถึงการใช้ quorums ในรายละเอียดเพิ่มเติมเมื่อเราไปถึง consensus algorithms ใน Chapter 10 .

Distributed Locks and Leases (Locks และ Leases แบบกระจาย)

Locks และ leases ในแอปพลิเคชันกระจายมีแนวโน้มที่จะถูกใช้ผิด และเป็นแหล่งที่มาทั่วไปของบั๊ก [ 84 ]. มาดูกรณีเฉพาะของวิธีที่มันสามารถผิดพลาดได้

ใน "Process Pauses" เราเห็นว่า lease เป็น lock ชนิดหนึ่งที่หมดเวลาและสามารถถูกกำหนดให้เจ้าของใหม่ได้ ถ้าเจ้าของเก่าหยุดตอบสนอง (อาจเพราะมัน crash, ถูกหยุดนานเกินไป, หรือถูกตัดการเชื่อมต่อจากเครือข่าย) คุณสามารถใช้ leases เมื่อระบบต้องการให้มีเพียงหนึ่งเดียวของบางสิ่ง ตัวอย่างเช่น:

• มีเพียง node เดียวที่ได้รับอนุญาตให้เป็น leader สำหรับ shard ของฐานข้อมูล เพื่อหลีกเลี่ยง split brain (ดู "Handling Node Outages" ).

• มีเพียง transaction หรือ client เดียวที่ได้รับอนุญาตให้อัปเดต resource หรือ object เพื่อป้องกันไม่ให้มันเสียหายจากการเขียนพร้อมกัน

• มีเพียง node เดียวที่ควรประมวลผล input file ที่กำหนดให้กับงานประมวลผลใหญ่ เพื่อหลีกเลี่ยงความพยายามที่สูญเปล่าเนื่องจากการทำงานซ้ำซ้อนโดยหลาย node

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

ตัวอย่างเช่น Figure 9-4 แสดงบั๊กการเสียหายของข้อมูลเนื่องจากการ implement locking ที่ไม่ถูกต้อง (บั๊กนี้ไม่ใช่แค่ในทางทฤษฎี; HBase เคยมีปัญหานี้ [ 85 , 86 ].) สมมติว่าคุณต้องการรับประกันว่าไฟล์ใน storage service สามารถเข้าถึงได้โดย client เพียงครั้งละหนึ่งราย เพราะถ้า client หลายรายพยายามเขียนลงไป ไฟล์จะเสียหาย คุณพยายาม implement สิ่งนี้โดยกำหนดให้ client ต้องได้รับ lease จาก lock service ก่อนเข้าถึงไฟล์ lock service ดังกล่าวมักถูก implement โดยใช้ consensus algorithm ซึ่งจะกล่าวถึงเพิ่มเติมใน Chapter 10 .

ปัญหานี้เป็นตัวอย่างของสิ่งที่เราได้พูดคุยใน "Process Pauses" . ถ้า client ที่ถือ lease ถูกหยุดนานเกินไป lease ของมันจะหมดอายุ client อื่นสามารถได้รับ lease สำหรับไฟล์เดียวกันและเริ่มเขียนถึงไฟล์นั้น เมื่อ client ที่ถูกหยุดกลับมา มันเชื่อ (อย่างผิดๆ) ว่ามันยังมี lease ที่ถูกต้อง และเขียนถึงไฟล์ต่อไป ตอนนี้เรามีสถานการณ์ split-brain: การเขียนของ client ชนกันและทำให้ไฟล์เสียหาย

Figure 9-4. การ implement distributed lock ที่ไม่ถูกต้อง: client 1 เชื่อว่ามันยังมี lease ที่ถูกต้อง แม้ว่ามันหมดอายุแล้ว และทำให้ไฟล์ใน storage เสียหาย

Figure 9-5 แสดงปัญหาที่แตกต่างกันที่มีผลลัพธ์คล้ายกัน ในตัวอย่างนี้ไม่มี process pause มีเพียง client 1 crash ก่อนที่ client 1 จะ crash มันส่ง write request ไปยัง storage service แต่คำขอนี้ล่าช้าเป็นเวลานานในเครือข่าย (จำได้จาก "Network Faults in Practice" ว่า packet บางครั้งสามารถดีเลย์ได้หนึ่งนาทีหรือมากกว่า) เมื่อ write request มาถึง storage service lease ของ client 1 ก็หมดอายุแล้ว ทำให้ client 2 สามารถรับมันและออก write ของตัวเอง ผลลัพธ์คือการเสียหายที่คล้ายกับใน Figure 9-4 .

Figure 9-5. ข้อความจากเจ้าของ lease คนเก่าอาจล่าช้าเป็นเวลานานและมาถึงหลังจาก node อื่น เข้ามารับช่วง lease ต่อแล้ว

Fencing off zombies and delayed requests (การกั้น Zombie และคำขอที่ล่าช้า)

คำว่า zombie บางครั้งใช้เพื่ออธิบายเจ้าของ lease คนเก่าที่ยังไม่รู้ว่าเสีย lease ไปแล้ว และยังคงทำตัวเหมือนเป็นเจ้าของ lease ปัจจุบัน เนื่องจากเราไม่สามารถกำจัด zombies ได้อย่างสมบูรณ์ เราต้องทำให้แน่ใจว่ามันไม่สามารถก่อความเสียหายในรูปแบบของ split brain ได้ สิ่งนี้เรียกว่า fencing off zombie

บางระบบพยายามกั้น zombies โดยการปิดมัน— เช่น โดยการตัดการเชื่อมต่อจากเครือข่าย [ 9 ], ปิด VM ผ่าน management interface ของ cloud provider, หรือแม้กระทั่งตัดไฟเครื่องทางกายภาพ [ 87 ]. วิธีการนี้บางครั้งเรียกว่า shoot the other node in the head (STONITH) แม้ว่าเราจะไม่ชอบใช้คำศัพท์ที่รุนแรงเช่นนี้ ไม่ว่ากรณีใด มันก็ไม่ได้ผลมากนัก: วิธีการนี้ไม่ป้องกันการดีเลย์เครือข่ายขนาดใหญ่ ที่แสดงใน Figure 9-5 ; node ทั้งหมดอาจปิดกันและกัน [ 19 ]; และเมื่อ zombie ถูกตรวจพบและปิดแล้ว มันอาจจะสายเกินไปและข้อมูลอาจเสียหายไปแล้ว

โซลูชันการกั้นที่แข็งแกร่งกว่า ซึ่งป้องกันทั้ง zombie และคำขอที่ล่าช้า แสดงใน Figure 9-6 .

Figure 9-6. การทำให้การเข้าถึง storage ปลอดภัยโดยอนุญาต writes ตามลำดับของ fencing tokens ที่เพิ่มขึ้นเท่านั้น

สมมติว่าทุกครั้งที่ lock service ให้ lock หรือ lease มันยังคืน fencing token ซึ่งเป็นตัวเลขที่เพิ่มขึ้นทุกครั้งที่มีการให้ lock (เช่น increment โดย lock service) จากนั้นเราสามารถกำหนดว่าทุกครั้งที่ client ส่ง write request ไปยัง storage service มันต้องรวม fencing token ปัจจุบันของมันด้วย

Note

มีชื่อทางเลือกหลายชื่อสำหรับ fencing tokens ใน Chubby ซึ่งเป็น lock service ของ Google พวกมันถูกเรียกว่า sequencers [ 88 ], และใน Kafka พวกมันถูกเรียกว่า epoch numbers . ใน consensus algorithms ซึ่งเราจะพูดถึงใน Chapter 10 , ballot number (Paxos) หรือ term number (Raft) มีวัตถุประสงค์คล้ายกัน

ใน Figure 9-6 , client 1 ได้รับ lease ด้วย token 33 แต่แล้วมันก็หยุดไปนาน และ lease หมดอายุ Client 2 ได้รับ lease ด้วย token 34 (ตัวเลขเพิ่มขึ้นเสมอ) และส่ง write request ไปยัง storage service รวมถึง token ต่อมา client 1 กลับมามีชีวิต และส่ง write ของมันไปยัง storage service รวมถึงค่า token 33 อย่างไรก็ตาม storage service จำได้ว่ามันประมวลผล write ด้วยหมายเลข token ที่สูงกว่า (34) ไปแล้ว ดังนั้นมันจึงปฏิเสธคำขอด้วย token 33 client ที่เพิ่งได้ lease ต้องทำ write ไปยัง storage service ทันที และเมื่อ write นั้นเสร็จสมบูรณ์ zombies ใดๆ จะถูกกั้นไว้ การดำเนินการเหล่านี้คล้ายกับเทคนิค optimistic concurrency control (OCC) ที่เราเห็นใน "Pessimistic versus optimistic concurrency control" ยกเว้นว่า fencing เป็นการถาวร ในขณะที่ concurrency control failures สามารถลองใหม่ได้

ถ้า ZooKeeper เป็น lock service ของคุณ คุณสามารถใช้ transaction ID zxid หรือ node version cversion เป็น fencing token [ 85 ]. ด้วย etcd revision number พร้อมกับ lease ID มีวัตถุประสงค์คล้ายกัน [ 89 ]. FencedLock API ใน Hazelcast สร้าง fencing token อย่างชัดเจน [ 90 ].

กลไกนี้ต้องการให้ storage service มีวิธีตรวจสอบว่า write ขึ้นอยู่กับ token ที่ล้าสมัยหรือไม่ อีกทางหนึ่ง มันเพียงพอสำหรับบริการที่รองรับ write ที่จะสำเร็จ เฉพาะเมื่อ object ไม่ถูกเขียนโดย client อื่นตั้งแต่ client ปัจจุบันอ่านมันครั้งล่าสุด คล้ายกับการดำเนินการ atomic CAS ตัวอย่างเช่น object storage services รองรับการตรวจสอบดังกล่าว; Amazon S3 เรียกว่า conditional writes , Azure Blob Storage เรียกว่า conditional headers , และ Google Cloud Storage เรียกว่า request preconditions .

Fencing with multiple replicas (การกั้นด้วย Replica หลายตัว)

ถ้า client ของคุณจำเป็นต้องเขียนไปยัง storage service เดียวที่รองรับ conditional writes lock service ก็ค่อนข้างซ้ำซ้อน [ 91 , 92 , 93 ] เพราะการกำหนด lease สามารถ implement ได้โดยตรงบน storage service นั้น อย่างไรก็ตาม เมื่อคุณมี fencing token คุณสามารถใช้มันกับหลาย services หรือ replicas และรับประกันว่าเจ้าของ lease คนเก่าถูกกั้นบนทั้งหมด

ตัวอย่างเช่น ลองนึกภาพ storage service เป็น leaderless replicated key-value store ที่มีการแก้ไขความขัดแย้งแบบ LWW (ดู "Leaderless Replication" ). ในระบบดังกล่าว client ส่ง writes โดยตรงไปยังแต่ละ replica และแต่ละ replica ตัดสินใจอย่างอิสระว่าจะยอมรับ write หรือไม่ ตาม timestamp ที่กำหนดโดย client

ดังที่แสดงใน Figure 9-7 คุณสามารถใส่ fencing token ของผู้เขียนในบิตหรือหลักที่มีนัยสำคัญที่สุดของ timestamp จากนั้นคุณสามารถแน่ใจได้ว่า timestamp ใดๆ ที่สร้างโดยเจ้าของ lease ใหม่ จะมากกว่า timestamp ใดๆ จากเจ้าของ lease เก่า แม้ว่า writes ของเจ้าของ lease เก่าจะเกิดขึ้นทีหลังก็ตาม

ใน Figure 9-7 , client 2 มี fencing token 34 ดังนั้น timestamps ทั้งหมดที่เริ่มต้นด้วย 34…​ จะมากกว่า timestamps ใดๆ ที่เริ่มต้นด้วย 33…​ ที่สร้างโดย client 1 Client 2 เขียนไปยัง quorum ของ replicas แต่มันไม่สามารถเข้าถึง replica 3 ซึ่งหมายความว่าเมื่อ zombie client 1 พยายามเขียนในภายหลัง การเขียนของมันอาจสำเร็จที่ replica 3 แม้ว่ามันจะถูก ignore โดย replicas 1 และ 2 นี่ไม่ใช่ปัญหา เพราะการอ่านจาก quorum ในภายหลัง จะเลือก write จาก client 2 ที่มี timestamp มากกว่า และ read repair หรือ anti-entropy จะเขียนทับค่าที่ client 1 เขียนในที่สุด

Figure 9-7. การใช้ fencing tokens เพื่อป้องกัน writes ใน leaderless replicated database

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

Byzantine Faults (Byzantine Faults)

Fencing tokens สามารถตรวจจับและบล็อก node ที่ ทำผิดพลาดโดยไม่ตั้งใจ (เช่น เพราะมันยังไม่รู้ว่า lease ของมันหมดอายุแล้ว) อย่างไรก็ตาม ถ้า node จงใจต้องการบ่อนทำลายการรับประกันของระบบ มันสามารถทำได้โดยส่งข้อความที่มี fencing token ปลอม

ในหนังสือเล่มนี้เราสมมติว่า node ไม่น่าเชื่อถือแต่ซื่อสัตย์ พวกมันอาจช้าหรือไม่ตอบสนอง (เพราะ fault) และสถานะของพวกมันอาจล้าสมัย (เพราะ GC pause หรือ network delays) แต่เราสมมติว่าถ้า node ตอบสนอง มันกำลังบอก "ความจริง" เท่าที่มันรู้ มันกำลังทำตามกฎของโปรโตคอล

ปัญหาระบบกระจายจะยากขึ้นมากถ้ามีความเสี่ยงที่ node อาจ "โกหก" (ส่งคำตอบที่ผิดพลาดหรือเสียหายตามอำเภอใจ) —เช่น node อาจลงคะแนนที่ขัดแย้งกันหลายครั้งในการเลือกตั้งเดียวกัน พฤติกรรมดังกล่าวเรียกว่า Byzantine fault และปัญหาของการบรรลุฉันทามติในสภาพแวดล้อมที่ไม่ไว้วางใจนี้ เรียกว่า Byzantine Generals Problem [ 94 ].

The Byzantine Generals Problem (ปัญหา Byzantine Generals)

Byzantine Generals Problem เป็นการขยายแนวคิดของ two generals problem [ 95 ] ซึ่งจินตนาการนายพลสองคนของกองทัพที่ต้องตกลงในแผนการรบ เนื่องจากพวกเขาตั้งค่ายที่ต่างที่กัน พวกเขาสามารถสื่อสารได้โดยคนส่งสารเท่านั้น และคนส่งสารบางครั้งก็ล่าช้าหรือหายไป (เหมือน packet ในเครือข่าย) เราจะพูดถึงปัญหาของ consensus ใน Chapter 10 .

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

Byzantium เป็นเมืองกรีกโบราณที่ต่อมากลายเป็น Constantinople ในสถานที่ซึ่งปัจจุบันคือ Istanbul ในตุรกี ไม่มีหลักฐานทางประวัติศาสตร์ว่านายพลของ Byzantium มีแนวโน้มที่จะวางอุบายและสมคบคิดมากกว่านายพลที่อื่น แต่ชื่อนี้มาจากคำว่า Byzantine ในความหมายของ ซับซ้อนเกินไป, ระบบราชการ, เจ้าเล่ห์ ซึ่งถูกใช้ในการเมืองมานานก่อนคอมพิวเตอร์ [ 96 ]. Lamport ต้องการเลือกสัญชาติที่จะไม่ทำให้ผู้อ่านคนใดขุ่นเคือง และเขาได้รับคำแนะนำว่าการเรียกมันว่า The Albanian Generals Problem ไม่ใช่ความคิดที่ดีนัก [ 97 ].

Uses of Byzantine fault tolerance (การใช้งาน Byzantine Fault Tolerance)

ระบบจะ Byzantine fault-tolerant ถ้ามันยังคงทำงานได้อย่างถูกต้องแม้ว่า node บางส่วนทำงานผิดปกติและไม่ทำตามโปรโตคอล หรือถ้าผู้โจมตีที่ประสงค์ร้ายรบกวนเครือข่าย ความกังวลนี้เกี่ยวข้องในบางสถานการณ์เฉพาะ ตัวอย่างเช่น:

• ในสภาพแวดล้อม aerospace ข้อมูลในหน่วยความจำหรือ CPU register ของคอมพิวเตอร์ อาจเสียหายจากรังสี ทำให้มันตอบสนองต่อ node อื่นในรูปแบบที่คาดเดาไม่ได้ตามอำเภอใจ เนื่องจากความล้มเหลวของระบบจะมีค่าใช้จ่ายสูงมาก (เช่น เครื่องบินตกและคร่าชีวิตทุกคนบนเครื่อง หรือจรวดชนกับสถานีอวกาศนานาชาติ) ระบบควบคุมการบินต้องทนต่อ Byzantine faults [ 98 , 99 ].

• ในระบบที่มีหลายฝ่ายเข้าร่วม ผู้เข้าร่วมบางคนอาจพยายามโกงหรือฉ้อโกงผู้อื่น ในสถานการณ์เช่นนี้ มันไม่ปลอดภัยที่ node จะเชื่อถือข้อความของ node อื่น เพราะพวกมันอาจถูกส่งด้วยเจตนาร้าย กลไกฉันทามติที่อยู่เบื้องหลัง cryptocurrencies เช่น Bitcoin และระบบ blockchain อื่นๆ ถือได้ว่าเป็นวิธีให้ฝ่ายที่ไม่ไว้วางใจซึ่งกันและกันตกลงกันว่า ธุรกรรมเกิดขึ้นหรือไม่ โดยไม่ต้องพึ่งพาผู้มีอำนาจส่วนกลาง [ 100 ].

อย่างไรก็ตาม ในระบบประเภทที่เราพูดถึงในหนังสือเล่มนี้ เรามักจะสรุปได้อย่างปลอดภัยว่าไม่มี Byzantine faults ใน datacenter node ทั้งหมดถูกควบคุมโดยองค์กรของคุณ (ดังนั้นหวังว่าจะเชื่อถือได้) และระดับรังสีต่ำพอที่ความเสียหายของหน่วยความจำไม่ใช่ปัญหาใหญ่ (แม้ว่า datacenters ในวงโคจรกำลังถูกพิจารณา [ 101 ]) ระบบ multitenant มีผู้เช่าที่ไม่ไว้วางใจซึ่งกันและกัน แต่พวกมันถูกแยกจากกันด้วย firewalls, virtualization และ access control policies ไม่ใช่การใช้ Byzantine fault tolerance โปรโตคอลสำหรับทำให้ระบบ Byzantine fault-tolerant มีราคาค่อนข้างแพง [ 102 ] และระบบ embedded ที่ทนทานต่อ fault พึ่งพาการสนับสนุนจากระดับฮาร์ดแวร์ [ 98 ]. ในระบบข้อมูลฝั่งเซิร์ฟเวอร์ส่วนใหญ่ ต้นทุนของการปรับใช้โซลูชัน Byzantine fault-tolerant ทำให้มันไม่สามารถปฏิบัติได้

เว็บแอปพลิเคชันต้องคาดหวังพฤติกรรมตามอำเภอใจและประสงค์ร้ายจาก clients ที่อยู่ภายใต้การควบคุมของผู้ใช้ปลายทาง เช่น เว็บเบราว์เซอร์ นี่คือเหตุผลที่ input validation, sanitization และ output escaping มีความสำคัญมาก: เพื่อป้องกัน SQL injection และ cross-site scripting อย่างไรก็ตาม เรามักจะไม่ใช้ Byzantine fault-tolerant protocols ที่นี่ แต่เพียงทำให้เซิร์ฟเวอร์เป็นผู้มีอำนาจในการกำหนดว่าพฤติกรรม client อะไรได้รับอนุญาตและไม่อนุญาต ในเครือข่าย peer-to-peer ที่ไม่มีผู้มีอำนาจส่วนกลางเช่นนี้ Byzantine fault tolerance มีความเกี่ยวข้องมากกว่า [ 103 , 104 ].

บั๊กในซอฟต์แวร์อาจถือเป็น Byzantine fault แต่ถ้าคุณ deploy ซอฟต์แวร์เดียวกันไปยังทุก node อัลกอริทึม Byzantine fault-tolerant ก็ไม่สามารถช่วยคุณได้ อัลกอริทึม Byzantine fault-tolerant ส่วนใหญ่ต้องการ supermajority มากกว่าสองในสามของ node ที่ทำงานถูกต้อง (เช่น ถ้าคุณมีสี่ node อย่างมากหนึ่งตัวอาจทำงานผิดปกติ) เพื่อใช้วิธีการนี้กับบั๊ก คุณจะต้องมี implementations อิสระสี่ตัวของซอฟต์แวร์เดียวกัน และหวังว่าบั๊กที่กำหนดจะปรากฏ ในเพียงหนึ่งในสี่ implementations

ในทำนองเดียวกัน มันคงจะดีถ้าโปรโตคอลสามารถป้องกันเราจาก ช่องโหว่ การถูกบุกรุกด้านความปลอดภัย และการโจมตีที่ประสงค์ร้าย โชคไม่ดีที่สิ่งนี้ก็ไม่สมจริงเช่นกัน ในระบบส่วนใหญ่ ถ้าผู้โจมตีสามารถบุกรุกหนึ่ง node ได้ อาจสามารถบุกรุกทั้งหมดได้ เพราะ node อาจรันซอฟต์แวร์เดียวกัน ดังนั้นกลไกดั้งเดิม (authentication, access control, encryption, firewalls และอื่นๆ) ยังคงเป็นการป้องกันหลักต่อผู้โจมตี

Weak forms of lying (รูปแบบการโกหกแบบอ่อน)

แม้ว่าเราสมมติว่า node โดยทั่วไปซื่อสัตย์ การเพิ่มกลไกในซอฟต์แวร์ที่ป้องกัน "การโกหก" ในรูปแบบอ่อน ก็คุ้มค่า—เช่น ข้อความที่ไม่ถูกต้องเนื่องจากปัญหาฮาร์ดแวร์, บั๊กซอฟต์แวร์ และการตั้งค่าผิดพลาด กลไกป้องกันดังกล่าวไม่ใช่ Byzantine fault tolerance เต็มรูปแบบ เพราะมันจะไม่ต้านทาน adversaries ที่มุ่งมั่น แต่มันก็เป็นขั้นตอนที่เรียบง่ายและปฏิบัติได้จริงสู่ความน่าเชื่อถือที่ดีขึ้น ตัวอย่างเช่น:

• Network packets บางครั้งถูกทำให้เสียหายเนื่องจากปัญหาฮาร์ดแวร์หรือบั๊กในระบบปฏิบัติการ, driver, router ฯลฯ โดยปกติ packet ที่เสียหายจะถูกจับโดย checksums ที่สร้างขึ้นใน TCP และ UDP แต่บางครั้งมันก็หลุดรอดการตรวจจับ [ 105 , 106 , 107 ]. มาตรการง่ายๆ มักเพียงพอต่อการป้องกันความเสียหายดังกล่าว เช่น checksum ในโปรโตคอลระดับแอปพลิเคชัน การเชื่อมต่อที่เข้ารหัสด้วย TLS ก็ช่วยป้องกันความเสียหายเช่นกัน

• แอปพลิเคชันที่เข้าถึงได้สาธารณะต้อง sanitize input ของผู้ใช้อย่างระมัดระวัง —เช่น escape อักขระบางตัวเพื่อป้องกัน SQL injection, ตรวจสอบว่าค่าอยู่ในช่วงที่เหมาะสม, และจำกัดขนาดของ string เพื่อป้องกัน denial of service ผ่านการจัดสรรหน่วยความจำขนาดใหญ่ บริการภายในที่อยู่หลัง firewall อาจไม่ต้องตรวจสอบ input อย่างเข้มงวด แต่การตรวจสอบพื้นฐานใน protocol parsers ก็ยังเป็นความคิดที่ดี [ 105 ].

• NTP clients สามารถกำหนดค่าด้วยที่อยู่เซิร์ฟเวอร์หลายแห่ง เมื่อซิงโครไนซ์ client จะติดต่อทั้งหมด ประมาณการ error ของพวกมัน และตรวจสอบว่าเซิร์ฟเวอร์ส่วนใหญ่เห็นด้วยกับช่วงเวลา ตราบใดที่เซิร์ฟเวอร์ส่วนใหญ่โอเค NTP server ที่ตั้งค่าผิด ซึ่งรายงานเวลาที่ไม่ถูกต้องจะถูกตรวจจับเป็นค่าผิดปกติและถูกแยกออกจากการซิงโครไนซ์ [ 39 ]. การใช้หลายเซิร์ฟเวอร์ทำให้ NTP ทนทานมากขึ้น กว่าถ้ามันใช้เซิร์ฟเวอร์เดียว

System Model and Reality (System Model และความเป็นจริง)

อัลกอริทึมมากมายถูกออกแบบมาเพื่อแก้ปัญหาระบบกระจาย—ตัวอย่างเช่น เราจะตรวจสอบโซลูชันสำหรับปัญหา consensus ใน Chapter 10 . เพื่อให้มีประโยชน์ อัลกอริทึมเหล่านี้ต้องทนต่อ fault ต่างๆ ของระบบกระจายที่เราได้พูดคุยในบทนี้

อัลกอริทึมต้องถูกเขียนในลักษณะที่ไม่พึ่งพารายละเอียดของฮาร์ดแวร์และซอฟต์แวร์ ที่มันทำงานมากเกินไป ซึ่งต้องการให้เราทำให้ fault ที่เราคาดหวังว่าจะเกิดขึ้นในระบบเป็นทางการ เราทำสิ่งนี้โดยการกำหนด system model ซึ่งเป็นนามธรรมที่อธิบายสมมติฐานของอัลกอริทึม

ในส่วนของสมมติฐานเกี่ยวกับ timing มีสาม system models ที่ใช้กันทั่วไป:

Synchronous model

Synchronous model สมมติ bounded network delay, bounded process pauses และ bounded clock error นี่ไม่ได้หมายถึง clock ที่ซิงโครไนซ์อย่างแม่นยำหรือ network delay เป็นศูนย์; มันหมายถึงคุณรู้ว่า network delay, pauses และ clock drift จะไม่มีวันเกินขอบเขตบนที่แน่นอน [ 108 ]. Synchronous model ไม่ใช่ model ที่สมจริงสำหรับระบบปฏิบัติจริงส่วนใหญ่ เพราะ (ดังที่ได้กล่าวถึงในบทนี้) unbounded delays และ pauses เกิดขึ้นจริง

Partially synchronous model

Partial synchrony หมายความว่าระบบทำงานเหมือน synchronous system เป็นส่วนใหญ่ แต่บางครั้งมันก็เกินขอบเขตของ network delay, process pauses และ clock drift [ 108 ]. นี่เป็น model ที่สมจริงสำหรับหลายระบบ ส่วนใหญ่แล้วเครือข่ายและ process ทำงานค่อนข้างดี— มิฉะนั้นเราจะไม่สามารถทำอะไรสำเร็จได้— แต่เราต้องคำนึงถึงความจริงที่ว่าสมมติฐาน timing ใดๆ อาจถูกทำลายในบางครั้ง เมื่อสิ่งนี้เกิดขึ้น network delay, pauses และ clock error อาจใหญ่ตามอำเภอใจ

Asynchronous model

ใน model นี้ อัลกอริทึมไม่ได้รับอนุญาตให้ตั้งสมมติฐาน timing ใดๆ —ในความเป็นจริง มันไม่มี clock ด้วยซ้ำ (ดังนั้นมันไม่สามารถใช้ timeout ได้) อัลกอริทึมบางอันสามารถถูกออกแบบสำหรับ asynchronous model แต่มันถูกจำกัดอย่างมาก

นอกจากปัญหา timing แล้ว เรายังต้องพิจารณา node failures ด้วย system models ทั่วไปบางประการสำหรับ node มีดังนี้:

Crash-stop faults

ใน crash-stop (หรือ fail-stop ) model อัลกอริทึมอาจสมมติว่า node สามารถล้มเหลวได้ในทางเดียวเท่านั้น —นั่นคือโดยการ crash [ 109 ]. Node อาจหยุดตอบสนองทันทีทุกเมื่อ และหลังจากนั้น node นั้นจะหายไปตลอดกาล—มันไม่มีวันกลับมา

Crash-recovery faults

ใน crash-recovery model เราสมมติว่า node อาจ crash ทุกเมื่อ และอาจเริ่มตอบสนองอีกครั้งหลังจากเวลาที่ไม่ทราบ Node ถูกสมมติว่ามี stable storage (นั่นคือ nonvolatile disk storage) ที่ถูกเก็บรักษาไว้ข้าม crash ในขณะที่สถานะในหน่วยความจำถูกสมมติว่าสูญหาย

Degraded performance and partial functionality

นอกเหนือจากการ crash และ restart node อาจช้าลง พวกมันอาจยังสามารถตอบสนองต่อ health check requests แต่ช้าเกินกว่าจะทำงานจริงใดๆ ตัวอย่างเช่น network interface Gigabit อาจลด throughput ลงเหลือ 1 Kb/s ทันทีเพราะบั๊ก driver [ 110 ]; process ที่อยู่ภายใต้แรงดันหน่วยความจำ อาจใช้เวลาส่วนใหญ่ไปกับการทำ garbage collection [ 111 ]; SSDs ที่เสื่อมสภาพอาจมีประสิทธิภาพที่ไม่สม่ำเสมอ; และฮาร์ดแวร์อาจได้รับผลกระทบจากอุณหภูมิสูง, ขั้วต่อหลวม, การสั่นสะเทือนทางกล, ปัญหาแหล่งจ่ายไฟ, บั๊ก firmware และอื่นๆ [ 112 ]. สถานการณ์เช่นนี้เรียกว่า limping node , gray failure , หรือ fail-slow [ 113 ] และมันอาจจัดการได้ยากกว่า node ที่ล้มเหลวอย่างสมบูรณ์ ปัญหาที่เกี่ยวข้องเกิดขึ้นเมื่อ process หยุดทำบางสิ่งที่มันควรจะทำ ในขณะที่ด้านอื่นยังคงทำงาน—เช่น เพราะ background thread crash หรือ deadlock [ 114 ].

Byzantine (arbitrary) faults

Node อาจทำอะไรก็ได้ รวมถึงพยายามหลอกลวงและโกหก node อื่น ดังที่อธิบายในหัวข้อก่อนหน้า

สำหรับการสร้างโมเดลระบบจริง partially synchronous model ที่มี crash-recovery faults โดยทั่วไปมีประโยชน์มากที่สุด มันอนุญาตให้มี unbounded network delay, process pauses และ slow nodes แต่ distributed algorithms รับมือกับ model นั้นได้อย่างไร?

Defining the correctness of an algorithm (การกำหนดความถูกต้องของอัลกอริทึม)

เพื่อกำหนดว่าอัลกอริทึม ถูกต้อง หมายถึงอะไร เราสามารถอธิบาย properties ของมัน ตัวอย่างเช่น ผลลัพธ์ของ sorting algorithm มี property ที่ว่าสำหรับสอง element ที่แตกต่างกันใน output list element ที่อยู่ทางซ้ายกว่าจะมีค่าน้อยกว่า element ที่อยู่ทางขวากว่า นั่นเป็นเพียงวิธีที่เป็นทางการในการกำหนดว่าการเรียงลำดับ list หมายถึงอะไร —invariant ของ sorted list

ในทำนองเดียวกัน เราสามารถเขียน properties ที่เราต้องการของ distributed algorithm เพื่อกำหนดว่ามันหมายถึงอะไรที่จะถูกต้อง ตัวอย่างเช่น ถ้าเรากำลังสร้าง fencing tokens สำหรับ lock (ดู "Fencing off zombies and delayed requests" ) เราอาจต้องการให้อัลกอริทึมมี properties ดังต่อไปนี้:

Uniqueness

ไม่มีสองคำขอสำหรับ fencing token ที่คืนค่าเดียวกัน

Monotonic sequence

ถ้าคำขอ x คืน token t x , และคำขอ y คืน token t y , และ x เสร็จก่อน y เริ่ม, ดังนั้น t x  <  t y .

Availability

Node ที่ขอ fencing token และไม่ crash จะได้รับการตอบกลับในที่สุด

อัลกอริทึมจะถูกต้องใน system model ถ้ามันเป็นไปตาม properties ของมันเสมอ ในทุกสถานการณ์ที่เราสมมติว่าอาจเกิดขึ้นใน system model นั้น อย่างไรก็ตาม ถ้า node ทั้งหมด crash หรือ network delays ทั้งหมดยาวเป็นอนันต์ ก็ไม่มีอัลกอริทึมใดที่จะสามารถทำอะไรสำเร็จได้ เราจะยังคงให้การรับประกันที่มีประโยชน์ได้อย่างไร แม้ใน system model ที่อนุญาตให้เกิดความล้มเหลวอย่างสมบูรณ์?

Distinguishing between safety and liveness (การแยกแยะระหว่าง Safety และ Liveness)

เพื่อให้สถานการณ์ชัดเจน มันคุ้มค่าที่จะแยกแยะระหว่าง properties สองประเภท: safety และ liveness . ในตัวอย่างที่ให้มา uniqueness และ monotonic sequence เป็น safety properties แต่ availability เป็น liveness property

อะไรที่แยก properties ทั้งสองประเภท? จุดสังเกตคือ liveness properties มักรวมคำว่า "inที่สุด" ในคำจำกัดความ (และใช่ คุณเดาถูก— eventual consistency เป็น liveness property [ 115 ].)

Safety มักถูกกำหนดอย่างไม่เป็นทางการว่า nothing bad happens และ liveness ว่า something good eventually happens . อย่างไรก็ตาม ดีที่สุดคือไม่ตีความมากเกินไปจากคำจำกัดความที่ไม่เป็นทางการเหล่านั้น เพราะ "good" และ "bad" เป็น judgment ที่ใช้กับอัลกอริทึมได้ไม่ดีนัก คำจำกัดความที่แท้จริงของ safety และ liveness นั้นแม่นยำกว่า [ 116 ]:

• ถ้า safety property ถูกละเมิด เราสามารถชี้ไปยังจุดในเวลาที่มันถูกทำลาย (เช่น ถ้า uniqueness property ถูกละเมิด เราสามารถระบุ operation ที่ fencing token ซ้ำถูกคืน) หลังจาก safety property ถูกละเมิด การละเมิดไม่สามารถแก้ไขได้ —ความเสียหายเกิดขึ้นแล้ว

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

ข้อดีของการแยกแยะระหว่าง safety และ liveness properties คือมันช่วยเราจัดการกับ system models ที่ยาก สำหรับ distributed algorithms เป็นเรื่องปกติที่จะกำหนดให้ safety properties เป็นจริงเสมอ ในทุกสถานการณ์ที่เป็นไปได้ของ system model [ 108 ]. แม้ว่า node ทั้งหมด crash หรือเครือข่ายทั้งหมดล้มเหลว อัลกอริทึมต้องรับประกันว่ามันไม่คืนผลลัพธ์ที่ผิด (นั่นคือ safety properties ยังคงเป็นที่พอใจ)

อย่างไรก็ตาม สำหรับ liveness properties เราได้รับอนุญาตให้มีข้อแม้ —เช่น เราสามารถบอกว่าคำขอต้องการได้รับการตอบกลับ เฉพาะถ้า node ส่วนใหญ่ไม่ crash และเฉพาะถ้าเครือข่ายฟื้นตัวจาก outage ในที่สุด คำจำกัดความของ partially synchronous model กำหนดว่า ในที่สุดระบบจะกลับสู่สถานะ synchronous —นั่นคือระยะเวลาของ network interruption ใดๆ จะมีระยะเวลาจำกัดและได้รับการซ่อมแซม

Mapping system models to the real world (การจับคู่ System Models กับโลกจริง)

Safety และ liveness properties และ system models มีประโยชน์มากสำหรับการใช้เหตุผลเกี่ยวกับความถูกต้องของ distributed algorithm อย่างไรก็ตาม เมื่อ implement อัลกอริทึมในทางปฏิบัติ ข้อเท็จจริงที่ยุ่งเหยิงของความเป็นจริงกลับมากัดเราอีกครั้ง และมันชัดเจนว่าระบบ model เป็นนามธรรมที่เรียบง่ายของความเป็นจริง

ตัวอย่างเช่น อัลกอริทึมใน crash-recovery model มักสมมติว่า ข้อมูลใน stable storage อยู่รอดจากการ crash อย่างไรก็ตาม จะเกิดอะไรขึ้นถ้าข้อมูลบนดิสก์ถูกทำให้เสียหายหรือถูกลบ โดย error ของฮาร์ดแวร์หรือการตั้งค่าผิด [ 117 ]? จะเกิดอะไรขึ้นถ้าเซิร์ฟเวอร์มีบั๊ก firmware และไม่รู้จัก hard drives ของมันเมื่อรีบูต แม้ว่า drives จะต่อกับเซิร์ฟเวอร์อย่างถูกต้อง [ 118 ]?

Quorum algorithms (ดู "Using quorums for reading and writing" ) พึ่งพา node ที่จำข้อมูลที่มันอ้างว่าเก็บไว้ ถ้า node อาจมี amnesia และลืมข้อมูลที่เก็บไว้ก่อนหน้านี้ มันจะทำลายเงื่อนไขของ quorum และดังนั้นจึงทำให้ความถูกต้องของอัลกอริทึมเสียหาย บางที system model ใหม่อาจจำเป็น ซึ่งเราสมมติว่า stable storage ส่วนใหญ่รอดจากการ crash แต่บางครั้งอาจสูญหาย แต่ model นั้นก็จะยากขึ้นที่จะใช้เหตุผล

คำอธิบายเชิงทฤษฎีของอัลกอริทึมสามารถประกาศว่าบางสิ่ง ถูกสมมติว่าไม่เกิดขึ้น—และในระบบที่ไม่ใช่ Byzantine เราต้องตั้งสมมติฐานเกี่ยวกับ fault ที่สามารถและไม่สามารถเกิดขึ้นได้ อย่างไรก็ตาม การ implement จริงอาจยังต้องรวมโค้ด เพื่อจัดการกับกรณีที่สิ่งที่ถูกสมมติว่าเป็นไปไม่ได้เกิดขึ้น แม้ว่าการจัดการนั้นจะลงเอยด้วย printf("Sucks to be you") และ exit(666) —นั่นคือให้ผู้ปฏิบัติงานที่เป็นมนุษย์มาจัดการ [ 119 ]. (นี่คือหนึ่งในความแตกต่างระหว่างวิทยาการคอมพิวเตอร์และวิศวกรรมซอฟต์แวร์)

นั่นไม่ได้หมายความว่า system models เชิงทฤษฎีที่เป็นนามธรรมไม่มีค่า —ตรงกันข้ามเลย มันมีประโยชน์อย่างเหลือเชื่อสำหรับการลดทอนความซับซ้อน ของระบบจริงให้เป็นชุด fault ที่จัดการได้ ที่เราสามารถใช้เหตุผลเกี่ยวกับมัน เพื่อให้เราเข้าใจปัญหาและพยายามแก้ไขอย่างเป็นระบบ

Formal Methods and Randomized Testing (วิธีการเชิงรูปแบบและการทดสอบแบบสุ่ม)

เราจะรู้ได้อย่างไรว่าอัลกอริทึมเป็นไปตาม properties ที่ต้องการ? เนื่องจาก concurrency, partial failures และ network delays มีสถานะที่เป็นไปได้จำนวนมหาศาล เราต้องรับประกันว่า properties ยังคงเป็นจริงในทุกสถานะที่เป็นไปได้ และแน่ใจว่าเราไม่ได้ลืม edge case ใดๆ

วิธีหนึ่งคือการตรวจสอบอัลกอริทึมอย่างเป็นทางการ (formally verify) โดยการอธิบายมันทางคณิตศาสตร์และใช้เทคนิคการพิสูจน์ เพื่อแสดงว่ามันเป็นไปตาม properties ที่ต้องการในทุกสถานการณ์ ที่ system model อนุญาต การพิสูจน์ว่าอัลกอริทึมถูกต้องไม่ได้หมายความว่า implementation บนระบบจริงจะทำงานได้ถูกต้องเสมอไป แต่มันเป็นขั้นตอนแรกที่ดีมาก เพราะการวิเคราะห์เชิงทฤษฎีสามารถเปิดเผยปัญหาในอัลกอริทึม ที่อาจซ่อนอยู่เป็นเวลานานในระบบจริง และจะมากัดคุณเมื่อสมมติฐานของคุณ (เช่น เกี่ยวกับ timing) ถูกทำลายโดยสถานการณ์ที่ไม่ปกติ

มันฉลาดที่จะรวมการวิเคราะห์เชิงทฤษฎีเข้ากับการทดสอบเชิงประจักษ์ เพื่อตรวจสอบว่า implementation ทำงานตามที่คาดหวัง เทคนิคเช่น property-based testing, fuzzing และ deterministic simulation testing ใช้การสุ่มเพื่อทดสอบระบบในสถานการณ์ที่หลากหลาย องค์กร เช่น Amazon Web Services, FoundationDB และ TigerBeetle ได้ใช้เทคนิคร่วมกันเหล่านี้สำเร็จในผลิตภัณฑ์หลายตัวของพวกเขา [ 120 , 121 , 122 , 123 ].

Model checking and specification languages (Model Checking และภาษา Specification)

Model checkers เป็นเครื่องมือที่ช่วยตรวจสอบว่าอัลกอริทึมหรือระบบทำงานตามที่คาดหวัง ข้อกำหนดของอัลกอริทึมถูกเขียนในภาษาที่สร้างขึ้นเพื่อจุดประสงค์เฉพาะ เช่น TLA+, Gallina หรือ FizzBee ภาษาเหล่านี้ทำให้ง่ายต่อการโฟกัสที่พฤติกรรมของอัลกอริทึม โดยไม่ต้องกังวลเกี่ยวกับรายละเอียดการ implement โค้ด จากนั้น model checkers ใช้โมเดลเหล่านี้เพื่อตรวจสอบว่า invariants เป็นจริงในทุกสถานะของอัลกอริทึม โดยการลองทุกสิ่งทุกอย่างที่อาจเกิดขึ้นอย่างเป็นระบบ

Model checking ไม่สามารถพิสูจน์ได้ว่า invariants ของอัลกอริทึม เป็นจริงสำหรับทุกสถานะที่เป็นไปได้ เพราะอัลกอริทึมในโลกจริงส่วนใหญ่มี state space ที่ไม่มีที่สิ้นสุด การตรวจสอบทุกสถานะอย่างแท้จริงจะต้องมีการพิสูจน์อย่างเป็นทางการ ซึ่งทำได้ แต่มักจะยากกว่าการรัน model checker แทนที่จะเป็นเช่นนั้น model checkers สนับสนุนให้คุณลดโมเดลของอัลกอริทึม เป็นการประมาณที่สามารถตรวจสอบได้อย่างสมบูรณ์ หรือจำกัดการทำงานให้มีขอบเขตบน (เช่น โดยกำหนดจำนวนข้อความสูงสุดที่สามารถส่งได้) บั๊กใดๆ ที่เกิดขึ้นเฉพาะในการทำงานที่ยาวนานกว่าก็จะไม่ถูกพบ

อย่างไรก็ตาม model checkers สร้างสมดุลที่ดีระหว่างความง่ายในการใช้ และความสามารถในการค้นหาบั๊กที่ไม่ชัดเจน CockroachDB, TiDB, Kafka และระบบกระจายอื่นๆ อีกมากมาย ใช้ model specifications เพื่อค้นหาและแก้ไขบั๊ก [ 124 , 125 , 126 ]. ตัวอย่างเช่น การใช้ TLA+ นักวิจัยสามารถแสดงให้เห็นถึงศักยภาพของการสูญเสียข้อมูล ใน viewstamped replication (VR) ที่เกิดจากความคลุมเครือ ในคำอธิบาย prose ของอัลกอริทึม [ 127 ].

โดยการออกแบบ model checkers ไม่ได้รันโค้ดจริงของคุณ แต่รันโมเดลที่เรียบง่ายที่ระบุเฉพาะแนวคิดหลักของโปรโตคอลของคุณ สิ่งนี้ทำให้สามารถสำรวจ state space ได้อย่างเป็นระบบมากขึ้น แต่มันเสี่ยงที่ specification และ implementation ของคุณ จะไม่สอดคล้องกัน [ 128 ]. มันเป็นไปได้ที่จะตรวจสอบว่าโมเดลและ implementation จริง มีพฤติกรรมที่เทียบเท่ากันหรือไม่ แต่สิ่งนี้ต้องการ instrumentation ใน implementation จริง [ 129 ].

Fault injection (การฉีด Fault)

บั๊กจำนวนมากถูกกระตุ้นเมื่อเกิดความล้มเหลวของเครื่องและเครือข่าย Fault injection เป็นเทคนิคที่มีประสิทธิภาพ (และบางครั้งก็น่ากลัว) ที่ตรวจสอบว่า implementation ของระบบทำงานตามที่คาดหวังหรือไม่เมื่อสิ่งต่างๆ ผิดพลาด แนวคิดนั้นง่าย: ฉีด fault เข้าสู่สภาพแวดล้อมของระบบที่กำลังทำงาน และดูว่ามันทำงานอย่างไร Fault อาจเป็น network failures, machine crashes, disk corruption, paused processes —อะไรก็ได้ที่คุณนึกออกว่าอาจผิดพลาดกับคอมพิวเตอร์

การทดสอบ fault injection มักรันในสภาพแวดล้อมที่คล้ายคลึงกับสภาพแวดล้อม production ที่ระบบจะทำงาน บางรายถึงกับฉีด fault โดยตรงในสภาพแวดล้อม production ของพวกเขา Netflix ทำให้แนวทางนี้เป็นที่นิยมด้วยเครื่องมือ Chaos Monkey [ 130 ]. Fault injection ใน production มักถูกเรียกเป็น chaos engineering ซึ่งเราได้กล่าวถึงใน "Reliability and Fault Tolerance" .

เพื่อรันการทดสอบ fault injection ระบบภายใต้การทดสอบจะถูกปรับใช้พร้อมกับ coordinators และ scripts สำหรับ fault injection Coordinators รับผิดชอบในการตัดสินใจว่า fault ใดที่จะดำเนินการและเมื่อไหร่ที่จะดำเนินการ สคริปต์ท้องถิ่นหรือระยะไกลรับผิดชอบในการฉีดความล้มเหลว ไปยัง node หรือ process แต่ละตัว สคริปต์การฉีดใช้เครื่องมือมากมายเพื่อกระตุ้น fault กระบวนการ Linux สามารถถูกหยุดหรือฆ่าได้โดยใช้คำสั่ง kill ของ Linux, ดิสก์สามารถถูก unmount ด้วย umount , และการเชื่อมต่อเครือข่ายสามารถถูกขัดจังหวะผ่านการตั้งค่า firewall คุณสามารถตรวจสอบพฤติกรรมของระบบระหว่างและหลังจากที่ fault ถูกฉีด เพื่อให้แน่ใจว่าสิ่งต่างๆ ทำงานตามที่คาดหวัง

เครื่องมือมากมายที่จำเป็นในการกระตุ้นความล้มเหลว ทำให้การทดสอบ fault injection ยุ่งยากในการเขียน เป็นเรื่องปกติที่จะใช้ framework fault injection เช่น Jepsen เพื่อรันการทดสอบ fault injection เพื่อลดความยุ่งยากของกระบวนการ framework ดังกล่าวมาพร้อมกับการผสานรวมกับระบบปฏิบัติการต่างๆ และตัวฉีด fault ที่สร้างไว้ล่วงหน้าหลายตัว [ 131 ]. Jepsen มีประสิทธิภาพอย่างโดดเด่นในการค้นหาบั๊กที่สำคัญ ในระบบที่ใช้กันอย่างแพร่หลายหลายระบบ [ 132 , 133 ].

Deterministic simulation testing (การทดสอบแบบจำลองสถานการณ์ที่กำหนดได้)

เทคนิคการทำให้เป็นทางการอีกวิธีหนึ่ง ซึ่งกลายเป็นส่วนเสริมที่ได้รับความนิยมสำหรับ model checking และ fault injection คือ deterministic simulation testing (DST) มันใช้กระบวนการสำรวจ state space ที่คล้ายกับ model checker แต่มันทดสอบโค้ดจริงของคุณ ไม่ใช่โมเดล

ใน DST การจำลองสถานการณ์จะรันผ่านการทำงานแบบสุ่มของระบบจำนวนมากโดยอัตโนมัติ การสื่อสารเครือข่าย I/O และ timing ของ clock ระหว่างการจำลอง ถูกแทนที่ด้วย mocks ที่ช่วยให้ simulator ควบคุมลำดับที่แน่นอนของสิ่งที่เกิดขึ้น รวมถึง timing และสถานการณ์ความล้มเหลวต่างๆ สิ่งนี้ช่วยให้ simulator สำรวจสถานการณ์ได้มากกว่าที่ handwritten tests หรือ fault injection จะทำได้ ถ้าการทดสอบล้มเหลว มันสามารถรันซ้ำได้เนื่องจาก simulator รู้ลำดับที่แน่นอน ของ operation ที่กระตุ้นความล้มเหลว —ตรงกันข้ามกับ fault injection ที่ไม่มีการควบคุมระบบอย่างละเอียดเช่นนี้

DST ต้องการให้ simulator สามารถควบคุมแหล่งที่มาของ nondeterminism ทั้งหมด เช่น network delays หรือ thread scheduling ใน multithreaded code โดยทั่วไปหนึ่งในสามกลยุทธ์ถูกนำมาใช้เพื่อทำให้โค้ด deterministic:

Application-level

บางระบบถูกสร้างขึ้นตั้งแต่ต้นเพื่อให้ง่ายต่อการรันโค้ดแบบ deterministic ตัวอย่างเช่น FoundationDB หนึ่งในผู้บุกเบิกในพื้นที่ DST ถูกสร้างขึ้นโดยใช้ asynchronous communication library ที่เรียกว่า Flow Flow ให้จุดสำหรับนักพัฒนาในการฉีด deterministic network simulation เข้าสู่ระบบ [ 134 ]. ในทำนองเดียวกัน TigerBeetle เป็น OLTP database ที่รองรับ DST เป็นสำคัญ สถานะของระบบถูกสร้างเป็น state machine โดยการกลายพันธุ์ทั้งหมดเกิดขึ้นภายใน event loop เดียว เมื่อรวมกับ primitives แบบ deterministic จำลองเช่น clocks สถาปัตยกรรมดังกล่าวสามารถทำงานแบบ deterministic [ 135 ].

Runtime-level

ภาษาที่มี asynchronous runtimes และ libraries ที่ใช้กันทั่วไป ให้จุดแทรกเพื่อนำความ deterministic มาใช้ runtime แบบ single-threaded ถูกใช้เพื่อบังคับให้โค้ด asynchronous ทั้งหมด รันตามลำดับ ตัวอย่างเช่น FrostDB patch Go's runtime เพื่อรัน goroutines ตามลำดับ [ 136 ]. ไลบรารี MadSim ของ Rust ทำงานในลักษณะเดียวกัน มันให้ deterministic implementations ของ Tokio's asynchronous runtime API, Amazon's S3 library, Kafka's Rust library และอื่นๆ อีกมากมาย; แอปพลิเคชันสามารถสลับใช้ deterministic libraries และ runtimes เพื่อให้ได้ deterministic test executions โดยไม่ต้องเปลี่ยนโค้ด

Machine-level

แทนที่จะ patch โค้ดที่ runtime เครื่องทั้งหมดสามารถถูกทำให้ deterministic ได้ นี่เป็นกระบวนการที่ละเอียดอ่อนที่ต้องให้เครื่องตอบสนองต่อ การเรียก nondeterministic ทั้งหมดด้วยการตอบสนองแบบ deterministic เครื่องมือเช่น Antithesis ทำสิ่งนี้โดยการสร้าง custom hypervisor ที่แทนที่ operation nondeterministic ปกติด้วย operation deterministic ทุกอย่างตั้งแต่ clock ไปจนถึงเครือข่ายและ storage ต้องถูกจัดการ เมื่อเสร็จแล้ว นักพัฒนาสามารถรันระบบกระจายทั้งหมดของพวกเขา ในคอลเลกชันของ containers ภายใน hypervisor และได้รับระบบกระจายที่ deterministic อย่างสมบูรณ์

DST ให้ข้อดีหลายอย่างนอกเหนือจากการเล่นซ้ำได้ ตัวอย่างเช่น Antithesis พยายามสำรวจหลาย paths ใน application code โดยการแยกการทำงานของ test ออกเป็นหลาย subexecutions เมื่อมันค้นพบพฤติกรรมที่พบได้น้อยกว่า และเนื่องจาก deterministic tests มักใช้ mocked clocks และ network calls การทดสอบดังกล่าวสามารถรันได้เร็วกว่า wall clock time ตัวอย่างเช่น time abstraction ของ TigerBeetle ช่วยให้ simulations จำลอง network latency และ timeouts โดยไม่ต้องใช้เวลาจริงทั้งหมดในการกระตุ้น timeout เทคนิคดังกล่าวช่วยให้ simulator สำรวจ code paths ได้มากขึ้นเร็วขึ้น

The Power of Determinism (พลังของ Determinism)

Nondeterminism อยู่ที่แกนกลางของความท้าทายระบบกระจายทั้งหมด ที่เราได้กล่าวถึงในบทนี้: concurrency, network delay, process pauses, clock jumps และ crashes ล้วนเกิดขึ้นในรูปแบบที่คาดเดาไม่ได้ที่แตกต่างกันไปในแต่ละการรันของระบบ ในทางตรงกันข้าม ถ้าคุณสามารถทำให้ระบบ deterministic ได้ นั่นสามารถทำให้สิ่งต่างๆ ง่ายขึ้นอย่างมหาศาล

ในความเป็นจริง การทำให้สิ่งต่างๆ deterministic เป็นแนวคิดที่เรียบง่ายแต่ทรงพลัง ที่เกิดขึ้นซ้ำแล้วซ้ำเล่าในการออกแบบระบบกระจาย นอกเหนือจากการ deterministic simulation testing เราได้เห็นหลายวิธีในการใช้ determinism ในบทที่ผ่านมา:

• ข้อดีสำคัญของ event sourcing (ดู "Event Sourcing and CQRS" ) คือคุณสามารถ deterministic replay log ของเหตุการณ์ เพื่อสร้าง derived materialized views ขึ้นมาใหม่

• Workflow engines (ดู "Durable Execution and Workflows" ) พึ่งพาคำจำกัดความของ workflow ที่เป็น deterministic เพื่อให้ durable execution semantics

• State machine replication ซึ่งเราจะพูดถึงใน "Using shared logs" จำลองข้อมูลโดยการรันลำดับเดียวกันของ deterministic transactions บนแต่ละ replica อย่างอิสระ เราได้เห็นสองรูปแบบของแนวคิดนั้นแล้ว: statement-based replication (ดู "Implementation of Replication Logs" ) และ serial transaction execution โดยใช้ stored procedures (ดู "Pros and cons of stored procedures" ).

อย่างไรก็ตาม การทำให้โค้ด deterministic อย่างสมบูรณ์ต้องใช้ความระมัดระวัง แม้ว่าคุณจะลบ concurrency ทั้งหมดและแทนที่ I/O, การสื่อสารเครือข่าย, clocks และ random number generators ด้วยการจำลองแบบ deterministic แล้ว องค์ประกอบของ nondeterminism อาจยังคงอยู่ ตัวอย่างเช่น ในภาษาโปรแกรมบางภาษา ลำดับที่คุณ iterate ผ่าน element ของ hash table อาจเป็น nondeterministic ไม่ว่าคุณจะถึง resource limit (memory allocation failure, stack overflow) ก็เป็น nondeterministic เช่นกัน

Summary (สรุป)

ในบทนี้เราได้พูดถึงปัญหามากมายที่สามารถเกิดขึ้นในระบบกระจาย ตัวอย่างเช่น:

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

• Clock ของ node อาจคลาดเคลื่อนอย่างมากจาก node อื่น (แม้ว่าคุณจะพยายามตั้งค่า NTP อย่างดีที่สุด) มันอาจกระโดดไปข้างหน้าหรือถอยหลังในเวลาอย่างกะทันหัน และการพึ่งพามันเป็นอันตรายเพราะคุณส่วนใหญ่ไม่มีค่าประมาณที่ดี ของ confidence interval ของ clock

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

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

เพื่อทนต่อ fault ขั้นตอนแรกคือการ ตรวจจับ พวกมัน แต่แม้แต่นั้นก็ยาก ระบบส่วนใหญ่ไม่มีกลไกที่แม่นยำสำหรับการตรวจจับว่า node ล้มเหลวหรือไม่ ดังนั้น distributed algorithms ส่วนใหญ่พึ่งพา timeouts เพื่อตรวจสอบว่า node ระยะไกลยังคงพร้อมใช้งานหรือไม่ อย่างไรก็ตาม timeouts ไม่สามารถแยกแยะระหว่างความล้มเหลวของเครือข่ายและ node และ network delay ที่แปรปรวนบางครั้งทำให้ node ถูกสงสัยอย่างผิดพลาดว่าล้มเหลว การจัดการกับ limping nodes ที่ตอบสนองแต่ช้าเกินกว่าจะทำอะไรที่มีประโยชน์ ยิ่งยากกว่า

เมื่อตรวจพบ fault แล้ว การทำให้ระบบทนต่อมันก็ไม่ใช่เรื่องง่ายเช่นกัน ไม่มี global variable, ไม่มี shared memory, ไม่มีความรู้ร่วมกันหรือสถานะแชร์อื่นใดระหว่างเครื่อง [ 83 ]. Node ไม่สามารถตกลงกันด้วยซ้ำว่าตอนนี้กี่โมง นับประสาอะไรกับสิ่งที่ลึกซึ้งกว่านั้น วิธีเดียวที่ข้อมูลจะไหลจาก node หนึ่งไปยังอีก node คือการส่งผ่านเครือข่ายที่ไม่น่าเชื่อถือ การตัดสินใจสำคัญไม่สามารถทำโดย node เดียวอย่างปลอดภัย ดังนั้นเราจึงต้องการโปรโตคอลที่ขอความช่วยเหลือจาก node อื่น และพยายามให้ quorum เห็นด้วย

ถ้าคุณคุ้นเคยกับการเขียนซอฟต์แวร์ในโลกอุดมคติทางคณิตศาสตร์ของคอมพิวเตอร์เครื่องเดียว ที่ operation เดียวกันคืนผลลัพธ์เดียวกันแบบ deterministic เสมอ การย้ายสู่ความเป็นจริงทางกายภาพที่ยุ่งเหยิงของระบบกระจายอาจเป็นเรื่องช็อค ในทางกลับกัน วิศวกรระบบกระจายมักจะมองว่าปัญหาเป็นเรื่องเล็กน้อย ถ้ามันสามารถแก้ไขได้บนคอมพิวเตอร์เครื่องเดียว [ 4 ] และแน่นอนว่าคอมพิวเตอร์เครื่องเดียวสามารถทำอะไรได้มากมายในปัจจุบัน ถ้าคุณสามารถหลีกเลี่ยงการเปิดกล่องแพนโดร่าและเก็บทุกอย่างไว้บนเครื่องเดียว —เช่น โดยใช้ embedded storage engine (ดู "Embedded Storage Engines" )—โดยทั่วไปแล้วมันคุ้มค่าที่จะทำ

อย่างไรก็ตาม ดังที่ได้กล่าวถึงใน "Distributed Versus Single-Node Systems" scalability ไม่ใช่เหตุผลเดียวที่อยากใช้ระบบกระจาย Fault tolerance และ low latency (โดยวางข้อมูลไว้ใกล้ผู้ใช้ตามภูมิศาสตร์) เป็นเป้าหมายที่สำคัญเท่าเทียมกัน และไม่สามารถบรรลุได้ด้วย node เดียว พลังของระบบกระจายคือ โดยหลักการแล้ว พวกมันสามารถรันได้ตลอดไป โดยไม่ถูกขัดจังหวะในระดับบริการ เพราะ fault และการบำรุงรักษาทั้งหมดสามารถจัดการได้ในระดับ node (ในทางปฏิบัติ ถ้าการเปลี่ยนแปลง configuration ที่ไม่ดี ถูกปรับใช้กับทุก node มันก็ยังทำให้ระบบกระจายล้มลงได้)

ในบทนี้เรายังได้ไปในทางอ้อมเพื่อสำรวจว่าความไม่น่าเชื่อถือของเครือข่าย, clock และ process เป็นกฎของธรรมชาติที่หลีกเลี่ยงไม่ได้หรือไม่ เราเห็นว่ามันไม่ใช่: มันเป็นไปได้ที่จะให้การรับประกัน hard real-time response และ bounded delays ในเครือข่าย แต่การทำเช่นนั้นแพงมากและส่งผลให้การใช้ทรัพยากรฮาร์ดแวร์ต่ำลง ระบบที่ไม่ใช่ safety-critical ส่วนใหญ่เลือกที่ถูกและไม่น่าเชื่อถือ มากกว่าแพงและเชื่อถือได้

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