2. Concurrency Control

Kontrol konkurensi adalah manajemen sistem database (DBMS) konsep yang digunakan untuk mengatasi konflik dengan mengakses secara simultan atau mengubah data yang dapat terjadi dengan sistem multi user-. Concurrency kontrol, bila diterapkan pada DBMS, dimaksudkan untuk mengkoordinasikan transaksi simultan sementara preerving integritas data.  Concurrency adalah tentang untuk mengontrol akses pengguna mulit Database.

Tujuan utama dalam pengembangan database adalah membuat banyak pengguna bisa mengakses data secara bersamaan. Pengaksesan data ini tidak bermasalah jika semua pengguna hanya membaca data dan mereka tidak mengganggu satu sama lain. Tapi ketika dua pengguna atau lebih mengakses database yang sama secara bersamaan dan salah satu melakukan perubahan terhadap data, maka hal ini akan dapat menimbulkan adanya data yang tidak konsisten (inconsistency data).

Untuk mengatasi adanya kemungkinan inconsistency data, maka dibutuhkan adanya suatu mekanisme yang mengatur jalannya transaksi pengaksesan data yang sama tersebut. Mekanisme ini dikenal dengan istilah concurrency control.

Concurrency control adalah proses pengaturan operasi–operasi dalam banyak transaksi yang berjalan secara simultan pada database tanpa mengganggu operasi pada transaksi lainnya sehingga dapat menghasilkan data yang konsisten ( Connolly, 2005, p577 ).

Tiga contoh Masalah interferansi penting yang terkait oleh concurrency, yaitu masalah    Lost-Update,  masalah Uncommitted Dependency, dan masalah Inconsistent Analysis.

Masalah Lost-Update

Penjelasan : Transaksi T1 dan T2 mulai pada waktu yang hampir bersamaan, dan keduanya membaca saldo $100. T2 menambah balx $100 menjadi $200 dan menyimpan hasil perubahannya dalam database. Di sisi lain, transaksi T1 mengurangi copy dari balx $10 menjadi $90 dan menyimpan nilai ini dalam database, menimpa hasil update sebelumnya dan akhirnya menghilangkan $100 yang telah ditambahkan sebelumnya ke dalam saldo. Kehilangan update transaksi T2 dapat dihindari dengan mencegah T­1 membaca nilai dari balx sampai update T2 telah selesai.

Masalah Uncommited Dependency (dirty read)

Penjelasan: Transaksi T4 mengubah balx menjadi $200 namun T4 membatalkan transaksi sehingga balx harus dikembalikan ke nilai asalnya, yaitu $100. Namun, pada waktu itu, transaksi T3 telah membaca nilai baru balx ($200) dan menggunakan nilai ini sebagai dasar pengurangan $10, sehingga memberikan saldo yang keliru sebesar $190, yang seharusnya adalah $90. Nilai balx yang dibaca T3 disebut dirty data, yang berasal dari nama alternatifnya, yaitu masalah dirty read. Alasan rollback ini tidaklah penting.

Masalahnya adalah transaksinya gagal (error), mungkin mengurangi rekening yang salah. Efeknya adalah asumsi T3 yang menganggap update T4 telah berhasil dijalankan, meskipun selanjutnya perubahannya dibatalkan. Masalah ini dihindari dengan mencegah T3 membaca balx sampai keputusan telah dibuat, yaitu commit atau membatalkan efek T4. Dua masalah di atas mengkonsentrasikan pada transaksi yang mengubah database dan campur tangan mereka bisa membuat database menjadi corrupt. Namun, transaksi yang hanya membaca database bisa juga memberikan hasil yang tidak akurat jika mereka diijinkan untuk membaca hasil bagian dari transaksi yang belum selesai yang secara bersamaan membaca database. Contohnya dijelaskan pada masalah inconsistent analysis.

Masalah Inconsistent Analysis

Penjelasan: Masalah inconsistent analysis muncul ketika sebuah transaksi membaca beberapa nilai dari database tapi transaksi kedua mengubah beberapa darinya ketika eksekusi transaksi yang pertama. Contohnya, sebuah transaksi yang meringkas data pada sebuah database(contohnya, saldo total) akan mendapat hasil yang tidak akurat jika, ketika berjalan, transaksi lain sedang mengubah database. Pada contoh diatas, ringkasan transaksi T6 sedang berjalan secara bersamaan dengan transaksi T5. Transaksi T6 sedang menjumlahkan saldo rekening x ($100), rekening y ($50), dan rekening z($25). Namun, di tengah jalan, transaksi T5 telah mentransfer $10 dari balx ke bal­z, sehingga T6 sekarang mempunyai hasil yang salah (lebih besar $10).

Tujuan protokol concurrency control adalah untuk menjadwalkan transaksi sedemikian rupa sehingga dapat menghindar dari berbagai gangguan, dan juga mencegah tipe-tipe masalah yang digambarkan pada sesi sebelumnya. Satu solusi yang jelas adalah mengijinkan hanya satu transaksi yang berjalan dalam satu waktu. Satu transaksi berstatus commit sebelum transaksi berikutnya diijinkan mulai. Namun, tujuan dari DBMS multi user juga untuk memaksimalkan derajat concurrency atau paralelisme dalam sebuah sistem, sehingga transaksi yang dapat berjalan tanpa mengganggu satu sama lain dapat berjalan secara paralel. Contohnya, transaksi yang mengakses bagian berbeda pada database dapat dijadwalkan bersama tanpa gangguan. Dalam bagian ini, kita memeriksa serializability sebagai sebuah cara untuk membantu mengidentifikasi eksekusi transaksi tersebut yang dijamin untuk memastikan konsistensi. Pertama, kita beri beberapa definisi:

Schedule adalah sebuah urutan dari operasi-operasi oleh satu set transaksi yang jalan bersamaan yang menjaga urutan operasi pada setiap transaksi individual ( Connolly, 2005, p580 ). Sebuah transaksi mencakup sebuah urutan operasi yang terdiri dari tindakan baca dan/atau tulis pada database, diikuti oleh sebuah tindakan commit atau abort. Sebuah schedule S terdiri dari sebuah urutan operasi dari sekumpulan n transaksi T1, T2, … Tn, bergantung pada constraint yang dilindungi oleh urutan operasi untuk setiap transaksi pada schedule tersebut. Jadi, untuk setiap transaksi Ti pada schedule S, urutan operasi pada Ti harus sama dengan schedule S.                                                                                                                         

Serial Schedule adalah sebuah schedule di mana operasi dari setiap transaksi dijalankan secara berurutan tanpa adanya tarnsaksi yang mengganggu transaksi lainnya (Connolly, 2005, p580).

NonSerial Schedule adalah sebuah schedule di mana operasi-operasi dari satu set concurrent transactions mengalami interleaved (Connolly, 2005, p580). Pada sebuah serial schedule, transaksi dijalankan pada serial order. Contohnya, jika kita mempunyai dua transaksi T1 dan T2, serial ordernya akan menjadi T1 diikuti oleh T2, atau T2 diikuti oleh T1. Lalu, pada eksekusi serial tidak ada interferensi antara transaksi, karena hanya satu transaksi yang berjalan pada satu waktu.

 Tujuan serializibility adalah untuk menemukan non serial schedule yang mengijinkan transaksi untuk berjalan secara bersamaan tanpa mengganggu satu sama lain, dan kemudian memproduksi sebuah state database yang dapat diproduksi oleh sebuah eksekusi serial. Jika sebuah set transaksi berjalan secara bersamaan, bisa dikatakan bahwa schedule (nonserial) adalah benar jika memproduksi hasil yang sama seperti beberapa eksekusi serial lainnya. Schedule seperti itu disebut serializable. Untuk mencegah inkonsistensi dari transaksi yang mengganggu satu sama lain, penting untuk menjamin serializability dari transaksi yang jalan bersamaan.

Pada serializability, urutan operasi baca dan tulis itu penting. Berikut ini hal – hal yang perlu diperhatikan:

Anggap schedule S1 yang ditunjukkan oleh gambar (a) di bawah mengandung operasi dari dua transaksi yang sedang berjalan secara bersamaan, yaitu T7­ dan T8. Karena operasi tulis pada balx di T8 tidak konflik dengan operasi baca berikutnya pada baly di T7, kita dapat mengubah urutan operasinya untuk memproduksi schedule yang ekuivalen (S2) ditunjukkan oleh gambar (b). Jika kita sekarang juga mengubah urutan dari operasi yang tidak konflik berikut, kita memproduksi serial schedule yang ekuivalen (S3) ditunjukkan oleh gambar (c) di bawah.

 

Keterangan Gambar :

(a) nonserial schedule S1

(b) nonserial schedule S2

(c) serial schedule S3, ekuivalen dengan S1 dan S2

Schedule S3 adalah sebuah schedule serial dan karena S1 dan S2 ekuivalen dengan S3, maka S1 dan S2 adalah serializable schedule.

Recoverable schedule adalah sebuah schedule di mana, untuk setiap transaksi Ti dan Tj, jika Tj membaca sebuah item data yang sebelumnya ditulis oleh Ti, kemudian operasi commit dari Ti mendahului operasi commit Tj.

D. Teknik Concurrency Control

Ada dua teknik concurrency control utama yang mengijinkan transaksi untuk berjalan dengan aman dalam subjek paralel untuk constraint tertentu, yaitu locking dan metode timestamp tertentu. Locking dan timestamping adalah pendekatan konservatif karena mereka menyebabkan transaksi ditunda dalam kasus mereka konflik dengan transaksi lain pada beberapa waktu di masa yang akan datang. Metode optimistik, didasarkan pada premis bahwa konflik itu jarang ditemui, jadi mereka mengijinkan transaksi untuk lanjut tidak tersinkronisasi dan hanya mengecek konflik di bagian akhir, ketika transaksi melakukan operasi commit.

Locking adalah sebuah prosedur yang digunakan untuk mengendalikan akses bersamaan ke data. Ketika sebuah transaksi sedang mengakses database, sebuah lock mungkin menolak akses ke transaksi lain untuk mencegah hasil yang salah ( Connolly, 2005, p587 ). Ada dua macam lock, yaitu shared lock dan exclusive lock yang harus digunakan sebelum melakukan akses membaca ataupun menulis terhadap database. Penggunaan lock ini adalah untuk menjaga konsistensi data didalam database. Jika sebuah transaksi mempunyai sebuah shared lock pada sebuah item data, transaksi tersebut dapat membaca item tapi tidak dapat mengubah datanya ( Connolly, 2005, p588 ). Jika sebuah transaksi mempunyai sebuah exclusive lock pada sebuah item data, transaksi tersebut dapat membaca dan mengubah item data ( Connolly, 2005, p588 ).

Lock digunakan dengan cara sebagai berikut:

Two Phase Locking adalah sebuah transaksi yang mengikuti protokol two-phase locking jika semua operasi locking mendahului operasi unlock pertama pada transaksi ( Connolly, 2005, p589 ).

Aturan-aturannya adalah sebagai berikut :

Timestamping Dasar adalah kontrol konkurensi mekanisme yang menghilangkan kebuntuan. Metode ini tidak menggunakan kunci untuk mengontrol konkurensi, sehingga tidak mungkin bagi kebuntuan terjadi. Menurut metode ini timestamp unik ditugaskan untuk setiap transaksi, biasanya menampilkan saat itu dimulai. Ini secara efektif memungkinkan usia yang akan ditugaskan untuk transaksi dan perintah untuk ditugaskan. Item data memiliki kedua read-timestamp dan menulis-timestamp. Ini cap waktu akan diperbarui setiap kali item data dibaca atau diperbaharui masing-masing.

Masalah timbul dalam sistem ini ketika transaksi mencoba untuk membaca data item yang telah ditulis oleh transaksi yang lebih muda. Ini disebut membaca terlambat. Ini berarti bahwa item data telah berubah sejak waktu mulai transaksi awal dan solusinya adalah untuk memutar kembali timestamp dan memperoleh yang baru. Masalah lain terjadi ketika transaksi mencoba untuk menulis item data yang telah dibaca oleh transaksi yang lebih muda. Ini disebut menulis terlambat. Ini berarti bahwa item data telah dibaca oleh transaksi lain sejak awal transaksi yang mengubah itu. Solusi untuk masalah ini adalah sama seperti untuk masalah membaca terlambat. Timestamp harus digulung kembali dan yang baru diperoleh.

Mengikuti aturan-aturan dari proses timestamping dasar ini memungkinkan transaksi untuk menjadi serial dan jadwal kronologis transaksi maka dapat diciptakan. Timestamping mungkin tidak praktis dalam hal database yang lebih besar dengan tingkat tinggi transaksi. Sejumlah besar ruang penyimpanan harus didedikasikan untuk menyimpan cap waktu dalam kasus ini.

Deadlock adalah jalan buntu yang dapat terjadi ketika dua atau lebih transaksi masing-masing menunggu lock yang sedang dipegang oleh transaksi lainnya untuk dilepas. Hanya ada satu cara untuk menghancurkan deadlock, yaitu abort satu atau lebih transaksi.

Ketika berhadapan dengan kunci dua masalah dapat timbul, yang pertama menjadi kebuntuan. Deadlock mengacu pada situasi tertentu di mana dua atau lebih proses masing-masing menunggu yang lain untuk melepaskan sumber daya, atau lebih dari dua proses yang menunggu sumber daya dalam rantai melingkar. Deadlock adalah masalah umum di mana banyak proses multiprocessing berbagi jenis tertentu sumber daya saling eksklusif. Beberapa komputer, biasanya yang dimaksudkan untuk berbagi waktu dan / atau real-time pasar, sering dilengkapi dengan kunci perangkat keras, atau keras kunci, yang menjamin akses eksklusif untuk proses, memaksa serialisasi.

 Ada tiga cara untuk menangani deadlock, yaitu timeout, deadlock prevention dan deadlock detection and recovery.

Pendekatan sederhana pada pencegahan deadlock adalah berdasarkan lock timeout. Dengan pendekatan ini, sebuah transaksi yang meminta sebuah lock akan menunggu hanya sampai periode waktu tertentu yang didefinisikan sistem.

Pendekatan lain untuk mencegah deadlock adalah untuk memesan transaksi menggunakan timestamp transaksi. Dua algoritma telah ditemukan oleh Rosenkrantz. Algoritma pertama, Wait-Die, mengijinkan hanya transaksi yang lebih tua untuk menunggu yang lebih muda, jika tidak transaksi dibatalkan (die/mati) dan restart dengan timestamp yang sama, sehingga lama kelamaan transaksi tersebut akan menjadi transaksi aktif tertua dan tidak akan mati. Algoritma kedua, Wound-Wait, menggunakan pendekatan simetrikal. Hanya transaksi yang lebih muda yang dapat menunggu untuk yang lebih tua. Jika transaksi yang lebih tua meminta lock yang dipegang oleh transaksi yang lebih muda, transaksi yang lebih muda digagalkan.

Deadlock Detection

Deadlock detection biasanya ditangani oleh konstruksi wait-for graph (WFG) yang menunjukkan ketergantungan transaksi, yaitu transaksi Ti tergantung pada Tj jika transaksi Tj memegang lock pada sebuah item data yang ditunggu oleh Ti.

WFG adalah sebuah directed graph G = (N, E ) yang terdiri dari satu set node N dan satu set directed edge E, yang dikonstruksi sebagai berikut

Deadlock terjadi jika dan hanya jika WFG mengandung sebuah cycle. Gambar di atas menunjukkan WFG yang menunjukkan deadlock antara dua transaksi.

DAFTAR PUSTAKA

Pengantar Perancangan Sistem, Erlangga

Jogiyanto, Pengenalan Komputer, 1995

http://www.sqlcourse.com