DBMS Terdistribusi - Mengontrol Konkurensi
Teknik pengendalian konkurensi memastikan bahwa beberapa transaksi dieksekusi secara bersamaan sambil mempertahankan properti ACID dari transaksi dan kemampuan bersambung dalam jadwal.
Dalam bab ini, kita akan mempelajari berbagai pendekatan untuk kontrol konkurensi.
Protokol Kontrol Konkurensi Berbasis Penguncian
Protokol kontrol konkurensi berbasis penguncian menggunakan konsep penguncian item data. SEBUAHlockadalah variabel yang terkait dengan item data yang menentukan apakah operasi baca / tulis dapat dilakukan pada item data tersebut. Umumnya, matriks kompatibilitas kunci digunakan yang menyatakan apakah item data dapat dikunci oleh dua transaksi pada waktu yang sama.
Sistem kontrol konkurensi berbasis penguncian dapat menggunakan protokol penguncian satu fase atau dua fase.
Protokol Penguncian Satu Fase
Dalam metode ini, setiap transaksi mengunci item sebelum digunakan dan melepaskan kunci segera setelah selesai menggunakannya. Metode penguncian ini menyediakan konkurensi maksimum tetapi tidak selalu memberlakukan kemampuan bersambung.
Protokol Penguncian Dua-fase
Dalam metode ini, semua operasi penguncian mendahului operasi kunci-lepas atau buka kunci pertama. Transaksi terdiri dari dua tahap. Pada tahap pertama, transaksi hanya memperoleh semua kunci yang dibutuhkannya dan tidak melepaskan kunci apa pun. Ini disebut perluasan ataugrowing phase. Pada fase kedua, transaksi melepaskan kunci dan tidak dapat meminta kunci baru. Ini disebutshrinking phase.
Setiap transaksi yang mengikuti protokol penguncian dua fase dijamin dapat diserialkan. Namun, pendekatan ini memberikan paralelisme rendah antara dua transaksi yang saling bertentangan.
Algoritma Kontrol Konkurensi Stempel Waktu
Algoritme kontrol konkurensi berbasis stempel waktu menggunakan stempel waktu transaksi untuk mengoordinasikan akses bersamaan ke item data untuk memastikan kemampuan serial. Stempel waktu adalah pengenal unik yang diberikan oleh DBMS ke transaksi yang mewakili waktu mulai transaksi.
Algoritme ini memastikan bahwa transaksi dilakukan dalam urutan yang ditentukan oleh stempel waktunya. Transaksi lama harus dilakukan sebelum transaksi yang lebih muda, karena transaksi lama memasuki sistem sebelum transaksi yang lebih muda.
Teknik kontrol konkurensi berbasis stempel waktu menghasilkan jadwal yang dapat diserialkan sedemikian rupa sehingga jadwal seri yang setara diatur dalam urutan usia transaksi yang berpartisipasi.
Beberapa algoritma kontrol konkurensi berbasis stempel waktu adalah -
- Algoritme pengurutan stempel waktu dasar.
- Algoritme pengurutan stempel waktu konservatif.
- Algoritme multiversi berdasarkan pengurutan stempel waktu.
Pengurutan berdasarkan stempel waktu mengikuti tiga aturan untuk menerapkan kemampuan serial -
Access Rule- Ketika dua transaksi mencoba mengakses item data yang sama secara bersamaan, untuk operasi yang berkonflik, prioritas diberikan ke transaksi yang lebih lama. Hal ini menyebabkan transaksi yang lebih muda menunggu transaksi yang lebih lama untuk dilakukan terlebih dahulu.
Late Transaction Rule- Jika transaksi yang lebih muda telah menulis item data, maka transaksi yang lebih lama tidak diperbolehkan untuk membaca atau menulis item data tersebut. Aturan ini mencegah transaksi yang lebih lama dilakukan setelah transaksi yang lebih muda telah dilakukan.
Younger Transaction Rule - Transaksi yang lebih muda dapat membaca atau menulis item data yang telah ditulis oleh transaksi yang lebih lama.
Algoritma Kontrol Konkurensi Optimis
Dalam sistem dengan tingkat konflik rendah, tugas memvalidasi setiap transaksi untuk kemampuan bersambung dapat menurunkan kinerja. Dalam kasus ini, pengujian serializability ditunda sebelum dilakukan. Karena tingkat konflik rendah, kemungkinan membatalkan transaksi yang tidak dapat diserialkan juga rendah. Pendekatan ini disebut teknik kontrol konkurensi optimis.
Dalam pendekatan ini, siklus hidup transaksi dibagi menjadi tiga fase berikut -
Execution Phase - Transaksi mengambil item data ke memori dan melakukan operasi padanya.
Validation Phase - Transaksi melakukan pemeriksaan untuk memastikan bahwa melakukan perubahan ke database melewati uji kemampuan bersambung.
Commit Phase - Transaksi menulis kembali item data yang diubah dalam memori ke disk.
Algoritme ini menggunakan tiga aturan untuk memaksakan serializability dalam fase validasi -
Rule 1- Diberikan dua transaksi T i dan T j , jika T i membaca item data yang ditulis T j , maka fase eksekusi T i tidak dapat tumpang tindih dengan fase komit T j . T j dapat melakukan hanya setelah T i telah menyelesaikan eksekusi.
Rule 2- Diberikan dua transaksi T i dan T j , jika T i menulis item data yang dibaca T j , maka fase commit T i tidak dapat tumpang tindih dengan fase eksekusi T j . T j dapat mulai mengeksekusi hanya setelah T i telah dilakukan.
Rule 3- Diberikan dua transaksi T i dan T j , jika T i menulis item data yang juga ditulis T j , maka fase commit T i tidak dapat tumpang tindih dengan fase commit T j . T j dapat mulai berkomitmen hanya setelah T i telah berkomitmen.
Kontrol Konkurensi dalam Sistem Terdistribusi
Pada bagian ini, kita akan melihat bagaimana teknik di atas diimplementasikan dalam sistem database terdistribusi.
Algoritma Penguncian Dua-fase Terdistribusi
Prinsip dasar penguncian dua fase terdistribusi sama dengan protokol penguncian dua fase dasar. Namun, dalam sistem terdistribusi ada situs yang ditetapkan sebagai pengelola kunci. Manajer kunci mengontrol permintaan akuisisi kunci dari monitor transaksi. Untuk menegakkan koordinasi antara pengelola kunci di berbagai situs, setidaknya satu situs diberi kewenangan untuk melihat semua transaksi dan mendeteksi konflik kunci.
Bergantung pada jumlah situs yang dapat mendeteksi konflik kunci, pendekatan penguncian dua fase terdistribusi dapat terdiri dari tiga jenis -
Centralized two-phase locking- Dalam pendekatan ini, satu lokasi ditetapkan sebagai pengelola kunci pusat. Semua situs di lingkungan mengetahui lokasi pengelola kunci pusat dan memperoleh kunci darinya selama transaksi.
Primary copy two-phase locking- Dalam pendekatan ini, sejumlah situs ditetapkan sebagai pusat kendali kunci. Masing-masing situs ini memiliki tanggung jawab untuk mengelola sekumpulan kunci yang ditentukan. Semua situs tahu pusat kendali kunci mana yang bertanggung jawab untuk mengelola kunci dari tabel data / item fragmen mana.
Distributed two-phase locking- Dalam pendekatan ini, ada sejumlah manajer kunci, di mana setiap manajer kunci mengontrol kunci item data yang disimpan di situs lokalnya. Lokasi manajer kunci didasarkan pada distribusi dan replikasi data.
Kontrol Konkurensi Stempel Waktu Terdistribusi
Dalam sistem terpusat, stempel waktu dari setiap transaksi ditentukan oleh pembacaan jam fisik. Namun, dalam sistem terdistribusi, pembacaan jam fisik / logis lokal situs mana pun tidak dapat digunakan sebagai stempel waktu global, karena tidak unik secara global. Jadi, stempel waktu terdiri dari kombinasi ID situs dan pembacaan jam situs tersebut.
Untuk menerapkan algoritme pengurutan stempel waktu, setiap situs memiliki penjadwal yang mengelola antrian terpisah untuk setiap pengelola transaksi. Selama transaksi, manajer transaksi mengirimkan permintaan kunci ke penjadwal situs. Penjadwal menempatkan permintaan ke antrian terkait dalam meningkatkan urutan stempel waktu. Permintaan diproses dari depan antrian dalam urutan stempel waktunya, yaitu yang terlama lebih dulu.
Grafik Konflik
Metode lain adalah membuat grafik konflik. Untuk kelas transaksi ini ditentukan. Kelas transaksi berisi dua set item data yang disebut set baca dan set tulis. Sebuah transaksi termasuk dalam kelas tertentu jika set baca transaksi adalah himpunan bagian dari set baca kelas dan set tulis transaksi adalah himpunan bagian dari set tulis kelas. Dalam fase baca, setiap transaksi mengeluarkan permintaan baca untuk item data dalam kumpulan bacanya. Pada fase tulis, setiap transaksi mengeluarkan permintaan tulisnya.
Grafik konflik dibuat untuk kelas yang memiliki transaksi aktif. Ini berisi satu set tepi vertikal, horizontal, dan diagonal. Tepi vertikal menghubungkan dua node di dalam kelas dan menunjukkan konflik di dalam kelas. Tepi horizontal menghubungkan dua node di dua kelas dan menunjukkan konflik tulis-tulis di antara kelas yang berbeda. Tepi diagonal menghubungkan dua node di dua kelas dan menunjukkan konflik tulis-baca atau baca-tulis di antara dua kelas.
Grafik konflik dianalisis untuk memastikan apakah dua transaksi dalam kelas yang sama atau di dua kelas berbeda dapat dijalankan secara paralel.
Algoritma Kontrol Konkurensi Optimis Terdistribusi
Algoritme kontrol konkurensi optimis terdistribusi memperluas algoritme kontrol konkurensi optimis. Untuk ekstensi ini, dua aturan diterapkan -
Rule 1- Menurut aturan ini, transaksi harus divalidasi secara lokal di semua situs saat dijalankan. Jika transaksi ditemukan tidak valid di situs mana pun, itu dibatalkan. Validasi lokal menjamin bahwa transaksi mempertahankan serialisasi di situs tempat ia dijalankan. Setelah transaksi lolos uji validasi lokal, transaksi divalidasi secara global.
Rule 2- Menurut aturan ini, setelah transaksi lolos uji validasi lokal, transaksi tersebut harus divalidasi secara global. Validasi global memastikan bahwa jika dua transaksi yang berkonflik berjalan bersama di lebih dari satu situs, keduanya harus dilakukan dalam urutan relatif yang sama di semua situs yang dijalankan bersama. Ini mungkin memerlukan transaksi untuk menunggu transaksi bentrok lainnya, setelah validasi sebelum komit. Persyaratan ini membuat algoritme kurang optimis karena transaksi mungkin tidak dapat dilakukan segera setelah divalidasi di sebuah situs.