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

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

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

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

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

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

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

แนวทางนี้มองว่าแอปพลิเคชันไม่ควรต้องกังวลกับรายละเอียดภายในของ replication และระบบควรทำงานราวกับเป็นโหนดเดียว ข้อดีคือทำให้งานของคุณในฐานะนักพัฒนาแอปพลิเคชันง่ายขึ้น ข้อเสียคือ strong consistency มีต้นทุนด้านประสิทธิภาพ และ fault บางประเภทที่ระบบ 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 ได้อย่างไรโดยยังทนต่อ fault ได้ — คำตอบคือ consensus algorithm

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

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

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

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

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

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

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

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

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

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

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

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

Figure 10-2. ถ้า read เกิดพร้อมกับ write อาจได้ค่าเก่าหรือค่าใหม่ก็ได้

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

ในตัวอย่างนี้ register มี operation สองแบบ:

• 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 poll ฐานข้อมูลซ้ำ ๆ เพื่ออ่านค่าล่าสุด A และ B จะได้ค่าอะไรบ้างจาก read ของพวกเขา?

มาไล่ดูทีละกรณี:

• read ครั้งแรกของ client A เสร็จก่อนที่ write จะเริ่ม จึงต้องคืนค่าเก่า คือ 0

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

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

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

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

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

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

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

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

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

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

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

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

มีรายละเอียดน่าสนใจบางข้อใน Figure 10-4 :

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

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

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

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

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

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

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

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

Serializability

Serializability เป็น isolation level ของ transaction ซึ่งแต่ละ transaction อาจอ่านและเขียน หลาย object (row, document, record) โดยรับประกันว่า transaction ทำงานเหมือนกับถูกรันตาม บาง ลำดับแบบ serial — คือเหมือนรัน transaction หนึ่งให้จบทั้งหมดก่อน แล้วค่อยรันอีกอันให้จบ ไปเรื่อย ๆ โดยไม่สลับกัน ลำดับ serial นี้จะต่างจากลำดับที่ transaction ถูกเรียกจริงก็ได้ [ 9 ]

Linearizability

Linearizability เป็นการรับประกันเกี่ยวกับ read และ write ของ register ( object เดียว ) ไม่ได้รวม operation เป็น transaction จึงไม่ป้องกันปัญหาอย่าง write skew ที่เกี่ยวกับหลาย object (ดู "Write Skew and Phantoms" ) แต่ linearizability รับประกัน recency (ความใหม่ของข้อมูล) : ถ้า operation หนึ่งเสร็จก่อนที่อีก operation จะเริ่ม operation หลังต้องเห็นสถานะที่ใหม่อย่างน้อยเท่ากับ operation แรก Serializability ไม่มีเงื่อนไขนี้ — ตัวอย่างเช่น serializability อนุญาตให้เกิด stale read [ 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 ] เพราะต้องมีการประสานงานระหว่าง transaction ซึ่งมีต้นทุนสูง [ 14 ] ในทางกลับกัน Spanner และ FoundationDB มี strict serializability [ 15 , 16 ]

เรายังเอา isolation level ที่อ่อนกว่ามาใช้ร่วมกับ linearizability หรือเอา consistency model ที่อ่อนกว่ามาใช้ร่วมกับ serializability ได้ จริง ๆ แล้ว consistency model กับ isolation level เลือกแยกจากกันได้ค่อนข้างอิสระ [ 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 ] ไม่ว่ากลไกนี้จะ implement แบบไหน มันต้องเป็น linearizable ต้องไม่มีทางที่สอง node จะได้ lease พร้อมกัน

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

Note

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

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

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

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

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

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

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

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

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

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

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

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

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

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

race condition แบบเดียวกันเกิดขึ้นได้ถ้าคุณมีแอปมือถือที่รับ push notification แล้วดึงข้อมูลจากเซิร์ฟเวอร์เมื่อได้รับ 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 โดยพื้นฐานแล้วแปลว่า "ทำงานราวกับมีข้อมูลเพียงชุดเดียว และทุก operation บนข้อมูลนั้นเป็น atomic" คำตอบที่ง่ายที่สุดก็คือใช้ข้อมูลเพียงชุดเดียวจริง ๆ แต่แนวทางนั้นจะทนต่อ fault ไม่ได้: ถ้า node ที่เก็บข้อมูลชุดเดียวนั้นล่ม ข้อมูลจะหายไป หรืออย่างน้อยก็เข้าถึงไม่ได้จนกว่า node จะกลับมา

ลองกลับไปดูวิธี replication จาก Chapter 6 อีกครั้งว่าวิธีไหนทำให้เป็น linearizable ได้บ้าง:

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

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

การ shard ฐานข้อมูลแบบ single-leader โดยมี leader แยกกันในแต่ละ shard ไม่กระทบ linearizability เพราะเป็นการรับประกันในระดับ object เดียวเท่านั้น ส่วน cross-shard transaction เป็นอีกเรื่องหนึ่ง (ดู "Distributed Transactions" )

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

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

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

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

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

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

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

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

ใน Figure 10-6 ค่าเริ่มต้นของ x คือ 0 และ writer client กำลังอัปเดต x เป็น 1 โดยส่ง write ไปยัง replica ทั้งสามตัว ( 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 request ของ B เริ่มหลัง request ของ A เสร็จ แต่ B ได้ค่าเก่าในขณะที่ A ได้ค่าใหม่ (เป็นสถานการณ์ Aaliyah และ Bryce อีกครั้งจาก Figure 10-1 )

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

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

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

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

replication บางวิธีให้ linearizability ได้ บางวิธีให้ไม่ได้ ลองมาดู trade-off ของ linearizability ให้ลึกขึ้น

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

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

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

ถ้าเป็นฐานข้อมูล multi-leader แต่ละภูมิภาคยังทำงานได้ตามปกติ เพราะ write จากภูมิภาคหนึ่งถูก replicate ไปอีกภูมิภาคแบบ asynchronous write จะรออยู่ในคิวและถูกแลกเปลี่ยนกันเมื่อเครือข่ายกลับมาเชื่อมต่อได้

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

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

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

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

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

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

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

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

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

CAP theorem ตามนิยามอย่างเป็นทางการ [ 32 ] มีขอบเขตแคบมาก มันพิจารณา consistency model เพียงแบบเดียว (คือ linearizability) และ fault ชนิดเดียว (network partition ซึ่งจากข้อมูลของ Google เป็นสาเหตุของ incident น้อยกว่า 8% [ 39 ]) มันไม่ได้พูดถึง network delay, node ที่ตาย หรือ trade-off อื่น ๆ ดังนั้นแม้ CAP จะมีอิทธิพลในอดีต แต่ในทางปฏิบัติมีประโยชน์ต่อการออกแบบระบบน้อยมาก [ 4 , 45 ]

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

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

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

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

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

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

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

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

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

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

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

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

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

ID Generators and Logical Clocks (ID generator และ logical clock)

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

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

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

Figure 10-8. ID generator ที่กำหนด autoincrementing integer ID ให้ข้อความในแอปแชท

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

• ID generator แบบโหนดเดียวทนต่อ fault ไม่ได้ เพราะ node นั้นเป็น single point of failure

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

• node เดียวอาจกลายเป็นคอขวดถ้ามี write จำนวนมาก

ลองดูตัวเลือกอื่น ๆ สำหรับ ID generator:

Sharded ID assignment (การกำหนด ID แบบแบ่ง shard)

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

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

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

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

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

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

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

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

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

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

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

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

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

logical clock โดยทั่วไปต้องมีคุณสมบัติดังนี้:

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

• เทียบ timestamp สองตัวเพื่อดูว่าอันไหนเกิดก่อนได้ (นั่นคือ totally ordered (เรียงลำดับได้ทั้งหมด) )

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

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

Lamport timestamps (timestamps ของ Lamport)

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

แม้ Lamport clock จะให้ total ordering (การเรียงลำดับทั้งหมด) แต่ ไม่ได้ ให้ linearizability — คือไม่ได้รับประกันว่าค่าที่อ่านเป็นค่าล่าสุด เป็นเพียงวิธีกำหนด ID ให้ event เพื่อให้ถ้า 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 ก็ไม่ซ้ำกัน

Figure 10-9. Lamport timestamp ให้ total ordering ที่สอดคล้องกับ causality

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

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

ในการเทียบ Lamport timestamp สองตัว ให้เทียบ counter ก่อน — ตัวอย่างเช่น (2, "Bryce") มากกว่า (1, "Aaliyah") และมากกว่า (1, "Caleb") ด้วย ถ้า counter เท่ากัน ก็เทียบ node ID ด้วยการเทียบ string แบบ lexicographic ธรรมดา ดังนั้นลำดับ timestamp ในตัวอย่างนี้คือ (1, "Aaliyah") < (1, "Caleb") < (2, "Bryce")

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

Lamport timestamp บันทึกลำดับของเหตุการณ์ได้ดี แต่ก็มีข้อจำกัดบางอย่าง:

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

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

Hybrid logical clock รวมข้อดีของ physical time-of-day clock เข้ากับการรับประกันเรื่องลำดับของ Lamport clock [ 57 ] เหมือน physical clock ตรงที่นับเป็นวินาทีหรือไมโครวินาที และเหมือน Lamport clock ตรงที่เมื่อ node หนึ่งเห็น timestamp จาก node อื่นที่มากกว่า clock ของตัวเอง ก็จะเลื่อน clock ของตัวเองไปข้างหน้าให้ตรงกับ timestamp นั้น ดังนั้นถ้า 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 relation ไม่ต้องพึ่งฮาร์ดแวร์พิเศษ และต้องการแค่ clock ที่ synchronize กันแบบคร่าว ๆ Hybrid logical clock ถูกใช้ใน CockroachDB เป็นต้น

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

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

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

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

Linearizable ID Generators (ID generator แบบ Linearizable)

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

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

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

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

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

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

Implementing a linearizable ID generator (การ Implement ID generator แบบ Linearizable)

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

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

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

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

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

Enforcing constraints using logical clocks (การบังคับใช้ข้อจำกัดโดยใช้ logical clock)

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

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

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

การ implement lock, lease และโครงสร้างที่คล้ายกันให้ทนต่อ fault ได้ ต้องใช้บางอย่างที่แข็งแรงกว่า logical clock หรือ ID generator สิ่งที่ต้องใช้คือ consensus

Consensus (ฉันทามติ)

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

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

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

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

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

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

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

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

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

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

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

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

Consensus ปรากฏได้หลายรูปแบบ ตัวอย่างเช่น:

• Single-value consensus คล้ายกับ CAS แบบ atomic มาก ใช้ implement lock, lease และ uniqueness constraint ได้

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

• Operation fetch-and-add แบบ atomic (หรือ atomic increment) ก็เทียบเท่ากับ consensus เช่นกัน

• Atomic commitment ของ transaction ที่ข้ามหลายฐานข้อมูลหรือหลาย shard ต้องการให้ผู้เข้าร่วมทั้งหมดตกลงกันว่าจะ commit หรือ abort transaction

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

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

การที่หลาย node ตกลงกันเลือกค่าเดียวได้นั้นมีประโยชน์มาก ตัวอย่างเช่น:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Compare-and-set as consensus (Compare-and-set ในฐานะ consensus)

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

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

ในทำนองเดียวกัน ถ้ามีวิธีแก้ consensus ก็ implement CAS ได้ เมื่อใดก็ตามที่ node หนึ่งตัวหรือมากกว่าต้องการทำ CAS ด้วยค่าที่คาดหวังเดียวกัน ก็ใช้ consensus protocol เสนอค่าใหม่ที่อยู่ใน CAS invocation แล้วตั้ง object เป็นค่าที่ consensus ตัดสิน CAS invocation ที่ค่าที่เสนอไม่ถูกเลือกจะคืน error ส่วน CAS invocation ที่มีค่าที่คาดหวังต่างกันจะใช้ consensus protocol คนละรอบกัน

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

Shared logs as consensus (shared log ในฐานะ consensus)

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

ในเชิงทางการมากขึ้น shared log รองรับสอง operation คือขอให้เพิ่มค่าลงใน log และอ่าน entry ใน log โดยต้องมีคุณสมบัติดังนี้:

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

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

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

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

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

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

Agreement (ข้อตกลงร่วม)

ถ้าสอง node อ่าน log entry e ก่อน e นั้น ทั้งสอง node ต้องอ่าน log entry ชุดเดียวกันทุกประการในลำดับเดียวกัน

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 "deliver" ค่านั้น มันจะกลายเป็นส่วนหนึ่งของ log entry ที่อ่านได้

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

ในทางกลับกัน ถ้ามีวิธีแก้ consensus ก็ implement shared log ได้ รายละเอียดซับซ้อนกว่าเล็กน้อย แต่แนวคิดพื้นฐานเป็นดังนี้ [ 75 ]:

1. มี slot ใน log สำหรับ log entry ในอนาคตทุกตัว และรัน consensus algorithm แยก instance ต่อหนึ่ง slot เพื่อตัดสินว่าค่าใดควรอยู่ใน entry นั้น

2. เมื่อ node ต้องการเพิ่มค่าลงใน log ก็เสนอค่านั้นสำหรับ slot ใด slot หนึ่งที่ยังไม่ถูกตัดสิน

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

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

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

Fetch-and-add as consensus (Fetch-and-add ในฐานะ consensus)

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

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

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

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

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

Atomic commitment as consensus (Atomic commitment ในฐานะ consensus)

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

consensus กับ atomic commitment เกี่ยวข้องกันอย่างไร? เมื่อมองครั้งแรกดูคล้ายกันมาก — ทั้งสองอย่างต้องให้ node ตกลงกันในรูปแบบใดรูปแบบหนึ่ง แต่มีความต่างสำคัญข้อหนึ่ง: ใน consensus ตัดสินเลือกค่าใดก็ได้ที่ถูกเสนอมา ส่วนใน 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 และไม่มีการสื่อสารที่ timeout ทุก node ต้อง commit

Termination

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

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

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

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

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

นี่แสดงว่า atomic commit กับ consensus ก็เทียบเท่ากันเช่นกัน

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

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

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

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

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

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

Note

ฐานข้อมูลแบบ sharded ที่มี strong consistency model มักมี log แยกต่อ shard ซึ่งช่วยเรื่อง scalability แต่จำกัดการรับประกันด้านความสอดคล้อง (เช่น consistent snapshot, foreign-key reference) ที่ให้ได้ข้าม shard Serializable transaction ข้าม shard ทำได้ แต่ต้องมีการประสานงานเพิ่มเติม [ 85 ]

shared log ยังทรงพลังเพราะดัดแปลงให้เป็น consensus รูปแบบอื่นได้ง่าย:

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

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

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

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

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

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

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

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

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

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

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

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

Subtleties of consensus (รายละเอียดปลีกย่อยของ consensus)

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

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

Consistency Versus Availability in Leader Election (Consistency เทียบกับ Availability ในการเลือก leader)

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

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

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

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

สำหรับฐานข้อมูลที่ใช้ consensus algorithm ทำ replication การแปลง write เป็น log entry แล้ว replicate ไปยัง quorum ยังไม่ใช่ทั้งหมดที่ต้องทำ ถ้าต้องการรับประกัน linearizable read ก็ต้องผ่านการโหวตของ quorum เช่นเดียวกับ write เพื่อยืนยันว่า node ที่เชื่อว่าตัวเองเป็น leader ยัง up-to-date อยู่จริง linearizable read ใน etcd ทำงานแบบนี้ เป็นต้น

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

Pros and cons of consensus (ข้อดีข้อเสียของ consensus)

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

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

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

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

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

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

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

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

coordination service ถูกออกแบบตามแบบ Chubby lock service ของ Google [ 19 , 60 ] โดยรวม consensus algorithm เข้ากับฟีเจอร์อื่นอีกหลายอย่างที่กลายเป็นว่ามีประโยชน์เป็นพิเศษเวลาสร้างระบบกระจาย:

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

เราเห็นไปแล้วว่าระบบ consensus implement CAS แบบ atomic ที่ทนต่อ fault ได้อย่างไร coordination service อาศัยแนวทางนี้ implement lock และ lease ถ้าหลาย node พยายามขอ lease เดียวกันพร้อมกัน จะมีเพียงตัวเดียวที่สำเร็จ

Support for fencing (รองรับ fencing)

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

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

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

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

client ขอให้ coordination service ส่ง notification ให้เมื่อ key บางตัวเปลี่ยนได้ ทำให้ client รู้ได้ว่า client อื่นเข้าร่วม cluster เมื่อไหร่ (จากค่าที่มันเขียนลงใน coordination service) หรือ client อื่นล้มเหลวเมื่อไหร่ (เพราะ session หมดเวลาและ ephemeral node ของมันหายไป) เป็นต้น notification เหล่านี้ช่วยให้ client ไม่ต้อง poll service บ่อย ๆ เพื่อดูว่ามีอะไรเปลี่ยน

failure detection และ change notification ไม่ต้องใช้ consensus แต่มีประโยชน์ต่อการประสานงานแบบกระจาย ควบคู่กับ atomic operation และ fencing ที่ต้องใช้ consensus

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

แอปพลิเคชันและโครงสร้างพื้นฐานมักมี configuration parameter เช่น timeout, ขนาดของ thread pool และอื่น ๆ บางครั้งมีการใช้ coordination service เก็บข้อมูล configuration เหล่านี้ในรูป key-value pair โดย process จะโหลดค่าล่าสุดตอนเริ่มทำงานและ subscribe เพื่อรับ notification เมื่อมีการเปลี่ยนแปลง เมื่อ configuration เปลี่ยน process จะเริ่มใช้ค่าใหม่ทันที หรือ restart ตัวเองเพื่อโหลดการเปลี่ยนแปลงล่าสุดก็ได้

การจัดการ configuration ไม่ต้องใช้ส่วน consensus ของ coordination service แต่ถ้ารัน service นี้อยู่แล้ว ก็สะดวกที่จะใช้มันและพึ่งพาฟีเจอร์ notification ของมัน อีกทางเลือกคือให้ process poll หาการอัปเดต configuration จากไฟล์หรือ URL เป็นระยะ ซึ่งไม่ต้องมี service เฉพาะทาง

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

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

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

งานเหล่านี้ทำได้โดยใช้ atomic operation, ephemeral node และ notification ของ coordination service อย่างเหมาะสม ถ้าทำถูกต้อง แนวทางนี้ช่วยให้แอปพลิเคชันกู้คืนจาก fault ได้เองโดยไม่ต้องให้คนเข้ามาแทรกแซง ซึ่งไม่ง่าย แม้จะมีไลบรารีอย่าง Apache Curator ที่เกิดขึ้นมาเพื่อให้เครื่องมือระดับสูงบน ZooKeeper client API—แต่มัน แต่ก็ยังดีกว่าการพยายาม implement consensus algorithm ที่ต้องใช้ขึ้นเองตั้งแต่ต้นมาก ซึ่งเสี่ยงที่จะมีบั๊กสูง

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

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

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

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

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

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

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

Summary (สรุป)

ในบทนี้เราพิจารณา strong consistency ในระบบที่ทนต่อ fault ว่าคืออะไรและทำได้อย่างไร เราดู linearizability อย่างลึก ซึ่งเป็นการนิยาม strong consistency ที่นิยมใช้ โดยรับประกันว่าข้อมูลที่ replicate ไว้จะดูราวกับมีเพียงชุดเดียว และทุก operation กับข้อมูลนั้นเป็น atomic เราเห็นว่า linearizability มีประโยชน์ถ้าต้องการให้ข้อมูลบางอย่าง up-to-date ตอนอ่าน หรือต้องแก้ race condition (เช่น เมื่อหลาย node พยายามทำสิ่งเดียวกันพร้อมกัน เช่น สร้างไฟล์ชื่อเดียวกัน)

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

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

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

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

Linearizable CAS operation

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

Locks and leases

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

Uniqueness constraints

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

Shared logs

เมื่อหลาย node ต้องการ append entry ลง log พร้อมกัน log จะ ตัดสินใจ ว่าจะ append ตามลำดับใด shared log ถูก implement ด้วย total order broadcast protocol

Atomic transaction commit

database node ที่เกี่ยวข้องกับ distributed transaction ทั้งหมดต้อง ตัดสินใจ ไปในทางเดียวกันว่าจะ commit หรือ abort transaction

Linearizable fetch-and-add operation

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

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

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

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

coordination service อย่าง ZooKeeper และ etcd ก็สร้างบน consensus algorithm เช่นกัน โดยให้ lock, lease, failure detection และ change notification ซึ่งมีประโยชน์ต่อการจัดการ state ของแอปพลิเคชันแบบกระจาย ถ้าคุณพบว่าต้องทำสิ่งใดสิ่งหนึ่งที่ลดรูปเป็น consensus ได้ และต้องการให้ทนต่อ fault แนะนำให้ใช้ coordination service มันไม่ได้รับประกันว่าคุณจะทำถูกต้อง แต่น่าจะช่วยได้

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

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