CAP และแบบจำลองความสอดคล้อง

แบบจำลองความสอดคล้อง (Consistency models) กำหนดการรับประกันที่ระบบจำลองแบบ (replicated system) ให้เกี่ยวกับค่าที่อ่านได้ และทฤษฎี CAP กำหนดขอบเขตว่าการรับประกันใดบ้างที่สามารถอยู่ร่วมกับการพร้อมใช้งาน (availability) ภายใต้การแบ่งพาร์ติชันเครือข่าย (network partitions) ได้

Definition

แบบจำลองความสอดคล้อง (consistency model) คือข้อตกลงระหว่างที่เก็บข้อมูลจำลองแบบ (replicated data store) กับไคลเอนต์ โดยระบุผลลัพธ์ที่อนุญาตของการอ่านและเขียนพร้อมกัน; ทฤษฎี CAP ระบุว่าเมื่อมีการแบ่งพาร์ติชันเครือข่าย ที่เก็บข้อมูลแบบกระจาย (distributed data store) ไม่สามารถให้ทั้งความสอดคล้องแบบ linearizable และความพร้อมใช้งานได้

Scope

หัวข้อนี้ครอบคลุมแบบจำลองความสอดคล้องอย่างเป็นทางการ ได้แก่ linearizability, sequential consistency, causal consistency และ eventual consistency รวมถึงการจัดลำดับตามความแข็งแกร่งของแบบจำลองเหล่านั้น; ทฤษฎี CAP และคำกล่าวที่แม่นยำพร้อมข้อพิสูจน์; และการปรับปรุงแก้ไข เช่น PACELC ซึ่งพิจารณาถึงการแลกเปลี่ยนระหว่างความหน่วง (latency) กับความสอดคล้อง (consistency) ในกรณีที่ไม่มีการแบ่งพาร์ติชันด้วย หัวข้อนี้ให้คำศัพท์สำหรับการระบุและเปรียบเทียบการรับประกันของระบบจำลองแบบ

Core questions

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

Key theories

Linearizability และ sequential consistency

Linearizability กำหนดให้การดำเนินการแต่ละครั้งต้องปรากฏว่ามีผลทันที ณ จุดใดจุดหนึ่งระหว่างการเรียกใช้และการตอบสนอง ซึ่งสอดคล้องกับเวลาจริง; sequential consistency ละเว้นข้อกำหนดด้านเวลาจริง โดยต้องการเพียงการจัดเรียงลำดับที่ถูกต้องเพียงครั้งเดียวที่เคารพคำสั่งของแต่ละกระบวนการ

ทฤษฎี CAP

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

การปรับปรุง PACELC

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

Clinical relevance

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

History

แลมพอร์ต (Lamport) ได้นิยาม sequential consistency ในปี 1979 และเฮอร์ลิฮี (Herlihy) กับวิง (Wing) ได้กำหนด linearizability อย่างเป็นทางการในปี 1990; บรูเวอร์ (Brewer) ได้ตั้งข้อสังเกตเกี่ยวกับการแลกเปลี่ยน CAP ในปี 2000, กิลเบิร์ต (Gilbert) และลินช์ (Lynch) ได้พิสูจน์ในปี 2002 และการปรับกรอบ PACELC ของอาบาดี (Abadi) ในปี 2012 ได้ชี้แจงว่าความหน่วง ไม่ใช่แค่การแบ่งพาร์ติชันเท่านั้น ที่เป็นตัวขับเคลื่อนการเลือกความสอดคล้อง

Debates

CAP มักถูกตีความผิดหรือไม่?

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

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

CAP หมายความว่าระบบจะมีเพียงสองในสามของความสอดคล้อง ความพร้อมใช้งาน และความทนทานต่อการแบ่งพาร์ติชันเท่านั้นใช่หรือไม่?

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