Ketika multiple user mengakses multiple objek basis data yang berada pada multiple site di sistem basis data terdistribusi, maka permasalahan kontrol konkurensi akan terjadi.Konflik terjadi apabila sekumpulan read dari satu transaksi berpotongan dengan sekumpulan read dari transaksi lainnya, dan/atau sekumpulan write dari satu transaksi berpotongan dengan sekumpulan write dari transaksi lainnya. Transaksi T1 dan T2 dikatakan konflik jika kedua-duanya dieksekusi pada waktu yang bersamaan. Bila T1 telah selesai sebelum T2 dikirim ke sistem, dalam kasus ini sekumpulan read dan write saling memotong, tidak dianggap konflik. Konflik diperhatikan pada sekumpulan write yang saling memotong di antara dua transaksi. Ada tiga pendekatan secara umum untuk mendesain algoritma kontrol konkurensi:
1. Wait. Jika dua transaksi konflik, transaksi yang konflik harus menunggu sampai transaksi lainnya selesai.
2. Timestamp. Urutan eksekusi transaksi berdasarkan timestamp. Setiap transaksi memiliki timestamp yang unik dan dua transaksi yang konflik diselesaikan berdasarkan urutan timestamp. Timestamp dapat diletakkan di awal, tengah, atau akhir eksekusi. Pendekatan berdasarkan version digunakan untuk menentukan timestamp objek basis data.
3. Rollback. Dua transaksi yang konflik, salah satu transaksinya diulang kembali pengerjaannya. Disebut juga optimistic, karena bila terjadi konflik maka beberapa transaksi akan di-rollback. Algoritma berdasarkan Mekanisme Wait
Sistem akan melakukan lock pada entitas basis data. Ada dua tipe lock:
1. Readlock. Transaksi akan mengunci entitas pada mode shared. Sehingga transaksi lain yang menunggu untuk membaca beberapa entitas juga bisa mendapatkan readlock.
2. Writelock. Transaksi akan mengunci entitas pada mode eksklusif. Jika ada satu transaksi akan melakukan penulisan pada entitas yang telah di-writelock, maka transaksi lainnya tidak boleh mendapatkan readlock maupun writelock pada entitas ini.
Lock akan menimbulkan masalah baru. Livelock dan deadlock. Livelock terjadi ketika suatu transaksi berkali-kali gagal dalam mendapatkan lock. Deadlock terjadi ketika beberapa transaksi melakukan lock pada beberapa entitas pada saat yang bersamaan; setiap transaksi mendapatkan lock dari entitas yang berbeda dan saling menunggu transaksi lainnya untuk melepaskan lock.
Deadlock dapat diatasi dengan:
1. Setiap transaksi melakukan lock pada semua entitas sekali. Jika ada beberapa lock yang digunakan oleh beberapa transaksi lainnya, maka transaksi akan melepaskan semua lock yang ada. 2. Membuat order linier secara acak pada item-item, dan semua transaksi melakukan urutan request berdasarkan order ini.
Deadlock
ini sangat jarang terjadi, sehingga akan lebih efektif ditanggulangi ketika telah terjadi daripadamelakukantindakan preventif dari awal yang memakan biaya lebih besar.Protokol sederhana yang diperlukan, sehingga setiap transaksi dapat memenuhi aturan keberlanjutan adalah two-phase locking (2PL).
1. Fase locking. Transaksi mengambil lock tanpa melepasnya.
2. Fase unlocking. Dalam fase ini, transaksi melepaskan lock yang ada dan tidak boleh mengambil lock.
lockpoint merupakan keadaan sesaat sebelum pelepasan lock yang pertama kali dilakukan. Algoritma berdasarkan Mekanisme Timestamp .Untuk mendapatkan timestamp unik untuk transaksi pada node berbeda di sistem terdistribusi, clock setiap node harus disamakan. Untuk menyelaraskan clock dapat digunakan message passing. Algoritma berdasarkan Mekanisme Rollback/Optimistic.
Terdapat 4 fase eksekusi transaksi pada pendekatan kontrol konkurensi optimistic:
1. Read. Proses membaca tidak terlalu dibatasi. Hasilnya diletakkan pada variabel lokal. Sekumpulan read tergantung juga pada proses validasi.
2. Compute. Transaksi menghitung sekumpulan nilai dari data entitas yang disebut sekumpulan write. Hasilnya diletakkan pada variabel lokal.
3. Validate. Sekumpulan write dan read transaksi lokal divalidasi oleh sekumpulan transaksi yang sedang berjalan.
4. Commit and Write. Setelah berhasil divalidasi, akan dijalankan di sistem dan diberikan timestamp. Sekumpulan write akan diubah menjadi variabel global dan nilainya dikirim ke setiap node. Jika tidak berhasil divalidasi, transaksi diulangi lagi dari fase compute atau read.
Evaluasi Performansi dari Algoritma Kontrol Konkurensi
Derajat Konkurensi
Serial history memiliki derajat konkurensi yang rendah, sedangkan pendekatan 2PL dan optimistic memberikan derajat konkurensi yang lebih tinggi. Tingkat Lanjut untuk Peningkatan Konkurensi Timestamp yang Multidimensional Protokol ini memungkinkan transaksi untuk memiliki vektor timestamp sampai k elemen. Maksimum k diperoleh dari dua kali jumlah maksimum operasi pada satu kali transaksi.
Relaksasi dari Two-Phase Locking
Suatu transaksi dapat melepaskan suatu lock, sebelum transaksi ini me-request beberapa lock lagi. Pada transaksi berikutnya yang mengambil lock ini, lock tidak dapat dilepaskan sampai transaksi sebelumnya tidak lagi me-request lock.
System Defined Prewrites
Prewrite menunjukkan bahwa value dari transaksi akan di-write disaat yang akan datang. Prewrite tidak akan mengubah status objek data. Ketika prewrite dari suatu transaksi dilakukan, transaksi akan melakukan operasi precommit. Setelah tahapan ini, transaksi lain dapat membaca prewrite, walaupun transaksi ini belum di-update dan di-commit. Dengan prewrite, sistem yang terdiri dari transaksi berdurasi panjang maupun pendek dapat diseimbangkan, sehingga tidak ada delay untuk transaksi berdurasi pendek.
Transaksi yang Fleksibel
Memungkinkan spesifikasi dari beberapa alternatif subset dari subtransaksi untuk dieksekusi dan menghasilkan eksekusi yang berhasil dalam satu dari beberapa alternatif subset tersebut. Eksekusi dari transaksi yang fleksibel dapat diproses dalam beberapa cara.
Kontrol Konkurensi yang dapat Disesuaikan
Sistem basis data yang ada, saling terhubung dengan sistem basis data terdistribusi yang heterogen. Penggunaan konsep sistem basis data Reliable, Adaptable, Interoperable, Distributed (RAID), menjadi fasilitas dalam metode kontrol konkurensi. Model umum untuk pendekatan terhadap sistem dan transaksi yang berbeda adalah dengan generic state, converting state, dan suffix sufficient state.
Kesimpulan
Kontrol konkurensi adalah masalah yang timbul ketika beberapa proses terjadi pada berbagai tempat di sistem. Solusi awal untuk hal ini adalah dengan memastikan kelas-kelas serializability, two-phase locking, dan formalisasi pendekatan optimistic. Mekanisme populer untuk kontrol konkurensi adalah two-phase locking. Kontrol konkurensi yang dapat disesuaikan diimplementasikan pada sistem RAID. Penelitian diharapkan berlanjut, pada bidang semantik dari transaksi dan terutama pada sistem yang berorientasi objek. Pada sistem berskala besar, sangat sulit untuk mem-blok akses ke objek basis data untuk melakukan transaksi. Locking pada masa yang akan datang tidak akan relevan lagi pada kasus seperti ini.
)
Schedule of GOOGLE SUMMER of CODE 2007
