DBMS แบบกระจาย - การควบคุมภาวะพร้อมกัน
เทคนิคการควบคุมภาวะพร้อมกันทำให้มั่นใจได้ว่าธุรกรรมหลายรายการจะดำเนินการพร้อมกันในขณะที่ยังคงรักษาคุณสมบัติกรดของธุรกรรมและความสามารถในการต่ออนุกรมในตาราง
ในบทนี้เราจะศึกษาแนวทางต่างๆสำหรับการควบคุมภาวะพร้อมกัน
การล็อคตามโปรโตคอลการควบคุมการทำงานพร้อมกัน
การล็อกตามโปรโตคอลการควบคุมการทำงานพร้อมกันใช้แนวคิดของการล็อกรายการข้อมูล กlockเป็นตัวแปรที่เกี่ยวข้องกับรายการข้อมูลที่กำหนดว่าสามารถดำเนินการอ่าน / เขียนบนรายการข้อมูลนั้นได้หรือไม่ โดยทั่วไปจะใช้เมทริกซ์ความเข้ากันได้ของการล็อกซึ่งระบุว่ารายการข้อมูลสามารถล็อกโดยธุรกรรมสองรายการในเวลาเดียวกันได้หรือไม่
ระบบควบคุมการทำงานพร้อมกันแบบล็อคสามารถใช้โปรโตคอลการล็อกแบบเฟสเดียวหรือสองเฟสก็ได้
หนึ่งเฟสล็อคโปรโตคอล
ในวิธีนี้ธุรกรรมแต่ละรายการจะล็อกรายการก่อนใช้งานและปลดล็อกทันทีที่ใช้เสร็จสิ้น วิธีการล็อกนี้จัดเตรียมการทำงานพร้อมกันสูงสุด แต่ไม่ได้บังคับใช้ความสามารถในการอนุกรมเสมอไป
โปรโตคอลการล็อคสองเฟส
ในวิธีนี้การดำเนินการล็อคทั้งหมดจะเกิดขึ้นก่อนการดำเนินการปลดล็อกหรือปลดล็อกครั้งแรก ธุรกรรมประกอบด้วยสองขั้นตอน ในระยะแรกธุรกรรมจะได้มาจากการล็อกทั้งหมดที่จำเป็นเท่านั้นและไม่ได้คลายล็อกใด ๆ นี้เรียกว่าการขยายหรือgrowing phase. ในขั้นตอนที่สองธุรกรรมจะคลายการล็อกและไม่สามารถขอล็อกใหม่ได้ นี้เรียกว่าshrinking phase.
ทุกธุรกรรมที่เป็นไปตามโปรโตคอลล็อคสองเฟสรับประกันว่าสามารถต่ออนุกรมกันได้ อย่างไรก็ตามวิธีนี้ให้ความเท่าเทียมกันต่ำระหว่างธุรกรรมที่ขัดแย้งกันสองรายการ
อัลกอริทึมการควบคุมการทำงานพร้อมกันของเวลาประทับ
อัลกอริธึมการควบคุมการทำงานพร้อมกันตามการประทับเวลาใช้การประทับเวลาของธุรกรรมเพื่อประสานการเข้าถึงรายการข้อมูลพร้อมกันเพื่อให้แน่ใจว่าสามารถต่ออนุกรมกันได้ การประทับเวลาคือตัวระบุเฉพาะที่ DBMS กำหนดให้กับธุรกรรมที่แสดงถึงเวลาเริ่มต้นของธุรกรรม
อัลกอริทึมเหล่านี้ช่วยให้มั่นใจได้ว่าธุรกรรมจะดำเนินการตามลำดับที่กำหนดโดยการประทับเวลา ธุรกรรมที่เก่ากว่าควรกระทำก่อนธุรกรรมที่มีอายุน้อยกว่าเนื่องจากธุรกรรมเก่าเข้าสู่ระบบก่อนธุรกรรมที่มีอายุน้อยกว่า
เทคนิคการควบคุมการทำงานพร้อมกันตามการประทับเวลาจะสร้างตารางเวลาที่ทำให้เป็นอนุกรมได้ซึ่งจะจัดเรียงตารางเวลาแบบอนุกรมที่เทียบเท่ากันตามอายุของธุรกรรมที่เข้าร่วม
อัลกอริธึมการควบคุมการทำงานพร้อมกันตามการประทับเวลาบางส่วน ได้แก่ -
- อัลกอริทึมการจัดลำดับการประทับเวลาพื้นฐาน
- อัลกอริทึมการสั่งซื้อการประทับเวลาแบบอนุรักษ์นิยม
- อัลกอริทึมหลายทางตามลำดับการประทับเวลา
ลำดับตามการประทับเวลาปฏิบัติตามกฎสามข้อเพื่อบังคับใช้ความสามารถในการอนุกรม -
Access Rule- เมื่อธุรกรรมสองรายการพยายามเข้าถึงรายการข้อมูลเดียวกันพร้อมกันสำหรับการดำเนินการที่ขัดแย้งกันลำดับความสำคัญจะถูกกำหนดให้กับธุรกรรมที่เก่ากว่า สิ่งนี้ทำให้ธุรกรรมที่อายุน้อยกว่าต้องรอให้ธุรกรรมที่เก่ากว่ากระทำก่อน
Late Transaction Rule- หากธุรกรรมที่มีอายุน้อยกว่าได้เขียนรายการข้อมูลธุรกรรมที่เก่ากว่าจะไม่ได้รับอนุญาตให้อ่านหรือเขียนรายการข้อมูลนั้น กฎนี้ป้องกันไม่ให้ทำธุรกรรมที่เก่ากว่าหลังจากที่ธุรกรรมที่อายุน้อยกว่าได้กระทำไปแล้ว
Younger Transaction Rule - ธุรกรรมที่อายุน้อยกว่าสามารถอ่านหรือเขียนรายการข้อมูลที่เขียนโดยธุรกรรมเก่าแล้ว
อัลกอริทึมการควบคุมภาวะพร้อมกันในแง่ดี
ในระบบที่มีอัตราความขัดแย้งต่ำงานในการตรวจสอบความถูกต้องของธุรกรรมทุกรายการสำหรับความสามารถในการต่ออนุกรมอาจลดประสิทธิภาพลง ในกรณีเหล่านี้การทดสอบความสามารถในการอนุกรมจะถูกเลื่อนออกไปก่อนที่จะกระทำ เนื่องจากอัตราความขัดแย้งอยู่ในระดับต่ำความน่าจะเป็นของการยกเลิกธุรกรรมที่ไม่สามารถต่ออนุกรมกันได้ก็ต่ำเช่นกัน วิธีนี้เรียกว่าเทคนิคการควบคุมภาวะพร้อมกันในแง่ดี
ด้วยวิธีนี้วงจรชีวิตของธุรกรรมแบ่งออกเป็นสามขั้นตอนต่อไปนี้ -
Execution Phase - ธุรกรรมดึงรายการข้อมูลไปยังหน่วยความจำและดำเนินการกับพวกเขา
Validation Phase - ธุรกรรมจะทำการตรวจสอบเพื่อให้แน่ใจว่าการเปลี่ยนแปลงในฐานข้อมูลนั้นผ่านการทดสอบความสามารถในการต่ออนุกรม
Commit Phase - ธุรกรรมจะเขียนกลับรายการข้อมูลที่แก้ไขในหน่วยความจำไปยังดิสก์
อัลกอริทึมนี้ใช้กฎสามข้อเพื่อบังคับใช้ serializability ในขั้นตอนการตรวจสอบความถูกต้อง -
Rule 1- ให้ธุรกรรมสองรายการ T iและ T jหาก T iกำลังอ่านรายการข้อมูลที่ T jกำลังเขียนขั้นตอนการดำเนินการของT iจะไม่สามารถทับซ้อนกับเฟสคอมมิตของT jได้ T jสามารถกระทำได้หลังจาก T iเสร็จสิ้นการดำเนินการเท่านั้น
Rule 2- ให้ธุรกรรมสองรายการ T iและ T jหาก T iกำลังเขียนรายการข้อมูลที่ T jกำลังอ่านเฟสการคอมมิตของT iจะไม่สามารถทับซ้อนกับเฟสการดำเนินการของT jได้ T jสามารถเริ่มดำเนินการได้ก็ต่อเมื่อ T iได้กระทำไปแล้ว
Rule 3- ให้ธุรกรรมสองรายการ T iและ T jหาก T iกำลังเขียนรายการข้อมูลที่ T jเขียนด้วยดังนั้นเฟสการคอมมิตของT iจะไม่สามารถทับซ้อนกับเฟสคอมมิตของT jได้ T jสามารถเริ่มกระทำได้หลังจาก T iได้กระทำไปแล้วเท่านั้น
การควบคุมภาวะพร้อมกันในระบบกระจาย
ในส่วนนี้เราจะดูวิธีการนำเทคนิคข้างต้นไปใช้ในระบบฐานข้อมูลแบบกระจาย
อัลกอริทึมการล็อคสองเฟสแบบกระจาย
หลักการพื้นฐานของการล็อคสองเฟสแบบกระจายนั้นเหมือนกับโปรโตคอลการล็อคสองเฟสพื้นฐาน อย่างไรก็ตามในระบบแบบกระจายมีไซต์ที่กำหนดให้เป็นตัวจัดการล็อก ตัวจัดการการล็อกจะควบคุมการร้องขอการได้มาจากการตรวจสอบธุรกรรม เพื่อบังคับใช้การประสานงานระหว่างผู้จัดการล็อกในไซต์ต่างๆอย่างน้อยหนึ่งไซต์จะได้รับสิทธิ์ในการดูธุรกรรมทั้งหมดและตรวจจับข้อขัดแย้งของการล็อก
ขึ้นอยู่กับจำนวนไซต์ที่สามารถตรวจจับความขัดแย้งของการล็อกได้แนวทางการล็อกแบบสองเฟสแบบกระจายสามารถมีได้สามประเภท -
Centralized two-phase locking- ในแนวทางนี้ไซต์หนึ่งถูกกำหนดให้เป็นตัวจัดการล็อคกลาง ไซต์ทั้งหมดในสภาพแวดล้อมทราบตำแหน่งของตัวจัดการล็อคกลางและรับการล็อกจากมันในระหว่างการทำธุรกรรม
Primary copy two-phase locking- ในแนวทางนี้ไซต์จำนวนหนึ่งถูกกำหนดให้เป็นศูนย์ควบคุมการล็อก แต่ละไซต์เหล่านี้มีหน้าที่จัดการชุดล็อกที่กำหนดไว้ ไซต์ทั้งหมดทราบว่าศูนย์ควบคุมการล็อกใดรับผิดชอบในการจัดการการล็อกของตารางข้อมูล / รายการแฟรกเมนต์
Distributed two-phase locking- ในแนวทางนี้มีตัวจัดการการล็อกจำนวนหนึ่งซึ่งตัวจัดการล็อกแต่ละตัวจะควบคุมการล็อกรายการข้อมูลที่จัดเก็บไว้ในไซต์ท้องถิ่น ตำแหน่งของตัวจัดการล็อกขึ้นอยู่กับการกระจายและการจำลองข้อมูล
การควบคุมการทำงานพร้อมกันของเวลาประทับแบบกระจาย
ในระบบรวมศูนย์การประทับเวลาของธุรกรรมใด ๆ จะถูกกำหนดโดยการอ่านนาฬิกาทางกายภาพ แต่ในระบบแบบกระจายการอ่านนาฬิกาแบบโลจิคัล / โลจิคัลของไซต์ใด ๆ ไม่สามารถใช้เป็นการประทับเวลาส่วนกลางได้เนื่องจากไม่ซ้ำกันทั่วโลก ดังนั้นการประทับเวลาจึงประกอบด้วยรหัสไซต์ร่วมกันและการอ่านนาฬิกาของไซต์นั้น
สำหรับการใช้อัลกอริธึมการสั่งซื้อการประทับเวลาแต่ละไซต์จะมีตัวกำหนดตารางเวลาที่ดูแลคิวแยกต่างหากสำหรับตัวจัดการธุรกรรมแต่ละรายการ ในระหว่างการทำธุรกรรมตัวจัดการธุรกรรมจะส่งคำขอล็อกไปยังตัวกำหนดตารางเวลาของไซต์ ตัวกำหนดตารางเวลาทำให้การร้องขอไปยังคิวที่สอดคล้องกันในการเพิ่มลำดับการประทับเวลา คำขอจะถูกประมวลผลจากด้านหน้าของคิวตามลำดับการประทับเวลากล่าวคือเก่าที่สุดก่อน
กราฟความขัดแย้ง
อีกวิธีหนึ่งคือการสร้างกราฟความขัดแย้ง สำหรับคลาสธุรกรรมนี้ถูกกำหนดไว้ คลาสธุรกรรมประกอบด้วยชุดข้อมูลสองชุดที่เรียกว่าชุดอ่านและชุดเขียน ธุรกรรมเป็นของคลาสเฉพาะถ้าชุดการอ่านของธุรกรรมเป็นส่วนย่อยของคลาส 'read set และชุดการเขียนของธุรกรรมเป็นเซตย่อยของคลาส' การเขียนเซต ในขั้นตอนการอ่านแต่ละธุรกรรมจะออกคำขออ่านสำหรับรายการข้อมูลในชุดการอ่าน ในขั้นตอนการเขียนแต่ละธุรกรรมจะออกคำขอเขียน
กราฟความขัดแย้งถูกสร้างขึ้นสำหรับคลาสที่มีธุรกรรมที่ใช้งานอยู่ ซึ่งประกอบด้วยชุดของขอบแนวตั้งแนวนอนและแนวทแยงมุม ขอบแนวตั้งเชื่อมต่อสองโหนดภายในคลาสและแสดงถึงความขัดแย้งภายในคลาส ขอบแนวนอนเชื่อมต่อสองโหนดในสองคลาสและแสดงถึงความขัดแย้งในการเขียนและการเขียนระหว่างคลาสต่างๆ ขอบทแยงมุมเชื่อมต่อสองโหนดในสองคลาสและหมายถึงข้อขัดแย้งในการเขียน - อ่านหรืออ่าน - เขียนระหว่างสองคลาส
กราฟความขัดแย้งได้รับการวิเคราะห์เพื่อให้แน่ใจว่าธุรกรรมสองรายการภายในคลาสเดียวกันหรือระหว่างคลาสที่แตกต่างกันสองคลาสสามารถรันควบคู่กันได้
อัลกอริธึมการควบคุมภาวะพร้อมกันในแง่ดีแบบกระจาย
อัลกอริธึมการควบคุมภาวะพร้อมกันในแง่ดีแบบกระจายช่วยขยายอัลกอริธึมการควบคุมภาวะพร้อมกันในแง่ดี สำหรับส่วนขยายนี้จะใช้กฎสองข้อ -
Rule 1- ตามกฎนี้ธุรกรรมจะต้องได้รับการตรวจสอบความถูกต้องในทุกไซต์เมื่อดำเนินการ หากพบว่าธุรกรรมไม่ถูกต้องในไซต์ใด ๆ ธุรกรรมนั้นจะถูกยกเลิก การตรวจสอบความถูกต้องในพื้นที่รับประกันว่าธุรกรรมจะคงความสามารถในการทำให้เป็นอนุกรมได้ที่ไซต์ที่มีการดำเนินการ หลังจากธุรกรรมผ่านการทดสอบการตรวจสอบความถูกต้องภายในระบบจะได้รับการตรวจสอบความถูกต้องทั่วโลก
Rule 2- ตามกฎนี้หลังจากธุรกรรมผ่านการทดสอบการตรวจสอบความถูกต้องในพื้นที่แล้วควรมีการตรวจสอบความถูกต้องทั่วโลก การตรวจสอบความถูกต้องทั่วโลกช่วยให้มั่นใจได้ว่าหากธุรกรรมที่ขัดแย้งกันสองรายการทำงานร่วมกันในไซต์มากกว่าหนึ่งไซต์ควรกระทำในลำดับสัมพันธ์เดียวกันกับไซต์ทั้งหมดที่ทำงานร่วมกัน อาจต้องมีการทำธุรกรรมเพื่อรอธุรกรรมอื่นที่ขัดแย้งกันหลังจากการตรวจสอบความถูกต้องก่อนที่จะกระทำ ข้อกำหนดนี้ทำให้อัลกอริทึมมองโลกในแง่ดีน้อยลงเนื่องจากธุรกรรมอาจไม่สามารถกระทำได้ทันทีที่มีการตรวจสอบความถูกต้องที่ไซต์