ทฤษฎีบท C.A.P

All lectures for TH purposes
ระดับ , บทเรียน
มีอยู่

4.1 ความสอดคล้องเกี่ยวกับ Brewera

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

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

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

ด้วยความรู้สึกสอดคล้องกันนี้ "ทฤษฎีบท" ของ Brewer จึงถือได้ว่าค่อนข้างเข้าใจได้และชัดเจน: ในระบบแบบกระจายใดๆ ที่มีข้อมูลที่ใช้ร่วมกัน มีเพียงสองคุณสมบัติของความสอดคล้อง ความพร้อมใช้งาน และความทนทานต่อพาร์ติชันของเครือข่ายเท่านั้นที่สามารถรับประกันได้พร้อมๆ กัน ในเรื่องนี้ Brewer ยังเปรียบเทียบชุดของคุณสมบัติของกรดกับชุดของคุณสมบัติของ BASE ที่เขาเสนอ (พร้อมใช้งานโดยทั่วไป, สถานะอ่อน, ความสม่ำเสมอในท้ายที่สุด - ความพร้อมใช้งานในกรณีส่วนใหญ่, สถานะที่ไม่เสถียร, ความสอดคล้องขั้นสุดท้าย) แต่ในความคิดของฉันการต่อต้านนี้ไม่ยุติธรรมเนื่องจากในกรณีแรกเรากำลังพูดถึงลักษณะเชิงตรรกะของธุรกรรมและประการที่สอง - เกี่ยวกับคุณสมบัติทางกายภาพของระบบกระจาย

4.2 การพิสูจน์ "ทฤษฎีบท"

หลายคนเชื่อว่า "ทฤษฎีบท" ของบรูเออร์ได้รับการพิสูจน์อย่างเป็นทางการแล้ว อันที่จริง บทความของ Seth Gilbert และ Nancy Lynch ได้แนะนำคำจำกัดความที่เป็นทางการ (เกือบ) บางประการ ซึ่งบริบทของ "ทฤษฎีบท" กลายเป็นทฤษฎีบทจริงๆ และได้รับการพิสูจน์แล้ว อย่างไรก็ตาม เรามาดูกันว่าคุณสมบัติของระบบแบบกระจายทั้งสามนั้นถูกกำหนดอย่างไร ซึ่งตาม "ทฤษฎีบทของ Brewer" นั้น สามารถรองรับได้เพียงสองคุณสมบัติพร้อมกันเท่านั้น

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

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

ตามคำจำกัดความเหล่านี้ Hilbert และ Lynch กำหนดทฤษฎีบทต่อไปนี้ (ไม่มีนาฬิกาในโมเดลเครือข่ายแบบอะซิงโครนัส และโหนดควรทำการตัดสินใจตามข้อความที่ได้รับและการคำนวณในเครื่องเท่านั้น):

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

ทฤษฎีบทนี้ได้รับการพิสูจน์อย่างเป็นทางการโดยวิธี "โดยความขัดแย้ง" บทความนี้สรุปว่า:

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

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

ใช่ ในแง่หนึ่ง (ไม่จำเป็นต้องเหมือนกับความตั้งใจของ Brewer) Gilbert และ Lynch ได้รับการพิสูจน์แล้วว่าเป็นไปไม่ได้ที่จะตรวจสอบคุณสมบัติของความสม่ำเสมอของอะตอม ความพร้อมใช้งาน และความคลาดเคลื่อนของพาร์ติชันของเครือข่ายในระบบแบบกระจายระบบเดียวไปพร้อม ๆ กัน แต่สิ่งนี้เกี่ยวข้องกับธุรกรรมฐานข้อมูลโดยทั่วไปและธุรกรรมกรดโดยเฉพาะอย่างยิ่ง?

4.3 ธุรกรรมกรด

นี่คือสิ่งที่ Julian Browne เขียนเกี่ยวกับเรื่องนี้ในบันทึกของเขาเกี่ยวกับการอภิปรายเกี่ยวกับ "ทฤษฎีบท" ของ CAP:

ในข้อพิสูจน์ของพวกเขา Hilbert และ Lynch ใช้คำว่า atomicity แทนความสอดคล้อง ซึ่งเหมาะสมกว่าจากมุมมองทางเทคนิค เพราะหากพูดอย่างเคร่งครัด ความสอดคล้องตามความหมายของ ACID หมายถึงคุณสมบัติในอุดมคติของธุรกรรมฐานข้อมูล และหมายความว่าไม่มีข้อมูลใดที่จะ จะกลายเป็นถาวรหากละเมิดข้อจำกัดบางอย่างที่กำหนดไว้ล่วงหน้า แต่ถ้าเราคิดว่าข้อ จำกัด ที่กำหนดไว้ล่วงหน้าของระบบการกระจายคือการห้ามการมีอยู่ของค่าต่าง ๆ หลายค่าสำหรับองค์ประกอบข้อมูลเดียวกัน ในความคิดของฉันข้อบกพร่องนี้ในการสรุปความสอดคล้องสามารถพิจารณาได้ ไม่มีนัยสำคัญ (นอกจากนี้ หากบริวเวอร์ใช้คำว่า ปรมาณู ทฤษฎีบท AAP จะปรากฏขึ้น ซึ่งเป็นชื่อที่ออกเสียงไม่สะดวกอย่างยิ่ง)

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

และนี่คือสิ่งที่ตัวแทนของชุมชนฐานข้อมูล Daniel Abadi และ Alexander Thomson เขียนค่อนข้างจริงจังในบันทึกของพวกเขา:

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

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

Michael Stonebreaker กล่าวว่ากุญแจสำคัญในการสร้าง DBMS สมัยใหม่ที่มีคุณภาพสูงคือทางเลือกที่เหมาะสมในการประนีประนอมทางเทคนิค เมื่อเลือกโซลูชันทางวิศวกรรมเฉพาะ ต้องคำนึงถึงปัจจัยหลายอย่าง - ความต้องการของผู้ใช้ในอนาคต ความน่าจะเป็นของสถานการณ์ความล้มเหลวต่างๆ ฯลฯ และไม่ควรถูกชี้นำโดยแนวทางทฤษฎีทั่วไปใดๆ (รวมถึง "ทฤษฎีบท" ของ CAP)

Stonebreaker เชื่อว่าในขอบเขตของระบบฐานข้อมูลแบบขนานในการทำธุรกรรม การละทิ้งความสอดคล้องของ Brewer เพื่อสนับสนุนความพร้อมใช้งานสูงและความทนทานต่อพาร์ติชันเครือข่ายเป็นการแลกเปลี่ยนที่ไม่ดี เนื่องจาก (a) ความสอดคล้องของแบบจำลองเป็นคุณสมบัติที่มีประโยชน์มากของระบบ; (b) DBMS แบบคู่ขนานขนาดใหญ่ที่ทำธุรกรรมได้ไม่ต้องการคลัสเตอร์ที่มีโหนดจำนวนมาก ดังนั้น สถานการณ์การแยกเครือข่ายจึงไม่น่าเป็นไปได้ (c) ระบบอาจไม่พร้อมใช้งานได้ง่าย ไม่ใช่เพราะพาร์ติชันเครือข่าย แต่ ตัวอย่างเช่น เนื่องจากมีข้อผิดพลาดของซอฟต์แวร์เกิดขึ้นเป็นประจำ

ดังนั้นกิจกรรมระดับสูงของตัวแทนของค่าย NoSQL (อ่านว่า NoACID) ซึ่งมักอ้างถึง "ทฤษฎีบท" ของ Brewer นั้นไม่ได้เชื่อมโยงกับความเป็นไปไม่ได้ทางทฤษฎีในการสร้าง DBMS ของทรานแซคชันขนานขนาดใหญ่ที่รองรับธุรกรรม ACID แต่ด้วยความจริงที่ว่าระบบที่เรียบง่าย ที่ไม่รองรับเฉพาะธุรกรรม ACID เท่านั้น แต่ยังรวมถึงความสอดคล้องของแบบจำลองอีกด้วย ถูกสร้างขึ้นได้ง่ายและรวดเร็วขึ้น เนื่องจากการจัดระเบียบที่เรียบง่าย จึงสามารถประมวลผลข้อมูลได้อย่างรวดเร็ว และสำหรับบางแอปพลิเคชัน สิ่งนี้มีความสำคัญมากกว่าสิ่งอำนวยความสะดวกทั้งหมดที่มีอยู่ในเทคโนโลยีฐานข้อมูล

มาดูกันว่าชุมชนฐานข้อมูลตอบสนองต่อความท้าทายนี้อย่างไร

ความคิดเห็น
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION