Timestamp-Based Protocol (Timestamp Ordering)

Back to IF3140 Sistem Basis Data

3.1: Timestamp-Based Protocol

Questions/Cues

• Apa ide dasar Timestamp Protocol?

• Apa bedanya dengan Locking?

• Apa itu Timestamp (TS)?

• TS apa saja yang disimpan?

• Apa itu TS(Ti)?

• Apa itu W-TS(Q)?

• Apa itu R-TS(Q)?

• Bagaimana Aturan Read?

• Bagaimana Aturan Write?

• Apakah menjamin serializability?

• Apakah bebas deadlock?

• Apakah bebas cascading rollback?

• Apa itu Thomas’s Write Rule?

Reference Points

• Slides “11 - Concurrency Control - 2.pdf” (Hal 25-28)

Ide Dasar: Timestamp-Based Protocol

Berbeda dengan Lock-Based Protocol yang bersifat “pesimis” (minta izin dulu sebelum bekerja), Timestamp-Based Protocol menggunakan urutan serializability yang ditentukan di awal.

• Setiap transaksi (Ti) diberi Timestamp unik (TS(Ti)) saat ia dimulai.

• Sistem menjamin bahwa setiap eksekusi yang konkuren akan setara dengan eksekusi serial dalam urutan timestamp tersebut.

• Jika ada operasi yang “melanggar” urutan timestamp, operasi itu akan ditolak dan transaksinya di-rollback (Abort).

Jenis-Jenis Timestamp

1. TS(Ti) (Timestamp Transaksi): Sebuah nilai unik (biasanya waktu sistem atau counter) yang diberikan saat transaksi Ti dimulai. Jika TS(Ti) < TS(Tj), maka Ti dianggap lebih tua dari Tj.

2. W-TS(Q) (Write-Timestamp): Disimpan untuk setiap item data Q. Ini mencatat timestamp dari transaksi terbaru yang berhasil melakukan write(Q).

3. R-TS(Q) (Read-Timestamp): Disimpan untuk setiap item data Q. Ini mencatat timestamp dari transaksi terbaru yang berhasil melakukan read(Q).

Aturan Protokol Timestamp-Ordering

Protokol ini mengecek dua aturan berikut pada setiap operasi read dan write:

1. Aturan read(Q) oleh Transaksi Ti

• Kasus 1: TS(Ti) < W-TS(Q)

  • Logika: Ti (yang lebih tua) mencoba read(Q), TAPI data Q sudah ditulis oleh transaksi lain (Tj) yang lebih muda.

  • Masalah: Nilai Q yang akan dibaca Ti adalah nilai yang “terlalu baru” (seharusnya belum ada di dunia Ti). Ini melanggar urutan serial.

  • Tindakan: read ditolak. Transaksi Ti di-ABORT (rollback).

• Kasus 2: TS(Ti) >= W-TS(Q)

  • Logika: Ti (yang lebih tua) mencoba read(Q), dan data Q ditulis oleh transaksi yang setara atau lebih tua.
  • Tindakan: read DIIZINKAN.
  • Update: Sistem meng-update R-TS(Q) = max(R-TS(Q), TS(Ti)).

2. Aturan write(Q) oleh Transaksi Ti

• Kasus 1: TS(Ti) < R-TS(Q)

  • Logika: Ti (yang lebih tua) mencoba write(Q), TAPI data Q sudah dibaca oleh transaksi lain (Tj) yang lebih muda.

  • Masalah: Tulisan Ti akan membuat nilai yang sudah dibaca Tj menjadi tidak valid (usang). Ini melanggar urutan serial.

  • Tindakan: write ditolak. Transaksi Ti di-ABORT (rollback).

• Kasus 2: TS(Ti) < W-TS(Q)

  • Logika: Ti (yang lebih tua) mencoba write(Q), TAPI data Q sudah ditulis oleh transaksi lain (Tj) yang lebih muda.

  • Masalah: Tulisan Ti adalah tulisan yang “usang”.

  • Tindakan (Normal): write ditolak. Transaksi Ti di-ABORT.

  • Tindakan (Thomas’s Write Rule): Lihat di bawah.

• Kasus 3: (Aman, TS(Ti) >= R-TS(Q) dan TS(Ti) >= W-TS(Q))

  • Tindakan: write DIIZINKAN.

  • Update: Sistem meng-update W-TS(Q) = TS(Ti).

Jaminan dan Masalah

• Menjamin Conflict Serializability: Ya, karena protokol ini secara eksplisit memaksakan urutan konflik sesuai urutan timestamp.

• Bebas Deadlock: YA. Ini keunggulan utamanya. Tidak ada mekanisme “tunggu” (wait) seperti di locking. Jika terjadi konflik, salah satu transaksi langsung di-rollback. Tidak ada siklus tunggu.

• Bisa terjadi Cascading Rollback: YA. (Misal: T1 write(Q). T2 (TS lebih besar) read(Q). Lalu T1 abort. T2 yang sudah membaca data T1 juga harus abort).

Modifikasi: Thomas’s Write Rule

Ini adalah modifikasi untuk Aturan write(Q) Kasus 2 (TS(Ti) < W-TS(Q)).

• Aturan Asli: write ditolak dan Ti di-rollback.

• Aturan Thomas: write dari Ti DIABAIKAN (IGNORED), dan Ti boleh lanjut (tidak abort).

• Logika: Transaksi Tj (yang lebih muda) sudah write(Q). Tulisan Ti (yang lebih tua) sudah “usang” (obsolete). Tidak ada gunanya menulisnya, toh akan ditimpa lagi oleh Tj. Jadi, abaikan saja seolah-olah tidak pernah terjadi.

• Hasil: Mengizinkan lebih banyak konkurensi. Hasilnya adalah jadwal yang View Serializable, meskipun tidak Conflict Serializable.

Summary

Timestamp-Based Protocol adalah protokol non-locking yang menentukan urutan serializability di awal menggunakan Timestamp (TS) unik untuk setiap transaksi. Setiap item data Q menyimpan W-TS(Q) (TS write terbaru) dan R-TS(Q) (TS read terbaru). Protokol ini menjamin serializability dengan me-rollback (abort) transaksi (Ti) jika ia mencoba read data yang sudah ditulis oleh transaksi lebih muda (TS(Ti) < W-TS(Q)) atau mencoba write data yang sudah dibaca oleh transaksi lebih muda (TS(Ti) < R-TS(Q)). Keunggulan utamanya adalah bebas deadlock (karena tidak ada wait), namun masih bisa terjadi cascading rollback.

Additional Information

Pendalaman: Mengapa Timestamp-Based Protocol Bebas Deadlock?

Deadlock terjadi karena adanya Circular Wait (saling tunggu).

1. Dalam Locking, T1 bisa memegang A dan menunggu B, sementara T2 memegang B dan menunggu A. Ini adalah Circular Wait.

2. Dalam Timestamp Protocol, mekanisme “tunggu” tidak ada.

3. Jika T1 (lebih tua) konflik dengan T2 (lebih muda) yang memegang resource… T1 tidak menunggu. T1 akan memaksa T2 untuk rollback (jika T2 melanggar read/write T1) atau T1 sendiri yang rollback (jika T1 melanggar read/write T2).

4. Karena tidak ada status “menunggu” yang saling bergantung, deadlock secara definisi tidak mungkin terjadi.

Kekurangan Timestamp-Based Protocol

1. Biaya Rollback Tinggi: Protokol ini bisa menghasilkan rollback yang sebenarnya tidak perlu. Banyak jadwal non-serializable yang aman, tetapi tetap di-rollback oleh protokol ini karena kaku.

2. Overhead Komunikasi: Setiap operasi read dan write sekarang menjadi lebih mahal. Mereka tidak hanya mengakses data, tetapi juga harus mengakses (dan mungkin meng-update) timestamp R-TS dan W-TS, yang memerlukan lock internal level-rendah (latch).

3. Potensi Starvation: Transaksi yang “tua” (TS kecil) yang di-rollback akan dimulai ulang dengan timestamp yang sama (tua). Jika ia terus-menerus konflik dengan transaksi baru (yang lebih muda), ia bisa di-rollback berulang kali.