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.
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.
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
TOOL
Google Translate (sebagai alat bantu pendekatan)
