Concurency Control: Timestamp-Based Protocol

เป็นความพยายามที่จะทำให้เกิดความถูกต้องใน concurrency execution แต่ว่าไม่ต้อง lock เลย เพื่อให้มีความ flexible ในการทำงาน เช่น Oracle ใ้ช้ timestamp-based รวมกัน lock-based

โดย timestamp ของ transaction อาจจะไม่ใช่เวลาก็ได้ แต่จะต้องสามารถบอกได้ว่า transaction ใดเกิดก่อนเกิดหลัง transaction ที่เกิดก่อน จะต้องมี timestamp น้อยกว่า transaction ต่อๆ มา

แต่ละ data item จะมี timestamp สองตัว คือ
1. W-timestamp คือ timestamp ของ transaction ล่าสุดที่มา write ข้อมูลนั้นๆ
2. R-timestamp คือ timestamp ของ transaction ล่าสุดที่มา read ข้อมูลนั้นๆ

จากนั้น Timestamp-Ordering Protocolจะมีกฎในการ read/write data ดังนี้

1. กรณีที่จะ read แล้วพบว่า data นั้น มี w-timestamp มากกว่า จะไม่ยอมให้ read ก็จะถูก rollback (คือมี transaction ที่เกิดขึ้นทีหลังมี write data ไปแล้ว) ถ้ามี w-timestamp มีค่าน้อยกว่า ก็จะให้ read ได้ และจะ update r-timestamp นั้นเป็น timestamp ของ transaction ใหม่ที่มี read


2. กรณีที่จะ write แล้วพบว่า data นั้น มี r-timestamp มากกว่า จะไม่ยอมให้ write ก็จะถูก rollback (คือมี transaction ที่เกิดขึ้นทีหลังได้ read ค่าไปก่อนที่เราจะ write ค่าแล้ว) หรือ ถ้าพบว่า data นั้นมี w-timestamp มากกว่า ก็จะไม่ยอมให้ write เช่นเดียวกัน (คือมี transaction ที่มีทีหลัง write ค่าไปแล้ว) แต่ถ้าพบว่า timestamp ของเรามีค่ามากกว่าหรือเท่ากับทั้ง r-timestamp และ w-timestamp ก็จะยอมให้ write ค่าได้ และ update w-timestamp เป็น timestamp ของ transaction ใหม่

แต่เนื่องจากเมื่อมีปัญหาเกิดขึ้นในทุกกรณี protocol นี้บอกว่า จะต้อง rollback จึงทำให้เกิดการ rollback บ่อยครั้ง สำหรับ DBMS ที่เป็น timestamp-based อย่างเดียว ก็จะมีวิธีแก้ปัญหานี้คือ เมื่อ rollback แล้วให้นำกลับมา start transaction ใหม่อีกครั้ง ซึ่งไม่พบใน DBMS ในเชิงพาณิชย์ทั่วๆ ไป แต่อาจจะพบใน database ที่ใช้ใน controller

สำหรับ Oracle ที่ใช้ protocol นี้เ่ช่นกัน ใช้ multi-version scheme ในการแก้ปัญหา คือ แต่ละ transaction จะีสร้าง version ของ data ขึ้นมา เช่น data Q ก็จะมี Q1, Q2, Q3, ...
1. ในกรณีที่ read ข้อมูล ให้ read ค่า Qk โดยที่ Qk คือ version ของ data ที่เป็น transaction ก่อนหน้าเราสำหรับ data นั้น (นิยาย คือ version ที่มี w-timestamp(Qk) มากที่สุดที่ยังน้อยกว่า timestamp ของเรา) ดังนั้นจะ read ค่าได้เสมอ
2. การ write data ที่ Qk (ซึ่ง version k จะเป็น version ที่มี w-timestamp ที่มากที่สุดที่ยังน้อยกว่า timestamp ของเรา) ในกรณีที่ Qk มี r-timestamp ที่มากกว่า timestamp เรา ก็ต้อง rollback transaction นั้น นอกนั้นสามารถ write ได้เป็น version ใหม่ คือ Q(k+1) ซึ่งนั้นหมายถึงการทำ multi-version ไม่ได้แก้การ write data (หรือ lost update ยังคงแก้ไม่ได้)

ซึ่ง multiversion scheme จะทำให้ lost update ยังคง rollback แต่ว่า ปัญหาเรื่อง uncommitted dependency จะต้องใช้ commit bit เข้ามาช่วย คือจะ read เฉพาะ transaction ที่ commit แล้วเท่านั้น แต่สำหรับ inconsistent analysis และ phantom phenomenon สามารถแก้ได้โดยตรง

ดังนั้นเพื่อที่จะแก้ปัญหา lost update ที่ยังคงต้อง rollback อยู่ จึงทำ two-phase locking มาใช้ รวมเรียกว่า multiversion two-phase locking

การใ้ช้เทคนิคนี้ จำเป็นจะต้องเก็บทุกๆ ค่าของแต่ละ transaction ไว้ จนกว่า w-timestamp ของ version นั้นๆ จะน้อยกว่า transaction ที่เก่าที่สุด (หรือมี timestamp น้อยที่สุด) ในระบบ แต่เนื่องจาก memory ไม่เพียงพอกับข้อมูลที่มากมายขนาดนั้น จึงต้องลบค่าเก่าๆ ออก ซึ่งนั้นก็ทำให้บาง transaction เก่าๆ ที่ยังทำงานไม่เสร็จและ ต้องการค่าใน version เก่าๆ จำเป็นจะต้องไปตามเอาค่าเหล่านี้จาก BIJ ดังนั้น Oracle จึงต้องเก็บ BIJ ไว้ใน DB space ด้วย เพื่อให้สามารถดึงข้อมูล old value ขึ้นมาได้