Mengenal Transaction & Concurrency Control

Bpk-bpk dan ibu-ibu yang saya hormati, selamat malam, terimaksih atas perhatian dan kesempatan yang diberikan kepada kami. Perkenankan kelompok kami untuk menyampaikan materi terkait sistem terdistribusi dengan judul "Transaction & Concurrency Control". Berikut adalah beberapa hal yang baru bisa kami pahami.

Mengenal Transaction & Concurrency Control

Pokok Bahasan:

Abstract
Introduction
Transactions
Nested transactions
Locks
Optimistic concurrency control
Timestamp ordering
Comparison of methods for concurrency control.

1. Abstract

Bab ini akan membahas tentang penerapan transactions and concurrency control terhadap shared objects yang dikelola oleh servers.

Transaksi mendefinisikan serangkaian operasi server yang dijamin oleh server atomic dalam menghadapi multiple clients dan server crashes.

Nested transactions (Transaksi bersarang / transaksi dalam transaksi) disusun dari set transaksi lainnya. Mereka sangat berguna dalam sistem terdistribusi karena memungkinkan konkurensi tambahan.

Semua protokol concurrency control didasarkan atas kriteria serial equivalence dan berasal dari aturan main yang sudah ditetapkan dalam mengatasi konflik antar operasi. Dijelaskan dalam 3 metode berikut:

Locks (kunci) digunakan untuk memesan transaksi yang sedang mengakses objek yang sama sesuai dengan urutan kedatangan operasi mereka. (kami memahaminya seperti saat memesan no. antrian di loket(object) yang sama).

Berbicara tentang serial equivalence, menurut KBBI daring; Equivalen berarti mempunyai nilai (ukuran, arti, atau efek) yang sama; seharga; sebanding; sepadan. Hal ini ditandai dengan method-method / fungsi-fungsi yang digunakan oleh setiap transaksi. Anda dapat melihatnya pada Gb.1, yang mana transaksi T dan transaksi U sama-sama menggunakan method/fungsi getBalance(), setBalance, dan withdraw(), itu artinya kedua transaksi tersebut akan memberikan efek yang sama terhadap resource. Serial berarti berturut-turut; berurutan; bersambungan, hal ini ditandai dengan pola proses transaksi antar keduanya, dimana keduanya saling bergantian dan berurutan.

Gb.1 - a serially equivalent interleaving of T and U

Optimistic concurrency control memungkinkan transaksi berlanjut sampai mereka siap untuk commit, dimana sebuah cek dibuat untuk melihat apakah operasi yang mereka lakukan mengalami konflik atau tidak terhadap objek. Kami memahami ini seperti saat bekerja dengan github.

Gb. 2 - Transaksi Sebelum Commit Pada Github Desktop

Timestamp ordering menggunakan timestamps untuk memesan transaksi yang sedang mengakses objek yang sama, sesuai dengan waktu mulai mereka.

Timestamps adalah waktu yang sedang berlangsung direkam oleh komputer melalui mekanisme seperti Network Time Protocol (NTP), sehingga komputer dapat mempertahankan waktu akurat saat ini. Ketepatan seperti ini memungkinkan komputer dan aplikasi daring dapat berkomunikasi dengan efektif.

Goalnya (target pencapaian) Transaksi adalah untuk menjamin semua object yang ditangani oleh server tetap dalam keadaan konsisten pada saat object -- object tersebut diakses oleh beberapa macam transaksi dan juga pada saat terjadi crash pada server.

Recoverable objects adalah object yang dapat dipulihkan setelah terjadinya crash.

2. Introduction

Sebuah transaksi yang dilakukan oleh client merupakan suatu rangkaian operasi pada object (mengakses object) diberlakukan sebagai unit yang terpisahkan dari server yang mengelola object tersebut.

Server harus menjamin bahwa ketika seluruh transaksi telah dilakukan, maka hasilnya disimpan pada permanent storage atau jika terdapat crash pada satu atau lebih object, efeknya harus dihilangkan seluruhnya.

Transaksi seorang client juga dapat dianggap terpisahkan dari client lainnya, dalam artian bahwa operasi dari satu transaksi tidak dapat digunakan untuk mengamati efek parsial operasi transaksi lainnya.

Untuk menjelaskan beberapa poin dalam bab ini, maka kami menggunakan contoh perbankan, ditunjukan pada Gb. 3, dimana setiap akun diwakili oleh remote object yang interface-nya, account-nya, menyediakan operasi untuk membuat deposit, withdrawals, membaca saldo dan mengatur saldo. Setiap branch of the bank diwakili oleh sebuah remote object yang interface-nya, branch-nya, menyediakan operasi untuk membuat akun baru, mencari akun berdasarkan nama, dan membaca total dana di branch tersebut.

Gb. 3 - Method-method Perbankan

2.1. Simple synchronization (without transactions)

Salah satu isu yang sering ditemui berhubungan dengan masalah transaksi adalah saling mengganggunya informasi satu client dengan client yang lain. Hal tersebut dapat menimbulkan kesalahan nilai pada object.

Atomic operations pada server, telah diketahui bahwa penggunaan multi threads sangat bermanfaat bagi server, selain itu penggunaan threads memperbolehkan operasi dari beberapa client untuk berjalan secara bersamaan dan mengakses object yang sama. Oleh sebab itu, method object -- object harus didesain untuk digunakan pada konteks multi thread.

Atomic Operations adalah pecahan operasi terkecil yang bebas dari gangguan operasi lain dalam threads lain.

Sebagai contoh, dibuat method pada kelas yang menjamin pengaksesan object unik (dibatasi hanya diperbolehkan satu saja).

Public synchronized void deposit(int amount) throws RemoteExceptions{
//adds amount to the balance of the amount
}

Jika satu thread memanggil method sinkronisasi pada sebuah object, maka object tersebut akan dikunci sehingga thread lain yang memanggil object tersebut akan diblok sampai kunci pada objectnya dilepaskan. Sinkronisasi ini mengharuskan pengeksekusian thread terpisah dalam satuan waktu dan menjamin variabel dalam object diakses secara konsisten.

Penggunaan method sinkronisasi dalam java adalah untuk mencapai atomic operations ini.

Namun, dalam bahasa pemrograman lain untuk lingkungan multi thread server, operasi pada object masih membutuhkan atomic operations untuk menjaga agar objectnya konsisten.

Synchronization (Sinkronisasi)

Adalah proses yang mengontrol jalannya beberapa proses dalam waktu yang bersamaan. Bertujuan untuk menghindari inkonsistensi data karena pengaksesan oleh beberapa proses berbeda (mutual exclusion), serta mengatur urutan jalannya proses-proses tersebut, sehingga dapat berjalan dengan lancar dan terhindar dari deadlock atau starvation.

Peningkatan kerjasama client dengan sinkronisasi operasi server, client bisa saja menggunakan server untuk berbagi resource yang dimilikinya. Untuk mengupdate objek pada server tersebut, maka bisa dilakukan dengan sebuah operasi, sedangkan client lain menggunakan operasi lainnya untuk mengakses object tersebut.

Sebagai contoh, ada situasi dimana satu client tidak dapat menyelesaikan operasi yang dilakukannya sampai operasi yang dilakukan client lain selesai. Hal ini misalnya situasi dimana satu client menjadi produser dan client lainnya menjadi konsumen. Client yang membutuhkan sumber (konsumen), harus menunggu sampai client yang menjadi produser menyelesaikan operasinya.

The Java wait() & notify() Methods

Pada pemrograman java, 2 method diatas digunakan untuk menyelesaikan problem komunikasi antar threads.

Misalnya threads A memanggil method wait() pada suatu object, maka threads lain bisa menggunakan method lainnya dalam object tersebut. Method notify() dipangil untuk memperingatkan thread lain yang mengakses object tersebut, memberitahukan bahwa telah terjadi perubahan data pada object tersebut (jika terjadi perubahan). Kedua method tersebut akan mempengaruhi status lock pada object tersebut.

2.2. Failure model for transactions

Lampson [1981a] membuat suatu model untuk menggambarkan distributed transactions yang mengalami kegagalan disk, server dan komunikasinya. Model ini mengklaim bahwa algoritma yang digunakannya berhasil mendeteksi adanya kesalahan, namun tidak dapat memprediksi mengenai kelakuan obyek saat terjadi kesalahan. Modelnya dapat dijelaskan sebagai berikut:

Kegagalan penulisan ke storage,
Server crash secara tiba-tiba,
Pesan delay (bisa disebabkan karena duplicate, corrupt).

Desain sistem yang stabil dirancang atas dasar model-model kesalahan/kegagalan yang terjadi pada permanent storage, prosesor serta komunikasinya.

Dalam prakteknya, stable storage menyediakan atomic write operation untuk mengatasi kegagalan, entah itu kesalahan operasi tulis atau kegagalan proses. Stable processor menggunakan stable storage untuk menyediakan proses recovery bilamana terjadinya crash.

3. Transactions

Dalam berbagai situasi, client membutuhkan suatu urutan pemisahan requests (a sequence of separate requests) ke server agar:

Client terbebas dari gangguan operasi client lain yang sedang berjalan bersamaan.
Operasi client dapat diselesaikan sepenuhnya atau operasi tersebut tidak menimbulkan efek tambahan ketika server mengalami crash.

Transaksi berhubungan dengan sistem manajemen database. Transaksi adalah eksekusi program yang mengakses database. Transaksi dikenalkan ke sistem terdistribusi dengan bentuk transaksi file server semisal XDFS [Mitchell and Dion 1982] yang pada konteksnya, transaksi diartikan sebagai eksekusi urutan requests client untuk operasi file.

Transaksi pada obyek terdistribusi disediakan beberapa sistem, semisal Argus [Liskov 1988] dana Arjuna [Shrivastava et al. 1991]. Dari sudut pandang client, transaksi dapat diartikan sebagai urutan operasi yang berbentuk satu langkah tunggal, yang mengubah data dari server dari satu bentuk ke bentuk lainnya.

Atomic transactions

Meliputi; All or nothing: transaksi dapat berhasil sepenuhnya atau tidak sama sekali. Ada dua aspek mengenai hal ini:

Failure automicity: efeknya kecil meskipun server mengalami crash.
Durability: setelah transaksi berhasil, datanya akan disimpan dalam storage. Data yang disimpan dalam storage akan tetap ada meskipun server mengalami crash.
Isolation: tiap -- tiap transaksi harus dilakukan tanpa ada gangguan dari transaksi lain.

Syarat dukungan failure automicity dan durability

Obyeknya harus dapat diperbaiki,
Setiap ada perubahan mengenai obyek harus disimpan pada storage.

Server yang mendukung proses transaksi harus mensinkronkan operasinya untuk menjamin setiap persyaratan mengenai aspek isolation terpenuhi.

Caranya dengan menjalankan transaksi secara serial.
Namun sayangnya, cara ini secara umum ditolak oleh server yang sumbernya dibagi untuk beberapa user.

Tujuan dari server yang mendukung transaksi adalah untuk memaksimalkan penggunaan secara bersamaan. Oleh sebab itu, transaksi diperbolehkan untuk dieksekusi secara bersamaan jika efeknya serupa dengan eksekusi secara serial.

3.1 Concurrency control

Meliputi;

Lost update problem, adalah suatu masalah yang timbul akibat dihiraukannya informasi pada saat ada update dari operasi lain yang hampir bersamaan waktunya.
Inconsistent retrievals, adalah permasalahan mengenai informasi update suatu operasi yang belum didapatkan oleh operasi lain saat operasi tersebut berjalan.
Serial equivalence, adalah kriteria untuk mengkoreksi eksekusi secara bersamaan yang bertujuan untuk menghindari adanya lost update problems dan inconsistent retrievals.
Conflicting operations, adalah adanya konflik antara dua atau lebih operasi yang efeknya saling bertentangan.

Serial equivalence

Sering digunakan sebagai kriteria protokol concurrency control.

Pada dasarnya, kontrol konkurensi dapat dicapai dengan memaksa klien menunggu klien lain menyelesaikan operasinya atau dengan merestart transaksi klien setelah terdeteksi adanya konflik, atau kombinasi dari keduanya.

3.2 Recoverability from aborts (Kemampuan Recovery dari Pembatalan Operasi)

Server harus mencatat setiap efek dari transaksi yang dilakukan dan tidak mencatat efek pembatalan transaksi. Meski demikian, server harus mencegah pembatalan transaksi yang mengganggu transaksi lain yang sedang berlangsung bersamaan.

Masalah -- masalah berkaitan dengan pembatalan transaksi;

"dirty read", adalah masalah yang disebabkan oleh interaksi antara operasi read dan operasi write yang lebih dahulu berlangsung, namun dibatalkan pada obyek yang sama.
"premature writes", adalah masalah yang timbul akibat adanya pembatalan operasi write pada suatu obyek yang mempengaruhi operasi write pada transaksi lain dalam obyek tersebut.

Keduanya dapat terjadi pada saat pengeksekusian transaksi.

"dirty read"

Hal yang perlu diperhatikan bersangkutan dengan terjadinya dirty read. Misalnya:

Recoverability of transactions,

Masalah yang ditimbulkan oleh adanya proses dirty read tidak dapat disembuhkan secara langsung.
Perlu dideteksi sebelumnya dan dicegah agar tidak terjadi.
Pencegahannya dapat dilakukan dengan menambah waktu delay operasi sesudah pembatalan.

Cascading aborts,

Masalah yang timbul pada transaksi sesudah pembatalan.
Transaksi-transaksi lain yang menerima efek pembatalan juga harus dibatalkan.
Untuk menghindari adanya cascading abort, suatu transaksi hanya diperbolehkan membaca obyek yang sudah berhasil proses write. Untuk menjamin hal ini, setiap operasi read harus ditunda sampai operasi write pada obyek yang bersangkutan selesai atau dibatalkan.

"premature writes"

Hal lain yang perlu diperhatikan mengenai masalah recoverability:

Strict executions of transactions, secara umum, transaksi perlu menunda operasi read dan operasi write untuk mencegah terjadinya dirty read dan premature write. Eksekusi transaksi dikatakan 'strict' jika ada penundaan operasi read dan write pada suatu obyek sampai semua transaksi yang sebelumnya menuliskan operasi write pada obyek tersebut telah selesai atau dibatalkan.

Tentative versions, server yang digunakan untuk memperbaiki obyek harus didesain agar server dapat menghapus setiap update obyek yang transaksinya dibatalkan. Untuk melakukan hal ini, semua update selama proses transaksi harus disimpan pada memori volatile pada versi eksperimen. Setiap transaksi harus disediakan dengan masing -- masing set eksperimen pada obyeknya.

Versi eksperimen tersebut kemudian ditransfer ke obyek ketika transaksi terjadi, yang juga sekaligus menuliskannya pada storage. Ketika transaksi dibatalkan, versi eksperimennya juga dihapus.

4. Nested Transactions

Transaksi bersarang adalah mekanisme transaksi yang dibentuk oleh transaksi lainnya. transaksi terluar pada sebuah set transaksi bersarang disebut transaksi level atas. Selain dari pada transaksi level atas maka akan disebut dengan transaksi Sub.

Gb. 4 - Nested Transactions

Transaksi sub pada level yang sama dapat berjalan secara konkuren tetapi akses nya ke objek objek umum menggunakan mekanisme terserialisasi. Seperti pada skema penguncian(locking). Ketika kita akan membedakan bentuk original dari sebuah transaksi dari yang bersarang kita dapat menggunakan skema transaksi datar.

Kelebihan dari transaksi bersarang:

Transaksi -- transaksi sub yang berada pada level yang sama dapat bekerja secara konkuren. Ketika transaksi sub dijalankan pada server yang berbeda mereka dapat bekerja secara parallel.
Transaksi sub dapat melakukan operasi atau mebatalkan operasi secara independen.

Aturan komitmen transaksi bersarang:

Sebuah transaksi dapat berjalan atau batal hanya setelah transaksi anakannya selesai.
Ketika sebuah transaksi sub/anakan selesai, dia akan membuat keputusan independen, antara menjalankan provisionally atau batal.
Ketika transaksi top levelnya batal maka transaksi anakannya akan otomatis dibatalkan.
Ketika transaksi anakannya batal maka transaksi top levelnya akan mengambil keputusan akan membatalkan atau tidak.

Contoh transaksi bersarang:

Transfer $100 from B to A
a.deposit(100)
b.withdraw(100)

Dari contoh diatas dapat dilihat bahwa transaksi top level Transfer dapat dibagi menjadi 2 buah transaksi sub yaitu deposit dan withdraw. Ketika 2 buah transaksi sub itu commit / berjalan maka transaksi top levelnya hamper pasti berjalan. Tetapi jika transaksi top levelnya dibatalkan dalam hal ini transaksi transfer, maka transaksi sub (deposit dan withdraw) juga akan ikut dibatalkan.

5. Locks

Gb. 5 - Contoh operasi lock

Pada contoh diatas terlihat bahwa terdapat 2 buah transaksi T dan U sedang transaksi T melibatkan objek A dan B dan transaksi U melibatkan objek B dan C . dari uraian contoh diatas terlihat bahwa transaksi T bekerja lebih dulu, sehingga dia akan melakukan penguncian terhadap objek B dan objek A pada saat penguncian ini terjadi maka transaksi U akan menunggu sampai tansaksi T benar benar membebaskan objek B. Barulah saat itu transaksi U dapat menggunakan objek B untuk untuk menjalankan transaksinya.

"strict two-phases locking"

Sebuah transaksi dapat batal, sehingga dibutuhkan eksekusi yang ketat untuk mencegah "dirty reads" dan "Premature Write". Pada saat ini sebuah transaksi yang akan membaca atau menulis sebuah objek harus ditunda hingga transaksi lain yang sedang beraktivitas dengan objek objek tersebut menyelesaikan / membatalkan aktivitasnya. Situasi ini disebut "strict two-phases locking".

Sehingga dapat disimpulkan aturan dari konflik operasi tersebut adalah:

Jika transaksi T sedang melakukan kegiatan baca pada sebuah objek maka transaksi U tidak boleh melakukan aktivitas tulis pada objek tersebut.
Jika transaksi T sedang melakukan aktivitas tulis maka transaksi U tidak diperbolehkan melakukan aktivitas baca maupun tulis.

Penggunaan mekanisme strict two-phase locking

1. Ketika sebuah operasi mengakses sebuah objek untuk sebuah transaksi:

Jika objek belum terkunci , maka transaksi akan mengunci objek tersebut dan transaksi dilakukan.
Jika objek sedang dipakai /dikunci oleh transaksi lain maka. Operasi lain dari sebuah transaksi yang berkenaan dari objek tersebut harus menunggu hingga objek tersebut dibebaskan.
Jika sebuah objek memiliki sifat "non-conflicting lock". Penguncian akan di share dan operasi dijalankan.
Jika sebuah objek telah terkunci pada transaksi yang sama. Penguncian akan dipromosikan dan operasi dijalankan . (promosi dalam hal ini sama dengan konteks aturan b).

2. Ketika sebuah transaksi dibatalkan maka server akan membebaskan semua objek yang digunakan.

5.1. Deadlock

Resiko dari penggunaan lock adalah deadlock. Hal ini bisa terjadi manakala keadaan saling tunggu akan pembebasan penguncian terjadi pada Gb. 6.

Gb. 6 - Deadlock

Sehingga dapat disimpulkan bahwa deadlock adalah keadaan dimana setiap member dari group transaksi menunggu member lainnya untuk membebaskan penguncian seperti pada situasi di atas yang kerap disebut keadaan wait-for graph.

Pencegahan

Sebuah solusi pencegahan yang dapat digunakan adalah dengan mengunci semua objek yang digunakan ketika sebuah transaksi mulai berjalan. Sehingga transaksi tersebut tidak akan pernah menuju keadaan deadlock dengan transaksi lainnya. Tetapi masih terdapat kendala yakni meprediksi objek objek mana yang kemungkinan akan dipakai dalam sebuah transaksi tersebut. Dengan mengimplementasikan cara pencegahan ini dapat mengurangi potensi deadlock tetapi memiliki efek samping terjadinya premature locking dan menurunnya konkurensi.

Deteksi deadlock

Deadlock dapat dideteksi dengan menemukan/ mengidentifikasi cycles pada waitfor graph. Setelah itu dipilihlah sebuah transaksi pembatalan untuk merusak cyclenya.

Selain dari pada cara diatas maka digunakan pula cara/ mekanisme timeouts yang memberikan batas waktu operasi kepada setiap transaksi. Sehingga jika deadlock terjadi maka timeouts ini akan menghitung mundur dan jika waktu habis maka transaksi yang terlibat deadlock akan dibatalkan.

5.2. Peningkatan Konkurensi pada Skema Penguncian

Two-version locking
Hierarchic locks
Penguncian hiararki

1. Two-version locking

Pada dasarnya metode ini menekankan pada operasi read yang harus menunggu jika transaksi lain sedang bekerja dengan objek yang sama. Skema ini mengijinkan konkurensi yang lebih ketimbang read-write lock. Transaksi tidak dapat menjalankan operasi penulisannya secara langsung jika transaksi lain yang belum selesai masih melakukan operasi read pada objek yang sama.

2. Hierarchic locks

Pada penguncian hirarkis di setiap level setting parents lock mempunyai efek yang sama seperti setting semua child lock yang sebanding. Pada skema ini setiap node pada hirarki dapat dikunci dan memberikan pemilik dari kunci sebuah akses eksplisit ke node dan akses implicit ke anak anaknya. Contohnya misalkan terjadi operasi read/write di di cabang maka secaara implisit terjadi read/write locks di setiap akun.

3. Penguncian hiararki

Mempunyai kelebihan yaitu mampu mereduksi jumlah penguncian ketika mixedgranularity locking dibutuhkan. Selain itu juga mengijinkan setiap transaksi untuk mengunci bagian yang ukurannya dipilih bergantung dari kebutuhanannya.

6. Optimistic Concurrency Control

Kung dan Robinson telah mengidentifikasi sejumlah kekurangan penguncian dari pewarisan dan pengajukan pendekatan optimistik untuk serialisasi transaksi yang dapat mencegah kerugian tersebut. Kekurangan penguncian tersebut antara lain:

Pemeliharaan kunci mewakili sebuah overhead yang tidak tampak pada sistem yang tidak mendukung konkuren akses ke data bersama. Akantetapi penguncian tetap dibutuhkan untuk berjaga-jaga.
Penggunaan kunci dapat berakhir pada sebuah buntu.
Untuk mencegah pembatalan, kunci tidak dapat dilepas sampai pada akhir transaksi.

Pendekatan alternatif yang diajukan olek Kung dan Robinson dikatakan 'optimistik' karena berdasarkan pada obserfasi yang menyatakan bahwa kemungkinan dua klien mengakses data yang sama adalah kecil. Saat terjadi sebuah konflik , beberapa transaksi secara umum akan dibatalkan dan harus diulang oleh klien.

Fase Transaksi

Fase bekerja: pada fase ini, setiap transsaksi memiliki versi tentatif dari setiap objek yang diperbarui. Kegunaanya adalah memperbolehkan transaksi terhenti disaat fase kerja maupun bila gagal saat validasi, tanpa mempengaruhi objeknya. Opreasi read akan langsung dilakukan. Operasi ini akan mengakses versi tentatif dari transaksi tersebut bila sudah ada. Operasi write akan merekam nilai terbaru dari objek yang ada sebagai nilai tentatif. Bila ada beberapa transaksi yang bersamaan, beberapa nilai tentatif berbeda untuk objek yang sama dapat terjadi.
Fase validasi: saat permintaan closeTransaction diterima, transasksi tersebut divalidasi untuk mengetahui apakah operasi pada objek bermasalah dengan operasi pada transaksi atas objek yang sama. Bila validasi berhasil terbukti sukses, maka transaksi dapat diteruskan. Akan tetapi bila validasi gagal, maka harus ada pembenaran konflik harus dilakukan.
Fase pembaruan: bila transaksi sudah dilakukan dan terbukti valid, maka semua perubahan pada versi tentatif akan permanen.

Validasi transaksi

Validasi menggunakan aturan konflik read-write untuk memastika penjadwalan atas sebuah transaksi tertentu telah setara secara serial. Untuk membantu proses valdasi, setiap transaksi diberi sebuah nomer transaksi saat memasuki fase validasi. Nomer tersebut akan permanen saat transaksi sudah divalidasi. Nomer tersebut berupa sebuah interger yang disusun dengan urutan naik, sehingga sebuah transaksi selalu selesai fase kerjanya setelah semua transaksi yang memiliki nomer yang lebih kecil.

Gb. 7 - Validasi transaksi

Misalnya bila sebuah transaksi diberi nomer Ti selalu mendahului transaksi dengan nomer Tj if i < j.

Karena semua operas read yang terjadi pada transaksi yang overlap dilakukan sebelum validasi Tv dilakukan, maka transaksi tersebut tidak dapat diganggu oleh operasi write pada transaksi yang sama. Validasi transaksi Tv memeriksa apakah read set pada transaksi tersebut overlap dengan write set pada transaksi overlap Ti sebelumnya. bila terjadi overlap, maka validasi gagal.

Pada validasi backward, read set pada transaksi divalidasi dengan membandingkan pada write set transaksi yang sudah dilakukan sebelumnya. sehingga satu-satunya cara untuk menyelesaikan konflik yang ada adalah dengan menghentikan transaksi yang sedang di validasi.

Kontrol optimistik yang konkuren dengan menggunakan validasi backward memerlukan write set pada versi yang terdahulu dari objek yang terkoresponden dengan transaksi yang sedang dilakukan sampai tidak ada transaksi overlap yang tidak valid.

Validasi forward

Dalam validasi forward pada transaksi Tv, write set Tv dibandingkan dengan read set pada semua transaksi overlap yang aktif. Validasi forward memperbolehkan sebuah fakta dimana read set pada sebuah transaksi aktif dapat berubah pada saat validasi. Saat transaksi dibandingkan dengan transaksi valid yang masih aktif, kita memiliki pilihan untuk membatalkan validasi transaksi atau mengambil cara alternatif untuk menyelesaikan konflik. Härder memberikan beberapa solusi alternatif:

Menunda validasi hingga waktu transaksi yang bermasalah telah selesai.
Membatalkan semua transaksi aktif yang bermasalah dan menyatakan transaksi tersebut sudah tervalidasi.
Membatalkan proses validasi transaksi tersebut.

Perbandingan backward dan forward

Dapat dilihat bahwa validasi forward memperbolehkan kelonggaran dalam menangani konflik, sedangan pada validasi backward hanya memiliki satu solusi, membatalkan proses validasi. Akan tetapi validasi backward memiliki keunggulan dalam menyusun write set lama sampai mereka tidak dibutuhkan lagi, sedangkan pada validasi forward harus memperbolehkan transaksi baru dimulai saat proses validasi terjadi.

Starvation

Transaksi yang dibatalkan akan dimulai kembali oleh program klien, akan tetapi transaksi tersebut tetap memiliki kemungkinan untuk gagal saat proses validasi. Ini dapat terjadi bila transaksi tersebut mengalami konlik dengan transaksi lainnya karena penggunaan objek setiap kali transaksi tersebut diulang.

Pencegahan transaksi untuk tidak dapat dilaksanakan disebut starvation yang jarang kali terjadi.

7. Timestamp Ordering

Pada kontrol konkuren yang berdasarkan pada timestamp ordering, setiap opersai pada semua transaksi divaldidasi. Bila operasi tidak dapat divalidasi, transkaksi tersebut langsung dibatalkan dan kemudian diulang oleh program klien. Setiap transkasi ditandai dengan nilai timestamp yang unik pada saat dimulai. Timestamp tersebut mendefinisikan posisinya pada urutan waktu transaksi. Permintaan sebuah transaksi dapat dipesan berdasarkan timestampnya.

Aturan pada timestamp dibuat untuk memastikan agar setia transaksi mengakses sebuah nilai objek yang konsisten. Aturan tersebut juga harus memastikan bahwa versi tentatif pada setiap objek harus diselesaikan dengan urutan yang ditentukan oleh timestamps dari transaksi yang membuatnya.

Seperti biasa, operasi write direkam dalam versi tentatif pada objek dan tidak terlihat sampai transaksi memanggil closeTransaction dan transaksi selesai. Write timestamp dari objek akan lebih awal dari versi tentatifnya, dan read timestamps dapat diwakili oleh jumlah anggota maksimalnya. Pada timestamp ordering, setiap permintaan leh transaksi untuk read atau write pada sebuah objek akan diperiksa apakah sesuai dengan konflik pada operasi. Saat sebuah koordinator menerima permintaan untuk sebuah transaksi, koordinator tersebut akan selalu dapat melakukannya karena setiap operasi dari sebuah transaksi diperiksa secara konsisten oleh transaksi yang sudah dilakukan sebelunya.

Sebuah timestamp method mencegah terjadinya deadlock (buntu), tetapi sangat rawan terhadap terjadinya pengulangan. Sebuah modifikasi yang dikenal sebagai aturan "ignore obsolete write" telah dimplementasikan.

Multiversion timestamp ordering

Pada multiversion timestamp ordering, sebuah daftar objek maupun nilai tentatif objek tersebut disimpan pada masing-masing objek. Daftar ini mewakili sejarah dari nilai objek tersebut. Keuntungan menggunakan beberapa versi adalah operasi read yang datang terlambat tidak perlu ditolak.

8. Comparison of Methods for Concurrency Control

Kita telah mendeskripsikan tiga metode terpisah untuk mengontrol akses konkuren ke data bersama; strict two-phase locking, optimistic methods dan timestamp ordering. Semua metode memiliki beberapa kelebihan dan tempat yang diperlukan, dan ketiganya memiliki batas-batas tertentu untuk operasi konkuren. Beberapa penelitian sistem terdistribusi telah mencari kegunaan dari kunci semantic, timestamp ordering dan pendekatan baru untuk transaksi jarak jauh.

Bekerja pada dua area aplikasi telah menunjukan mekanisme kontrol konkuren tidak selalu memadai. Salah satu dari area yang mengkhawatirkan adalah aplikasi multiuser dimana setiap user berharap dapat melihat pandangan umum objek yang sedang diperbarui oleh user lain. Aplikasi seperti ini membutuhkan data mereka seperti atom saat dihadapkan pada pembaruan yang konkuren dan tabrakan server, dan teknik traksaksi tampak memberikan sebuah pendekatan pada rancangan mereka.

Kebutuhan Aplikasi Berhubungan Dengan Concurrency Control

Pengguna membutuhkan notofikasi langsung atas perubahan yang dilakukan oleh pengguna lain
Pengguna harus bisa mengakses objek sebelum pengguna lain menyelesaikan transaksi mereka, yang menjadi dasar alasan pengembangan tipe baru penguncian yang memicu sebuah aksi saat objek diakses.

Beberapa contoh aplikasi yang menggunakan Concurrency Control

Dropbox
Google apps
Wikipedia.

1. Dropbox

Adalah cloud service yang menyediakan backup file dan memungkinkan user untuk berbagi file dan folder, serta mengaksesnya dari mana saja.

Dropbox menggunakan optimistic form of concurrency control untuk mencatat konsitensi file dan mencegah bentrokan antar pengguna (saat melakuan update).

Jadi jika dua pengguna melakukan update secara concurrent (serentak) pada file yang sama, maka yang lebih awal menulis akan diaccepted dan sisanya direjected. Namun dropbox juga menyediakan versi history, sehingga memungkinkan user menggabungkan updatenya sercara manual atau bisa juga mengembalikannya seperti semula.

2. Google apps

Adalah could service yang menyediakan aplikasi berbasis web seperti word processor, spreadsheet and presentation,yang mana memungkinkan pengguna untuk berkolaborasi. Antar pengguna bisa saling edit dokumen yang sama dalam waktu yang bersamaan. Jika dua pengguna mengakses sel yang sama secara bersamaan, maka yang melakukan update paling akhir adalah pemenangnya.

3. Wikipedia

Memungkinkan editor concurrent (secara serentak/bersamaan) mengakses halaman web tempat menulis konten, editor pertama akan diterima sementara yang lain akan ditampilkan halaman 'edit conflict' dan diminta untuk menyelesaikan konflik tersebut.

Referensi

Coulouris George, Dollimore Jean, and Kindberg Tim, "Distributed Systems Concepts and Design," Fifth Edition, Fi Pearson Education Ltd, 2001. (bahan utama untuk korelasi)
http://whatis.techtarget.com/definition/timestamp (definisi timestamp)
http://te.ugm.ac.id/~risanuri/distributed/ringk/bab12.pdf (terjemahan indonesia)
http://kbbi.web.id/ekuivalen (definisi ekuivalen)
http://kbbi.web.id/serial (definisi serial)

TOOL

Google Translate (sebagai alat bantu pendekatan)

APPENDIX

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 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 T1 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 balz, sehingga T6 sekarang mempunyai hasil yang salah (lebih besar $10).

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.

Schedule

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:

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.

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.

Ubah urutan write(balx) di T8 dengan write(baly) di T7
Ubah urutan read(balx) di T8 dengan read(baly) di T7
Ubah urutan read(balx) di T8 dengan write(baly) di T7

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.

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.

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 ( 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:

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.

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:

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.

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.

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.

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.

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.

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