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

Douglas Adams, ส่วนใหญ่ก็ไม่เป็นอันตราย (1992)

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

• เพื่อเก็บข้อมูลให้อยู่ใกล้ผู้ใช้ตามภูมิศาสตร์ (และลดความหน่วงในการเข้าถึง)

• เพื่อให้ระบบทำงานต่อได้แม้บางส่วนล้มเหลว (ทำให้ availability และความคงทนของข้อมูลสูงขึ้น)

• เพื่อเพิ่มจำนวนเครื่องที่รับ read query ได้ (ทำให้ read throughput สูงขึ้น)

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

ถ้าข้อมูลที่คุณจำลองไม่เปลี่ยนแปลงตามกาลเวลา การจำลองก็ง่าย แค่คัดลอกข้อมูลไปยังทุก node ครั้งเดียวก็เสร็จ ความยากทั้งหมดของการจำลองข้อมูลอยู่ที่การจัดการ การเปลี่ยนแปลง ของข้อมูลที่ถูกจำลอง และนั่นคือสิ่งที่บทนี้พูดถึง เราจะพูดถึงอัลกอริทึมสามตระกูลสำหรับการจำลองการเปลี่ยนแปลงระหว่าง nodes: single-leader, multi-leader, และ leaderless replication ฐานข้อมูลแบบกระจายเกือบทั้งหมดใช้หนึ่งในสามวิธีนี้ แต่ละวิธีมีข้อดีข้อเสียที่เราจะดูอย่างละเอียด

การทำ replication มี trade-off ให้ต้องคิดหลายข้อ เช่น จะใช้ synchronous หรือ asynchronous replication และจะรับมือกับ replica ที่ล้มเหลวอย่างไร ซึ่งมักเป็น configuration option ของฐานข้อมูล แม้รายละเอียดจะต่างกันไปในแต่ละฐานข้อมูล แต่หลักการทั่วไปก็คล้ายกันในหลาย implementation บทนี้จะอธิบายผลของแต่ละตัวเลือก

การจำลองฐานข้อมูลเป็นหัวข้อเก่าแก่ หลักการไม่ได้เปลี่ยนแปลงมากนักตั้งแต่ถูกศึกษาครั้งแรกในยุค 1970 [ 1 ] เพราะข้อจำกัดพื้นฐานของเครือข่ายยังคงเหมือนเดิม อย่างไรก็ตาม แนวคิดอย่าง eventual consistency ยังคงสร้างความสับสน ในหัวข้อ "ปัญหาจาก Replication Lag" เราจะอธิบาย eventual consistency ให้ชัดขึ้น และพูดถึงหลักประกันอย่าง read-your-writes และ monotonic reads

Backups and Replication (Backup และการจำลองข้อมูล)

คุณอาจสงสัยว่ายังจำเป็นต้องมี backups หรือไม่ถ้ามี replication คำตอบคือใช่ เพราะทั้งสองมีวัตถุประสงค์ต่างกัน: replicas จะสะท้อน writes จาก node หนึ่งไปยัง nodes อื่นๆ อย่างรวดเร็ว แต่ backups จะเก็บ snapshot เก่าของข้อมูลเพื่อให้คุณย้อนเวลากลับไปได้ ถ้าคุณลบข้อมูลบางอย่างโดยไม่ตั้งใจ replication ไม่ช่วยเพราะการลบจะถูกกระจายไปยัง replicas เช่นกัน คุณต้องมี backup ถ้าต้องการกู้คืนข้อมูลที่ถูกลบ

ในความเป็นจริง replication และ backups มักเสริมซึ่งกันและกัน Backups บางครั้งเป็นส่วนหนึ่งของกระบวนการตั้งค่า replication ดังที่เราจะเห็นในหัวข้อ "การตั้งค่า Follower ใหม่" ในทางกลับกัน การเก็บถาวร replication logs ก็สามารถเป็นส่วนหนึ่งของกระบวนการ backup ได้

ฐานข้อมูลบางตัวเก็บ immutable snapshot ของสถานะในอดีตไว้ภายในเอง ซึ่งทำหน้าที่เป็น backup ในตัว อย่างไรก็ตาม นี่หมายถึงการเก็บข้อมูลเวอร์ชันเก่าไว้บน storage เดียวกับสถานะปัจจุบัน ถ้าคุณมีข้อมูลจำนวนมาก การเก็บ backups ของข้อมูลเก่าไว้ใน object store ที่ถูกปรับให้เหมาะสมสำหรับข้อมูลที่เข้าถึงไม่บ่อย และเก็บเฉพาะสถานะปัจจุบันของฐานข้อมูลในพื้นที่จัดเก็บหลักอาจมีต้นทุนถูกกว่า

Single-Leader Replication (การจำลองแบบผู้นำเดียว)

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

ทุก write ไปยังฐานข้อมูลต้องถูกประมวลผลโดยทุก replica มิฉะนั้น replicas จะไม่มีข้อมูลที่เหมือนกันอีกต่อไป วิธีแก้ปัญหาที่พบมากที่สุดเรียกว่า leader-based, primary-backup, หรือ active/passive replication มันทำงานดังนี้ (ดู Figure 6-1):

1. replica ตัวหนึ่งถูกกำหนดให้เป็น leader (หรือเรียกอีกอย่างว่า primary หรือ source [ 2 ]) เมื่อ client ต้องการเขียนข้อมูล ต้องส่ง request ไปที่ leader ซึ่งจะเขียนข้อมูลใหม่ลง storage ของตัวเองก่อน

2. replicas อื่นๆ เรียกว่า followers (หรือ read replicas, secondaries, หรือ hot standbys) เมื่อใดก็ตามที่ leader เขียนข้อมูลใหม่ลงในพื้นที่จัดเก็บของตน มันจะส่งการเปลี่ยนแปลงข้อมูลนั้นไปยัง followers ทั้งหมดโดยเป็นส่วนหนึ่งของ replication log หรือ change stream แต่ละ follower จะนำ log จาก leader ไปอัปเดตสำเนาฐานข้อมูลในเครื่องตัวเอง โดย apply write ทั้งหมดตามลำดับเดียวกับที่ leader ประมวลผล

3. เมื่อ client ต้องการอ่านข้อมูล จะ query จาก leader หรือ follower ตัวไหนก็ได้ แต่มีเพียง leader เท่านั้นที่รับ write (followers เป็นแบบอ่านอย่างเดียวจากมุมมองของ client)

Figure 6-1. Single-leader replication ส่ง write ทั้งหมดไปที่ leader ที่กำหนดไว้ แล้ว leader ส่ง stream ของการเปลี่ยนแปลงต่อไปให้ follower replica

ถ้าฐานข้อมูลถูก sharded (ดู บทที่ 7) แต่ละ shard จะมี leader หนึ่งตัว shard ต่างกันอาจมี leader อยู่คนละ node กัน แต่ละ shard ก็ยังต้องมี leader node หนึ่งตัวอยู่ดี ในหัวข้อ "การจำลองแบบ Multi-Leader" เราจะดูโมเดลทางเลือกที่ shard เดียวกันมี leader หลายตัวพร้อมกันได้

Single-leader replication ถูกใช้กันอย่างแพร่หลาย และเป็นฟีเจอร์ในตัวของ relational database หลายตัว เช่น PostgreSQL, MySQL, Oracle Data Guard [ 3 ], และ SQL Server's Always On availability groups [ 4 ] และยังใช้ใน document database บางตัว (เช่น MongoDB และ DynamoDB [ 5 ]), message brokers อย่าง Kafka, replicated block devices อย่าง DRBD, และ network filesystems บางตัว อัลกอริทึม consensus หลายตัว—เช่น Raft ที่ใช้สำหรับ replication ใน CockroachDB [ 6 ], TiDB [ 7 ], etcd, และ RabbitMQ quorum queues—ก็ใช้ single leader เช่นกัน และจะเลือก leader ใหม่โดยอัตโนมัติถ้าตัวเก่าล้มเหลว (เราจะพูดถึง consensus ในรายละเอียดเพิ่มเติมใน บทที่ 10)

หมายเหตุ

ในเอกสารเก่าคุณอาจเห็นคำว่า master--slave replication ซึ่งหมายถึงสิ่งเดียวกับ leader-based replication แต่ควรหลีกเลี่ยงคำนี้เนื่องจากถูกมองว่าไม่เหมาะสมอย่างกว้างขวาง [ 8 ]

Synchronous Versus Asynchronous Replication (การจำลองแบบซิงโครนัสกับอะซิงโครนัส)

รายละเอียดสำคัญของระบบที่ทำ replication คือจะ replicate แบบ synchronous หรือ asynchronous (ในฐานข้อมูลเชิงสัมพันธ์ มักเป็นตัวเลือกที่กำหนดค่าได้ ส่วนระบบอื่นมักตายตัวอยู่แล้วว่าเป็นแบบใดแบบหนึ่ง)

ลองดูสิ่งที่เกิดขึ้นใน Figure 6-1 ซึ่งผู้ใช้เว็บไซต์กำลังอัปเดตรูปโปรไฟล์ ขณะหนึ่ง client ส่ง request อัปเดตไปที่ leader และไม่นานหลังจากนั้น leader ก็ได้รับ request จากนั้น leader จะส่งต่อการเปลี่ยนแปลงข้อมูลไปยัง followers และแจ้งให้ client ทราบว่าการอัปเดตสำเร็จ Figure 6-2 แสดงลำดับเวลาที่เป็นไปได้แบบหนึ่ง

Figure 6-2. การจำลองแบบ Leader-based ที่มี follower แบบซิงโครนัสหนึ่งตัวและแบบอะซิงโครนัสหนึ่งตัว

ในตัวอย่างนี้ การจำลองไปยัง follower 1 เป็นแบบ synchronous: leader จะรอจน follower 1 ยืนยันว่าได้รับ write แล้ว จึงรายงานความสำเร็จให้ผู้ใช้ทราบ และทำให้ write นั้นปรากฏแก่ client อื่น การจำลองไปยัง follower 2 เป็นแบบ asynchronous (หรือ nonblocking): leader ส่ง message ไปแล้วไม่ต้องรอ response จาก follower

แผนภาพแสดงว่ากว่า follower 2 จะประมวลผล message ก็ใช้เวลาไปพอสมควร โดยปกติแล้วการจำลองค่อนข้างรวดเร็ว ระบบฐานข้อมูลส่วนใหญ่ใช้เวลาไม่ถึงวินาทีในการส่งการเปลี่ยนแปลงไปยัง followers อย่างไรก็ตาม ไม่มีการรับประกันว่าจะใช้เวลานานเท่าใด ในบางสถานการณ์ followers อาจตามหลัง leader หลายนาทีหรือมากกว่า—เช่น ถ้า follower กำลังกู้คืนจากความล้มเหลว ถ้าระบบทำงานใกล้ขีดความสามารถสูงสุด หรือถ้ามีปัญหาเครือข่ายระหว่าง nodes

ข้อดีของ synchronous replication คือรับประกันได้ว่า follower มีข้อมูลล่าสุดที่ตรงกับ leader ถ้า leader ล้มเหลวกะทันหัน เรามั่นใจได้ว่าข้อมูลยังคงพร้อมใช้งานบน follower ข้อเสียคือถ้า synchronous follower ไม่ตอบสนอง (เพราะมันล่ม หรือเพราะมีปัญหาเครือข่าย หรือด้วยเหตุผลอื่นใด) ก็จะประมวลผล write ไม่ได้ และ leader ต้อง block write ทั้งหมดไว้จนกว่า synchronous replica จะพร้อมใช้งานอีกครั้ง

ด้วยเหตุนี้ การให้ follower ทุกตัวเป็นแบบ synchronous จึงใช้งานจริงไม่ได้ เพราะแค่ node ใด node หนึ่งหยุดทำงานก็ทำให้ทั้งระบบชะงัก ในทางปฏิบัติ ถ้าฐานข้อมูลเสนอการจำลองแบบ synchronous ก็มักหมายความว่า หนึ่ง ใน followers เป็นแบบ synchronous และตัวอื่นๆ เป็นแบบ asynchronous ถ้า synchronous follower ไม่พร้อมใช้งานหรือช้า ตัวหนึ่งใน asynchronous followers จะถูกเปลี่ยนเป็นแบบ synchronous วิธีนี้ทำให้มั่นใจได้ว่ามีข้อมูลล่าสุดอยู่บนอย่างน้อยสอง node: leader และ synchronous follower หนึ่งตัว การกำหนดค่านี้บางครั้งเรียกว่า semisynchronous

ในบางระบบ replicas ส่วนใหญ่ (เช่น สามในห้า รวมถึง leader) จะถูกอัปเดตแบบ synchronous และส่วนน้อยที่เหลือเป็นแบบ asynchronous นี่คือตัวอย่างของ quorum ซึ่งเราจะพูดถึงเพิ่มเติมในหัวข้อ "การใช้ Quorum สำหรับการอ่านและเขียน" Majority quorums มักใช้ในระบบ eventual consistency หรือระบบที่ใช้ consensus protocol สำหรับการเลือก leader อัตโนมัติ เราจะกลับมาที่ระบบเหล่านี้ใน บทที่ 10

บางครั้ง leader-based replication ถูกตั้งค่าให้เป็น asynchronous ทั้งหมด ในกรณีนี้ ถ้า leader ล้มเหลวและไม่สามารถกู้คืนได้ writes ที่ยังไม่ถูกจำลองไปยัง followers จะหายไป ซึ่งหมายความว่า write ไม่ได้รับประกันความคงทน แม้ client จะได้รับการยืนยันไปแล้ว อย่างไรก็ตาม การตั้งค่าแบบ asynchronous ทั้งหมดมีข้อดีคือ leader สามารถประมวลผล writes ต่อไปได้ แม้ว่า followers ทั้งหมดจะตามหลังอยู่

การยอมลดความคงทนของข้อมูลอาจฟังดูเป็น trade-off ที่ไม่ดี แต่ asynchronous replication ก็ยังถูกใช้อย่างแพร่หลาย โดยเฉพาะถ้ามี followers จำนวนมากหรือกระจายตามภูมิศาสตร์ [ 9 ] เราจะกลับมาที่ประเด็นนี้ในหัวข้อ "ปัญหาจาก Replication Lag"

Setting Up New Followers (การตั้งค่า Follower ใหม่)

ในบางครั้ง คุณต้องตั้งค่า followers ใหม่—อาจเพื่อเพิ่มจำนวน replicas หรือแทนที่ nodes ที่ล้มเหลว คุณจะมั่นใจได้อย่างไรว่า follower ใหม่มีสำเนาข้อมูลที่ถูกต้องของ leader?

การคัดลอกไฟล์ข้อมูลจาก node หนึ่งไปยังอีก node หนึ่งโดยทั่วไปแล้วไม่เพียงพอ Clients กำลังเขียนไปยังฐานข้อมูลตลอดเวลา และข้อมูลก็เปลี่ยนแปลงอยู่เสมอ การคัดลอกไฟล์ธรรมดาจึงได้ข้อมูลแต่ละส่วนของฐานข้อมูลมาจากคนละช่วงเวลา ผลลัพธ์ที่ได้อาจไม่สมเหตุสมผล

คุณทำให้ไฟล์บนดิสก์สอดคล้องกันได้ด้วยการ lock ฐานข้อมูล (ไม่ให้เขียนได้) แต่วิธีนี้ขัดกับเป้าหมาย high availability ของเรา โชคดีที่การตั้งค่า follower โดยปกติทำได้โดยไม่ต้อง downtime ในเชิงแนวคิด กระบวนการมีดังนี้:

1. ถ่าย snapshot ที่สอดคล้องกันของฐานข้อมูล leader ณ จุดเวลาใดเวลาหนึ่ง—ถ้าเป็นไปได้ โดยไม่ต้องล็อกฐานข้อมูลทั้งหมด ฐานข้อมูลส่วนใหญ่มีฟีเจอร์นี้ เพราะจำเป็นสำหรับ backups เช่นกัน ในบางกรณีต้องใช้เครื่องมือของ third party เช่น Percona XtraBackup สำหรับ MySQL

2. คัดลอก snapshot ไปยัง follower node ใหม่

3. follower เชื่อมต่อกับ leader และขอการเปลี่ยนแปลงข้อมูลทั้งหมดที่เกิดขึ้นตั้งแต่ถ่าย snapshot snapshot ต้องผูกกับตำแหน่งที่แน่นอนใน replication log ของ leader ตำแหน่งนั้นมีชื่อเรียกต่างๆ กัน—ตัวอย่างเช่น PostgreSQL เรียกว่า log sequence number; MySQL มีสอง กลไกคือ binlog coordinates และ global transaction identifiers (GTIDs)

4. เมื่อ follower ประมวลผลการเปลี่ยนแปลงที่ค้างอยู่ตั้งแต่ snapshot จนหมดแล้ว เราเรียกว่ามัน ตามทันแล้ว จากนั้นมันก็ประมวลผลการเปลี่ยนแปลงจาก leader ต่อไปได้ทันทีที่เกิดขึ้น

ขั้นตอนจริงในการตั้งค่า follower ต่างกันมากในแต่ละฐานข้อมูล บางระบบทำให้อัตโนมัติทั้งหมด แต่บางระบบเป็น workflow หลายขั้นตอนที่ค่อนข้างซับซ้อน และผู้ดูแลระบบต้องทำเอง

คุณยัง archive replication log ไปไว้ใน object store ได้ พร้อมกับ snapshot ของฐานข้อมูลทั้งหมดเป็นระยะๆ นี่เป็นวิธีที่ดีในการ implement database backups และ disaster recovery และคุณสามารถทำขั้นตอนที่ 1 และ 2 ของการตั้งค่า follower ใหม่โดยดาวน์โหลดไฟล์เหล่านั้นจาก object store ตัวอย่างเช่น WAL-G ทำสิ่งนี้สำหรับ PostgreSQL, MySQL, และ SQL Server ส่วน Litestream ทำสิ่งเดียวกันให้ SQLite

Databases Backed by Object Storage (ฐานข้อมูลที่ใช้ Object Storage)

Object storage ใช้ได้มากกว่าแค่ archive ข้อมูล ฐานข้อมูลจำนวนมากเริ่มใช้ object store เช่น Amazon S3, Google Cloud Storage, และ Azure Blob Storage เพื่อ serve ข้อมูลให้ query แบบ real-time การเก็บข้อมูลฐานข้อมูลใน object storage มีประโยชน์มากมาย:

• Object storage มีราคาถูกเมื่อเทียบกับตัวเลือกพื้นที่จัดเก็บคลาวด์อื่นๆ ทำให้ cloud database เก็บข้อมูลที่ถูก query น้อยไว้บน storage ที่ถูกกว่าแต่ latency สูงกว่า ส่วน working set ก็ serve จากหน่วยความจำ, SSD และ NVMe

• Object store ทำ replication แบบ multi-zone, dual-region หรือ multi-region ให้ พร้อมการรับประกันความคงทนที่สูงมาก ฐานข้อมูลจึงเลี่ยงค่า network ข้าม zone ได้ด้วย

• ฐานข้อมูลสามารถใช้ฟีเจอร์ conditional write ของ object store (โดยพื้นฐานแล้วก็คือการดำเนินการ compare-and-set หรือ CAS) เพื่อ implement transaction และ leadership election [ 10, 11 ]

• การเก็บข้อมูลจากฐานข้อมูลหลายตัวใน object store เดียวกันสามารถทำให้การรวมข้อมูลง่ายขึ้น (ดูหัวข้อ "Cloud Data Warehouses") โดยเฉพาะเมื่อใช้รูปแบบเปิดเช่น Parquet และ Iceberg

ประโยชน์เหล่านี้ช่วยให้สถาปัตยกรรมฐานข้อมูลง่ายลงมาก เพราะย้ายหน้าที่เรื่อง transaction, leadership election และ replication ไปให้ object storage

อย่างไรก็ตาม ระบบที่ใช้ object storage ทำ replication ก็ต้องแลกกับข้อเสียบางอย่าง โดยเฉพาะ object store มี read/write latency สูงกว่า local disk หรือ virtual block device เช่น Amazon EBS มาก cloud provider หลายรายยังคิดค่าบริการต่อ API call ระบบจึงต้อง batch read และ write เพื่อลดต้นทุน ซึ่ง batching แบบนี้ยิ่งเพิ่ม latency นอกจากนี้ object มักเป็น immutable การเขียนแบบ random ลงใน object ขนาดใหญ่จึงสิ้นเปลืองทรัพยากรมาก สุดท้าย object store จำนวนมากไม่มี filesystem interface มาตรฐาน ระบบที่ไม่ได้ผสานกับ object storage โดยตรงจึงใช้ประโยชน์จากมันไม่ได้ interface อย่าง filesystem in userspace (FUSE) ช่วยให้ operator mount bucket ของ object store เป็น filesystem ที่แอปพลิเคชันใช้ได้โดยไม่ต้องรู้ว่าข้อมูลถูกเก็บบน object storage อย่างไรก็ตาม FUSE interface จำนวนมากยังขาดฟีเจอร์ POSIX เช่น nonsequential writes หรือ symlinks ซึ่งระบบอาจพึ่งพา

แต่ละระบบรับมือกับข้อเสียเหล่านี้ต่างกัน บางระบบใช้สถาปัตยกรรม tiered storage ที่วางข้อมูลที่เข้าถึงน้อยไว้บน object storage ส่วนข้อมูลใหม่หรือที่เข้าถึงบ่อยจะเก็บไว้บนอุปกรณ์ที่เร็วกว่า เช่น SSD หรือ NVMe หรือแม้แต่ในหน่วยความจำ ระบบอื่นใช้ object storage เป็นชั้นเก็บข้อมูลหลัก แต่ใช้ระบบ storage ที่ latency ต่ำแยกต่างหาก (เช่น Amazon EBS หรือ Neon's Safekeepers [ 12 ]) เพื่อเก็บ WAL เมื่อไม่นานมานี้ บางระบบไปไกลกว่านั้นด้วยการใช้สถาปัตยกรรม zero-disk (ZDA) มาใช้ ระบบที่ใช้ ZDA เก็บข้อมูลทั้งหมดไว้ใน object storage และใช้ดิสก์กับหน่วยความจำเพื่อ caching เท่านั้น ทำให้ node ไม่ต้องเก็บ state ถาวร ซึ่งช่วยลดความยุ่งยากในการ operate ระบบ WarpStream, Confluent Freight, Buf's Bufstream, และ Redpanda Serverless ล้วนเป็นระบบที่เข้ากันได้กับ Kafka ซึ่งสร้างด้วยสถาปัตยกรรม zero-disk cloud data warehouse สมัยใหม่เกือบทุกตัวก็ใช้สถาปัตยกรรมแบบนี้เช่นกัน เช่นเดียวกับ Turbopuffer (vector search engine) และ SlateDB (cloud native LSM storage engine)

Handling Node Outages (การจัดการเมื่อ Node หยุดทำงาน)

node ใดๆ ในระบบสามารถหยุดทำงานได้ อาจเกิดจากความผิดพลาดโดยไม่คาดคิด หรือจากการบำรุงรักษาตามแผน (เช่น การ reboot เครื่องเพื่อลง security patch ของ kernel) การ reboot แต่ละ node ได้โดยไม่ต้อง downtime เป็นข้อได้เปรียบใหญ่ในการ operate และบำรุงรักษา เป้าหมายของเราจึงเป็นทำให้ระบบโดยรวมทำงานต่อได้แม้บาง node จะล้มเหลว และให้ผลกระทบจาก node ที่หยุดทำงานน้อยที่สุด

คุณจะบรรลุความพร้อมใช้งานสูงด้วย leader-based replication ได้อย่างไร?

Follower failure: Catch-up recovery (Follower ล้มเหลว: การกู้คืนแบบตามทัน)

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

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

leader สามารถลบ log ของ writes หลังจาก followers ทั้งหมดยืนยันว่าได้ประมวลผลแล้ว แต่ถ้า follower ไม่พร้อมใช้งานเป็นเวลานาน leader ต้องเผชิญกับทางเลือก: เก็บ log ไว้จนกว่า follower จะกู้คืนและตามทัน (เสี่ยงต่อการเต็มดิสก์บน leader) หรือลบ log ที่ follower ที่ใช้งานไม่ได้ยังไม่ได้รับ (ในกรณีนี้ follower จะไม่สามารถกู้คืนจาก log ได้และต้องกู้คืนจาก backup เมื่อกลับมาออนไลน์)

Leader failure: Failover (Leader ล้มเหลว: การ Failover)

การรับมือเมื่อ leader ล้มเหลวยุ่งยากกว่านั้น ต้องเลือก follower ตัวหนึ่งขึ้นเป็น leader ใหม่ ต้องตั้งค่า client ใหม่ให้ส่ง write ไปที่ leader ใหม่ และ follower ตัวอื่นต้องเริ่มรับการเปลี่ยนแปลงข้อมูลจาก leader ใหม่ กระบวนการนี้เรียกว่า failover

Failover ทำได้ทั้งแบบ manual (ผู้ดูแลระบบได้รับแจ้งว่า leader ล้มเหลว แล้วทำขั้นตอนที่จำเป็นเพื่อตั้ง leader ใหม่) และแบบอัตโนมัติ ซึ่งมักมีขั้นตอนดังนี้:

1. การตรวจสอบว่า leader ล้มเหลว มีหลายอย่างที่ผิดพลาดได้ ทั้งเครื่องล่ม ไฟดับ ปัญหาเครือข่าย และอื่นๆ และไม่มีวิธีที่แน่นอนในการตรวจจับว่าเกิดอะไรขึ้น ระบบส่วนใหญ่จึงใช้ timeout โดย node จะส่ง message หากันอยู่บ่อยๆ และถ้า node ไหนไม่ตอบสนองภายในช่วงเวลาหนึ่ง เช่น 30 วินาที ก็ถือว่าตายแล้ว (ถ้า leader ถูกนำลงโดยตั้งใจเพื่อบำรุงรักษาตามแผน กรณีนี้ไม่เกี่ยวข้อง เพราะ leader trigger safe handoff ก่อนปิดเครื่องได้)

2. การเลือก leader ใหม่ ทำได้โดยการเลือกตั้ง (replica ที่เหลืออยู่ลงคะแนนเลือก leader ด้วยเสียงข้างมาก) หรือให้ controller node ที่กำหนดไว้ล่วงหน้าเป็นผู้แต่งตั้ง leader ใหม่ [ 13 ] ผู้สมัครที่ดีที่สุดมักเป็น replica ที่มีข้อมูลจาก leader เก่าล่าสุดที่สุด (เพื่อลดการสูญเสียข้อมูล) การทำให้ทุก node เห็นพ้องกันว่าใครคือ leader ใหม่เป็นปัญหา consensus ซึ่งอธิบายละเอียดใน บทที่ 10

3. การกำหนดค่าระบบใหม่ให้ใช้ leader ใหม่ client ต้องส่ง write request ไปที่ leader ใหม่ (เราพูดถึงเรื่องนี้ในหัวข้อ "การกำหนดเส้นทางคำขอ") ถ้า leader เก่ากลับมา มันอาจยังเชื่อว่าตัวเองเป็น leader โดยไม่รู้ว่า replica อื่นปลดมันลงไปแล้ว ระบบต้องทำให้แน่ใจว่า leader เก่ากลายเป็น follower และยอมรับ leader ใหม่

Failover มีจุดที่ผิดพลาดได้มากมาย:

• ถ้าใช้ asynchronous replication leader ใหม่อาจยังไม่ได้รับ write ทั้งหมดจาก leader เก่าก่อนที่มันจะล้มเหลว ถ้า leader เก่ากลับมาเข้าร่วม cluster หลังจากเลือก leader ใหม่ไปแล้ว write เหล่านั้นควรเป็นอย่างไร? ในระหว่างนั้น leader ใหม่อาจได้รับ write ที่ขัดแย้งกันด้วย วิธีแก้ที่พบบ่อยที่สุดคือทิ้ง write ของ leader เก่าที่ยังไม่ได้ replicate ซึ่งหมายความว่า write ที่คุณเชื่อว่า commit แล้วอาจไม่คงทนในที่สุด

• การทิ้ง write อันตรายเป็นพิเศษเมื่อมีระบบ storage อื่นนอกจากฐานข้อมูลที่ต้องสอดคล้องกับเนื้อหาในฐานข้อมูล ตัวอย่างเช่น ในเหตุการณ์หนึ่งที่ GitHub [ 14 ] MySQL follower ที่ข้อมูลตามหลังอยู่ถูกเลื่อนขึ้นเป็น leader ฐานข้อมูลนี้ใช้ counter แบบ autoincrement กำหนด primary key ให้แถวใหม่ แต่เพราะ counter ของ leader ใหม่ตามหลัง leader เก่า มันจึงนำ primary key บางตัวที่ leader เก่าเคยแจกไปแล้วมาใช้ซ้ำ ขณะที่ primary key เหล่านี้ถูกใช้ใน Redis store ด้วย การใช้ซ้ำจึงทำให้ MySQL กับ Redis ไม่สอดคล้องกัน และทำให้ข้อมูลส่วนตัวบางส่วนถูกเปิดเผยแก่ผู้ใช้ผิดคน

• ในสถานการณ์ที่เกิดความผิดพลาดบางแบบ (ดู บทที่ 9) สอง node อาจเชื่อว่าตัวเองเป็น leader สถานการณ์นี้เรียกว่า split brain และเป็นอันตราย ถ้า leader ทั้งสองรับ write และไม่มีกระบวนการแก้ conflict (ดูหัวข้อ "การจำลองแบบ Multi-Leader") ข้อมูลมีแนวโน้มจะสูญหายหรือเสียหาย เพื่อความปลอดภัย บางระบบจึงมีกลไกปิด node หนึ่งทิ้งเมื่อตรวจพบว่ามี leader สองตัว แต่ถ้ากลไกนี้ออกแบบไม่ดี ก็อาจลงเอยด้วยการปิดทั้งสอง node [ 15 ] ยิ่งไปกว่านั้น กว่าจะตรวจพบ split brain และปิด node เก่า ก็อาจสายเกินไปและข้อมูลเสียหายไปแล้ว

• การเลือก timeout ที่เหมาะสมก่อนประกาศว่า leader ตายแล้วนั้นยุ่งยาก ถ้า timeout ยาวขึ้น เวลาที่ใช้กู้คืนเมื่อ leader ล้มเหลวก็ยาวขึ้นตาม แต่ถ้าสั้นเกินไป ก็อาจเกิด failover ที่ไม่จำเป็น เช่น โหลดพุ่งชั่วคราวอาจทำให้ response time ของ node เกิน timeout หรือเครือข่ายสะดุดจนแพ็กเก็ตล่าช้า ถ้าระบบกำลังรับโหลดสูงหรือมีปัญหาเครือข่ายอยู่แล้ว failover ที่ไม่จำเป็นมักทำให้สถานการณ์แย่ลง ไม่ใช่ดีขึ้น

การป้องกัน split brain ด้วยการจำกัดหรือปิด leader เก่าเรียกว่า fencing ซึ่งเราจะอธิบายละเอียดขึ้นในหัวข้อ "ล็อคแบบกระจายและสัญญาเช่า" ปัญหาเหล่านี้ไม่มีวิธีแก้ง่ายๆ ทีม operations บางทีมจึงเลือกทำ failover เองด้วยมือ แม้ซอฟต์แวร์จะรองรับ failover อัตโนมัติก็ตาม

สิ่งสำคัญที่สุดใน failover คือต้องเลือก follower ที่ข้อมูลล่าสุดมาเป็น leader ใหม่ ถ้าใช้ synchronous หรือ semisynchronous replication ก็คือ follower ที่ leader เก่ารอให้ตอบรับก่อนยืนยัน write ส่วน asynchronous replication ให้เลือก follower ที่มี log sequence number สูงที่สุด วิธีนี้ช่วยลดข้อมูลที่สูญเสียระหว่าง failover การเสีย write ไปแค่เสี้ยววินาทีอาจยังพอรับได้ แต่ถ้าเลือก follower ที่ตามหลังอยู่หลายวันอาจเป็นหายนะ

ประเด็นเหล่านี้ ทั้ง node failure, เครือข่ายที่ไว้ใจไม่ได้ และ trade-off ระหว่าง replica consistency, durability, availability และ latency ล้วนเป็นปัญหาพื้นฐานของระบบกระจาย บทที่ 9 และ 10 จะลงลึกเรื่องเหล่านี้มากขึ้น

Implementation of Replication Logs (การนำ Replication Logs ไปใช้)

leader-based replication ทำงานอย่างไรเบื้องหลัง? ในทางปฏิบัติมีวิธี replicate หลายแบบ มาดูแต่ละแบบโดยสังเขป

Statement-based replication (การจำลองแบบตามคำสั่ง)

ในกรณีที่ง่ายที่สุด leader จะบันทึกทุก write request (statement) ที่ประมวลผล แล้วส่ง statement log นั้นไปให้ follower สำหรับ relational database นี่หมายความว่าทุก INSERT, UPDATE, หรือ DELETE statement จะถูกส่งต่อไปยัง follower และแต่ละ follower จะ parse และรัน SQL statement นั้นเหมือนกับว่าได้รับจาก client

วิธีนี้อาจฟังดูสมเหตุสมผล แต่ก็พังได้หลายทาง:

• Statement ใดๆ ที่เรียกฟังก์ชัน nondeterministic เช่น NOW เพื่อดึงวันที่และเวลาปัจจุบัน หรือ RAND เพื่อสุ่มตัวเลข มักได้ค่าต่างกันในแต่ละ replica

• ถ้า statement ใช้คอลัมน์แบบ autoincrement หรือขึ้นอยู่กับข้อมูลที่มีอยู่ในฐานข้อมูล (เช่น UPDATE ... WHERE _<เงื่อนไขบางอย่าง>_) statement เหล่านั้นต้องรันในลำดับเดียวกันทุกประการบนทุก replica ไม่เช่นนั้นอาจได้ผลต่างกัน ซึ่งเป็นข้อจำกัดเมื่อมีหลาย transaction ทำงานพร้อมกัน

• Statement ที่มี side effect (เช่น trigger, stored procedure, user-defined function) อาจให้ผลต่างกันในแต่ละ replica เว้นแต่ side effect นั้นจะ deterministic อย่างสมบูรณ์

ปัญหาเหล่านี้แก้ได้ เช่น leader อาจแทนที่การเรียกฟังก์ชัน nondeterministic ด้วยค่าตายตัวตอนบันทึก statement เพื่อให้ follower ทุกตัวได้ค่าเดียวกัน แนวคิดที่ให้รัน deterministic statement ตามลำดับที่แน่นอนนี้คล้ายกับโมเดล event sourcing ที่เราเคยพูดถึงในหัวข้อ "Event Sourcing และ CQRS" วิธีนี้เรียกว่า state machine replication และเราจะพูดถึงทฤษฎีเบื้องหลังในหัวข้อ "การใช้ Shared Logs"

MySQL ก่อนเวอร์ชัน 5.1 ใช้ statement-based replication และบางครั้งก็ยังมีใช้อยู่ทุกวันนี้เพราะค่อนข้างกะทัดรัด แต่โดยค่าเริ่มต้น MySQL จะสลับไปใช้ row-based replication (จะอธิบายต่อไป) ถ้า statement ใดมี nondeterminism VoltDB ใช้ statement-based replication และทำให้ปลอดภัยด้วยการบังคับให้ transaction ต้อง deterministic [ 16 ] อย่างไรก็ตาม การรับประกัน determinism ในทางปฏิบัติทำได้ยาก ฐานข้อมูลจำนวนมากจึงเลือกวิธี replicate แบบอื่น

Write-ahead log shipping (การส่ง Write-ahead Log)

ใน บทที่ 4 เราเห็นแล้วว่า B-tree storage engine ต้องใช้ write-ahead log เพื่อให้ทนต่อความล้มเหลวได้ ทุกการแก้ไขจะถูกเขียนลง WAL ก่อน เพื่อให้กู้ tree กลับสู่สถานะที่สอดคล้องกันได้หลัง crash เนื่องจาก WAL มีข้อมูลครบพอจะกู้ index และ heap กลับสู่สถานะที่สอดคล้องกัน เราจึงใช้ log เดียวกันนี้สร้าง replica บน node อื่นได้ นอกจากเขียน log ลงดิสก์แล้ว leader ยังส่ง log ผ่านเครือข่ายไปให้ follower ด้วย เมื่อ follower ประมวลผล log นี้ ก็จะได้สำเนาไฟล์ที่เหมือนกับบน leader ทุกประการ

วิธีนี้ใช้ใน PostgreSQL และ Oracle เป็นต้น [ 17, 18 ] ข้อเสียหลักคือ log อธิบายข้อมูลในระดับต่ำมาก WAL ระบุรายละเอียดว่า byte ใดใน disk block ใดถูกเปลี่ยน ทำให้ replication ผูกแน่นกับ storage engine ถ้าฐานข้อมูลเปลี่ยนรูปแบบการจัดเก็บระหว่างเวอร์ชัน ก็มักจะรันซอฟต์แวร์ฐานข้อมูลคนละเวอร์ชันบน leader และ follower ไม่ได้

ฟังดูเหมือนรายละเอียด implementation เล็กน้อย แต่ส่งผลต่อการ operate ระบบมาก ถ้า replication protocol ยอมให้ follower รันซอฟต์แวร์เวอร์ชันใหม่กว่า leader ได้ คุณก็อัปเกรดฐานข้อมูลแบบ zero-downtime ได้ โดยอัปเกรด follower ก่อน แล้วทำ failover ให้ node ที่อัปเกรดแล้วขึ้นเป็น leader ใหม่ แต่ถ้า protocol ไม่ยอมให้เวอร์ชันต่างกัน ซึ่งมักเป็นกรณีของ WAL shipping การอัปเกรดแบบนี้ต้องมี downtime

Logical (row-based) log replication (การจำลองแบบ Logical Log แบบ Row-based)

อีกทางเลือกคือใช้ log คนละรูปแบบสำหรับ replication และ storage engine ซึ่งแยก replication log ออกจากรายละเอียดภายในของ storage engine replication log แบบนี้เรียกว่า logical log เพื่อแยกจากการแทนข้อมูลแบบ physical ของ storage engine

logical log ของ relational database มักเป็นลำดับของ record ที่อธิบาย write ลงตารางในระดับแถว:

• สำหรับแถวที่ insert log จะมีค่าของทุกคอลัมน์ในแถวใหม่

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

• สำหรับแถวที่อัปเดต log จะมีข้อมูลมากพอที่จะระบุแถวนั้นได้อย่างไม่ซ้ำ พร้อมค่าใหม่ของทุกคอลัมน์ (หรืออย่างน้อยทุกคอลัมน์ที่ค่าเปลี่ยน)

transaction ที่แก้หลายแถวจะสร้าง log record หลายรายการ ตามด้วย record ที่ระบุว่า transaction ถูก commit แล้ว เมื่อตั้งค่าให้ใช้ row-based replication MySQL จะเก็บ logical replication log แยกต่างหาก เรียกว่า binlog นอกเหนือจาก WAL ส่วน PostgreSQL implement logical replication ด้วยการ decode physical WAL ให้เป็น event insert/update/delete ระดับแถว [ 19 ]

เพราะ logical log แยกจากรายละเอียดภายในของ storage engine จึงรักษา backward compatibility ได้ง่ายกว่า ทำให้ leader และ follower รันซอฟต์แวร์ฐานข้อมูลคนละเวอร์ชันได้ และอัปเกรดเป็นเวอร์ชันใหม่โดยมี downtime น้อยที่สุด [ 20 ]

รูปแบบ logical log ยังให้แอปพลิเคชันภายนอก parse ได้ง่ายกว่า ซึ่งมีประโยชน์ถ้าคุณต้องการส่งเนื้อหาของฐานข้อมูลไปยังระบบภายนอก เช่น data warehouse สำหรับวิเคราะห์แบบ offline หรือระบบเฉพาะทางที่สร้าง index และ cache แบบ custom [ 21 ] เทคนิคนี้เรียกว่า change data capture และเราจะกลับมาพูดถึงใน บทที่ 12

Problems with Replication Lag (ปัญหาจาก Replication Lag)

การ ทนต่อ node ที่ล้มเหลวได้เป็นเพียงเหตุผลเดียวที่ต้องการ replication ดังที่กล่าวไว้ในหัวข้อ "ระบบกระจายเทียบกับระบบโหนดเดียว" เหตุผลอื่นๆ ได้แก่ scalability (รองรับ request ได้มากกว่าที่เครื่องเดียวจะรับไหว) และ latency (วาง replica ให้อยู่ใกล้ผู้ใช้ทางภูมิศาสตร์)

Leader-based replication บังคับให้ write ทั้งหมดผ่าน node เดียว แต่ query แบบอ่านอย่างเดียวส่งไปที่ replica ตัวไหนก็ได้ สำหรับ workload ที่เป็นการอ่านเสียส่วนใหญ่และมี write น้อย (ซึ่งมักเป็นกรณีของบริการออนไลน์) มีทางเลือกที่น่าสนใจคือ สร้าง follower จำนวนมากแล้วกระจาย read request ไปที่ follower เหล่านั้น วิธีนี้ช่วยลดโหลดของ leader และทำให้ read request ถูกรับโดย replica ที่อยู่ใกล้ผู้ใช้ได้

ในสถาปัตยกรรม read-scaling นี้ คุณเพิ่มความสามารถในการรับ request แบบอ่านอย่างเดียวได้ด้วยการเพิ่ม follower อย่างไรก็ตาม วิธีนี้ใช้ได้จริงเฉพาะกับ asynchronous replication ถ้าพยายาม replicate แบบ synchronous ไปยัง follower ทุกตัว แค่ node เดียวล้มหรือเครือข่ายขัดข้องก็ทำให้ทั้งระบบเขียนไม่ได้ และยิ่งมี node มาก โอกาสที่จะมี node ล้มก็ยิ่งสูง การตั้งค่าแบบ synchronous ทั้งหมดจึงไม่น่าเชื่อถืออย่างยิ่ง

น่าเสียดายที่แอปพลิเคชันที่อ่านจาก asynchronous follower อาจเห็นข้อมูลที่ล้าสมัยถ้า follower ตามหลังอยู่ ซึ่งทำให้ฐานข้อมูลดูไม่สอดคล้องกันอย่างเห็นได้ชัด ถ้ารัน query เดียวกันบน leader และ follower ในเวลาเดียวกัน คุณอาจได้ผลต่างกัน เพราะ write บางส่วนยังไม่ถูก replicate ไปถึง follower ความไม่สอดคล้องนี้เป็นเพียงชั่วคราว ถ้าหยุดเขียนลงฐานข้อมูลแล้วรอสักครู่ follower จะตามทันและตรงกับ leader ในที่สุด ด้วยเหตุนี้ปรากฏการณ์นี้จึงเรียกว่า eventual consistency [ 22 ]

หมายเหตุ

คำว่า eventual consistency ถูกบัญญัติโดย Douglas Terry และคณะ [ 23 ] และแพร่หลายขึ้นด้วย Werner Vogels [ 24 ] จนกลายเป็นคำขวัญของโปรเจกต์ NoSQL จำนวนมาก แต่ไม่ได้มีเพียงฐานข้อมูล NoSQL ที่เป็น eventually consistent follower ใน relational database ที่ replicate แบบ asynchronous ก็เป็นเช่นเดียวกัน

คำว่า "eventually" ตั้งใจให้คลุมเครือ โดยทั่วไปไม่มีขีดจำกัดว่า replica จะตามหลังได้มากแค่ไหน ในการทำงานปกติ ช่วงเวลาระหว่างที่ write เกิดบน leader กับที่ปรากฏบน follower หรือ replication lag อาจเป็นเพียงเสี้ยววินาทีจนแทบไม่รู้สึก แต่ถ้าระบบทำงานใกล้ขีดความสามารถสูงสุดหรือเครือข่ายมีปัญหา lag อาจเพิ่มเป็นหลายวินาทีหรือหลายนาทีได้ง่ายๆ

เมื่อ lag สูง ความไม่สอดคล้องที่ตามมาไม่ใช่แค่ปัญหาเชิงทฤษฎี แต่เป็นปัญหาจริงของแอปพลิเคชัน ส่วนนี้จะยกตัวอย่างปัญหาที่พบบ่อยจาก replication lag สามแบบ พร้อมแนวทางแก้ไขบางส่วน

Reading your own writes (การอ่านข้อมูลที่ตัวเองเขียน)

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

แต่ asynchronous replication ทำให้เกิดปัญหา ดังที่แสดงใน Figure 6-3: ถ้าผู้ใช้ดูข้อมูลหลังเขียนไปได้ไม่นาน ข้อมูลใหม่อาจยังไปไม่ถึง replica ในสายตาของผู้ใช้ ข้อมูลที่เพิ่งส่งไปดูเหมือนหายไป จึงไม่น่าแปลกที่พวกเขาจะไม่พอใจ

Figure 6-3. ความไม่สอดคล้องเกิดได้เมื่อผู้ใช้เขียนข้อมูล แล้วอ่านต่อจาก replica ที่ข้อมูลยังเก่าอยู่

ในสถานการณ์นี้ เราต้องการ read-after-write consistency หรือที่เรียกว่า read-your-writes consistency [ 23 ] นี่คือหลักประกันว่าถ้าผู้ใช้โหลดหน้าเว็บซ้ำ จะเห็นการอัปเดตที่ตัวเองส่งไปเสมอ แต่ไม่รับประกันอะไรเกี่ยวกับผู้ใช้คนอื่น การอัปเดตของคนอื่นอาจยังไม่ปรากฏจนกว่าจะผ่านไปสักพัก แม้อย่างนั้น หลักประกันนี้ก็ทำให้ผู้ใช้มั่นใจได้ว่าข้อมูลที่ป้อนไปถูกบันทึกอย่างถูกต้อง

เราจะ implement read-after-write consistency ในระบบ leader-based replication ได้อย่างไร? ทำได้หลายเทคนิค ขอยกมาบางส่วน:

• เมื่ออ่านสิ่งที่ผู้ใช้อาจแก้ไขได้ ให้อ่านจาก leader หรือ follower ที่อัปเดตแบบ synchronous ส่วนสิ่งอื่นอ่านจาก follower ที่อัปเดตแบบ asynchronous ได้ วิธีนี้ต้องมีวิธีรู้ล่วงหน้าว่าอะไรอาจถูกแก้ไข โดยไม่ต้อง query ดู เช่น ข้อมูลโปรไฟล์บน social network ปกติมีแต่เจ้าของโปรไฟล์ที่แก้ได้ ไม่ใช่คนอื่น กฎง่ายๆ จึงเป็น อ่านโปรไฟล์ของผู้ใช้เองจาก leader เสมอ และอ่านโปรไฟล์ของผู้ใช้คนอื่นจาก follower

• แต่ถ้าผู้ใช้อาจแก้ไขข้อมูลส่วนใหญ่ในแอปพลิเคชันได้ วิธีนั้นจะใช้ไม่ได้ผล เพราะแทบทุกอย่างต้องอ่านจาก leader (ประโยชน์ของ read scaling จึงหายไป) ในกรณีนั้นอาจใช้เกณฑ์อื่นตัดสินว่าจะอ่านจาก leader หรือไม่ เช่น ติดตามเวลาของการอัปเดตล่าสุด แล้วให้อ่านจาก leader ทั้งหมดภายในหนึ่งนาทีหลังอัปเดตล่าสุด [ 25 ] หรือติดตาม replication lag ของ follower และไม่ให้ query ไปที่ follower ที่ตามหลัง leader เกินหนึ่งนาที

• client จำ timestamp ของ write ล่าสุดของตัวเองไว้ได้ แล้วระบบก็ทำให้แน่ใจว่า replica ที่รับ read ของผู้ใช้คนนั้นมีการอัปเดตอย่างน้อยถึง timestamp นั้น ถ้า replica ยังไม่ทัน ก็ให้ replica อื่นรับ read แทน หรือให้ query รอจน replica ตามทัน [ 26 ] timestamp อาจเป็น logical timestamp (ตัวบอกลำดับของ write เช่น log sequence number) หรือนาฬิกาของระบบจริง (กรณีนั้นการ sync นาฬิกาจะสำคัญมาก ดูหัวข้อ "นาฬิกาที่ไม่น่าเชื่อถือ")

• ถ้า replica ของคุณกระจายอยู่หลาย region (เพื่ออยู่ใกล้ผู้ใช้ เพื่อ availability หรือเพื่อความคงทน) จะมีความซับซ้อนเพิ่มขึ้น request ใดที่ต้องให้ leader รับ จะต้องถูกส่งต่อไปยัง region ที่มี leader

ความซับซ้อนอีกแบบเกิดขึ้นเมื่อผู้ใช้คนเดียวกันเข้าบริการของคุณจากหลายอุปกรณ์ เช่น เว็บเบราว์เซอร์บนเดสก์ท็อปกับแอปมือถือ กรณีนี้คุณอาจต้องการ cross-device read-after-write consistency คือถ้าผู้ใช้ป้อนข้อมูลบนอุปกรณ์หนึ่งแล้วไปดูบนอีกอุปกรณ์ ก็ควรเห็นข้อมูลที่เพิ่งป้อน

มีประเด็นเพิ่มเติมที่ต้องคิดอีกสองข้อ:

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

• ถ้า replica ของคุณกระจายอยู่หลาย region ไม่มีอะไรรับประกันว่า connection จากอุปกรณ์ต่างๆ จะถูกส่งไปที่ region เดียวกัน (เช่น ถ้าเดสก์ท็อปของผู้ใช้ใช้อินเทอร์เน็ตบ้าน ส่วนมือถือใช้เครือข่ายเซลลูลาร์ เส้นทางเครือข่ายของสองอุปกรณ์อาจต่างกันโดยสิ้นเชิง) ถ้าวิธีของคุณต้องอ่านจาก leader คุณอาจต้องส่ง request จากทุกอุปกรณ์ของผู้ใช้ไปที่ region เดียวกันก่อน

Regions and Availability Zones (Region และ Availability Zone)

เราใช้คำว่า region หมายถึง datacenter หนึ่งแห่งหรือมากกว่าที่ตั้งอยู่ในพื้นที่ทางภูมิศาสตร์เดียวกัน cloud provider วาง datacenter หลายแห่งไว้ในพื้นที่เดียวกัน โดยแต่ละ datacenter เรียกว่า availability zone หรือเรียกสั้นๆ ว่า zone cloud region หนึ่งจึงประกอบด้วยหลาย zone แต่ละ zone คือ datacenter ที่แยกกัน อยู่คนละสถานที่ทางกายภาพ และมีระบบไฟฟ้า ระบบทำความเย็น ฯลฯ ของตัวเอง

Zone ใน region เดียวกันเชื่อมต่อกันด้วยเครือข่ายความเร็วสูงมาก latency ต่ำพอที่ระบบกระจายส่วนใหญ่จะรันโดยกระจาย node ไปหลาย zone ใน region เดียวกันได้เหมือนอยู่ใน zone เดียว การตั้งค่าแบบ multi-zone ช่วยให้ระบบกระจายรอดจาก zonal outage ที่ zone หนึ่งออฟไลน์ แต่ไม่ป้องกัน regional outage ที่ทุก zone ใน region ใช้งานไม่ได้ การจะรอดจาก regional outage ต้อง deploy ระบบกระจายข้ามหลาย region ซึ่งอาจทำให้ latency สูงขึ้น throughput ลดลง และค่า network บนคลาวด์เพิ่มขึ้น เราจะพูดถึง trade-off เหล่านี้เพิ่มเติมในหัวข้อ "โทโพโลยีการจำลองแบบ Multi-Leader" ตอนนี้ขอให้รู้ไว้แค่ว่า เมื่อพูดถึง region เราหมายถึงกลุ่มของ zone/datacenter ในพื้นที่ทางภูมิศาสตร์เดียวกัน

Monotonic reads (การอ่านแบบ Monotonic)

ตัวอย่างที่สองของความผิดปกติที่อาจเกิดเมื่ออ่านจาก asynchronous follower คือผู้ใช้อาจเห็นสิ่งต่างๆ เคลื่อนย้อนกลับในเวลา

เรื่องนี้เกิดได้ถ้าผู้ใช้อ่านหลายครั้งจาก replica คนละตัว เช่น Figure 6-4 แสดงผู้ใช้ 2345 ที่ query เดียวกันสองครั้ง ครั้งแรกไปที่ follower ที่มี lag น้อย ครั้งที่สองไปที่ follower ที่มี lag มากกว่า (เกิดได้ง่ายถ้าผู้ใช้รีเฟรชหน้าเว็บ แล้วแต่ละ request ถูกส่งไปยังเซิร์ฟเวอร์แบบสุ่ม) query แรกคืนความคิดเห็นที่ผู้ใช้ 1234 เพิ่งเพิ่มเข้ามา แต่ query ที่สองไม่คืนอะไรเลย เพราะ follower ที่ตามหลังยังไม่ได้รับ write นั้น พูดอีกอย่างคือ query ที่สองเห็นสถานะของระบบก่อนหน้าที่ query แรกเห็น ถ้า query แรกไม่คืนอะไรเลยก็คงไม่แย่นัก เพราะผู้ใช้ 2345 คงไม่รู้ว่าผู้ใช้ 1234 เพิ่งคอมเมนต์ แต่ผู้ใช้ 2345 จะสับสนมากถ้าเห็นความคิดเห็นของผู้ใช้ 1234 โผล่ขึ้นมาก่อน แล้วหายไปอีก

Monotonic reads [ 22 ] รับประกันว่าความผิดปกติแบบนี้จะไม่เกิดขึ้น เป็นหลักประกันที่อ่อนกว่า strong consistency แต่แข็งกว่า eventual consistency เวลาอ่านข้อมูลคุณอาจเห็นค่าเก่า แต่ monotonic reads หมายความเพียงว่าถ้าผู้ใช้คนหนึ่งอ่านหลายครั้งต่อเนื่องกัน จะไม่เห็นเวลาย้อนกลับ (คือจะไม่อ่านข้อมูลที่เก่ากว่า หลังจากเคยอ่านข้อมูลที่ใหม่กว่าแล้ว)

วิธีหนึ่งที่ทำให้ได้ monotonic reads คือให้ผู้ใช้แต่ละคนอ่านจาก replica เดียวกันเสมอ (ผู้ใช้ต่างคนต่าง replica กันได้) เช่น เลือก replica ด้วย hash ของ user ID แทนที่จะสุ่ม แต่ถ้า replica นั้นล้มเหลว query ของผู้ใช้ต้องถูกส่งต่อไปยัง replica อื่น

Figure 6-4. เมื่อผู้ใช้อ่านจาก replica ที่ข้อมูลใหม่ก่อน แล้วจึงอ่านจาก replica ที่ข้อมูลเก่า เวลาจะดูเหมือนย้อนกลับ

Consistent prefix reads (การอ่านแบบ Consistent Prefix)

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

คุณพูนส์: คุณมองเห็นอนาคตได้ไกลแค่ไหน คุณเค้ก?

คุณเค้ก: โดยปกติประมาณ 10 วินาทีค่ะ คุณพูนส์

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

ทีนี้ลองนึกว่ามีคนที่สามกำลังฟังบทสนทนานี้ผ่าน follower สิ่งที่คุณเค้กพูดผ่านไปยัง follower ที่มี lag น้อย แต่สิ่งที่คุณพูนส์พูดมี replication lag นานกว่า (ดู Figure 6-5) ผู้สังเกตการณ์นี้จะได้ยินดังนี้:

คุณเค้ก: โดยปกติประมาณ 10 วินาทีค่ะ คุณพูนส์

คุณพูนส์: คุณมองเห็นอนาคตได้ไกลแค่ไหน คุณเค้ก?

สำหรับผู้ฟัง ดูเหมือนคุณเค้กตอบคำถามก่อนที่คุณพูนส์จะถามเสียอีก พลังจิตแบบนี้น่าทึ่งแต่ก็ทำให้งงมาก [ 27 ]

Figure 6-5. ถ้า shard บางตัว replicate ช้ากว่าตัวอื่น ผู้สังเกตการณ์อาจเห็นคำตอบก่อนคำถาม

การป้องกันความผิดปกติแบบนี้ต้องใช้หลักประกันอีกแบบหนึ่ง คือ consistent prefix reads [ 22 ] หลักประกันนี้ระบุว่า ถ้ามี write ชุดหนึ่งเกิดขึ้นตามลำดับ ใครที่อ่าน write เหล่านั้นก็จะเห็นมันปรากฏตามลำดับเดียวกัน

นี่เป็นปัญหาเฉพาะของฐานข้อมูลแบบ sharded (partitioned) ซึ่งเราจะพูดถึงใน บทที่ 7 ถ้าฐานข้อมูล apply write ในลำดับเดียวกันเสมอ การอ่านก็จะเห็น consistent prefix เสมอ และความผิดปกตินี้จะไม่เกิดขึ้น แต่ในฐานข้อมูลแบบกระจายหลายตัว แต่ละ shard ทำงานอิสระต่อกัน จึงไม่มีลำดับ write แบบ global เมื่อผู้ใช้อ่านจากฐานข้อมูล อาจเห็นบางส่วนอยู่ในสถานะเก่าและบางส่วนอยู่ในสถานะใหม่

วิธีแก้อย่างหนึ่งคือทำให้ write ที่มีความสัมพันธ์เชิงเหตุและผลต่อกันถูกเขียนไปยัง shard เดียวกัน แต่ในบางแอปพลิเคชันทำแบบนั้นอย่างมีประสิทธิภาพไม่ได้ ส่วนอัลกอริทึมบางตัวติดตามความสัมพันธ์เชิงเหตุและผลอย่างชัดเจน ซึ่งเราจะกลับมาพูดถึงในหัวข้อ "ความสัมพันธ์แบบ Happens-Before และ Concurrency"

Solutions for Replication Lag (แนวทางแก้ไข Replication Lag)

เมื่อทำงานกับระบบ eventual consistency ควรคิดไว้ว่าแอปพลิเคชันจะทำงานอย่างไรถ้า replication lag เพิ่มเป็นหลายนาทีหรือหลายชั่วโมง ถ้าคำตอบคือ "ไม่มีปัญหา" ก็ดีไป แต่ถ้าผู้ใช้จะได้ประสบการณ์ที่แย่ ก็ต้องออกแบบระบบให้มีหลักประกันที่แข็งแรงขึ้น เช่น read-after-write การแกล้งทำเป็นว่า replication เป็นแบบ synchronous ทั้งที่จริงเป็น asynchronous คือสูตรสำเร็จของปัญหาในอนาคต

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

โมเดลการเขียนโปรแกรมที่ง่ายที่สุดสำหรับนักพัฒนาแอปพลิเคชันคือเลือกฐานข้อมูลที่ให้หลักประกัน consistency ที่แข็งแรงกับ replica เช่น linearizability (ดู บทที่ 10) และรองรับ ACID transaction (ดู บทที่ 8) วิธีนี้ทำให้คุณแทบไม่ต้องสนใจความท้าทายของ replication และปฏิบัติต่อฐานข้อมูลเหมือนมี node เดียวได้ ช่วงต้นทศวรรษ 2010 กระแส NoSQL เสนอมุมมองว่าฟีเจอร์เหล่านี้จำกัด scalability และระบบขนาดใหญ่ต้องยอมรับ eventual consistency

แต่ตั้งแต่นั้นมา ฐานข้อมูลหลายตัวเริ่มให้ strong consistency และรองรับ transaction ได้ โดยยังคงได้ fault tolerance, high availability และข้อได้เปรียบด้าน scalability ของฐานข้อมูลแบบกระจาย ดังที่กล่าวถึงในหัวข้อ "โมเดลเชิงสัมพันธ์เทียบกับโมเดลเอกสาร" แนวโน้มนี้เรียกว่า NewSQL เพื่อเทียบกับ NoSQL (แม้จะเกี่ยวกับ SQL น้อยกว่า และเกี่ยวกับแนวทางใหม่ในการทำ transaction ที่ scalable มากกว่า)

แม้ตอนนี้จะมีฐานข้อมูลแบบกระจายที่ scalable และ strongly consistent ให้ใช้แล้ว แต่ก็ยังมีเหตุผลดีๆ ที่บางแอปพลิเคชันเลือกรูปแบบ replication อื่นที่ให้หลักประกัน consistency อ่อนกว่า โดยเฉพาะอย่างยิ่ง รูปแบบเหล่านั้นอาจทนต่อเครือข่ายที่ขัดข้องได้ดีกว่า และมี overhead ต่ำกว่าระบบ transactional เราจะดูแนวทางเหล่านี้ใน ส่วนที่เหลือของบทนี้

Multi-Leader Replication (การจำลองแบบหลายผู้นำ)

จนถึงตอนนี้ บทนี้พูดถึงเฉพาะสถาปัตยกรรม replication ที่ใช้ leader เดียว ซึ่งเป็นแนวทางที่พบได้ทั่วไป แต่ก็ยังมีทางเลือกที่น่าสนใจ

Single-leader replication มีข้อเสียหลักข้อหนึ่ง คือ write ทั้งหมดต้องผ่าน leader ตัวเดียว ถ้าคุณเชื่อมต่อกับ leader ไม่ได้ไม่ว่าด้วยเหตุผลใด เช่น เครือข่ายระหว่างคุณกับ leader ขัดข้อง ก็จะเขียนลงฐานข้อมูลไม่ได้

ส่วนขยายที่เป็นธรรมชาติของโมเดล single-leader replication คือให้ node มากกว่าหนึ่งตัวรับ write ได้ การ replicate ยังทำแบบเดิม คือแต่ละ node ที่ประมวลผล write ต้องส่งต่อการเปลี่ยนแปลงนั้นไปยัง node อื่นทั้งหมด เราเรียกรูปแบบนี้ว่าการตั้งค่าแบบ multi-leader (หรือเรียกว่า active/active หรือ bidirectional replication) ในรูปแบบนี้ leader แต่ละตัวทำหน้าที่เป็น follower ของ leader ตัวอื่นไปพร้อมกัน

เช่นเดียวกับ single-leader replication เราเลือกได้ว่าจะเป็น synchronous หรือ asynchronous สมมติว่ามี leader สองตัวคือ A และ B และคุณกำลังเขียนไปที่ A ถ้า write ถูก replicate แบบ synchronous จาก A ไป B แล้วเครือข่ายระหว่างสอง node ขัดข้อง คุณจะเขียนไปที่ A ไม่ได้จนกว่าการเชื่อมต่อจะกลับมา synchronous multi-leader replication จึงให้โมเดลที่คล้ายกับ single-leader replication มาก เช่น ถ้าให้ B เป็น leader แล้ว A แค่ส่งต่อ write request ทุกอย่างไปให้ B ประมวลผล

ด้วยเหตุนี้ เราจะไม่ลงลึกเรื่อง synchronous multi-leader replication และจะถือว่ามันเทียบเท่ากับ single-leader replication ส่วนที่เหลือของหัวข้อนี้จะเน้น asynchronous multi-leader replication ซึ่ง leader ตัวไหนก็ประมวลผล write ได้ แม้การเชื่อมต่อไปยัง leader ตัวอื่นจะขัดข้อง

Geographically Distributed Operation (การทำงานแบบกระจายตามภูมิศาสตร์)

การใช้ multi-leader setup ภายใน region เดียวมักไม่ค่อยคุ้ม เพราะประโยชน์ที่ได้มักไม่คุ้มกับความซับซ้อนที่เพิ่มขึ้น แต่ในบางสถานการณ์ รูปแบบนี้ก็สมเหตุสมผล

ลองนึกถึงฐานข้อมูลที่มี replica อยู่ในหลาย region (อาจเพื่อทนต่อความล้มเหลวของทั้ง region หรือเพื่ออยู่ใกล้ผู้ใช้) รูปแบบนี้เรียกว่าการตั้งค่าแบบ geographically distributed, geo-distributed, หรือ geo-replicated ถ้าใช้ single-leader replication leader ต้องอยู่ใน region ใด region หนึ่ง และ write ทั้งหมดต้องผ่าน region นั้น

Figure 6-6. Multi-leader replication ข้ามหลาย region

ในการตั้งค่าแบบ multi-leader คุณมี leader ใน ทุก region ได้ Figure 6-6 แสดงตัวอย่างหน้าตาที่เป็นไปได้ของสถาปัตยกรรมนี้ ภายในแต่ละ region ใช้ leader–follower replication ตามปกติ (โดย follower อาจอยู่ใน availability zone ต่างจาก leader) ส่วนระหว่าง region leader ของแต่ละ region จะ replicate การเปลี่ยนแปลงไปให้ leader ใน region อื่น มาเปรียบเทียบ single-leader กับ multi-leader เมื่อ deploy หลาย region:

ประสิทธิภาพ

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

ความทนทานต่อการล่มของทั้ง region

ถ้าเป็น single-leader และ region ที่มี leader ใช้งานไม่ได้ failover สามารถเลื่อน follower ใน region อื่นขึ้นเป็น leader ได้ ส่วน multi-leader แต่ละ region ทำงานต่อได้อย่างอิสระจาก region อื่น และเมื่อ region ที่ออฟไลน์กลับมาออนไลน์ replication ก็จะตามทัน

ความทนทานต่อปัญหาเครือข่าย

แม้จะมี connection เฉพาะ traffic ระหว่าง region อาจน่าเชื่อถือน้อยกว่า traffic ระหว่าง zone ใน region เดียวกัน หรือภายใน zone เดียว single-leader อ่อนไหวต่อปัญหาของ link ระหว่าง region นี้มาก เพราะเมื่อ client ใน region หนึ่งต้องการเขียนไปที่ leader ใน region อื่น ก็ต้องส่ง request ผ่าน link นั้นแล้วรอ response กว่าจะเสร็จ

multi-leader ที่ใช้ asynchronous replication ทนต่อปัญหาเครือข่ายได้ดีกว่า ระหว่างที่เครือข่ายขัดข้องชั่วคราว leader ของแต่ละ region ก็ประมวลผล write ต่อไปได้อย่างอิสระ

Consistency

ระบบ single-leader ให้หลักประกัน consistency ที่แข็งแรงได้ เช่น serializable transaction ซึ่งเราจะพูดถึงใน บทที่ 8 ข้อเสียที่ใหญ่ที่สุดของระบบ multi-leader คือ consistency ที่ทำได้อ่อนกว่ามาก เช่น คุณรับประกันไม่ได้ว่าบัญชีธนาคารจะไม่ติดลบ หรือชื่อผู้ใช้จะไม่ซ้ำกัน leader คนละตัวอาจประมวลผล write ที่เมื่อดูเดี่ยวๆ ไม่มีปัญหา (เช่น การจ่ายเงินออกจากบัญชี หรือการลงทะเบียนชื่อผู้ใช้หนึ่งชื่อ) แต่เมื่อรวมกับ write อีกอันบน leader อื่นแล้วละเมิดข้อจำกัด ซึ่งเป็นไปได้เสมอ

นี่เป็นเพียงข้อจำกัดพื้นฐานของระบบกระจาย [ 28 ] ถ้าต้องการบังคับใช้ข้อจำกัดแบบนี้ ระบบ single-leader จะเหมาะกว่า อย่างไรก็ตาม ดังที่เราจะเห็นในหัวข้อ "การจัดการกับ Write Conflicts" ระบบ multi-leader ก็ยังให้คุณสมบัติ consistency ที่เป็นประโยชน์ได้ในแอปพลิเคชันหลายแบบที่ไม่ต้องการข้อจำกัดเช่นนั้น

Multi-leader replication พบน้อยกว่า single-leader replication แต่ฐานข้อมูลหลายตัวก็รองรับ รวมถึง MySQL, Oracle, SQL Server, และ YugabyteDB ในบางกรณีมันเป็นฟีเจอร์ add-on ภายนอก เช่น ใน Redis Enterprise, EDB Postgres Distributed และ pglogical [ 29 ]

เพราะ multi-leader replication ในฐานข้อมูลหลายตัวเป็นฟีเจอร์ที่ถูกต่อเติมเข้ามาทีหลัง จึงมักมี configuration ที่พลาดง่ายอย่างไม่ชัดเจน และปฏิสัมพันธ์ที่ไม่คาดคิดกับฟีเจอร์อื่นของฐานข้อมูล เช่น autoincrement key, trigger และ integrity constraint อาจเป็นปัญหาได้ multi-leader replication จึงมักถูกมองว่าเป็นดินแดนอันตรายที่ควรเลี่ยงถ้าเป็นไปได้ [ 30 ]

Multi-leader replication topologies (โทโพโลยีการจำลองแบบ Multi-Leader)

replication topology อธิบายเส้นทางการสื่อสารที่ใช้กระจาย write จาก node หนึ่งไปอีก node หนึ่ง ถ้ามี leader สองตัว ดังใน Figure 6-6 จะมี topology เดียวที่เป็นไปได้ คือ leader 1 ต้องส่ง write ทั้งหมดไปให้ leader 2 และในทางกลับกัน แต่ถ้ามี leader มากกว่าสองตัว ก็มี topology ได้หลายแบบ ตัวอย่างบางแบบแสดงใน Figure 6-7

Figure 6-7. ตัวอย่าง topology สามแบบของ multi-leader replication

topology ที่ทั่วไปที่สุดคือ all-to-all ดังแสดงใน Figure 6-7 (c) ซึ่งทุก leader ส่ง write ของตัวเองไปให้ leader อื่นทุกตัว แต่ topology ที่จำกัดกว่าก็มีใช้เช่นกัน เช่น ใน circular topology ดังแสดงใน Figure 6-7 (a) แต่ละ node รับ write จาก node หนึ่ง แล้วส่งต่อ write เหล่านั้น (รวมกับ write ของตัวเอง) ไปให้อีก node หนึ่ง star topology ดังแสดงใน Figure 6-7 (b) ก็เป็นที่นิยมเช่นกัน โดยมี node root ที่กำหนดไว้หนึ่งตัวส่งต่อ write ไปยัง node อื่นทั้งหมด และ star topology ยังขยายเป็น tree ได้ด้วย

หมายเหตุ

network topology แบบ star ไม่เกี่ยวข้องกับ star schema (ดูหัวข้อ "Stars and Snowflakes: Schemas for Analytics") ซึ่งอธิบายโครงสร้างของโมเดลข้อมูล

ใน circular และ star topologies write อาจต้องผ่านหลาย node ก่อนจะถึงทุก replica ดังนั้น node ต้องส่งต่อการเปลี่ยนแปลงที่ได้รับมาจาก node อื่น เพื่อป้องกัน replication วนลูปไม่รู้จบ แต่ละ node จะมี identifier ที่ไม่ซ้ำกัน และใน replication log แต่ละ write จะถูกติดแท็กด้วย identifier ของทุก node ที่มันผ่านมา [ 31 ] เมื่อ node ได้รับการเปลี่ยนแปลงที่ติดแท็ก identifier ของตัวเอง ก็จะข้ามการเปลี่ยนแปลงนั้นไป เพราะรู้ว่าตัวเองประมวลผลไปแล้ว

Problems with different topologies (ปัญหาของ topology แต่ละแบบ)

ปัญหาของ circular และ star topology คือถ้า node เดียวล้มเหลว ก็อาจขัดขวางการไหลของ replication message ระหว่าง node อื่น ทำให้สื่อสารกันไม่ได้จนกว่า node นั้นจะถูกซ่อม เราตั้งค่า topology ใหม่ให้เลี่ยง node ที่ล้มเหลวได้ แต่ในการ deploy ส่วนใหญ่ต้องทำเองด้วยมือ topology ที่เชื่อมต่อกันหนาแน่นกว่า (เช่น all-to-all) จึงทนต่อความผิดพลาดได้ดีกว่า เพราะ message เดินทางผ่านเส้นทางต่างๆ ได้ และเลี่ยง single point of failure

แต่ all-to-all topology ก็มีปัญหาได้เช่นกัน โดยเฉพาะ network link บางเส้นอาจเร็วกว่าเส้นอื่น (เช่น เพราะเครือข่ายคับคั่ง) ทำให้ replication message บางตัว "แซง" ตัวอื่น ดังที่แสดงใน Figure 6-8

ใน Figure 6-8 client A insert แถวลงตารางบน leader 1 และ client B อัปเดตแถวนั้นบน leader 3 แต่ leader 2 อาจได้รับ write ในลำดับที่ต่างออกไป คือได้รับ update ก่อน (ซึ่งในมุมมองของมันคือการอัปเดตแถวที่ไม่มีอยู่ในฐานข้อมูล) แล้วจึงได้รับ insert ที่เกี่ยวข้องทีหลัง (ทั้งที่ insert ควรมาก่อน update)

Figure 6-8. ใน multi-leader replication write อาจมาถึงบาง replica ในลำดับที่ผิด

นี่คือปัญหาเรื่องความเป็นเหตุเป็นผล คล้ายกับที่เราเห็นในหัวข้อ "การอ่านแบบ Consistent Prefix" update ขึ้นอยู่กับ insert ก่อนหน้า เราจึงต้องมั่นใจว่าทุก node ประมวลผล insert ก่อน แล้วค่อยประมวลผล update แค่แนบ timestamp ให้ทุก write ไม่พอ เพราะนาฬิกาไม่น่าไว้ใจว่าจะ sync กันดีพอที่จะเรียงลำดับเหตุการณ์เหล่านี้ที่ leader 2 ได้ถูกต้อง (ดู บทที่ 9)

การเรียงลำดับเหตุการณ์เหล่านี้ให้ถูกต้องทำได้ด้วยเทคนิคที่เรียกว่า version vector ซึ่งเราจะพูดถึงในหัวข้อ "การตรวจจับ Concurrent Writes" แต่ระบบ multi-leader replication จำนวนมากไม่มีเทคนิคเรียงลำดับ update ที่ดี จึงเสี่ยงต่อปัญหาอย่างที่เห็นใน Figure 6-8 ถ้าคุณใช้ multi-leader replication ควรรู้เท่าทันปัญหาเหล่านี้ อ่านเอกสารให้ละเอียด และทดสอบฐานข้อมูลอย่างถี่ถ้วน เพื่อให้แน่ใจว่ามันให้หลักประกันตามที่คุณเชื่อจริงๆ

Sync Engines and Local-First Software (Sync engine และ Local-first software)

Multi-leader replication ก็เหมาะเช่นกันถ้าแอปพลิเคชันของคุณต้องทำงานต่อได้แม้ไม่ได้เชื่อมต่ออินเทอร์เน็ต ลองนึกถึงแอปปฏิทินบนมือถือ แล็ปท็อป และอุปกรณ์อื่นของคุณ คุณต้องดูนัดหมาย (read request) และเพิ่มนัดหมายใหม่ (write request) ได้ตลอดเวลา ไม่ว่าอุปกรณ์จะต่ออินเทอร์เน็ตอยู่หรือไม่ และถ้าแก้ไขอะไรขณะออฟไลน์ ก็ต้อง sync การเปลี่ยนแปลงเหล่านั้นไปยังเซิร์ฟเวอร์และอุปกรณ์อื่นเมื่ออุปกรณ์กลับมาออนไลน์

ในกรณีนี้ ทุกอุปกรณ์มี replica ของฐานข้อมูลในเครื่องที่ทำหน้าที่เป็น leader (รับ write request) และมีกระบวนการ asynchronous multi-leader replication (sync) ระหว่าง replica ของปฏิทินบนทุกอุปกรณ์ replication lag อาจนานเป็นชั่วโมงหรือเป็นวัน ขึ้นอยู่กับว่าคุณต่ออินเทอร์เน็ตได้เมื่อไร

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

Real-time collaboration, offline-first, and local-first apps

เว็บแอปสมัยใหม่หลายตัวมีฟีเจอร์ real-time collaboration เช่น Google Docs และ Sheets สำหรับเอกสารข้อความและสเปรดชีต Figma สำหรับงานกราฟิก และ Linear สำหรับการจัดการโปรเจกต์ สิ่งที่ทำให้แอปเหล่านี้ตอบสนองได้ดีคือสิ่งที่ผู้ใช้ป้อนจะแสดงใน UI ทันที โดยไม่ต้องรอ network round trip ไปหาเซิร์ฟเวอร์ และการแก้ไขของผู้ใช้คนหนึ่งก็แสดงให้ผู้ร่วมงานเห็นด้วย latency ต่ำ [ 32, 33, 34 ]

ผลที่ได้คือสถาปัตยกรรม multi-leader อีกครั้ง แต่ละแท็บเบราว์เซอร์ที่เปิดไฟล์ร่วมกันคือ replica และทุกการอัปเดตที่คุณทำกับไฟล์จะถูก replicate แบบ asynchronous ไปยังอุปกรณ์ของผู้ใช้คนอื่นที่เปิดไฟล์เดียวกัน แม้แอปจะไม่ให้แก้ไขไฟล์ต่อขณะออฟไลน์ แต่การที่ผู้ใช้หลายคนแก้ไขได้โดยไม่ต้องรอ response จากเซิร์ฟเวอร์ ก็ทำให้มันเป็น multi-leader อยู่แล้ว

ทั้งการแก้ไขแบบออฟไลน์และ real-time collaboration ต้องใช้โครงสร้างพื้นฐาน replication ที่คล้ายกัน แอปพลิเคชันต้องบันทึกการเปลี่ยนแปลงทุกอย่างที่ผู้ใช้ทำกับไฟล์ แล้วส่งให้ผู้ร่วมงานทันที (ถ้าออนไลน์) หรือเก็บไว้ในเครื่องเพื่อส่งทีหลัง (ถ้าออฟไลน์) นอกจากนี้ยังต้องรับการเปลี่ยนแปลงจากผู้ร่วมงาน นำมารวมกับสำเนาไฟล์ในเครื่องของผู้ใช้ และอัปเดต UI ให้เป็นเวอร์ชันล่าสุด ถ้าผู้ใช้หลายคนแก้ไฟล์พร้อมกัน อาจต้องมีตรรกะแก้ conflict เพื่อรวมการเปลี่ยนแปลงเหล่านั้น

library ที่รองรับกระบวนการนี้เรียกว่า sync engine แม้แนวคิดนี้จะมีมานานแล้ว แต่คำนี้เพิ่งได้รับความสนใจเมื่อไม่นานมานี้ [ 35, 36, 37 ] แอปพลิเคชันที่ให้ผู้ใช้แก้ไขไฟล์ต่อได้ขณะออฟไลน์ (ซึ่งอาจ implement ด้วย sync engine) เรียกว่า offline-first [ 38 ] คำว่า local-first software หมายถึงแอปที่ทำงานร่วมกันได้ ซึ่งไม่ได้แค่ offline-first แต่ยังออกแบบให้ทำงานต่อไปได้ แม้ผู้พัฒนาซอฟต์แวร์จะปิดบริการออนไลน์ทั้งหมดไปแล้ว [ 39 ] ทำได้โดยใช้ sync engine ที่มี sync protocol เป็นมาตรฐานเปิดและมีผู้ให้บริการหลายราย [ 40 ] ตัวอย่างเช่น Git เป็นระบบทำงานร่วมกันแบบ local-first (แม้จะไม่รองรับ real-time collaboration) เพราะคุณ sync ผ่าน GitHub, GitLab หรือบริการโฮสต์ repository เจ้าไหนก็ได้

Pros and cons of sync engines (ข้อดีและข้อเสียของ sync engine)

วิธีสร้างเว็บแอปที่ใช้กันทั่วไปในปัจจุบันคือเก็บ persistent state บน client น้อยมาก และอาศัยการส่ง request ไปหาเซิร์ฟเวอร์ทุกครั้งที่ต้องแสดงข้อมูลใหม่หรืออัปเดตข้อมูล ในทางกลับกัน เมื่อใช้ sync engine คุณจะมี persistent state อยู่บน client และการสื่อสารกับเซิร์ฟเวอร์ถูกย้ายไปเป็น background process แนวทางแบบ sync engine มีข้อดีหลายอย่าง:

• การมีข้อมูลในเครื่องหมายความว่า UI ตอบสนองได้เร็วกว่าการรอเรียก service เพื่อดึงข้อมูล บางแอปตั้งเป้าให้ตอบสนองต่อสิ่งที่ผู้ใช้ป้อนภายใน เฟรมถัดไป ของระบบกราฟิก ซึ่งหมายถึงต้องแสดงผลภายใน 16 ms บนจอที่รีเฟรช 60 Hz

• การให้ผู้ใช้ทำงานต่อได้ขณะออฟไลน์มีคุณค่า โดยเฉพาะบนมือถือที่การเชื่อมต่อไม่สม่ำเสมอ ถ้าใช้ sync engine แอปไม่ต้องมีโหมดออฟไลน์แยกต่างหาก เพราะการออฟไลน์ก็แค่เหมือนมี network latency สูงมาก

• sync engine ทำให้โมเดลการเขียนโปรแกรมของ frontend app ง่ายขึ้น เมื่อเทียบกับการเรียก service ตรงๆ ในโค้ดแอปพลิเคชัน ซึ่งทุกการเรียกต้องมีการจัดการข้อผิดพลาด ดังที่กล่าวถึงในหัวข้อ "ปัญหาของการเรียกโพรซีเยอร์ระยะไกล"; เช่น ถ้า request อัปเดตข้อมูลบนเซิร์ฟเวอร์ล้มเหลว UI ก็ต้องแสดงข้อผิดพลาดนั้นด้วยวิธีใดวิธีหนึ่ง แต่ sync engine ให้แอปอ่านและเขียนข้อมูลในเครื่อง ซึ่งแทบไม่ล้มเหลวเลย ทำให้เขียนโปรแกรมแบบ declarative ได้มากขึ้น [ 41 ]

• การจะแสดงการแก้ไขจากผู้ใช้อื่นแบบ real-time ได้ คุณต้องรับการแจ้งเตือนเมื่อมีการแก้ไข และอัปเดต UI ตามอย่างมีประสิทธิภาพ sync engine ที่ใช้ร่วมกับโมเดล reactive programming เป็นวิธีที่ดีในการ implement เรื่องนี้ [ 42 ]

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

Lotus Notes บุกเบิก sync engine ไว้ตั้งแต่ยุค 1980 [ 43 ] (แม้จะไม่ได้ใช้คำนั้น) และ sync สำหรับแอปเฉพาะอย่างปฏิทินก็มีมานานแล้ว ปัจจุบันมี sync engine แบบ general-purpose มากมาย บางตัวใช้บริการ backend แบบ proprietary (เช่น Google Firestore, Realm หรือ Ditto) ส่วนบางตัวมี backend แบบ open source จึงเหมาะกับการสร้าง local-first software (เช่น PouchDB/CouchDB, Automerge, และ Yjs)

วิดีโอเกมแบบผู้เล่นหลายคนก็มีความต้องการคล้ายกัน คือต้องตอบสนองต่อการกระทำของผู้ใช้ในเครื่องทันที และกระทบยอดกับการกระทำของผู้เล่นคนอื่นที่เข้ามาทางเครือข่ายแบบ asynchronous ในศัพท์ของวงการพัฒนาเกม สิ่งที่เทียบเท่ากับ sync engine เรียกว่า netcode เทคนิคที่ใช้ใน netcode ค่อนข้างเฉพาะกับความต้องการของเกม [ 44 ] และนำไปใช้กับซอฟต์แวร์ประเภทอื่นโดยตรงไม่ได้ เราจึงจะไม่พูดถึงเพิ่มเติมในหนังสือเล่มนี้

Dealing with Conflicting Writes (การจัดการกับ Write Conflicts)

ปัญหาใหญ่ที่สุดของ multi-leader replication ไม่ว่าจะเป็นฐานข้อมูลฝั่งเซิร์ฟเวอร์แบบ geo-distributed หรือ sync engine แบบ local-first บนอุปกรณ์ผู้ใช้ คือ write ที่เกิดพร้อมกันบน leader คนละตัวอาจทำให้เกิด conflict ที่ต้องแก้

ตัวอย่างเช่น หน้า wiki ที่ผู้ใช้สองคนแก้ไขพร้อมกัน ดังแสดงใน Figure 6-9 ผู้ใช้ 1 เปลี่ยนชื่อหน้าจาก A เป็น B และผู้ใช้ 2 เปลี่ยนชื่อจาก A เป็น C โดยต่างคนต่างทำ การเปลี่ยนแปลงของแต่ละคนถูก apply บน leader ใกล้ตัวของตนสำเร็จ แต่เมื่อ replicate การเปลี่ยนแปลงแบบ asynchronous จึงตรวจพบ conflict ปัญหานี้ไม่เกิดในฐานข้อมูล single-leader

Figure 6-9. Write conflict ที่เกิดจาก leader สองตัวอัปเดต record เดียวกันพร้อมกัน

หมายเหตุ

เราบอกว่า write สองครั้งใน Figure 6-9 เป็น concurrent เพราะตอนที่ write ถูกสร้างขึ้น ไม่มีฝ่ายใด "รู้" เรื่องของอีกฝ่าย ไม่สำคัญว่า write จะเกิดพร้อมกันจริงๆ หรือไม่ อันที่จริง ถ้า write เกิดขึ้นขณะออฟไลน์ ก็อาจเกิดห่างกันนานเป็นช่วงเวลาหนึ่งได้ สิ่งสำคัญคือ write หนึ่งเกิดขึ้นในสถานะที่ write อีกอันมีผลไปแล้วหรือไม่

ในหัวข้อ "การตรวจจับ Concurrent Writes" เราจะดูว่าฐานข้อมูลระบุได้อย่างไรว่า write สองครั้งเป็น concurrent ส่วนตอนนี้ให้สมมติว่าเราตรวจจับ conflict ได้แล้ว และต้องการหาวิธีแก้ที่ดีที่สุด

Conflict avoidance (การหลีกเลี่ยง Conflict)

กลยุทธ์หนึ่งในการรับมือกับ conflict คือป้องกันไม่ให้เกิดขึ้นตั้งแต่แรก เช่น ถ้าแอปพลิเคชันรับประกันได้ว่า write ทั้งหมดของ record หนึ่งๆ ผ่าน leader ตัวเดียวกัน conflict ก็จะไม่เกิดขึ้น แม้ฐานข้อมูลโดยรวมจะเป็น multi-leader ก็ตาม วิธีนี้ใช้ไม่ได้กับ client ของ sync engine ที่อัปเดตขณะออฟไลน์ แต่บางครั้งทำได้ในระบบเซิร์ฟเวอร์แบบ geo-replicated [ 30 ]

เช่น ในแอปพลิเคชันที่ผู้ใช้แก้ไขได้เฉพาะข้อมูลของตัวเอง คุณจัดให้ request จากผู้ใช้คนหนึ่งถูกส่งไปที่ region เดียวกันเสมอ และใช้ leader ใน region นั้นอ่านและเขียนได้ ผู้ใช้แต่ละคนอาจมี region "บ้าน" ต่างกัน (อาจเลือกตามความใกล้ทางภูมิศาสตร์) แต่ในมุมของผู้ใช้คนใดคนหนึ่ง การตั้งค่านี้ก็เป็น single-leader โดยพื้นฐาน

แต่บางครั้งคุณอาจอยากเปลี่ยน leader ที่กำหนดไว้สำหรับ record เช่น เพราะ region หนึ่งใช้งานไม่ได้และต้องย้าย traffic ไปอีก region หรือเพราะผู้ใช้ย้ายที่อยู่จนใกล้ region อื่นมากกว่า ตอนนี้จึงมีความเสี่ยงที่ผู้ใช้จะ write ระหว่างที่กำลังเปลี่ยน leader ที่กำหนดไว้ ซึ่งทำให้เกิด conflict ที่ต้องแก้ด้วยวิธีใดวิธีหนึ่งต่อไปนี้ conflict avoidance จึงใช้ไม่ได้ผลถ้าคุณยอมให้เปลี่ยน leader

อีกตัวอย่างของการหลีกเลี่ยง conflict คือสมมติว่าคุณต้องการ insert record ใหม่และสร้าง ID ที่ไม่ซ้ำให้ โดยใช้ counter แบบ autoincrement ถ้ามี leader สองตัว คุณตั้งให้ leader ตัวหนึ่งสร้างเฉพาะเลขคี่ และอีกตัวสร้างเฉพาะเลขคู่ได้ วิธีนี้ทำให้มั่นใจได้ว่า leader ทั้งสองจะไม่กำหนด ID เดียวกันให้ record คนละอันพร้อมกัน เราจะพูดถึงรูปแบบการกำหนด ID แบบอื่นในหัวข้อ "ID Generators และ Logical Clocks"

Last write wins (discarding concurrent writes) (Last Write Wins: การทิ้ง Concurrent Writes)

ถ้าหลีกเลี่ยง conflict ไม่ได้ วิธีแก้ที่ง่ายที่สุดคือแนบ timestamp ให้แต่ละ write แล้วเลือกค่าที่มี timestamp ล่าสุด (มากที่สุด) เสมอ เช่น ใน Figure 6-9 สมมติว่า timestamp ของ write ของผู้ใช้ 1 มากกว่าของผู้ใช้ 2 ในกรณีนั้น leader ทั้งสองจะตัดสินว่าชื่อใหม่ของหน้าควรเป็น B และทิ้ง write ที่ตั้งเป็น C ถ้า write สองตัวมี timestamp เท่ากันโดยบังเอิญ ก็เลือกผู้ชนะด้วยการเปรียบเทียบค่า (เช่น ถ้าเป็นสตริง ให้เลือกตัวที่มาก่อนตามลำดับตัวอักษร)

วิธีนี้เรียกว่า last write wins (LWW) เพราะ write ที่มี timestamp มากที่สุดถือเป็นตัว "ล่าสุด" แต่ชื่อนี้ชวนให้เข้าใจผิด เพราะเมื่อ write สองครั้งเป็น concurrent (ดังใน Figure 6-9) จะบอกไม่ได้ว่าอันไหนล่าสุดจริง ลำดับ timestamp ของ concurrent write จึงเป็นการสุ่มโดยพื้นฐาน

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

ถ้าคุณหลีกเลี่ยง conflict ได้ เช่น ด้วยการ insert record ที่มี key ไม่ซ้ำเท่านั้นและไม่เคย update LWW ก็ไม่มีปัญหา แต่ถ้าคุณ update record ที่มีอยู่แล้ว หรือ leader คนละตัวอาจ insert record ที่มี key เดียวกัน คุณต้องตัดสินใจว่าการสูญเสีย update เป็นปัญหาสำหรับแอปพลิเคชันของคุณหรือไม่ ถ้ายอมให้ update หายไม่ได้ ก็ต้องใช้วิธีแก้ conflict ที่อธิบายต่อไป

ปัญหาอีกข้อของ LWW คือถ้าใช้ real-time clock (เช่น Unix timestamp) เป็น timestamp ของ write ระบบจะอ่อนไหวต่อการ sync นาฬิกามาก ถ้า node หนึ่งมีนาฬิกาเดินเร็วกว่าตัวอื่น แล้วคุณพยายามเขียนทับค่าที่ node นั้นเขียนไว้ write ของคุณอาจถูกละเลย เพราะอาจมี timestamp ต่ำกว่า ทั้งที่เกิดขึ้นทีหลังอย่างชัดเจน ปัญหานี้แก้ได้ด้วยการใช้ logical clock ซึ่งเราจะพูดถึงในหัวข้อ "ID Generators และ Logical Clocks"

Manual conflict resolution (การแก้ไข Conflict ด้วยตนเอง)

ถ้าไม่อยากทิ้ง write ของคุณแบบสุ่ม ตัวเลือกถัดไปคือแก้ conflict ด้วยมือ คุณอาจคุ้นกับการแก้ conflict ด้วยมือจาก Git และระบบ version control อื่นอยู่แล้ว ถ้า commit บนสอง branch แก้บรรทัดเดียวกันของไฟล์เดียวกัน แล้วคุณพยายาม merge สอง branch นั้น คุณจะเจอ merge conflict ที่ต้องแก้ก่อน การ merge จึงจะเสร็จ

ในฐานข้อมูล การให้ conflict หยุดกระบวนการ replication ทั้งหมดไว้จนกว่าคนจะมาแก้ เป็นเรื่องที่ทำไม่ได้จริง ฐานข้อมูลมักจะเก็บค่าที่ถูกเขียนพร้อมกันทั้งหมดของ record นั้นไว้แทน เช่น ทั้ง B และ C ใน Figure 6-9 ค่าเหล่านี้บางครั้งเรียกว่า siblings ครั้งต่อไปที่คุณ query record นั้น ฐานข้อมูลจะคืนค่า ทั้งหมด แทนที่จะคืนแค่ค่าล่าสุด จากนั้นคุณจะแก้ค่าเหล่านั้นด้วยวิธีใดก็ได้ ไม่ว่าจะอัตโนมัติในโค้ดแอปพลิเคชัน (เช่น ต่อ B กับ C เป็น B/C) หรือถามผู้ใช้ แล้วเขียนค่าใหม่กลับลงฐานข้อมูลเพื่อปิด conflict

วิธีแก้ conflict แบบนี้ใช้ในบางระบบ เช่น CouchDB แต่ก็มีปัญหาดังนี้:

• API ของฐานข้อมูลเปลี่ยนไป เช่น จากเดิมที่ชื่อของหน้า wiki เป็นแค่ string ก็กลายเป็น set ของ string ที่ปกติมี element เดียว แต่บางครั้งอาจมีหลาย element ถ้ามี conflict ซึ่งอาจทำให้ใช้ข้อมูลนี้ในโค้ดแอปพลิเคชันได้ลำบาก

• การให้ผู้ใช้ merge sibling เองเป็นงานหนักทั้งสำหรับนักพัฒนาแอป (ที่ต้องสร้าง UI สำหรับแก้ conflict) และสำหรับผู้ใช้ (ที่อาจงงว่ากำลังถูกขอให้ทำอะไรและทำไม) ในหลายกรณี การ merge อัตโนมัติดีกว่าการไปรบกวนผู้ใช้

• การ merge sibling อัตโนมัติอาจให้ผลที่น่าประหลาดใจถ้าไม่ระวัง เช่น ตะกร้าสินค้าของ Amazon เคยยอมให้อัปเดตพร้อมกัน แล้วรวมกันด้วยการเก็บทุกรายการที่ปรากฏใน sibling ใดก็ตาม (คือใช้ set union ของตะกร้า) ซึ่งหมายความว่า ถ้าลูกค้าเอาสินค้าออกจากตะกร้าใน sibling หนึ่ง แต่ sibling อื่นยังมีสินค้านั้นอยู่ สินค้าที่ลบไปแล้วก็จะโผล่กลับมาในตะกร้าของลูกค้าโดยไม่คาดคิด [ 45 ] ใน Figure 6-10 อุปกรณ์ 1 ลบ Book ออกจากตะกร้า และอุปกรณ์ 2 ลบ DVD ออกพร้อมกัน แต่หลัง merge sibling แล้ว ทั้งสองรายการก็กลับมาปรากฏอีก

• ถ้าหลาย node สังเกตเห็น conflict และแก้พร้อมกัน กระบวนการแก้ conflict เองก็อาจสร้าง conflict ใหม่ได้ ผลการแก้ของแต่ละ node อาจไม่ตรงกันด้วย เช่น node หนึ่งอาจ merge B กับ C เป็น B/C ขณะที่อีก node merge เป็น C/B ถ้าคุณไม่ระวังเรื่องการเรียงลำดับให้ตรงกัน และเมื่อ merge conflict ระหว่าง B/C กับ C/B ก็อาจได้ B/C/C/B หรืออะไรทำนองนั้นที่น่าประหลาดใจ

Figure 6-10. ตัวอย่างความผิดปกติของตะกร้าสินค้า Amazon: ถ้า merge conflict ด้วย union ของ set รายการที่ถูกลบอาจกลับมาปรากฏอีก

Automatic conflict resolution (การแก้ไข Conflict อัตโนมัติ)

สำหรับแอปพลิเคชันจำนวนมาก วิธีที่ดีที่สุดในการรับมือกับ conflict คือใช้อัลกอริทึมที่ merge concurrent write ให้เป็นสถานะที่สอดคล้องกันโดยอัตโนมัติ การแก้ conflict อัตโนมัติทำให้แน่ใจว่า replica ทั้งหมด converge (ลู่เข้า) สู่สถานะเดียวกัน คือ replica ทั้งหมดที่ประมวลผล write ชุดเดียวกันจะมีสถานะเดียวกัน ไม่ว่า write จะมาถึงในลำดับใด การรวม eventual consistency เข้ากับหลักประกันเรื่อง convergence เรียกว่า strong eventual consistency [ 46 ]

LWW เป็นตัวอย่างง่ายๆ ของอัลกอริทึมแก้ conflict ยังมีอัลกอริทึม merge ที่ซับซ้อนกว่านี้ซึ่งพัฒนาขึ้นสำหรับข้อมูลหลายประเภท โดยมีเป้าหมายรักษาผลที่ตั้งใจของทุกการอัปเดตไว้ให้ได้มากที่สุด และหลีกเลี่ยงการสูญเสียข้อมูล:

• ถ้าข้อมูลเป็นข้อความ (เช่น ชื่อหรือเนื้อหาของหน้า wiki) เราตรวจจับได้ว่าตัวอักษรใดถูกแทรกหรือลบจากเวอร์ชันหนึ่งไปอีกเวอร์ชัน ผลลัพธ์ที่ merge แล้วจะเก็บการแทรกและการลบทั้งหมดที่เกิดใน sibling ใดก็ตามไว้ ถ้าผู้ใช้แทรกข้อความที่ตำแหน่งเดียวกันพร้อมกัน ก็เรียงลำดับแบบ deterministic ได้ เพื่อให้ทุก node ได้ผลลัพธ์เหมือนกัน

• ถ้าข้อมูลเป็น collection ของ item (แบบมีลำดับอย่าง to-do list หรือแบบไม่มีลำดับอย่างตะกร้าสินค้า) เรา merge ได้คล้ายกับข้อความ คือติดตามการแทรกและการลบ เพื่อเลี่ยงปัญหาตะกร้าสินค้าใน Figure 6-10 อัลกอริทึมจะบันทึกว่า Book และ DVD ถูกลบไปแล้ว ผลลัพธ์ที่ merge จึงเป็น Cart = {Soap}

• ถ้าข้อมูลเป็น integer ที่เป็น counter เพิ่มหรือลดค่าได้ (เช่น จำนวนไลค์ของโพสต์บนโซเชียลมีเดีย) อัลกอริทึม merge จะรู้ว่าแต่ละ sibling มีการเพิ่มและลดกี่ครั้ง แล้วรวมกันอย่างถูกต้อง ผลลัพธ์จึงไม่นับซ้ำและไม่ทิ้ง update

• ถ้าข้อมูลเป็น key-value mapping เรา merge update ของ key เดียวกันได้ โดยใช้อัลกอริทึมแก้ conflict แบบอื่นอย่างใดอย่างหนึ่งกับค่าภายใต้ key นั้น ส่วน update ของ key ต่างกันจัดการแยกจากกันได้

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

Conflict-free replicated datatypes and operational transformation (CRDTs และ Operational Transformation)

อัลกอริทึมสอง ตระกูลที่ใช้กันทั่วไปในการ implement การแก้ conflict อัตโนมัติ คือ conflict-free replicated datatypes (CRDTs) [ 46 ] และ operational transformation (OT) [ 47 ] ทั้งสองมีปรัชญาการออกแบบและลักษณะด้านประสิทธิภาพต่างกัน แต่ merge อัตโนมัติได้กับข้อมูลทุกประเภทที่กล่าวมาข้างต้น

Figure 6-11 แสดงตัวอย่างว่า OT และ CRDT merge update ที่เกิดพร้อมกันบนข้อความอย่างไร สมมติว่ามี replica สองตัวที่เริ่มด้วยข้อความ ice replica ตัวหนึ่งเติมตัวอักษร n ไว้ข้างหน้าเป็น nice ขณะเดียวกันอีกตัวต่อท้ายด้วยเครื่องหมายอัศเจรีย์เป็น ice!

Figure 6-11. OT และ CRDT merge การแทรกข้อความสองครั้งที่เกิดพร้อมกันอย่างไร (ตามลำดับ)

อัลกอริทึมสองประเภทได้ผลลัพธ์ที่ merge แล้วเป็น nice! เหมือนกัน แต่ใช้วิธีต่างกัน:

OT

เราบันทึก index ที่ตัวอักษรถูกแทรกหรือลบ: n ถูกแทรกที่ index 0 และ ! ที่ index 3 จากนั้น replica แลกเปลี่ยน operation กัน การแทรก n ที่ index 0 apply ได้ตามเดิม แต่ถ้า apply การแทรก ! ที่ index 3 กับสถานะ nice, เราจะได้ nic!e, ซึ่งไม่ถูกต้อง เราจึงต้องแปลง index ของแต่ละ operation ให้คำนึงถึง operation ที่เกิดพร้อมกันและถูก apply ไปแล้ว ในกรณีนี้ การแทรก ! ถูกแปลงเป็น index 4 เพื่อชดเชยการแทรก n ที่ index ก่อนหน้า

CRDT

CRDT ส่วนใหญ่ให้ตัวอักษรแต่ละตัวมี ID ที่ไม่ซ้ำและ immutable แล้วใช้ ID เหล่านั้นระบุตำแหน่งของการแทรก/การลบ แทนการใช้ index ตัวอย่างเช่น ใน Figure 6-11 เรากำหนด ID 1A ให้ i, ID 2A ให้ c, ฯลฯ เมื่อแทรกเครื่องหมายอัศเจรีย์ เราสร้าง operation ที่ประกอบด้วย ID ของตัวอักษรใหม่ (4B) และ ID ของตัวอักษรเดิมที่เราต้องการแทรกต่อท้าย (3A) ถ้าจะแทรกที่ต้นสตริง เราให้ nil เป็น ID ของตัวอักษรก่อนหน้า การแทรกที่เกิดพร้อมกันที่ตำแหน่งเดียวกันจะเรียงตาม ID ของตัวอักษร ทำให้ replica converge ได้โดยไม่ต้องแปลงอะไรเลย

อัลกอริทึมจำนวนมากพัฒนามาจากแนวคิดเหล่านี้ list และ array รองรับได้ในลักษณะเดียวกัน โดยใช้ element ของ list แทนตัวอักษร และ datatype อื่นๆ เช่น key-value map ก็เพิ่มเข้าไปได้ค่อนข้างง่าย OT และ CRDT มี trade-off ด้านประสิทธิภาพและฟังก์ชันการทำงานอยู่บ้าง แต่ก็เป็นไปได้ที่จะรวมข้อดีของทั้งสองไว้ในอัลกอริทึมเดียว [ 48 ]

OT มักใช้กับการแก้ไขข้อความร่วมกันแบบ real-time เช่นใน Google Docs [ 32 ] ส่วน CRDT พบได้ในฐานข้อมูลแบบกระจาย เช่น Redis Enterprise, Riak และ Azure Cosmos DB [ 49 ] sync engine สำหรับข้อมูล JSON implement ได้ทั้งด้วย CRDT (เช่น Automerge หรือ Yjs) และ OT (เช่น ShareDB)

Types of conflict (ประเภทของ Conflict)

conflict บางแบบเห็นได้ชัด ในตัวอย่างของ Figure 6-9 write สองครั้งแก้ field เดียวกันใน record เดียวกันพร้อมกัน โดยตั้งเป็นสองค่าที่ต่างกัน ไม่ต้องสงสัยเลยว่านี่คือ conflict

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

ไม่มีคำตอบสำเร็จรูปที่ได้ทันที แต่ในบทต่อๆ ไป เราจะค่อยๆ สร้างความเข้าใจที่ดีต่อปัญหานี้ เราจะเห็นตัวอย่าง conflict เพิ่มเติมใน บทที่ 8 และใน บทที่ 13 จะพูดถึงแนวทางที่ scalable สำหรับตรวจจับและแก้ conflict ในระบบที่ทำ replication

Leaderless Replication (การจำลองแบบไร้ผู้นำ)

แนวทาง replication ที่เราพูดถึงมาตลอดบทนี้ ทั้ง single-leader และ multi-leader replication อยู่บนแนวคิดที่ว่า client ส่ง write request ไปที่ node หนึ่ง (leader) แล้วระบบฐานข้อมูลดูแลการคัดลอก write นั้นไปยัง replica อื่น leader เป็นผู้กำหนดลำดับที่ต้องประมวลผล write และ follower apply write ของ leader ตามลำดับเดียวกัน

ระบบจัดเก็บข้อมูลบางตัวใช้แนวทางต่างออกไป โดยทิ้งแนวคิดเรื่อง leader และให้ replica ตัวไหนก็รับ write จาก client ได้โดยตรง ระบบข้อมูลแบบ replicated รุ่นแรกๆ บางระบบเป็นแบบ leaderless [ 1, 50 ] แต่แนวคิดนี้ถูกลืมไปเป็นส่วนใหญ่ในยุคที่ relational database ครองตลาด และกลับมาเป็นสถาปัตยกรรมยอดนิยมสำหรับฐานข้อมูลอีกครั้งหลังจาก Amazon ใช้กับระบบ Dynamo ภายในของตัวเองในปี 2007 [ 45 ] Riak, Cassandra, และ ScyllaDB เป็น datastore แบบ open source ที่มีโมเดล leaderless replication ซึ่งได้แรงบันดาลใจจาก Dynamo ฐานข้อมูลประเภทนี้จึงเรียกว่า Dynamo-style

หมายเหตุ

สถาปัตยกรรมของระบบ Dynamo ดั้งเดิมถูกอธิบายไว้ในบทความ [ 45 ] แต่ไม่เคยเปิดตัวนอก Amazon ส่วน DynamoDB ที่ชื่อคล้ายกันและเป็นฐานข้อมูลบนคลาวด์รุ่นใหม่กว่าของ Amazon มีสถาปัตยกรรมต่างออกไปโดยสิ้นเชิง คือใช้ single-leader replication บนพื้นฐานของ consensus algorithm แบบ Multi-Paxos [ 5, 51 ]

ใน leaderless implementation บางแบบ client ส่ง write ไปที่ replica หลายตัวโดยตรง ส่วนบางแบบมี node coordinator ทำหน้าที่นี้แทน client แต่ต่างจากฐานข้อมูลแบบมี leader ตรงที่ coordinator ไม่ได้บังคับลำดับของ write ดังที่เราจะเห็น ความต่างในการออกแบบนี้ส่งผลอย่างลึกซึ้งต่อวิธีใช้งานฐานข้อมูล

Writing to the Database When a Node Is Down (การเขียนข้อมูลเมื่อ Node ไม่ทำงาน)

ลองนึกภาพ ว่าคุณมีฐานข้อมูลที่มีสาม replica และหนึ่งในนั้นใช้งานไม่ได้อยู่ชั่วคราว เช่น กำลัง reboot เพื่อติดตั้งอัปเดตระบบ ถ้าเป็น single-leader และคุณต้องการประมวลผล write ต่อไป คุณอาจต้องทำ failover (ดูหัวข้อ "การจัดการเมื่อ Node หยุดทำงาน")

ในทางกลับกัน ถ้าเป็น leaderless จะไม่มี failover เลย เพราะ replica ทั้งหมดเท่าเทียมกันและไม่มี leader Figure 6-12 แสดงสิ่งที่เกิดขึ้น

Figure 6-12. เขียนไปยัง replica ส่วนใหญ่ อ่านจากส่วนใหญ่ และส่งค่าล่าสุดต่อไปยัง replica ที่ใช้งานไม่ได้ระหว่างที่เขียน

client (ผู้ใช้ 1234) ส่ง write ไปที่ทั้งสาม replica แบบขนาน replica สองตัวที่ใช้งานได้รับ write ส่วน replica ที่ใช้งานไม่ได้พลาด write นั้นไป สมมติว่าแค่ได้ acknowledgment จากสองในสาม replica ก็เพียงพอ หลังผู้ใช้ 1234 ได้รับ response OK สองครั้ง เราถือว่า write สำเร็จ และ client ก็แค่ไม่สนใจว่ามี replica หนึ่งที่พลาด write ไป

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

เพื่อแก้ปัญหานั้น เมื่อ client อ่านจากฐานข้อมูล มันไม่ได้ส่ง request ไปที่ replica เดียว แต่ read request ก็ถูกส่งไปหลาย node แบบขนานด้วย client อาจได้ response ต่างกันจากแต่ละ node เช่น ค่าล่าสุดจาก node หนึ่งและค่าที่ล้าสมัยจากอีก node

เพื่อให้ client บอกได้ว่า response ไหนล่าสุดและไหนล้าสมัย ทุกค่าที่เขียนต้องถูกติดแท็กด้วยหมายเลขเวอร์ชันหรือ timestamp คล้ายกับที่เราเห็นในหัวข้อ "Last Write Wins: การทิ้ง Concurrent Writes" เมื่อ client ได้หลายค่ากลับมาจากการอ่าน มันจะใช้ค่าที่มี timestamp มากที่สุด (แม้ค่านั้นจะมาจาก replica เพียงตัวเดียว ขณะที่ replica อื่นอีกหลายตัวคืนค่าที่เก่ากว่า) ดูหัวข้อ "การตรวจจับ Concurrent Writes" สำหรับรายละเอียดเพิ่มเติม

Catching up on missed writes (การตามทัน writes ที่พลาดไป)

ระบบ replication ควรทำให้แน่ใจว่าในที่สุดข้อมูลทั้งหมดจะถูกคัดลอกไปยังทุก replica หลังจาก node ที่ใช้งานไม่ได้กลับมาออนไลน์ มันจะตามทัน write ที่พลาดไปได้อย่างไร? datastore แบบ Dynamo ใช้กลไกหลายอย่าง:

Read Repair

เมื่อ client อ่านจากหลาย node แบบขนาน ก็ตรวจจับ response ที่ล้าสมัยได้ เช่น ใน Figure 6-12 ผู้ใช้ 2345 ได้ค่าเวอร์ชัน 6 จาก replica 3 และค่าเวอร์ชัน 7 จาก replica 1 และ 2 client เห็นว่า replica 3 มีค่าที่ล้าสมัย จึงเขียนค่าใหม่กลับไปที่ replica นั้น วิธีนี้ใช้ได้ผลดีกับค่าที่ถูกอ่านบ่อย

Hinted Handoff

ถ้า replica หนึ่งใช้งานไม่ได้ replica อื่นอาจเก็บ write แทนมันไว้ในรูปของ hint เมื่อ replica ที่ควรได้รับ write เหล่านั้นกลับมา replica ที่เก็บ hint ไว้จะส่ง hint ให้ replica ที่กลับมา แล้วลบ hint ทิ้ง กระบวนการ handoff นี้ช่วยให้ replica เป็นปัจจุบัน แม้แต่กับค่าที่ไม่เคยถูกอ่านและจึงไม่ถูกจัดการโดย read repair

Anti-Entropy

นอกจากนี้ background process จะคอยหาความแตกต่างของข้อมูลระหว่าง replica เป็นระยะ แล้วคัดลอกข้อมูลที่ขาดจาก replica หนึ่งไปอีกตัว ต่างจาก replication log ใน leader-based replication กระบวนการ anti-entropy นี้ไม่ได้คัดลอก write ตามลำดับใดโดยเฉพาะ และอาจต้องรอนานพอสมควรกว่าข้อมูลจะถูกคัดลอก

Using quorums for reading and writing (การใช้ Quorum สำหรับการอ่านและเขียน)

ใน Figure 6-12 เราถือว่า write สำเร็จ ทั้งที่ประมวลผลบนเพียงสองในสาม replica แล้วถ้ามีเพียงหนึ่งในสาม replica ที่รับ write ล่ะ? เราจะผลักดันเรื่องนี้ได้ไกลแค่ไหน?

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

โดยทั่วไป ถ้ามี n replica ทุก write ต้องได้รับการยืนยันจาก w node จึงจะถือว่าสำเร็จ และเราต้อง query อย่างน้อย r node สำหรับการอ่านแต่ละครั้ง (ในตัวอย่างของเรา n = 3, w = 2, r = 2) ตราบใดที่ w + r > n เราคาดว่าจะได้ค่าล่าสุดตอนอ่าน เพราะอย่างน้อยหนึ่งใน r node ที่เราอ่านต้องเป็นข้อมูลล่าสุด การอ่านและเขียนที่เป็นไปตามค่า r และ w เหล่านี้เรียกว่า quorum read และ write [ 50 ] คุณอาจมอง r และ w เป็นจำนวนโหวตขั้นต่ำที่ต้องมีเพื่อให้การอ่านหรือเขียนนั้นใช้ได้

ในฐานข้อมูลแบบ Dynamo พารามิเตอร์ n, w และ r มักปรับตั้งค่าได้ ตัวเลือกที่พบบ่อยคือให้ n เป็นเลขคี่ (มักเป็น 3 หรือ 5) และตั้ง w = r = (n + 1) / 2 (ปัดขึ้น) แต่จะปรับตัวเลขตามที่เห็นสมควรก็ได้ เช่น workload ที่มี write น้อยและ read มากอาจได้ประโยชน์จากการตั้ง w = n และ r = 1 ซึ่งทำให้อ่านเร็วขึ้น แต่มีข้อเสียคือแค่ node เดียวล้มก็ทำให้ write ทั้งหมดของฐานข้อมูลล้มเหลว

หมายเหตุ

ใน cluster อาจมี node มากกว่า n ตัว แต่ค่าหนึ่งๆ จะถูกเก็บบนเพียง n node ซึ่งทำให้ชุดข้อมูลถูก shard ได้ และรองรับชุดข้อมูลที่ใหญ่เกินกว่าจะใส่ใน node เดียวได้ เราจะกลับมาพูดถึง sharding ใน บทที่ 7

เงื่อนไข quorum w + r > n ทำให้ระบบทนต่อ node ที่ใช้งานไม่ได้ดังนี้:

• ถ้า w < n เรายังประมวลผล write ได้แม้ node หนึ่งใช้งานไม่ได้

• ถ้า r < n เรายังประมวลผล read ได้แม้ node หนึ่งใช้งานไม่ได้

• ด้วย n = 3, w = 2, r = 2 เราทนต่อ node ที่ใช้งานไม่ได้หนึ่งตัวได้ ดังใน Figure 6-12

• ด้วย n = 5, w = 3, r = 3 เราทนต่อ node ที่ใช้งานไม่ได้สองตัวได้ กรณีนี้แสดงใน Figure 6-13

Figure 6-13. ถ้า w + r > n อย่างน้อยหนึ่งใน r replica ที่คุณอ่านต้องเห็น write ที่สำเร็จล่าสุด

โดยปกติ read และ write จะถูกส่งไปยัง n replica ทั้งหมดแบบขนานเสมอ พารามิเตอร์ w และ r กำหนดว่าเรารอกี่ node คือมี node กี่ตัวจาก n ตัวที่ต้องรายงานว่าสำเร็จ เราจึงจะถือว่าการอ่านหรือเขียนนั้นสำเร็จ

ถ้ามี node พร้อมใช้งานน้อยกว่า w หรือ r ที่ต้องการ write หรือ read จะคืนข้อผิดพลาด node อาจใช้งานไม่ได้ด้วยหลายสาเหตุ เช่น node หยุดทำงาน (เช่น crash หรือปิดเครื่อง) เกิดข้อผิดพลาดระหว่างทำ operation (เช่น เขียนไม่ได้เพราะดิสก์เต็ม) เครือข่ายระหว่าง client กับ node ขัดข้อง หรือสาเหตุอื่นอีกมากมาย เราสนใจเพียงว่า node ตอบกลับว่าสำเร็จหรือไม่ และไม่จำเป็นต้องแยกว่าเป็นความผิดพลาดชนิดใด

Understanding the limitations of quorum consistency (ข้อจำกัดของ Quorum Consistency)

ถ้าคุณมี n replica และเลือก w กับ r ให้ w + r > n โดยทั่วไปคุณคาดหวังได้ว่าทุกการอ่านจะคืนค่าล่าสุดที่เขียนไว้สำหรับ key นั้น เพราะเซตของ node ที่คุณเขียนกับเซตของ node ที่คุณอ่านต้องทับซ้อนกัน นั่นคือในบรรดา node ที่คุณอ่าน ต้องมีอย่างน้อยหนึ่ง node ที่มีค่าล่าสุด (ดังที่แสดงใน Figure 6-13)

บ่อยครั้ง r และ w จะถูกเลือกให้เป็นเสียงข้างมาก (มากกว่า n / 2) ของ node เพราะรับประกัน w + r > n พร้อมกับทนต่อ node ล้มเหลวได้ถึง n / 2 (ปัดลง) แต่ quorum ไม่จำเป็นต้องเป็นเสียงข้างมากเสมอไป สิ่งสำคัญคือเซตของ node ที่ operation อ่านและเขียนใช้ทับซ้อนกันอย่างน้อยหนึ่ง node การกำหนด quorum แบบอื่นก็เป็นไปได้ ซึ่งทำให้ออกแบบอัลกอริทึมแบบกระจายได้ยืดหยุ่นขึ้น [ 52 ]

คุณอาจตั้ง w และ r ให้เล็กลง จน w + r ≤ n (คือไม่เป็นไปตามเงื่อนไข quorum) ก็ได้ ในกรณีนี้ read และ write ยังคงถูกส่งไปที่ n node แต่ต้องการ response ที่สำเร็จน้อยลงเพื่อให้ operation สำเร็จ

ถ้า w และ r เล็กลง คุณมีแนวโน้มจะอ่านเจอค่าที่ล้าสมัยมากขึ้น เพราะมีโอกาสมากขึ้นที่การอ่านของคุณจะไม่รวม node ที่มีค่าล่าสุด ข้อดีคือการตั้งค่านี้ทำให้ latency ต่ำลง ซึ่งเป็นประโยชน์โดยเฉพาะกับ synchronous (blocking) replication การตั้งค่านี้ยังมี availability สูงขึ้นด้วย ถ้าเครือข่ายขัดข้องจน replica จำนวนมากเข้าถึงไม่ได้ ก็มีโอกาสมากขึ้นที่คุณจะประมวลผล read และ write ต่อไปได้ ฐานข้อมูลจะใช้เขียนหรืออ่านไม่ได้ ก็ต่อเมื่อจำนวน replica ที่เข้าถึงได้ต่ำกว่า w หรือ r ตามลำดับ

อย่างไรก็ตาม แม้จะมี w + r > n คุณสมบัติด้าน consistency ก็อาจสร้างความสับสนได้ในบาง edge case ตัวอย่างสถานการณ์ได้แก่:

• ถ้า node ที่ถือค่าใหม่ล้มเหลว แล้วข้อมูลของมันถูกกู้คืนจาก replica ที่ถือค่าเก่า จำนวน replica ที่เก็บค่าใหม่อาจลดลงต่ำกว่า w ทำให้เงื่อนไข quorum ใช้ไม่ได้

• ขณะที่กำลัง rebalancing ซึ่งข้อมูลบางส่วนถูกย้ายจาก node หนึ่งไปอีก node (ดู บทที่ 7) node ต่างๆ อาจเห็นไม่ตรงกันว่า node ไหนควรถือ n replica ของค่าหนึ่งๆ ซึ่งอาจทำให้ read quorum และ write quorum ไม่ทับซ้อนกันอีกต่อไป

• ถ้าการอ่านเกิดพร้อมกับการเขียน การอ่านนั้นอาจเห็นหรือไม่เห็นค่าที่เขียนพร้อมกันก็ได้ โดยเฉพาะอย่างยิ่ง เป็นไปได้ที่การอ่านครั้งหนึ่งจะเห็นค่าใหม่ แต่การอ่านครั้งถัดไปกลับเห็นค่าเก่า ดังที่เราจะเห็นในหัวข้อ "การ Implement ระบบ Linearizable"

• ถ้า write สำเร็จบนบาง replica แต่ล้มเหลวบนบางตัว (เช่น เพราะดิสก์บางเครื่องเต็ม) และโดยรวมสำเร็จน้อยกว่า w replica write นั้นจะไม่ถูก roll back บน replica ที่สำเร็จ ซึ่งหมายความว่าถ้า write ถูกรายงานว่าล้มเหลว การอ่านครั้งหลังอาจคืนหรือไม่คืนค่าจาก write นั้นก็ได้ [ 53 ]

• ถ้าฐานข้อมูลใช้ timestamp จาก real-time clock เพื่อตัดสินว่า write ไหนใหม่กว่า (เช่น Cassandra และ ScyllaDB ที่ทำแบบนี้) write อาจถูกทิ้งไปเงียบๆ ถ้ามี node อื่นที่นาฬิกาเร็วกว่าเขียนลง key เดียวกัน ซึ่งเป็นปัญหาที่เราเห็นไปแล้วในหัวข้อ "Last Write Wins: การทิ้ง Concurrent Writes" เราจะพูดถึงรายละเอียดเพิ่มเติมในหัวข้อ "การพึ่งพา Synchronized Clocks"

• ถ้า write สองครั้งเกิดขึ้นพร้อมกัน ครั้งหนึ่งอาจถูกประมวลผลก่อนบน replica ตัวหนึ่ง ขณะที่อีกครั้งอาจถูกประมวลผลก่อนบน replica อีกตัว ซึ่งนำไปสู่ conflict คล้ายกับที่เราเห็นใน multi-leader replication (ดูหัวข้อ "การจัดการกับ Write Conflicts") เราจะกลับมาที่ประเด็นนี้ในหัวข้อ "การตรวจจับ Concurrent Writes"

ดังนั้น แม้ quorum จะดูเหมือนรับประกันว่าการอ่านจะคืนค่าล่าสุดที่เขียน แต่ในทางปฏิบัติไม่ง่ายอย่างนั้น ฐานข้อมูลแบบ Dynamo มักถูกปรับให้เหมาะกับ use case ที่ทนต่อ eventual consistency ได้ พารามิเตอร์ w และ r ช่วยให้คุณปรับความน่าจะเป็นที่จะอ่านเจอค่าที่ล้าสมัย [ 54 ] แต่ก็ไม่ควรถือว่าเป็นหลักประกันที่แน่นอน

Monitoring staleness (การติดตามความเก่าของข้อมูล)

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

สำหรับ leader-based replication ฐานข้อมูลมักเปิดเผย metric ของ replication lag ซึ่งคุณส่งเข้าระบบ monitoring ได้ ทำได้เพราะ write ถูก apply บน leader และ follower ในลำดับเดียวกัน และแต่ละ node มีตำแหน่งใน replication log (จำนวน write ที่มัน apply ในเครื่อง) เมื่อเอาตำแหน่งปัจจุบันของ follower ไปลบจากตำแหน่งปัจจุบันของ leader คุณก็วัด replication lag ได้

แต่ในระบบ leaderless replication ไม่มีลำดับตายตัวที่ write ถูก apply ทำให้ monitor ยากขึ้น จำนวน hint ที่ replica เก็บไว้สำหรับ handoff เป็นตัวชี้วัดสุขภาพของระบบได้อย่างหนึ่ง แต่ตีความให้เป็นประโยชน์ได้ยาก [ 55 ] Eventual consistency เป็นหลักประกันที่ตั้งใจให้คลุมเครือ แต่ในแง่การ operate สิ่งสำคัญคือต้อง วัดค่าของคำว่า "eventual" ออกมาเป็นตัวเลขได้

Single-Leader Versus Leaderless Replication Performance (ประสิทธิภาพของ Single-Leader เทียบกับ Leaderless)

ระบบ replication ที่ใช้ leader เดียวให้หลักประกัน consistency ที่แข็งแรงได้ ซึ่งในระบบ leaderless ทำได้ยากหรือเป็นไปไม่ได้ แต่ดังที่เราเห็นในหัวข้อ "ปัญหาจาก Replication Lag" การอ่านในระบบแบบ leader-based ก็คืนค่าที่ล้าสมัยได้เช่นกัน ถ้าคุณอ่านจาก follower ที่อัปเดตแบบ asynchronous

การอ่านจาก leader รับประกันว่าได้ response ล่าสุด แต่ก็มีปัญหาด้านประสิทธิภาพ:

• read throughput ถูกจำกัดด้วยความสามารถของ leader ในการจัดการ request (ต่างจาก read scaling ที่กระจาย read ไปยัง replica ที่อัปเดตแบบ asynchronous ซึ่งอาจคืนค่าที่ล้าสมัย)

• ถ้า leader ล้มเหลว คุณต้องรอให้ตรวจพบความผิดพลาดและ failover เสร็จก่อน จึงจะรับ request ต่อได้ แม้ failover จะเร็วมาก ผู้ใช้ก็ยังสังเกตเห็นเพราะ response time เพิ่มขึ้นชั่วคราว และถ้า failover ใช้เวลานาน ระบบก็ใช้งานไม่ได้ตลอดช่วงนั้น

• ระบบอ่อนไหวมากต่อปัญหาด้านประสิทธิภาพบน leader ถ้า leader ตอบช้า (เช่น เพราะโอเวอร์โหลดหรือแย่งทรัพยากรกัน) response time ที่เพิ่มขึ้นก็กระทบผู้ใช้ทันทีเช่นกัน

ข้อดีใหญ่ของสถาปัตยกรรม leaderless คือทนต่อปัญหาเหล่านี้ได้ดีกว่า เพราะไม่มี failover และ request ก็ถูกส่งไปหลาย replica แบบขนานอยู่แล้ว replica ที่ช้าหรือใช้งานไม่ได้เพียงตัวเดียวจึงกระทบ response time น้อยมาก client แค่ใช้ response จาก replica อื่นที่ตอบเร็วกว่า การใช้ response ที่เร็วที่สุดนี้เรียกว่า request hedging และช่วยลด tail latency ได้อย่างมาก [ 56 ]

หัวใจของความทนทานในระบบ leaderless คือมันไม่แยกระหว่างกรณีปกติกับกรณีล้มเหลว ซึ่งมีประโยชน์เป็นพิเศษเมื่อเจอ gray failure ที่ node ไม่ได้ล่มสนิท แต่ทำงานในสถานะเสื่อมประสิทธิภาพที่ช้าผิดปกติเวลาจัดการ request [ 57 ] หรือเมื่อ node แค่โอเวอร์โหลด (เช่น ถ้า node ออฟไลน์ไปพักหนึ่ง การกู้คืนผ่าน hinted handoff อาจทำให้เกิดโหลดเพิ่มอีกมาก) ระบบ leader-based ต้องตัดสินใจว่าสถานการณ์แย่พอจะต้อง failover หรือไม่ (ซึ่งอาจก่อให้เกิดการหยุดชะงักเพิ่มเติมได้เอง) ขณะที่ในระบบ leaderless คำถามนี้ไม่เกิดขึ้นเลย

ระบบ leaderless ก็มีปัญหาด้านประสิทธิภาพได้เช่นกัน:

• แม้ระบบไม่ต้องทำ failover แต่ replica ตัวหนึ่งก็ยังต้องตรวจจับว่า replica อื่นใช้งานไม่ได้ เพื่อจะเก็บ hint ของ write ที่ replica นั้นพลาดไป เมื่อ replica ที่ใช้งานไม่ได้กลับมา กระบวนการ handoff ต้องส่ง hint เหล่านั้นไปให้ ซึ่งเพิ่มโหลดบน replica ในช่วงที่ระบบกำลังรับภาระหนักอยู่แล้ว [ 55 ]

• ยิ่งมี replica มาก quorum ก็ยิ่งใหญ่ขึ้น และต้องรอ response มากขึ้นกว่า request จะเสร็จ แม้คุณจะรอเฉพาะ r หรือ w replica ที่เร็วที่สุด และส่ง request แบบขนาน แต่ r หรือ w ที่ใหญ่ขึ้นก็เพิ่มโอกาสที่จะเจอ replica ที่ช้า ทำให้ response time โดยรวมเพิ่มขึ้น (ดูหัวข้อ "การใช้ Metrics เวลาตอบสนอง") ในทางปฏิบัติ quorum มักไม่เกินสี่ในเจ็ด node หรือห้าในเก้า node

• เครือข่ายขัดข้องขนาดใหญ่ที่ตัด client ออกจาก replica จำนวนมากอาจทำให้สร้าง quorum ไม่ได้ ฐานข้อมูล leaderless บางตัวมี configuration option ที่ให้ replica ตัวไหนก็ได้ที่เข้าถึงได้รับ write แม้จะไม่ใช่ replica ตามปกติของ key นั้น (Riak และ Dynamo เรียกว่า sloppy quorum [ 45 ]; Cassandra และ ScyllaDB เรียกว่า consistency level ANY) ไม่มีการรับประกันว่าการอ่านครั้งหลังจะเห็นค่าที่เขียน แต่ขึ้นอยู่กับแอปพลิเคชัน วิธีนี้อาจยังดีกว่าปล่อยให้ write ล้มเหลว

Multi-leader replication อาจทนต่อเครือข่ายขัดข้องได้ดีกว่า leaderless replication เสียอีก เพราะ read และ write ต้องติดต่อกับ leader เพียงตัวเดียว ซึ่งอาจอยู่ใกล้ client ได้ แต่เนื่องจาก write บน leader หนึ่งถูกกระจายไปยังตัวอื่นแบบ asynchronous การอ่านจึงอาจล้าสมัยเท่าไรก็ได้ Quorum read และ write เป็นทางสายกลาง คือมี fault tolerance ที่ดีและมีโอกาสสูงที่จะอ่านได้ข้อมูลล่าสุด

Multi-Region Operation (การทำงานแบบหลายภูมิภาค)

เราเคยพูดถึง cross-region replication ในฐานะ use case ของ multi-leader replication (ดูหัวข้อ "การจำลองแบบ Multi-Leader") Leaderless replication ก็เหมาะกับการทำงานแบบหลาย region เช่นกัน เพราะถูกออกแบบให้ทนต่อ concurrent write ที่ขัดแย้งกัน เครือข่ายขัดข้อง และ latency spike

ใน Cassandra และ ScyllaDB client ที่ต้องการทำ multi-region write จะเลือก node ใน region ของตัวเองก่อน เรียกว่า coordinator node แล้วส่ง write ไปที่ node นั้น coordinator node จะส่งต่อ write ไปยัง replica ทั้งหมดใน region ของตัวเอง และไปยัง replica หนึ่งตัวในแต่ละ region อื่น ซึ่งจะส่งต่อไปยัง replica ตัวอื่นใน region นั้นอีกที การปรับแต่งนี้ช่วยเลี่ยงการส่ง request ข้าม region หลายครั้ง

คุณเลือก consistency level ได้หลายระดับ ซึ่งกำหนดว่าต้องได้ response กี่ตัว request จึงจะสำเร็จ เช่น ขอ quorum ข้ามทุก replica ในทุก region, ขอ quorum แยกในแต่ละ region หรือขอ quorum เฉพาะใน region ของ client เอง local quorum ช่วยเลี่ยงการรอ request ที่ช้าไปยัง region อื่น แต่ก็มีแนวโน้มจะคืนผลลัพธ์ที่ล้าสมัยมากกว่า

Riak เก็บการสื่อสารทั้งหมดระหว่าง client กับ node ของฐานข้อมูลไว้ภายใน region เดียว n จึงหมายถึงจำนวน replica ภายในหนึ่ง region ส่วน cross-region replication ระหว่าง database cluster เกิดขึ้นแบบ asynchronous เบื้องหลัง ในรูปแบบที่คล้ายกับ multi-leader replication

Detecting Concurrent Writes (การตรวจจับ Concurrent Writes)

เช่นเดียวกับ multi-leader replication ฐานข้อมูล leaderless ยอมให้ write ลง key เดียวกันพร้อมกันได้ ทำให้เกิด conflict ที่ต้องแก้ conflict เหล่านี้อาจถูกตรวจพบตอนที่ write เกิดขึ้น แต่ก็ไม่เสมอไป อาจตรวจพบทีหลังระหว่าง read repair, hinted handoff หรือ anti-entropy ก็ได้

ปัญหาคือ event อาจมาถึงแต่ละ node ในลำดับที่ต่างกัน เพราะความหน่วงของเครือข่ายที่ไม่คงที่และความล้มเหลวบางส่วน เช่น Figure 6-14 แสดง client สองตัวคือ A และ B ที่เขียนลง key X ใน datastore สาม node พร้อมกัน:

• Node 1 ได้รับ write จาก A แต่ไม่เคยได้รับ write จาก B เพราะหยุดทำงานชั่วคราว

• Node 2 ได้รับ write จาก A ก่อน แล้วจึงได้รับ write จาก B

• Node 3 ได้รับ write จาก B ก่อน แล้วจึงได้รับ write จาก A

ถ้าแต่ละ node แค่เขียนทับค่าของ key ทุกครั้งที่ได้รับ write request จาก client node ต่างๆ จะไม่สอดคล้องกันถาวร ดังที่เห็นจาก get request สุดท้ายใน Figure 6-14 คือ node 2 คิดว่าค่าสุดท้ายของ X เป็น B ขณะที่ node อื่นคิดว่าเป็น A

เพื่อให้เป็น eventually consistent ได้ replica ควร converge ไปสู่ค่าเดียวกัน ซึ่งทำได้ด้วยกลไกแก้ conflict ที่เราเคยพูดถึงในหัวข้อ "การจัดการกับ Write Conflicts" เช่น LWW (ที่ Cassandra และ ScyllaDB ใช้) การแก้ด้วยมือ หรือ CRDT (ที่ Riak ใช้)

Figure 6-14. Concurrent write ใน datastore แบบ Dynamo: ไม่มีลำดับที่นิยามไว้ชัดเจน

LWW implement ง่าย แต่ละ write ถูกติดแท็ก timestamp และค่าที่มี timestamp สูงกว่าจะเขียนทับค่าที่มี timestamp ต่ำกว่าเสมอ แต่ timestamp ไม่ได้บอกว่าสองค่านั้นขัดแย้งกันจริงหรือไม่ (คือเขียนพร้อมกัน) หรือเขียนต่อเนื่องกัน (ทีละอัน) ถ้าคุณต้องการแก้ conflict อย่างชัดเจน ระบบต้องระวังมากขึ้นในการตรวจจับ concurrent write

The happens-before relation and concurrency (ความสัมพันธ์แบบ Happens-Before และ Concurrency)

เราจะตัดสินได้อย่างไรว่า operation สองตัวเป็น concurrent? เพื่อสร้างความเข้าใจเชิงสัญชาตญาณ มาดูตัวอย่างกัน:

• ใน Figure 6-8 write สองครั้งไม่ใช่ concurrent เพราะการ insert ของ A เกิดขึ้นก่อน การ increment ของ B ค่าที่ B increment คือค่าที่ A insert ไว้ พูดอีกอย่างคือ operation ของ B สร้างต่อจาก operation ของ A ดังนั้น operation ของ B ต้องเกิดขึ้นทีหลัง เรายังพูดได้ว่า B มี causal dependency กับ A

• ในทางกลับกัน writes สองครั้งใน Figure 6-14 เป็น concurrent เพราะตอนที่ client แต่ละตัวเริ่ม operation ไม่รู้ว่ามี client อื่นกำลังทำ operation บน key เดียวกันอยู่ด้วย จึงไม่มี causal dependency ระหว่าง operation ทั้งสอง

operation A เกิดขึ้นก่อน operation B ถ้า B รู้เรื่องของ A หรือขึ้นอยู่กับ A หรือสร้างต่อจาก A ในทางใดทางหนึ่ง การที่ operation หนึ่งเกิดก่อนอีกตัวหรือไม่ เป็นกุญแจสำคัญในการนิยามว่า concurrency หมายถึงอะไร อันที่จริง เราพูดได้ง่ายๆ ว่า operation สองตัวเป็น concurrent ถ้าไม่มีตัวใดเกิดก่อนอีกตัว [ 58 ]

ดังนั้นเมื่อมี operation สองตัวคือ A และ B จะมีความเป็นไปได้สามอย่าง คือ A เกิดก่อน B หรือ B เกิดก่อน A หรือ A กับ B เป็น concurrent สิ่งที่เราต้องการคืออัลกอริทึมที่บอกได้ว่า operation สองตัวเป็น concurrent หรือไม่ ถ้าตัวหนึ่งเกิดก่อนอีกตัว ตัวที่มาทีหลังควรเขียนทับตัวก่อนหน้า แต่ถ้าเป็น concurrent เราก็มี conflict ที่ต้องแก้

Concurrency, Time, and Relativity (Concurrency, เวลา และทฤษฎีสัมพัทธภาพ)

อาจดูเหมือนว่า operation สองตัวควรเรียกว่า concurrent ถ้าเกิดขึ้น "ในเวลาเดียวกัน" แต่อันที่จริงไม่สำคัญเลยว่าจะเหลื่อมกันตามเวลาจริงหรือไม่ เพราะปัญหาของนาฬิกาในระบบกระจาย การบอกว่าสองสิ่งเกิดขึ้นในเวลาเดียวกันพอดีหรือไม่เป็นเรื่องยากมาก ซึ่งเป็นปัญหาที่เราจะพูดถึงละเอียดขึ้นใน บทที่ 9

ในการนิยาม concurrency เวลาที่แน่นอนไม่สำคัญ เราเรียก operation สองตัวว่า concurrent ถ้าทั้งสองไม่รู้เรื่องของกันและกัน ไม่ว่าในทางกายภาพจะเกิดขึ้นเมื่อไรก็ตาม บางครั้งมีคนโยงหลักการนี้เข้ากับทฤษฎีสัมพัทธภาพพิเศษในวิชาฟิสิกส์ [ 58 ] ซึ่งเสนอว่าข้อมูลเดินทางเร็วกว่าความเร็วแสงไม่ได้ ดังนั้น event สองเหตุการณ์ที่เกิดห่างกันในระยะหนึ่งจะส่งผลต่อกันไม่ได้เลย ถ้าเวลาระหว่าง event ทั้งสองสั้นกว่าเวลาที่แสงใช้เดินทางระหว่างสองจุดนั้น

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

Capturing the happens-before relationship (การจับความสัมพันธ์แบบ happens-before)

มาดูอัลกอริทึมที่ตัดสินว่า operation สองตัวเป็น concurrent หรือตัวหนึ่งเกิดก่อนอีกตัว เพื่อให้ง่าย เราจะเริ่มจากฐานข้อมูลที่มี replica เดียว เมื่อหาวิธีทำบน replica เดียวได้แล้ว เราก็ขยายแนวทางไปสู่ฐานข้อมูล leaderless ที่มีหลาย replica ได้ อัลกอริทึมทำงานดังนี้:

• เซิร์ฟเวอร์เก็บหมายเลขเวอร์ชันของทุก key เพิ่มหมายเลขเวอร์ชันทุกครั้งที่ key นั้นถูกเขียน และเก็บหมายเลขเวอร์ชันใหม่ไว้คู่กับค่าที่เขียน

• เมื่อ client อ่าน key เซิร์ฟเวอร์จะคืน sibling ทั้งหมด (คือค่าทั้งหมดที่ยังไม่ถูกเขียนทับ) พร้อมหมายเลขเวอร์ชันล่าสุด client ต้องอ่าน key ก่อนเขียนเสมอ

• เมื่อ client เขียน key ต้องแนบหมายเลขเวอร์ชันจากการอ่านก่อนหน้ามาด้วย และต้อง merge ค่าทั้งหมดที่ได้รับจากการอ่านครั้งนั้น (เช่น ใช้ CRDT ร่วมกับข้อมูลจากผู้ใช้) response ของ write request ก็คืน sibling ทั้งหมดเช่นกัน ซึ่งทำให้เรา chain write หลายครั้งต่อกันได้ (ดังในตัวอย่างตะกร้าสินค้าที่กล่าวถึงในหัวข้อ "การจัดการกับ Write Conflicts")

• เมื่อเซิร์ฟเวอร์ได้รับ write ที่มีหมายเลขเวอร์ชันหนึ่ง มันเขียนทับค่าทั้งหมดที่มีหมายเลขเวอร์ชันนั้นหรือต่ำกว่าได้ (เพราะรู้ว่าค่าเหล่านั้นถูก merge เข้าไปในค่าใหม่แล้ว) แต่ต้องเก็บค่าทั้งหมดที่มีหมายเลขเวอร์ชันสูงกว่าไว้ (เพราะค่าเหล่านั้น concurrent กับ write ที่เข้ามา)

สังเกตว่าเซิร์ฟเวอร์ดูแค่หมายเลขเวอร์ชันก็รู้ได้ว่า operation สองตัวเป็น concurrent หรือไม่ โดยไม่ต้องตีความตัวค่าเอง ค่าจึงเป็น data structure แบบใดก็ได้

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

Figure 6-15. การจับ causal dependency ระหว่าง client สองตัวที่แก้ไขตะกร้าสินค้าพร้อมกัน

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

1. Client 1 เพิ่ม milk ลงตะกร้า นี่เป็น write แรกของ key นั้น เซิร์ฟเวอร์จึงเก็บสำเร็จและกำหนดเวอร์ชัน 1 ให้ แล้วส่งค่ากลับไปให้ client พร้อมหมายเลขเวอร์ชันด้วย

2. Client 2 เพิ่ม eggs ลงตะกร้า โดยไม่รู้ว่า client 1 เพิ่ม milk ไปพร้อมกัน (client 2 คิดว่า eggs ของตัวเองเป็นสินค้าชิ้นเดียวในตะกร้า) เซิร์ฟเวอร์กำหนดเวอร์ชัน 2 ให้ write นี้ และเก็บ eggs กับ milk เป็นสองค่าแยกกัน (sibling) แล้วคืนค่า ทั้งสอง ให้ client พร้อมหมายเลขเวอร์ชัน 2

3. Client 1 ซึ่งไม่รู้เรื่อง write ของ client 2 ต้องการเพิ่ม flour ลงตะกร้า และสมมติว่าหลังจากนั้นตะกร้าจะมีของเป็น [milk, flour] มันส่งค่านี้ไปที่เซิร์ฟเวอร์ พร้อมหมายเลขเวอร์ชันที่เซิร์ฟเวอร์ให้มาก่อนหน้านี้ (1) เซิร์ฟเวอร์ดูจากหมายเลขเวอร์ชันได้ว่า write ของ [milk, flour] มาแทนที่ค่าก่อนหน้าคือ [milk] แต่ concurrent กับ [eggs] เซิร์ฟเวอร์จึงกำหนดเวอร์ชัน 3 ให้ [milk, flour] เขียนทับค่าเวอร์ชัน 1 คือ [milk] แต่เก็บค่าเวอร์ชัน 2 คือ [eggs] ไว้ แล้วคืนทั้งสองค่าที่เหลือให้ client

4. ในระหว่างนั้น client 2 ต้องการเพิ่ม ham ลงตะกร้า โดยไม่รู้ว่า client 1 เพิ่งเพิ่ม flour client 2 ได้รับสองค่าคือ [milk] และ [eggs] จากเซิร์ฟเวอร์ใน response ล่าสุด จึง merge ค่าเหล่านั้นแล้วเพิ่ม ham เป็นค่าใหม่ [eggs, milk, ham] แล้วส่งค่านั้นไปที่เซิร์ฟเวอร์ พร้อมหมายเลขเวอร์ชันก่อนหน้า (2) เซิร์ฟเวอร์ตรวจพบว่าเวอร์ชัน 2 เขียนทับ [eggs] แต่ concurrent กับ [milk, flour] ค่าที่เหลือสองค่าจึงเป็น [milk, flour] เวอร์ชัน 3 และ [eggs, milk, ham] เวอร์ชัน 4

5. สุดท้าย client 1 ต้องการเพิ่ม bacon ก่อนหน้านี้มันได้รับ [milk, flour] และ [eggs] จากเซิร์ฟเวอร์ที่เวอร์ชัน 3 จึง merge ค่าเหล่านั้น เพิ่ม bacon แล้วส่งค่าสุดท้าย [milk, flour, eggs, bacon] ไปที่เซิร์ฟเวอร์พร้อมหมายเลขเวอร์ชัน 3 ซึ่งเขียนทับ [milk, flour] (สังเกตว่า [eggs] ถูกเขียนทับไปแล้วในขั้นตอนก่อนหน้า) แต่ concurrent กับ [eggs, milk, ham] เซิร์ฟเวอร์จึงเก็บค่า concurrent ทั้งสองนั้นไว้

dataflow ระหว่าง operation ใน Figure 6-15 แสดงเป็นภาพกราฟใน Figure 6-16 ลูกศรบอกว่า operation ไหน เกิดก่อน operation ไหน ในแง่ที่ว่า operation ที่มาทีหลัง รู้เรื่อง หรือ ขึ้นอยู่กับ operation ก่อนหน้า ในตัวอย่างนี้ client ไม่เคยมีข้อมูลทันกับเซิร์ฟเวอร์เต็มที่ เพราะมี operation อื่นเกิดขึ้นพร้อมกันอยู่เสมอ แต่ค่าเวอร์ชันเก่าก็ถูกเขียนทับในที่สุด และไม่มี write ใดสูญหาย

Figure 6-16. กราฟของ causal dependency ใน Figure 6-15

Version vectors (เวกเตอร์เวอร์ชัน)

ตัวอย่างใน Figure 6-15 ใช้ replica เดียวเท่านั้น แล้วอัลกอริทึมจะเปลี่ยนไปอย่างไรเมื่อมีหลาย replica แต่ไม่มี leader?

Figure 6-15 ใช้หมายเลขเวอร์ชันเดียวเพื่อจับ dependency ระหว่าง operation แต่ไม่พอเมื่อมีหลาย replica ที่รับ write พร้อมกัน เราต้องใช้หมายเลขเวอร์ชัน ต่อ replica และต่อ key แต่ละ replica จะเพิ่มหมายเลขเวอร์ชันของตัวเองเมื่อประมวลผล write และคอยบันทึกหมายเลขเวอร์ชันที่เคยเห็นจาก replica อื่นด้วย ข้อมูลนี้บอกว่าค่าไหนควรเขียนทับและค่าไหนควรเก็บไว้เป็น sibling

ชุดของหมายเลขเวอร์ชันจาก replica ทั้งหมดเรียกว่า version vector [ 59 ] แนวคิดนี้มีหลายรูปแบบที่ใช้งานอยู่ แต่ที่น่าสนใจที่สุดน่าจะเป็น dotted version vector [ 60, 61 ] ซึ่งใช้ใน Riak 2.0 [ 62, 63 ] เราจะไม่ลงรายละเอียด แต่หลักการทำงานค่อนข้างคล้ายกับที่เห็นในตัวอย่างตะกร้าสินค้า

เช่นเดียวกับหมายเลขเวอร์ชันใน Figure 6-15 version vector จะถูกส่งจาก database replica ไปยัง client เมื่อมีการอ่านค่า และต้องส่งกลับมายังฐานข้อมูลเมื่อมีการเขียนค่าในภายหลัง (Riak encode version vector เป็นสตริงที่เรียกว่า causal context) version vector ช่วยให้ฐานข้อมูลแยกได้ว่าอะไรคือการเขียนทับ และอะไรคือ concurrent write

version vector ยังทำให้มั่นใจได้ว่าการอ่านจาก replica หนึ่งแล้วเขียนกลับไปยังอีก replica หนึ่งนั้นปลอดภัย การทำแบบนี้อาจทำให้เกิด sibling แต่จะไม่มีข้อมูลสูญหาย ตราบใดที่ sibling ถูก merge อย่างถูกต้อง

Version vectors and vector clocks (Version Vectors และ Vector Clocks)

version vector บางครั้งก็เรียกว่า vector clock แม้ทั้งสองจะไม่เหมือนกันเสียทีเดียว ความต่างระหว่างสองอย่างนี้ละเอียดอ่อน [ 61, 64, 65 ] ดูรายละเอียดได้ในเอกสารอ้างอิง โดยสรุป เมื่อต้องเปรียบเทียบสถานะของ replica version vector คือ data structure ที่ถูกต้องที่ควรใช้

Summary (สรุป)

ในบทนี้เราได้ดูเรื่อง replication ซึ่งตอบโจทย์ได้หลายอย่าง:

High availability

ทำให้ระบบทำงานต่อไปได้ แม้เครื่องหนึ่งเครื่อง (หรือหลายเครื่อง ทั้ง zone หรือแม้แต่ทั้ง region) จะหยุดทำงาน

Durability

ทำให้มั่นใจว่าคุณไม่สูญเสียข้อมูล แม้เครื่องทั้งเครื่อง (หรือแม้แต่ทั้ง region) จะล้มเหลวอย่างถาวร

Disconnected operation

ให้แอปพลิเคชันทำงานต่อไปได้แม้เครือข่ายขัดข้อง

Latency

วางข้อมูลให้ใกล้ผู้ใช้ทางภูมิศาสตร์ เพื่อให้ผู้ใช้ใช้งานข้อมูลนั้นได้เร็วขึ้น

Scalability

รองรับปริมาณการอ่านที่สูงกว่าที่เครื่องเดียวจะรับไหว ด้วยการอ่านบน replica

แม้แนวคิดจะเรียบง่าย คือเก็บสำเนาของข้อมูลเดียวกันไว้บนหลายเครื่อง แต่ replication กลับเป็นปัญหาที่ยุ่งยากอย่างน่าทึ่ง ต้องคิดอย่างรอบคอบเรื่อง concurrency ทุกสิ่งที่อาจผิดพลาด และวิธีรับมือผลที่ตามมาจากความผิดพลาดเหล่านั้น อย่างน้อยที่สุดเราต้องรับมือกับ node ที่ใช้งานไม่ได้และเครือข่ายขัดข้อง (ซึ่งยังไม่นับความผิดพลาดที่แฝงตัวร้ายกาจกว่า เช่น ข้อมูลเสียหายแบบเงียบๆ จาก bug ในซอฟต์แวร์หรือความผิดพลาดของฮาร์ดแวร์)

เราได้พูดถึงแนวทางหลักสามแบบของ replication:

Single-leader replication (การจำลองแบบผู้นำเดียว)

Client ส่ง write ทั้งหมดไปที่ node เดียว (leader) ซึ่งส่ง stream ของ data change event ไปยัง replica อื่น (follower) อ่านจาก replica ตัวไหนก็ได้ แต่การอ่านจาก follower อาจล้าสมัย

Multi-leader replication (การจำลองแบบหลายผู้นำ)

Client ส่งแต่ละ write ไปที่ leader node ตัวใดตัวหนึ่งจากหลายตัว ซึ่งตัวไหนก็รับ write ได้ แล้ว leader จะส่ง stream ของ data change event ให้กันและกัน และให้ follower node ทั้งหลาย

Leaderless replication (การจำลองแบบไร้ผู้นำ)

Client ส่งแต่ละ write ไปหลาย node และอ่านจากหลาย node แบบขนาน เพื่อตรวจจับและแก้ไข node ที่มีข้อมูลล้าสมัย

แต่ละแนวทางมีข้อดีข้อเสีย Single-leader replication เป็นที่นิยมเพราะค่อนข้างเข้าใจง่ายและให้ consistency ที่แข็งแรง ส่วน multi-leader และ leaderless replication อาจทนทานกว่าเมื่อมี node ที่ผิดพลาด เครือข่ายขัดข้อง และ latency spike โดยแลกกับการต้องแก้ conflict และหลักประกัน consistency ที่อ่อนกว่า

replication จะเป็น synchronous หรือ asynchronous ก็ได้ ซึ่งส่งผลอย่างลึกซึ้งต่อพฤติกรรมของระบบเมื่อเกิดความผิดพลาด แม้ asynchronous replication จะเร็วเมื่อระบบทำงานราบรื่น แต่ก็สำคัญที่ต้องรู้ว่าจะเกิดอะไรขึ้นเมื่อ replication lag เพิ่มขึ้นและเซิร์ฟเวอร์ล้มเหลว ถ้า leader ล้มเหลวและคุณเลื่อน follower ที่อัปเดตแบบ asynchronous ขึ้นเป็น leader ใหม่ ข้อมูลที่เพิ่ง commit ไปอาจสูญหาย

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

Read-after-write consistency

ผู้ใช้ควรเห็นข้อมูลที่ตัวเองส่งไปเสมอ

Monotonic reads

หลังจากผู้ใช้เห็นข้อมูล ณ จุดเวลาหนึ่งแล้ว ก็ไม่ควรเห็นข้อมูลจากจุดเวลาที่เก่ากว่านั้นในภายหลัง

Consistent prefix reads

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

สุดท้าย เราได้พูดถึงวิธีที่ multi-leader และ leaderless replication ทำให้ replica ทั้งหมด converge สู่สถานะที่สอดคล้องกันในที่สุด คือใช้ version vector หรืออัลกอริทึมที่คล้ายกันเพื่อตรวจจับว่า write ไหน concurrent และใช้อัลกอริทึมแก้ conflict เช่น CRDT เพื่อ merge ค่าที่เขียนพร้อมกัน นอกจากนี้ LWW และการแก้ conflict ด้วยมือก็ทำได้เช่นกัน

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