Validation-Based Protocol

Back to IF3140 Sistem Basis Data

3.2: Validation-Based Protocol (Optimistic)

Questions/Cues

• Apa ide dasar Validation Protocol?

• Mengapa disebut Optimistic?

• Apa bedanya dengan Pessimistic (Locking)?

• Apa 3 fase eksekusi?

• Fase 1: Read Phase?

• Fase 2: Validation Phase?

• Fase 3: Write Phase?

• Apa itu Read Set RS(Ti)?

• Apa itu Write Set WS(Ti)?

• Apa 3 timestamp yang digunakan?

• Apa itu Start(Ti)?

• Apa itu Validation(Ti)?

• Apa itu Finish(Ti)?

• Bagaimana aturan Tes Validasi?

Reference Points

• Slides “11 - Concurrency Control - 3.pdf” (Hal 3-7)

Ide Dasar: Optimistic Concurrency Control

Validation-Based Protocol juga dikenal sebagai Optimistic Concurrency Control (OCC).

• Asumsi Optimis: Konflik antar transaksi adalah kejadian yang jarang.

• Strategi: Biarkan transaksi bekerja “bebas” (tanpa lock), dengan asumsi tidak akan ada konflik. Sebelum commit, lakukan “tes validasi” untuk memeriksa apakah ada konflik yang benar-benar terjadi.

• Kontras (Pessimistic): Lock-Based Protocol bersifat “pesimis”. Asumsinya: konflik sering terjadi. Jadi, minta izin dulu (lock) sebelum bekerja.

Tiga Fase Eksekusi Transaksi

Setiap transaksi Ti dibagi menjadi tiga fase:

1. Read Phase (Fase Baca & Eksekusi):

   • Transaksi Ti membaca nilai dari basis data.

   • Ti melakukan semua perhitungan.

   • Jika Ti melakukan write(Q), nilai baru hanya disimpan di variabel lokal (temporer), BUKAN di basis data.

   • Sistem mencatat Read Set RS(Ti) (item data apa saja yang dibaca) dan Write Set WS(Ti) (item data apa saja yang akan ditulis).

2. Validation Phase (Fase Validasi):

   • Dilakukan saat Ti siap untuk commit.

   • Sistem menjalankan Tes Validasi untuk memeriksa apakah write Ti melanggar serializability terhadap transaksi lain yang sudah commit.

   • Jika validasi Gagal, Ti di-rollback (Abort).

   • Jika validasi Sukses, Ti lanjut ke fase 3.

3. Write Phase (Fase Tulis):

• Nilai-nilai dari variabel lokal (di WS(Ti)) disalin secara permanen ke basis data.

Timestamp untuk Validasi

Untuk melakukan tes, sistem menggunakan 3 timestamp (berbeda dari protokol sebelumnya):

1. Start(Ti): Waktu ketika Ti memulai Read Phase.

2. Validation(Ti): Waktu ketika Ti memulai Validation Phase.

3. Finish(Ti): Waktu ketika Ti menyelesaikan Write Phase.

Urutan serializability ditentukan oleh urutan Validation(Ti).

Aturan Tes Validasi

Saat Ti melakukan validasi (Validation(Ti)), sistem harus mengecek Ti terhadap semua transaksi Tj yang sudah divalidasi lebih dulu (yaitu, Validation(Tj) < Validation(Ti)).

Validasi Ti SUKSES jika, untuk setiap Tj tersebut, salah satu dari kondisi berikut terpenuhi:

1. Kondisi 1: Finish(Tj) < Start(Ti)

   • Logika: Tj sudah selesai (finish) sebelum Ti mulai (start).
   • Artinya: Eksekusi mereka tidak overlap sama sekali. 100% Aman. Urutan serial: (Tj → Ti).

2. Kondisi 2: WS(Tj) ∩ RS(Ti) = ∅

   • Logika: Write Set Tj TIDAK beririsan dengan Read Set Ti.
   • Artinya: Ti TIDAK membaca data apapun yang ditulis oleh Tj.
   • Dan: Write Phase Ti terjadi setelah Write Phase Tj (karena Validation(Ti) > Validation(Tj)).
   • Kesimpulan: Ini aman karena menjamin urutan serial (Tj → Ti). Ti tidak mungkin membaca data “kotor” dari Tj.

Summary

Validation-Based Protocol (atau Optimistic) berasumsi konflik jarang terjadi, sehingga transaksi dieksekusi tanpa lock. Eksekusi dibagi 3 fase: (1) Read Phase (baca dari DB, tulis ke variabel lokal), (2) Validation Phase (saat commit, lakukan tes validasi), dan (3) Write Phase (salin local write ke DB jika valid). Validasi Ti sukses jika, untuk setiap transaksi Tj yang sudah divalidasi lebih dulu, terbukti mereka tidak overlap (Finish(Tj) < Start(Ti)) ATAU Ti tidak membaca apa yang Tj tulis (WS(Tj) ∩ RS(Ti) = ∅). Jika validasi gagal, Ti di-rollback.

Additional Information

Kelebihan dan Kekurangan Protokol Optimistic

Kelebihan:

1. Konkurensi Tinggi: Jika konflik memang jarang terjadi (misal, sistem read-heavy), protokol ini sangat efisien. Banyak transaksi bisa berjalan bersamaan tanpa blocking (menunggu lock).

2. Bebas Deadlock: Sama seperti Timestamp-Based, protokol ini tidak memiliki mekanisme wait, sehingga dijamin bebas deadlock.

Kekurangan:

1. Biaya Rollback Mahal: Jika transaksi Ti gagal validasi, ia di-rollback setelah melakukan semua pekerjaannya (seluruh Read Phase). Ini membuang-buang sumber daya.

2. Potensi Starvation: Sebuah transaksi (misal Ti, transaksi yang berjalan lama) bisa saja berulang kali gagal validasi karena selalu konflik dengan transaksi-transaksi pendek yang commit lebih dulu.

3. Overhead Validasi: Validation Phase itu sendiri bisa menjadi bottleneck. Sistem harus mengecek RS(Ti) dan WS(Ti) terhadap banyak transaksi lain, yang bisa jadi mahal dan butuh latch (lock internal).