TRANSAKSI TERDISTRIBUSI

DISTRIBUTED SYSTEMS Concept and Design – Fifth Edition
George Coulouris
Cambridge University
Jean Dollimore
formerly of Queen Mary, University of London
Tim Kindberg
matter 2 media
Gordon Blair
Lancaster University

Bab ini memperkenalkan didistribusikan transaksi - yang melibatkan lebih dari satu
Server. didistribusikan transaksi mungkin datar atau bersarang.
Protokol atom komit adalah prosedur koperasi digunakan oleh satu set server
terlibat dalam transaksi terdistribusi. Hal ini memungkinkan server untuk mencapai keputusan bersama untuk
apakah transaksi dapat dilakukan atau dibatalkan. Bab ini menjelaskan dua fase
commit protocol, yang merupakan paling umum digunakan atom komit protokol.

Bagian pada kontrol concurrency dalam transaksi terdistribusi membahas bagaimana
penguncian, timestamp pemesanan dan kontrol konkurensi optimis dapat diperpanjang untuk digunakan
dengan transaksi terdistribusi.
Penggunaan skema penguncian dapat menyebabkan kebuntuan didistribusikan. didistribusikan kebuntuan algoritma deteksi dibahas dalam Bagian 17.5.
Server yang menyediakan transaksi termasuk manajer pemulihan keprihatinan yang adalah untuk
memastikan bahwa efek dari transaksi pada objek yang dikelola oleh server dapat
pulih ketika diganti setelah kegagalan. Manajer pemulihan menyimpan benda-benda di
penyimpanan permanen bersama dengan daftar niat dan informasi tentang status setiap
transaksi.

17.1PENDAHULUAN

Dalam Bab 16, kita membahas transaksi datar dan bersarang yang diakses objek pada satu
Server. Dalam kasus umum, transaksi, apakah datar atau bersarang, akan mengakses obyek
terletak di beberapa komputer yang berbeda. Kami menggunakan transaksi jangka didistribusikan untuk merujuk
untuk transaksi datar atau bersarang yang mengakses objek yang dikelola oleh beberapa server.
Ketika transaksi terdistribusi berakhir, properti atomicity
transaksi mensyaratkan bahwa baik semua server yang terlibat melakukan transaksi atau semua
dari mereka batalkan transaksi. Untuk mencapai hal ini, salah satu server mengambil koordinator
peran, yang melibatkan memastikan hasil yang sama pada semua server. Cara di
yang koordinator mencapai hal ini tergantung pada protokol yang dipilih. Sebuah protocol dikenal sebagai 'dua fase komit protokol' adalah yang paling umum digunakan. Protokol ini memungkinkan server untuk berkomunikasi dengan satu sama lain untuk mencapai keputusan bersama, apakah untuk  melakukan atau batalkan.
concurrency control dalam transaksi terdistribusi didasarkan pada metode yang dibahas
dalam Bab 16. Setiap server berlaku kontrol concurrency lokal untuk objek sendiri, yang
memastikan bahwa transaksi serial lokal. Tetapi didistribusikan transaksi juga harus
serial global. Bagaimana ini dicapai bervariasi tergantung pada apakah penguncian,
memesan timestamp atau kontrol konkurensi optimis sedang digunakan. Dalam beberapa kasus,
transaksi dapat serial di setiap server, namun siklus dependensi
antara server yang berbeda dapat terjadi dan kebuntuan didistribusikan timbul.
pemulihan transaksi berkaitan dengan memastikan bahwa semua benda yang terlibat dalam
transaksi dapat dipulihkan. Selain itu, menjamin bahwa nilai-nilai dari
benda mencerminkan semua perubahan yang dilakukan oleh transaksi yang dilakukan dan tidak ada yang dibuat
oleh orang-orang dibatalkan.






17.2 FLAT DAN nested TRANSAKSI TERDISTRIBUSI

Sebuah transaksi klien menjadi didistribusikan jika memanggil operasi di beberapa berbeda
server. Ada dua cara yang berbeda yang didistribusikan transaksi dapat terstruktur: sebagai
transaksi datar dan transaksi sebagai bersarang.
Dalam transaksi datar, klien membuat permintaan untuk lebih dari satu server. Sebagai contoh,
pada Gambar 17.1 (a), transaksi T adalah transaksi datar yang memanggil operasi pada objek dalam
server X, Y dan Z. Sebuah transaksi klien datar melengkapi setiap permintaan sebelum pergi
Ke yang berikutnya. Oleh karena itu, setiap transaksi mengakses objek server 'berurutan.
Ketika server menggunakan penguncian, transaksi hanya dapat menunggu satu objek pada satu waktu.
Dalam transaksi bersarang, transaksi top-level dapat membuka subtransactions, dan
setiap subtransaction dapat membuka subtransactions lebih bawah untuk setiap kedalaman bersarang.
Gambar 17.1 (b) menunjukkan T transaksi klien yang membuka dua subtransactions, T1 dan T2,
yang mengakses obyek di server X dan Y. subtransactions T1 dan T2 membuka lebih lanjut
subtransactions T11, T12, T21, dan T22, yang mengakses objek pada server M, N dan P. Dalam
bersarang kasus, subtransactions pada tingkat yang sama dapat berjalan secara bersamaan,

sehingga T1 dan T2 yang
bersamaan, dan karena mereka memanggil objek di server yang berbeda, mereka dapat berjalan secara paralel. Itu
empat subtransactions T11, T12, T21 dan T22 juga berjalan bersamaan.

ta baru telah bergabung dengan transaksi Trans.







17.2.1 Koordinator transaksi terdistribusi
Server yang menjalankan permintaan sebagai bagian dari transaksi terdistribusi harus dapat
berkomunikasi dengan satu sama lain untuk mengkoordinasikan tindakan mereka saat transaksi melakukan.
Seorang klien mulai transaksi dengan mengirim permintaan Transaksi terbuka untuk koordinator di
server apapun, seperti yang dijelaskan dalam Bagian 16.2. Koordinator yang dihubungi melaksanakan
Transaksi terbuka dan mengembalikan pengenal yang dihasilkan transaksi (TID) ke klien.
pengidentifikasi transaksi untuk transaksi terdistribusi harus unik dalam didistribusikan
sistem. Cara mudah untuk mencapai ini adalah untuk TID mengandung dua bagian: pengenal (untuk
Misalnya, alamat IP) dari server yang menciptakannya dan nomor unik ke server.
Koordinator yang membuka transaksi menjadi koordinator untuk
didistribusikan transaksi dan pada akhirnya bertanggung jawab untuk melakukan atau menggugurkannya. Setiap
server yang mengelola objek diakses oleh transaksi adalah peserta di
transaksi dan memberikan sebuah objek yang kita sebut peserta. Setiap peserta adalah
bertanggung jawab untuk melacak semua benda dipulihkan pada server yang
yang terlibat, dalam transaksi. Peserta bertanggung jawab untuk bekerja sama dengan
Koordinator dalam melaksanakan komit protokol.
Selama kemajuan transaksi, koordinator mencatat daftar referensi
kepada para peserta, dan setiap peserta mencatat referensi ke koordinator.
Gambar 17.3 Sebuah transaksi perbankan didistribusikan
..
Catatan: koordinator adalah di salah satu server, misalnya, BranchX
Antarmuka untuk Koordinator ditunjukkan pada Gambar 13.3 memberikan tambahan
Metode, bergabung, yang digunakan setiap kali peserta baru bergabung transaksi:
bergabung (Trans, referensi untuk peserta)
Menginformasikan koordinator yang peserta baru telah bergabung dengan transaksi Trans.

koordinator mencatat peserta baru dalam daftar peserta nya. fakta bahwa
Koordinator tahu semua peserta dan setiap peserta tahu koordinator kehendak
memungkinkan mereka untuk mengumpulkan informasi yang akan dibutuhkan pada waktu komit.
Gambar 17.3 menunjukkan klien (datar) transaksi perbankan yang melibatkan rekening A,
B
, C dan D di server BranchX, bercabang dan BranchZ. transaksi klien, T,
transfer $ 4 dari rekening A ke rekening C dan kemudian mentransfer $ 3 dari akun B ke
Akun D. Transaksi dijelaskan di sebelah kiri diperluas untuk menunjukkan bahwa
openTransaction dan closeTransaction diarahkan ke koordinator, yang akan
terletak di salah satu server yang terlibat dalam transaksi. Setiap server ditunjukkan dengan
peserta, yang bergabung transaksi dengan menerapkan metode bergabung dalam koordinator.
Ketika klien memanggil salah satu metode dalam transaksi, misalnya
b.withdraw (T, 3), objek menerima doa (B di bercabang, dalam kasus ini)
menginformasikan objek pesertanya bahwa objek milik T. transaksi Jika belum
sudah diberitahu koordinator, objek peserta menggunakan operasi bergabung untuk melakukannya.
Dalam contoh ini, kita menunjukkan pengenal transaksi yang lulus sebagai tambahan
Argumen sehingga penerima dapat menularkannya kepada koordinator. Pada saat klien
panggilan closeTransaction, koordinator memiliki referensi untuk semua peserta.
Perhatikan bahwa adalah mungkin bagi peserta untuk memanggil abortTransaction di koordinator
jika untuk beberapa alasan tidak dapat melanjutkan transaksi.

17.3 Atom komit protokol
Transaksi komit protokol yang dirancang pada awal tahun 1970, dan dua-fase
commit protocol muncul di Gray [1978]. Atomicity properti transaksi
mensyaratkan bahwa ketika transaksi terdistribusi berakhir, baik semua operasinya
dilakukan atau tidak satupun dari mereka. Dalam kasus transaksi terdistribusi, klien memiliki
meminta operasi di lebih dari satu server. Sebuah transaksi berakhir ketika
permintaan klien yang akan dilakukan atau dibatalkan. Cara mudah untuk menyelesaikan transaksi
dengan cara atom adalah untuk koordinator untuk mengkomunikasikan melakukan atau membatalkan permintaan
untuk semua peserta dalam transaksi dan untuk terus mengulangi permintaan sampai semua
dari mereka telah mengakui bahwa mereka telah melakukan itu. Ini adalah contoh dari satu fase atom komit protokol.
Ini sederhana satu-fase atom komit protokol tidak memadai, meskipun, karena
tidak memungkinkan server untuk membuat keputusan sepihak untuk membatalkan transaksi ketika
permintaan klien komit. Alasan yang mencegah server dari mampu untuk melakukan nya
bagian dari transaksi umumnya berhubungan dengan masalah kontrol concurrency. Sebagai contoh, jika
penguncian digunakan, resolusi kebuntuan dapat menyebabkan batal transaksi
tanpa klien menyadari kecuali itu membuat permintaan lain ke server. juga jika
kontrol konkurensi optimis digunakan, kegagalan validasi di server akan menyebabkan
itu untuk memutuskan untuk membatalkan transaksi. Akhirnya, koordinator mungkin tidak tahu jika server memiliki
jatuh dan digantikan selama kemajuan transaksi terdistribusi - seperti server
harus membatalkan transaksi.

Dua-fase komit protokol dirancang untuk memungkinkan peserta untuk membatalkan nya
bagian dari transaksi. Karena persyaratan untuk atomicity, jika salah satu bagian dari transaksi adalah
dibatalkan, maka seluruh transaksi harus dibatalkan. Pada tahap pertama dari protokol,
setiap orang peserta untuk transaksi yang akan dilakukan atau dibatalkan. Setelah peserta
telah memutuskan untuk melakukan transaksi, tidak diperbolehkan untuk membatalkan itu. Oleh karena itu, sebelum
Peserta suara untuk melakukan transaksi, itu harus memastikan bahwa pada akhirnya akan dapat
melaksanakan bagiannya dari komit protokol, bahkan jika itu gagal dan diganti sementara. SEBUAH
peserta dalam transaksi dikatakan dalam keadaan siap untuk transaksi jika itu akan
akhirnya bisa melakukan itu. Untuk memastikan hal ini, masing-masing peserta menghemat di
penyimpanan permanen semua objek yang telah diubah dalam transaksi, bersama-sama dengan
statusnya - disiapkan.
Pada tahap kedua protokol, setiap peserta dalam transaksi melakukan
keputusan bersama. Jika salah satu peserta suara untuk membatalkan, maka keputusan harus untuk membatalkan
transaksi. Jika semua peserta memilih untuk melakukan, maka keputusannya adalah untuk komit
transaksi.
Masalahnya adalah untuk memastikan bahwa semua peserta memilih dan bahwa mereka semua mencapai
keputusan yang sama. Hal ini cukup sederhana jika tidak ada kesalahan terjadi, tetapi protokol harus bekerja
benar bahkan ketika beberapa server gagal, pesan yang hilang atau server untuk sementara

17.3.1 Dua fase komit protokol
Selama kemajuan transaksi, tidak ada komunikasi antara koordinator
dan peserta selain dari peserta menginformasikan koordinator ketika mereka bergabung
transaksi. permintaan A klien untuk melakukan (atau membatalkan) transaksi diarahkan ke
koordinator. Jika permintaan klien membatalkan transaksi, atau jika transaksi dibatalkan oleh
salah satu peserta, koordinator menginformasikan semua peserta segera. Ini adalah ketika
klien meminta koordinator untuk melakukan transaksi yang dua-tahap komit
protokol datang ke digunakan.
Pada tahap pertama dari dua tahap melakukan protokol koordinator meminta semua
peserta apakah mereka siap untuk melakukan; kedua, ia memberitahu mereka untuk melakukan (atau
batalkan) transaksi. Jika peserta dapat melakukan bagiannya dari transaksi, itu akan setuju
segera setelah mencatat perubahan itu telah membuat (ke objek) dan statusnya di

Gambar 17.4 Operasi untuk dua fase komit protokol
canCommit? (trans) o Ya / Tidak
Panggilan dari koordinator kepada peserta untuk bertanya apakah bisa melakukan transaksi.
Peserta menjawab dengan suara nya.
doCommit (trans)
Panggilan dari koordinator kepada peserta untuk memberitahu peserta untuk melakukan bagiannya dari
transaksi.
doAbort (trans)
Panggilan dari koordinator kepada peserta untuk memberitahu peserta untuk membatalkan bagiannya dari transaksi.
telah Berkomitmen (trans, peserta)
Panggilan dari peserta untuk koordinator untuk mengkonfirmasi bahwa mereka telah melakukan transaksi.
getDecision (trans) o Ya / Tidak
Panggilan dari peserta untuk koordinator untuk meminta keputusan pada transaksi ketika
telah sebagai Ya tapi masih tidak punya balasan setelah beberapa penundaan. Digunakan untuk memulihkan dari server
kecelakaan atau pesan tertunda.
BAGIAN 17,3 ATOMIC COMMIT PROTOKOL 733
Oleh karena itu penyimpanan permanen dan siap untuk melakukan. Koordinator dalam didistribusikan
transaksi berkomunikasi dengan peserta untuk melaksanakan dua fase komit
protokol dengan cara operasi diringkas dalam Gambar 17.4. metode
canCommit, doCommit dan doAbort metode dalam antarmuka dari peserta. Itu
metode haveCommitted dan getDecision berada di antarmuka koordinator.
Dua-tahap melakukan protokol terdiri dari fase voting dan penyelesaian suatu
fase, seperti yang ditunjukkan pada Gambar 17.5. Pada akhir langkah 2, koordinator dan semua
peserta yang sebagai Ya siap untuk berkomitmen. Pada akhir langkah 3, transaksi
secara efektif selesai. Pada langkah 3a koordinator dan peserta berkomitmen,
sehingga koordinator dapat melaporkan keputusan untuk berkomitmen klien. Pada 3b koordinator
melaporkan keputusan untuk membatalkan ke klien.
Pada langkah 4 peserta mengkonfirmasi bahwa mereka telah melakukan sehingga koordinator
tahu kapan informasi itu telah mencatat tentang transaksi tersebut tidak lagi diperlukan.
Protokol tampaknya sederhana ini bisa gagal karena salah satu atau lebih dari
server menabrak atau karena gangguan dalam komunikasi antara server. untuk menangani
dengan kemungkinan menabrak, setiap server menyimpan informasi yang berkaitan dengan dua fase
commit protocol dalam penyimpanan permanen. Informasi ini dapat diambil oleh baru
Proses yang mulai mengganti server jatuh. Aspek pemulihan didistribusikan
transaksi dibahas dalam Bagian 17.6.
Pertukaran informasi antara koordinator dan peserta bisa gagal
ketika salah satu server crash, atau ketika pesan hilang. Timeout digunakan untuk menghindari
proses memblokir selamanya. Ketika timeout terjadi pada proses, itu harus mengambil
tindakan yang tepat. Untuk memungkinkan untuk protokol termasuk tindakan batas waktu untuk setiap langkah
di mana proses dapat menghalangi. Tindakan ini dirancang untuk memungkinkan fakta bahwa dalam
sistem asynchronous, timeout mungkin tidak selalu berarti bahwa server telah gagal.



Dua-fase komit protokol dirancang untuk memungkinkan peserta untuk membatalkan nya

bagian dari transaksi. Karena persyaratan untuk atomicity, jika salah satu bagian dari transaksi adalah

dibatalkan, maka seluruh transaksi harus dibatalkan. Pada tahap pertama dari protokol,

setiap orang peserta untuk transaksi yang akan dilakukan atau dibatalkan. Setelah peserta

telah memutuskan untuk melakukan transaksi, tidak diperbolehkan untuk membatalkan itu. Oleh karena itu, sebelum

Peserta suara untuk melakukan transaksi, itu harus memastikan bahwa pada akhirnya akan dapat

melaksanakan bagiannya dari komit protokol, bahkan jika itu gagal dan diganti sementara. SEBUAH

peserta dalam transaksi dikatakan dalam keadaan siap untuk transaksi jika itu akan

akhirnya bisa melakukan itu. Untuk memastikan hal ini, masing-masing peserta menghemat di

penyimpanan permanen semua objek yang telah diubah dalam transaksi, bersama-sama dengan

statusnya - disiapkan.

Pada tahap kedua protokol, setiap peserta dalam transaksi melakukan

keputusan bersama. Jika salah satu peserta suara untuk membatalkan, maka keputusan harus untuk membatalkan

transaksi. Jika semua peserta memilih untuk melakukan, maka keputusannya adalah untuk komit

transaksi.

Masalahnya adalah untuk memastikan bahwa semua peserta memilih dan bahwa mereka semua mencapai

keputusan yang sama. Hal ini cukup sederhana jika tidak ada kesalahan terjadi, tetapi protokol harus bekerja

benar bahkan ketika beberapa server gagal, pesan yang hilang atau server untuk sementara

tidak dapat berkomunikasi dengan satu sama lain.

Model gagal untuk melakukan protokol • Bagian 16.1.2 menyajikan model kegagalan untuk

transaksi yang berlaku sama untuk dua-fase (atau lainnya) commit protocol.

Komit protokol dirancang untuk bekerja dalam sebuah sistem asynchronous dimana server

mungkin crash dan pesan mungkin akan hilang. Hal ini diasumsikan bahwa yang mendasari permintaan-balasan

protokol menghapus pesan korup dan digandakan. Tidak ada kesalahan Bizantium -

server baik crash atau mentaati pesan mereka akan dikirim.

Dua-tahap melakukan protokol adalah contoh dari protokol untuk mencapai

konsensus. Bab 15 menegaskan bahwa konsensus tidak dapat dicapai dalam asynchronous

sistem jika proses kadang-kadang gagal. Namun, dua-tahap melakukan protokol tidak mencapai

konsensus dalam kondisi seperti itu. Hal ini karena kegagalan kecelakaan dari proses yang bertopeng

dengan mengganti proses jatuh dengan proses baru yang negara diatur dari informasi

disimpan dalam penyimpanan permanen dan informasi yang dimiliki oleh proses lainnya.

17.3.1 Dua fase komit protokol

Selama kemajuan transaksi , tidak ada komunikasi antara koordinator

dan peserta selain dari peserta menginformasikan koordinator ketika mereka bergabung

transaksi . permintaan A klien untuk melakukan ( atau membatalkan ) transaksi diarahkan ke

koordinator. Jika klien meminta abortTransaction , atau jika transaksi dibatalkan oleh

salah satu peserta , koordinator menginformasikan semua peserta segera . Ini adalah ketika

klien meminta koordinator untuk melakukan transaksi yang dua - tahap komit

protokol datang ke digunakan .

Pada tahap pertama dari dua tahap melakukan protokol koordinator meminta semua

peserta apakah mereka siap untuk melakukan ; kedua, ia memberitahu mereka untuk melakukan ( atau

batalkan ) transaksi . Jika peserta dapat melakukan bagiannya dari transaksi , itu akan setuju

segera setelah mencatat perubahan itu telah membuat ( ke objek ) dan statusnya di

17.4 Operasi untuk dua fase komit protokol



canCommit ? ( trans ) o Ya / Tidak

Panggilan dari koordinator kepada peserta untuk bertanya apakah bisa melakukan transaksi .

Peserta menjawab dengan suara nya.

doCommit ( trans )

Panggilan dari koordinator kepada peserta untuk memberitahu peserta untuk melakukan bagiannya dari

transaksi.

doAbort ( trans )

Panggilan dari koordinator kepada peserta untuk memberitahu peserta untuk membatalkan bagiannya dari transaksi .

haveCommitted ( trans , peserta )

Panggilan dari peserta untuk koordinator untuk mengkonfirmasi bahwa mereka telah melakukan transaksi .

getDecision ( trans ) o Ya / Tidak

Panggilan dari peserta untuk koordinator untuk meminta keputusan pada transaksi ketika

telah sebagai Ya tapi masih tidak punya balasan setelah beberapa penundaan . Digunakan untuk memulihkan dari server

kecelakaan atau pesan tertunda

Oleh karena itu penyimpanan permanen dan siap untuk melakukan. Koordinator dalam didistribusikan

transaksi berkomunikasi dengan peserta untuk melaksanakan dua fase komit

protokol dengan cara operasi diringkas dalam Gambar 17.4.







metode canCommit, doCommit dan doAbort metode dalam antarmuka dari peserta. Itu

metode haveCommitted dan getDecision berada di antarmuka koordinator.

Dua-tahap melakukan protokol terdiri dari fase voting dan penyelesaian suatu

fase, seperti yang ditunjukkan pada Gambar 17.5. Pada akhir langkah 2, koordinator dan semua

peserta yang sebagai Ya siap untuk berkomitmen. Pada akhir langkah 3, transaksi

secara efektif selesai. Pada langkah 3a koordinator dan peserta berkomitmen,

sehingga koordinator dapat melaporkan keputusan untuk berkomitmen klien. Pada 3b koordinator

melaporkan keputusan untuk membatalkan ke klien.

Pada langkah 4 peserta mengkonfirmasi bahwa mereka telah melakukan sehingga koordinator

tahu kapan informasi itu telah mencatat tentang transaksi tersebut tidak lagi diperlukan.

Protokol tampaknya sederhana ini bisa gagal karena salah satu atau lebih dari

server menabrak atau karena gangguan dalam komunikasi antara server. untuk menangani

dengan kemungkinan menabrak, setiap server menyimpan informasi yang berkaitan dengan dua fase

commit protocol dalam penyimpanan permanen. Informasi ini dapat diambil oleh baru

Proses yang mulai mengganti server jatuh. Aspek pemulihan didistribusikan

transaksi dibahas dalam Bagian 17.6.

Pertukaran informasi antara koordinator dan peserta bisa gagal

ketika salah satu server crash, atau ketika pesan hilang. Timeout digunakan untuk menghindari

proses memblokir selamanya. Ketika timeout terjadi pada proses, itu harus mengambil

tindakan yang tepat. Untuk memungkinkan untuk protokol termasuk tindakan batas waktu untuk setiap langkah

di mana proses dapat menghalangi. Tindakan ini dirancang untuk memungkinkan fakta bahwa dalam

sistem asynchronous, timeout mungkin tidak selalu berarti bahwa server telah gagal.

17.5 Dua fase komit protokol



Tahap 1 (fase voting):
1. Koordinator mengirimkan canCommit sebuah? meminta untuk masing-masing peserta dalam
transaksi.
2. Saat peserta menerima canCommit sebuah? memintanya menjawab dengan suaranya (Ya atau
Tidak ada) ke koordinator. Sebelum voting Ya, mempersiapkan untuk melakukan dengan menyimpan benda-benda
dalam penyimpanan permanen. Jika suara adalah ada, peserta dibatalkan segera.
Tahap 2 (penyelesaian sesuai dengan hasil suara):
3. Koordinator mengumpulkan orang (termasuk sendiri).
(A) Jika tidak ada kegagalan dan semua orang yang Ya, koordinator memutuskan untuk
melakukan transaksi dan mengirimkan permintaan doCommit untuk masing-masing
peserta.
(B) Jika tidak, koordinator memutuskan untuk membatalkan transaksi dan mengirimkan doAbort
permintaan untuk semua peserta yang sebagai Ya.
4. Peserta yang sebagai Ya menunggu permintaan Komit atau Abort dari
koordinator. Ketika peserta menerima salah satu pesan ini bertindak
sesuai dan, dalam kasus komit, membuat memiliki Berkomitmen panggilan sebagai
konfirmasi kepada koordinator.Tindakan







 Timeout dalam dua fase komit protokol • Ada berbagai tahapan dalam
protokol di mana koordinator atau peserta tidak bisa maju yang bagian dari protokol
sampai menerima permintaan lain atau balasan dari salah satu orang lain.
Pertimbangkan pertama situasi di mana peserta telah sebagai Ya dan menunggu
koordinator untuk melaporkan hasil pemungutan suara dengan mengatakan itu untuk melakukan atau membatalkantransaksi (langkah 2 pada Gambar 17.6 Gambar 17.6 Komunikasi dalam dua fase komit protokolcanCommit?iya nih de Committelah Berkomitmen Koordinator1 3(Menunggupenilaian)berkomitmenmatangsiap untuk melakukanlangkahPeserta2 4(Pasti)siap untuk melakukan berkomitmen Status Status langkah). peserta seperti tidak pasti hasilnya dan
tidak bisa melanjutkan lebih jauh sampai mendapatkan hasil suara dari koordinator.
peserta tidak bisa memutuskan secara sepihak apa yang harus dilakukan selanjutnya, dan sementara itu obyekdigunakan oleh transaksi yang tidak bisa dilepaskan untuk digunakan oleh transaksi lainnya. peserta
dapat membuat permintaan getDecision untuk koordinator untuk menentukan hasil dari
transaksi. Ketika mendapat balasan, terus protokol pada langkah 4 pada Gambar 17.5. Jika
koordinator telah gagal, peserta tidak akan bisa mendapatkan keputusan sampai
Koordinator diganti, yang dapat mengakibatkan penundaan yang luas untuk peserta di
negara pasti.

17.6

strategi alternatif yang tersedia untuk peserta untuk mendapatkan keputusan
kooperatif bukannya menghubungi koordinator. Strategi ini memiliki keuntungan
bahwa mereka dapat digunakan ketika koordinator telah gagal. Lihat Latihan 17,5 dan Bernstein
et al. [1987] untuk rincian. Namun, bahkan dengan protokol koperasi, jika semua
peserta di negara pasti, mereka tidak akan dapat mendapatkan keputusan sampai
koordinator atau peserta dengan pengetahuan yang diperlukan tersedia.

Hal lain di mana peserta dapat tertunda adalah ketika telah dilakukan semua
permintaan klien dalam transaksi namun belum menerima canCommit sebuah? panggilan dari
koordinator. Sebagai klien mengirimkan Transaksi dekat dengan koordinator, peserta
hanya dapat mendeteksi situasi seperti jika pemberitahuan bahwa itu belum punya permintaan di tertentu
transaksi untuk waktu yang lama - misalnya, pada saat periode timeout pada kunci berakhir.
Karena tidak ada keputusan yang dibuat pada tahap ini, peserta dapat memutuskan untuk membatalkan
secara sepihak.

Koordinator mungkin tertunda ketika sedang menunggu orang dari peserta.
Karena belum memutuskan nasib transaksi mungkin memutuskan untuk membatalkan transaksi
setelah beberapa periode waktu. Kemudian harus mengumumkan doAbort kepada peserta yang memiliki
sudah dikirim suara mereka. Beberapa peserta terlambat mungkin mencoba untuk memilih Ya setelah ini, tapi mereka
orang akan diabaikan dan mereka akan memasuki kondisi tidak menentu seperti dijelaskan di atas.

Kinerja dari dua fase komit protokol • Asalkan semua berjalan dengan baik - yaitu,
bahwa koordinator, para peserta dan komunikasi di antara mereka tidak gagal
- Dua-tahap komit protokol melibatkan N peserta dapat diselesaikan dengan N
canCommit? pesan dan balasan, diikuti oleh pesan N doCommit. Artinya, biaya
dalam pesan sebanding dengan 3N, dan biaya dalam waktu tiga putaran pesan. Itu
Pesan haveCommitted tidak dihitung dalam perkiraan biaya protokol, yang
dapat berfungsi dengan benar tanpa mereka - peran mereka adalah untuk memungkinkan server untuk menghapus basi
informasi koordinator.

Dalam kasus terburuk, mungkin ada sewenang-wenang banyak server dan komunikasi
kegagalan selama dua fase komit protokol. Namun, protokol ini dirancang untuk
mentolerir suksesi kegagalan (crash server atau pesan yang hilang) dan dijamin
menyelesaikan akhirnya, meskipun tidak mungkin untuk menentukan batas waktu di mana itu
akan selesai.

Seperti tercantum dalam bagian sebelumnya, dua-tahap melakukan protokol dapat menyebabkan
penundaan yang cukup untuk peserta di negara pasti. penundaan ini terjadi ketika
Koordinator telah gagal dan tidak dapat menjawab mendapatkan permintaan Keputusan dari peserta. Bahkan
jika protokol koperasi memungkinkan peserta untuk membuat permintaan Keputusan set ke lainnya
peserta, penundaan akan terjadi jika semua peserta aktif tidak pasti.
Tiga fase komit protokol telah dirancang untuk meringankan penundaan tersebut, tetapi
mereka lebih mahal dalam hal jumlah pesan dan jumlah putaran
diperlukan untuk normal kasus (kegagalan-free). Untuk keterangan tiga fase komit
protokol, lihat Latihan 17,2 dan Bernstein et al. [1987].

17.7 Operasi di koordinator untuk transaksi bersarang
openSub Transaksi (trans) o subTrans
Membuka sub transaksi baru yang induknya adalah trans dan mengembalikan unik
subtransaction identifier.
getStatus (trans) o berkomitmen, dibatalkan, sementara
Meminta koordinator untuk melaporkan status transaksi trans. nilai pengembalian
mewakili salah satu dari berikut: terikat, dibatalkan atau sementara.

17.3.2 Dua-fase komit protokol untuk transaksi bersarang
Transaksi terluar dalam satu set transaksi bersarang disebut top-level
transaksi. Transaksi selain transaksi top-level disebut subtransactions.
Pada Gambar 17.1 (b), T adalah transaksi top-level dan T1, T2, T11, T12, T21 dan T22 adalah
sub transaksi. T1 dan T2 adalah transaksi anak T, yang disebut sebagai orang tua mereka.
Demikian pula, T11 dan T12 adalah transaksi anak T1, dan T21 dan T22 adalah transaksi anak
T2. Setiap subtransaction dimulai setelah induknya dan selesai sebelum. Jadi, misalnya,
T11 dan T12 dimulai setelah T1 dan selesai sebelum itu.

Ketika subtransaction sebuah selesai, itu membuat keputusan independen baik untuk
komit sementara atau untuk membatalkan. Sebuah sementara komit berbeda dari yang disiapkan
untuk melakukan: tidak didukung dalam penyimpanan permanen. Jika server crash
kemudian, penggantinya tidak akan mampu melakukan. Setelah semua subtransactions memiliki
selesai, yang sementara dilakukan berpartisipasi dalam dua fase komit
protokol, di mana server dari subtransactions sementara mengakui mengungkapkan mereka
niat untuk melakukan dan mereka dengan nenek moyang dibatalkan akan membatalkan. Sedang dipersiapkan untuk
komit jaminan subtransaction akan mampu melakukan, sedangkan sementara
komit hanya berarti telah selesai dengan benar - dan mungkin akan setuju untuk melakukan saat
itu kemudian diminta untuk.

Seorang koordinator untuk subtransaction akan memberikan operasi untuk membuka
subtransaction, bersama-sama dengan operasi yang memungkinkan bahwa koordinator untuk menanyakan apakah
induknya belum dilakukan atau dibatalkan, seperti yang ditunjukkan pada Gambar 17.7.
Gambar 17.7 Operasi di koordinator untuk transaksi bersarang
openSub Transaksi (trans) o subTrans
Membuka subtransaction baru yang induknya adalah trans dan mengembalikan unik
subtransaction identifier.
getStatus (trans) o berkomitmen, dibatalkan, sementara
Meminta koordinator untuk melaporkan status transaksi trans. nilai pengembalian
mewakili salah satu dari berikut: terikat, dibatalkan atau sementara.
Seorang klien memulai set transaksi bersarang dengan membuka transaksi top-level dengan
operasi openTransaction, yang mengembalikan pengenal transaksi untuk tingkat atas
transaksi. klien mulai subtransaction dengan menyerukan Transaksi openSub
operasi, yang argumen menentukan transaksi induknya. The subtransaction baru
otomatis bergabung transaksi orangtua, dan pengenal transaksi untuk
subtransaction dikembalikan.

Pengidentifikasi untuk subtransaction harus menjadi perpanjangan dari induknya TID,
dibangun sedemikian rupa bahwa identifier dari orang tua atau tingkat atas transaksi dari
subtransaction dapat ditentukan dari pengenal transaksi sendiri. Selain itu, semua
pengidentifikasi subtransaction harus unik secara global. Klien membuat satu set bersarang
transaksi datang sampai selesai dengan menerapkan Transaksi dekat atau membatalkan Transaksi
koordinator transaksi top-level.
Sementara itu, setiap transaksi bersarang melakukan operasinya. Ketika mereka
selesai, server mengelola subtransaction sebuah mencatat informasi mengenai apakah

17.8  subtransaction mengaku sementara atau dibatalkan. Perhatikan bahwa jika induknya dibatalkan, maka
subtransaction akan dipaksa untuk membatalkan juga.

Ingat dari Bab 16 bahwa transaksi orangtua - termasuk transaksi top-level
- Dapat melakukan bahkan jika salah satu subtransactions anaknya telah dibatalkan. Dalam kasus tersebut,
transaksi orangtua akan diprogram untuk mengambil tindakan yang berbeda sesuai dengan apakah
subtransaction telah dilakukan atau dibatalkan. Misalnya, mempertimbangkan transaksi perbankan
yang dirancang untuk melakukan semua 'berdiri perintah' di cabang pada hari tertentu. Ini
transaksi dinyatakan sebagai beberapa subtransactions transfer bersarang, yang masing-masing
terdiri dari deposito bersarang dan menarik subtransactions. Kami berasumsi bahwa ketika
account tekor, menarik dibatalkan dan kemudian sesuai transfer dibatalkan. Tapi
tidak perlu untuk membatalkan semua perintah berdiri hanya karena satu transfer subtransaction
dibatalkan. Alih-alih batal, transaksi top-level akan dicatat Transfer
subtransactions yang dibatalkan dan mengambil tindakan yang tepat.

Pertimbangkan transaksi top-level T dan subtransactions yang ditunjukkan pada Gambar 17.8Gambar 17.8 Transaksi T memutuskan apakah akan melakukan batalkan (at M)sementara komit(at N)sementara komit (di X)dibatalkan (di Y)sementara komit (at N)sementara komit (pada P)T TT
.
yang didasarkan pada Gambar 17.1 (b). Setiap subtransaction memiliki baik sementara
dilakukan atau dibatalkan. Misalnya, T12 telah sementara berkomitmen dan T11 memiliki
dibatalkan, namun nasib T12 tergantung pada T1 induknya dan akhirnya pada tingkat atas
transaksi, T. Meskipun T21 dan T22 memiliki keduanya sementara berkomitmen, T2 telah dibatalkan
dan ini berarti bahwa T21 dan T22 juga harus membatalkan. Misalkan T memutuskan untuk komit dalam
Terlepas dari kenyataan bahwa T2 telah dibatalkan, dan bahwa T1 memutuskan untuk melakukan terlepas dari kenyataan bahwa
T11 telah dibatalkan.



Ketika transaksi top-level selesai, koordinatornya melakukan dua fase
commit protocol. Satu-satunya alasan untuk subtransaction peserta tidak mampu
lengkap jika telah jatuh karena menyelesaikan nya sementara komit. Ingat bahwa ketika
setiap subtransaction diciptakan, itu bergabung transaksi induknya. Oleh karena itu,
koordinator setiap transaksi orangtua memiliki daftar subtransactions anaknya. Ketika sebuah
transaksi bersarang sementara melakukan, itu laporan status dan status nya
keturunan ke induknya. Ketika transaksi bersarang dibatalkan, hanya melaporkan membatalkan untuk nya
orang tua tanpa memberikan informasi apapun tentang keturunannya. Akhirnya, tingkat atas
transaksi menerima daftar semua sub transaksi di pohon, bersama-sama dengan status
setiap. Keturunan subtransactions dibatalkan dihilangkan dari daftar ini.

17.9 Informasi Yang dimiliki oleh koordinator transaksi bersarang



Informasi yang diselenggarakan oleh masing-masing koordinator dalam contoh pada Gambar 17.8 diperlihatkan

* Orang tua T21 telah dibatalkan
. Perhatikan bahwa T12 dan T21 berbagi koordinator karena keduanya berjalan pada server yang N.
Ketika subtransaction T2 dibatalkan, melaporkan fakta ke induknya, T, tapi tanpa melewati
informasi apapun tentang T21 subtransactions dan T22. Sebuah subtransaction adalah seorang yatim piatu
jika salah satu dari nenek moyangnya dibatalkan, baik secara eksplisit maupun karena crash koordinatornya. dalam kami
Misalnya, subtransactions T21 dan T22 adalah anak yatim karena orang tua mereka dibatalkan tanpa
menyampaikan informasi tentang mereka untuk transaksi top-level. Koordinator mereka bisa,
Namun, membuat pertanyaan tentang status orang tua mereka dengan menggunakan getStatus
operasi. Sebuah subtransaction sementara berkomitmen dari transaksi dibatalkan harus
dibatalkan, terlepas dari apakah transaksi top-level akhirnya melakukan.

Transaksi top-level memainkan peran koordinator dalam dua fase komit
protokol, dan daftar peserta terdiri dari koordinator dari semua subtransactions di
pohon yang telah sementara berkomitmen tetapi tidak memiliki nenek moyang dibatalkan. Dengan ini
panggung, logika program telah menetapkan bahwa transaksi tingkat atas harus mencoba
untuk melakukan apa pun yang tersisa, meskipun beberapa subtransactions dibatalkan. Pada Gambar 17.8, yang
koordinator T, T1 dan T12 adalah peserta dan akan diminta untuk memilih pada hasil.
Jika mereka memilih untuk melakukan, maka mereka harus mempersiapkan transaksi mereka dengan menyimpan negara
benda-benda di penyimpanan permanen. negara ini dicatat sebagai milik tingkat atas
transaksi yang akan membentuk bagian. Dua-tahap melakukan protokol mungkin
dilakukan baik secara hierarkis atau secara mendatar.
Tahap kedua dari dua fase komit protokol adalah sama seperti untuk kasus non bersarang. koordinator mengumpulkan orang dan kemudian menginformasikan peserta untuk
hasil. Ketika selesai, koordinator dan peserta akan telah melakukan atau
dibatalkan transaksinya.
Hierarkis dua fase komit protokol • Dalam pendekatan ini, dua fase komit
protokol menjadi protokol bersarang multi-level. Koordinator tingkat atas
transaksi berkomunikasi dengan koordinator dari subtransactions yang merupakan
induk langsung. Ini mengirimkan canCommit? pesan satu sama yang terakhir, yang pada gilirannya
meneruskannya ke koordinator transaksi anak mereka (dan seterusnya ke bawah pohon).
Setiap peserta mengumpulkan balasan dari keturunan sebelum membalas induknya.
Dalam contoh kita, T mengirimkan canCommit? pesan ke koordinator T1 dan kemudian T1
mengirimkan canCommit? pesan ke T12 bertanya tentang keturunan T1. protokol tidak
tidak termasuk koordinator transaksi seperti T2, yang telah dibatalkan. Gambar 17.10

Gambar 17.10 canCommit? untuk hirarkis dua fase komit protokol
canCommit? (trans, subTrans) o Ya / Tidak
Panggilan dari koordinator ke koordinator subtransaction anak untuk bertanya apakah itu bisa
melakukan suatu subtransaction subTrans. Argumen pertama, trans, adalah transaksi
identifier transaksi top-level. Peserta menjawab dengan suaranya, Ya / Tidak

menunjukkan argumen diperlukan untuk canCommit ?. Argumen pertama adalah TID transaksi toplevel, untuk digunakan saat mempersiapkan data. Argumen kedua adalah TID dari
peserta membuat canCommit? panggilan. Peserta menerima panggilan tampak dalam
daftar transaksi untuk setiap transaksi sementara yang dilakukan atau subtransaction
cocok dengan TID di argumen kedua. Misalnya, koordinator T12 juga
koordinator T21, karena mereka berjalan di server yang sama, tetapi ketika menerima
canCommit? sebut, argumen kedua akan T1 dan akan hanya berurusan dengan T12.
Jika peserta menemukan apapun subtransactions yang cocok dengan argumen kedua,
mempersiapkan objek dan menjawab dengan Ya suara. Jika gagal untuk menemukan apapun, maka ia harus memiliki
jatuh karena dilakukan subtransaction dan itu menjawab dengan suara ada.
Datar dua fase komit protokol • Dalam pendekatan ini, koordinator tingkat atas
transaksi mengirimkan canCommit? pesan untuk para koordinator semua subtransactions
dalam sementara melakukan daftar - dalam contoh kita, untuk koordinator T1 dan T12. Selama
komit protokol, para peserta mengacu pada transaksi dengan yang TID tingkat atas. Setiap
Peserta terlihat dalam daftar transaksi untuk setiap transaksi atau subtransaction pencocokan
yang TID. Misalnya, koordinator T12 juga koordinator T21, karena mereka
berjalan di server yang sama (N).

Sayangnya, hal ini tidak memberikan informasi yang cukup untuk memungkinkan benar
tindakan oleh peserta seperti koordinator di Server N yang memiliki campuran
sementara berkomitmen dan dibatalkan subtransactions. Jika koordinator N ini hanya diminta untuk
komit T itu akan berakhir dengan melakukan kedua T12 dan T21, karena menurut nya lokal
informasi, keduanya telah sementara berkomitmen. Ini salah dalam kasus T21,
karena induknya, T2, telah dibatalkan. Untuk memungkinkan untuk kasus-kasus seperti itu, canCommit? operasi
untuk protokol datar komit memiliki argumen kedua yang menyediakan daftar dibatalkan
subtransactions, seperti yang ditunjukkan pada Gambar 17.11.
Gambar 17.11 canCommit? untuk flat dua fase komit protokol
canCommit? (trans, abortList) o Ya / Tidak
Panggilan dari koordinator kepada peserta untuk bertanya apakah bisa melakukan transaksi.
Peserta menjawab dengan suaranya, Ya / Tidak
Peserta dapat melakukan keturunan
transaksi tingkat atas kecuali mereka telah dibatalkan leluhur. Ketika peserta menerima
canCommit? permintaan, ia melakukan berikut:
• Jika peserta memiliki transaksi sementara berkomitmen yang
keturunan transaksi top-level, trans, itu:
- Cek bahwa mereka tidak telah dibatalkan leluhur di abortList, kemudian menyiapkan
untuk melakukan (dengan mencatat transaksi dan benda-benda di penyimpanan permanen);

Gambar 17.11 canCommit? untuk flat dua fase komit protokol
canCommit? (trans, abortList) o Ya / Tidak
Panggilan dari koordinator kepada peserta untuk bertanya apakah bisa melakukan transaksi.
Peserta menjawab dengan suaranya, Ya / Tidak



- Dibatalkan mereka dengan nenek moyang dibatalkan;
- Mengirimkan Ya suara untuk koordinator.
• Jika peserta tidak memiliki keturunan sementara mengakui transaksi toplevel, pasti gagal karena dilakukan subtransaction dan itu
mengirimkan Tidak ada suara untuk koordinator.

Perbandingan dari dua pendekatan • The hirarkis protokol memiliki keunggulan yang di
setiap tahap, peserta hanya perlu mencari subtransactions induk langsung,
sedangkan protokol datar perlu memiliki daftar batalkan untuk menghilangkan transaksi
orang tua yang telah dibatalkan. Moss [1985] disukai algoritma datar karena memungkinkan
koordinator transaksi top-level untuk berkomunikasi langsung dengan semua
peserta, sedangkan varian hirarkis melibatkan melewati serangkaian pesan bawah
dan sampai pohon secara bertahap.

Tindakan Timeout • Dua-tahap melakukan protokol untuk transaksi bersarang dapat menyebabkan
koordinator atau peserta ditunda pada tiga langkah yang sama seperti pada non-bersarang
versi. Ada langkah keempat di mana subtransactions dapat ditunda. Mempertimbangkan
sementara mengakui subtransactions anak subtransactions dibatalkan: mereka tidak
tentu mendapatkan informasi dari hasil transaksi. Dalam contoh kita, T22 adalah seperti
a subtransaction - telah sementara berkomitmen, tetapi sebagai induknya T2 telah dibatalkan, itu tidak
tidak menjadi peserta. Untuk menghadapi situasi seperti itu, setiap subtransaction yang belum
menerima dapat Komit? pesan akan membuat penyelidikan setelah periode timeout. Itu
getStatus operasi pada Gambar 17.7 memungkinkan subtransaction untuk menanyakan apakah induknya
telah dilakukan atau dibatalkan. Untuk membuat pertanyaan seperti itu mungkin, para koordinator dibatalkan
subtransactions perlu untuk bertahan hidup untuk jangka waktu. Jika subtransaction yatim tidak bisa
hubungi induknya, pada akhirnya akan membatalkan.

     17.4 kontrol Concurrency dalam transaksi terdistribusi

Setiap server mengelola satu set objek dan bertanggung jawab untuk memastikan bahwa mereka tetap
konsisten ketika diakses oleh transaksi konkuren. Oleh karena itu, setiap server adalah
bertanggung jawab untuk menerapkan kontrol konkurensi ke obyek sendiri. Para anggota dari
koleksi server transaksi terdistribusi secara bersama-sama bertanggung jawab untuk memastikan bahwa
mereka dilakukan dengan cara serial setara.
Ini berarti bahwa jika transaksi T adalah sebelum transaksi U di akses mereka saling
ke objek pada salah satu server, maka mereka harus dalam rangka bahwa pada semua server yang
benda diakses dengan cara yang bertentangan dengan kedua T dan U.

     17.4.1 Mengunci
Dalam transaksi terdistribusi, kunci pada sebuah objek yang diselenggarakan secara lokal (di server yang sama).
Lock manager lokal dapat memutuskan apakah akan memberikan kunci atau membuat yang meminta
transaksi menunggu. Namun, tidak dapat melepaskan kunci sampai tahu bahwa transaksi
telah dilakukan atau dibatalkan sama sekali server yang terlibat dalam transaksi. Kapan
penguncian digunakan untuk kontrol concurrency, objek tetap terkunci dan tidak tersedia

BAGIAN PENGENDALIAN 17,4 CONCURRENCY DI TERDISTRIBUSI TRANSAKSI 741

untuk transaksi lain selama atom komit protokol, walaupun dibatalkan
transaksi rilis kunci setelah fase 1 dari protokol.
Sebagai manajer kunci di server yang berbeda set kunci mereka secara independen satu sama lain,
adalah mungkin bahwa server yang berbeda dapat mengenakan orderings berbeda pada transaksi.
Pertimbangkan interleaving berikut transaksi T dan U di server X danY



Kunci transaksi T keberatan A di X server, dan kemudian transaksi U kunci keberatan B di
Server Y. Setelah itu, T mencoba untuk mengakses B di Server Y dan menunggu Kami kunci. Demikian pula,
Transaksi U mencoba untuk mengakses A di X server dan harus menunggu kunci T. Oleh karena itu, kami
memiliki T sebelum U di satu server dan U sebelum T yang lain. Ini orderings yang berbeda dapat
menyebabkan ketergantungan siklik antara transaksi, sehingga menimbulkan kebuntuan didistribusikan
situasi. Deteksi dan resolusi kebuntuan didistribusikan dibahas dalam Bagian
17.5. Ketika kebuntuan terdeteksi, transaksi digagalkan untuk menyelesaikan kebuntuan. Di
hal ini, koordinator akan diinformasikan dan akan membatalkan transaksi di
peserta yang terlibat dalam transaksi.

17.4.2 Timestamp memesan kontrol konkurensi
Dalam transaksi server tunggal, koordinator mengeluarkan timestamp unik untuk setiap
transaksi ketika mulai. Serial kesetaraan diberlakukan dengan melakukan versi
benda di urutan cap waktu transaksi yang diakses mereka. dalam didistribusikan
transaksi, kami mewajibkan setiap masalah koordinator cap waktu global yang unik. SEBUAH
global timestamp transaksi unik dikeluarkan untuk klien oleh koordinator pertama
diakses oleh transaksi. Timestamp transaksi akan diteruskan ke koordinator di setiap
Server yang objek melakukan operasi dalam transaksi.
Server transaksi terdistribusi secara bersama-sama bertanggung jawab untuk memastikan bahwa
mereka dilakukan dengan cara serial setara. Sebagai contoh, jika versi dari
objek diakses oleh transaksi U melakukan setelah versi diakses oleh T di satu server,
jika T dan U mengakses objek yang sama dengan satu sama lain di server lain mereka harus komit mereka
dalam urutan yang sama. Untuk mencapai urutan yang sama di semua server, koordinator harus
setuju untuk pemesanan cap waktu mereka. Sebuah timestamp terdiri dari <lokal
timestamp, server-id> pasangan. pemesanan yang disepakati pasang cap waktu didasarkan pada
perbandingan di mana bagian server-id kurang signifikan.
Urutan yang sama transaksi dapat dicapai pada semua server bahkan jika mereka
jam lokal tidak disinkronkan. Namun, untuk alasan efisiensi diperlukan bahwa
cap waktu yang dikeluarkan oleh salah satu koordinator secara kasar disinkronkan dengan orang-orang yang dikeluarkan oleh
koordinator lainnya. Ketika hal ini terjadi, urutan transaksi umumnya





sesuai dengan urutan di mana mereka mulai secara real time. Cap waktu dapat disimpan
kira-kira disinkronkan dengan menggunakan jam fisik lokal disinkronisasi (lihat Bab 14).
Ketika timestamp ordering digunakan untuk kontrol concurrency, konflik diselesaikan
karena setiap operasi dilakukan dengan menggunakan aturan yang diberikan dalam Bagian 16.6. Jika resolusi
konflik membutuhkan transaksi akan dibatalkan, koordinator akan diinformasikan dan
akan membatalkan transaksi pada semua peserta. Oleh karena itu setiap transaksi yang mencapai
permintaan klien untuk melakukan harus selalu mampu melakukan, dan peserta dalam
dua fase komit protokol biasanya akan setuju untuk melakukan. Satu-satunya situasi di mana
peserta tidak akan setuju untuk melakukan ini jika telah jatuh selama transaksi.

    17.4.3 kontrol konkurensi Optimis
Ingat bahwa dengan kontrol konkurensi optimis, setiap transaksi divalidasi sebelum itu
diizinkan untuk melakukan. nomor transaksi ditugaskan pada awal validasi dan
transaksi serial sesuai dengan urutan nomor transaksi. SEBUAH
transaksi terdistribusi divalidasi oleh koleksi server independen, yang masing-masing
memvalidasi transaksi yang mengakses obyek sendiri. Validasi ini berlangsung selama
Tahap pertama dari dua fase komit protokol.
Pertimbangkan interleavings berikut transaksi T dan U, yang mengakses obyek
A dan B di server X dan Y, masing-masing





Transaksi mengakses objek dalam urutan T sebelum U di X Server dan dalam urutan
U sebelum T di Server Y. Sekarang anggaplah bahwa T dan U mulai validasi pada waktu yang sama,
tetapi server X memvalidasi T pertama dan server Y memvalidasi U pertama. Ingat Bagian yang 16,5
merekomendasikan penyederhanaan protokol validasi yang membuat aturan bahwa hanya satu
transaksi dapat melakukan validasi dan pemutakhiran fase pada suatu waktu. Oleh karena itu setiap server
akan dapat memvalidasi transaksi lain sampai yang pertama telah selesai. Ini adalah
contoh komitmen kebuntuan.
Aturan validasi dalam Bagian 16.5 menganggap bahwa validasi cepat, yang benar
untuk transaksi tunggal-server. Namun, dalam transaksi terdistribusi, dua-fase
commit protocol mungkin memerlukan beberapa waktu untuk menyelesaikan, dan transaksi lainnya akan
dicegah dari memasuki validasi sampai keputusan atas transaksi saat ini telah
diperoleh. Dalam transaksi optimis didistribusikan, setiap server menerapkan validasi paralel
protokol. Ini adalah perpanjangan dari salah validasi mundur atau maju untuk memungkinkan beberapa
transaksi berada di fase validasi pada saat yang sama. Dalam ekstensi ini, aturan 3 keharusan
diperiksa serta aturan 2 untuk validasi mundur. Artinya, menulis set
transaksi divalidasi harus diperiksa untuk tumpang tindih dengan menulis set sebelumnya
transaksi yang tumpang tindih. Kung dan Robinson [1981] menjelaskan validasi paralel.

Jika validasi paralel digunakan, transaksi tidak akan menderita dari komitmen
jalan buntu. Namun, jika server hanya melakukan validasi independen, adalah mungkin bahwa
server yang berbeda dalam transaksi terdistribusi mungkin cerita set yang sama transaksi di
perintah yang berbeda - misalnya, dengan T sebelum U di Server X dan U sebelum T di Server Y,
dalam contoh kita.
Server transaksi terdistribusi harus mencegah hal ini terjadi. salah satu pendekatan
adalah bahwa setelah validasi lokal dengan masing-masing server, validasi global yang dilakukan [Ceri dan
Owicki 1982]. Validasi global yang memeriksa bahwa kombinasi dari orderings di
server individu serializable; yaitu, bahwa transaksi divalidasi tidak
terlibat dalam siklus.

Pendekatan lain adalah bahwa semua server dari transaksi tertentu menggunakan yang sama
jumlah transaksi global yang unik pada awal validasi [Schlageter 1982]. Itu
koordinator dua fase komit protokol bertanggung jawab untuk menghasilkan secara global
jumlah transaksi yang unik dan dibagikan kepada para peserta di dapat Komit? pesan.
Sebagai server yang berbeda dapat berkoordinasi transaksi yang berbeda, server harus (seperti pada
didistribusikan timestamp protokol pemesanan) memiliki perintah yang disepakati untuk transaksi
nomor yang mereka hasilkan.
Agrawal et al. [1987] telah mengusulkan variasi Kung dan Robinson
algoritma yang nikmat read-only transaksi, bersama-sama dengan sebuah algoritma yang disebut MVGV
(Multi-versi umum validasi). MVGV adalah bentuk validasi paralel yang
memastikan bahwa nomor transaksi mencerminkan urutan serial, tetapi membutuhkan bahwa dalam beberapa kasus,
transaksi lainnya tidak dapat membaca efek mereka segera setelah mereka memiliki
berkomitmen. Hal ini juga memungkinkan jumlah transaksi harus diubah sehingga memungkinkan beberapa
transaksi untuk memvalidasi yang lain akan gagal. Makalah ini juga mengusulkan
algoritma untuk melakukan transaksi terdistribusi. Hal ini mirip dengan usulan Schlageter ini
dalam sejumlah transaksi global harus ditemukan. Pada akhir fase baca,
Koordinator mengusulkan nilai untuk jumlah transaksi global dan setiap peserta
mencoba untuk memvalidasi transaksi lokal menggunakan nomor itu. Namun, jika yang diusulkan
jumlah transaksi global terlalu kecil, beberapa peserta mungkin tidak dapat memvalidasi
transaksi mereka, dan mereka akan harus bernegosiasi dengan koordinator untuk peningkatan
jumlah. Jika tidak ada nomor yang sesuai dapat ditemukan, maka para peserta harus membatalkan
transaksi mereka. Akhirnya, jika semua peserta dapat memvalidasi transaksi mereka,
Koordinator akan menerima proposal untuk nomor transaksi dari masing-masing. Jika
nomor umum dapat ditemukan maka transaksi akan dilakukan.





17.5 kebuntuan Terdistribusi

 Pembahasan kebuntuan dalam Bagian 16.4 menunjukkan bahwa deadlock dapat timbul dalam
server tunggal saat penguncian digunakan untuk kontrol concurrency. Server harus baik mencegah
atau mendeteksi dan mengatasi kebuntuan. Menggunakan timeout untuk mengatasi kemungkinan kebuntuan adalah
Pendekatan kikuk - sulit untuk memilih interval timeout yang tepat, dan
transaksi dapat dibatalkan tidak perlu. Dengan skema deteksi kebuntuan, sebuah
transaksi dibatalkan hanya ketika terlibat dalam kebuntuan. Kebanyakan deteksi deadlock
skema beroperasi dengan menemukan siklus dalam transaksi grafik menunggu-untuk. Dalam didistribusikan
sistem yang melibatkan beberapa server yang diakses oleh beberapa transaksi, global

 gambar17.12



menunggu-untuk grafik dapat secara teori dibangun dari yang lokal. Bisa ada siklus di
menunggu-untuk dunia grafik yang tidak dalam satu lokal satu - yaitu, bisa ada
didistribusikan kebuntuan. Ingat bahwa grafik menunggu untuk ini diarahkan grafik di mana node
merupakan transaksi dan benda-benda, dan tepi mewakili baik objek yang diselenggarakan oleh
transaksi atau transaksi menunggu sebuah objek. Ada kebuntuan jika dan hanya jika ada
adalah siklus dalam grafik menunggu-untuk.

Gambar 17.12 menunjukkan interleavings transaksi U, V dan W melibatkan
benda A dan B yang dikelola oleh server X dan Y dan benda C dan D dikelola oleh server Z.
Gambar 17.12 interleavings transaksi U, V dan W
U V W
d.deposit (10) kunci D
b.deposit (10) kunci B
a.deposit (20) kunci A di Y
di X
c.deposit (30) kunci C
b.withdraw (30) menunggu di Y di Z
c.withdraw (20) menunggu di Z
a.withdraw (20) menunggu di X
Lengkap menunggu untuk grafik pada Gambar 17,13 (a) menunjukkan bahwa siklus deadlock
terdiri dari tepi alternatif, yang merupakan transaksi menunggu untuk sebuah objek dan
objek dipegang oleh transaksi. Seperti transaksi hanya dapat menunggu satu objek pada
waktu, benda dapat ditinggalkan dari grafik menunggu-untuk, seperti yang ditunjukkan pada Gambar 17,13 (b).
Deteksi kebuntuan didistribusikan membutuhkan siklus dapat ditemukan di global
transaksi menunggu-untuk grafik yang didistribusikan di antara server yang terlibat dalam
transaksi. grafik menunggu-untuk lokal dapat dibangun oleh manajer kunci di setiap server, seperti
dibahas dalam Bab 16. Dalam contoh di atas, lokal menunggu-untuk grafik dari server
adalah:
Server Y: U o V (ditambahkan ketika U meminta b.withdraw (30))
Server Z: V o W (ditambahkan ketika permintaan V c.withdraw (20))
Server X: W o U (ditambahkan ketika permintaan W a.withdraw (20))
Sebagai grafik menunggu-untuk global yang diadakan di sebagian oleh masing-masing dari beberapa server yang terlibat,
komunikasi antara server ini diperlukan untuk menemukan siklus dalam grafik.
Sebuah solusi sederhana adalah dengan menggunakan deteksi kebuntuan terpusat, di mana satu server
mengambil peran detektor kebuntuan global. Dari waktu ke waktu, setiap server mengirimkan
copy terbaru dari grafik menunggu-untuk lokal untuk detektor kebuntuan global, yang
amalgamates informasi dalam grafik lokal untuk membangun menunggu-untuk global yang
grafik. Global cek kebuntuan detektor untuk siklus dalam grafik menunggu-untuk global yang

Gamabar 17.13





Ketika ia menemukan sebuah siklus, itu membuat keputusan tentang cara mengatasi kebuntuan dan memberitahu
server yang transaksi untuk membatalkan.
Deteksi deadlock terpusat bukan ide yang baik, karena bergantung pada satu
server untuk melaksanakannya. Menderita dari masalah yang biasa berhubungan dengan terpusat
solusi dalam sistem terdistribusi - ketersediaan buruk, kurangnya toleransi kesalahan dan tidak memiliki kemampuan
untuk mengukur. Selain itu, biaya transmisi sering lokal grafik menunggu-adalah
tinggi. Jika grafik global yang dikumpulkan lebih jarang, kebuntuan bisa lebih lama menjadi
terdeteksi.

kebuntuan phantom • Sebuah gembok yang 'terdeteksi' tapi tidak benar-benar deadlock disebut
hantu kebuntuan. Dalam deteksi kebuntuan didistribusikan, informasi tentang menunggu-untuk
hubungan antara transaksi ditularkan dari satu server ke yang lain. Jika ada
kebuntuan, informasi yang diperlukan pada akhirnya akan dikumpulkan di satu tempat dan
siklus akan terdeteksi. Sebagai prosedur ini akan memakan waktu, ada kemungkinan bahwa salah satu
dari transaksi yang memegang kunci akan sementara telah dirilis, dalam hal ini
kebuntuan akan ada lagi.
Pertimbangkan kasus detektor kebuntuan global yang menerima lokal menunggu untuk grafik
dari server X dan Y, seperti yang ditunjukkan pada Gambar 17.14. Misalkan transaksi yang U kemudian melepaskan
objek pada X server dan meminta satu dipegang oleh V di server yang Y. Misalkan juga bahwa
detektor global yang menerima grafik lokal Server Y sebelum server X. Dalam hal ini, itu akan
mendeteksi siklus T o U o V o T, meskipun tepi T o U tidak ada lagi. Ini adalah sebuah
contoh hantu kebuntuan.
Pembaca yang jeli akan menyadari bahwa jika transaksi menggunakan dua fase
kunci, mereka tidak bisa melepaskan benda dan kemudian memperoleh lebih banyak benda, dan phantom kebuntuan



gambar 17.14



siklus tidak dapat terjadi dengan cara yang disarankan di atas. Mempertimbangkan situasi di mana siklus
T o U o V o T terdeteksi: baik ini merupakan kebuntuan atau setiap transaksi
T,
U dan V akhirnya harus berkomitmen. Hal ini sebenarnya tidak mungkin untuk salah satu dari mereka untuk melakukan,
karena masing-masing dari mereka sedang menunggu untuk sebuah objek yang tidak akan pernah dirilis.

Tepi mengejar • Pendekatan didistribusikan ke kebuntuan deteksi menggunakan teknik yang disebut
tepi mengejar atau jalan mendorong. Dalam pendekatan ini, grafik menunggu-untuk global tidak
dibangun, tetapi masing-masing dari server yang terlibat memiliki pengetahuan tentang beberapa ujungnya.
Server mencoba untuk menemukan siklus dengan meneruskan pesan yang disebut probe, yang mengikuti
tepi grafik seluruh sistem terdistribusi. Sebuah pesan Probe terdiri dari
transaksi menunggu-untuk hubungan mewakili jalan dalam grafik menunggu-untuk global.
Pertanyaannya adalah, ketika server harus mengirimkan probe? Mempertimbangkan situasi di
Server X pada Gambar 17,13. Server ini baru saja menambahkan tepi W o U untuk lokal menunggu-untuk
grafik, dan pada transaksi saat ini U menunggu untuk mengakses objek B, dimana transaksi V
memegang di Server Y. tepi ini mungkin bisa menjadi bagian dari siklus seperti
V o? T1? O? T2 o ... o W o U o V melibatkan transaksi menggunakan benda-benda di lain
server. Hal ini menunjukkan bahwa ada siklus didistribusikan kebuntuan potensial, yang bisa
ditemukan dengan mengirimkan probe ke server Y.

Sekarang mempertimbangkan situasi sedikit lebih awal, ketika server Z menambahkan tepi V o W
untuk grafik lokal. Pada titik ini dalam waktu W tidak menunggu, sehingga tidak ada gunanya mengirim
out probe.
Setiap transaksi terdistribusi dimulai pada server (disebut koordinator
transaksi) dan bergerak ke beberapa server lain (disebut peserta dalam transaksi),
yang dapat berkomunikasi dengan koordinator. Pada setiap titik waktu, transaksi dapat
baik yang aktif atau menunggu di salah satu server ini. Koordinator bertanggung jawab untuk
merekam apakah transaksi tersebut aktif atau sedang menunggu untuk objek tertentu, dan
peserta bisa mendapatkan informasi ini dari koordinator mereka. manajer kunci menginformasikan
koordinator ketika transaksi mulai menunggu benda dan ketika transaksi mengakuisisi
benda dan menjadi aktif kembali. Ketika suatu transaksi dibatalkan untuk memecahkan kebuntuan, yang
Koordinator akan menginformasikan peserta dan semua kunci yang akan dihapus, dengan
Efek yang semua tepi yang melibatkan transaksi yang akan dihapus dari lokal menunggu-untuk
grafik.

Gambar 17.16

algoritma tepi-mengejar memiliki tiga langkah:
Inisiasi: Ketika server mencatat bahwa transaksi T mulai menunggu lain
Transaksi U, di mana U sedang menunggu untuk mengakses objek di server lain, ia memulai
deteksi dengan mengirimkan probe yang berisi tepi <T o U> ke server dari
objek di mana transaksi U diblokir. Jika U adalah berbagi kunci, probe dikirim ke semua
pemegang kunci. Kadang-kadang transaksi lebih lanjut dapat mulai berbagi kunci
nanti, di mana probe kasus dapat dikirim kepada mereka juga.
Deteksi: Deteksi terdiri dari menerima probe dan memutuskan apakah deadlock
telah terjadi dan apakah akan meneruskan probe.
Misalnya, ketika server dari obyek menerima probe <T o U>
(Menunjukkan bahwa T sedang menunggu transaksi U yang memegang objek lokal), ia akan mengecek ke
melihat apakah U juga menunggu. Jika ya, transaksi itu menunggu (misalnya, V) adalah
ditambahkan ke probe (menjadikannya <T o? U? o V!? dan jika transaksi baru (V) adalah
menunggu untuk objek lain di tempat lain, probe diteruskan.
Dengan cara ini, jalur melalui grafik menunggu-untuk global dibangun satu sisi pada suatu waktu.
Sebelum meneruskan probe, cek server untuk melihat apakah transaksi (untuk
Misalnya, T) itu baru saja menambahkan telah menyebabkan probe mengandung siklus (misalnya,
<T ke U ke  o V ke o T>). Jika hal ini terjadi, ia telah menemukan siklus dalam grafik dan
kebuntuan telah terdeteksi.
Figure 17.15 Probe ditransmisikan untuk mendeteksi deadlock
V
Diselenggarakan oleh
W
Yang diselenggarakan oleh Menunggu
Waits
untuk
menunggu
Jalan buntu
terdeteksi
U
C
SEBUAH
Inisiasi
Wo U o V o W
wo U
W o U o V
Z
Y
X
B
Resolusi: Ketika siklus terdeteksi, transaksi dalam siklus dibatalkan untuk istirahat
kebuntuan.



Dalam contoh kita, langkah-langkah berikut menggambarkan bagaimana kebuntuan deteksi dimulai dan
probe yang diteruskan selama fase deteksi yang sesuai:

Server X memulai deteksi dengan mengirimkan penyelidikan <W o U> ke server dari B (Server
Y).
• Server Y menerima menyelidiki <W o U>, mencatat bahwa B dipegang oleh V dan menambahkan V untuk
probe untuk menghasilkan <W o U o V>. Ini mencatat bahwa V menunggu C di Server Z.
Probe ini diteruskan ke server Z.
• Server Z menerima menyelidiki <W o U o? V>, mencatat C dipegang oleh W dan menambahkan WWW untuk
probe untuk menghasilkan <W o U o V o W>.
Jalan ini mengandung siklus. Server terdeteksi kebuntuan. Salah satu transaksi di
siklus harus dibatalkan untuk memecahkan kebuntuan. transaksi yang akan dibatalkan dapat dipilih
sesuai dengan prioritas transaksi, yang dijelaskan lama.

Gambar 17.15 menunjukkan kemajuan pesan penyelidikan dari inisiasi oleh
server A untuk deteksi kebuntuan oleh server C. Probe ditampilkan sebagai berat
panah, benda-benda seperti oval (seperti biasa) dan koordinator transaksi sebagai persegi panjang. Setiap
probe ditampilkan sebagai akan langsung dari satu objek yang lain. Pada kenyataannya, sebelum server
mentransmisikan probe ke server lain, itu berkonsultasi koordinator transaksi terakhir di
jalan untuk mengetahui apakah yang terakhir ini menunggu untuk objek lain di tempat lain. Untuk
Misalnya, sebelum server B mengirimkan probe <W o U o V> itu berkonsultasi
koordinator V untuk mengetahui bahwa V menunggu C. Di sebagian tepi-mengejar
algoritma, server objek mengirim probe untuk koordinator transaksi, yang kemudian
meneruskannya (jika transaksi tersebut menunggu) ke server objek dimana
transaksi menunggu. Dalam contoh kita, server dari B mengirimkan probe
<W o U o V> koordinator V, yang kemudian meneruskannya ke server C. Ini
menunjukkan bahwa ketika probe diteruskan, dua pesan yang diperlukan.

Algoritma di atas harus menemukan kebuntuan yang terjadi, asalkan menunggu
transaksi tidak menggugurkan dan tidak ada kegagalan seperti pesan hilang atau server
menerjang. Untuk memahami hal ini, mempertimbangkan siklus kebuntuan di mana transaksi terakhir, W,
mulai menunggu dan melengkapi siklus. Ketika W mulai menunggu untuk sebuah objek, server
memulai penyelidikan yang masuk ke server objek yang dimiliki oleh setiap transaksi yang
W menunggu. Para penerima memperluas dan meneruskan probe ke server objek
diminta oleh semua transaksi menunggu mereka menemukan. Dengan demikian setiap transaksi yang W menunggu,
langsung atau tidak langsung, akan ditambahkan ke probe kecuali kebuntuan terdeteksi. Kapan
ada kebuntuan, W menunggu untuk dirinya sendiri secara tidak langsung. Oleh karena itu, probe akan kembali ke
objek yang W memegang.

objek yang W memegang.
Ini mungkin tampak bahwa sejumlah besar pesan yang dikirim untuk mendeteksi
kebuntuan. Dalam contoh di atas, kita melihat dua pesan probe untuk mendeteksi siklus yang melibatkan
tiga transaksi. Setiap pesan probe secara umum dua pesan (dari objek
Koordinator dan kemudian dari koordinator ke objek).

Penyelidikan yang mendeteksi siklus yang melibatkan transaksi N akan diteruskan oleh (N - 1)
koordinator transaksi via (N - 1) server objek, membutuhkan 2 (N - 1) pesan.
Untungnya, sebagian besar kebuntuan melibatkan siklus yang hanya berisi dua transaksi,
dan tidak ada kebutuhan untuk khawatir tentang jumlah pesan yang terlibat. Ini
Pengamatan telah dibuat dari studi database. Hal ini juga bisa dikatakan oleh
mempertimbangkan kemungkinan bertentangan akses ke objek (lihat Bernstein et al. [1987]).

Gambar 17.16



prioritas transaksi • Pada algoritma di atas, setiap transaksi yang terlibat dalam kebuntuan
siklus dapat menyebabkan deteksi kebuntuan untuk diinisiasi. Pengaruh beberapa transaksi dalam
siklus memulai deteksi kebuntuan adalah bahwa deteksi mungkin terjadi di beberapa berbeda
server dalam siklus, dengan hasil yang lebih dari satu transaksi dalam siklus tersebut dibatalkan.
Pada Gambar 17.16 (a)
Gambar 17.16 Dua probe dimulai
(A) situasi awal (b) deteksi dimulai pada obyek
diminta oleh T
(C) deteksi dimulai pada obyek
diminta oleh W
U
T
V
W
menunggu
Waits
untuk
V
W
U
T
T o U o W o V
T o U o W
T o U
menunggu
U
V
T
W
W o V o T
W o V o T o U
W o V
Waits
untuk
, Pertimbangkan transaksi T, U, V dan W, di mana U menunggu W
dan V menunggu T. Pada waktu yang sama, T meminta objek dipegang oleh U dan W
meminta objek dipegang oleh V. Dua probe terpisah, <T o U> dan <W o V>, yang
diprakarsai oleh server dari benda-benda dan diedarkan sampai deadlock terdeteksi
oleh masing-masing server. Pada Gambar 17.16 (b), siklus adalah <T o? U? O? W o V o? T?! ?? Dan
pada Gambar 17.16 (c), siklus adalah <W o V o T o U o W>.

Dalam rangka untuk memastikan bahwa hanya satu transaksi dalam siklus dibatalkan, transaksi
diberikan prioritas dalam sedemikian rupa sehingga semua transaksi benar-benar memerintahkan. Cap waktu, untuk
Misalnya, dapat digunakan sebagai prioritas. Ketika siklus kebuntuan ditemukan, transaksi dengan
prioritas terendah dibatalkan. Bahkan jika beberapa server yang berbeda mendeteksi siklus yang sama,
mereka semua akan mencapai keputusan yang sama untuk yang transaksi harus dibatalkan. Kami menulis
T> U untuk menunjukkan bahwa T memiliki prioritas lebih tinggi daripada U. Dalam contoh di atas, asumsikan
T> U> V> W. Kemudian transaksi W akan dibatalkan ketika salah satu siklus
<T o U o W o V o T> atau <W o V o T o U o W> terdeteksi.
Ini mungkin tampak bahwa prioritas transaksi juga bisa digunakan untuk mengurangi jumlah
situasi yang menyebabkan deteksi kebuntuan akan dimulai, dengan menggunakan aturan bahwa deteksi
dimulai hanya ketika transaksi yang lebih tinggi-prioritas mulai menunggu lebih rendah-prioritas satu.
Dalam contoh kita pada Gambar 17.16, sebagai TU yang pemulai penyelidikan <T o U> akan dikirim,
tetapi sebagai W <V yang memulai penyelidikan <W o V> tidak akan dikirim. Jika kita berasumsi bahwa ketika
transaksi mulai menunggu untuk transaksi lain adalah sama kemungkinan bahwa menunggu
transaksi memiliki prioritas yang lebih tinggi atau lebih rendah dari transaksi menunggu-untuk, maka penggunaan
aturan ini kemungkinan akan mengurangi jumlah pesan penyelidikan oleh sekitar setengah.
prioritas transaksi juga dapat digunakan untuk mengurangi jumlah probe yang
diteruskan. Ide umum adalah bahwa probe harus melakukan perjalanan 'menurun' - yaitu, dari
transaksi dengan prioritas yang lebih tinggi untuk transaksi dengan prioritas yang lebih rendah. Untuk akhir ini,
server menggunakan aturan bahwa mereka tidak meneruskan penyelidikan apapun untuk pemegang yang memiliki prioritas lebih tinggi
dari inisiator. Argumen untuk melakukan hal ini adalah bahwa jika pemegang menunggu lain
transaksi, itu harus dimulai deteksi dengan mengirimkan probe ketika mulai menunggu

Gambar 17.17



Namun, ada perangkap yang terkait dengan perbaikan jelas. dalam kami
Misalnya pada Gambar 17,15 transaksi U, V dan W dijalankan dalam urutan di mana U adalah
menunggu V dan V sedang menunggu W saat W mulai menunggu U. Tanpa aturan prioritas,
Deteksi dimulai ketika W dimulai menunggu dengan mengirimkan probe <W o U>. Di bawah
Aturan prioritas, penyelidikan ini tidak akan dikirim karena W <U dan kebuntuan tidak akan
terdeteksi.
Masalahnya adalah bahwa urutan transaksi mulai tunggu dapat menentukan
apakah kebuntuan akan terdeteksi. Perangkap di atas dapat dihindari dengan menggunakan
skema di mana koordinator menyimpan salinan dari semua probe yang diterima atas nama masing-masing
transaksi dalam antrian pemeriksaan. Ketika transaksi mulai menunggu untuk sebuah objek, itu ke depan
probe dalam antrian untuk server dari objek, yang menyebar probe pada
-rute menurun.

Dalam contoh kita pada Gambar 17.15, ketika U mulai menunggu V, koordinator V
akan menghemat probe <U o V> - lihat Gambar 17.17 (a). Kemudian ketika V mulai menunggu W,
koordinator W akan menyimpan <V o W> dan V akan meneruskan antrian probe,
<U o V>, untuk W. (Lihat Gambar 17.17 (b), di mana antrian pemeriksaan W memiliki <U o V> dan
<V o W>.) Ketika W mulai menunggu A itu akan meneruskan antrian probe,
<U o V o W>, ke server A, yang mencatat ketergantungan baru W o U dan
menggabungkannya dengan informasi dalam penyelidikan yang diterima untuk menentukan bahwa
U o V o? W o U. Deadlock terdeteksi.

Ketika suatu algoritma membutuhkan probe untuk disimpan dalam antrian pemeriksaan, hal itu juga memerlukan
pengaturan untuk menyampaikan probe untuk pemegang baru dan membuang probe yang merujuk
transaksi yang telah dilakukan atau dibatalkan. Jika probe yang relevan dibuang,
deadlock terdeteksi dapat terjadi, dan jika probe usang dipertahankan, kebuntuan palsu
dapat dideteksi. Hal ini menambah banyak kompleksitas algoritma tepi-mengejar.
Pembaca yang tertarik dalam rincian algoritma tersebut harus melihat Sinha dan
Natarajan [1985] dan Choudhary et al. [1989], yang hadir algoritma untuk digunakan dengan
kunci eksklusif. Tapi mereka akan melihat bahwa Choudhary et al. menunjukkan bahwa Sinha dan
Algoritma Natarajan adalah salah: gagal untuk mendeteksi semua kebuntuan dan bahkan mungkin melaporkan
kebuntuan palsu. Kshemkalyani dan Singhal [1991] dikoreksi algoritma
Choudhary et al. dan memberikan bukti kebenaran untuk algoritma dikoreksi. Di sebuah
kertas berikutnya, Kshemkalyani dan Singhal [1994] berpendapat bahwa didistribusikan kebuntuan
tidak dipahami dengan baik karena tidak ada negara global atau waktu dalam terdistribusisistem. Bahkan, setiap siklus yang telah dikumpulkan mungkin berisi bagian yang tercatat di
waktu yang berbeda. Selain itu, situs mungkin mendengar tentang kebuntuan tetapi mungkin tidak mendengar bahwa mereka
telah diselesaikan sampai setelah penundaan acak. Makalah ini menjelaskan kebuntuan didistribusikan
dalam hal isi memori terdistribusi, menggunakan hubungan kausal antara
Peristiwa di lokasi yang berbeda.

17.6 PEMULIHAN TRANSAKSI

Properti atom transaksi mensyaratkan bahwa semua efek yang dilakukan
transaksi dan tidak ada efek transaksi tidak lengkap atau dibatalkan tercermin
dalam benda mereka diakses. Properti ini dapat digambarkan dalam dua aspek:
daya tahan dan kegagalan atomicity. Daya tahan mensyaratkan bahwa objek yang disimpan di permanen
penyimpanan dan akan tersedia tanpa batas waktu setelahnya. Oleh karena itu pengakuan
klien melakukan permintaan menyiratkan bahwa semua efek dari transaksi telah
disimpan di penyimpanan permanen serta (mudah menguap) obyek server. Kegagalan
atomicity membutuhkan bahwa efek dari transaksi atom bahkan ketika server crash.
Pemulihan berkaitan dengan memastikan bahwa benda-benda server adalah tahan lama dan bahwalayanan menyediakan kegagalan atomicity.

Meskipun server file dan server database mempertahankan data dalam penyimpanan permanen,
jenis lain dari server benda dipulihkan tidak perlu melakukannya kecuali untuk pemulihan
tujuan. Dalam bab ini, kita berasumsi bahwa ketika server sedang berjalan itu membuat semua yang
benda di memori volatile dan mencatat objek berkomitmen dalam file pemulihan atau
file. Oleh karena itu pemulihan terdiri dari memulihkan server dengan terbaru berkomitmen
versi dari objek dari penyimpanan permanen. Database perlu berurusan dengan besar
volume data. Mereka umumnya memegang benda dalam penyimpanan stabil pada disk dengan cache
dalam memori volatile.

Persyaratan untuk daya tahan dan kegagalan atomicity tidak benar-benar independen
dari satu sama lain dan dapat ditangani oleh mekanisme tunggal - manajer pemulihan.
Tugas seorang manajer pemulihan adalah:
• untuk menyimpan benda-benda dalam penyimpanan permanen (dalam file recovery) untuk berkomitmen
transaksi;
• untuk mengembalikan benda server setelah kecelakaan;
• untuk membenahi file recovery untuk meningkatkan kinerja pemulihan;
• untuk merebut kembali ruang penyimpanan (dalam file recovery).

Dalam beberapa kasus, kita memerlukan manajer pemulihan untuk menjadi tahan terhadap kegagalan media yang.
Korupsi selama kecelakaan, kerusakan acak atau kegagalan permanen dapat menyebabkan kegagalan
file recovery, yang dapat mengakibatkan beberapa data pada disk yang hilang. Sedemikian
kasus kita perlu salinan lain dari file recovery. penyimpanan stabil, yang diimplementasikan
sehingga sangat tidak mungkin untuk gagal dengan menggunakan disk dicerminkan atau salinan di lokasi yang berbeda
dapat digunakan untuk tujuan ini.

Daftar niat • Setiap server yang menyediakan transaksi perlu melacak
benda diakses oleh transaksi nasabah. Ingat dari Bab 16 bahwa ketika klien
membuka transaksi, server pertama dihubungi memberikan pengenal transaksi baru dan



Jenis entri Deskripsi isi entri
Object Sebuah nilai suatu obyek.
status transaksi
Transaksi identifier, status transaksi (disiapkan, berkomitmen,
dibatalkan) dan lainnya nilai status digunakan untuk dua fase komit
protokol.
daftar niat
pengenal transaksi dan urutan niat, yang masing-masing
terdiri dari <objectID, Pi>, di mana Pi adalah posisi dalam pemulihan
file dari nilai objek.

Kembali ke klien. Setiap permintaan klien berikutnya dalam transaksi sampai dengan
termasuk melakukan atau membatalkan permintaan meliputi pengenal transaksi sebagai argumen.
Selama kemajuan transaksi, operasi pembaruan diterapkan untuk satu set pribadi
versi tentatif dari benda milik transaksi.

Pada setiap server, daftar niat dicatat untuk semua yang sedang aktif
Transaksi - daftar niat dari transaksi tertentu berisi daftar referensi
dan nilai-nilai dari semua benda yang diubah oleh transaksi itu. Ketika transaksi
berkomitmen, bahwa daftar transaksi niat digunakan untuk mengidentifikasi objek yang terpengaruh.
Versi berkomitmen setiap objek digantikan oleh versi tentatif dibuat oleh yang
transaksi, dan nilai baru ditulis ke file recovery server. Ketika transaksi
dibatalkan, server menggunakan niat daftar untuk menghapus semua versi tentatif obyek
dibuat oleh transaksi itu.

Ingat juga bahwa transaksi terdistribusi harus melaksanakan komit protokol atom
sebelum dapat dilakukan atau dibatalkan. Diskusi kita pemulihan didasarkan pada dua fase komit protokol, di mana semua peserta yang terlibat dalam transaksi pertama mengatakan
apakah mereka siap untuk melakukan dan kemudian, jika semua peserta setuju, melaksanakan
sebenarnya melakukan tindakan. Jika peserta tidak setuju untuk melakukan, mereka harus membatalkan transaksi.
Gambar 17.18 Jenis entri dalam file recovery Jenis entri Deskripsi isi entri Object Sebuah nilai suatu obyek.
status transaksi Transaksi identifier, status transaksi (disiapkan, berkomitmen,
dibatalkan) dan lainnya nilai status digunakan untuk dua fase komit
protokol.
daftar niat pengenal transaksi dan urutan niat, yang masing-masing terdiri dari <objectID, Pi>, di mana Pi adalah posisi dalam pemulihan file dari nilai objek.

Pada titik ketika peserta mengatakan pihaknya siap untuk melakukan transaksi, yang
manajer pemulihan harus disimpan baik daftar niatnya untuk transaksi dan
objek dalam daftar itu niat dalam file pemulihan, sehingga akan mampu melaksanakan
Komitmen kemudian, bahkan jika itu crash di interim

Ketika semua peserta yang terlibat dalam transaksi setuju untuk melakukan hal itu,
Koordinator memberitahu klien dan kemudian mengirimkan pesan kepada para peserta untuk melakukan
bagian mereka dari transaksi. Setelah klien telah diberitahu bahwa transaksi memiliki
berkomitmen, file pemulihan server yang berpartisipasi harus mengandung cukup
informasi untuk memastikan bahwa transaksi tersebut dilakukan oleh semua server, bahkan jika beberapa
dari mereka kecelakaan antara bersiap-siap untuk melakukan dan melakukan.
Entri dalam file recovery • Untuk menghadapi pemulihan server yang dapat terlibat dalam
didistribusikan transaksi, informasi lebih lanjut selain nilai-nilai dari benda adalah
disimpan dalam file recovery. Informasi ini menyangkut status setiap transaksi –

apakah itu berkomitmen, dibatalkan atau dipersiapkan untuk melakukan. Selain itu, setiap objek dalam
File recovery terkait dengan transaksi tertentu dengan menyimpan daftar niat di
File recovery. Gambar 17.18 menunjukkan ringkasan dari jenis entri termasuk dalam pemulihan
mengajukan.
Nilai-nilai status transaksi yang berkaitan dengan dua fase komit protokol yang
dibahas dalam Bagian 17.6.4. Kami sekarang menggambarkan dua pendekatan untuk penggunaan pemulihan
file: logging dan versi bayangan.

17.6.1 Logging
Dalam teknik logging, file recovery merupakan log yang berisi sejarah semua
transaksi yang dilakukan oleh server. sejarah terdiri dari nilai-nilai objek,
entri status transaksi dan daftar niat transaksi. Urutan entri dalam
log mencerminkan urutan di mana transaksi telah disiapkan, berkomitmen dan dibatalkan pada saat itu
Server. Dalam prakteknya, file recovery akan berisi snapshot terbaru dari nilai-nilai semua
benda di server diikuti dengan riwayat transaksi postdating snapshot

Selama operasi normal dari server, manajer pemulihan disebut setiap kali
transaksi mempersiapkan untuk melakukan, melakukan atau dibatalkan transaksi. Ketika server
siap untuk melakukan transaksi, manajer pemulihan menambahkan semua benda di nya
niat daftar ke file recovery, diikuti dengan status transaksi yang
(Disiapkan) bersama-sama dengan daftar niatnya. Ketika transaksi akhirnya berkomitmen
atau dibatalkan, manajer pemulihan menambahkan status yang bersangkutan transaksi untuk
File pemulihan.

Hal ini diasumsikan bahwa operasi append adalah atom dalam arti bahwa itu menulis satu atau
entri yang lebih lengkap untuk file recovery. Jika server gagal, hanya menulis terakhir dapat
tidak lengkap. Untuk membuat efisiensi penggunaan disk, beberapa menulis berikutnya dapat buffered
dan kemudian ditulis ke disk sebagai write tunggal. Keuntungan tambahan dari penebangan
Teknik adalah bahwa menulis sekuensial ke disk lebih cepat daripada menulis ke lokasi acak.
Setelah kecelakaan, setiap transaksi yang tidak memiliki status berkomitmen dalam log adalah
dibatalkan. Oleh karena itu ketika transaksi melakukan, entri statusnya berkomitmen yang harus
dipaksa untuk log - yaitu, ditulis ke log bersama dengan entri buffered lainnya.

Manajer pemulihan mengaitkan pengenal yang unik dengan setiap objek sehingga
versi-versi dari sebuah objek di file recovery dapat berhubungan dengan server
benda. Misalnya, bentuk tahan lama dari objek remote referensi seperti CORBA sebuah
referensi gigih akan melakukan sebagai identifier objek.
Gambar 17.19 mengilustrasikan mekanisme log untuk transaksi layanan perbankan T
dan U pada Gambar 16.7. log baru-baru ini melakukan reorganisasi, dan entri ke kiri
garis ganda merupakan sebuah snapshot dari nilai-nilai A, B dan C sebelum transaksi T dan U
mulai. Dalam diagram ini, kita menggunakan nama A, B dan C sebagai pengidentifikasi unik untuk objek.
Kami menunjukkan situasi ketika transaksi T telah berkomitmen dan transaksi U telah menyiapkan
tapi tidak dilakukan. Ketika transaksi T mempersiapkan untuk melakukan, nilai-nilai benda A dan
B ditulis pada posisi P1 dan P2 di log, diikuti dengan status transaksi siap
entri untuk T dengan daftar niatnya (<A, P1>, <B, P2>). Ketika transaksi T melakukan, sebuah
transaksi yang dijanjikan masuk status T diletakkan pada posisi P4. Kemudian ketika transaksi U
mempersiapkan untuk melakukan, nilai-nilai objek C dan B ditulis pada posisi P5 dan P6 di
log, diikuti dengan masuknya status transaksi siap untuk U dengan daftar niatnya
(<C, P5>, <B, P6>).

GAMBAR 17.19

Setiap entri status transaksi berisi sebuah pointer ke posisi dalam file recovery
entri status transaksi sebelumnya untuk memungkinkan manajer pemulihan untuk mengikuti
entri status transaksi dalam urutan terbalik melalui file recovery. Pointer terakhir di
urutan status transaksi entri poin untuk pos pemeriksaan.
Pemulihan benda • Ketika server diganti setelah terjadi kecelakaan, itu set pertama awal bawaan
nilai untuk objek dan kemudian menyerahkan kepada manajer pemulihan. Manajer Pemulihan
bertanggung jawab untuk memulihkan objek server sehingga mereka mencakup semua dampak dari
transaksi yang dilakukan dilakukan dalam urutan yang benar dan tidak ada efek
lengkap atau dibatalkan transaksi.

Informasi terbaru tentang transaksi adalah pada akhir log. Ada
dua pendekatan untuk memulihkan data dari file recovery. Pada bagian pertama, pemulihan
Manajer dimulai di awal dan mengembalikan nilai-nilai semua benda dari yang paling
pos pemeriksaan baru-baru ini (dibahas pada bagian berikutnya). Kemudian membaca dalam nilai-nilai dari masing-masing
benda, mengaitkan mereka dengan daftar transaksi mereka niat dan komitmen
transaksi menggantikan nilai-nilai dari objek. Dalam pendekatan ini, transaksi yang
diputar dalam urutan di mana mereka dieksekusi dan mungkin ada sejumlah besar
mereka. Dalam pendekatan kedua, manajer pemulihan akan mengembalikan objek server oleh
'Membaca file recovery mundur'. File pemulihan telah terstruktur sehingga ada
adalah pointer mundur dari setiap entri status transaksi ke yang berikutnya. pemulihan
Manajer menggunakan transaksi dengan status yang berkomitmen untuk mengembalikan benda-benda yang belum
belum dikembalikan. Terus sampai telah dipulihkan semua benda server. Ini mempunyai
keuntungan bahwa setiap objek dipulihkan sekali saja.

Untuk memulihkan efek dari transaksi, manajer pemulihan mendapat yang sesuai
niat daftar dari file pemulihan. Daftar niat berisi pengenal dan
posisi dalam file pemulihan nilai-nilai semua benda dipengaruhi oleh transaksi.
Jika server gagal pada titik mencapai pada Gambar 17.19, manajer pemulihan akan
memulihkan benda sebagai berikut. Dimulai pada transaksi terakhir masuk status dalam log (di
P7) dan menyimpulkan bahwa transaksi U belum berkomitmen dan dampaknya harus
diabaikan. Kemudian bergerak ke sebelumnya masuk status transaksi di log (di P4) dan
menyimpulkan bahwa transaksi T telah berkomitmen. Untuk memulihkan benda dipengaruhi oleh
transaksi T, bergerak ke sebelumnya masuk status transaksi di log (di P3) dan menemukandaftar niat untuk T (<A, P1>, <B, P2>). Kemudian mengembalikan benda A dan B dari
nilai-nilai di P1 dan P2. Karena belum dipulihkan C, bergerak kembali ke P0, yang merupakan
pos pemeriksaan, dan mengembalikan C.

Untuk membantu dengan reorganisasi berikutnya dari file recovery, manajer pemulihan
mencatat semua transaksi siap yang ditemukan selama proses mengembalikan server
benda. Untuk setiap transaksi siap, ia menambahkan status transaksi dibatalkan dengan
File recovery. Hal ini memastikan bahwa dalam file recovery, setiap transaksi akhirnya
ditampilkan baik sebagai komitmen atau dibatalkan.
Server bisa gagal lagi selama prosedur pemulihan. Adalah penting bahwa
recovery akan idempoten, dalam arti bahwa hal itu dapat dilakukan sejumlah kali dengan
efek yang sama. Ini sangat mudah di bawah asumsi kita bahwa semua benda dikembalikan
ke memori volatile. Dalam kasus database, yang membuat benda di permanen
penyimpanan dengan cache dalam memori volatile, beberapa objek dalam penyimpanan permanen akan
kedaluwarsa ketika server diganti setelah terjadi kecelakaan. Oleh karena itu manajer pemulihan
harus mengembalikan benda-benda di penyimpanan permanen. Jika gagal selama pemulihan, sebagian
benda dipulihkan akan tetap ada. Hal ini membuat idempotence sedikit lebih sulit untuk dicapai.

Reorganisasi file recovery • Seorang manajer pemulihan bertanggung jawab untuk reorganisasi nya
File recovery sehingga membuat proses pemulihan lebih cepat dan mengurangi penggunaan ruang.
Jika file recovery tidak pernah ditata ulang, maka proses pemulihan harus mencari
mundur melalui file recovery sampai telah menemukan nilai untuk masing-masing objek tersebut.
Secara konseptual, satu-satunya informasi yang diperlukan untuk pemulihan adalah salinan berkomitmen
versi setiap objek di server. Ini akan menjadi bentuk paling kompak untuk
File recovery. Nama checkpointing digunakan untuk merujuk pada proses penulisan
nilai berkomitmen saat benda server untuk file recovery baru, bersama-sama dengan
entri status transaksi dan daftar niat transaksi yang belum sepenuhnya
diselesaikan (termasuk informasi yang terkait dengan dua-tahap melakukan protocol). Syarat
pos pemeriksaan digunakan untuk merujuk pada informasi yang disimpan oleh proses checkpointing. Itu
Tujuan dari pembuatan pos pemeriksaan adalah untuk mengurangi jumlah transaksi yang harus ditangani
selama pemulihan dan untuk merebut kembali ruang file.

Checkpointing dapat segera dilakukan setelah pemulihan tapi sebelum baru
transaksi dimulai. Namun, pemulihan mungkin tidak terjadi sangat sering. Karena itu,
checkpointing mungkin perlu dilakukan dari waktu ke waktu selama aktivitas normal dari
Server. pos pemeriksaan ditulis ke file pemulihan di masa depan, dan file recovery saat ini
tetap digunakan sampai pos pemeriksaan selesai. Checkpointing terdiri dari 'menambahkan
mark 'ke file recovery ketika checkpointing dimulai, menulis objek server untuk
file pemulihan di masa depan dan kemudian menyalin ke file yang (1) semua entri sebelum tanda yang
berhubungan dengan transaksi yang belum terselesaikan dan (2) semua entri setelah tanda pemulihan yang
mengajukan. Ketika pemeriksaan selesai, file pemulihan di masa depan menjadi pemulihan
mengajukan.

Sistem pemulihan dapat mengurangi penggunaan ruang dengan membuang pemulihan tua

mengajukan. Ketika manajer pemulihan melaksanakan proses pemulihan, itu mungkin mengalami

sebuah pos pemeriksaan di file recovery. Ketika ini terjadi, dapat segera mengembalikan semua

benda luar biasa dari pos pemeriksaan.

GAMBAR 17.20





17.6.2VERSI Bayangan
Teknik penebangan mencatat entri status transaksi, daftar niat dan objek semua
dalam file yang sama - log. Teknik versi bayangan adalah cara alternatif untuk
mengatur file recovery. Menggunakan peta untuk menemukan versi objek server dalam sebuah file
disebut toko versi. peta mengaitkan pengenal objek server dengan
posisi versi mereka saat ini di toko versi. Versi ditulis oleh masing-masing
Transaksi yang 'bayangan' dari versi berkomitmen sebelumnya. Seperti yang akan kita lihat,
transaksi entri status dan daftar niat disimpan secara terpisah. versi bayangan yang
dijelaskan pertama.

Ketika transaksi disiapkan untuk melakukan, salah satu objek diubah oleh
transaksi yang ditambahkan ke toko versi, meninggalkan yang sesuai berkomitmen
versi tidak berubah. Ini versi yang belum tentatif baru disebut versi shadow.
Ketika transaksi melakukan, peta baru dibuat dengan menyalin peta tua dan memasuki
posisi dari versi bayangan. Untuk melengkapi komit proses, peta baru
menggantikan peta tua.

Untuk mengembalikan objek ketika server diganti setelah kecelakaan, manajer pemulihan
membaca peta dan menggunakan informasi dalam peta untuk menemukan benda-benda di versi
toko.
Gambar 17.20 mengilustrasikan teknik ini dengan contoh yang sama yang melibatkan
transaksi T dan U
Gambar 17.20 versi Bayangan
Map di awal Peta ketika T melakukan
A o P0 A o P1
B o P0 'B o P2
C o P0 "C o P0"
P0 P0 'P0 "P1 P2 P3 P4
Versi store 100 200 300 80 220 278 242
Pos pemeriksaan
. Kolom pertama dalam tabel menunjukkan peta sebelum transaksi T
dan U, ketika saldo dari rekening A, B dan C adalah $ 100, $ 200 dan $ 300,
masing-masing. Kolom kedua menunjukkan peta setelah transaksi T telah berkomitmen.
Toko Versi berisi sebuah pos pemeriksaan, diikuti oleh versi A dan B di P1
dan P2 yang dibuat oleh T. transaksi Hal ini juga berisi versi bayangan B dan C yang dibuat oleh
Transaksi U, di P3 dan P

Peta harus selalu ditulis untuk tempat terkenal (misalnya, di awal
toko versi atau file terpisah) sehingga dapat ditemukan ketika sistem perlu
diperoleh kembali.
Beralih dari peta lama ke peta baru harus dilakukan dalam atom tunggal
langkah. Untuk mencapai hal ini sangat penting bahwa penyimpanan stabil digunakan untuk peta, sehingga ada
dijamin peta valid bahkan ketika operasi menulis file gagal. Versi shadow
Metode menyediakan pemulihan lebih cepat dari penebangan karena posisi saat ini
benda berkomitmen dicatat dalam peta, sedangkan pemulihan dari log membutuhkan

mencari seluruh log untuk objek. Penebangan harus lebih cepat dari versi shadow
selama aktivitas normal dari sistem, meskipun. Hal ini karena penebangan hanya membutuhkan
urutan operasi append ke file yang sama, sedangkan versi bayangan membutuhkan
tambahan stabil penyimpanan write (melibatkan dua blok disk yang tidak terkait).
versi bayangan sendiri tidak cukup untuk server yang menangani
didistribusikan transaksi. entri status transaksi dan daftar niat disimpan dalam file
disebut file status transaksi. Setiap daftar niat merupakan bagian dari peta yang
akan diubah oleh transaksi ketika melakukan. Status transaksi berkas mungkin, untuk
Misalnya, diatur sebagai log.

Gambar di bawah menunjukkan peta dan status transaksi file untuk saat ini kami
Misalnya ketika IT telah berkomitmen dan U siap untuk melakukan:



Ada kemungkinan bahwa server mungkin crash antara waktu ketika status berkomitmen adalah
ditulis ke file status transaksi dan waktu ketika peta diperbarui - di mana
kasus klien tidak akan telah diakui. Manajer pemulihan harus memungkinkan untuk
kemungkinan ini ketika server diganti setelah kecelakaan, misalnya dengan memeriksa
apakah peta mencakup dampak dari transaksi yang dijanjikan terakhir dalam transaksi
File status. Jika tidak, maka yang terakhir harus ditandai sebagai dibatalkan.

   17.6.3 Kebutuhan status transaksi dan daftar niat entri dalam file recovery
Hal ini dimungkinkan untuk merancang file pemulihan sederhana yang tidak termasuk entri untuk transaksi
item status dan daftar niat. semacam ini file recovery mungkin cocok ketika semua
transaksi diarahkan ke server tunggal. Penggunaan barang-barang status transaksi dan
niat daftar dalam file recovery adalah penting untuk server yang dimaksudkan untuk berpartisipasi
dalam transaksi terdistribusi. Pendekatan ini juga dapat berguna untuk server dari transaksi non didistribusikan karena berbagai alasan, termasuk yang berikut:
• Beberapa manajer pemulihan dirancang untuk menulis objek untuk file recovery
awal, dengan asumsi bahwa transaksi biasanya komit.
• Jika transaksi menggunakan sejumlah besar objek besar, kebutuhan untuk menulis mereka
contiguously ke file recovery dapat mempersulit desain server. Kapan
objek yang direferensikan dari daftar niat, mereka dapat ditemukan di mana pun mereka berada.
• Dalam timestamp kontrol konkurensi memesan, server kadang-kadang tahu bahwa
transaksi akhirnya akan mampu untuk melakukan dan mengakui klien - di ini
waktu, objek yang ditulis ke file recovery (lihat Bab 16) untuk memastikan mereka
keabadian. Namun, transaksi mungkin harus menunggu untuk melakukan sampai awal
transaksi telah berkomitmen. Dalam situasi seperti itu, sesuai transaksi
entri status dalam file recovery akan menunggu untuk melakukan dan kemudian berkomitmen untukmemastikan timestamp pemesanan transaksi yang dilakukan di file recovery. Di
recovery, setiap tunggu-to-komit transaksi dapat diizinkan untuk melakukan, karena
yang mereka sedang menunggu akan memiliki baik saja bunuh atau telah dibatalkan karena
kegagalan server.

   17.6.4 Pemulihan dari dua fase komit protokol
Dalam transaksi terdistribusi, setiap server terus recovery file sendiri. pemulihan
manajemen dijelaskan dalam bagian sebelumnya harus diperluas untuk menangani setiap
transaksi yang melakukan dua fase komit protokol pada waktu itu ketika
server gagal. Manajer Pemulihan menggunakan dua nilai status baru untuk tujuan ini: dilakukan dan
pasti. nilai status ini ditunjukkan pada Gambar 17.6. Seorang koordinator menggunakan berkomitmen
untuk menunjukkan bahwa hasil pemungutan suara adalah Ya dan dilakukan untuk menunjukkan bahwa dua-fase
commit protocol selesai. Seorang peserta menggunakan pasti untuk menunjukkan bahwa ia telah sebagai
Ya tapi belum tahu hasil suara. Dua jenis tambahan entri memungkinkan
koordinator untuk merekam daftar peserta dan peserta untuk merekam koordinatornya:





Jenis entri                                           Deskripsi isi entri
Koordinator                                        Transaksi identifier, daftar peserta
Peserta                                              Transaksi identifier, koordinator

    Pada fase 1 dari protokol, ketika koordinator disiapkan untuk melakukan (dan sudah
menambahkan entri statusnya siap ke file pemulihan), manager pemulihan menambahkan
Koordinator masuk ke file pemulihan. Sebelum peserta dapat memilih Ya, itu harus memiliki
sudah siap untuk melakukan (dan harus telah menambahkan entri statusnya siap untuk nya
File recovery). Ketika memberikan suara Ya, manajer pemulihan mencatat entri peserta dan
menambahkan status transaksi pasti ke file recovery sebagai write paksa. Ketika sebuah
peserta penilaian ada, itu menambah status transaksi batalkan ke file pemulihan.

Pada fase 2 protokol, manajer pemulihan koordinator menambahkan baik
berkomitmen atau status transaksi dibatalkan ke file recovery, menurut keputusan.
Ini harus menjadi write paksa (yaitu, ada tertulis segera ke file recovery).
manajer pemulihan peserta menambahkan melakukan atau membatalkan status transaksi ke mereka
file recovery sesuai dengan pesan yang diterima dari koordinator. Ketika sebuah
Koordinator telah menerima konfirmasi dari semua peserta, manajer pemulihan
menambahkan status transaksi yang dilakukan ke file pemulihan - ini tidak perlu dipaksakan. yang dilakukan
entri Status bukan bagian dari protokol tetapi digunakan ketika file recovery adalah reorganisasi.
Gambar 17.21 menunjukkan entri dalam log transaksi T, di mana server memainkan
peran koordinator, dan untuk transaksi U, di mana server memainkan peran peserta.
Untuk kedua transaksi, yang siap masuk status transaksi yang lebih dulu. Dalam kasus
koordinator itu diikuti dengan entri koordinator dan status transaksi yang dijanjikan
masuk. Entri status transaksi yang dilakukan tidak ditampilkan pada Gambar 17.21. Dalam kasus
peserta, entri status transaksi yang disiapkan diikuti dengan masuknya peserta
negara yang tidak pasti dan kemudian masuk status transaksi berkomitmen atau dibatalkan.
Gambar 17.21 Log dengan entri yang berkaitan dengan dua fase komit protokol
Trans: T Coord'r: T • • Trans: T Trans: U • • Part'pant: U Trans: U Trans: U
siap
part'pant
Daftar:. . .
berkomitmen disiapkan Coord'r:. . . pasti berkomitmen
niat
daftar
niat
daftar
BAGIAN 17,6 TRANSAKSI RECOVERY 759
Ketika server diganti setelah terjadi kecelakaan, manajer pemulihan harus berurusan dengan
dua fase komit protokol selain memulihkan benda. Untuk setiap transaksi
di mana server telah memainkan peran koordinator, harus menemukan entri koordinator dan
satu set entri status transaksi. Untuk setiap transaksi di mana server memainkan
Peran peserta, harus menemukan entri peserta dan satu set entri status transaksi.
Dalam kedua kasus, yang paling baru masuk status transaksi - yaitu, yang terdekat akhirnya
log - menentukan status transaksi pada saat kegagalan. Aksi
manajer pemulihan sehubungan dengan dua fase komit protokol untuk setiap transaksi
tergantung pada apakah server adalah koordinator atau peserta dan statusnya di
saat kegagalan, seperti yang ditunjukkan pada Gambar 17.22.

Reorganisasi file recovery • Perawatan harus diambil ketika melakukan sebuah pos pemeriksaan untuk
memastikan bahwa entri koordinator transaksi tanpa status dilakukan tidak dihapus dari
file recovery. entri ini harus dipertahankan sampai semua peserta telah dikonfirmasi
bahwa mereka telah menyelesaikan transaksi mereka. Entri dengan status yang dilakukan dapat dibuang.
entri peserta dengan negara transaksi pasti juga harus dipertahankan.
Pemulihan transaksi bersarang • Dalam kasus yang paling sederhana, masing-masing subtransaction dari bersarang
transaksi mengakses satu set yang berbeda dari objek. Seperti setiap peserta mempersiapkan untuk melakukan
selama dua fase komit protokol, itu menulis objek dan daftar niat untuk
File recovery lokal, menghubungkan mereka dengan pengenal transaksi dari tingkat atas
transaksi. Meskipun transaksi bersarang menggunakan varian khusus dari dua fase komit
protokol, manajer pemulihan menggunakan nilai status transaksi sama dengan datar
transaksi.

Namun, batalkan pemulihan rumit oleh fakta bahwa beberapa subtransactions di
tingkat yang sama dan berbeda dalam hirarki bersarang dapat mengakses objek yang sama. Bagian 16,4 menjelaskan skema penguncian di mana transaksi orangtua mewarisi kunci dan
sub transaksi mendapatkan kunci dari orang tua mereka. Pasukan skema penguncian orang tua
transaksi dan subtransactions untuk mengakses objek data umum pada waktu yang berbeda dan
Memastikan bahwa mengakses oleh subtransactions bersamaan dengan objek yang sama harus
serial.
Benda yang diakses sesuai dengan aturan transaksi bersarang dilakukan
dipulihkan dengan menyediakan versi tentatif untuk setiap subtransaction. Hubungan
antara versi tentatif dari obyek yang digunakan oleh subtransactions dari bersarang
transaksi ini mirip dengan hubungan antara kunci. Untuk mendukung pemulihan dari
dibatalkan, server obyek bersama oleh transaksi pada berbagai tingkat menyediakan setumpuk
versi tentatif - satu untuk setiap transaksi bersarang untuk digunakan.



Gambar 17.21 Log dengan entri yang berkaitan dengan dua fase komit protokol

Ketika server diganti setelah terjadi kecelakaan, manajer pemulihan harus berurusan dengan
dua fase komit protokol selain memulihkan benda. Untuk setiap transaksi
di mana server telah memainkan peran koordinator, harus menemukan entri koordinator dan
satu set entri status transaksi. Untuk setiap transaksi di mana server memainkan
Peran peserta, harus menemukan entri peserta dan satu set entri status transaksi.
Dalam kedua kasus, yang paling baru masuk status transaksi - yaitu, yang terdekat akhirnya
log - menentukan status transaksi pada saat kegagalan. Aksi
manajer pemulihan sehubungan dengan dua fase komit protokol untuk setiap transaksi
tergantung pada apakah server adalah koordinator atau peserta dan statusnya di
saat kegagalan, seperti yang ditunjukkan pada Gambar 17.22.

Reorganisasi file recovery • Perawatan harus diambil ketika melakukan sebuah pos pemeriksaan untuk
memastikan bahwa entri koordinator transaksi tanpa status dilakukan tidak dihapus dari
file recovery. entri ini harus dipertahankan sampai semua peserta telah dikonfirmasi
bahwa mereka telah menyelesaikan transaksi mereka. Entri dengan status yang dilakukan dapat dibuang.
entri peserta dengan negara transaksi pasti juga harus dipertahankan.
Pemulihan transaksi bersarang • Dalam kasus yang paling sederhana, masing-masing subtransaction dari bersarang
transaksi mengakses satu set yang berbeda dari objek. Seperti setiap peserta mempersiapkan untuk melakukan
selama dua fase komit protokol, itu menulis objek dan daftar niat untuk
File recovery lokal, menghubungkan mereka dengan pengenal transaksi dari tingkat atas
transaksi. Meskipun transaksi bersarang menggunakan varian khusus dari dua fase komit
protokol, manajer pemulihan menggunakan nilai status transaksi sama dengan datar
transaksi.

Namun, batalkan pemulihan rumit oleh fakta bahwa beberapa subtransactions di
tingkat yang sama dan berbeda dalam hirarki bersarang dapat mengakses objek yang sama. Bagian
16,4 menjelaskan skema penguncian di mana transaksi orangtua mewarisi kunci dan
sub transaksi mendapatkan kunci dari orang tua mereka. Pasukan skema penguncian orang tua
transaksi dan subtransactions untuk mengakses objek data umum pada waktu yang berbeda dan
Memastikan bahwa mengakses oleh subtransactions bersamaan dengan objek yang sama harus
serial.
Benda yang diakses sesuai dengan aturan transaksi bersarang dilakukan
dipulihkan dengan menyediakan versi tentatif untuk setiap subtransaction. Hubungan
antara versi tentatif dari obyek yang digunakan oleh subtransactions dari bersarang
transaksi ini mirip dengan hubungan antara kunci. Untuk mendukung pemulihan dari
dibatalkan, server obyek bersama oleh transaksi pada berbagai tingkat menyediakan setumpuk
versi tentatif - satu untuk setiap transaksi bersarang untuk digunakan.

Gambar 17.22 Pemulihan dari dua fase komit protokol


Peran Status Aksi manajer pemulihan
Koordinator disiapkan ada keputusan telah dicapai sebelum server gagal. Saya t
mengirimkan membatalkan transaksi ke semua server di peserta
daftar dan menambahkan status transaksi dibatalkan di pemulihan
mengajukan. tindakan yang sama untuk negara dibatalkan. Jika tidak ada peserta
daftar, peserta akhirnya akan waktu dan membatalkantransaksi.
Koordinator berkomitmen Keputusan untuk melakukan telah dicapai sebelum server
gagal. Ini mengirimkan doCommit untuk semua peserta di nya
daftar peserta (dalam kasus itu tidak melakukannya sebelumnya) dan
resume protokol dua-fasa pada langkah 4 (lihat Gambar 17.5).
Peserta berkomitmen Peserta mengirimkan pesan telah Berkomitmen untuk
Koordinator (dalam hal ini tidak dilakukan sebelum gagal).
Hal ini akan memungkinkan koordinator untuk membuang informasi
tentang transaksi ini di pos pemeriksaan berikutnya.
Peserta tidak pasti peserta gagal sebelum tahu hasil dari
transaksi. Tidak dapat menentukan status
transaksi sampai koordinator menginformasikan itu keputusan.
Ini mengirimkan getDecision untuk koordinator untuk menentukan
status transaksi. Ketika menerima balasan itu akan
melakukan atau membatalkan sesuai.
Peserta mempersiapkan peserta belum sebagai dan dapat membatalkan
transaksi.
Koordinator dilakukan Tidak ada tindakan yang diperlukan.



Ketika subtransaction pertama dalam serangkaian transaksi bersarang mengakses sebuah objek, itu
dilengkapi dengan versi tentatif yang merupakan salinan dari versi berkomitmen saat ini
obyek. Hal ini dianggap sebagai di bagian atas tumpukan, tetapi kecuali salah nya
subtransactions mengakses objek yang sama, tumpukan tidak akan terwujud.
Ketika salah satu dari subtransactions yang tidak mengakses objek yang sama, itu salinan versi
di bagian atas tumpukan dan mendorong kembali ke stack. Semua subtransactions yang
update diterapkan ke versi tentatif di bagian atas tumpukan. Ketika subtransaction a
sementara melakukan, induknya mewarisi versi baru. Untuk mencapai hal ini, baik
Versi subtransactions dan versi induknya dibuang dari stack dan kemudian
Versi baru subtransaction ini didorong kembali ke stack (efektif menggantikan nya
versi orang tua). Ketika subtransaction sebuah dibatalkan, versi di atas tumpukan
dibuang. Akhirnya, pada saat transaksi tingkat atas melakukan, versi di atas
stack (jika ada) menjadi versi berkomitmen baru.



Gambar 17.23 transaksi Bersaran





Misalnya, pada Gambar 17.23
Gambar 17.23 transaksi Bersarang
T1
A11 A12 A2
A1
T1 T11 T12 T2
A11
A11 A12
A2
atas tumpukan
T1
T2
T11
T12
A11 A2
, Misalkan transaksi T1, T11, T12 dan T2 semua
mengakses objek yang sama, A, dalam urutan T1; T11; T12; T2. Misalkan tentatif mereka
versi disebut A1, A11, A12 dan A2. Ketika T1 mulai dijalankan, A1 didasarkan pada
Versi berkomitmen A dan didorong ke stack. Ketika T11 mulai dijalankan, itu mendasarkan
A11 versi pada A1 dan mendorong ke stack; ketika itu selesai, itu menggantikan nya
versi orang tua di stack. Transaksi T12 dan T2 bertindak dengan cara yang sama, akhirnya
meninggalkan hasil T2 di bagian atas tumpukan.

17.7 Ringkasan
Dalam kasus yang paling umum, transaksi klien akan meminta operasi pada objek di
beberapa server yang berbeda. Sebuah transaksi terdistribusi adalah transaksi yang kegiatan
melibatkan beberapa server yang berbeda. Sebuah struktur transaksi bersarang dapat digunakan untuk memungkinkan
concurrency tambahan dan independen melakukan oleh server dalam didistribusikan
transaksi.
Properti atomicity transaksi mensyaratkan bahwa server berpartisipasi dalam
transaksi terdistribusi baik semua komit atau semua menggugurkannya. Atom komit protokol yang
dirancang untuk mencapai efek ini, bahkan jika server kecelakaan selama eksekusi mereka. Dua tahap melakukan protocol memungkinkan server untuk memutuskan untuk membatalkan secara sepihak. Ini termasuk batas waktu
tindakan untuk menangani penundaan karena server menerjang. Dua fase komit protokol dapat
mengambil jumlah tak terbatas waktu untuk menyelesaikan tapi dijamin untuk menyelesaikan akhirnya.

concurrency control dalam transaksi terdistribusi adalah modular - masing server
bertanggung jawab atas serializability transaksi yang mengakses obyek sendiri. Namun,
protokol tambahan yang diperlukan untuk memastikan bahwa transaksi serializable global.
didistribusikan transaksi yang menggunakan timestamp ordering membutuhkan sarana untuk menghasilkan sebuah
setuju timestamp ordering antara beberapa server. Mereka yang menggunakan optimis
kontrol konkurensi memerlukan validasi global atau sarana memaksa memesan global
melakukan transaksi.
Didistribusikan transaksi yang menggunakan dua fase penguncian dapat menderita didistribusikan
kebuntuan. Tujuan dari deteksi kebuntuan didistribusikan adalah untuk mencari siklus di global
menunggu-untuk grafik. Jika siklus ditemukan, satu atau lebih transaksi harus dibatalkan untuk menyelesaikan
kebuntuan. Tepi mengejar adalah pendekatan non-terpusat untuk deteksi terdistribusi
kebuntuan.

Aplikasi berbasis transaksi memiliki persyaratan yang kuat untuk hidup panjang dan
integritas informasi yang disimpan, tetapi mereka biasanya tidak memiliki persyaratan untuk
tanggapan langsung setiap saat. Atom komit protokol adalah kunci untuk didistribusikan
transaksi, tetapi mereka tidak dapat dijamin untuk menyelesaikan dalam batas waktu tertentu.
Transaksi dilakukan tahan lama dengan melakukan pemeriksaan dan masuk pemulihan
file, yang digunakan untuk pemulihan ketika server diganti setelah terjadi kecelakaan. Pengguna dari
layanan transaksi akan mengalami beberapa penundaan selama pemulihan. Meskipun diasumsikan
bahwa server transaksi terdistribusi menunjukkan kegagalan kecelakaan dan dijalankan dalam
sistem asynchronous, mereka mampu mencapai konsensus tentang hasil
transaksi karena jatuh server diganti dengan proses baru yang dapat memperoleh
semua informasi yang relevan dari penyimpanan permanen atau dari server lain.



LATIHAN
17.1 Dalam varian desentralisasi dari dua fase komit protokol peserta
berkomunikasi langsung dengan satu sama lain bukannya tidak langsung melalui koordinator. Dalam fase
1, koordinator mengirimkan suara untuk semua peserta. Pada fase 2, dari koordinator
orang adalah ada, para peserta hanya membatalkan transaksi; jika Ya, setiap peserta mengirimkan
suara kepada koordinator dan para peserta lainnya, yang masing-masing memutuskan pada
hasil sesuai dengan suara dan membawanya keluar. Menghitung jumlah pesan dan
jumlah putaran yang dibutuhkan. Apa keuntungan dan kerugiannya dibandingkan
dengan varian terpusat?

17.2 A tiga fase komit protokol memiliki bagian-bagian berikut:
Tahap 1: Apakah sama dengan dua fase komit.
Tahap 2: Koordinator mengumpulkan orang dan membuat keputusan. Jika ada, itu
dibatalkan dan menginformasikan bahwa sebagai Ya; jika keputusan adalah Ya, ia akan mengirimkan
preCommit permintaan untuk semua peserta. Peserta yang sebagai Ya tunggu
preCommit atau permintaan doAbort. Mereka mengakui permintaan preCommit dan membawa
out permintaan doAbort.
Tahap 3: Koordinator mengumpulkan pengakuan. Ketika semua diterima,
itu melakukan dan mengirimkan permintaan doCommit kepada para peserta. Peserta menunggu
permintaan doCommit. Ketika tiba, mereka melakukan.
Jelaskan bagaimana protokol ini menghindari keterlambatan peserta selama periode 'pasti' mereka
karena kegagalan koordinator atau peserta lainnya. Asumsikan bahwa komunikasi
tidak gagal. halaman 735
17.3 Jelaskan bagaimana dua fase komit protokol untuk transaksi bersarang memastikan bahwa jika
transaksi tingkat atas melakukan, semua keturunan yang benar berkomitmen atau dibatalkan.
halaman 736

17.4 Berikan contoh interleaving itu, dua transaksi yang serial setara di
setiap server tetapi tidak secara serial setara global. halaman 740
LATIHAN 763
17.5 Prosedur getDecision didefinisikan pada Gambar 17.4 disediakan hanya oleh koordinator.
Mendefinisikan versi baru dari getDecision yang akan diberikan oleh peserta untuk digunakan oleh lainnya
peserta yang perlu untuk mendapatkan keputusan ketika koordinator tidak tersedia.
Asumsikan bahwa setiap peserta aktif dapat membuat permintaan getDecision ke yang lain
peserta aktif. Apakah ini memecahkan masalah keterlambatan selama periode 'pasti'?
Jelaskan jawabanmu. Pada titik dalam dua fase komit protokol akankah
Koordinator menginformasikan peserta identitas peserta lain '(untuk mengaktifkan ini
komunikasi)? halaman 732
17.6 Perluas definisi penguncian dua-tahap untuk berlaku untuk transaksi terdistribusi.

Menjelaskan
bagaimana ini dipastikan dengan transaksi didistribusikan menggunakan penguncian dua-fase yang ketat secara lokal.
Halaman 740, Bab 16




17,7 Dengan asumsi bahwa penguncian dua-fase yang ketat sedang digunakan, menggambarkan bagaimana tindakan twophase komit protokol berhubungan dengan tindakan kontrol konkurensi dari masing-masing individu
Server. Bagaimana didistribusikan kebuntuan deteksi cocok? halaman 732, 740
17,8 Server menggunakan timestamp ordering untuk kontrol concurrency lokal. Perubahan apa yang harus
dibuat untuk beradaptasi untuk digunakan dengan transaksi terdistribusi? Dalam kondisi apa bisa itu
berpendapat bahwa dua-tahap melakukan protokol berlebihan dengan tanda waktu pemesanan?
halaman 732, 741
17,9 Pertimbangkan didistribusikan kontrol konkurensi optimis di mana setiap server melakukan lokal
mundur validasi berurutan (yaitu, dengan hanya satu transaksi memvalidasi dan
memperbarui fase pada satu waktu), dalam kaitannya dengan jawaban Anda untuk Latihan 17,4. Jelaskan
kemungkinan hasil ketika dua transaksi mencoba untuk melakukan. Apa bedanya
itu membuat jika server menggunakan validasi paralel? Bab 16, halaman 742
17.10 Sebuah detektor kebuntuan global yang terpusat memegang persatuan lokal grafik menunggu-untuk. Berikan
contoh untuk menjelaskan bagaimana hantu kebuntuan dapat dideteksi jika transaksi menunggu
dalam siklus kebuntuan dibatalkan selama prosedur deteksi deadlock. halaman 745
17,11 Pertimbangkan algoritma tepi-mengejar (tanpa prioritas). Berikan contoh untuk menunjukkan bahwa
bisa mendeteksi deadlock phantom. halaman 746
17.12 Sebuah server mengelola objek a1, a2, ... an. Ini menyediakan dua operasi untuk klien:
membaca (i) mengembalikan nilai ai
menulis (i, Nilai) memberikan Nilai untuk ai
Transaksi T, U dan V didefinisikan sebagai berikut:
T: x = read (i); menulis (j, 44);
U: write (i, 55); menulis (j, 66);
V: write (k, 77); menulis (k, 88);
Menggambarkan informasi tertulis ke file log atas nama tiga transaksi ini jika
penguncian dua-fase yang ketat sedang digunakan dan U mengakuisisi ai dan aj sebelum T. Jelaskan bagaimana
Manajer pemulihan akan menggunakan informasi ini untuk memulihkan efek T, U dan V saat
server diganti setelah terjadi kecelakaan. Apa arti penting dari urutan komit
entri dalam file log? halaman 753-754
17,13 The menambahkan sebuah entri ke file log adalah atom, tapi menambahkan operasi dari berbagai
transaksi dapat disisipkan. Bagaimana hal ini mempengaruhi jawaban untuk Latihan 17,12?



17.14 Transaksi T, U dan V dari Latihan 17.12 penggunaan penguncian dua-fase yang ketat dan mereka
permintaan yang disisipkan sebagai berikut:



Dengan asumsi bahwa manajer pemulihan menambahkan entri data yang sesuai untuk setiap menulis
operasi untuk file log segera bukannya menunggu sampai akhir transaksi,
menggambarkan informasi tertulis ke file log atas nama transaksi T, U dan V.
Apakah tulisan awal mempengaruhi kebenaran dari prosedur pemulihan? Apa
keuntungan dan kerugian dari tulisan awal? halaman 753-754







17.15 Transaksi T dan U dijalankan dengan kontrol concurrency timestamp pemesanan.                 Jelaskaninformasi tertulis ke file log atas nama T dan U, yang memungkinkan untuk fakta bahwa U memilikitimestamp lambatnya T dan harus menunggu untuk melakukan setelah T. Mengapa penting bahwakomit entri dalam file log dipesan oleh cap waktu? Menggambarkan efek pemulihan
jika server crash (i) antara dua Komit; (Ii) setelah mereka berdua.

Apa keuntungan dan kerugian dari tulisan awal dengan timestamp ordering?
halaman 757

17.16 Transaksi T dan U di Latihan 17,15 dijalankan dengan kontrol konkurensi optimis
menggunakan validasi mundur dan restart setiap transaksi yang gagal. Jelaskan
informasi tertulis ke file log atas nama mereka. Mengapa penting bahwa komit
entri dalam file log dipesan oleh nomor transaksi? Bagaimana menulis set
berkomitmen transaksi diwakili dalam file log? halaman 753-754
17,17 Misalkan koordinator transaksi crash setelah itu telah mencatat niat
daftar entri tapi sebelum itu telah mencatat daftar peserta atau dikirim canCommit itu?
permintaan. Jelaskan bagaimana para peserta mengatasi situasi. Apa yang akan koordinator
dilakukan ketika pulih? Apakah akan lebih baik untuk merekam daftar peserta sebelum
Daftar niat masuk?