ทฤษฎี CAP และแบบจำลองความสอดคล้อง

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมทฤษฎี CAP และการทำให้เป็นทางการ การตีความในทางปฏิบัติที่ว่าการแลกเปลี่ยนที่แท้จริงเกิดขึ้นเฉพาะในระหว่างการแบ่งพาร์ติชันเครือข่าย และการปรับปรุง PACELC ที่เป็นผลลัพธ์ นอกจากนี้ยังครอบคลุมสเปกตรัมของแบบจำลองความสอดคล้อง — ตั้งแต่ความสอดคล้องที่เข้มงวด (linearizable) ไปจนถึงความสอดคล้องเชิงสาเหตุ และความสอดคล้องในท้ายที่สุด — และรูปแบบ BASE ที่แตกต่างจาก ACID โดยจะกล่าวถึงว่าแบบจำลองเหล่านี้ชี้นำการออกแบบพื้นที่เก็บข้อมูลแบบจำลองได้อย่างไร ไม่รวมถึงโปรโตคอลฉันทามติและคอมมิตที่ใช้ในการนำความสอดคล้องที่เข้มงวดไปใช้ ซึ่งครอบคลุมภายใต้ฐานข้อมูลแบบกระจาย

Core questions

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

Key concepts

• ความสอดคล้อง, ความพร้อมใช้งาน, ความทนทานต่อการแบ่งพาร์ติชัน
• การแบ่งพาร์ติชันเครือข่าย
• ความสอดคล้องเชิงเส้น / ความสอดคล้องที่เข้มงวด
• ความสอดคล้องเชิงสาเหตุ
• ความสอดคล้องในท้ายที่สุด
• PACELC
• BASE เทียบกับ ACID
• การแก้ไขข้อขัดแย้ง

Key theories

ทฤษฎี CAP

CAP ซึ่งได้รับการทำให้เป็นทางการโดย Gilbert และ Lynch แสดงให้เห็นว่าเมื่อเครือข่ายถูกแบ่งพาร์ติชัน พื้นที่เก็บข้อมูลแบบจำลองจะต้องเลือกระหว่างการส่งคืนข้อมูลที่อาจล้าสมัย (ความพร้อมใช้งาน) และการปฏิเสธบริการเพื่อรักษามูลค่าที่สอดคล้องกันเพียงค่าเดียว (ความสอดคล้อง) ความทนทานต่อการแบ่งพาร์ติชันไม่สามารถเลือกได้ในเครือข่ายจริง

สเปกตรัมความสอดคล้อง

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

BASE เทียบกับ ACID

ระบบที่มีความพร้อมใช้งานสูงมักจะใช้รูปแบบ BASE — พร้อมใช้งานโดยพื้นฐาน สถานะอ่อน และสอดคล้องกันในท้ายที่สุด — โดยจงใจผ่อนคลายการรับประกัน ACID ที่เข้มงวดเพื่อรักษาสภาพการตอบสนองภายใต้การแบ่งพาร์ติชันและในขนาดใหญ่

Clinical relevance

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

History

Eric Brewer ได้ตั้งสมมติฐานเกี่ยวกับการแลกเปลี่ยน CAP ประมาณปี 2000; Gilbert และ Lynch ได้พิสูจน์อย่างเป็นทางการในปี 2002 Amazon's Dynamo (2007) และบทความของ Vogels ในปี 2009 ได้ทำให้ความสอดคล้องในท้ายที่สุดเป็นที่นิยมในทางปฏิบัติ บทวิเคราะห์ย้อนหลังของ Brewer ในปี 2012 ชี้แจงว่า CAP ห้ามความสอดคล้องและความพร้อมใช้งานที่สมบูรณ์แบบเฉพาะในระหว่างการแบ่งพาร์ติชัน และการกำหนด PACELC ในภายหลังได้เพิ่มการแลกเปลี่ยนระหว่างความหน่วงและความสอดคล้องในกรณีที่ไม่มีการแบ่งพาร์ติชัน

Debates

การแลกเปลี่ยนระหว่างความสอดคล้องและความพร้อมใช้งานมีความสำคัญเพียงใด

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

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

CAP หมายความว่าฉันสามารถมีคุณสมบัติได้เพียงสองในสามเท่านั้นใช่หรือไม่?

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

ความสอดคล้องในท้ายที่สุดรับประกันอะไรบ้าง?

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