Concurrency Control Based on Timestamp Ordering

Time stamps คืออะไร ?

time stamp เป็นสิ่งที่ DBMS สร้างขึ้นเพื่อใช้ในการ identify transaction ซึ่งแต่ละ transaction จะมีค่าที่ไม่ซ้ำกัน และจะระบุได้ว่า transaction นั้น ๆเข้าสู่ระบบเป็นลำดับที่เท่าไหร่หรือเวลาใด แล้วแต่ว่าค่าของ timestamp จะเป็นลำดับที่ (1,2,3,...)หรือเป็นเวลาที่เข้าสู่ระบบ(โดยต้องทำให้แน่ใจว่าไม่มี 2 transaction ใดที่จะมีค่าเวลาที่เท่ากัน)ใช้สัญลักษณ์ TS(X) แทนค่า timestamp ของ transaction

Timestamps ของข้อมูล

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

1.read timestamp ของข้อมูล a (read_TS(a)) จะมีค่าเท่ากับค่า timestamp ที่มากที่สุดใน transaction ทั้งหมดที่เคย read ข้อมูล a สำเร็จ

2.write timestamp ของข้อมูล a (write_TS(a)) จะมีค่าเท่ากับค่า timestamp ที่มากที่สุดใน transaction ทั้งหมดที่เคย write ข้อมูล a สำเร็จ

Guarantees serialzability with timestamps

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

การตรวจสอบว่า transaction นั้นๆจะได้รับอนุญาตให้ read หรือ write ข้อมูลใดๆได้หรือไม่นั้นมีดังนี้

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

1.ถ้า read_ TS(a) >TS(x) หรือ write_TS(a) >TS(x) แล้ว transaction x จะถูก rollback เนื่องจากมี transaction อื่นที่มีค่า timestamp มากกว่า transaction x ได้ อ่านหรือเขียนข้อมูลไปก่อนแล้ว การแก้ไขข้อมูลของ transaction x ในตอนนี้จะทำให้เกิดความขัดแย้งของข้อมูล

2.ถ้าไม่เป็นไปตามเงื่อนไขในข้อ1. จะอนุญาตให้ทำการ write ข้อมูล a และเปลี่ยนค่า write_TS(a) ให้เป็น TS(x) ด้วย

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

1.ถ้า write_TS(a) >TS(x) แล้ว transaction x จะถูก rollback เนื่องจากมี transaction อื่นที่ต้องอยู่หลัง transaction x ตามลำดับของ timestamp ได้แก้ไขข้อมูลไปก่อนที่ transaction x จะมีโอกาสอ่านข้อมูล a

2.ถ้า write_TS(a) <=TS(x) จะอนุญาตให้ read ข้อมูล a และเปลี่ยนค่า read_TS(a) เป็นค่าที่มากกว่าระหว่าง TS(x) กับค่าเดิมของ read_TS(a) ที่มีอยู่