Selasa, 10 Mei 2011

CONCURRENCY CONTROL


CONCURRENCY CONTROL
(PENGENDALIAN PERSAINGAN EKSEKUSI TRANSAKSI DALAM BASIS DATA)

A.     Concurrency Control
Concurrency control merupakan proses pengaturan ooperasi yang simultan pada database tanpa menyebabkan saling mempengaruhi antara satu dengan yang lain. Akses konkuren tidak akan bermasalah jika user hanya melakukan pembacaan data saja, gangguan akan terjadi jika dua atau lebih user mengakses database secara simultan dan sedikitnya melakukan suatu perubahan (update), maka dapat menyebabkan ketidak-konsistenan (inconsistencies).
Walaupun masing-masing transaksi tersebut secara terpisah benar, tetapi secara keseluruhan akan menghasilkan output yang salah. Terdapat tiga masalah potensial yang disebabkan oleh concurrency, yaitu:
1.      Masalah kehilangan modifikasi (Lost Updates Problem)
Sebuah transaksi kedua menulis nilai kedua dari data-item (datum) di atas nilai pertama yang ditulis oleh transaksi konkuren pertama, dan nilai pertama hilang untuk transaksi lainnya berjalan bersamaan yang membutuhkan, dengan prioritas mereka, untuk membaca nilai pertama. Transaksi yang telah membaca akhir nilai yang salah dengan hasil yang salah.
2.      Masalah modifikasi sementara (Uncommitted Dependency Problem)
Transaksi membaca nilai yang ditulis oleh transaksi yang telah kemudian dibatalkan. Nilai ini menghilang dari database pada abort, dan tidak seharusnya dibaca oleh setiap transaksi ("membaca kotor"). Pembacaan transaksi diakhiri dengan hasil yang salah.
3.      Masalah Analisa yang tidak konsisten (Inconsistent Analysis Problem)
Ketika satu transaksi mengambil ringkasan atas nilai dari semua contoh item-data ulang, sebuah update transaksi kedua beberapa kasus itu barang-data. Ringkasan yang dihasilkan tidak mencerminkan hasil yang benar untuk setiap (biasanya diperlukan untuk pembenaran) agar mengutamakan antara dua transaksi (jika dijalankan sebelum yang lain), melainkan beberapa hasil acak, tergantung pada waktu update, dan apakah tertentu Hasil update telah dimasukkan dalam ringkasan atau tidak.

B.     Concurrency Control dalam Database
Concurrency control dalam sistem manajemen database, lain transaksional benda, dan aplikasi terdistribusi yang terkait (misalnya, komputasi Grid dan Cloud computing ) memastikan bahwa database transaksi dilakukan bersamaan tanpa melanggar integritas data dari masing-masing database . Jadi kontrol concurrency merupakan elemen penting untuk pembenaran dalam sistem dimana transaksi basis data dua atau lebih, dilaksanakan dengan waktu tumpang tindih, dapat mengakses data yang sama, misalnya, hampir di setiap sistem database untuk tujuan umum. Akibatnya tubuh besar penelitian terkait telah terakumulasi karena sistem database yang telah muncul pada awal tahun 1970. Sebuah didirikan concurrency dengan baik kontrol teori untuk sistem database diuraikan dalam referensi disebutkan di atas: serializability teori , yang memungkinkan untuk secara efektif desain dan menganalisis metode kontrol concurrency dan mekanisme. Sebuah teori alternatif untuk mengontrol concurrency transaksi atom lebih dari tipe data abstrak, dan tidak digunakan di bawah ini. Teori ini lebih halus, dengan lingkup yang lebih luas, namun kurang digunakan dalam literatur Database dari teori klasik di atas. Teori Masing-masing memiliki kelebihan dan kontra, penekanan dan wawasan . Untuk beberapa hal mereka saling melengkapi, dan penggabungan mereka mungkin berguna.
Untuk memastikan kebenaran, DBMS biasanya menjamin bahwa hanya serializable transaksi jadwal yang dihasilkan, kecuali serializability ini sengaja santai untuk meningkatkan kinerja, tetapi hanya dalam kasus di mana aplikasi yang benar tidak dirugikan. Untuk menjaga kebenaran dalam kasus gagal (dibatalkan) transaksi (yang selalu bisa terjadi karena berbagai alasan) jadwal juga perlu memiliki recoverability (dari batalkan) properti. Sebuah DBMS juga menjamin bahwa tidak ada efek transaksi komitmen ini hilang, dan tidak ada efek dibatalkan ( kembali digulung transaksi) tetap dalam database terkait. Secara keseluruhan transaksi karakterisasi biasanya diringkas oleh ACID aturan di bawah ini. Seperti database telah menjadi didistribusikan, atau diperlukan untuk bekerja sama dalam lingkungan terdistribusi (misalnya, Federated database pada awal tahun 1990, dan Cloud komputasi saat ini), distribusi efektif mekanisme kontrol concurrency telah mendapat perhatian khusus.

C.     Transaksi Database dan Aturan ACID
Arti Transaksi : “Sebuah transaksi adalah unit eksekusi program yang mengakses dan mungkin mengubah beberapa item data”. Dalam Konsep transaksi di database harus di penuhi empat sifat database agar integritas database tetap terjaga. Adapun keempat sifat tersebut adalah :
·         Atomicity: Setiap transaksi harus dijamin untuk dapat sukses dalam melakukan aksinya atau jika gagal , maka tidak berpengaruh apapun terhadap database.
·         Consistency: Setiap transaksi adalah sebuah aksi kombinasi secara logikal dari sebuah state database yang konsisten ke state yang lain dengan tetap menjaga kekonsisten-an database tersebut.
·         Isolation: Meskipun ada beberapa transaksi yang berlangsung bersamaan, masing-masing transaksi tidak boleh mengetahui transaksi lain yang sedang berlangsung. Hasil transaksi sementara harus disembunyikan dari transaksi lain yang sedang berlangsung . (level transparansi transaksi dapat di set).
·         Durability: Setelah sebuah transaksi sukses dilakukan, perubahan-perubahan yang dibuatnya terhadap database bersifat permanen, bahkan jika terjadi kegagalan sistem sekalipun.

D.    Subsistem Transaksi DBMS (DBMS Transaction Subsystem)
Transaction Manager mengkoordinasikan transaksi untuk kepentingan program aplikasi, yang saling berkomunikasi dengan scheduler, yaitu modul yang bertanggung jawab mengenai implementasi strategi khusus untuk control concurrency. Scheduler kadang mangacu pada Lock Manager, jika protokol control concurrency berdasarkan penguncian (locking).
Tujuan dari scheduler adalah memaksimalkan concurrency tanpa memungkinkan transaksi yang sedang dieksekusi untuk mempengaruhi / saling mempengaruhi dengan transaksi lainnya. Jika terjadi kegagalan, maka database dapat menjadi tidak konsisten. Hal tersebut merupakan tugas bagi recovery manager untuk memastikan database dikembalikan ke saat sebelum dilakukannya transaksi.
Akhirnya, buffer manager bertanggung jawab untuk mengirimkan data antar penyimpanan disk dengan main memory.
E.     Serializability dan Recoverability
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.

F.      Schedule
Schedule adalah sebuah urutan dari operasi-operasi oleh satu set transaksi yang jalan bersamaan yang menjaga urutan operasi pada setiap transaksi individual. 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. NonSerial Schedule adalah sebuah schedule di mana operasi-operasi dari satu set concurrent transactions mengalami interleaved. 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:
·         Jika dua transaksi hanya membaca satu item data yang sama, dua transaksi tersebut tidak mengalami konflik dan urutan menjadi tidak penting.
·         Jika dua transaksi melakukan operasi membaca ataupun menulis pada item data yang berbeda, dua transaksi tersebut tidak mengalami konflik dan urutan menjadi tidak penting.
·         Jika satu transaksi menulis sebuah item data dan transaksi lain baik membaca ataupun menulis pada item data yang sama, maka urutan eksekusi itu menjadi penting.
G.    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.

H.    Metode Locking
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. 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. Jika sebuah transaksi mempunyai sebuah exclusive lock pada sebuah item data, transaksi tersebut dapat membaca dan mengubah item data.

1.      Lock digunakan dengan cara sebagai berikut:
·       Transaksi apapun yang membutuhkan akses pada sebuah item data harus melakukan lock terhadap item tersebut, meminta shared lock untuk akses membaca saja atau sebuah exclusive lock untuk akses membaca dan menulis.
·       Jika item belum dikunci oleh transaksi lain, lock tersebut akan dikabulkan
·       Jika item sedang dikunci, DBMS menentukan apakah permintaan ini compatible dengan lock saat ini. Jika diminta shared lock pada sebuah item yang sudah mempunyai shared lock terpasang padanya, permintaan itu akan dikabulkan. Selain itu, transaksi harus menunggu sampai lock yang ada terlepas.
·       Sebuah transaksi lanjut memegang lock sampai transaksi tersebut melepasnya baik pada waktu eksekusi ataupun pada waktu transaksi tersebut berakhir (abort atau commit). Efek operasi tulis akan terlihat pada transaksi lain hanya pada waktu exclusive lock telah dilepas.
2.      Two Phase Locking adalah sebuah transaksi yang mengikuti protokol two-phase locking jika semua operasi locking mendahului operasi unlock pertama pada transaksi.
Aturan-aturannya adalah sebagai berikut :
·         Sebuah transaksi harus mendapatkan sebuah lock pada item sebelum beroperasi pada item tersebut. Lock tersebut bisa berupa baca atau tulis, tergantung dari tipe akses yang dibutuhkan
·         Sebelum transaksi melepaskan sebuah lock, transaksi tersebut tidak akan pernah mendapatkan lock baru lainnya.
3.      Deadlock
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. Ada tiga cara untuk menangani deadlock, yaitu timeout, deadlock prevention dan deadlock detection and recovery.

4.      Timeout
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.

5.      Deadlock Prevention
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.

6.      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
·         Buat sebuah node untuk setiap transaksi.
·         Buat sebuah directed edge Ti → Tj , jika transaksi Ti menunggu untuk melakukan lock sebuah item yang sedang di-lock oleh Tj.

1 komentar: