Multiversion Concurrency Control Techniques

เทคนิคนี้จะอาศัยการเก็บรักษาข้อมูลที่ถูกเปลี่ยนแปลงให้เป็นหลายๆ version และเมื่อมี transaction ต้องการใช้ข้อมูลนั้นๆ ก็จะเลือก version ที่เหมาะสมกับ transaction นั้นไปใช้ โดยการควบคุมลำดับการทำงานจะมีอยู่ 2 ลักษณะคือ Based on Timestamp Ordering และ Based on Two-phase locking

Multiversion Technique Based on Timestamp Ordering

ในเทคนิคนี้ version ต่างๆของข้อมูล a (สัญลักษณ์ a1,a2,a3,...ak) จะถูกจัดเก็บโดยแต่ละ version ก็จะมีค่า read timestamp (read_TS(ai)) และ write timestamp (write_TS(ai))ตามหลักการที่ได้กล่าวมาในเรื่องของ timestamp โดยมีการกำหนดค่าคือ

- เมื่อ transaction X ได้รับอนุญาตให้แก้ไขข้อมูล a เมื่อนั้นจะมีการสร้าง version ใหม่ของข้อมูล a ขึ้นมา (ak+1) และตั้งค่า read_TS(ak+1) และ write_TS(ak+1) ให้เป็นค่า TS(X)

- เมื่อ transaction X ได้รับอนุญาตให้อ่านข้อมูลจาก version ai ของข้อมูล a ( เป็น version ที่เหมาะสม ) ค่าของ read_TS(ai) จะถูกตั้งเป็นค่าที่มากกว่าระหว่าง read_TS(ai) เดิมกับ TS(X)

Guarantee Serializability

จะใช้กฎในการอ่านหรือเขียนข้อมูลดังนี้

ถ้า transaction X ต้องการ write ข้อมูล a

1.จะตรวจสอบ version i ซึ่งเป็น version ที่มีค่า write_TS(ai) สูงสุดแต่น้อยกว่าหรือเท่ากับ TS(X) ว่ามีค่า read_TS(ai) > TS(X) หรือไม่ ถ้าใช่ transaction X จะถูก rollback

2. ถ้าไม่เป็นตามเงื่อนไขข้อ 1. จะสร้าง version ใหม่ของข้อมูล a (ak+1) เพื่อแก้ไขค่าตาม transaction X และตั้งค่า read_TS(ak+1) และ write_TS(ak+1) ให้เป็นค่า TS(X)

ถ้า transaction X ต้องการ read ข้อมูล a

ให้เลือกอ่นจาก version i ซึ่งมีค่า write_TS(ai) สูงสุดแต่น้อยกว่าหรือเท่ากับ TS(X) จากนั้นตั้งค่า read_TS(ai) เป็นค่าที่มากกว่าระหว่าง read_TS(ai) เดิมกับ TS(X)

จากกฎที่ว่ามาหมายความว่าการ read ข้อมูลของ transaction ใดๆจะได้รับอนุญาตเสมอและเลือก read จาก version ที่ถูก โดยพิจารณาจากลำดับของ timestamp เป็นเกณฑ์ ส่วนการ write จะมีการพิจารณาอนุญาตให้ทำหรือให้ rollback ตามหลักเกณฑ์เดียวกัน

Multiversion Two-phase locking

ในการใช้แนวคิด Multiversion กับ Two-phase locking นี้จะมีสถานะของการปิดกั้น 3 แบบคือ read lock , write lock และ certify lock โดยระดับของการปิดกั้นเปรียบเทียบกับเทคนิคการ locking ธรรมดาเป็นดังตาราง โดยแนวนอนเป็นสถานะการปิดกั้นของ transaction X ส่วนแนวตั้งเป็นการขอปิดกั้นของ transaction Y

standard Locking Technique

Multiversion Two-phase Locking Technique

โดยการใช้ multiversion จะสามารถอนุญาตให้ transaction อื่นๆ read ข้อมูลที่ถูก write lock อยู่ได้โดยจะ read จาก version ที่ถูก commit แล้ว ส่วนการ write ข้อมูลจะแก้ไขในอีก version หนึ่งซึ่งเมื่อแก้ไขเสร็จแล้วจะต้องขอ certify lock เพื่อทำการ commit อีกที