“อย่าออกทะเลไปกับนาฬิกาสองเรือน จงพาไปหนึ่งหรือสามเรือน” — คำโบราณกล่าวไว้

Frederick P. Brooks Jr., The Mythical Man-Month: Essays on Software Engineering (1995)

ปัญหามากมายสามารถเกิดขึ้นได้ในระบบกระจาย (distributed systems) ดังที่ได้กล่าวถึงใน Chapter 9 หากเราต้องการให้บริการทำงานอย่างถูกต้องต่อไปแม้จะเจอปัญหาเหล่านั้น เราจำเป็นต้องหาวิธีในการทนต่อความผิดพลาด (fault tolerance)

หนึ่งในเครื่องมือที่ดีที่สุดสำหรับ fault tolerance คือ การจำลองข้อมูล (replication) อย่างไรก็ตาม ดังที่เราเห็นใน Chapter 6 การมีข้อมูลหลายชุดบนหลาย replica จะเพิ่มความเสี่ยงของความไม่สอดคล้องกัน (inconsistencies) การอ่านอาจถูกจัดการโดย replica ที่ไม่ทันสมัย ทำให้ได้ข้อมูลที่เก่า (stale) ถ้า replica หลายตัวสามารถรับ write ได้ เราก็ต้องจัดการกับความขัดแย้งที่อาจเกิดขึ้นระหว่างค่าที่ถูกเขียนพร้อมกันบน replica ที่แตกต่างกัน ในระดับสูง เรามีแนวทางที่แข่งขันกันสองแนวทางในการจัดการกับปัญหาเหล่านี้:

Eventual consistency (ความสอดคล้องแบบท้ายที่สุด)

ในแนวทางนี้ ข้อเท็จจริงที่ว่าระบบมีการจำลองข้อมูลจะถูกเปิดเผยให้แอปพลิเคชันเห็น และคุณในฐานะนักพัฒนาแอปพลิเคชันจะต้องจัดการกับความไม่สอดคล้องและความขัดแย้งที่อาจเกิดขึ้น แนวทางนี้มักใช้ในระบบที่มี multi-leader (ดู "Multi-Leader Replication" ) และ leaderless replication (ดู "Leaderless Replication" )

Strong consistency (ความสอดคล้องแบบเข้มงวด)

แนวทางนี้บอกว่าแอปพลิเคชันไม่ควรต้องมากังวลกับรายละเอียดภายในของการจำลองข้อมูล และระบบควรทำงานราวกับว่ามันเป็นโหนดเดียว ข้อดีของแนวทางนี้คือมันง่ายกว่าสำหรับคุณในฐานะนักพัฒนาแอปพลิเคชัน ข้อเสียคือความสอดคล้องแบบเข้มงวดมีต้นทุนด้านประสิทธิภาพ และความผิดพลาดบางประเภทที่ระบบ eventual consistency สามารถทนได้อาจทำให้ระบบ strong consistency เกิดการหยุดชะงักได้

เช่นเคย แนวทางไหนดีกว่าก็ขึ้นอยู่กับแอปพลิเคชันของคุณ ถ้าแอปของคุณอนุญาตให้ผู้ใช้เปลี่ยนแปลงข้อมูลขณะออฟไลน์ eventual consistency ก็เป็นสิ่งที่หลีกเลี่ยงไม่ได้ ดังที่กล่าวถึงใน "Sync Engines and Local-First Software" อย่างไรก็ตาม eventual consistency อาจเป็นเรื่องยากสำหรับแอปพลิเคชันในการจัดการ ถ้า replica ของคุณอยู่ใน datacenter ที่มีการสื่อสารที่รวดเร็วและเชื่อถือได้ strong consistency ก็มักจะเหมาะสมเพราะต้นทุนของมันเป็นที่ยอมรับได้

ในบทนี้เราจะเจาะลึกเข้าไปในแนวทาง strong consistency โดยเน้นที่สามหัวข้อ:

  • ความท้าทายหนึ่งคือ "strong consistency" เป็นคำที่ค่อนข้างคลุมเครือ ดังนั้นเราจะพัฒนาคำจำกัดความที่แม่นยำยิ่งขึ้นของสิ่งที่เราต้องการให้บรรลุ: linearizability

  • เราจะดูปัญหาของการสร้าง ID และ timestamp สิ่งนี้อาจฟังดูไม่เกี่ยวข้องกับความสอดคล้อง แต่มันเชื่อมโยงกันอย่างใกล้ชิด

  • เราจะสำรวจว่าระบบกระจายสามารถบรรลุ linearizability ในขณะที่ยังคงทนต่อความผิดพลาดได้อย่างไร — คำตอบคือ consensus algorithms

ระหว่างทาง เราจะเห็นว่ามีข้อจำกัดพื้นฐานเกี่ยวกับสิ่งที่เป็นไปได้ในระบบกระจาย

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

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

Linearizability (ความเป็นเชิงเส้น)

ถ้าคุณต้องการให้ฐานข้อมูลแบบจำลองข้อมูล (replicated database) ใช้งานง่ายที่สุด คุณควรทำให้มันทำงานราวกับว่ามันเป็นฐานข้อมูลโหนดเดียวที่สอดคล้องกัน ผู้ใช้จะได้ไม่ต้องกังวลเกี่ยวกับ replication lag, conflicts, และความไม่สอดคล้องอื่นๆ มันให้ข้อดีของ fault tolerance แต่ไม่ต้องมีความซับซ้อนในการคิดถึง replica หลายตัว

นี่คือแนวคิดเบื้องหลัง linearizability [ 1 ] (หรือที่รู้จักในชื่อ atomic consistency [ 2 ], strong consistency , immediate consistency หรือ external consistency [ 3 ]) คำจำกัดความที่แน่นอนของ linearizability ค่อนข้างละเอียดอ่อน และเราจะสำรวจมันในส่วนที่เหลือของหัวข้อนี้ แนวคิดพื้นฐานคือการทำให้ระบบดูราวกับว่ามีข้อมูลเพียงชุดเดียว และการดำเนินการทั้งหมดบนข้อมูลนั้นเป็นอะตอมมิก (atomic) ด้วยการรับประกันนี้ ถึงแม้ว่าในความเป็นจริงอาจมี replica หลายตัว แอปพลิเคชันก็ไม่จำเป็นต้องกังวลเกี่ยวกับพวกมัน

ในระบบที่เป็น linearizable ทันทีที่ client หนึ่งทำการ write สำเร็จ client ทั้งหมดที่อ่านจากฐานข้อมูลจะต้องสามารถเห็นค่าที่เพิ่งเขียนได้ การรักษาภาพลวงตาของข้อมูลชุดเดียวหมายถึงการรับประกันว่าค่าที่อ่านได้นั้นเป็นค่าล่าสุดที่ทันสมัย และไม่ได้มาจาก cache หรือ replica ที่เก่า กล่าวอีกนัยหนึ่ง linearizability คือ การรับประกันความใหม่ (recency guarantee) เพื่อให้แนวคิดนี้ชัดเจนขึ้น มาดูตัวอย่างของระบบที่ไม่เป็น linearizable กัน

Figure 10-1 แสดงเว็บไซต์กีฬาที่ไม่เป็น linearizable [ 4 ] Aaliyah และ Bryce นั่งอยู่ในห้องเดียวกัน ต่างก็ตรวจสอบโทรศัพท์เพื่อดูผลการแข่งขันของทีมโปรดของพวกเขา ทันทีที่ผลคะแนนสุดท้ายประกาศ Aaliyah รีเฟรชหน้าเว็บ เห็นผู้ชนะ และบอก Bryce อย่างตื่นเต้น Bryce กดรีโหลดบนโทรศัพท์ของเขาด้วยความไม่อยากเชื่อ แต่คำขอของเขาไปยัง replica ของฐานข้อมูลที่กำลังล่าช้า ดังนั้นโทรศัพท์ของเขายังคงแสดงว่าเกมกำลังดำเนินอยู่

Diagram illustrating a nonlinearizable system where different clients see inconsistent sports match results, causing confusion.

Figure 10-1. ระบบนี้ไม่เป็น linearizable ทำให้แฟนกีฬาสับสน

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

What Makes a System Linearizable? (อะไรที่ทำให้ระบบเป็น Linearizable)

เพื่อทำความเข้าใจ linearizability ให้ดีขึ้น มาดูตัวอย่างเพิ่มเติมกัน Figure 10-2 แสดง client สามตัวที่อ่านและเขียนวัตถุเดียวกัน x ในฐานข้อมูลแบบ linearizable พร้อมกัน ในทฤษฎีระบบกระจาย x ถูกเรียกว่า register —ในทางปฏิบัติ มันอาจเป็น key หนึ่งใน key-value store, หนึ่งแถวในฐานข้อมูลเชิงสัมพันธ์, หรือหนึ่งเอกสารใน document database เป็นต้น

Diagram showing Client C writing to a register, while Clients A and B alternate in reading the register. Reads that overlap in time with the write may or may not return the written value, but reads that begin after the write is complete return the new value.

Figure 10-2. ถ้าคำขออ่านเกิดขึ้นพร้อมกับคำขอเขียน มันอาจคืนค่าทั้งเก่าหรือใหม่ก็ได้

เพื่อความง่าย Figure 10-2 แสดงเฉพาะคำขอจากมุมมองของ client ไม่ใช่ภายในของฐานข้อมูล แต่ละแท่งคือคำขอที่ทำโดย client จุดเริ่มต้นของแท่งคือเวลาที่ส่งคำขอ และจุดสิ้นสุดของแท่งคือเวลาที่ client ได้รับการตอบกลับ เนื่องจากความหน่วงของเครือข่ายที่แปรปรวน client ไม่รู้แน่ชัดว่าฐานข้อมูลประมวลผลคำขอเมื่อไหร่ มันรู้เพียงว่ามันต้องเกิดขึ้นในช่วงเวลาระหว่างที่ client ส่งคำขอและได้รับการตอบกลับ

ในตัวอย่างนี้ register มีการดำเนินการสองประเภท:

  • Read ( x ) ⇒  v หมายถึง client ขออ่านค่าของ register x และฐานข้อมูลคืนค่า v

  • Write ( x ,  v ) ⇒  r หมายถึง client ขอตั้งค่า register x เป็นค่า v และฐานข้อมูลคืนค่าการตอบกลับ r (ซึ่งอาจเป็น OK หรือ Error)

ใน Figure 10-2 ค่าของ x เริ่มต้นเป็น 0 และ client C ทำการ write เพื่อตั้งค่าเป็น 1 ในขณะที่กำลังเกิดเหตุการณ์นี้ client A และ B กำลัง polling ฐานข้อมูลซ้ำๆ เพื่ออ่านค่าล่าสุด คำตอบที่เป็นไปได้ที่ A และ B อาจได้รับสำหรับคำขออ่านของพวกเขาคืออะไร?

มาแยกวิเคราะห์กัน:

  • การอ่านครั้งแรกโดย client A เสร็จสมบูรณ์ก่อนที่ write จะเริ่ม ดังนั้นมันต้องคืนค่าเก่า คือ 0

  • การอ่านครั้งสุดท้ายโดย client A เริ่มหลังจาก write เสร็จสมบูรณ์ ดังนั้นถ้าฐานข้อมูลเป็น linearizable มันต้องคืนค่าใหม่ คือ 1 เพราะการอ่านต้องถูกประมวลผลหลังจาก write

  • การอ่านใดๆ ที่ทับซ้อนกับ write อาจคืนค่า 0 หรือ 1 ก็ได้ เพราะเราไม่รู้ว่า write มีผลแล้วหรือยังในเวลาที่ดำเนินการอ่าน การดำเนินการเหล่านี้ เกิดขึ้นพร้อมกัน (concurrent) กับ write

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

เพื่อทำให้ระบบเป็น linearizable เราจำเป็นต้องเพิ่มข้อจำกัดอีกข้อ ดังแสดงใน Figure 10-3

Same as the previous diagram, but with an additional restriction: once Client A has read the new value, the subsequent read by Client B must also return that value.

Figure 10-3. หลังจากที่การอ่านใดๆ คืนค่าใหม่แล้ว การอ่านที่ตามมาทั้งหมด (บน client เดียวกันหรืออื่นๆ) ก็ต้องคืนค่าใหม่ด้วยเช่นกัน

ในระบบที่เป็น linearizable เราจินตนาการว่าต้องมีจุดในเวลา (ระหว่างจุดเริ่มต้นและจุดสิ้นสุดของ write operation) ที่ค่าของ x เปลี่ยนจาก 0 เป็น 1 อย่างอะตอมมิก ดังนั้น ถ้า client หนึ่งอ่านค่าใหม่ 1 ได้ การอ่านที่ตามมาทั้งหมดก็ต้องคืนค่าใหม่เช่นกัน แม้ว่า write operation จะยังไม่เสร็จสมบูรณ์ก็ตาม

การขึ้นต่อกันของเวลานี้แสดงด้วยลูกศรใน Figure 10-3 Client A เป็นคนแรกที่อ่านค่าใหม่คือ 1 ทันทีหลังจากที่ A's read คืนค่า B ก็เริ่มอ่านใหม่ เนื่องจากการอ่านของ B เกิดขึ้นหลังจากของ A อย่างเคร่งครัด มันก็ต้องคืนค่า 1 เช่นกัน แม้ว่า write โดย C จะยังดำเนินอยู่ (มันเป็นสถานการณ์เดียวกับ Aaliyah และ Bryce ใน Figure 10-1 : หลังจาก Aaliyah อ่านค่าใหม่แล้ว Bryce ก็คาดหวังว่าจะอ่านค่าใหม่เช่นกัน)

เราสามารถปรับแต่ง timing diagram นี้เพิ่มเติมเพื่อเห็นภาพแต่ละ operation ที่มีผลแบบอะตอมมิก ณ จุดใดจุดหนึ่งในเวลา [ 5 ] ดังในตัวอย่างที่ซับซ้อนกว่าที่แสดงใน Figure 10-4 ในตัวอย่างนี้ เราเพิ่ม operation ประเภทที่สามนอกเหนือจาก read และ write :

CAS ( x ,  v old ,  v new ) ⇒  r หมายถึง client ขอ operation CAS แบบอะตอมมิก (ดู "Conditional writes (compare-and-set)" ) ถ้าค่าปัจจุบันของ register x เท่ากับ v old มันจะถูกตั้งค่าเป็น v new แบบอะตอมมิก ถ้าค่าของ x แตกต่างจาก v old operation จะปล่อย register ไว้เหมือนเดิมและคืนค่า error r คือการตอบกลับของฐานข้อมูล (OK หรือ Error)

แต่ละ operation ใน Figure 10-4 ถูกทำเครื่องหมายด้วยเส้นแนวตั้ง (ภายในแท่งของแต่ละ operation) ณ เวลาที่เราคิดว่า operation ถูกดำเนินการ เครื่องหมายเหล่านั้นเชื่อมต่อกันตามลำดับ และผลลัพธ์ต้องเป็นลำดับการอ่านและเขียนที่ถูกต้องสำหรับ register (ทุกการอ่านต้องคืนค่าที่ถูกตั้งโดย write ล่าสุด)

ข้อกำหนดของ linearizability คือเส้นที่เชื่อมเครื่องหมาย operation ต้องเคลื่อนที่ไปข้างหน้าในเวลาเท่านั้น (จากซ้ายไปขวา) ไม่สามารถถอยหลังได้ ข้อกำหนดนี้รับประกันความใหม่ (recency guarantee) ที่เรากล่าวถึงก่อนหน้านี้: เมื่อค่าใหม่ได้ถูกเขียนหรืออ่านแล้ว การอ่านที่ตามมาทั้งหมดจะเห็นค่าที่ถูกเขียน จนกว่ามันจะถูกเขียนทับอีกครั้ง

Diagram illustrating client operations over time to show linearizability, with a highlighted point where read by Client B is not linearizable.

Figure 10-4. การแสดงจุดในเวลาที่การอ่านและเขียนมีผล — การอ่านครั้งสุดท้ายของ B ไม่เป็น linearizable

มีรายละเอียดที่น่าสนใจบางอย่างที่ควรชี้ให้เห็นใน Figure 10-4 :

  • อันดับแรก client B ส่งคำขออ่าน x จากนั้น client D ส่งคำขอตั้งค่า x เป็น 0 แล้ว client A ก็ส่งคำขอตั้งค่า x เป็น 1 อย่างไรก็ตาม ค่าที่คืนให้ B's read คือ 1 (ค่าที่เขียนโดย A) ซึ่งถือว่าใช้ได้: มันหมายความว่าฐานข้อมูลประมวลผล write ของ D ก่อน จากนั้น write ของ A และสุดท้าย read ของ B ถึงแม้ว่านี่ไม่ใช่ลำดับที่ส่งคำขอ แต่มันเป็นลำดับที่ยอมรับได้ เพราะคำขอทั้งสามเกิดพร้อมกัน (concurrent) บางทีคำขอ read ของ B อาจล่าช้าเล็กน้อยในเครือข่าย จึงไปถึงฐานข้อมูลหลังจาก write ทั้งสองครั้ง

  • Client B's read คืนค่า 1 ก่อนที่ client A จะได้รับการตอบกลับจากฐานข้อมูลว่า write ค่า 1 สำเร็จแล้ว ซึ่งก็ถือว่าใช้ได้เช่นกัน เพราะมันแค่หมายความว่าการตอบกลับ OK จากฐานข้อมูลไปยัง client A ล่าช้าเล็กน้อยในเครือข่าย

  • โมเดลนี้ไม่ได้สันนิษฐานถึง transaction isolation ใดๆ client อื่นอาจเปลี่ยนค่าได้ตลอดเวลา ตัวอย่างเช่น C อ่าน 1 ก่อนแล้วจึงอ่าน 2 เพราะค่าถูกเปลี่ยนโดย B ระหว่างการอ่านทั้งสองครั้ง operation CAS แบบอะตอมมิกสามารถใช้เพื่อตรวจสอบว่าค่าไม่ได้ถูกเปลี่ยนโดย client อื่นพร้อมกัน: คำขอ CAS ของ B และ C สำเร็จ แต่คำขอ CAS ของ D ล้มเหลว (เมื่อถึงเวลาที่ฐานข้อมูลประมวลผล ค่าของ x ไม่ใช่ 0 อีกต่อไป)

  • การอ่านครั้งสุดท้ายโดย client B (ในแท่งสีเทา) ไม่เป็น linearizable operation เกิดพร้อมกับ CAS write ของ C ซึ่งอัปเดต x จาก 2 เป็น 4 หากไม่มีคำขออื่น การอ่านของ B ที่คืนค่า 2 ก็ถือว่าใช้ได้ อย่างไรก็ตาม client A ได้อ่านค่าใหม่ (4) ก่อนที่ read ของ B จะเริ่ม ดังนั้น B จึงไม่ได้รับอนุญาตให้อ่านค่าที่เก่ากว่า A ซึ่งเป็นสถานการณ์เดียวกับ Aaliyah และ Bryce ใน Figure 10-1

นั่นคือสัญชาตญาณเบื้องหลัง linearizability; คำจำกัดความทางการ [ 1 ] อธิบายไว้อย่างแม่นยำยิ่งขึ้น สามารถทดสอบได้ (แม้จะมีต้นทุนการคำนวณสูง) ว่าระบบมีพฤติกรรมเป็น linearizable หรือไม่ โดยการบันทึกเวลาของคำขอและการตอบกลับทั้งหมด และตรวจสอบว่าสามารถจัดเรียงเป็นลำดับที่ถูกต้องได้หรือไม่ [ 6 , 7 ]

เช่นเดียวกับที่มีระดับ isolation สำหรับ transaction ที่อ่อนแอกว่า serializability (ดู "Weak Isolation Levels" ) ก็มีโมเดลความสอดคล้องที่อ่อนแอกว่าสำหรับระบบจำลองข้อมูลนอกเหนือจาก linearizability [ 8 ] การรับประกันของ read-after-write consistency, monotonic reads, และ consistent prefix reads ที่เราเห็นใน "Problems with Replication Lag" เป็นตัวอย่างของสิ่งเหล่านี้ Linearizability รวมการรับประกันทั้งหมดนี้และมากกว่า; มันเป็นโมเดลความสอดคล้องที่แข็งแกร่งที่สุดในการใช้งานทั่วไป

Linearizability Versus Serializability (Linearizability เทียบกับ Serializability)

Linearizability มักสับสนกับ serializability (ดู "Serializability" ) เนื่องจากทั้งสองคำดูเหมือนจะหมายถึง "สามารถจัดเรียงตามลำดับได้" อย่างไรก็ตาม พวกมันเป็นการรับประกันที่แตกต่างกันมาก และสิ่งสำคัญคือต้องแยกแยะระหว่างพวกมัน:

Serializability

Serializability เป็นระดับ isolation ของ transactions ซึ่งทุก transaction อาจอ่านและเขียน หลายวัตถุ (rows, documents, records) มันรับประกันว่า transactions มีพฤติกรรมเหมือนกับว่าพวกมันถูกดำเนินการใน บาง ลำดับแบบ serial — นั่นคือ เหมือนกับว่าคุณดำเนินการทั้งหมดของ transaction หนึ่งก่อน จากนั้นทั้งหมดของอีก transaction หนึ่ง และต่อๆ ไป โดยไม่สลับกัน การที่ลำดับ serial นั้นแตกต่างจากลำดับที่ transactions ถูกเรียกใช้งานจริงก็ถือว่าใช้ได้ [ 9 ]

Linearizability

Linearizability คือการรับประกันเกี่ยวกับการอ่านและเขียนของ register (an วัตถุเดี่ยว ) มันไม่ได้จัดกลุ่ม operations เข้าด้วยกันเป็น transactions ดังนั้นมันจึงไม่ได้ป้องกันปัญหาเช่น write skew ที่เกี่ยวข้องกับหลายวัตถุ (ดู "Write Skew and Phantoms" ) อย่างไรก็ตาม linearizability คือการรับประกัน ความใหม่ (recency) : มันกำหนดว่าถ้า operation หนึ่งเสร็จก่อนที่อีก operation หนึ่งจะเริ่ม operation ที่หลังต้องสังเกตสถานะที่ใหม่อย่างน้อยเท่ากับ operation ก่อนหน้า Serializability ไม่มีข้อกำหนดนั้น — ตัวอย่างเช่น stale reads อนุญาตให้เกิดขึ้นได้ใน serializability [ 10 ]

Sequential consistency เป็นอีกสิ่งหนึ่ง [ 8 ] แต่เราจะไม่พูดถึงมันในที่นี้

ฐานข้อมูลอาจให้ทั้ง serializability และ linearizability; การรวมกันนี้เรียกว่า strict serializability หรือ strong one-copy serializability ( strong-1SR ) [ 11 , 12 ] ฐานข้อมูลโหนดเดียวมักจะเป็น linearizable สำหรับฐานข้อมูลแบบกระจายที่ใช้วิธีการ optimistic อย่าง SSI (ดู "Serializable Snapshot Isolation" ) สถานการณ์จะซับซ้อนกว่า ตัวอย่างเช่น CockroachDB ให้ serializability และการรับประกันความใหม่บางอย่างในการอ่าน แต่ไม่ใช่ strict serializability [ 13 ] เพราะสิ่งนี้ต้องใช้การประสานงานที่มีราคาแพงระหว่าง transactions [ 14 ] ในทางกลับกัน Spanner และ FoundationDB มี strict serializability [ 15 , 16 ]

นอกจากนี้ยังสามารถรวมระดับ isolation ที่อ่อนแอกว่ากับ linearizability หรือโมเดลความสอดคล้องที่อ่อนแอกว่ากับ serializability; ในความเป็นจริง โมเดลความสอดคล้องและระดับ isolation สามารถเลือกได้อย่างอิสระจากกัน [ 17 , 18 ]

Relying on Linearizability (การพึ่งพา Linearizability)

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

Locking and leader election (การล็อกและการเลือกผู้นำ)

ระบบที่ใช้ single-leader replication ต้องมั่นใจว่ามี leader เพียงตัวเดียว ไม่ใช่หลายตัว (split brain) วิธีหนึ่งในการเลือก leader คือการใช้ lease ทุก node ที่เริ่มต้นจะพยายามขอ lease และ node ที่สำเร็จจะกลายเป็น leader [ 19 ] ไม่ว่ากลไกนี้จะถูกนำไปใช้อย่างไร มันต้องเป็น linearizable ไม่ควรเป็นไปได้ที่สอง node จะได้ lease พร้อมกัน

บริการประสานงานอย่าง Apache ZooKeeper [ 20 ] และ etcd มักใช้ในการ implement distributed leases และ leader election พวกมันใช้ consensus algorithms เพื่อ implement การดำเนินการแบบ linearizable ในลักษณะที่ทนต่อความผิดพลาด (เราจะพูดถึงอัลกอริทึมเหล่านี้ภายหลังในบทนี้) มีรายละเอียดปลีกย่อยมากมายที่เกี่ยวข้องในการ implement leases และ leader election อย่างถูกต้อง (เช่น ปัญหา fencing ใน "Distributed Locks and Leases" ) และไลบรารีอย่าง Apache Curator ช่วยโดยให้ higher-level recipes บน ZooKeeper อย่างไรก็ตาม บริการจัดเก็บข้อมูลแบบ linearizable เป็นพื้นฐานสำหรับงานประสานงานเหล่านี้

Note

ตามที่เคร่งครัดแล้ว ZooKeeper ให้การเขียนแบบ linearizable แต่การอ่านอาจเก่า เนื่องจากไม่มีการรับประกันว่ามันจะถูกให้บริการจาก leader ปัจจุบัน [ 20 ] etcd ตั้งแต่เวอร์ชัน 3 ให้การอ่านแบบ linearizable เป็นค่าเริ่มต้น

การล็อกแบบกระจายยังใช้ในระดับที่ละเอียดกว่ามากในฐานข้อมูลแบบกระจายบางตัว เช่น Oracle Real Application Clusters (RAC) [ 21 ] RAC ใช้ lock ต่อ disk page โดยมีหลาย node แชร์การเข้าถึงระบบจัดเก็บข้อมูลดิสก์เดียวกัน เนื่องจาก locks แบบ linearizable เหล่านี้อยู่ใน critical path ของการดำเนินการ transaction การปรับใช้ RAC มักจะมีเครือข่ายเชื่อมต่อคลัสเตอร์โดยเฉพาะสำหรับการสื่อสารระหว่าง node ฐานข้อมูล

Constraints and uniqueness guarantees (ข้อจำกัดและการรับประกันความเป็นเอกลักษณ์)

ข้อจำกัดด้านความเป็นเอกลักษณ์ (uniqueness constraints) เป็นเรื่องธรรมดาในฐานข้อมูล — ตัวอย่างเช่น ชื่อผู้ใช้หรือที่อยู่อีเมลต้องระบุตัวตนผู้ใช้ได้ไม่ซ้ำกัน และในบริการจัดเก็บไฟล์จะไม่สามารถมีสองไฟล์ที่มีพาธและชื่อไฟล์เดียวกันได้ ถ้าคุณต้องการบังคับใช้ข้อจำกัดนี้ในขณะที่เขียนข้อมูล (เช่น ถ้าสองคนพยายามสร้างผู้ใช้หรือไฟล์ที่มีชื่อเดียวกันพร้อมกัน หนึ่งในนั้นจะได้รับ error) คุณจำเป็นต้องมี linearizability

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

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

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

อย่างไรก็ตาม ข้อจำกัดความเป็นเอกลักษณ์แบบแข็ง (hard uniqueness constraint) เช่นที่คุณมักพบในฐานข้อมูลเชิงสัมพันธ์ ต้องใช้ linearizability ข้อจำกัดประเภทอื่นๆ เช่น foreign-key หรือ attribute constraints สามารถนำไปใช้ได้โดยไม่ต้องมี linearizability [ 22 ]

Cross-channel timing dependencies (การขึ้นต่อกันของเวลาข้ามช่องทาง)

มีรายละเอียดสำคัญที่ควรสังเกตใน Figure 10-1 : ถ้า Aaliyah ไม่ได้อุทานคะแนน Bryce ก็คงไม่รู้ว่าผลการค้นหาของเขาเก่า เขาแค่คงรีเฟรชหน้าอีกครั้งหลังจากนั้นไม่กี่วินาทีและในที่สุดก็เห็นคะแนนสุดท้าย การละเมิด linearizability สังเกตได้เพียงเพราะมีช่องทางการสื่อสารเพิ่มเติมในระบบ (เสียงของ Aaliyah ไปยังหูของ Bryce)

สถานการณ์ที่คล้ายกันสามารถเกิดขึ้นได้ในระบบคอมพิวเตอร์ ตัวอย่างเช่น สมมติว่าเว็บไซต์ของคุณอนุญาตให้ผู้ใช้อัปโหลดวิดีโอ และกระบวนการเบื้องหลังทำการ transcoding วิดีโอให้มีคุณภาพต่ำลงที่สามารถสตรีมบนการเชื่อมต่ออินเทอร์เน็ตที่ช้าได้ สถาปัตยกรรมและการไหลของข้อมูลของระบบนี้แสดงใน Figure 10-5 ตัว transcoder วิดีโอต้องได้รับคำสั่งอย่างชัดเจนให้ทำงาน transcoding และคำสั่งนี้ถูกส่งจากเว็บเซิร์ฟเวอร์ไปยัง transcoder ผ่าน message queue (ดู Chapter 12 ) เว็บเซิร์ฟเวอร์ไม่ได้วางวิดีโอทั้งหมดใน queue เนื่องจาก message brokers ส่วนใหญ่ออกแบบมาสำหรับข้อความขนาดเล็กและวิดีโออาจมีขนาดหลายเมกะไบต์ แต่จะเขียนวิดีโอไปยังบริการจัดเก็บไฟล์ก่อน และเมื่อการเขียนเสร็จสมบูรณ์ คำสั่งไปยัง transcoder จะถูกวางใน queue

Diagram illustrating the communication process between the web server and video transcoder using file storage and a message queue, highlighting potential race conditions in video processing.

Figure 10-5. เว็บเซิร์ฟเวอร์และตัว transcoder วิดีโอสื่อสารผ่านทั้งที่จัดเก็บไฟล์และ message queue ทำให้เกิดโอกาสเกิด race conditions

ถ้าบริการจัดเก็บไฟล์เป็น linearizable ระบบนี้ควรทำงานได้ดี ถ้ามันไม่เป็น linearizable ก็มีความเสี่ยงของ race condition: message queue (ขั้นตอน 3 และ 4 ใน Figure 10-5 ) อาจเร็วกว่า replication ภายในของระบบจัดเก็บข้อมูล ในกรณีนี้ เมื่อ transcoder ดึงวิดีโอต้นฉบับ (ขั้นตอน 5) มันอาจเห็นเวอร์ชันเก่าของไฟล์หรือไม่เห็นอะไรเลย ถ้ามันประมวลผลวิดีโอเวอร์ชันเก่า วิดีโอต้นฉบับและ transcoded ในที่จัดเก็บไฟล์จะไม่สอดคล้องกันอย่างถาวร

ปัญหานี้เกิดขึ้นเพราะมีสองช่องทางการสื่อสารระหว่างเว็บเซิร์ฟเวอร์และ transcoder: ที่จัดเก็บไฟล์และ message queue หากปราศจากการรับประกันความใหม่ของ linearizability race condition ระหว่างสองช่องทางนี้เป็นไปได้ สถานการณ์นี้คล้ายคลึงกับใน Figure 10-1 ที่ก็มี race condition ระหว่างสองช่องทางการสื่อสาร: การจำลองฐานข้อมูลและช่องเสียงจริงระหว่างปากของ Aaliyah และหูของ Bryce

race condition ที่คล้ายกันเกิดขึ้นถ้าคุณมีแอปมือถือที่สามารถรับ push notifications และแอปดึงข้อมูลบางอย่างจากเซิร์ฟเวอร์เมื่อได้รับ notification ถ้าการดึงข้อมูลอาจไปที่ replica ที่ล่าช้า อาจเกิดขึ้นได้ว่า push notification ไปถึงเร็ว แต่การดึงข้อมูลที่ตามมาไม่เห็นข้อมูลที่ notification เกี่ยวข้อง

Linearizability ไม่ใช่วิธีเดียวในการหลีกเลี่ยง race condition นี้ แต่มันเป็นวิธีที่ง่ายที่สุดในการทำความเข้าใจ ถ้าคุณควบคุมช่องทางการสื่อสารเพิ่มเติมได้ (เช่นในกรณีของ message queue แต่ไม่ใช่ในกรณีของ Aaliyah และ Bryce) คุณสามารถใช้แนวทางอื่นคล้ายกับที่เรากล่าวถึงใน "Reading your own writes" โดยมีค่าใช้จ่ายเป็นความซับซ้อนที่เพิ่มขึ้น

Implementing Linearizable Systems (การ Implement ระบบ Linearizable)

ตอนนี้เราได้ดูตัวอย่างบางส่วนที่ linearizability มีประโยชน์แล้ว มาคิดดูว่าเราจะ implement ระบบที่มี semantics แบบ linearizable ได้อย่างไร

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

มาดูวิธีการจำลองข้อมูลจาก Chapter 6 อีกครั้งและดูว่าพวกมันสามารถทำให้เป็น linearizable ได้หรือไม่:

Single-leader replication (อาจเป็น linearizable)

ในระบบที่มี single-leader replication ผู้นำ (leader) มีสำเนาหลักของข้อมูลที่ใช้สำหรับการเขียน และ followers รักษาสำเนาสำรองของข้อมูลบน node อื่น ตราบใดที่คุณดำเนินการอ่านและเขียนทั้งหมดบน leader ก็มีแนวโน้มว่าจะเป็น linearizable อย่างไรก็ตาม สิ่งนี้สมมติว่าคุณรู้แน่ชัดว่าใครคือ leader ดังที่กล่าวถึงใน "Distributed Locks and Leases" มันค่อนข้างเป็นไปได้ที่ node คิดว่าตัวเองเป็น leader ทั้งที่จริงแล้วไม่ใช่ — และถ้า leader ที่หลงผิดยังคงให้บริการคำขอต่อไป ก็มีแนวโน้มที่จะละเมิด linearizability [ 23 ] ด้วย asynchronous replication การ failover อาจทำให้ write ที่ commit แล้วสูญหาย ซึ่งละเมิดทั้ง durability และ linearizability

การ sharding ฐานข้อมูลแบบ single-leader โดยมี leader แยกต่อ shard ไม่ส่งผลต่อ linearizability เนื่องจากมันเป็นการรับประกันระดับวัตถุเดียวเท่านั้น Cross-shard transactions เป็นอีกเรื่องหนึ่ง (ดู "Distributed Transactions" )

Consensus algorithms (มีแนวโน้มเป็น linearizable)

อัลกอริทึม consensus บางตัวโดยเนื้อแท้คือ single-leader replication ที่มีการเลือก leader และ failover อัตโนมัติ พวกมันถูกออกแบบมาอย่างระมัดระวังเพื่อป้องกัน split brain ทำให้สามารถ implement การจัดเก็บข้อมูลแบบ linearizable ได้อย่างปลอดภัย ตัวอย่างเช่น ZooKeeper ใช้ Zab consensus algorithm [ 24 ] และ etcd ใช้ Raft [ 25 ] อย่างไรก็ตาม เพียงเพราะระบบใช้ consensus ไม่ได้รับประกันว่าทุกการดำเนินการบนมันจะเป็น linearizable ถ้ามันอนุญาตให้อ่านบน node โดยไม่ตรวจสอบว่ามันยังเป็น leader อยู่ ผลลัพธ์ของการอ่านอาจเก่าถ้ามี leader ใหม่เพิ่งถูกเลือก

Multi-leader replication (ไม่เป็น linearizable)

ระบบที่มี multi-leader replication โดยทั่วไปไม่เป็น linearizable เพราะพวกมันประมวลผล writes พร้อมกันบนหลาย node และจำลองข้อมูลไปยัง node อื่นแบบอะซิงโครนัส ด้วยเหตุนี้ พวกมันจึงสร้าง write ที่ขัดแย้งกันซึ่งจำเป็นต้องแก้ไข (ดู "Dealing with Conflicting Writes" )

Leaderless replication (อาจไม่เป็น linearizable)

สำหรับระบบที่มี leaderless replication (Dynamo-style; ดู "Leaderless Replication" ) บางครั้งคนอ้างว่าคุณสามารถได้รับ "strong consistency" โดยกำหนดให้ quorum reads และ writes ( w  +  r > n ) ขึ้นอยู่กับอัลกอริทึมที่แน่นอนและวิธีที่คุณนิยาม strong consistency นี่ไม่เป็นความจริงทั้งหมด

วิธีการแก้ไขความขัดแย้งแบบ LWW ที่ใช้ clock แบบ time-of-day (เช่นใน Cassandra และ ScyllaDB) แทบจะไม่เป็น linearizable อย่างแน่นอน เนื่องจาก timestamps ของ clock ไม่สามารถรับประกันได้ว่าสอดคล้องกับลำดับเหตุการณ์จริงเนื่องจากการคลาดเคลื่อนของนาฬิกา (clock skew) (ดู "Relying on Synchronized Clocks" ) แม้จะใช้ quorum พฤติกรรมที่ไม่เป็น linearizable ก็เป็นไปได้ ดังที่แสดงในหัวข้อถัดไป

โดยสัญชาตญาณ ดูเหมือนว่า quorum reads และ writes ควรเป็น linearizable ในโมเดล Dynamo-style อย่างไรก็ตาม เมื่อเรามีความหน่วงของเครือข่ายที่แปรปรวน ก็เป็นไปได้ที่จะเกิด race conditions ดังที่แสดงใน Figure 10-6

ใน Figure 10-6 ค่าเริ่มต้นของ x คือ 0 และ writer client กำลังอัปเดต x เป็น 1 โดยส่ง write ไปยังทั้งสาม replicas ( n  = 3, w  = 3) ในเวลาเดียวกัน client A อ่านจาก quorum สอง node ( r  = 2) และเห็นค่าใหม่ 1 บน node หนึ่งและค่าเก่า 0 บนอีก node หนึ่ง ในเวลาเดียวกับ write client B อ่านจาก quorum ที่แตกต่างกันของสอง node และได้ค่าเก่า 0 จากทั้งสอง

เงื่อนไข quorum เป็นไปตาม ( w  +  r > n ) แต่การดำเนินการนี้ก็ยังไม่เป็น linearizable คำขอของ B เริ่มหลังจากคำขอของ A เสร็จสมบูรณ์ แต่ B คืนค่าเก่าในขณะที่ A คืนค่าใหม่ (มันเป็นสถานการณ์ Aaliyah และ Bryce อีกครั้งจาก Figure 10-1 )

มันเป็นไปได้ที่จะทำให้ Dynamo-style quorums เป็น linearizable โดยแลกกับประสิทธิภาพที่ลดลง ผู้อ่านต้องทำ read repair แบบซิงโครนัส (ดู "Catching up on missed writes" ) ก่อนที่จะคืนผลลัพธ์ให้แอปพลิเคชัน [ 26 ] นอกจากนี้ ก่อนที่จะเขียน ผู้เขียนต้องอ่านสถานะล่าสุดของ quorum node เพื่อดึง timestamp ล่าสุดของ write ก่อนหน้าใดๆ เพื่อให้แน่ใจว่า write ใหม่มี timestamp ที่มากกว่า [ 27 , 28 ] อย่างไรก็ตาม Riak ไม่ได้ทำ synchronous read repair เนื่องจากค่าเสียหายด้านประสิทธิภาพ Cassandra รอให้ read repair เสร็จสมบูรณ์สำหรับ quorum reads [ 29 ] แต่มันสูญเสีย linearizability เนื่องจากการใช้ clock แบบ time-of-day สำหรับ timestamps

Diagram illustrating a nonlinearizable execution in a leaderless replication system, showing how different clients read inconsistent values from replicas despite using quorums.

Figure 10-6. การดำเนินการที่ไม่เป็น linearizable แม้จะใช้ quorum

ยิ่งไปกว่านั้น มีเพียงการดำเนินการ read และ write แบบ linearizable เท่านั้นที่สามารถ implement ได้ด้วยวิธีนี้; operation CAS แบบ linearizable ไม่สามารถทำได้เพราะต้องใช้ consensus algorithm [ 30 ] โดยสรุป มันปลอดภัยที่สุดที่จะสมมติว่าระบบ leaderless ที่มี Dynamo-style replication ไม่ได้ให้ linearizability แม้จะใช้ quorum reads และ writes

The Cost of Linearizability (ต้นทุนของ Linearizability)

เนื่องจากบางวิธีการจำลองข้อมูลสามารถให้ linearizability ได้และบางวิธีก็ไม่สามารถ ให้สำรวจข้อดีข้อเสียของ linearizability ในเชิงลึกมากขึ้น

เราได้พูดถึงกรณีการใช้งานบางอย่างสำหรับวิธีการจำลองข้อมูลที่แตกต่างกันใน Chapter 6 แล้ว; ตัวอย่างเช่น เราเห็นว่า multi-leader replication มักเป็นตัวเลือกที่ดีสำหรับการจำลองข้อมูลหลายภูมิภาค (ดู "Geographically Distributed Operation" ) ตัวอย่างของการปรับใช้ดังกล่าวแสดงใน Figure 10-7

ลองพิจารณาว่าเกิดอะไรขึ้นถ้าการเชื่อมต่อเครือข่ายระหว่างสองภูมิภาคถูกขัดจังหวะ สมมติว่าเครือข่ายภายในแต่ละภูมิภาคทำงานได้ดี และ client สามารถเข้าถึงภูมิภาคท้องถิ่นของพวกเขาได้ แต่ภูมิภาคไม่สามารถเชื่อมต่อถึงกันได้ สิ่งนี้เรียกว่า network partition

Diagram illustrating a network partition between two regions, showing how clients connect to local applications and databases amidst connectivity interruption.

Figure 10-7. การขัดจังหวะเครือข่ายที่บังคับให้เลือกระหว่าง linearizability และ ความพร้อมใช้งาน (availability)

ด้วยฐานข้อมูล multi-leader แต่ละภูมิภาคสามารถทำงานได้ตามปกติ เนื่องจากการเขียนจากภูมิภาคหนึ่งถูกจำลองแบบอะซิงโครนัสไปยังอีกภูมิภาคหนึ่ง writes จะถูกจัดคิวและแลกเปลี่ยนเมื่อการเชื่อมต่อเครือข่ายกลับคืนมา

ในทางกลับกัน ถ้าใช้ single-leader replication leader ต้องอยู่ในภูมิภาคใดภูมิภาคหนึ่ง writes ทั้งหมดและการอ่านแบบ linearizable ทั้งหมดต้องถูกส่งไปยัง leader ดังนั้น สำหรับ client ใดๆ ที่เชื่อมต่อกับภูมิภาค follower คำขออ่านและเขียนเหล่านั้นต้องถูกส่งแบบซิงโครนัสผ่านเครือข่ายไปยังภูมิภาค leader

ถ้าเครือข่ายระหว่างภูมิภาคถูกขัดจังหวะในการตั้งค่า single-leader client ที่เชื่อมต่อกับภูมิภาค follower ไม่สามารถติดต่อ leader ได้ ดังนั้นพวกเขาไม่สามารถทำ writes ใดๆ กับฐานข้อมูลหรือการอ่านแบบ linearizable ใดๆ พวกเขายังสามารถอ่านจาก follower ได้ แต่มันอาจเก่า (ไม่เป็น linearizable) ถ้าแอปพลิเคชันต้องการการอ่านและเขียนแบบ linearizable การขัดจังหวะเครือข่ายทำให้แอปพลิเคชันไม่สามารถใช้งานได้ในภูมิภาคที่ไม่สามารถติดต่อ leader ได้

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

The CAP theorem (ทฤษฎีบท CAP)

ปัญหานี้ไม่ใช่แค่ผลลัพธ์ของ single-leader และ multi-leader replication เท่านั้น ฐานข้อมูลเชิงเส้นตรงใดๆ ก็มีปัญหานี้ ไม่ว่าจะถูก implement อย่างไร ปัญหานี้ยังไม่จำกัดเฉพาะการปรับใช้หลายภูมิภาค แต่สามารถเกิดขึ้นบนเครือข่ายที่ไม่น่าเชื่อถือใดๆ แม้แต่ในภูมิภาคเดียว การแลกเปลี่ยนมีดังนี้:

  • ถ้าแอปพลิเคชันของคุณ ต้องการ linearizability และ replica บางตัวถูกตัดการเชื่อมต่อจาก replica อื่นเนื่องจากปัญหาเครือข่าย replica เหล่านั้นจะไม่สามารถประมวลผลคำขอได้ชั่วคราว: พวกมันต้องรอจนกว่าปัญหาเครือข่ายจะได้รับการแก้ไข หรือคืนค่า error (ไม่ว่ากรณีไหน พวกมันจะ ไม่พร้อมใช้งาน (unavailable) ) ตัวเลือกนี้บางครั้งเรียกว่า CP ( consistent under network partitions )

  • ถ้าแอปพลิเคชันของคุณ ไม่ต้องการ linearizability มันสามารถถูกเขียนในลักษณะที่แต่ละ replica สามารถประมวลผลคำขอได้อย่างอิสระ แม้ว่ามันจะถูกตัดการเชื่อมต่อจาก replica อื่น (เช่น multi-leader) ในกรณีนี้ แอปพลิเคชันสามารถคง ความพร้อมใช้งาน (available) ไว้เมื่อเผชิญกับปัญหาเครือข่าย แต่พฤติกรรมของมันจะไม่เป็น linearizable ตัวเลือกนี้เรียกว่า AP ( available under network partitions )

ดังนั้น แอปพลิเคชันที่ไม่ต้องการ linearizability สามารถทนต่อปัญหาเครือข่ายได้ดีกว่า ข้อมูลเชิงลึกนี้เป็นที่รู้จักในชื่อ CAP theorem [ 31 , 32 , 33 , 34 , 35 , 36 , 37 ] ตั้งชื่อโดย Eric Brewer ในปี 2000 แม้ว่าการแลกเปลี่ยนนี้เป็นที่รู้จักของนักออกแบบฐานข้อมูลแบบกระจายตั้งแต่ปี 1970s

CAP ถูกเสนอครั้งแรกเป็นกฎง่ายๆ โดยไม่มีคำจำกัดความที่แม่นยำ โดยมีเป้าหมายเพื่อเริ่มการอภิปรายเกี่ยวกับการแลกเปลี่ยนในฐานข้อมูล ในเวลานั้น ฐานข้อมูลแบบกระจายจำนวนมากมุ่งเน้นที่การให้ semantics แบบ linearizable บน cluster ของเครื่องที่มี shared storage [ 21 ] และ CAP สนับสนุนให้วิศวกรฐานข้อมูลสำรวจพื้นที่การออกแบบที่กว้างขึ้นของระบบ shared-nothing แบบกระจาย ซึ่งเหมาะสมกว่าสำหรับการ implement บริการเว็บขนาดใหญ่ [ 38 ] CAP สมควรได้รับเครดิตสำหรับการเปลี่ยนแปลงวัฒนธรรมนี้ — มันช่วยจุดประกายการเคลื่อนไหว NoSQL ซึ่งเป็นการระเบิดของเทคโนโลยีฐานข้อมูลใหม่ในช่วงกลางปี 2000s

ทฤษฎีบท CAP ตามที่นิยามอย่างเป็นทางการ [ 32 ] มีขอบเขตที่แคบมาก มันพิจารณาเพียงโมเดลความสอดคล้องเดียว (คือ linearizability) และความผิดพลาดชนิดเดียว (network partitions ซึ่งจากข้อมูลของ Google เป็นสาเหตุของ incidents น้อยกว่า 8% [ 39 ]) มันไม่ได้พูดอะไรเกี่ยวกับ network delays, dead nodes, หรือการแลกเปลี่ยนอื่นๆ ดังนั้น แม้ว่า CAP จะมีอิทธิพลในอดีต แต่มันมีคุณค่าในทางปฏิบัติเพียงเล็กน้อยสำหรับการออกแบบระบบ [ 4 , 45 ]

มีความพยายามที่จะทำให้ CAP เป็นทั่วไป ตัวอย่างเช่น หลักการ PACELC (PACELC principle) สังเกตว่านักออกแบบระบบอาจเลือกที่จะทำให้ความสอดคล้องอ่อนแอลงแม้ในเวลาที่เครือข่ายทำงานได้ดีเพื่อลด latency [ 40 , 46 , 47 ] ดังนั้น ระหว่าง network partition (P) เราต้องเลือกระหว่าง availability (A) และ consistency (C); else (E) เมื่อไม่มี partition เราอาจเลือกระหว่าง low latency (L) และ consistency (C) อย่างไรก็ตาม คำจำกัดความนี้สืบทอดปัญหาหลายอย่างของ CAP เช่น คำจำกัดความของ consistency และ availability ที่ขัดกับสัญชาตญาณ

มีผลลัพธ์ความเป็นไปไม่ได้อีกมากมายที่น่าสนใจในระบบกระจาย [ 41 ] และ CAP ได้ถูกแทนที่ด้วยผลลัพธ์ที่แม่นยำกว่า [ 42 , 43 ] ดังนั้นมันจึงมีความสนใจทางประวัติศาสตร์เป็นส่วนใหญ่ในปัจจุบัน

The Unhelpful CAP Theorem (ทฤษฎีบท CAP ที่ไร้ประโยชน์)

CAP บางครั้งถูกนำเสนอเป็น consistency, availability, partition tolerance: เลือกสองในสาม น่าเสียดายที่การนำเสนอแบบนี้ทำให้เข้าใจผิด [ 34 ] เนื่องจาก network partitions เป็นความผิดพลาดชนิดหนึ่ง มันไม่ใช่สิ่งที่คุณเลือก แต่เป็นสิ่งที่เกิดขึ้นไม่ว่าคุณจะชอบหรือไม่ วิธีเดียวที่คุณจะรับประกันว่าไม่มี network partitions คือการไม่มีเครือข่าย — นั่นคือการมี replica เดียว — แต่แล้วคุณก็ไม่มีความพร้อมใช้งานสูงเช่นกัน

ในเวลาที่เครือข่ายทำงานได้ถูกต้อง ระบบสามารถให้ทั้งความสอดคล้อง (linearizability) และความพร้อมใช้งาน เมื่อความผิดพลาดของเครือข่ายเกิดขึ้น คุณต้องเลือกระหว่างพวกมัน ดังนั้น วิธีที่ดีกว่าในการกล่าวถึง CAP คือ ไม่ว่าจะสอดคล้องหรือพร้อมใช้งานเมื่อเกิด partition [ 44 ] เครือข่ายที่เชื่อถือได้มากกว่าต้องการให้ตัวเลือกนี้เกิดขึ้นน้อยลง แต่ในบางจุดตัวเลือกนั้นหลีกเลี่ยงไม่ได้

รูปแบบการจัดหมวดหมู่ CP/AP มีข้อบกพร่องอื่นๆ อีกหลายประการ [ 4 ] Consistency ถูกทำให้เป็นทางการเป็น linearizability (ทฤษฎีบทไม่ได้พูดอะไรเกี่ยวกับโมเดลความสอดคล้องที่อ่อนแอกว่า) และการทำให้ availability เป็นทางการ [ 32 ] ไม่ตรงกับความหมายปกติของคำนี้ [ 45 ] ระบบที่พร้อมใช้งานสูง (ทนต่อความผิดพลาด) จำนวนมากจริงๆ แล้วไม่ตรงตามคำจำกัดความเฉพาะของ CAP สำหรับ availability ยิ่งไปกว่านั้น นักออกแบบระบบบางคนเลือก (ด้วยเหตุผลที่ดี) ที่จะไม่ให้ทั้ง linearizability และรูปแบบ availability ที่ทฤษฎีบท CAP สันนิษฐาน ดังนั้นระบบเหล่านั้นจึงไม่ใช่ทั้ง CP และ AP [ 46 , 47 ]

โดยสรุป มีความเข้าใจผิดและความสับสนมากมายเกี่ยวกับ CAP และมันไม่ได้ช่วยให้เราเข้าใจระบบได้ดีขึ้น ดังนั้นจึงควรที่จะไม่ยึดติดกับมันมากเกินไป

Linearizability and network delays (Linearizability และความหน่วงของเครือข่าย)

แม้ว่า linearizability จะเป็นการรับประกันที่มีประโยชน์ แต่น่าแปลกที่มีระบบน้อยมากที่ใช้ linearizable ในทางปฏิบัติ ตัวอย่างเช่น แม้แต่ RAM ใน CPU แบบ multi-core สมัยใหม่ก็ไม่เป็น linearizable [ 48 ] ถ้า thread ที่รันบน CPU core หนึ่งเขียนไปยังที่อยู่หน่วยความจำ และ thread บน CPU core อีกตัวอ่านที่อยู่เดียวกันหลังจากนั้นไม่นาน ไม่มีการรับประกันว่ามันจะอ่านค่าที่เขียนโดย thread แรก (เว้นแต่จะใช้ memory barrier หรือ fence [ 49 ])

สาเหตุของพฤติกรรมนี้คือทุก CPU core มี memory cache และ store buffer ของตัวเอง โดยค่าเริ่มต้นการอ่านจะถูกให้บริการจาก cache และการเปลี่ยนแปลงใดๆ จะถูกเขียนไปยัง main memory แบบอะซิงโครนัส เนื่องจากการเข้าถึงข้อมูลใน cache เร็วกว่าการไปยัง main memory มาก [ 50 ] คุณสมบัตินี้จึงจำเป็นสำหรับประสิทธิภาพที่ดีบน CPU สมัยใหม่ อย่างไรก็ตาม มันหมายความว่าตอนนี้มีข้อมูลหลายชุด (หนึ่งชุดใน main memory และอีกหลายชุดใน caches ต่างๆ) และชุดข้อมูลเหล่านี้ถูกอัปเดตแบบอะซิงโครนัส ดังนั้น linearizability จึงสูญหายไป

ทำไมต้องแลกเปลี่ยนแบบนี้? มันไม่สมเหตุสมผลที่จะใช้ CAP theorem เพื่อ justify โมเดลความสอดคล้องของหน่วยความจำแบบ multi-core ภายในคอมพิวเตอร์เครื่องเดียว เรามักจะสมมติว่าการสื่อสารเชื่อถือได้ และเราไม่คาดหวังว่า CPU core หนึ่งจะยังคงทำงานได้ตามปกติถ้ามันถูกตัดการเชื่อมต่อจากส่วนอื่นของคอมพิวเตอร์ เหตุผลในการละทิ้ง linearizability คือ ประสิทธิภาพ (performance) ไม่ใช่ fault tolerance [ 46 ]

เช่นเดียวกันกับฐานข้อมูลแบบกระจายหลายตัวที่เลือกที่จะไม่ให้การรับประกันแบบ linearizable: พวกมันทำเช่นนั้นเพื่อเพิ่มประสิทธิภาพเป็นหลัก ไม่ใช่เพื่อ fault tolerance [ 40 ] ระบบ linearizable มีแนวโน้มที่จะมี latency สูงกว่า — และนี่เป็นจริงตลอดเวลา ไม่ใช่แค่ระหว่าง network fault

เราไม่สามารถหาการ implement ที่มีประสิทธิภาพมากขึ้นสำหรับการจัดเก็บข้อมูลแบบ linearizable ได้หรือ? ดูเหมือนว่าคำตอบคือไม่ Attiya และ Welch [ 51 ] พิสูจน์ว่าถ้าคุณต้องการ linearizability เวลาตอบสนองของ read และ write requests ต้องเป็นสัดส่วนอย่างน้อยกับความไม่แน่นอนของความหน่วงในเครือข่าย ในเครือข่ายที่มีความหน่วงแปรปรวนสูง เช่นเครือข่ายคอมพิวเตอร์ส่วนใหญ่ (ดู "Timeouts and Unbounded Delays" ) เวลาตอบสนองของการอ่านและเขียนแบบ linearizable จะสูงอย่างหลีกเลี่ยงไม่ได้ ไม่มีอัลกอริทึมที่เร็วกว่าสำหรับ linearizability แต่โมเดลความสอดคล้องที่อ่อนแอกว่าสามารถเร็วกว่ามาก ดังนั้นการแลกเปลี่ยนนี้จึงสำคัญสำหรับระบบที่ไวต่อ latency ใน Chapter 13 เราจะพูดถึงแนวทางบางอย่างในการหลีกเลี่ยง linearizability โดยไม่เสียความถูกต้อง

ID Generators and Logical Clocks (ตัวสร้าง ID และนาฬิกาเชิงตรรกะ)

ในหลายแอปพลิเคชัน คุณต้องกำหนด ID ที่ไม่ซ้ำกันให้กับระเบียนฐานข้อมูลเมื่อพวกมันถูกสร้างขึ้น ซึ่งให้คีย์หลักสำหรับการอ้างอิงระเบียนเหล่านั้น ในฐานข้อมูลโหนดเดียวมักใช้เลขจำนวนเต็มที่เพิ่มขึ้นอัตโนมัติ (autoincrementing integer) ซึ่งมีข้อดีคือสามารถจัดเก็บใน 64 บิตเท่านั้น (หรือแม้แต่ 32 บิต ถ้าคุณแน่ใจว่าจะไม่มีระเบียนเกิน 4 พันล้านรายการ แต่นั่นก็เสี่ยง)

ข้อดีอีกอย่างของ autoincrementing IDs คือลำดับของ ID บอกลำดับที่ระเบียนถูกสร้างขึ้น ตัวอย่างเช่น Figure 10-8 แสดงแอปพลิเคชันแชทที่กำหนด autoincrementing IDs ให้กับข้อความแชทเมื่อพวกมันถูกโพสต์ คุณสามารถแสดงข้อความตามลำดับ ID ที่เพิ่มขึ้น และเธรดแชทที่ได้จะสมเหตุสมผล: Aaliyah โพสต์คำถามที่ได้ ID 1 และคำตอบของ Bryce สำหรับคำถามนั้นได้ ID ที่มากกว่า — คือ 3

ตัวสร้าง ID แบบโหนดเดียวนี้อีกตัวอย่างของระบบ linearizable แต่ละคำขอเพื่อรับ ID คือ operation ที่อะตอมมิก increments ตัวนับและคืนค่าเก่าของตัวนับ ( fetch-and-add operation); linearizability รับประกันว่าถ้าการโพสต์ข้อความของ Aaliyah เสร็จก่อนที่การโพสต์ของ Bryce จะเริ่ม ID ของข้อความของ Bryce จะต้องมากกว่าของ Aaliyah ข้อความโดย Aaliyah และ Caleb ใน Figure 10-8 เกิดขึ้นพร้อมกัน ดังนั้น linearizability ไม่ได้ระบุว่า ID ของพวกเขาต้องเรียงลำดับอย่างไร ตราบใดที่พวกมันไม่ซ้ำกัน

Diagram of a chat application showing auto-incrementing ID assignment to messages by Aaliyah, Bryce, and Caleb, illustrating message order and concurrency.

Figure 10-8. ตัวสร้าง ID ที่กำหนด autoincrementing integer IDs ให้กับข้อความในแอปพลิเคชันแชท

ตัวสร้าง ID แบบ in-memory โหนดเดียวนั้น implement ง่าย คุณสามารถใช้ atomic increment instruction ที่ CPU ของคุณให้มา ซึ่งช่วยให้หลาย thread สามารถ increment ตัวนับเดียวกันได้อย่างปลอดภัย การทำให้ตัวนับคงอยู่ (persistent) นั้นต้องใช้ความพยายามมากกว่าเล็กน้อย เพื่อให้ node สามารถ crash และ restart ได้โดยไม่รีเซ็ตค่าตัวนับ ซึ่งจะส่งผลให้เกิด ID ซ้ำกัน แต่ปัญหาที่แท้จริงมีดังนี้:

  • ตัวสร้าง ID แบบโหนดเดียวไม่ทนต่อความผิดพลาดเนื่องจาก node นั้นเป็น single point of failure

  • มันช้าถ้าคุณต้องการสร้างระเบียนในอีกภูมิภาคหนึ่ง เนื่องจากคุณอาจต้องเดินทางไปกลับครึ่งโลกเพื่อรับ ID

  • node เดียวนั้นอาจกลายเป็นคอขวดถ้าคุณมีปริมาณการเขียนสูง

คุณสามารถพิจารณาตัวเลือกอื่นๆ ต่างๆ สำหรับตัวสร้าง ID:

Sharded ID assignment (การกำหนด ID แบบกระจาย)

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

Preallocated blocks of IDs (บล็อก ID ที่จัดสรรล่วงหน้า)

แทนที่จะเป็น IDs ทีละตัว ตัวสร้าง ID แบบโหนดเดียวสามารถแจกจ่ายบล็อกของ IDs ตัวอย่างเช่น node A อาจอ้างสิทธิ์บล็อกของ IDs ตั้งแต่ 1 ถึง 1,000 และ node B อาจอ้างสิทธิ์บล็อกตั้งแต่ 1,001 ถึง 2,000 จากนั้นแต่ละ node สามารถแจกจ่าย IDs จากบล็อกของมันได้อย่างอิสระ และขอบล็อกใหม่จากตัวสร้าง ID เมื่อหมายเลขลำดับของมันเริ่มหมด อย่างไรก็ตาม รูปแบบนี้ไม่รับประกันลำดับที่ถูกต้องเช่นกัน มันอาจเกิดขึ้นที่ข้อความหนึ่งได้รับ ID ในช่วง 1,001 ถึง 2,000 และข้อความที่หลังได้รับ ID ในช่วง 1 ถึง 1,000 ถ้า ID ถูกกำหนดโดย node ที่แตกต่างกัน

Random UUIDs (UUID แบบสุ่ม)

คุณสามารถใช้ universally unique identifiers (UUIDs) หรือที่รู้จักในชื่อ globally unique identifiers (GUIDs) สิ่งเหล่านี้มีข้อได้เปรียบที่สำคัญคือสามารถสร้างได้ในเครื่องบน node ใดๆ โดยไม่ต้องมีการสื่อสาร แต่มันต้องการพื้นที่มากกว่า (128 บิต) UUIDs มีหลายเวอร์ชัน; เวอร์ชันที่ง่ายที่สุดคือเวอร์ชัน 4 ซึ่งโดยพื้นฐานแล้วเป็นตัวเลขสุ่มที่ยาวมากจนไม่น่าเป็นไปได้ที่สอง node จะสุ่มได้ค่าเดียวกัน น่าเสียดายที่ลำดับของ IDs ดังกล่าวก็สุ่มเช่นกัน ดังนั้นการเปรียบเทียบสอง IDs ไม่ได้บอกอะไรคุณว่า ID ไหนใหม่กว่า

Wall-clock timestamp made unique (timestamp จากนาฬิกาผนังที่ทำให้ไม่ซ้ำกัน)

ถ้า time-of-day clocks ของ node ของคุณถูกทำให้ประมาณถูกต้องโดยใช้ NTP คุณสามารถสร้าง IDs โดยใส่ timestamp จาก clock นี้ในบิตที่มีนัยสำคัญที่สุด และเติมบิตที่เหลือด้วยข้อมูลเพิ่มเติมที่ทำให้ ID ไม่ซ้ำกันแม้ว่า timestamp จะไม่เป็นเช่นนั้น — ตัวอย่างเช่น หมายเลข shard และ per-shard incrementing sequence number หรือค่าสุ่มยาว วิธีนี้ใช้ใน UUIDs เวอร์ชัน 7 [ 52 ], Snowflake ของ X [ 53 ], ULIDs [ 54 ], Flake ID generator ของ Hazelcast, MongoDB ObjectIDs, และรูปแบบที่คล้ายกันอีกมากมาย [ 52 ] คุณสามารถ implement ตัวสร้าง ID เหล่านี้ในโค้ดแอปพลิเคชันหรือภายในฐานข้อมูล [ 55 ]

รูปแบบทั้งหมดนี้สร้าง IDs ที่ไม่ซ้ำกัน (อย่างน้อยก็มีความน่าจะเป็นสูงพอที่การชนกันจะหายากมาก) แต่พวกมันมีการรับประกันการเรียงลำดับที่อ่อนแอกว่ารูปแบบ autoincrementing แบบโหนดเดี่ยวมาก

ดังที่กล่าวถึงใน "Timestamps for ordering events" wall-clock timestamps สามารถให้การเรียงลำดับโดยประมาณเท่านั้น ถ้า write ก่อนหน้าได้ timestamp จากนาฬิกาที่เร็วไปเล็กน้อย และ write หลังจากได้ timestamp จากนาฬิกาที่ช้าไปเล็กน้อย ลำดับ timestamp อาจไม่สอดคล้องกับลำดับที่เหตุการณ์เกิดขึ้นจริง ด้วยการกระโดดของนาฬิกาเนื่องจากการใช้นาฬิกาที่ไม่เป็น monotonic แม้แต่ timestamps ที่สร้างโดย node เดียวก็อาจถูกเรียงลำดับผิดพลาดได้ ดังนั้นตัวสร้าง ID ที่ใช้ wall-clock time จึงไม่น่าจะเป็น linearizable

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

Logical Clocks (นาฬิกาเชิงตรรกะ)

ใน "Unreliable Clocks" เราได้พูดถึง time-of-day clocks และ monotonic clocks ทั้งสองเป็น physical clocks : อุปกรณ์ฮาร์ดแวร์ที่วัดเวลาที่ผ่านไป (วินาที, มิลลิวินาที, ไมโครวินาที ฯลฯ)

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

ข้อกำหนดทั่วไปสำหรับ logical clock มีดังนี้:

  • timestamps มีขนาดกะทัดรัด (ไม่กี่ไบต์) และไม่ซ้ำกัน

  • คุณสามารถเปรียบเทียบสอง timestamps เพื่อระบุว่าอันไหนเกิดก่อน (นั่นคือพวกมัน เรียงลำดับได้ทั้งหมด (totally ordered) )

  • ลำดับของ timestamps สอดคล้องกับความเป็นเหตุเป็นผล (consistent with causality) นั่นคือ ถ้า operation A เกิดขึ้นก่อน operation B timestamp ของ A จะน้อยกว่า timestamp ของ B (เราได้พูดถึงความเป็นเหตุเป็นผลก่อนหน้านี้ใน "The happens-before relation and concurrency" )

ตัวสร้าง ID แบบโหนดเดียวตอบสนองข้อกำหนดเหล่านี้ แต่ตัวสร้าง ID แบบกระจายที่เราเพิ่งพูดถึงไม่ตอบสนองข้อกำหนดการเรียงลำดับตามเหตุเป็นผล (causal ordering)

Lamport timestamps (timestamps ของ Lamport)

โชคดีที่มีวิธีง่ายๆ ในการสร้าง logical timestamps ที่ สอดคล้องกับความเป็นเหตุเป็นผล และคุณสามารถใช้มันเป็นตัวสร้าง ID แบบกระจายได้ มันเรียกว่า Lamport clock เสนอในปี 1978 โดย Leslie Lamport [ 56 ] ซึ่งเป็นหนึ่งในบทความที่ถูกอ้างถึงมากที่สุดในสาขาระบบกระจาย

แม้ว่า Lamport clocks จะให้การเรียงลำดับทั้งหมด (total ordering) แต่พวกมัน ไม่ได้ ให้ linearizability — นั่นคือพวกมันไม่ใช่วิธีการรับประกันว่าค่านั้นทันสมัย พวกมันเป็นเพียงวิธีการกำหนด IDs ให้กับ events เพื่อที่ว่าถ้า event A เกิดขึ้นก่อน event B ID ของ A จะน้อยกว่า ID ของ B

Figure 10-9 แสดงวิธีการทำงานของ Lamport clock ในตัวอย่างแชทจาก Figure 10-8 แต่ละ node มี identifier ที่ไม่ซ้ำกัน ซึ่งใน Figure 10-9 คือชื่อ Aaliyah, Bryce, หรือ Caleb แต่ในทางปฏิบัติอาจเป็น UUID แบบสุ่มหรือสิ่งที่คล้ายกัน แต่ละ node ยังเก็บจำนวน operation ที่มันประมวลผล Lamport timestamp ก็คือคู่ของ ( counter , node ID ) สอง node อาจมีค่า counter เดียวกันในบางครั้ง แต่โดยการรวม node ID ใน timestamp แต่ละ timestamp จะถูกทำให้ไม่ซ้ำกัน

Diagram illustrating how Lamport timestamps work in a chat scenario, showing message exchanges between nodes labeled "Aaliyah," "Bryce," and "Caleb" with unique identifiers and counters.

Figure 10-9. Lamport timestamps ให้การเรียงลำดับทั้งหมดที่สอดคล้องกับความเป็นเหตุเป็นผล

ทุกครั้งที่ node สร้าง timestamp มันจะเพิ่มค่า counter ของมันและใช้ค่าใหม่ ทุกครั้งที่ node เห็น timestamp จาก node อื่น ถ้าค่า counter ใน timestamp นั้นมากกว่าค่า counter ท้องถิ่นของมัน มันจะเพิ่ม counter ท้องถิ่นให้เท่ากับค่าที่มากกว่า

ใน Figure 10-9 Aaliyah ยังไม่เห็นข้อความของ Caleb เมื่อเธอโพสต์ข้อความของเธอ และในทางกลับกัน สมมติว่าผู้ใช้ทั้งสองเริ่มด้วยค่า counter เริ่มต้นที่ 0 ทั้งคู่จึงเพิ่ม counter ท้องถิ่นของตนและแนบค่า counter ใหม่คือ 1 ไปกับข้อความของพวกเขา เมื่อ Bryce ได้รับข้อความเหล่านั้น เขาเพิ่มค่า counter ท้องถิ่นของเขาเป็น 1 สุดท้าย Bryce ส่งคำตอบไปยังข้อความของ Aaliyah โดยเพิ่ม counter ท้องถิ่นและแนบค่าใหม่ 2 ไปกับข้อความ

ในการเปรียบเทียบสอง Lamport timestamps อันดับแรกเราเปรียบเทียบค่า counter — ตัวอย่างเช่น (2, "Bryce") มากกว่า (1, "Aaliyah") และมากกว่า (1, "Caleb") ด้วย ถ้า two timestamps มีค่า counter เท่ากัน เราจะเปรียบเทียบ node IDs โดยใช้การเปรียบเทียบสตริงแบบ lexicographic ทั่วไป ดังนั้น ลำดับ timestamp ในตัวอย่างนี้คือ (1, "Aaliyah") < (1, "Caleb") < (2, "Bryce")

Hybrid logical clocks (นาฬิกาเชิงตรรกะแบบลูกผสม)

Lamport timestamps ดีในการจับลำดับของสิ่งที่เกิดขึ้น แต่มันมีข้อจำกัดบางประการ:

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

  • ถ้าสอง node ไม่เคยสื่อสารกัน การเพิ่ม counter ของ node หนึ่งจะไม่มีทางสะท้อนใน counter ของอีก node หนึ่ง ดังนั้น events ที่เกิดขึ้นใกล้ๆ กันบน node ที่แตกต่างกันอาจมีค่า counter ที่แตกต่างกันอย่างมาก

Hybrid logical clock รวมข้อดีของ time-of-day clocks ทางกายภาพกับการรับประกันการเรียงลำดับของ Lamport clocks [ 57 ] เช่นเดียวกับ physical clock มันนับวินาทีหรือไมโครวินาที เช่นเดียวกับ Lamport clock เมื่อ node หนึ่งเห็น timestamp จากอีก node ที่มากกว่าค่า clock ท้องถิ่นของมัน มันจะเลื่อนค่าท้องถิ่นของตัวเองไปข้างหน้าให้ตรงกับ timestamp ของอีก node ดังนั้น ถ้า clock ของ node หนึ่งเดินเร็ว node อื่นก็จะเลื่อน clock ของพวกเขาไปข้างหน้าเมื่อพวกเขาสื่อสารกัน

ทุกครั้งที่ timestamp จาก hybrid logical clock ถูกสร้างขึ้น มันก็จะถูก increment เช่นกัน ซึ่งมั่นใจได้ว่า clock จะเดินหน้าแบบ monotonic แม้ว่า physical clock พื้นฐานจะกระโดดถอยหลัง — ตัวอย่างเช่น เนื่องจากการปรับ NTP ดังนั้น hybrid logical clock อาจเร็วกว่า physical clock พื้นฐานเล็กน้อย รายละเอียดของอัลกอริทึมทำให้แน่ใจว่าความคลาดเคลื่อนนี้ยังคงน้อยที่สุดเท่าที่จะเป็นไปได้

ดังนั้น คุณสามารถปฏิบัติต่อ timestamp จาก hybrid logical clock เกือบเหมือน timestamp จาก time-of-day clock ทั่วไป โดยมีคุณสมบัติเพิ่มเติมที่ว่าการเรียงลำดับของมันสอดคล้องกับความสัมพันธ์ happens-before มันไม่ต้องพึ่งพาฮาร์ดแวร์พิเศษใดๆ และต้องการเพียงนาฬิกาที่ซิงโครไนซ์แบบคร่าวๆ Hybrid logical clocks ถูกใช้โดย CockroachDB เป็นต้น

Lamport/hybrid logical clocks versus vector clocks (Lamport/hybrid logical clocks เทียบกับ vector clocks)

ใน "Multiversion concurrency control" เราได้พูดถึงว่า snapshot isolation มักถูก implement อย่างไร: โดยพื้นฐานแล้ว โดยการให้ transaction ID แก่แต่ละ transaction และอนุญาตให้แต่ละ transaction เห็น writes ที่ทำโดย transactions ที่มี ID ต่ำกว่า แต่ทำให้ writes โดย transactions ที่มี ID สูงกว่ามองไม่เห็น Lamport clocks และ hybrid logical clocks เป็นวิธีที่ดีในการสร้าง transaction IDs เหล่านี้เพราะพวกมันรับประกันว่า snapshot สอดคล้องกับความเป็นเหตุเป็นผล [ 58 ]

เมื่อ timestamps หลายตัวถูกสร้างขึ้นพร้อมกัน อัลกอริทึมเหล่านี้จัดลำดับพวกมันตามอำเภอใจ นั่นหมายความว่าเมื่อคุณดู two timestamps โดยทั่วไปคุณไม่สามารถบอกได้ว่าพวกมันถูกสร้างขึ้นพร้อมกันหรืออันหนึ่งเกิดขึ้นก่อนอีกอัน (ใน Figure 10-9 คุณสามารถบอกได้ว่าข้อความของ Aaliyah และ Caleb ต้องเกิดขึ้นพร้อมกัน เพราะพวกมันมีค่า counter เท่ากัน; อย่างไรก็ตาม เมื่อค่า counter แตกต่างกัน คุณไม่สามารถบอกได้ว่าพวกมันเกิดขึ้นพร้อมกันหรือไม่)

ถ้าคุณต้องการที่จะสามารถระบุได้ว่าระเบียนถูกสร้างขึ้นเมื่อใดพร้อมกัน คุณต้องใช้อัลกอริทึมอื่น เช่น vector clock Vector clocks เก็บ counter สำหรับแต่ละ node และเก็บค่า counter ทั้งหมดกับแต่ละ write ถ้า write A มีค่า counter สูงกว่า B สำหรับ node หนึ่ง และ write B มีค่า counter สูงกว่า A สำหรับอีก node หนึ่ง ดังนั้น A และ B ต้องเกิดขึ้นพร้อมกัน (ดู "Detecting Concurrent Writes" ) ข้อเสียคือ timestamps จาก vector clock ใช้พื้นที่มากกว่า timestamps อื่นที่เราได้พูดถึง—อาจเป็นจำนวนเต็มหนึ่งจำนวนต่อทุก node ในระบบ

Linearizable ID Generators (ตัวสร้าง ID แบบ Linearizable)

แม้ว่า Lamport clocks และ hybrid logical clocks จะให้การรับประกันการเรียงลำดับที่มีประโยชน์ แต่การเรียงลำดับนั้นยังอ่อนแอกว่าตัวสร้าง ID แบบ linearizable แบบโหนดเดียวที่เราพูดถึงก่อนหน้านี้ จำไว้ว่า linearizability กำหนดว่าถ้าคำขอ A เสร็จก่อนที่คำขอ B จะเริ่ม B ต้องมี ID ที่สูงกว่า แม้ว่า A และ B จะไม่เคยสื่อสารกัน ในทางกลับกัน Lamport clocks สามารถรับประกันได้เพียงว่า node สร้าง timestamps ที่มากกว่า timestamp อื่นใดที่ node นั้นเคยเห็น; ไม่มีการรับประกันดังกล่าวเกี่ยวกับ timestamps ที่มันไม่เคยเห็น

Figure 10-10 แสดงให้เห็นว่าตัวสร้าง ID ที่ไม่เป็น linearizable อาจทำให้เกิดปัญหาได้อย่างไร ลองนึกภาพว่าในเว็บไซต์โซเชียลมีเดีย ผู้ใช้ A ต้องการแชร์รูปถ่ายที่น่าอายกับเพื่อนๆ ส่วนตัว บัญชีของผู้ใช้ A เริ่มต้นเป็นสาธารณะ แต่ใช้แล็ปท็อปของพวกเขา พวกเขาเปลี่ยนการตั้งค่าบัญชีเป็นส่วนตัว จากนั้นพวกเขาใช้โทรศัพท์เพื่ออัปโหลดรูปถ่าย เนื่องจากผู้ใช้ A ดำเนินการอัปเดตเหล่านี้ตามลำดับ พวกเขาอาจคาดหวังว่าการอัปโหลดรูปถ่ายจะอยู่ภายใต้สิทธิ์บัญชีใหม่ที่จำกัด อย่างไรก็ตาม ดังที่รูปแสดง มันไม่จำเป็นต้องเป็นเช่นนั้น

Diagram illustrating the sequence of events where User A sets their account to private on a laptop before sharing a photo on a phone, showing the potential issue of a non-linearizable ID generator leading to the photo being exposed publicly.

Figure 10-10. ผู้ใช้ A ตั้งค่าบัญชีเป็นส่วนตัวก่อน แล้วจึงแชร์รูปถ่าย ด้วยตัวสร้าง ID ที่ไม่เป็น linearizable ผู้ชมที่ไม่ได้รับอนุญาตอาจเห็นรูปถ่าย

สิทธิ์ของบัญชีและรูปถ่ายถูกจัดเก็บในฐานข้อมูลสองแห่งที่แยกกัน (หรือ shards ที่แตกต่างกันของฐานข้อมูลเดียวกัน) และสมมติว่าพวกมันใช้ Lamport clock หรือ hybrid logical clock เพื่อกำหนด timestamp ให้กับทุก write เนื่องจากฐานข้อมูลรูปถ่ายไม่ได้อ่านจากฐานข้อมูลบัญชี มันเป็นไปได้ที่ counter ท้องถิ่นในฐานข้อมูลรูปถ่ายจะล้าหลังเล็กน้อย ดังนั้นการอัปโหลดรูปถ่ายจึงได้รับ timestamp ที่ต่ำกว่าการอัปเดตการตั้งค่าบัญชี

ทีนี้ สมมติว่ามีผู้ชม (ซึ่งไม่ใช่เพื่อนของ A) กำลังดูโปรไฟล์ของ A และการอ่านของพวกเขาใช้ MVCC implementation ของ snapshot isolation มันอาจเกิดขึ้นที่การอ่านของผู้ชมมี timestamp ที่มากกว่าของการอัปโหลดรูปถ่าย แต่น้อยกว่าของการอัปเดตการตั้งค่าบัญชี ผลลัพธ์คือ ระบบจะระบุว่าบัญชียังเป็นสาธารณะ ณ เวลาที่อ่าน และดังนั้นจึงแสดงรูปถ่ายที่น่าอายที่ผู้ชมไม่ควรเห็นให้พวกเขาดู

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

Implementing a linearizable ID generator (การ Implement ตัวสร้าง ID แบบ Linearizable)

วิธีที่ง่ายที่สุดในการรับประกันว่าการกำหนด ID เป็น linearizable คือการใช้ node เดียวเพื่อจุดประสงค์นี้ node นั้นต้องทำเพียงสามสิ่ง: อะตอมมิก increment ตัวนับและคืนค่าเมื่อมีการร้องขอ, ทำให้ค่าตัวนับคงอยู่ (persistent) (เพื่อไม่ให้สร้าง ID ซ้ำถ้า node crash และ restart), และจำลองข้อมูลเพื่อทนต่อความผิดพลาด (โดยใช้ single-leader replication) วิธีนี้ใช้ในทางปฏิบัติ — ตัวอย่างเช่น TiDB/TiKV เรียกมันว่า timestamp oracle ได้รับแรงบันดาลใจจาก Percolator ของ Google [ 59 ]

เพื่อเพิ่มประสิทธิภาพ คุณสามารถหลีกเลี่ยงการเขียนดิสก์และ replication ทุกครั้งที่มีคำขอ แต่ตัวสร้าง ID สามารถเขียน record ที่อธิบาย batch ของ IDs; เมื่อ record นั้นถูกทำให้คงอยู่และจำลองข้อมูลแล้ว node ก็สามารถเริ่มแจกจ่าย IDs เหล่านั้นให้ client ตามลำดับ ก่อนที่มันจะหมด IDs ใน batch นั้น มันสามารถทำให้ persistent และจำลอง record สำหรับ batch ถัดไป ด้วยวิธีนี้ IDs บางตัวจะถูกข้ามถ้า node crash และ restart หรือถ้าคุณ fail over ไปยัง follower แต่คุณจะไม่ออก ID ซ้ำหรือ ID ที่ไม่เรียงลำดับ

คุณไม่สามารถ shard ตัวสร้าง ID ได้ง่ายๆ เพราะถ้าคุณมีหลาย shards ที่แจกจ่าย IDs อย่างอิสระ คุณจะไม่สามารถรับประกันได้ว่าลำดับของพวกมันเป็น linearizable อีกต่อไป คุณยังไม่สามารถกระจายตัวสร้าง ID ข้ามหลายภูมิภาคได้ง่ายๆ ดังนั้นในฐานข้อมูลแบบกระจายตามภูมิศาสตร์ คำขอทั้งหมดสำหรับ IDs จะต้องไปที่ node ในภูมิภาคเดียว ข้อดีคืองานของตัวสร้าง ID นั้นง่ายมาก ดังนั้น node เดียวสามารถจัดการปริมาณคำขอที่มากได้

ถ้าคุณไม่ต้องการใช้ตัวสร้าง ID แบบโหนดเดียว คุณสามารถทำสิ่งที่ Spanner ของ Google ทำ ดังที่กล่าวถึงใน "Synchronized clocks for global snapshots" มันอาศัย physical clock ที่คืนค่าไม่ใช่แค่ timestamp เดียว แต่เป็นช่วงของ timestamps ที่ระบุความไม่แน่นอนในการอ่านค่า clock จากนั้น Spanner จะรอจนกว่าระยะเวลาความไม่แน่นอนนั้นจะผ่านไปก่อนที่จะคืนค่า

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

Enforcing constraints using logical clocks (การบังคับใช้ข้อจำกัดโดยใช้นาฬิกาเชิงตรรกะ)

ใน "Constraints and uniqueness guarantees" เราเห็นว่า operation CAS แบบ linearizable สามารถใช้เพื่อ implement locks, uniqueness constraints, และโครงสร้างที่คล้ายกันในระบบกระจาย สิ่งนี้ทำให้เกิดคำถาม: logical clock หรือตัวสร้าง ID แบบ linearizable เพียงพอที่จะ implement สิ่งเหล่านี้ด้วยหรือไม่?

คำตอบคือ: ไม่ทั้งหมด เมื่อคุณมีหลาย node ที่ทั้งหมดพยายามขอ lock เดียวกันหรือลงทะเบียนชื่อผู้ใช้เดียวกัน คุณสามารถใช้ logical clock เพื่อกำหนด timestamps ให้กับคำขอเหล่านั้นและเลือกอันที่มี timestamp ต่ำที่สุดเป็นผู้ชนะ ถ้า clock เป็น linearizable คุณรู้ว่าคำขอในอนาคตใดๆ จะสร้าง timestamps ที่มากกว่าเสมอ ดังนั้นคุณจึงมั่นใจได้ว่าไม่มีคำขอในอนาคตใดที่จะได้รับ timestamp ที่ต่ำกว่าผู้ชนะ

น่าเสียดายที่ส่วนหนึ่งของปัญหายังไม่ได้รับการแก้ไข: node รู้ได้อย่างไรว่า timestamp ของตัวเองต่ำที่สุด? เพื่อให้แน่ใจ มันต้องได้ยินจาก ทุก node อื่นที่อาจสร้าง timestamp [ 56 ] ถ้า node อื่นตัวใดตัวหนึ่งล้มเหลวในระหว่างนั้น หรือไม่สามารถเข้าถึงได้เนื่องจากปัญหาเครือข่าย ระบบนี้จะชะงักเพราะเราไม่สามารถแน่ใจได้ว่า timestamp ของ node นั้นไม่ได้ต่ำกว่า นี่ไม่ใช่ระบบที่ทนต่อความผิดพลาดแบบที่เราต้องการ

ในการ implement locks, leases, และโครงสร้างที่คล้ายกันในลักษณะที่ทนต่อความผิดพลาด เราต้องการบางสิ่งที่แข็งแกร่งกว่า logical clocks หรือตัวสร้าง ID เราต้องการ consensus

Consensus (ฉันทามติ)

ในบทนี้ เราได้เห็นตัวอย่างหลายอย่างของสิ่งที่ง่ายเมื่อคุณมีโหนดเดียว แต่ยากขึ้นมากถ้าคุณต้องการ fault tolerance:

  • ฐานข้อมูลสามารถเป็น linearizable ได้ถ้าคุณมี leader เพียงตัวเดียวและคุณดำเนินการอ่านและเขียนทั้งหมดบน leader นั้น แต่คุณจะ failover อย่างไรถ้า leader นั้นล้มเหลว ในขณะที่หลีกเลี่ยง split brain? คุณจะมั่นใจได้อย่างไรว่า node ที่เชื่อว่าตัวเองเป็น leader จริงๆ แล้วไม่ได้ถูกโหวตออกไปในขณะที่มันหยุดชั่วคราว?

  • ตัวสร้าง ID แบบ linearizable บน node เดียวก็แค่ counter ที่มี atomic fetch-and-add instruction — จะเกิดอะไรขึ้นถ้ามัน crash?

  • Operation CAS แบบอะตอมมิกมีประโยชน์สำหรับการตัดสินว่าใครได้ lock หรือ lease เมื่อหลาย process แข่งขันกันเพื่อขอสิทธิ์ ตัวอย่างเช่น หรือสำหรับการรับประกัน ความเป็นเอกลักษณ์ ของไฟล์หรือผู้ใช้ที่มีชื่อที่กำหนด บน node เดียว CAS อาจง่ายเท่ากับหนึ่ง CPU instruction แต่คุณจะทำให้มันทนต่อความผิดพลาดได้อย่างไร?

ปรากฎว่าทั้งหมดนี้เป็นตัวอย่างของปัญหาเดียวกันพื้นฐานในระบบกระจาย: consensus รูปแบบมาตรฐานของ consensus เกี่ยวข้องกับการให้หลาย node เห็นพ้องต้องกันบนค่าเดี่ยว มันเป็นหนึ่งในปัญหาที่สำคัญและพื้นฐานที่สุดในระบบกระจาย; และยังมีชื่อเสียงในด้านความยากที่จะทำให้ถูกต้อง [ 60 , 61 ] และหลายระบบก็เคยทำผิดพลาดมาก่อน ตอนนี้ที่เราได้พูดถึง replication ( Chapter 6 ), transactions ( Chapter 8 ), system models ( Chapter 9 ), และ linearizability (บทนี้) ในที่สุดเราก็พร้อมที่จะจัดการกับปัญหา consensus

อัลกอริทึม consensus ที่รู้จักกันดีที่สุดคือ Viewstamped Replication [ 62 , 63 ], Paxos [ 60 , 64 , 65 , 66 ], Raft [ 25 , 67 , 68 ], และ Zab [ 20 , 24 , 69 ] อัลกอริทึมเหล่านี้มีความคล้ายคลึงกันพอสมควร แต่ไม่เหมือนกัน [ 70 , 71 ] พวกมันทั้งหมดทำงานในโมเดลระบบที่ไม่ใช่ Byzantine — นั่นคือ การสื่อสารเครือข่ายอาจล่าช้าหรือหลุดโดยพลการ และ node อาจ crash, restart, และถูกตัดการเชื่อมต่อ แต่อัลกอริทึมสมมติว่า node ปฏิบัติตามโปรโตคอลอย่างถูกต้องและไม่ทำตัวเป็นอันตราย

นอกจากนี้ยังมี consensus algorithms ที่สามารถทนต่อ Byzantine nodes บางตัวได้ (เช่น node ที่ไม่ปฏิบัติตามโปรโตคอลอย่างถูกต้อง — ตัวอย่างเช่น โดยการส่งข้อความที่ขัดแย้งกันไปยัง node อื่น) ข้อสมมติทั่วไปคือน้อยกว่าหนึ่งในสามของ node เป็น Byzantine-faulty [ 28 , 72 ] อัลกอริทึมดังกล่าวใช้ใน blockchain เป็นต้น [ 73 ] อย่างไรก็ตาม ดังที่อธิบายใน "Byzantine Faults" อัลกอริทึมที่ทนต่อ Byzantine faults อยู่นอกขอบเขตของหนังสือเล่มนี้

The Impossibility of Consensus (ความเป็นไปไม่ได้ของฉันทามติ)

คุณอาจเคยได้ยินเกี่ยวกับ FLP result [ 74 ]—ตั้งชื่อตามผู้เขียน Fischer, Lynch, และ Paterson—ซึ่งพิสูจน์ว่าไม่มีอัลกอริทึมใดที่สามารถบรรลุฉันทามติได้เสมอถ้ามีความเสี่ยงที่ node อาจ crash ในระบบกระจาย เราต้องสมมติว่า node อาจ crash ได้ ดังนั้นฉันทามติที่เชื่อถือได้จึงเป็นไปไม่ได้ แต่เรากำลังพูดถึงอัลกอริทึมสำหรับการบรรลุฉันทามติตรงนี้ เกิดอะไรขึ้น?

ประการแรก FLP ไม่ได้บอกว่าเราไม่สามารถบรรลุฉันทามติได้เลย; มันบอกเพียงว่าเราไม่สามารถรับประกันได้ว่าอัลกอริทึมฉันทามติจะ สิ้นสุด (terminate) เสมอไป ยิ่งไปกว่านั้น ผลลัพธ์ของ FLP ได้รับการพิสูจน์ภายใต้สมมติฐานของ deterministic algorithm ในโมเดลระบบแบบ asynchronous (ดู "System Model and Reality" ) ซึ่งหมายความว่าอัลกอริทึมไม่สามารถใช้ clock หรือ timeouts ใดๆ ถ้ามันสามารถใช้ timeouts เพื่อสงสัยว่า node อื่นอาจ crash (แม้ว่าความสงสัยนั้นจะผิดเป็นบางครั้ง) ฉันทามติก็จะแก้ไขได้ [ 75 ] แม้แต่การอนุญาตให้อัลกอริทึมใช้ตัวเลขสุ่มก็เพียงพอ [ 76 ]

ดังนั้น แม้ว่าผลลัพธ์ของ FLP เกี่ยวกับความเป็นไปไม่ได้ของฉันทามติจะมีความสำคัญทางทฤษฎีอย่างมาก ระบบกระจายก็สามารถบรรลุฉันทามติได้ในทางปฏิบัติ

The Many Faces of Consensus (ใบหน้าหลากหลายของฉันทามติ)

Consensus สามารถแสดงออกได้หลายวิธี ตัวอย่างเช่น:

  • Single-value consensus คล้ายกับ operation CAS แบบอะตอมมิกมาก มันสามารถใช้เพื่อ implement locks, leases, และ uniqueness constraints

  • การสร้าง append-only log ก็ต้องใช้ฉันทามติ ซึ่งมักถูกทำให้เป็นทางการเป็น total order broadcast ด้วย log คุณสามารถ implement state machine replication, leader-based replication, event sourcing, และรูปแบบที่มีประโยชน์อื่นๆ

  • Operation fetch-and-add แบบอะตอมมิก (หรือ atomic increment) ก็กลายเป็นว่าเทียบเท่ากับฉันทามติ

  • Atomic commitment ของ transaction แบบ multidatabase หรือ multishard ต้องการให้ผู้เข้าร่วมทั้งหมดตกลงกันว่าจะ commit หรือ abort transaction

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

Single-value consensus (ฉันทามติค่าเดี่ยว)

ความสามารถในการให้หลาย node เห็นพ้องต้องกันบนค่าเดียวนั้นมีประโยชน์มาก ตัวอย่างเช่น:

  • เมื่อฐานข้อมูลที่มี single-leader replication เริ่มทำงานครั้งแรก หรือเมื่อ leader ปัจจุบันล้มเหลว หลาย node อาจพยายามเป็น leader พร้อมกัน ในทำนองเดียวกัน หลาย node อาจแข่งขันกันเพื่อขอ lock หรือ lease Consensus อนุญาตให้พวกมันตัดสินว่าใครชนะ

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

โดยทั่วไป หนึ่ง node หรือมากกว่าอาจ เสนอ (propose) ค่า และอัลกอริทึม consensus ตัดสินใจ (decide) หนึ่งในค่าเหล่านั้น ในตัวอย่างที่ให้ไว้ แต่ละ node สามารถเสนอ ID ของตัวเอง และอัลกอริทึมจะตัดสินใจว่า node ID ใดควรเป็น leader ใหม่, ผู้ถือ lease, หรือผู้ซื้อที่นั่งเครื่องบิน/โรงละคร ในรูปแบบนี้ อัลกอริทึม consensus ต้องมีคุณสมบัติดังต่อไปนี้ [ 28 ]:

Uniform agreement (ข้อตกลงร่วมกัน)

ไม่มีสอง node ใดตัดสินใจแตกต่างกัน

Integrity (ความถูกต้อง)

หลังจาก node ตัดสินใจค่าแล้ว มันไม่สามารถเปลี่ยนใจโดยตัดสินใจค่าอื่นได้

Validity (ความถูกต้องตามข้อกำหนด)

ถ้า node ตัดสินใจค่า v แสดงว่า v ถูกเสนอโดยบาง node

Termination (การสิ้นสุด)

ทุก node ที่ไม่ crash ในที่สุดจะตัดสินใจค่า

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

คุณสมบัติ uniform agreement และ integrity นิยามแนวคิดหลักของฉันทามติ: ทุกคนตัดสินใจผลลัพธ์เดียวกัน และหลังจากที่คุณตัดสินใจแล้ว คุณจะเปลี่ยนใจไม่ได้ คุณสมบัติ validity ตัดวิธีแก้ไขแบบ trivial — ตัวอย่างเช่น คุณสามารถมีอัลกอริทึมที่ตัดสินใจ null เสมอ ไม่ว่าจะเสนออะไรก็ตาม; อัลกอริทึมนี้จะตอบสนอง agreement และ integrity แต่ไม่ใช่ validity

ถ้าคุณไม่สนใจ fault tolerance การตอบสนองสามคุณสมบัติแรกนั้นง่าย คุณสามารถ hardcode หนึ่ง node ให้เป็น "dictator" และให้ node นั้นทำการตัดสินใจทั้งหมด อย่างไรก็ตาม ถ้า node นั้นล้มเหลว ระบบจะไม่สามารถตัดสินใจใดๆ ได้อีก — เหมือน single-leader replication ที่ไม่มี failover ความยากทั้งหมดเกิดจากความต้องการ fault tolerance

คุณสมบัติ termination ทำให้แนวคิดของ fault tolerance เป็นทางการ โดยพื้นฐานแล้วมันบอกว่าอัลกอริทึมฉันทามติไม่สามารถนั่งรอเฉยๆ ตลอดไป — กล่าวอีกนัยหนึ่ง มันต้องมีความคืบหน้า (make progress) แม้ว่าบาง node จะล้มเหลว node อื่นก็ยังคงต้องบรรลุการตัดสินใจ (Termination เป็น liveness property ในขณะที่สามอื่นๆ เป็น safety properties — ดู "Distinguishing between safety and liveness" )

ถ้า node ที่ crash อาจกู้คืนได้ คุณสามารถรอมันกลับมาได้ อย่างไรก็ตาม อัลกอริทึมฉันทามติต้องรับประกันว่ามันตัดสินใจแม้ว่า node ที่ crash จะหายไปกะทันหันและไม่กลับมา (แทนที่จะเป็น software crash ลองนึกภาพว่าแผ่นดินไหวทำให้ datacenter ที่มี node ของคุณถูกทำลายโดยดินถล่ม คุณต้องสมมติว่า node ของคุณถูกฝังอยู่ใต้โคลนหนา 30 ฟุตและจะไม่กลับมาออนไลน์อีก)

แน่นอน ถ้า ทุก node crash และไม่มีอันไหนทำงานอยู่ ก็เป็นไปไม่ได้ที่อัลกอริทึมใดๆ จะตัดสินใจอะไร มีข้อจำกัดเกี่ยวกับจำนวนความล้มเหลวที่อัลกอริทึมสามารถทนได้ ในความเป็นจริง มันพิสูจน์ได้ว่าอัลกอริทึมฉันทามติใดๆ ต้องการอย่างน้อย majority ของ node ที่ทำงานอย่างถูกต้องเพื่อรับประกัน termination [ 75 ] majority นั้นสามารถสร้าง quorum ได้อย่างปลอดภัย (ดู "Using quorums for reading and writing" )

ดังนั้น คุณสมบัติ termination อยู่ภายใต้ข้อสมมติว่าน้อยกว่าครึ่งหนึ่งของ node ไม่สามารถเข้าถึงได้ อย่างไรก็ตาม อัลกอริทึมฉันทามติส่วนใหญ่รับประกันว่าคุณสมบัติ safety — agreement, integrity, และ validity — เป็นไปตามเสมอ แม้ว่า majority ของ node จะล้มเหลวหรือปัญหาเครือข่ายรุนแรงเกิดขึ้น [ 77 ] ดังนั้น การหยุดทำงานขนาดใหญ่สามารถหยุดระบบไม่ให้สามารถประมวลผลคำขอได้ แต่มันไม่สามารถทำให้ระบบฉันทามติเสียหายโดยทำให้มันตัดสินใจที่ไม่สอดคล้องกัน

Compare-and-set as consensus (Compare-and-set ในฐานะฉันทามติ)

Operation CAS ตรวจสอบว่าค่าปัจจุบันของวัตถุเท่ากับค่าที่คาดหวังหรือไม่ ถ้าใช่ มันจะอัปเดตวัตถุเป็นค่าใหม่อย่างอะตอมมิก; ถ้าไม่ มันจะปล่อยวัตถุไว้เหมือนเดิมและคืนค่า error

ถ้าคุณมี operation CAS ที่ทนต่อความผิดพลาดและเป็น linearizable การแก้ปัญหาฉันทามตินั้นง่าย เริ่มต้นด้วยการตั้งค่าวัตถุเป็น null จากนั้นให้แต่ละ node ที่ต้องการเสนอค่าทำ CAS โดยมีค่าที่คาดหวังเป็น null และค่าใหม่เป็นค่าที่มันต้องการเสนอ (สมมติว่ามันไม่ใช่ null) ค่าที่ตัดสินใจแล้วก็คือค่าที่วัตถุถูกตั้งค่าไว้

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

สิ่งนี้แสดงให้เห็นว่า CAS และฉันทามติเทียบเท่ากัน [ 30 , 75 ] อีกครั้ง ทั้งสองอย่างตรงไปตรงมาบน node เดียวแต่ท้าทายที่จะทำให้ทนต่อความผิดพลาด ตัวอย่างของ CAS ในบริบทแบบกระจาย เราเห็น conditional write operations สำหรับ object stores ใน "Databases Backed by Object Storage" ซึ่งอนุญาตให้ write เกิดขึ้นได้ก็ต่อเมื่อ object ที่มีชื่อเดียวกันไม่ได้ถูกสร้างขึ้นหรือแก้ไขโดย client อื่นตั้งแต่ client ปัจจุบันอ่านมันครั้งสุดท้าย

Shared logs as consensus (log ร่วมในฐานะฉันทามติ)

เราได้เห็นตัวอย่างหลายอย่างของ logs เช่น replication logs, transaction logs, และ write-ahead logs log จัดเก็บลำดับของ log entries และใครก็ตามที่อ่านมันจะเห็น entries เดียวกันในลำดับเดียวกัน บางครั้ง log มี writer เดียวที่ได้รับอนุญาตให้ append entries ใหม่ แต่ shared log คือ log ที่หลาย node สามารถขอให้ append entries ได้ ตัวอย่างคือ single-leader replication: client ใดๆ สามารถขอให้ leader ทำการ write ซึ่ง leader จะ append ไปยัง replication log จากนั้น followers ทั้งหมดจะใช้ writes ในลำดับเดียวกันกับ leader

อย่างเป็นทางการมากขึ้น shared log รองรับสอง operations: คุณสามารถขอให้ค่าเพิ่มเข้าไปใน log และคุณสามารถอ่าน entries ใน log มันต้องมีคุณสมบัติดังต่อไปนี้:

Eventual append (การ append ในที่สุด)

ถ้า node ขอให้ค่าเพิ่มเข้าไปใน log และ node ไม่ crash node นั้นต้องอ่านค่านั้นใน log entry ในที่สุด

Reliable delivery (การส่งที่เชื่อถือได้)

ไม่มี log entries ใดสูญหาย—ถ้า node หนึ่งอ่าน log entry ในที่สุดทุก node ที่ไม่ crash ก็ต้องอ่าน log entry นั้นด้วย

Append-only (เพิ่มอย่างเดียว)

หลังจาก node อ่าน log entry แล้ว มันไม่สามารถเปลี่ยนแปลงได้ และสามารถเพิ่ม log entries ใหม่ได้หลังจากนั้นเท่านั้น ไม่ใช่ก่อนหน้านั้น ถ้า node อ่าน log อีกครั้ง มันจะเห็น log entries เดียวกันในลำดับเดียวกันกับที่อ่านครั้งแรก (แม้ว่า node จะ crash และ restart)

Agreement (ข้อตกลง)

ถ้าสอง node อ่าน log entry e ก่อน e พวกมันต้องอ่านลำดับ log entries ที่เหมือนกันในลำดับเดียวกัน

Validity (ความถูกต้อง)

ถ้า node อ่าน log entry ที่มีค่า แสดงว่า node เคยขอให้เพิ่มค่านั้นใน log

Note

shared log สามารถ implement ได้โดยใช้ total order broadcast protocol หรือที่รู้จักในชื่อ atomic broadcast หรือ total order multicast protocol [ 28 , 78 , 79 ] ในการเพิ่มค่าเข้าไปใน log เราจะ "broadcast" มันโดยใช้ protocol และเมื่อ protocol "delivers" มัน ค่านั้นจะกลายเป็นส่วนหนึ่งของ log entry ที่สามารถอ่านได้

ถ้าคุณมี implementation ของ shared log การแก้ปัญหาฉันทามตินั้นง่าย ทุก node ที่ต้องการเสนอค่าขอให้มันเพิ่มเข้าไปใน log และค่าใดก็ตามที่อ่านกลับมาใน log entry แรกคือค่าที่ตัดสินใจ เนื่องจากทุก node อ่าน log entries ในลำดับเดียวกัน พวกมันจึงรับประกันว่าจะตกลงกันว่าค่าใดถูกส่งก่อน [ 30 ]

ในทางกลับกัน ถ้าคุณมีวิธีแก้สำหรับฉันทามติ คุณสามารถ implement shared log รายละเอียดค่อนข้างซับซ้อนกว่า แต่แนวคิดพื้นฐานคือ [ 75 ]:

  1. คุณมีช่อง (slot) ใน log สำหรับทุก log entry ในอนาคต และคุณรันอินสแตนซ์แยกของอัลกอริทึมฉันทามติสำหรับทุกช่องดังกล่าวเพื่อตัดสินใจว่าควรใส่ค่าอะไรใน entry นั้น

  2. เมื่อ node ต้องการเพิ่มค่าเข้าไปใน log มันเสนอค่านั้นสำหรับหนึ่งในช่องที่ยังไม่ได้ตัดสินใจ

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

  4. ถ้าค่าที่เสนอไม่ถูกเลือกสำหรับช่อง node ที่ต้องการเพิ่มมันจะลองใหม่โดยเสนอสำหรับช่องที่หลังกว่า

สิ่งนี้แสดงให้เห็นว่า consensus เทียบเท่ากับ total order broadcast และ shared logs Single-leader replication ที่ไม่มี failover ไม่ตรงตามข้อกำหนด liveness เนื่องจากมันหยุดส่งข้อความถ้า leader crash เช่นเคย ความท้าทายคือการทำ failover อย่างปลอดภัยและอัตโนมัติ

Fetch-and-add as consensus (Fetch-and-add ในฐานะฉันทามติ)

ตัวสร้าง ID แบบ linearizable ที่เราเห็นใน "Linearizable ID Generators" ใกล้เคียงกับการแก้ปัญหาฉันทามติ แต่มันก็ยังขาดนิดหน่อย เราสามารถ implement ตัวสร้าง ID ดังกล่าวโดยใช้ fetch-and-add operation ซึ่งอะตอมมิก increment ตัวนับและคืนค่าเก่าของตัวนับ

ถ้าคุณมี CAS operation การ implement fetch-and-add นั้นง่าย ขั้นแรกให้อ่านค่าตัวนับ จากนั้นทำ CAS โดยที่ค่าที่คาดหวังคือค่าที่คุณอ่าน และค่าใหม่คือค่าบวก 1 ถ้า CAS ล้มเหลว คุณลองใหม่ทั้งกระบวนการจนกว่า CAS จะสำเร็จ ซึ่งมีประสิทธิภาพน้อยกว่า native fetch-and-add operation เมื่อมีการแย่งชิง (contention) แต่มันเทียบเท่ากันในเชิงฟังก์ชัน เนื่องจากคุณสามารถ implement CAS โดยใช้ฉันทามติ คุณจึงสามารถ implement fetch-and-add โดยใช้ฉันทามติได้เช่นกัน

ในทางกลับกัน ถ้าคุณมี fetch-and-add operation ที่ทนต่อความผิดพลาด คุณสามารถแก้ปัญหาฉันทามติได้หรือไม่? สมมติว่าคุณเริ่มต้นตัวนับเป็น 0 และทุก node ที่ต้องการเสนอค่าเรียกใช้ fetch-and-add operation เพื่อ increment ตัวนับ เนื่องจาก fetch-and-add operation เป็นอะตอมมิก หนึ่ง node จะอ่านค่าเริ่มต้น 0 และ node อื่นทั้งหมดจะอ่านค่าที่ถูก increment อย่างน้อยหนึ่งครั้ง

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

ข้อยกเว้นเกิดขึ้นถ้าเรารู้แน่ว่ามีไม่เกินสอง node ที่จะเสนอค่า ในกรณีนั้น node สามารถส่งค่าที่พวกมันต้องการเสนอให้กันและกัน แล้วแต่ละตัวทำ fetch-and-add operation node ที่อ่าน 0 ตัดสินใจค่าของตัวเอง และ node ที่อ่าน 1 ตัดสินใจค่าของอีก node ซึ่งแก้ปัญหาฉันทามติสำหรับสอง node ซึ่งเป็นเหตุผลที่เราสามารถพูดได้ว่า fetch-and-add มี consensus number เท่ากับ 2 [ 30 ] ในทางตรงกันข้าม CAS และ shared logs แก้ปัญหาฉันทามติสำหรับจำนวน node ใดๆ ที่อาจเสนอค่า ดังนั้นพวกมันมี consensus number เท่ากับ ∞ (อนันต์)

Atomic commitment as consensus (Atomic commitment ในฐานะฉันทามติ)

ใน "Distributed Transactions" เราเห็นปัญหา atomic commitment ซึ่งก็เพื่อรับประกันว่าฐานข้อมูลหรือ shards ที่เกี่ยวข้องใน distributed transaction ทั้ง commit หรือ abort transaction เรายังเห็นอัลกอริทึม two-phase commit ซึ่งอาศัย coordinator ที่เป็น single point of failure

ความสัมพันธ์ระหว่างฉันทามติและ atomic commitment คืออะไร? เมื่อมองแวบแรก พวกมันดูคล้ายกัน—ทั้งสองต้องการให้ node บรรลุข้อตกลงบางรูปแบบ อย่างไรก็ตาม มีความแตกต่างสำคัญหนึ่งประการ: ด้วยฉันทามติ มันโอเคที่จะตัดสินใจค่าใดๆ ที่ถูกเสนอ ในขณะที่ atomic commitment อัลกอริทึม ต้อง abort ถ้า ใดๆ ของผู้เข้าร่วมโหวตให้ abort โดยเฉพาะ atomic commitment ต้องการคุณสมบัติดังต่อไปนี้ [ 80 ]:

Uniform agreement

เป็นไปไม่ได้ที่หนึ่ง node จะ commit และอีก node จะ abort

Integrity

เมื่อ node commit แล้ว มันไม่สามารถเปลี่ยนใจเป็น abort และในทางกลับกัน

Validity

ถ้า node commit ทุก node ต้องเคยโหวตให้ commit ถ้า node ใดโหวตให้ abort ทุก node ต้อง abort

Nontriviality

ถ้าทุก node โหวตให้ commit และไม่มี communication timeout เกิดขึ้น ทุก node ต้อง commit

Termination

ทุก node ที่ไม่ crash จะ commit หรือ abort ในที่สุด

คุณสมบัติ validity รับประกันว่า transaction สามารถ commit ได้ก็ต่อเมื่อทุก node เห็นพ้องต้องกัน และคุณสมบัติ nontriviality รับประกันว่าอัลกอริทึมไม่สามารถ abort เสมอไป (แต่มันอนุญาตให้ abort ถ้าการสื่อสารระหว่าง node ใด timeout) สามคุณสมบัติอื่นโดยพื้นฐานแล้วเหมือนกับของฉันทามติ

ถ้าคุณมีวิธีแก้สำหรับฉันทามติ คุณสามารถแก้ไข atomic commitment ได้หลายวิธี [ 80 , 81 ] วิธีหนึ่งทำงานดังนี้: เมื่อคุณต้องการ commit transaction ทุก node ส่งการโหวต commit หรือ abort ไปยังทุก node อื่น node ที่ได้รับการโหวตให้ commit จากตัวเองและทุก node อื่นเสนอ "commit" ผ่านอัลกอริทึมฉันทามติ; node ที่ได้รับการโหวตให้ abort หรือที่เกิด timeout เสนอ "abort" ผ่านอัลกอริทึมฉันทามติ เมื่อ node รู้ว่าอัลกอริทึมฉันทามติตัดสินใจอะไร มันก็ commit หรือ abort ตามนั้น

ในอัลกอริทึมนี้ "commit" จะถูกเสนอก็ต่อเมื่อทุก node โหวตให้ commit ถ้า node ใดโหวตให้ abort ข้อเสนอทั้งหมดในอัลกอริทึมฉันทามติจะเป็น "abort" มันอาจเกิดขึ้นที่บาง node เสนอ "abort" ในขณะที่อื่นเสนอ "commit" ถ้าทุก node โหวตให้ commit แต่การสื่อสารบางอย่าง timeout; ในกรณีนี้ ไม่สำคัญว่า node จะ commit หรือ abort ตราบใดที่พวกมันทำสิ่งเดียวกันทั้งหมด

ถ้าคุณมีโปรโตคอล atomic commitment ที่ทนต่อความผิดพลาด คุณก็สามารถแก้ปัญหาฉันทามติได้เช่นกัน ทุก node ที่ต้องการเสนอค่าเริ่ม transaction บน quorum ของ node และที่แต่ละ node มันทำ single-node CAS เพื่อตั้งค่า register เป็นค่าที่เสนอถ้าค่าของมันยังไม่ได้ถูกตั้งโดย transaction อื่น ถ้า CAS สำเร็จ node โหวตให้ commit และถ้าไม่ก็โหวตให้ abort ถ้าโปรโตคอล atomic commit commit transaction ค่าของมันจะถูกตัดสินใจสำหรับฉันทามติ; ถ้า atomic commit abort node ที่เสนอจะลองใหม่กับ transaction ใหม่

นี่แสดงให้เห็นว่า atomic commit และฉันทามติก็เทียบเท่ากันเช่นกัน

Consensus in Practice (ฉันทามติในทางปฏิบัติ)

เราได้เห็นแล้วว่า single-value consensus, CAS, shared logs, และ atomic commitment ล้วนเทียบเท่ากัน: คุณสามารถแปลงวิธีแก้สำหรับปัญหาใดปัญหาหนึ่งเป็นวิธีแก้สำหรับปัญหาอื่นๆ ทั้งหมดได้ นั่นเป็นข้อมูลเชิงลึกทางทฤษฎีที่มีค่า แต่มันไม่ได้ตอบคำถามนี้: ในรูปแบบต่างๆ มากมายของฉันทามติ แบบไหนมีประโยชน์มากที่สุดในทางปฏิบัติ?

คำตอบคือระบบฉันทามติส่วนใหญ่ให้ shared logs (abstraction ที่เทียบเท่ากับ total order broadcast) Raft, Viewstamped Replication, และ Zab ให้ shared logs ทันทีที่ใช้งาน Paxos ให้ single-value consensus แต่ในทางปฏิบัติระบบส่วนใหญ่ที่ใช้ Paxos จริงๆ แล้วใช้ extension ที่เรียกว่า Multi-Paxos ซึ่งก็ให้ shared log เช่นกัน

Using shared logs (การใช้ shared logs)

shared log เหมาะกับการจำลองฐานข้อมูล ถ้าทุก log entry แทนการ write ไปยังฐานข้อมูล และทุก replica ประมวลผล writes เดียวกันในลำดับเดียวกันโดยใช้ตรรกะที่ deterministic แล้ว replica ทั้งหมดจะจบลงในสถานะที่สอดคล้องกัน แนวคิดนี้เรียกว่า state machine replication [ 82 ] และมันเป็นหลักการเบื้องหลัง event sourcing ซึ่งเราเห็นใน "Event Sourcing and CQRS" shared logs ยังมีประโยชน์สำหรับ stream processing ดังที่เราจะเห็นใน Chapter 12

ในทำนองเดียวกัน shared log สามารถใช้เพื่อ implement serializable transactions ดังที่กล่าวถึงใน "Actual Serial Execution" ถ้าทุก log entry แทน deterministic transaction ที่จะถูกดำเนินการเป็น stored procedure และถ้าทุก node ดำเนินการ transactions เหล่านั้นในลำดับเดียวกัน transactions จะเป็น serializable [ 83 , 84 ]

Note

ฐานข้อมูลแบบ sharded ที่มีโมเดลความสอดคล้องที่เข้มงวดมักจะรักษา log แยกต่อ shard ซึ่งปรับปรุง scalability แต่จำกัดการรับประกันความสอดคล้อง (เช่น consistent snapshots, foreign-key references) ที่พวกมันสามารถให้ข้าม shards Serializable transactions ข้าม shards เป็นไปได้แต่ต้องการการประสานงานเพิ่มเติม [ 85 ]

shared log ยังทรงพลังเพราะมันสามารถปรับให้เข้ากับรูปแบบอื่นของฉันทามติได้ง่าย:

  • เราเห็นก่อนหน้านี้แล้วว่าจะใช้มันเพื่อ implement single-value consensus และ CAS ได้อย่างไร: เพียงแค่ตัดสินใจค่าที่ปรากฏก่อนใน log

  • ถ้าคุณต้องการหลายอินสแตนซ์ของ single-value consensus — สมมติว่าหนึ่งต่อที่นั่งในโรงละครที่หลายคนพยายามจองที่นั่ง — ให้รวมหมายเลขที่นั่งใน log entries และตัดสินใจ log entry แรกที่มีหมายเลขที่นั่งนั้น

  • ถ้าคุณต้องการ atomic fetch-and-add ให้ใส่จำนวนที่จะบวกกับตัวนับใน log entry และให้ค่าตัวนับปัจจุบันเป็นผลรวมของ log entries ทั้งหมดจนถึงตอนนี้ ตัวนับอย่างง่ายบน log entries สามารถใช้เพื่อสร้าง fencing tokens (ดู "Fencing off zombies and delayed requests" ); ตัวอย่างเช่น ใน ZooKeeper หมายเลขลำดับนี้เรียกว่า zxid [ 20 ]

From single-leader replication to consensus (จาก Single-Leader Replication สู่ฉันทามติ)

เราเห็นก่อนหน้านี้ว่า single-value consensus นั้นง่ายถ้าคุณมี "dictator" node เดียวที่ทำการตัดสินใจ และในทำนองเดียวกัน shared log ก็ง่ายถ้า leader เดียวเป็น node เดียวที่ได้รับอนุญาตให้ append log entries คำถามคือจะให้ fault tolerance ได้อย่างไรถ้า node นั้นล้มเหลว

ตามธรรมเนียม ฐานข้อมูลที่มี single-leader replication ไม่ได้แก้ปัญหานี้: พวกมันปล่อยให้ leader failover เป็นการกระทำที่ผู้ดูแลระบบมนุษย์ต้องทำด้วยตนเอง น่าเสียดายที่นี่หมายถึง downtime จำนวนมาก เนื่องจากมีข้อจำกัดว่ามนุษย์สามารถตอบสนองได้เร็วแค่ไหน และมันไม่ตอบสนองคุณสมบัติ termination ของฉันทามติ สำหรับฉันทามติ เราต้องการให้อัลกอริทึมสามารถเลือก leader ใหม่ได้โดยอัตโนมัติ (ไม่ใช่อัลกอริทึมฉันทามติทั้งหมดที่มี leader แต่อัลกอริทึมที่ใช้กันทั่วไปมี [ 86 , 87 ])

สิ่งนี้ไม่ตรงไปตรงมา เราได้พูดถึงปัญหา split brain ก่อนหน้านี้ และเราได้กำหนดว่าทุก node ต้องตกลงกันว่าใครคือ leader — มิฉะนั้น สอง node แต่ละตัวอาจเชื่อว่าตัวเองเป็น leader และตัดสินใจที่ไม่สอดคล้องกัน ดังนั้น ดูเหมือนว่าเราจำเป็นต้องมีฉันทามติเพื่อเลือก leader และเราต้องการ leader เพื่อแก้ปัญหาฉันทามติ เราจะหลุดออกจากกับดักนี้ได้อย่างไร?

ในความเป็นจริง อัลกอริทึมฉันทามติไม่ได้ต้องการให้มี leader เพียงตัวเดียวในเวลาใดก็ตาม แต่พวกมันให้การรับประกันที่อ่อนแอกว่า: พวกมันกำหนด epoch number (เรียกว่า ballot number ใน Paxos, view number ใน Viewstamped Replication, และ term number ใน Raft) และรับประกันว่าภายในแต่ละ epoch leader จะไม่ซ้ำกัน

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

ก่อนที่ leader จะได้รับอนุญาตให้ append entry ถัดไปใน shared log มันต้องตรวจสอบก่อนว่าไม่มี leader อื่นที่มี epoch สูงกว่าที่อาจ append entry ที่แตกต่างกัน มันสามารถทำได้โดยรวบรวมโหวตจาก quorum ของ node — โดยปกติแล้ว แต่ไม่เสมอไป คือ majority ของ node [ 88 ] node โหวต "ใช่" ก็ต่อเมื่อมันไม่รู้จัก leader อื่นที่มี epoch สูงกว่า

ดังนั้น เรามีการโหวตสองรอบ: ครั้งแรกเพื่อเลือก leader และครั้งที่สองเพื่อโหวตข้อเสนอของ leader สำหรับ entry ถัดไปที่จะ append ไปยัง log quorums สำหรับการโหวตสองครั้งนี้ต้องทับซ้อนกัน: ถ้าการโหวตบนข้อเสนอสำเร็จ อย่างน้อยหนึ่งใน node ที่โหวตให้มันต้องมีส่วนร่วมในการเลือกตั้ง leader ที่สำเร็จล่าสุด [ 88 ] ถ้าการโหวตบนข้อเสนอผ่านโดยไม่เปิดเผย epoch ที่มีหมายเลขสูงกว่า leader ปัจจุบันสามารถสรุปได้ว่าไม่มี leader ที่มีหมายเลข epoch สูงกว่าถูกเลือก ดังนั้นมันสามารถ append entry ที่เสนอไปยัง log ได้อย่างปลอดภัย [ 28 , 89 ]

การโหวตสองรอบนี้ดูผิวเผินคล้ายกับ 2PC (ดู "Two-Phase Commit" ) แต่มันเป็นโปรโตคอลที่แตกต่างกันมาก ในอัลกอริทึมฉันทามติ node ใดๆ สามารถเริ่มการเลือกตั้งได้ และมันต้องการเพียง quorum ของ node ที่ตอบสนอง; ใน 2PC มีเพียง coordinator เท่านั้นที่สามารถขอโหวตได้ และมันต้องการโหวต "ใช่" จาก ทุก ผู้เข้าร่วมก่อนที่มันจะ commit

Subtleties of consensus (รายละเอียดปลีกย่อยของฉันทามติ)

โครงสร้างพื้นฐานนี้เป็นเรื่องธรรมดาใน Raft, Multi-Paxos, Viewstamped Replication, และ Zab: การโหวตโดย quorum ของ node เลือก leader และจากนั้นต้องมีการโหวต quorum อีกครั้งสำหรับทุก entry ที่ leader ต้องการ append ไปยัง log [ 70 , 71 ] ทุก log entry ใหม่ถูกจำลองแบบซิงโครนัสไปยัง quorum ของ node ก่อนที่จะยืนยันไปยัง client ที่ขอ write นี่รับประกันว่า log entry จะไม่สูญหายถ้า leader ปัจจุบันล้มเหลว

อย่างไรก็ตาม ปีศาจอยู่ในรายละเอียด และนั่นคือที่ที่อัลกอริทึมเหล่านี้ใช้แนวทางที่แตกต่างกัน ตัวอย่างเช่น เมื่อ leader เก่าล้มเหลวและ leader ใหม่ถูกเลือก อัลกอริทึมต้องแน่ใจว่า leader ใหม่ต้องยอมรับ log entries ใดๆ ที่ถูก append โดย leader เก่าก่อนที่มันจะล้มเหลว Raft ทำสิ่งนี้โดยอนุญาตให้ node กลายเป็น leader ใหม่ได้ก็ต่อเมื่อ log ของมันทันสมัยอย่างน้อยเท่ากับของ majority ของ followers [ 71 ] ในทางตรงกันข้าม Paxos อนุญาตให้ node ใดๆ กลายเป็น leader ใหม่ แต่ต้องการให้มันทำให้ log ทันสมัยกับ node อื่นก่อนที่มันจะเริ่ม append entries ใหม่ของตัวเอง

Consistency Versus Availability in Leader Election (ความสอดคล้องเทียบกับความพร้อมใช้งานในการเลือกตั้งผู้นำ)

ถ้าคุณต้องการให้อัลกอริทึมฉันทามติรับประกันคุณสมบัติที่วางไว้ใน "Shared logs as consensus" อย่างเคร่งครัด มันจำเป็นที่ leader ใหม่ต้องทันสมัยกับ log entries ที่ได้รับการยืนยันก่อนที่มันจะประมวลผล writes หรือ linearizable reads ใดๆ ถ้า node ที่มีข้อมูลเก่ากลายเป็น leader ใหม่ มันอาจเขียนค่าใหม่ไปยัง log entries ที่ถูกเขียนโดย leader เก่าแล้ว ซึ่งละเมิดคุณสมบัติ append-only ของ shared log

ในบางกรณี คุณอาจเลือกที่จะลดทอนคุณสมบัติของฉันทามติเพื่อกู้คืนจากความล้มเหลวของ leader ได้เร็วยิ่งขึ้น หรือเพื่อให้สามารถกู้คืนได้เลย ตัวอย่างเช่น Kafka เสนอตัวเลือกให้เปิดใช้งาน unclean leader election ซึ่งอนุญาตให้ replica ใดๆ กลายเป็น leader ได้ แม้ว่ามันจะไม่ทันสมัยก็ตาม นอกจากนี้ ในฐานข้อมูลที่มี asynchronous replication คุณไม่สามารถรับประกันว่า follower ใดๆ ทันสมัยเมื่อ leader ล้มเหลว

ถ้าคุณละทิ้งข้อกำหนดที่ leader ใหม่ต้องทันสมัย คุณอาจปรับปรุงประสิทธิภาพและความพร้อมใช้งานได้ แต่คุณกำลังอยู่บนน้ำแข็งบางๆ เนื่องจากทฤษฎีของฉันทามติไม่สามารถใช้ได้อีกต่อไป แม้ว่าสิ่งต่างๆ จะทำงานได้ดีตราบใดที่ไม่มีข้อผิดพลาด ปัญหาที่กล่าวถึงใน Chapter 9 อาจทำให้เกิดการสูญหายหรือเสียหายของข้อมูลได้ง่าย

รายละเอียดปลีกย่อยอีกประการคือวิธีที่อัลกอริทึมจัดการกับ log entries ที่ถูกเสนอโดย leader เก่าก่อนที่มันจะล้มเหลว แต่การโหวตในการ append ไปยัง log ยังไม่เสร็จสมบูรณ์ คุณสามารถหาการอภิปรายเกี่ยวกับรายละเอียดเหล่านี้ได้ในเอกสารอ้างอิงสำหรับบทนี้ [ 25 , 71 , 89 ]

สำหรับฐานข้อมูลที่ใช้อัลกอริทึมฉันทามติสำหรับการจำลองข้อมูล การเปลี่ยน writes เป็น log entries และจำลองไปยัง quorum ไม่ใช่ทั้งหมดที่จำเป็น ถ้าคุณต้องการรับประกันการอ่านแบบ linearizable พวกมันก็ต้องผ่านการโหวต quorum เช่นกัน คล้ายกับการเขียน เพื่อยืนยันว่า node ที่เชื่อว่าตัวเองเป็น leader ยังคงทันสมัยจริงๆ การอ่านแบบ linearizable ใน etcd ทำงานเช่นนี้ เป็นต้น

ในรูปแบบมาตรฐาน อัลกอริทึมฉันทามติส่วนใหญ่สมมติชุดของ node ที่คงที่ — นั่นคือ node อาจล้มและกลับมาอีกครั้ง แต่ชุดของ node ที่ได้รับอนุญาตให้โหวตจะคงที่เมื่อ cluster ถูกสร้างขึ้น ในทางปฏิบัติ มันมักจำเป็นต้องเพิ่ม node ใหม่หรือลบ node เก่าในการกำหนดค่าระบบ อัลกอริทึมฉันทามติได้ถูกขยายด้วยคุณสมบัติ reconfiguration ที่ทำให้สิ่งนี้เป็นไปได้ สิ่งนี้มีประโยชน์อย่างยิ่งเมื่อเพิ่มภูมิภาคใหม่ในระบบ หรือเมื่อย้ายจากที่หนึ่งไปยังอีกที่หนึ่ง (โดยการเพิ่ม node ใหม่ก่อนแล้วจึงลบ node เก่า)

Pros and cons of consensus (ข้อดีข้อเสียของฉันทามติ)

แม้ว่าพวกมันจะซับซ้อนและละเอียดอ่อน อัลกอริทึมฉันทามติคือความก้าวหน้าครั้งใหญ่สำหรับระบบกระจาย ฉันทามติโดยพื้นฐานแล้วคือ "single-leader replication ที่ทำถูกต้อง" ด้วย failover อัตโนมัติเมื่อ leader ล้มเหลว รับประกันว่าไม่มีข้อมูลที่ committed สูญหาย และ split brain เป็นไปไม่ได้ แม้จะเผชิญกับปัญหาทั้งหมดที่เรากล่าวถึงใน Chapter 9

ระบบใดๆ ที่ให้ automatic failover แต่ไม่ได้ใช้อัลกอริทึมฉันทามติที่ได้รับการพิสูจน์แล้วมักจะไม่ปลอดภัย [ 90 ] การใช้อัลกอริทึมฉันทามติที่ได้รับการพิสูจน์แล้วไม่ใช่การรับประกันความถูกต้องของทั้งระบบ—ยังมีสถานที่อื่นๆ อีกมากมายที่บั๊กสามารถซ่อนตัวได้—แต่มันเป็นจุดเริ่มต้นที่ดี

อย่างไรก็ตาม ฉันทามติไม่ได้ถูกใช้ทุกที่เพราะประโยชน์มาพร้อมกับต้นทุน ระบบฉันทามติต้องการ majority ที่เคร่งครัดเพื่อทำงาน—สาม node เพื่อทนต่อหนึ่งความล้มเหลว หรือห้า node เพื่อทนต่อสองความล้มเหลว ทุก operation ที่คุณทำต้องมีการสื่อสารกับ quorum ดังนั้นคุณไม่สามารถเพิ่ม throughput โดยการเพิ่ม node (ในความเป็นจริง ทุก node ที่คุณเพิ่มทำให้อัลกอริทึมช้าลง) ถ้า network partition ตัดบาง node ออกจากส่วนอื่น มีเพียงส่วน majority ของเครือข่ายเท่านั้นที่สามารถก้าวหน้าได้ และ node อื่นจะถูกบล็อก

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

บางครั้งอัลกอริทึมฉันทามติไวต่อปัญหาเครือข่ายเป็นพิเศษ ตัวอย่างเช่น Raft ได้รับการแสดงว่ามี edge cases ที่ไม่พึงประสงค์ [ 91 , 92 ] ถ้าเครือข่ายทั้งหมดทำงานอย่างถูกต้องยกเว้นลิงก์เครือข่ายหนึ่งที่เชื่อถือไม่ได้อย่างสม่ำเสมอ Raft อาจเข้าสู่สถานการณ์ที่ตำแหน่ง leader กระโดดไปมาระหว่างสอง node อย่างต่อเนื่อง หรือ leader ปัจจุบันถูกบังคับให้ลาออกอย่างต่อเนื่อง ทำให้ระบบไม่ก้าวหน้าเลย อัลกอริทึม Raft ดั้งเดิมถูกขยายด้วย pre-vote phase เพื่อแก้ไขปัญหานี้ [ 67 ] Paxos ก็ขึ้นอยู่กับ leaders เช่นกัน ซึ่งอาจทำให้เกิดปัญหา performance ที่คล้ายกัน Egalitarian Paxos (EPaxos) และอนุพันธ์ของมันใช้โปรโตคอลที่ไม่มี leader ซึ่งแข็งแกร่งกว่าต่อ node หรือการเชื่อมต่อเครือข่ายที่มีประสิทธิภาพต่ำ [ 86 ]

Coordination Services (บริการประสานงาน)

อัลกอริทึมฉันทามติมีประโยชน์ในฐานข้อมูลแบบกระจายใดๆ ที่ต้องการเสนอการดำเนินการแบบ linearizable และฐานข้อมูลแบบกระจายสมัยใหม่หลายตัวใช้พวกมันสำหรับการจำลองข้อมูล แต่ระบบหนึ่งตระกูลเป็นผู้ใช้ฉันทามติที่โดดเด่นเป็นพิเศษ: coordination services เช่น ZooKeeper, etcd, และ Consul แม้ว่าระบบเหล่านี้จะดูภายนอกเหมือน key-value store อื่นๆ พวกมันไม่ได้ออกแบบมาสำหรับปริมาณการเขียนสูงหรือการจัดเก็บข้อมูลทั่วไปเหมือนฐานข้อมูลส่วนใหญ่

แต่พวกมันถูกออกแบบมาเพื่อประสานงานระหว่าง node ของระบบกระจายอื่น ตัวอย่างเช่น Kubernetes พึ่งพา etcd ในขณะที่ Spark และ Flink ในโหมด high availability พึ่งพา ZooKeeper ที่ทำงานเบื้องหลัง Coordination services ออกแบบมาเพื่อเก็บข้อมูลจำนวนน้อยที่สามารถใส่ในหน่วยความจำทั้งหมด (แม้ว่าพวกมันยังเขียนลงดิสก์เพื่อความคงทน) ซึ่งถูกจำลองข้ามหลาย node ผ่านอัลกอริทึมฉันทามติที่ทนต่อความผิดพลาด

Coordination services ถูกสร้างแบบจำลองตามบริการล็อก Chubby ของ Google [ 19 , 60 ] พวกมันรวมอัลกอริทึมฉันทามติเข้ากับคุณสมบัติอื่นๆ อีกหลายอย่างที่มีประโยชน์อย่างยิ่งในการสร้างระบบกระจาย:

Locks and leases (การล็อกและสัญญาเช่า)

เราเห็นก่อนหน้านี้ว่าระบบฉันทามติสามารถ implement operation CAS แบบอะตอมมิกที่ทนต่อความผิดพลาดได้อย่างไร Coordination services อาศัยแนวทางนี้เพื่อ implement locks และ leases ถ้าหลาย node พยายามขอ lease เดียวกันพร้อมกัน มีเพียงหนึ่งในนั้นเท่านั้นที่จะสำเร็จ

Support for fencing (การสนับสนุนการกั้น)

ดังที่กล่าวถึงใน "Distributed Locks and Leases" เมื่อทรัพยากรถูกป้องกันโดย lease คุณต้องมี fencing เพื่อป้องกันไม่ให้ client รบกวนกันในกรณีที่ process หยุดชั่วคราวหรือ network delay มาก ระบบฉันทามติสามารถสร้าง fencing tokens โดยให้แต่ละ log entry มี ID ที่เพิ่มขึ้นแบบ monotonic ( zxid และ cversion ใน ZooKeeper, revision number ใน etcd)

Failure detection (การตรวจจับความล้มเหลว)

Client รักษา session ที่มีอายุยาวนานบน coordination service และแลกเปลี่ยน heartbeats เป็นระยะเพื่อตรวจสอบว่า node อื่นยังมีชีวิตอยู่หรือไม่ แม้ว่าการเชื่อมต่อจะถูกขัดจังหวะชั่วคราวหรือเซิร์ฟเวอร์ล้มเหลว leases ใดๆ ที่ client ถืออยู่จะยังคงทำงาน อย่างไรก็ตาม ถ้าไม่มี heartbeat นานกว่า timeout ของ lease coordination service จะถือว่า client ตายและปล่อย lease (ZooKeeper เรียกสิ่งเหล่านี้ว่า ephemeral nodes )

Change notifications (การแจ้งเตือนการเปลี่ยนแปลง)

client สามารถขอให้ coordination service ส่งการแจ้งเตือนเมื่อ keys บางอย่างเปลี่ยนแปลง สิ่งนี้ช่วยให้ client รู้ว่าเมื่อ client อื่นเข้าร่วม cluster (ขึ้นอยู่กับค่าที่มันเขียนไปยัง coordination service) หรือถ้า client อื่นล้มเหลว (เพราะ session ของมันหมดเวลาและ ephemeral nodes ของมันหายไป) เป็นต้น การแจ้งเตือนเหล่านี้ช่วย client จากการต้อง polling บริการบ่อยๆ เพื่อหาการเปลี่ยนแปลง

Failure detection และ change notifications ไม่ต้องการฉันทามติ แต่มันมีประโยชน์สำหรับการประสานงานแบบกระจายควบคู่ไปกับการดำเนินการอะตอมมิกและการสนับสนุน fencing ที่ต้องใช้ฉันทามติ

Managing Configuration with Coordination Services (การจัดการการกำหนดค่าด้วยบริการประสานงาน)

แอปพลิเคชันและโครงสร้างพื้นฐานมักมีพารามิเตอร์การกำหนดค่าเช่น timeouts, thread pool sizes และอื่นๆ Coordination services บางครั้งใช้เพื่อจัดเก็บข้อมูลการกำหนดค่าดังกล่าว แสดงเป็น key-value pairs กระบวนการโหลดการตั้งค่าล่าสุดเมื่อเริ่มต้นและสมัครรับการแจ้งเตือนการเปลี่ยนแปลงใดๆ เมื่อการกำหนดค่าเปลี่ยน กระบวนการสามารถเริ่มใช้การตั้งค่าใหม่ทันทีหรือรีสตาร์ทตัวเองเพื่อโหลดการเปลี่ยนแปลงล่าสุด

การจัดการการกำหนดค่าไม่จำเป็นต้องมี aspect ของฉันทามติของ coordination service แต่มันสะดวกที่จะใช้ coordination service และพึ่งพาคุณสมบัติการแจ้งเตือนของมันถ้าคุณกำลังรันบริการอยู่แล้ว อีกทางเลือกหนึ่ง กระบวนการสามารถ polling สำหรับการอัปเดตการกำหนดค่าเป็นระยะจากไฟล์หรือ URL ซึ่งหลีกเลี่ยงความต้องการบริการพิเศษ

Allocating work to nodes (การจัดสรรงานให้กับ nodes)

coordination service มีประโยชน์ถ้าคุณมีหลายอินสแตนซ์ของ process หรือบริการ และหนึ่งในนั้นต้องถูกเลือกเป็น leader หรือ primary ถ้า leader ล้มเหลว node อื่นควรรับช่วงต่อ การดำเนินการนี้จำเป็นสำหรับฐานข้อมูล single-leader แต่มันก็เหมาะสมสำหรับ job schedulers และระบบ stateful ที่คล้ายกัน

การใช้งานอีกอย่างคือเมื่อคุณมีทรัพยากรแบบ sharded (database, message streams, file storage, distributed actor system ฯลฯ) และต้องตัดสินใจว่าจะกำหนด shard ใดให้ node ใด เมื่อ node ใหม่เข้าร่วม cluster shards บางส่วนต้องถูกย้ายจาก node ที่มีอยู่ไปยัง node ใหม่เพื่อ rebalance โหลด เมื่อ node ถูกลบหรือล้มเหลว node อื่นต้องรับงานของ node ที่ล้มเหลว

งานประเภทนี้สามารถทำได้โดยการใช้ atomic operations, ephemeral nodes, และ notifications ใน coordination service อย่างชาญฉลาด ถ้าทำถูกต้อง แนวทางนี้ช่วยให้แอปพลิเคชันกู้คืนจากความผิดพลาดโดยอัตโนมัติโดยไม่ต้องมีการแทรกแซงจากมนุษย์ มันไม่ง่าย แม้จะมีไลบรารีเช่น Apache Curator ที่เกิดขึ้นเพื่อให้เครื่องมือระดับสูงบน ZooKeeper client API—แต่มัน ก็ยังดีกว่าการพยายาม implement อัลกอริทึมฉันทามติที่จำเป็นตั้งแต่ต้น ซึ่งมีแนวโน้มที่จะมีบั๊กมาก

coordination service โดยเฉพาะยังมีข้อได้เปรียบที่ว่ามันสามารถทำงานบนชุด node ที่คงที่ (ปกติสามหรือห้า) โดยไม่ขึ้นกับจำนวน node ในระบบกระจายที่พึ่งพามันสำหรับการประสานงาน ตัวอย่างเช่น ในระบบจัดเก็บข้อมูลที่มี shards นับพัน การรันอัลกอริทึมฉันทามติบน node นับพันจะไม่มีประสิทธิภาพอย่างยิ่ง; มันดีกว่ามากที่จะ "outsource" ฉันทามติไปยัง node จำนวนน้อยที่รัน coordination service

โดยปกติแล้ว ข้อมูลประเภทที่จัดการโดย coordination service เปลี่ยนแปลงค่อนข้างช้า ข้อมูลแสดงถึงข้อมูลเช่น "node ที่รันบน IP address 10.1.1.23 เป็น leader สำหรับ shard 7" และการกำหนดดังกล่าวมักเปลี่ยนในระดับนาทีหรือชั่วโมง Coordination services ไม่ได้มีไว้สำหรับจัดเก็บข้อมูลที่อาจเปลี่ยนแปลงหลายพันครั้งต่อวินาที สำหรับสิ่งนั้น ควรใช้ฐานข้อมูลทั่วไป; อีกทางเลือกหนึ่ง เครื่องมือเช่น Apache BookKeeper [ 93 , 94 ] สามารถใช้เพื่อจำลองสถานะภายในของบริการที่เปลี่ยนแปลงอย่างรวดเร็ว

Service discovery (การค้นพบบริการ)

ZooKeeper, etcd, และ Consul มักถูกใช้สำหรับ service discovery —นั่นคือ เพื่อค้นหาว่าต้องเชื่อมต่อกับ IP address ใดเพื่อเข้าถึงบริการเฉพาะ (ดู "Load balancers, service discovery, and service meshes" ) ในสภาพแวดล้อมคลาวด์ ซึ่งเป็นเรื่องธรรมดาที่เครื่องเสมือนจะมาและไปตลอดเวลา คุณมักจะไม่รู้ IP addresses ของบริการของคุณล่วงหน้า แต่คุณสามารถกำหนดค่าบริการของคุณให้เมื่อเริ่มต้น พวกมันลงทะเบียน endpoints เครือข่ายของพวกมันใน service registry ซึ่งพวกมันสามารถถูกค้นพบโดยบริการอื่น

การใช้ coordination service สำหรับ service discovery สะดวก เนื่องจากคุณสมบัติการตรวจจับความล้มเหลวและการแจ้งเตือนการเปลี่ยนแปลงทำให้ client ติดตามอินสแตนซ์บริการขณะที่พวกมันมาและไปได้ง่าย และถ้าคุณใช้ coordination service สำหรับ leases, locking, หรือ leader election อยู่แล้ว มันก็สมเหตุสมผลที่จะใช้มันสำหรับ service discovery ด้วย เนื่องจากมันรู้อยู่แล้วว่า node ใดควรได้รับคำขอสำหรับบริการของคุณ

อย่างไรก็ตาม การใช้ฉันทามติสำหรับ service discovery มักจะเกินความจำเป็น กรณีการใช้งานนี้โดยทั่วไปไม่ต้องการ linearizability และมันสำคัญกว่าที่ service discovery จะพร้อมใช้งานสูงและรวดเร็ว เนื่องจากถ้าไม่มีมันทุกอย่างจะชะงัก ดังนั้นจึงมักจะดีกว่าที่จะ cache ข้อมูล service discovery client ที่ไม่สามารถเชื่อมต่อกับบริการสามารถบายพาส cache, ลองใหม่ด้วยค่าล่าสุด, และอัปเดต cache ถ้าจำเป็น cache อาจถูกรีเฟรชเป็นระยะโดยใช้ time-to-live (TTL) configuration ตัวอย่างเช่น DNS-based service discovery ใช้หลายชั้นของการ caching เพื่อให้ได้ประสิทธิภาพและความพร้อมใช้งานที่ดี

เพื่อรองรับกรณีการใช้งานนี้ ZooKeeper รองรับ observers replica เหล่านี้รับ log และรักษาสำเนาของข้อมูลที่จัดเก็บใน ZooKeeper แต่ไม่ได้มีส่วนร่วมในกระบวนการโหวตของอัลกอริทึมฉันทามติ การอ่านจาก observer ไม่เป็น linearizable เนื่องจากอาจเก่า แต่มันยังคงพร้อมใช้งานแม้ว่าเครือข่ายจะถูกขัดจังหวะ และมันเพิ่ม throughput การอ่านที่ระบบสามารถรองรับได้โดยการ caching

Summary (สรุป)

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

แม้ว่า linearizability จะน่าสนใจเพราะมันเข้าใจง่าย—มันทำให้ฐานข้อมูลทำงานเหมือนตัวแปรในโปรแกรม single-threaded—แต่มันมีข้อเสียคือช้า โดยเฉพาะในสภาพแวดล้อมที่มีความหน่วงของเครือข่ายสูง อัลกอริทึมการจำลองข้อมูลจำนวนมากไม่รับประกัน linearizability แม้ว่ามันอาจดูผิวเผินเหมือนว่าพวกมันให้ความสอดคล้องแบบเข้มงวด

ต่อไป เราใช้แนวคิดของ linearizability ในบริบทของตัวสร้าง ID ตัวนับ autoincrementing แบบโน้ตเดียวเป็น linearizable แต่ไม่ทนต่อความผิดพลาด รูปแบบการสร้าง ID แบบกระจายจำนวนมากไม่รับประกันว่า IDs จะถูกเรียงลำดับสอดคล้องกับลำดับที่เหตุการณ์เกิดขึ้นจริง นาฬิกาเชิงตรรกะเช่น Lamport clocks และ hybrid logical clocks ให้การเรียงลำดับที่สอดคล้องกับความเป็นเหตุเป็นผล แต่ไม่รับประกัน linearizability

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

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

การดำเนินการ CAS แบบ Linearizable

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

Locks และ leases

เมื่อ client หลายตัวพยายามขอ lock หรือ lease พร้อมกัน lock ตัดสินใจ ว่าอันไหนได้รับมันสำเร็จ

ข้อจำกัดความเป็นเอกลักษณ์ (Uniqueness constraints)

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

Shared logs

เมื่อหลาย node ต้องการ append entries ไปยัง log พร้อมกัน log ตัดสินใจ ลำดับที่พวกมันถูก append shared logs ถูก implement โดยใช้ total order broadcast protocol

Atomic transaction commit

node ฐานข้อมูลที่เกี่ยวข้องใน distributed transaction ทั้งหมดต้อง ตัดสินใจ ในแนวทางเดียวกันว่าจะ commit หรือ abort transaction

การดำเนินการ Fetch-and-add แบบ Linearizable

การดำเนินการประเภทนี้สามารถใช้เพื่อ implement ตัวสร้าง ID หลาย node สามารถเรียกใช้การดำเนินการพร้อมกัน และมัน ตัดสินใจ ลำดับที่พวกมัน increment ตัวนับ กรณีนี้จริงๆ แล้วแก้ไขฉันทามติระหว่างสอง node เท่านั้น ในขณะที่กรณีอื่นทำงานสำหรับจำนวน node ใดๆ

ทั้งหมดนี้ตรงไปตรงมาถ้าคุณมีเพียง node เดียวหรือถ้าคุณยินดีมอบความสามารถในการตัดสินใจให้กับ node เดียว สิ่งนี้เกิดขึ้นในฐานข้อมูล single-leader: อำนาจทั้งหมดในการตัดสินใจอยู่ที่ leader ซึ่งเป็นเหตุผลที่ฐานข้อมูลดังกล่าวสามารถให้การดำเนินการแบบ linearizable, uniqueness constraints, replication log และอื่นๆ

อย่างไรก็ตาม ถ้า leader เดียวนั้นล้มเหลว หรือถ้าการขัดจังหวะเครือข่ายทำให้ leader ไม่สามารถเข้าถึงได้ ระบบดังกล่าวจะไม่สามารถก้าวหน้าใดๆ จนกว่ามนุษย์จะทำ manual failover อัลกอริทึมฉันทามติที่ใช้กันอย่างแพร่หลายเช่น Raft และ Paxos โดยพื้นฐานแล้วคือ single-leader replication ที่มีการเลือกตั้ง leader อัตโนมัติและ failover ในตัวถ้า leader ปัจจุบันล้มเหลว

อัลกอริทึมฉันทามติถูกออกแบบมาอย่างระมัดระวังเพื่อรับประกันว่าไม่มี writes ที่ committed สูญหายระหว่าง failover และระบบไม่สามารถเข้าสู่สถานะ split-brain ที่หลาย node กำลังรับ writes ซึ่งต้องการให้ทุก write และทุก linearizable read ได้รับการยืนยันโดย quorum (โดยปกติคือ majority) ของ node สิ่งนี้อาจแพง โดยเฉพาะข้ามภูมิภาค แต่มันหลีกเลี่ยงไม่ได้ถ้าคุณต้องการความสอดคล้องที่เข้มงวดและ fault tolerance ที่ฉันทามติให้

Coordination services เช่น ZooKeeper และ etcd ก็ถูกสร้างบนอัลกอริทึมฉันทามติเช่นกัน พวกมันให้ locks, leases, failure detection, และคุณสมบัติการแจ้งเตือนการเปลี่ยนแปลงที่มีประโยชน์สำหรับการจัดการสถานะของแอปพลิเคชันแบบกระจาย ถ้าคุณพบว่าตัวเองต้องการทำสิ่งใดสิ่งหนึ่งที่ลดลงเป็นฉันทามติ และคุณต้องการให้มันทนต่อความผิดพลาด ขอแนะนำให้ใช้ coordination service มันจะไม่รับประกันว่าคุณจะทำให้ถูกต้อง แต่มันจะช่วยได้

อัลกอริทึมฉันทามติซับซ้อนและละเอียดอ่อน แต่มันได้รับการสนับสนุนโดยทฤษฎีที่ร่ำรวยซึ่งได้รับการพัฒนาตั้งแต่ปี 1980s ทฤษฎีนี้ทำให้สามารถสร้างระบบที่สามารถทนต่อความผิดพลาดทั้งหมดที่เรากล่าวถึงใน Chapter 9 และยังรับประกันว่าข้อมูลของคุณไม่เสียหาย นี่คือความสำเร็จที่น่าทึ่ง และเอกสารอ้างอิงในตอนท้ายของบทนี้มีไฮไลท์บางส่วนของงานนี้

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