Replikasi

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

Replikasi adalah kunci untuk menyediakan ketersediaan tinggi dan toleransi kesalahan dalam didistribusikan sistem . ketersediaan tinggi adalah meningkatkan minat dengan kecenderungan menuju seluler komputasi dan operasi akibatnya terputus. toleransi kesalahan adalah kekal Perhatian untuk layanan yang disediakan dalam keselamatan kritis dan sistem penting lainnya .


Bagian pertama dari bab ini menganggap sistem yang menerapkan operasi tunggal pada waktu untuk koleksi benda-benda direplikasi. Ini dimulai dengan deskripsi arsitektur komponen dan model sistem untuk layanan yang mempekerjakan replikasi. Kami menggambarkan pelaksanaan manajemen keanggotaan kelompok sebagai bagian dari komunikasi kelompok ,

yang sangat penting untuk layanan toleran .

Bab ini kemudian menjelaskan pendekatan untuk mencapai toleransi kesalahan. Hal ini memperkenalkan kriteria kebenaran linearizability dan konsistensi sekuensial, maka mengeksplorasi dua pendekata: pasif ( primary - backup ) replikasi, di mana klien berkomunikasi dengan replika dibedakan: dan replikasi aktif, di mana klien berkomunikasi dengan multicast dengan semua replika .

Studi kasus dari tiga sistem untuk layanan sangat tersedia dianggap . Dalam gosip dan Bayou arsitektur, update disebarkan malas antara replika bersama data. Di Bayou, teknik transformasi operasional digunakan untuk menegakkan konsistensi. Coda adalah contoh dari layanan file sangat tersedia .     Bab ini berakhir dengan mempertimbangkan transaksi urutan operasi  kupon objek direplikasi. Ini mempertimbangkan arsitektur sistem transaksional direplikasi dan bagaimana sistem ini menangani kegagalan server dan partisi jaringan.

18.1 Pengenalan

Dalam bab ini, kita mempelajari replikasi data : pemeliharaan salinan data pada beberapa komputer. Replikasi adalah kunci untuk efektivitas sistem terdistribusi di yang dapat memberikan peningkatan kinerja, ketersediaan tinggi dan toleransi kesalahan. Replikasi digunakan secara luas. Sebagai contoh, caching sumber daya dari server web di browser dan server proxy web adalah bentuk replikasi, karena data yang diselenggarakan di cache dan pada server adalah replika dari satu sama lain. Layanan DNS penamaan, dijelaskan dalam Bab 13, mempertahankan salinan nama to atribut pemetaan untuk komputer dan mengandalkan pada untuk akses sehari- hari untuk layanan di Internet.     Replikasi adalah teknik untuk meningkatkan layanan. Motivasi untuk replikasi meliputi peningkatan kinerja: The caching data pada klien dan server adalah dengan sekarang akrab sebagai sarana peningkatan kinerja. Misalnya, Bab 2 menunjuk bahwa browser dan server proxy cache yang salinan sumber daya web untuk menghindari latency dari mengambil sumber daya dari server berasal. Furtherm bijih, data kadang-kadang direplikasi transparan antara beberapa server yang berasal sama domain. Beban kerja dibagi antara server dengan mengikat semua server IP alamat ke situs nama DNS, mengatakan www.aWebSite.org . Sebuah lookup DNS dari www.aWebSite.org hasil di salah satu alamat IP beberapa server yang akan dikembalikan,secara round- robin ( lihat Bagian 13.2.3 ). Lebih canggih load- balancing strategi diperlukan untuk layanan yang lebih kompleks berdasarkan data direplikasi antara ribuan server. Sebagai contoh, Dilleyetal. [ 2002 ] menggambarkan pendekatan untuk resolusi nama DNS yang diterapkan dalam jaringan distribusi konten Akamai .     Replikasi data berubah sepele: meningkatkan kinerja dengan sedikit biaya untuk sistem. Replikasi data berubah, seperti yang dari Web, incurs overhead dalam bentuk protokol yang dirancang untuk memastikan bahwa klien menerima up to date data ( lihat Bagian 2.3.1 ). Dengan demikian ada batas untuk efektivitas replikasi sebagai kinerja meningkatkan Teknik ment. Peningkatan ketersediaan Pengguna membutuhkan layanan menjadi sangat tersedia. Itu adalah proporsi waktu yang layanan dapat diakses dengan wajar waktu respons harus dekat dengan 100 %. Terlepas dari penundaan karena kontrol konkurensi pesimis konflik ( karena penguncian data) , faktor-faktor yang relevan dengan ketersediaan tinggi adalah:      • kegagalan server,

partisi jaringan dan operasi terputus ( pemutusan komunikasi
yang sering tidak direncanakan dan merupakan efek samping dari mobilitas pengguna ) .Untuk mengambil pertama ini, replikasi adalah teknik untuk secara otomatis menjaga ketersediaan data meskipun kegagalan Server. Jika data direplikasi di dua atau lebih Kegagalan independen server , maka software client mungkin dapat mengakses data pada Server alternatif harus defaul tserver gagal atau menjadi tidak terjangkau. Itu adalah persentase waktu selama layanan ini tersedia dapat ditingkatkan dengan replikasi server data. Jika masing-masing n server memiliki probabilitas p independen gagal atau menjadi tidak terjangkau, maka ketersediaan obyek disimpan pada masing-masing server adalah :

1 - probabilitas ( semua manajer gagal atau tidak terjangkau ) =1 p-n

Misalnya, jika ada kemungkinan 5 % dari setiap server individu gagal selama mengingat jangka waktu dan jika ada dua server , maka ketersediaan adalah 1-0,05= 1-0,0025= 99,75 % .Perbedaan penting antara sistem caching dan replikasi Server adalah bahwa cache tidak selalu memegang koleksi benda-benda seperti file dalam mereka keseluruhan. Jadi caching tidak selalu meningkatkan ketersediaan di tingkat aplikasi Pengguna dapat memiliki satu file yang dibutuhkan tetapi tidak lain .     partisi jaringan (lihat Bagian 15.1) dan operasi terputus adalah fakta kedua atau yang bertentangan ketersediaan tinggi. pengguna ponsel mungkin sengaja lepaskan komputer mereka atau menjadi tidak sengaja terputus dari nirkabel jaringan karena mereka bergerak di sekitar. Misalnya, pengguna di kereta dengan laptop mungkin memiliki tidak ada akses ke jaringan (jaringan nirkabel dapat terganggu, atau mereka mungkin memiliki ada kemampuan seperti). Agar dapat bekerja dalam keadaan ini disebut terputus kerja atau operasi terputus pengguna akan sering mempersiapkan diri dengan menyalin data berat bekas, seperti isi dari buku harian bersama, dari yang biasa mereka lingkungan ke laptop. Tapi sering ada trade-off ketersediaan selama seperti periode pemutusan: ketika pengguna berkonsultasi atau memperbarui buku harian itu, mereka berisiko membaca data bahwa orang lain telah diubah sementara itu. Misalnya, mereka mungkin membuat janji di slot yang sejak itu telah diduduki. terputus kerja hanya layak jika pengguna (atau aplikasi, atas nama pengguna) dapat mengatasi basidata dan kemudian dapat menyelesaikan setiap konflik yang muncul.Toleransi kesalahan : Data Sangat tersedia belum tentu data yang sepenuhnya benar . mungkin kedaluwarsa, misalnya: atau dua pengguna di sisi berlawanan dari partisi jaringan mungkin membuat update bahwa konflik dan perlu diselesaikan. Sebuah layanan fault-tolerant, oleh Sebaliknya, selalu menjamin perilaku sepenuhnya benar meskipun sejumlah tertentu dan jenis kesalahan. kebenaran yang menyangkut kesegaran data yang diberikan ke klien dan efek dari operasi klien pada data. Kebenaran kadang-kadang juga menyangkut ketepatan waktu respon layanan ini seperti, misalnya, dalam kasus ini dari sistem kontrol lalu lintas udara, di mana data yang benar yang dibutuhkan pada rentang waktu singkat Teknik dasar yang sama digunakan untuk berhasil tinggi kemampuan yang mereplikasi data yang dan fungsi antara komputer juga berlaku untuk mencapai kesalahan toleransi. Jika sampai dengan f f + 1 server kecelakaan, maka pada prinsipnya di least satu masih menyediakan layanan. Dan jika sampai dengan server f dapat menunjukkan kegagalan Bizantium, kemudian diPrinsip sekelompok 2f + 1 server dapat memberikan layanan yang benar, dengan memiliki yang benar server mengalahkan dalam pemilihan server yang gagal ( yang dapat menyediakan nilai-nilai palsu ). tapi kesalahan toleransi halus dari deskripsi sederhana ini membuatnya tampak . Sistem harus mengatur koordinasi dari komponennya tepat untuk mempertahankan kebenaran yang jaminan dalam menghadapi kegagalan, yang dapat terjadi sewaktu-waktu .     Persyaratan umum ketika data direplikasi adalah untuk transparansi replikasi Bahwa adalah, klien sebaiknya tidak harus menyadari bahwa beberapa salinan fisik data ada. Sejauh klien yang bersangkutan, data yang diatur sebagai objek logis individu dan mereka mengidentifikasi hanya satu item dalam setiap kasus ketika mereka meminta operasi untuk menjadi dilakukan. Selanjutnya, klien mengharapkan operasi untuk kembali hanya satu set nilai-nilai. Inis meskipun fakta bahwa operasi dapat dilakukan pada lebih dari satu salinan fisik di konser Persyaratan umum lainnya untuk data direplikasi salah satu yang dapat bervariasi dalam kekuatan antara aplikasi adalah bahwa konsistensi. Ini kekhawatiran apakah operasi dilakukan pada koleksi benda-benda direplikasi menghasilkan hasil yang memenuhi spesifikasi kebenaran bagi mereka objek Kami melihat pada contoh dari buku harian yang selama data operasi terputus mungkin diizinkan untuk menjadi tidak konsisten, setidaknya untuk sementara. Tapi ketika klien tetap Koneksi sering tidak dapat diterima untuk klien yang berbeda ( menggunakan salinan fisik yang berbeda data ) untuk mendapatkan hasil yang tidak konsisten ketika mereka membuat permintaan mempengaruhi sama benda logis . Artinya, itu tidak bisa diterima jika hasil mematahkan aplikasi.     Kami sekarang memeriksa lebih detail masalah desain muncul ketika kita replikasi data untuk mencapai sangat  layanan yang tersedia dan toleran. Kami juga memeriksa beberapa standar solusi dan teknik untuk menangani isu-isu tersebut. Pertama, Bagian 18,2-18,4 penutup kasus di mana klien membuat doa individual pada data bersama. bagian 18.2 menyajikan arsitektur umum untuk mengelola data direplikasi dan memperkenalkan kelompok komunikasi sebagai alat penting. komunikasi kelompok ini sangat berguna untuk mencapai toleransi kesalahan, yang merupakan subjek dari Bagian 18.3. Bagian 18.4 menggambarkan teknik untuk ketersediaan tinggi, termasuk operasi terputus. Ini termasuk kasus studi arsitektur gosip , Bayou dan sistem file Coda. bagian 18.5 meneliti bagaimana mendukung transaksi data direplikasi. Sebagai Bab 16 dan 17 menjelaskan, transaksi terdiri dari urutan operasi, bukan tunggal operasi .18.2. Model Sistem dan Peran Komunikasi Kelompok

Data dalam sistem kami terdiri dari koleksi item yang akan kita sebut benda. Sebuah ' Objek ' bisa menjadi sebuah file, misalnya, atau benda Java. Tapi setiap objek logis seperti ini dilaksanakan oleh kumpulan salinan fisik disebut replika . Replika yang fisik benda , masing-masing disimpan pada satu komputer, dengan data dan perilaku yang terkait dengan beberapa tingkat konsistensi dengan operasi sistem. The replika dari objek tertentu yang tidak harus sama , setidaknya tidak pada setiap titik waktu tertentu. Beberapa replika mungkin memiliki update menerima bahwa orang lain belum menerima .

Pada bagian ini, kami menyediakan model sistem umum untuk mengelola replika dan kemudian menggambarkan peran comm kelompok sistem unication dalam mencapai toleransi kesalahan melalui replikasi, menyoroti pentingnya komunikasi kelompok pandangan sinkron .

18.2.1 System Model

Kami menganggap sistem asynchronous dimana proses mungkin gagal hanya dengan menerjang. Kami asumsi default adalah bahwa partisi jaringan mungkin tidak terjadi, tapi kami akan kadang-kadang mempertimbangkan apa yang terjadi jika mereka terjadi . partisi jaringan membuat lebih sulit untuk membangun detektor kegagalan, yang kita gunakan untuk mencapai handal dan benar-benar memerintahkan multicast .









Gambar 18.1 Sebuah model arsitektur dasar untuk pengelolaan data replikasi

Demi umum, kami menjelaskan komponen arsitektur dengan peran mereka dan tidak bermaksud mengatakan bahwa mereka selalu dilaksanakan oleh proses yang berbeda ( atau perangkat keras). Model ini melibatkan replika dipegang oleh manajer replika yang berbeda ( lihat Gambar 18.1 ),  yang merupakan komponen yang berisi replika pada komputer yang diberikan dan melakukan operasi pada mereka secara langsung. Model umum ini dapat diterapkan dalam client-server lingkungan, dalam hal ini manajer replika adalah server . Kami akan kadang-kadang hanya menyebutnya server sebagai gantinya. Sama itu dapat diterapkan untuk aplikasi dan aplikasi proses bisa dalam kasus bertindak sebagai klien dan manajer replika . Sebagai contoh, laptop pengguna di kereta api mungkin berisi aplikasi yang bertindak sebagai manajer replika karena mereka buku harian.

Kami akan selalu mengharuskan seorang manajer replika berlaku operasi untuk replika nya recoverably. Hal ini memungkinkan kita untuk menganggap bahwa operasi pada manajer replika tidak meninggalkan hasil yang tidak konsisten jika gagal bagian jalan melalui. Kita kadang-kadang mengharuskan setiap replika manajer menjadi mesin negara [Lamport 1978, Schneider 1990]. Seperti manajer replikaberlaku operasi untuk replika nya atom (tidak terpisah), sehingga pelaksanaannya adalah setara dengan melakukan operasi di beberapa urutan yang ketat. Selain itu, keadaan yang replika adalah fungsi deterministik negara awal mereka dan urutan operasi yang berlaku untuk mereka. rangsangan lainnya, seperti membaca pada jam atau terpasang sensor, tidak memiliki bantalan pada nilai-nilai negara tersebut. Tanpa asumsi ini, konsistensi jaminan antara manajer replika yang menerima operasi update secara independen bisa tidak dilakukan. Sistem ini hanya dapat menentukan operasi untuk menerapkan sama sekali replika manajer dan dalam rangka apa-tidak dapat mereproduksi efek non-deterministik. Itu asumsi menyiratkan bahwa itu tidak mungkin, tergantung threading arsitektur, untuk server menjadi multi-threaded.     Sering kali setiap manajer replika mempertahankan replika setiap keberatan, dan kita asumsikan ini jadi kecuali kita menyatakan sebaliknya. Namun, replika objek yang berbeda mungkin dikelola oleh set yang berbeda dari manajer replika. Misalnya, satu objek mungkin dibutuhkan terutama oleh klien pada satu jaringan dan lain oleh klien pada jaringan lain. Ada sedikit yang bisa diperoleh dengan mereplikasi mereka di manajer di jaringan lain.     Himpunan manajer replika mungkin statis atau dinamis. Dalam sistem yang dinamis, baru manajer replika mungkin muncul (Misalnya, jika kedua salinan sekretaris buku harian ke mereka laptop) ini tidak diperbolehkan dalam system statis. Dalam sistem yang dinamis, manajer replika mungkin macet, dan mereka kemudian dianggap telah meninggalkan sistem (meskipun mereka mungkin diganti). Dalam sistem statis, manajer replika tidak crash (menerjang menyiratkan tidak pernah mengeksekusi langkah lain), tetapi mereka mungkin berhenti beroperasi untuk waktu yang tidak terbatas. Kami kembali dengan isu kegagalan dalam Bagian 18.4.2 .     Model umum manajemen replika ditunjukkan pada Gambar 18.1. Koleksi manajer replika menyediakan layanan kepada klien. Klien melihat layanan yang memberikan mereka akses ke objek ( misalnya, buku harian atau rekening bank ) yang sebenarnya adalah direplikasi di manajer. Setiap klien meminta serangkaian operasi doa pada satu atau lebih objek. Operasi mungkin melibatkan kombinasi dari membaca benda dan update ke objek. operasi yang diminta yang melibatkan tidak ada update disebut dibaca permintaan diminta operasi bahwa memperbarui obyek disebut pembaruan Permintaan (ini Mei juga melibatkan membaca ) .     permintaan setiap klien yang menangani pertama oleh komponen yang disebut front end. Peran dari ujung depan adalah untuk berkomunikasi melalui pesan lewat dengan satu atau lebih replika manajer, dari pada memaksa klien untuk melakukan ini sendiri secara eksplisit. Ini adalah kendaraan untuk membuat replikasi transparan. Sebuah front end dapat diimplementasikan di alamat klien ruang, atau mungkin menjadi proses yang terpisah. Secara umum , lima fase yang terlibat dalam kinerja satu permintaan pada objek direplikasi [ Wiesmannetal . 2000]. Tindakan dalam setiap fase berbeda-beda menurut dengan jenis sistem, seperti yang akan menjadi jelas dalam dua bagian berikutnya. sebuah layanan yang mendukung operasi terputus berperilaku berbeda dari satu yang menyediakan layanan toleran. Fase adalah sebagai berikut :     Permintaan : Ujung depan mengeluarkan permintaan ke satu atau lebih manajer replika :

- either ujung depan berkomunikasi dengan manajer replika tunggal, yang pada gilirannya berkomunikasi dengan manajer replika lainnya ;

- Atau depan mengakhiri multicast permintaan untuk manajer replika .

Koordinasi : Manajer replika koordinasi dalam persiapan untuk mengeksekusi meminta secara konsisten. Mereka setuju, jika diperlukan pada tahap ini, apakah permintaan tersebut untuk diterapkan ( mungkin tidak diterapkan sama sekali jika kegagalan terjadi pada tahap ini ).Mereka juga memutuskan urutan permintaan ini relatif terhadap orang lain. Semua jenis pemesanan ditetapkan untuk multicast dalam Bagian 15.4.3 juga berlaku untuk meminta penanganan dan kita mendefinisikan mereka perintah lagi untuk konteks ini :     FIFO memesan: Jika sebuah front masalah end permintaan r dan kemudian meminta r, setiap yang benar Manajer replika yang menanganir menangani r sebelum.Kausal pemesanan: Jika isu permintaan r terjadi sebelum isu permintaan r, maka setiap   yang benar replika manajer yang menangani r menangani r sebelum .Jumlah pemesanan: Jika seorang manajer replika yang benar menangani r sebelum permintaan r, maka setiap Manajer replika yang benar yang menangani r menangani r sebelumAplikasi yang paling membutuhkan FIFO pemesanan. Kami membahas persyaratan untuk kausal dan Jumlah pemesanan dan ordering shybrid yang baik FIFO dan total, atau keduanya kausal dan jumlah di dua bagian berikutnya .Eksekusi: Manajer replika melaksanakan permintaan mungkin sepuluh tatively: yaitu, di sedemikian rupa sehingga mereka dapat membatalkan efek nanti .Kesepakatan: Manajer replika mencapai konsensus pada efek dari permintaan jika apapun yang akan dilakukan. Misalnya dalam sistem transaksional replika manajer mungkin secara kolektif setuju untuk membatalkan atau melakukan transaksi pada tahap ini .System berbeda dapat membuat pilihan yang berbeda tentang pemesanan fase, serta sebagai isinya. Misalnya dalam sistem yang mendukung operasi terputus, itu adalahpenting untuk memberikan klien ( aplikasi pada laptop pengguna, mengatakan ) sebagai awal respons mungkin. Pengguna tidak ingin menunggu sampai manajer replika pada laptop dan replika manager kembali kantor dapat berkoordinasi. Sebaliknya, dalam fault-tolerant sistem klien tidak diberikan respon sampai akhir, ketika kebenaran Hasil dapat dijamin.  18.2.2 Peran komunikasi kelompok

Bab 6 memperkenalkan konsep komunikasi kelompok dan Bagian 15.4 diperluas pada diskusi ini dengan menutupi algoritma untuk keandalan dan pemesanan pesan pengiriman sistem komunikasi kelompok. Dalam bab ini, kita melihat peran kelompok dalam mengelola data direplikasi. Pembahasan dalam Bagian 15.4 mengambil keanggotaan kelompok harus statis didefinisikan, meskipun anggota kelompok mungkin macet. Dalam replikasi, dan memang dalam banyak situasi praktis lainnya, ada persyaratan yang kuat untuk dinamis keanggotaan , di mana proses bergabung dan meninggalkan kelompok sebagai sistem mengeksekusi. Di sebuah layanan yang direplikasi data, misalnya, pengguna dapat menambah atau menarik sebuah replika manager, atau manajer replika mungkin macet dan dengan demikian harus ditarik dari operasi sistem. manajemen keanggotaan kelompok, yang diperkenalkan dalam Bagian 6.2.2 , oleh karena itu sangat penting dalam konteks ini .

Sistem yang dapat beradaptasi sebagai proses bergabung, meninggalkan dan kecelakaan sistem fault-tolerant, khususnya membutuhkan fitur yang lebih canggih deteksi kegagalan dan pemberitahuan perubahan keanggotaan. Sebuah layanan keanggotaan kelompok penuh memelihara pandangan kelompok, yang adalah daftar anggota kelompok saat ini, diidentifikasi oleh pengidentifikasi proses unik mereka. Itu daftar memerintahkan misalnya sesuai dengan urutan di mana para anggota bergabung dengan kelompok. Sebuah baru group tampilan yang dihasilkan setiap kali proses ditambahkan atau dikecualikan Sistem yang dapat beradaptasi sebagai proses bergabung, meninggalkan dan kecelakaan - sistem fault-tolerant, khususnya - membutuhkan fitur yang lebih canggih deteksi kegagalan dan pemberitahuan perubahan keanggotaan .

Sebuah layanan keanggotaan kelompok penuh memelihara pandangan kelompok, yang adalah daftar anggota kelompok saat ini, diidentifikasi oleh pengidentifikasi proses unik mereka. Itu daftar memerintahkan, misalnya sesuai dengan urutan di mana para anggota bergabung dengan kelompok. Sebuah baru group tampilan yang dihasilkan setiap kali proses ditambahkan atau dikecualikan Hal ini penting untuk memahami bahwa layanan keanggotaan kelompok dapat mengecualikan memproses dari kelompok karena Diduga, meskipun mungkin tidak jatuh, sebuah kegagalan komunikasi mungkin telah membuat proses terjangkau, sementara itu terus mengeksekusi normal. Sebuah layanan keanggotaan selalu bebas untuk mengecualikan proses tersebut. Itu efek pengecualian adalah bahwa tidak ada pesan akan dikirim ke proses yang selanjutnya .

Selain itu, dalam kasus kelompok tertutup, jika proses yang menjadi terhubung lagi, setiap pesan itu berusaha mengirim tidak akan dikirimkan kepada anggota kelompok. proses itu harus bergabung kembali dengan group (sebagai reinkarnasi dari dirinya sendiri, dengan identifier baru) atau batalkan operasinya .

Kecurigaan palsu dari suatu proses dan mengesampingkan akibat dari proses dari kelompok dapat mengurangi efektivitas kelompok. Kelompok ini memiliki untuk mengelola tanpa kehandalan tambahan atau kinerja yang proses ditarik berpotensi memiliki disediakan. Tantangan desain, selain merancang detektor kegagalan untuk seakurat mungkin, adalah untuk memastikan bahwa sistem berdasarkan komunikasi kelompok tidak berperilaku salah jika suatu proses palsu dicurigai.     Satu pertimbangan penting adalah bagaimana layanan manajemen kelompok memperlakukan jaringan partitions. Pemutusan atau kegagalan komponen seperti router dalam jaringan dapat membagi kelompok proses menjadi dua atau lebih sub kelompok, dengan komunikasi antara sub-kelompok mustahil. jasa manajemen kelompok berbeda dalam apakah mereka adalah primary partition atau partitionable .Lihat pengiriman • Pertimbangkan tugas programmer menulis sebuah aplikasi yang berjalan di setiap proses dalam kelompok dan yang harus menghadapi anggota baru dan hilang .programmer

perlu tahu bahwa sistem memperlakukan setiap anggota dengan cara yang konsisten ketika perubahan keanggotaan. Ini akan menjadi canggung jika programmer harus query keadaan semua anggota lain dan mencapai keputusan global yang setiap kali perubahan keanggotaan terjadi, bukannya mampu membuat keputusan lokal tentang bagaimana menanggapi perubahan. kehidupan programmer dibuat lebih sulit atau lebih mudah sesuai dengan jaminan yang berlaku ketika sistem memberikan pandangan kepada anggota kelompok.

Kami berbicara tentang anggota delivering lihat ketika perubahan keanggotaan terjadi dan aplikasi diberitahu tentang keanggotaan baru, sama seperti kita berbicara tentang sebuah proses menyampaikan pesan multicast. Seperti dengan pengiriman multicast, memberikan pandangan berbeda menerima pandangan. Kelompok protokol keanggotaan terus diusulkan pandangan tentang rintangan yang antrian sampai semua masih ada anggota setuju Untuk pengiriman mereka. Yang pertama dari persyaratan ini berjalan beberapa cara untuk memberikan programmer konsistensi jaminan dengan memastikan bahwa pandangan perubahan selalu terjadi dalam urutan yang sama di berbagai proses. Persyaratan kedua adalah cek kewarasan. Para penjaga ketiga terhadap sepele solusi. Misalnya, layanan keanggotaan yang memberitahu setiap proses, terlepas dari yang konektivitas, bahwa itu adalah dalam kelompok dengan sendirinya tidak menarik. The non kesia Kondisi menyatakan bahwa jika dua proses yang masing-masing telah bergabung sama kelompok bisa akhirnya berkomunikasi tanpa batas, anggota kemudian mereka masing-masing harus dianggap itu kelompok yang sama. Demikian pula, hal itu mewajibkan, ketika partisi terjadi, layanan keanggotaan akhirnya harus mencerminkan partisi. Kondisi ini tidak menyatakan bagaimana kelompok layanan keanggotaan harus bersikap dalam kasus bermasalah konektivitas berselang.Lihat sinkron komunikasi kelompok • Sebuah komunikasi kelompok pandangan  sinkron Sistem membuat jaminan tambahan untuk yang di atas tentang pemesanan pengiriman pandang pemberitahuan sehubungan dengan pengiriman pesan multicast. Lihat sinkron komunikasi meluas semantik multicast handal yang kami jelaskan di Bab 15 untuk memperhitungkan perubahan pandangan kelompok. Demi kesederhanaan, kita membatasi kami diskusi untuk kasus di mana partisi tidak mungkin terjadi . Jaminan yang diberikan oleh viewsynchronous kelompok komunikasi adalah sebagai berikut: pertimbangkan grup dengan tiga proses, p , q dan r ( lihat Gambar 18.2 ). Misalkan p mengirimkanpesan m sementara dalam pandangan ( p , q , r ) tapi itu p crash segera setelah mengirim m,  sedangkan q danr benar. Salah satu kemungkinan adalah bahwa p crash sebelum m telah mencapai proses lainnya. Dalam hal ini, q dan r masing-masing memberikan pandangan baru ( q , r ), tapi tidak pernah memberikan m ( Gambar 18.2A ). Kemungkinan lain adalah bahwa m telah mencapai setidaknya salah satu dari dua yang masih hidup proses ketika p crash . Maka q dan r kedua memberikan m pertama dan kemudian pandangan ( q , r ) ( Gambar 18.2b ) . Hal ini tidak diperbolehkan untuk q dan r untuk memberikan pertama pandangan ( q , r ) dan kemudian( Gambar 18.2c ) , sejak itu mereka akan memberikan message dari sebuah proses yang mereka miliki.











Gambar 18.2 Lihat sinkron komunikasi kelompok





diberitahu telah gagal: juga tidak bisa dua menyampaikan pesan dan pandangan baru dalam perintah berlawanan ( Gambar 18.2d ) .     Dalam sistem tampilan sinkron, pengiriman dari Pandangan baru menarik garis konseptual seluruh sistem dan setiap pesan yang disampaikan sama sekali secara konsisten disampaikan pada satu sisi atau yang lain dari garis itu. Hal ini memungkinkan programmer untuk menggambar berguna kesimpulan tentang set pesan bahwa proses yang benar lainnya telah disampaikan saat itu memberikan pandangan baru, hanya berdasarkan pemesanan lokal pengiriman pesan dan melihat peristiwa pengiriman. Sebuah ilustrasi dari kegunaan komunikasi pandangan sinkron adalah bagaimana dapat digunakan untuk mencapai transfer negara - transfer dari negara bekerja dari arus anggota dari kelompok proses untuk anggota baru kelompok. Misalnya, jika proses adalah manajer replika yang masing-masing memegang keadaan buku harian, maka manajer replika yang bergabung kelompok untuk buku harian yang perlu untuk memperoleh negara diary saat ketika bergabung. Tetapi diary mungkin diperbarui secara bersamaan sementara negara sedang ditangkap. Adalah penting bahwa manajer replika tidak lewatkan setiap pesan update yang tidak tercermin dalam negara itu memperoleh dan bahwa itu tidak mengajukan permohonan kembali pesan update yang sudah tercermin dalam negara ( kecuali orang-orang pembaruan yang idempoten ) .     Untuk mencapai transfer negara ini, kita bisa komunikasi sepandangan  sinkron dalam skema sederhana seperti berikut ini. Setelah pengiriman pandangan pertama yang berisi baru proses, beberapa proses yang berbeda dari kalangan yang sudah ada anggota mengatakan, yang tertua Menangkap keadaan, mengirimkannya satu ke satu ke anggota baru dan menunda pelaksanaannya. Semua proses yang sudah ada lainnya menangguhkan eksekusi mereka. Perhatikan bahwa justru himpunan update tercermin dalam negara ini telah, menurut definisi, telah diterapkan pada semua anggota lainnya.Diskusi • Gagasan komunikasi kelompok pandangan sinkron yang kita miliki disajikan adalah formulasi dari paradigma komunikasi hampir sinkron awalnya dikembangkan dalam sistem ISIS [ Birman 1993, Birmanetal. 1991, Birman dan Joseph 1987b ]. Schiper dan Sandoz [ 1993] menggambarkan protokol untuk mencapai viewsynchronous (atau seperti mereka menyebutnya, lihat atom ) komunikasi. Catatan bahwa kelompok keanggotaan layanan Raih konsensus, tapi memang tanpa mencemoohkan itu ketidak mungkinan Hasil Fischer etal. [ 1985].Sebagaimana kita bahas pada Bagian 15.5.4, sistem dapat menghindari hasil bahwa dengan menggunakan detektor kegagalan yang tepat .     Sistem V [ Cheriton dan Zwaenepoel 1985] adalah sistem pertama yang memasukkan dukungan untuk kelompok proses. Setelah ISIS , kelompok proses dengan beberapa jenis kelompok layanan keanggotaan dikembangkan di beberapa sistem lain , termasuk Horus [ van Renesse et al. 1996 ], Totem [ Moser et al . 1996 ] dan Transis [ Dolev dan Malki 1996 ] Variasi pada tampilan sinkron telah diusulkan untuk kelompok partitionable layanan keanggotaan, termasuk dukungan untuk aplikasi partisi sadar [ Babaoglu et Al. 1998] dan diperpanjang sinkroni maya [ Moser et al . 1994] Akhirnya , Cristian [ 1991 ] membahas layanan keanggotaan grup untuk sinkron sistem terdistribusi  18.3 jasa kesalahan - toleran     Pada bagian ini, kita meneliti bagaimana memberikan layanan yang benar meskipun sampai dengan proses f kegagalan, dengan mereplikasi data dan fungsi di manajer replika. Demi kesederhanaan, kita mengasumsikan bahwa komunikasi tetap handal dan bahwa tidak ada partisi terjadi.     Setiap manajer replika diasumsikan berperilaku sesuai dengan spesifikasi dari semantik dari objek yang mengelola, ketika mereka tidak jatuh. Misalnya, spesifikasi rekening bank akan mencakup jaminan bahwa dana ditransfer antar rekening bank tidak pernah bisa hilang, dan bahwa hanya deposito dan penarikan mempengaruhi keseimbangan rekening tertentu .     Secara intuitif , layanan berbasis pada replikasi adalah benar jika itu terus merespon meskipun kegagalan dan jika klien tidak dapat membedakan antara layanan yang mereka peroleh dari sebuah implementasi dengan data direplikasi dan satu yang disediakan oleh replika yang benar tunggal manajer. Perawatan yang dibutuhkan dalam memenuhi kriteria tersebut . Jika tindakan pencegahan tidak dilakukan, maka



Eksekusi ini tidak sesuai spesifikasi yang masuk akal untuk perilaku bank account : klien 2 harus membaca saldo $ 1 untuk x, mengingat bahwa itu baca keseimbangan dari $ 2 untuk y, karena keseimbangan y itu diperbarui setelah itu dari x . Perilaku anomali kasus direplikasi tidak bisa terjadi jika rekening bank telah diimplementasikan oleh satu server . Kita dapat membangun sistem yang mengelola objek replikasi tanpa perilaku anomali yang dihasilkan oleh protokol naif dalam contoh kita. Pertama, kita perlu memahami apa yang dianggap perilaku sebagai yang benar untuk sistem direplikasi.     Linearizability dan konsistensi sekuensial • Ada berbagai kriteria kebenaran untuk objek direplikasi. Sistem yang paling ketat yang benar adalah linearizable, dan properti ini disebut linearizability. Untuk memahami linearizability, mempertimbangkan direplikasi pelaksanaan pelayanan dengan dua klien. Biarkan urutan membaca dan memperbarui operasi bahwa klien saya melakukan di beberapa eksekusi menjadi Hai i 0. Setiap operasi o di ini urutan ditentukan oleh jenis operasi dan argumen dan nilai-nilai kembali karena mereka terjadi pada saat runtime . Kami berasumsi bahwa setiap operasi sinkron. Artinya, klien menunggu satu operasi untuk menyelesaikan sebelum meminta berikutnya .     Sebuah server tunggal mengelola satu salinan dari objek akan cerita bersambung operations dari klien. Dalam kasus eksekusi dengan hanya klien 1 dan client 2 , iniinterleaving operasi bisa Hai, Mengatakan. kita mendefinisikan Kriteria kebenaran untuk objek direplikasi dengan mengacu Virtua sebuah l interleaving dari operasi klien, yang tidak selalu secara fisik terjadi setiap replika tertentu Manajer tapi yang menetapkan kebenaran eksekusi .     Sebuah layanan shared object direplikasi dikatakan linearizable jika untuk eksekusi apapun ada beberapa interleaving dari serangkaian operasi yang dikeluarkan oleh semua klien yang memenuhi berikut dua kriteria :• Urutan interleaved operasi memenuhi spesifikasi dari (single ) salinan yang benar dari objek .

Urutan operasi di interleaving konsisten dengan urutan program yang setiap klien mengksekusi mereka .
Perhatikan bahwa waktu mutlak tidak muncul dalam definisi ini . Juga tidak ada total pesanan lainnya pada semua operasi. Satu-satunya gagasan pemesanan yang relevan adalah urutan kejadian di setiap klien yang terpisah urutan Program. Interleaving operasi dapat mengocok urutan operasi dari satu set klien dalam urutan apapun, asalkan agar setiap klien tidak dilanggar dan hasil dari setiap operasi konsisten, dalam hal obyek spesifikasi, dengan operasi yang mendahuluinya  Hal ini mirip dengan menyeret bersama-sama beberapa bungkus kartu sehingga mereka bercampur sedemikian rupa untuk melestarikan urutan asli dari masing-masing paket.   Setiap layanan linearizable juga berurutan konsisten , karena pesanan real-time mencerminkan rangka Program masing-masing klien . Kebalikannya tidak tahan . Eksekusi Contoh untuk   yang berurutan konsisten tapi tidak linearizable berikut :       Eksekusi ini mungkin di bawah strategi replikasi naif bahkan jika tak satu pun dari komputer A atau B gagal tetapi jika update dari x bahwa klien 1 dibuat di B belum mencapai A ketika klien 2 membacanya. Kriteria real-time untuk linearizability tidak puas, karena get Balance x 1 ; tapi berikut interleaving memenuhi kedua kriteria untuk konsistensi berurutan :

Get Balance sebuah x 0 terjadi paling lambat setBalance By 0, Get Balance sebuah x 0 , setBalanceB x 1 , setBalance y 2.

Lamport dikandung dari kedua konsistensi berurutan [1979] dan linearizability sebuah [1986] dalam kaitannya dengan register memori bersama ( meskipun ia menggunakan istilah ' atomicity 'bukannya ' linearizability ' ). Herlihy dan Wing [1990] umum ide untuk menutupi benda bersama sewenang-wenang. Sistem terdistribusi memori bersama juga memiliki lemah model konsistensi, seperti yang dibahas di situs pendamping untuk buku.

18.3.1 Pasif ( primary - backup ) replikasi     Dalam model pasif atau primer - backup replikasi untuk toleransi kesalahan ( Gambar 18.3 )

ada pada satu waktu seorang manajer utama replika dan satu atau lebih sekunder reputasi manajer lica 'backup' atau 'budak'.  Dalam bentuk murni dari model, ujung depan berkomunikasi hanya dengan manajer replika utama untuk mendapatkan layanan. Primer Manajer replika mengeksekusi operasi dan mengirimkan salinan data diperbarui ke backup. Jika primer gagal, salah satu backup dipromosikan untuk bertindak sebagai primer.   Urutan kejadian ketika seorang klien meminta operasi  yang akan dilakukan adalah sebagai berikut :

request : Ujung depan mengeluarkan permintaan, yang berisi pengenal unik, dengan primar
Manajer replika y.

Coordination : primer mengambil setiap permintaan atom, dalam urutan di mana menerimanya. Ia memeriksa pengenal unik, dalam kasus itu telah dieksekusi permintaan, dan jika demikian itu hanya akan mengirim ulang respon .
Eksekusi : primer mengeksekusi permintaan dan menyimpan respon .
Persetujuan : Jika permintaan tersebut update, maka primer mengirimkan negara diperbarui, respon dan identifier unik untuk semua backup . Backup mengirim pengakuan.
Respon : The merespon utama ke ujung depan , yang tangan respon kembali untuk klien










Gambar 18.3 Pasif (primer - backup ) model untuk toleransi kesalahan







Sistem ini jelas mengimplementasikan linearizability jika primer benar, karena urutan utama semua operasi pada objek bersama Jika primer gagal, maka sistem mempertahankan linearizability jika cadangan tunggal menjadi dasar yang baru dan jika konfigurasi sistem baru mengambil alih persis di mana yang terakhir tinggalkanItu kalau :   • primer digantikan oleh cadangan yang unik ( jika dua klien mulai menggunakan dua backup maka sistem dapat melakukan salah).

Manajer replika yang bertahan setuju pada yang operasi telah dilakukan pada titik ketika penggantian utama lebih .
Kedua persyaratan ini terpenuhi jika manajer replika (primer dan backup) yang diselenggarakan sebagai sebuah kelompok dan jika primer menggunakan komunikasi kelompok pandangan-sinkron untuk mengirim update ke backup. Pertama di atas dua persyaratan ini kemudian dengan mudah puas. Ketika crash utama, sistem komunikasi akhirnya memberikan tampilan baru untuk backup yang masih hidup, salah satu yang mengecualikan utama yang lama . cadangan yang menggantikan primer dapat dipilih oleh fungsi pandangan itu. Sebagai contoh, backup dapat memilih anggota pertama dalam pandangan sebagai pengganti. cadangan yang bisa mendaftarkan diri sebagai primer dengan layanan nama yang klien berkonsultasi ketika menduga bahwa primer telah gagal ( atau ketika mereka membutuhkan layanan di tempat pertama ).

Persyaratan kedua juga puas, dengan properti pemesanan view  synchron dan menggunakan pengidentifikasi disimpan untuk mendeteksi permintaan ulang. The view synchronous semantik Menjamin yang baik semua Backup atau tak satupun dari mereka Akan menyampaikan apa saja diberikan pembaruan sebelum memberikan pandangan baru. Jadi dasar yang baru dan hidup backup semua sepakat tentang apakah pembaruan klien tertentu memiliki atau belum diproses.       Pertimbangkan front end yang memiliki tidak menerima tanggapan. The mentransmisikan kembali front end permintaan ke mana cadangan mengambil alih sebagai primer. primer mungkin memiliki jatuh pada setiap saat selama operasi. Jika jatuh sebelum tahap perjanjian ( 4 ), maka manajer replika yang masih hidup tidak dapat memproses permintaan. Jika jatuh selama setuju panggung, maka mereka mungkin telah diproses permintaan. Jika jatuh setelah tahap itu, maka mereka telah pasti diproses itu. Tapi dasar yang baru tidak harus tahu apa panggung utama tua itu di ketika jatuh. Ketika menerima permintaan, hasil dari tahap 2 di atas.  Oleh pandangan-sinkroni, tidak ada konsultasi dengan backup adalah diperlukan, karena mereka semua telah diproses set yang sama pesan .

Diskusi replikasi pasif • Model utama backup dapat digunakan bahkan di mana manajer replika utama berperilaku dalam cara yang non  deterministik, misalnya karena multi berulir operasi. Sejak utama berkomunikasi negara diperbarui dari operasi daripada spesifikasi operasi sendiri, backup merendahkan diri merekam negara ditentukan oleh tindakan utama sendirian .

replikasi pasif memiliki kelemahan menyediakan relatif large overhead. Lihat sinkron komunikasi memerlukan beberapa putaran komunikasi permulticast, dan jika primer gagal maka lebih banyak lagi latency dikeluarkan sementara kelompok sistem komunikasi setuju atas dan memberikan tampilan baru .     Dalam variasi model yang disajikan di sini, klien mungkin dapat mengirimkan read permintaan untuk backup, sehingga pembongkaran bekerja dari primer. Jaminan linearizability dengan demikian hilang, tapi klien menerima layanan yang konsisten secara berurutan .    replikasi pasif digunakan dalam Harp direplikasi sistem file [ Liskov et al. 1991 ]. The Sun Network Information Service ( NIS, sebelumnya Yellow Pages ) menggunakan pasif replikasi untuk mencapai ketersediaan tinggi dan kinerja yang baik,  meskipun dengan lemah jaminan dari consistenc berurutan y. Jaminan konsistensi lemah masih memuaskan untuk berbagai tujuan, seperti menyimpan beberapa jenis sistem administrasi catatan. Data direplikasi diperbarui pada server master dan disebarkan dari sana ke server slave menggunakan satu ke satu (bukan kelompok ) komunikasi. klien mungkin berkomunikasi dengan baik master atau slave server untuk mengambil informasi. Dalam NIS, Namun, klien tidak dapat meminta pembaruan : update yang dibuat ke file master .18.3.2 replikasi aktifDalam model aktif replikasi untuk toleransi kesalahan ( lihat Gambar 18.4 ), replika manajer mesin negara yang memainkan peran yang setara dan diselenggarakan sebagai sebuah kelompok.

Depan berakhir multicast permintaan mereka kepada sekelompok manajer replika dan semua replika manajer memproses permintaan secara mandiri tetapi identik dan balasan. Jika replika apapun Manajer crash, kebutuhan ini tidak berdampak pada kinerja pelayanan, karena manajer replika yang tersisa terus merespon dengan cara biasa. Kita akan melihat bahwa replikasi aktif dapat mentolerir kegagalan Bizantium, karena ujung depan dapat mengumpulkan dan membandingkan balasan yang diterimanya .

Di bawah replikasi aktif, urutan kejadian ketika seorang klien meminta sebuah operasi yang akan dilakukan adalah sebagai berikut :1. Permintaan : Ujung depan menempel pengenal unik untuk permintaan dan multicast itu untuk kelompok manajer replika, menggunakan benar-benar memerintahkan, multicast handal primitif. Ujung depan diasumsikan gagal oleh menerjang pada terburuk. Itu tidak mengeluarkan next yang permintaan sampai telah menerima tanggapan .

Koordinasi : Sistem komunikasi kelompok memberikan permintaan untuk setiap Manajer replika yang benar dalam (total) agar sama .


Gambar 18.4 replikasi aktif



3. Eksekusi : Setiap manajer replika mengeksekusi permintaan tersebut. Karena mereka negara mesin dan karena permintaan yang disampaikan dalam total order yang sama, replika yang benar manajer semua memproses permintaan identik. Tanggapan berisi klien permintaan unik identifier .

AgrElement : Tidak ada fase perjanjian diperlukan , karena pengiriman multicast semantik.
Respon : Setiap manajer replika mengirimkan tanggapannya terhadap ujung depan . Nomor
dari menjawab bahwa ujung depan mengumpulkan tergantung pada asumsi kegagalan dan algoritma multicast. Jika, misalnya, tujuannya adalah untuk mentolerir hanya kegagalan kecelakaan dan multicast memenuhi perjanjian seragam dan memesan properti, maka front end melewati respon pertama tiba kembali ke klien dan membuang sisanya ( dapat membedakan ini dari tanggapan terhadap permintaan lain dengan memeriksa identifier di tanggapan) sistem ini  mencapai konsistensi berurutan. Semua manajer replika yang benar memproses urutan yang sama permintaan. Keandalan multicast memastikan bahwa setiap yang benar.

Manajer replika proses set yang sama permintaan dan total order memastikan bahwa mereka memproses mereka dalam urutan yang sama. Karena mereka adalah mesin negara, mereka semua berakhir dengan negara sama satu sama lain setelah setiap permintaan. permintaan masing-masing ujung depan yang disajikan di Agar FIFO (karena ujung depan menunggu tanggapan sebelum membuat permintaan berikutnya), yang sama dengan 'agar program. Hal ini memastikan konsistensi berurutan. Jika klien tidak berkomunikasi dengan klien lainnya sambil menunggu tanggapan request, mereka maka permintaan mereka diproses agar terjadi sebelumnya. Jika klien

multi berulir dan dapat berkomunikasi dengan satu sama lain sambil menunggu tanggapan dari layanan, maka untuk menjamin memproses permintaan di terjadi sebelum pesanan kami akan harus mengganti multicast dengan satu yang baik kausal dan benar-benar memerintahkan. Sistem replikasi aktif tidak mencapai linearizability. Hal ini karena total order di mana permintaan manajer replika proses belum tentu sama dengan urutan real-time di mana klien membuat permintaan mereka. Schneider [ 1990] menjelaskan bagaimana, dalam sistem sinkron dengan jam sekitar disinkronkan, total order di mana permintaan manajer replika proses dapat didasarkan pada urutan fisik.

Diskusi replikasi aktif • Kami telah diasumsikan solusi untuk benar-benar memerintahkan dan multicast handal. Seperti Bab 15 menunjukkan, memecahkan handal dan benar-benar memerintahkan multicast setara dengan memecahkan konsensus. Pemecahan konsensus pada gilirannya membutuhkan baik bahwa sistem ini sinkron atau teknik seperti menggunakan detektor kegagalan digunakan dalam sistem asynchronous, untuk bekerja di sekitar hasil ketidak mungkinan Fischer etal. [1985]     Beberapa solusi untuk konsensus, seperti yang dari Canetti dan Rabin [1993], bekerja bahkan

With asumsi kegagalan Bizantium. Mengingat solusi tersebut, dan karena itu solusi untuk benar-benar memerintahkan dan multicast handal, sistem replikasi aktif dapat menutupi hingga kegagalan Bizantium f, selama layanan menggabungkan setidaknya 2f + 1 replika manusia. Setiap ujung depan menunggu sampai telah dikumpulkan f + 1 tanggapan identik dan melewati bahwa respon kembali ke klien. Ini membuang tanggapan lain untuk permintaan yang sama. Menjadi ketat yakin yang respon benar-benar berhubungan dengan yang request (diberikan Byzantine perilaku), kami mengharuskan manajer replika digital sign tanggapan mereka.

Dimungkinkan untuk bersantai sistem yang kita telah dijelaskan. Pertama, kita harus Assumed bahwa semua update ke objek direplikasi bersama harus terjadi dalam urutan yang sama.Namun, dalam prakteknya beberapa operasi mungkin bolak-balik: yaitu, efek dari dua operasidilakukan dalam urutan Hai: mungkin sama seperti jika mereka dilakukan di sebaliknya memesan, Hai 2 Hai 1 1Hai 2. Misalnya, dua operasi read-only (dari klien yang berbeda) perjalanan, dan dua operasi apapun yang tidak melakukan membaca tapi memperbarui objek yang berbeda perjalanan. Sebuah sistem replikasi aktif mungkin dapat memanfaatkan pengetahuan komutatif untuk menghindari biaya pemesanan segala permintaan. Kami menunjukkan dalam Bab 15 bahwa beberapa telah mengusulkan khusus aplikasi multicast memesan semantik [Cheriton dan Skeen 1993, Pedone dan Schiper 1999].

Akhirnya, ujung depan dapat mengirimkan read-only permintaan hanya untuk replika individu manusia. Dalam melakukannya, mereka kehilangan toleransi kesalahan yang datang dengan multicasting permintaan, tapi layanan tetap berurutan konsisten. Selain itu, ujung depan bisa mudah masuk kegagalan seorang manajer replika dalam hal ini , hanya dengan mengirimkan dibaca pada permintaan untuk lain tiruan manajer.    18. studi kasus pelayanan sangat tersedia :       Gosip arsitektur , Bayou dan Coda

Pada bagian ini, kita mempertimbangkan bagaimana menerapkan teknik replikasi untuk membuat layanan yang sangat tersedia. penekanan kami saat ini adalah untuk memberikan klien akses ke layanan  dengan wajar waktu respon sebanyak waktu mungkin, bahkan jika beberapa hasil tidak sesuai konsistensi berurutan. Misalnya,  pengguna di kereta dijelaskan di awal bab ini mungkin bersedia untuk mengatasi inkonsistensi temporer antara salinan Data seperti buku harian jika mereka dapat terus bekerja sementara terputus dan memperbaiki masalah di kemudian .

Dalam Bagian 18.3 , kita melihat bahwa sistem fault-tolerant mengirimkan update ke replika

manajer dalam mode ' bersemangat ' : semua replic benar

manajer menerima update segera.

Gambar 18.5 Query dan memperbarui operasi di layanan gosip     mungkin dan mereka mencapai kesepakatan bersama sebelum melewati kontrol kembali ke klien. perilaku ini tidak diinginkan untuk operasi yang sangat tersedia.  Sebaliknya, sistem harus

memberikan tingkat yang dapat diterima dari layanan menggunakan seperangkat minimal manajer replika terhubung ke klien. Dan itu harus meminimalkan berapa lama klien diikat sementara replika manajer mengkoordinasikan kegiatan mereka. derajat lemah konsistensi umumnya memerlukan kurang perjanjian dan data sehingga memungkinkan berbagi menjadi lebih tersedia.

     Kami sekarang memeriksa desain tiga systems yang menyediakan sangat tersedia Layanan : arsitektur gosip , Bayou dan Coda . 18.4.1 Arsitektur gosipLadinetal. [1992] mengembangkan apa yang kita sebut arsitektur gosip sebagai kerangka kerja untuk melaksanakan layanan sangat tersedia dengan mereplikasi data yang dekat dengan titik di mana kelompok klien membutuhkannya. Nama mencerminkan fakta bahwa pertukaran manajer replika 'Gosip' pesan secara berkala untuk menyampaikan update mereka masing-masing menerima dari klien (lihat Gambar 18.5). Arsitektur ini didasarkan pada karya sebelumnya pada database oleh Fischer dan Michael [1982] dan wuu dan Bernstein [1984]. Ini dapat digunakan, untuk Misalnya, untuk membuat buletin elektronik sangat tersedia papan atau layanan diary.     Sebuah layanan gosip menyediakan dua tipe dasar operasi: qu Eries yang read-only operasi dan update memodifikasi tapi tidak membaca negara (yang terakhir adalah lebih terbatas definisi dari yang kami telah menggunakan). Fitur utama adalah bahwa ujung depan mengirim permintaan dan update setiap manajer replika yang mereka pilih, asalkan tersedia dan dapat memberikan wajar waktu respon. Sistem ini membuat dua jaminan, meskipun replika manajer mungkin sementara tidak dapat berkomunikasi dengan satu sama lain:

Untuk mendukung konsistensi santai, arsitektur gosip mendukung kausal pembaruan pemesanan, seperti yang kita didefinisikan dalam Bagian 15.2.1. Ini juga mendukung kuat memesan jaminan di bentuk paksa (total dan kausal) dan segera memesan. update segera memerintahkan diterapkan dalam urutan yang konsisten relatif terhadap setiap update lain di semua manajer replika, apakah pembaruan pemesanan lainnya ditetapkan sebagai kausal, dipaksa atau langsung. Segera pemesanan disediakan selain untuk memesan paksa, karena update dipaksa-order dan kausal-order pembaruan yang tidak berhubungan dengan terjadi-sebelum hubungan dapat diterapkan dalam urutan yang berbeda pada manajer replika yang berbeda. Segera pemesanan disediakan selain untuk memesan paksa, karena updatedipaksa-order dan kausal-order pembaruan yang tidak berhubungan dengan terjadi-sebelum hubungan dapat diterapkan dalam urutan yang berbeda pada manajer replika yang berbeda. Pilihan yang memesan untuk digunakan diserahkan kepada desainer aplikasi dan mencerminkan trade-off antara konsistensi dan biaya operasi. update kausal yang jauh lebih murah dari yang lain dan diharapkan akan digunakan bila memungkinkan. Catat itu query, yang dapat dipenuhi oleh setiap manajer replika tunggal, selalu dilaksanakan di Agar kausal sehubungan dengan operasi lainnya. Ujung depan untuk layanan gosip menangani operasi yang klien membuat menggunakan API aplikasi khusus dan mengubahnya menjadi operasi gosip. Secara umum, klien operasi dapat membaca keadaan direplikasi, memodifikasi atau keduanya. Sejak di update gossip murni memodifikasi negara, ujung depan mengkonversi sebuah operasi yang baik membaca dan memodifikasi negara menjadi query dan update terpisah. Ujung depan untuk layanan gosip menangani operasi yang klien membuat menggunakan API aplikasi khusus dan mengubahnya menjadi operasi gosip.

Operation hal replikasi model dasar kita, garis besar bagaimana layanan gosip memproses query dan memperbarui operasi adalah sebagai berikut:

Permintaan: Ujung depan biasanya mengirimkan permintaan hanya seorang manajer replika tunggal pada suatu waktu. Namun, ujung depan akan berkomunikasi dengan manajer replika yang berbeda ketika salah satu biasanya menggunakan gagal atau menjadi tidak terjangkau, dan mungkin mencoba salah satu atau lebih orang lain jika manajer normal berat dimuat. Ujung depan, dan dengan demikian klien, mungkin diblokir pada operasi query. Susunan default untuk operasi update, di sisi lain, adalah untuk kembali ke klien secepat operasi telah berlalu ke ujung depan; ujung depan kemudian merambat operasi di latar belakang. Atau, untuk meningkatkan kehandalan, klien dapat dicegah untuk melanjutkan sampai update telah dikirim ke f+ 1 replika manajer, memastikan bahwa hal itu akan disampaikan di mana-mana meskipun hingga kegagalan f.
Tanggapan Update: Jika permintaan tersebut update, maka manajer replika balasan sebagai Begitu mereka telah menerima update.
Koordinasi: Manajer replika yang menerima permintaan tidak memproses sampai dapat menerapkan permintaan sesuai dengan kendala pemesanan yang diperlukan. Hal ini mungkin
melibatkan menerima pembaruan dari manajer replika lainnya, dalam pesan gosip. Tidak ada yang lain koordinasi antara manajer replika yang terlibat.

Eksekusi: Manajer replika mengeksekusi permintaan tersebut.
Tanggapan Query: Jika permintaan tersebut query, maka manajer replika balasan di ini titik.
Persetujuan: Manajer replika pembaruan satu sama lain dengan bertukar gosip pesan, yang berisi update terbaru mereka terima. Mereka mengatakan untuk informasi satu sama lain dengan cara malas, dalam pesan gosip mungkin ditukar hanya kadang-kadang, setelah beberapa update telah dikumpulkan, atau ketika replika Manajer tahu bahwa itu hilang update dikirim ke salah satu rekan-rekan yang perlu memproses permintaan dapat membaca keadaan direplikasi, memodifikasi atau keduanya.
Sejak di update gosip murni memodifikasi negara, ujung depan mengkonversi sebuah operasi yang baik membaca dan memodifikasi negara menjadi query dan update terpisah. Kami sekarang menggambarkan sistem gosip secara lebih rinci. Kita mulai dengan mempertimbangkan cap waktu dan data struktur yang berakhir depan dan manajer replika menjaga agar mempertahankan pembaruan memesan jaminan. Kemudian, dalam hal ini, kami akan menjelaskan bagaimana replika manajer memproses query dan update. Banyak dari pengolahan cap waktu vektor diperlukan untuk mempertahankan update kausal mirip dengan algoritma multicast kausal Seksi.

The front end ini versi timestamp • Untuk mengontrol urutan operasi pengolahan, masing-masing ujung depan menyimpan timestamp vektor yang mencerminkan versi terbaru nilai data diakses oleh ujung depan (dan karena itu diakses oleh klien). Ini timestamp, dilambangkan prev di Gambar 18.5, berisi entri untuk setiap manajer replika. Ujung depan mengirimkannya dalam setiap pesan permintaan untuk manajer replika, bersama-sama dengan deskripsi query atau memperbarui operasi itu sendiri. Ketika seorang manajer replika mengembalikan nilai sebagai hasil dari operasi query, itu memasok timestamp vektor baru (baru dalam Gambar 18,5), karena replika mungkin telah diperbarui sejak operasi terakhir. Demikian pula, memperbarui operasi mengembalikan timestamp vektor (Update ID pada Gambar 18.5) yang unik untuk update. Setiap timestamp kembali digabungkan dengan timestamp sebelumnya front end ini.

Gambar 18.6 ujung depan menyebarkan cap waktu mereka setiap kali klien berkomunikasi secara langsung



untuk merekam versi data direplikasi yang telah diamati oleh klien. (LihatBagian 14.4 untuk definisi vektor timestamp penggabungan). Klien bertukar data dengan mengakseslayanan gosip yang sama dan dengan berkomunikasi langsung dengan satu sama lain. Karena klien ke klien komunikasi juga bisa menyebabkan hubungan kausal antara operasi diterapkan ke layanan, juga terjadi melalui ujung depan klien. Dengan cara itu, ujung depan dapat kuda-kudaan cap waktu vektor mereka pada pesan ke klien lain. Para penerima menggabungkan mereka dengan cap waktu mereka sendiri di memesan bahwa hubungan kausal dapat disimpulkan dengan benar . Situasi ini ditunjukkan pada Gambar 18,6 .Negara manager replika• Terlepas dari aplikasi, manajer replika berisi berikut komponen negara utama ( Gambar 18.7 ) :

Nilai : ini adalah nilai dari negara aplikasi sebagai dikelola oleh replika manajer. Setiap manajer replika adalah mesin negara, yang dimulai dengan yang ditentukan nilai awal dan setelah itu semata-mata hasil dari penerapan operasi update untuk yang negara Aluetimestamp : ini adalah timestamp vektor yang mewakili pembaruan yang tercermin dalam nilai. Ini berisi satu entri untuk setiap manajer replika. Hal ini diperbarui setiap kali operasi update diterapkan untuk nilai .

Updatelog : Semua operasi update yangtercatat dalam log ini secepat mereka diterima. Seorang manajer replika terus update dalam log untuk salah satu dari dua alasan. Pertama adalah bahwa manajer replika belum bisa menerapkan pembaruan karena belum stabil. Sebuah  update stabil adalah salah satu yang dapat diterapkan secara konsisten dengan jaminan pemesanan nya ( Kausal , dipaksa atau immediate ). Pembaruan yang belum stabil harus diadakan kembali dan belum diproses. Alasan kedua untuk menjaga update di log adalah bahwa, bahkan meskipun update telah menjadi stabil dan telah diterapkan untuk nilai, replika.

Gambar 18.7 Seorang manajer replika gosip , menunjukkan komponen negara utama





Pengolahan operasi update agar kausal • A front end menyampaikan permintaan update ke satu atau lebih manajer replika. Setiap permintaan update berisi spesifikasi update ( jenis dan parameter ) u.op, ujung depan ini timestampu.prev, dan unik identifier yang ujung depan menghasilkan, u.id. Jika ujung depan mengirimkan permintaan yang sama u untuk.beberapa manajer replika, menggunakan identifier yang sama di u setiap kali sehingga tidak akan diproses karena beberapa permintaan yang berbeda tetapi identik. Ketika manajer replika saya menerima permintaan update dari front end itu cek yang belum sudah diproses permintaan ini dengan melihat identifier operasinya di dieksekusi meja operasi dan dalam catatan di log-nya.                          manager replika membuang informasi jika sudah melihatnya: jika tidak, itu akan menambahkan elemen-i di replikanya timestamp per satu, untuk menjaga hitungan jumlah update telah diterima langsung dari ujung depan. Kemudian manajer replika menugaskan kepada permintaan update u vektor yang unik timestamp yang derivasi diberikan segera, dan catatan untuk update ditempatkan di replika manajer log. Jika ts adalah timestamp unik yang manajer replika menugaskan untuk pembaruan, maka catatan pembaruan dibangun dan disimpan dalam log sebagai berikut tuple: Manajer replika saya berasal tstimestamp dari u.prev dengan mengganti enganu.prev ini elemen dengan elemen i dari cap replika nya ( yang baru saja bertambah ). Tindakan ini membuat unik. sehingga memastikan  bahwa semua komponen sistem akan benar merekam apakah atau tidak mereka telah mengamati update. Unsur-unsur yang tersisa di ts adalah disalin dari u.prev , karena nilai-nilai ini dikirim oleh ujung depan yang harus digunakan untuk menentukan kapan update stabil . Manajer replika kemudian segera berlalu ts.Paksa dan operasi operasi segera • paksa dan update segera membutuhkan perlakuan khusus. Ingat yang memaksa update benar-benar serta kausal memerintahkan. Itu Metode dasar untuk memesan update paksa adalah untuk nomor urut yang unik untuk menjadi ditambahkan ke cap waktu yang terkait dengan mereka, dan untuk memproses mereka dalam urutan ini urutan nomor. Seperti Bab 15 menjelaskan, metode umum untuk menghasilkan urutan nomor adalah dengan menggunakan proses sequencer tunggal. Tapi ketergantungan pada proses tunggal tidak memadai dalam konteks layanan sangat tersedia. Solusinya adalah dengan menunjuk begitu- sebuah disebut replika utama manajer sebagai sequencer dan untuk memastikan bahwa replika lain Manajer dapat dipilih untuk mengambil alih secara konsisten sebagai sequencer seharusnya primer gagal.     Apa yang diperlukan adalah untuk mayoritas manajer replika (termasuk primer) untuk record yang update berikutnya dalam urutan sebelum operasi dapat diterapkan. Kemudian, sebagai Selama ma diterima kebanyakan manajer replika bertahan kegagalan, keputusan pemesanan ini akan dihormati oleh primer baru dipilih dari kalangan manajer replika yang masih hidup. update langsung diperintahkan sehubungan dengan update dipaksa by menggunakan primer Manajer replika untuk memesan mereka dalam urutan ini. primer juga menentukan update kausal dianggap telah didahului update segera. Hal ini dilakukan dengan berkomunikasi dan sinkronisasi dengan manajer replika lainnya untuk mencapai perjanjian. Rincian lebih lanjut tersedia di Ladinetal. [1992].Pesan gosip • manajer Replica mengirim pesan gosip yang berisi informasi tentang satu atau lebih update sehingga manajer replika lainnya dapat membawa negara mereka upto - date. Seorang manajer replika menggunakan entri dalam timestampnya tabel untuk memperkirakan Yang update apa saja replika lainnya manajer belum menerimanya adalah perkiraan karena itu

Manajer replika mungkin telah menerima lebih update sekarang ).

Sebuah m pesan gosip terdiri dari dua item yang dikirim oleh manajer replika sumber: nya log, m.log ,dan replika timestamp -nya, m.ts ( lihat Gambar 18.7 ). Replika manager yang menerima pesan gosip memiliki tiga tugas utama :

untuk menggabungkan log tiba dengan sendiri ( itu mungkin berisi pembaruan tidak terlihat oleh penerima sebelumnya).
ke apply setiap pembaruan yang telah menjadi stabil dan belum dijalankan sebelum (Update stabil dalam log tiba pada gilirannya membuat tertunda update menjadi stabil).
untuk menghilangkan catatan dari log dan entri dalam tabel operasi dijalankan ketika itu adalah known bahwa pembaruan telah diterapkan di mana-mana dan yang ada ada bahaya mengulangi. Kliring entri berlebihan dari log dan dari dieksekusi meja operasi merupakan tugas penting, karena mereka dinyatakan akan tumbuh tanpa batas.
Ketika catatan update baru telah digabungkan dalam untuk log, manajer replika mengumpulkan set S dari setiap pembaruan dalam log yang sekarang stabil. Ini dapat diterapkan untuk nilai tetapi perawatan harus diambil alih urutan di mana mereka diterapkan sehingga happenedbefore yang hubungan diamati. replika manajer macam update di set sesuai untuk urutan parsial '' antara cap waktu vektor. Kemudian menerapkan pembaruan dalam memesan, terkecil pertama. Bahwa adalah, masing-masing rS  hanya diterapkan jika tidak ada sS sehingga s.prev< r .prev .propagasi Update • Gosip arsitektur tidak menentukan ketika manajer replika bertukar pesan gosip, atau bagaimana seorang manajer replika memutuskan di mana untuk mengirim gosip nya pesan. Strategi update- propagasi yang kuat diperlukan jika semua manajer replika yang ke menerima semua update di waktu yang dapat diterima .

Waktu yang dibutuhkan untuk semua manajer replika untuk menerima update yang diberikan tergantung pada tiga faktor :

frekuensi dan durasi partisi jaringan ;
frekuensi yang manajer replika mengirim pesan gosip ;
kebijakan untuk memilih pasangan dengan yang gosip pertukaran .
Faktor pertama adalah di luar kendali sistem , meskipun pengguna bisa untuk batas tertentu

menentukan seberapa sering y bekerja hubungan arti .

frekuensi gosip - exchange yang diinginkan dapat disetel untuk aplikasi. Mempertimbangkan

sistem papan buletin dibagi antara beberapa situs. Ini tampaknya tidak perlu untuk setiap Item akan dikirim segera ke semua situs. Tapi bagaimana jika gosip hanya dipertukarkan setelah waktu yang lama, mengatakan sekali sehari ? Jika hanya update kausal yang digunakan maka sangat mungkin untuk klien di setiap situs memiliki perdebatan yang konsisten mereka sendiri atas papan buletin yang sama, menyadari diskusi di situs lain. Kemudian, katakanlah, tengah malam, semua perdebatan akan terserap: tapi perdebatan tentang topik yang sama cenderung aneh, ketika akan menjadi lebih baik bagi mereka untuk mempertimbangkan satu sama lain. Sebuah periode gosip – exchange menit atau jam tampaknya lebih tepat dalam hal ini .

kebijakan acak memilih pasangan secara acak tetapi dengan probabilitas tertimbang sehingga mendukung beberapa mitra atas orang lain  misalnya , dekat mitra lebih dari mitra jauh . Goldin dan panjang menemukan bahwa kebijakan seperti itu bekerja dengan sangat baik di bawah simulasi. kebijakan deterministik memanfaatkan fungsi sederhana dari negara replika manajer untuk membuat pilihan mitra.Misalnya, seorang manajer replika bisa memeriksa meja timestamp -nyadan memilih manajer replika yang muncul untuk menjadi tertinggal dalam update itu telah menerima.

kebijakan topologi mengatur manajer replika menjadi grafik tetap. Satu kemungkinan adalah mesh: manajer replika mengirim pesan gosip ke empat replika manajer yang terhubung. Lain adalah untuk mengatur manajer replika dalam lingkaran, dengan masing-masing menyampaikan gosip hanya untuk tetangganya (searah jarum jam, mengatakan), sehingga bahwa pembaruan dari setiap manajer replika akhirnya melintasi lingkaran. Ada banyak mungkin topologi lainnya, termasuk pohon.

kebijakan mitra-seclection yang berbeda seperti perdagangan ini off jumlah komunikasi terhadap latency transmisi yang lebih tinggi dan kemungkinan bahwa satu kegagalan akan mempengaruhi manajer replika lainnya. Pilihan tergantung pada prakteknya pada relatif faktor-faktor ini. Misalnya, topologi lingkaran  menghasilkan relatif sedikit komunikasi tetapi tunduk pada latency transmisi tinggi sejak gosip umumnya memiliki untuk melintasi beberapa manajer replika. Selain itu, jika salah satu manajer replika gagal maka lingkaran tidak dapat berfungsi dan perlu ulang. Sebaliknya, pemilihan acak itektur bertujuan untuk mencapai ketersediaan tinggi untuk layanan. Mendukungnya, arsitektur ini memastikan bahwa klien dapat terus mendapatkan layanan bahkan ketika mereka dipartisi dari sisa jaringan, selama setidaknya satu manajer replika terus berfungsi dalam partisi mereka. Tapi ini jenis ketersediaan dicapai dengan mengorbankan menegakkan konsistensi hanya santai jaminan. Untuk objek seperti rekening bank, di mana konsistensi sekuensial diperlukan, arsitektur gosip bisa melakukan tidak lebih baik dari pada sistem fault-tolerant dipelajari dalam Bagian 18,3 dan menyediakan layanan satu-satunya di partisi mayoritas.

Skalabilitas sistem gosip adalah anot masalah nya. Karena jumlah replika manajer tumbuh, begitu pula jumlah pesan gosip yang harus ditransmisikan dan ukuran cap waktu yang digunakan. Jika klien membuat permintaan, maka ini biasanya memakan waktu dua Pesan ( antara ujung depan dan manajer replika ). Jika klien membuat update kausal operasi dan jika masing-masing manajer replika R yang biasanya dikumpulkan update G menjadi gosip pesan, maka jumlah pesan yang dipertukarkan adalah 2 R 1 - G +.Istilah pertama merupakan komunikasi antara ujung depan dan manajer replika dan yang kedua adalah update ini share pesan gosip dikirim ke manajer replika lainnya. meningkatkan G meningkatkan jumlah pesan tetapi memperburuk latency pengiriman, karena replika Manajer menunggu lebih update tiba sebelum menyebarkan mereka.    Salah satu pendekatan untuk membuat layanan berbasis gosip scal mampu adalah untuk membuat sebagian besar replika read-only. Dengan kata lain, replika ini diperbarui oleh pesan gosip tapi lakukan tidak menerima update langsung dari ujung depan. Pengaturan ini berpotensi berguna dimana rasio update / permintaan kecil. Read-only replika dapat terletak dekat dengan klien kelompok dan update dapat dilayani oleh relatively beberapa manajer replika pusat. Gosip lalu lintas berkurang sejak read-only replika tidak memiliki gosip untuk menyebarkan, dan vektor cap hanya perlu berisi entri untuk replika diupdate.

18.4.2 Bayou dan pendekatan transformasi operasional

The Bayou sistem [ Terry dkk . 1995 , Petersen et al . 1997] memberikan replikasi data untuk

ketersediaan tinggi dengan jaminan lebih lemah dari konsistensi berurutan, seperti gosip arsitektur dan timestamped protokol anti entropi . Seperti dalam sistem-sistem, Bayou manajer replika mengatasi konektivitas variabel dengan bertukar update berpasangan, di apa para desainer juga memanggil protokol anti entropi. Tapi Bayou mengadopsi nyata pendekatan yang berbeda dalam hal itu memungkinkan deteksi konflik domain spesifik dan konflik Resolusi untuk mengambil tempat.

Mempertimbangkan pengguna yang perlu  memperbarui buku harian saat bekerja hubungan arti. Jika konsistensi yang ketat diperlukan, dalam update arsitektur gosip akan menjadi dilakukan dengan menggunakan dipaksa ( benar-benar memerintahkan ) operasi. Tapi kemudian hanya pengguna di mayoritas partisi bisa memperbarui buku harian itu. akses pengguna ke buku harian itu mungkin demikian terbatas, terlepas dari apakah mereka sebenarnya membuat pembaruan yang akan mematahkan buku harian ini integritas. Pengguna yang ingin mengisi janji non bertentangan diperlakukan sama sebagai pengguna yang mungkin memiliki sengaja memesan ganda slot waktu.     Di Bayou, sebaliknya, pengguna di kereta dan di tempat kerja dapat membuat pembaruan mereka suka. Semua pembaruan diterapkan dan dicatat pada apa pun manager replika mereka mencapai. Ketika update menerima setiap dua manajer replika digabung selama antientropy bertukar, Namun, manajer replika menemukan dan menyelesaikan konflik. Apa saja domain spesifik kriteria untuk menyelesaikan konflik antara operasi Mei diterapkan. contoh, jika seorang eksekutif bekerja di offsite , dan dia sekretaris memiliki menambahkan janji di slot waktu yang sama , maka sistem Bayou mendeteksi ini setelah eksekutif telah menghubungkan kembali laptop mereka . Selain itu, menyelesaikan konflik menurut kebijakan domain-spesifik . Di kasus ini , itu bisa , misalnya , mengkonfirmasi janji eksekutif dan menghapus pemesanan sekretaris di slot. Seperti efek , di mana satu atau lebih dari satu set

operasi yang bertentangan yang dibatalkan atau diubah untuk mengatasinya, disebut transformasi operasional.

Negara yang Bayou ulangan diadakan dalam bentuk database, mendukung query sebuah update d ( yang mungkin memasukkan, mengubah atau menghapus item dalam database ). Meskipun kita tidak akan berkonsentrasi pada aspek ini di sini , update Bayou adalah kasus khusus dari transaksi. Ini terdiri dari satu operasi, sebuah doa dari 'prosedur yang tersimpan' yang mempengaruhi beberapa objek dalam setiap manajer replika tapi dilakukan dengan ACID                               jaminan . Bayou dapat membatalkan dan mengulang update ke database sebagai hasil eksekusi .     The Bayou jaminan adalah bahwa, pada akhirnya, malam Manajer replika menerima sama set update dan akhirnya berlaku update tersebut sedemikian rupa bahwa replika database manajer adalah identik. Dalam prakteknya, mungkin ada aliran kontinu update dan database mungkin tidak pernah menjadi identik ; tetapi mereka akan menjadi identik jika update lagi.update berkomitmen dan tentatif • Pembaruan ditandai sebagai tentatif ketika mereka pertama kali diterapkan ke database. Bayou mengatur bahwa pembaruan tentatif pada akhirnya ditempatkan dikanonik ketertiban dan ditandai sebagai komitmen . Sementara update tentatif, sistem dapat membatalkan dan lagi mereka yang diperlukan untuk menghasilkan keadaan yang konsisten. Setelah berkomitmen, mereka tetap diterapkan agar mereka diberikan. Dalam prakteknya, urutan berkomitmen dapat dicapai dengan menunjuk beberapa manajer replika sebagai manajer replika primer. Dengan cara yang biasa, ini memutuskan urutan berkomitmen seperti itu di mana ia menerima update tentatif dan menjalar bahwa memesan informasi kepada manajer replika lainnya. Untuk utama, pengguna dapat memilih, misalnya, mesin cepat yang biasanya tersedia, atau manager replika di laptop seorang eksekutif, jika update yang pengguna diprioritaskan .cek ketergantungan dan menggabungkan prosedur • Pembaruan mungkin bertentangan dengan beberapa lainnya operasi yang telah diterapkan. Karena kemungkinan ini, setiap update Bayou berisi cek ketergantungan dan prosedur merge selain operasi ini Spesifikasi ( jenis operasi dan parameter ). Semua komponen ini dari update yang domain spesifik .Gambar 18,8 update berkomitmen dan tentatif di Bayou

Seorang manajer replika panggilan prosedur ketergantungan cek sebelum menerapkan operasi. Ia memeriksa apakah konflik akan terjadi jika update diterapkan dan hal itu mungkin memeriksa setiap bagian dari database untuk melakukan itu . Sebagai contoh, perhatikan kasus pemesanan janji di buku harian. Ketergantungan cek bisa, paling sederhana, tes untuk write write sebuah Konflik: yaitu, apakah klien lain memiliki terisi itu wajib Slot. Tapi itu ketergantungan Memeriksa juga dapat menguji untuk read- write konflik. Sebagai contoh, bisa menguji bahwa itu Slot diinginkan kosong dan bahwa jumlah janji pada hari itu adalah lebih sedikit dari enam.

Jika cek ketergantungan menunjukkan confli act , maka Bayou memanggil operasi ini menggabungkan prosedur. Prosedur yang mengubah operasi yang akan diterapkan sehingga mencapai sesuatu mirip dengan efek yang diinginkan tapi menghindari konflik. Sebagai contoh, dikasus buku harian prosedur merge bisa memilih slot lain pada waktu terdekat bukan atau, seperti yang telah disebutkan di atas, itu bisa menggunakan skema prioritas sederhana untuk menentukan janji yang lebih penting dan memaksakan satu itu. Prosedur gabungan mungkin gagal untuk menemukan perubahan yang sesuai operasi , dalam hal sistem menunjukkan kesalahan. Pengaruh prosedur merge adalah deterministik, namun Bayou manajer replika yang mesin negara .Diskusi • Bayou berbeda dari skema replikasi lain bahwa kita telah dianggap dalam hal itu membuat replikasi non transparan ke aplikasi. Ini mengeksploitasi pengetahuan semantik aplikasi untuk meningkatkan ketersediaan data tetap menjaga negara direplikasi yang apa yang kita sebut akhirnya berurutan konsisten.    Pendekatan ini memiliki beberapa kelemahan. Yang pertama adalah peningkatan kompleksitas

programmer aplikasi, yang harus menyediakan cek ketergantungan dan menggabungkan Prosedur. Keduanya mungkin rumit untuk menghasilkan, mengingat jumlah berpotensi besar kemungkinan konflik yang perlu dideteksi dan diatasi. Kerugian kedua adalah peningkatan kompleksitas bagi pengguna. Pengguna diharapkan untuk menangani tidak hanya dengan data yang membaca sementara mereka masih tentatif, tetapi juga dengan fakta bahwa operasi mereka tentukan mungkin ternyata telah diubah nanti. Misalnya pengguna dapat memesan slot di buku harian, hanya untuk menemukan kemudian bahwa pemesanan telah melompat ke slot di dekatnya. Hal ini sangat penting bahwa pengguna diberikan indikasi yang jelas dari mana data tentatif dan yang berkomitmen.

Pendekatan transformasi operasional yang digunakan oleh Bayou muncul terutama disistem

untuk mendukung komputer didukung kooperatif kerja ( CSCW ), di mana update bertentangan antara pengguna yang terpisah secara geografis dapat terjadi [Kindberg et al.1996, Sun dan Ellis 1998]. Pendekatan terbatas, dalam prakteknya, untuk aplikasi di mana konflik relatif jarang, di mana semantik data yang mendasari adalah relativel y sederhana ; dan di mana pengguna dapat mengatasi informasi tentatif.

18.4.3 sistem file coda

Sistem file Coda adalah keturunan dari AFS ( lihat Bagian 12.4 ) yang bertujuan untuk alamat

beberapa persyaratan yang AFS tidak memenuhi terutama kebutuhan untuk menyediakan ketersediaan tinggi meskipun operasi terputus. Ini dikembangkan dalam proyek penelitian dilakukan oleh Satyanarayanan dan rekan-rekan kerjanya di Carnegie Mellon University [Satyanarayanan et al.1990, Kistler dan Satyanarayanan 1992]. Desain persyaratan untuk Coda berasal dari pengalaman dengan AFS di CMU dan tempat lain melibatkan penggunaannya dalam sistem terdistribusi skala besar di kedua wilayah lokal dan luas jaringan komunikasi .

Sementara kinerja dan kemudahan administrasi AFS yang ditemukan memuaskan di bawah kondisi penggunaan di CMU, dirasakan bahwa bentuk terbatas replikasi ( dibatasi untuk read-only volume ) yang ditawarkan oleh AFS terikat untuk menjadi faktor pembatas di begitu saya skala, terutama untuk mengakses file secara luas bersama seperti papan buletin elektronik dan seluruh sistem database lainnya.     Selain itu, ada ruang untuk perbaikan dalam ketersediaan layanan ditawarkan oleh AFS. Kesulitan yang paling umum dialami oleh pengguna dari AFS muncul dari kegagala ( atau gangguan dijadwalkan ) dari server dan komponen jaringan. Skala sistem di CMU adalah seperti bahwa kegagalan layanan beberapa terjadi setiap hari dan mereka serius bisa merepotkan banyak pengguna untuk periode mulai dari beberapa menit untuk berjam-jam.     Akhirnya, modus penggunaan komputer telah muncul yang AFS tidak memenuhi yang penggunaan mobile komputer portabel. Hal ini menyebabkan kebutuhan untuk membuat semua file diperlukan bagi pengguna untuk melanjutkan pekerjaan mereka tersedia saat terputus dari jaringan tanpa resorting untuk metode manual untuk mengelola lokasi file.     Coda bertujuan untuk memenuhi ketiga persyaratan tersebut di bawah judul umum ketersediaan data konstan. Tujuannya adalah untuk menyediakan pengguna dengan manfaat dari file bersama repositori tetapi untuk memungkinkan mereka untuk bergantung sepenuhnya pada sumber daya lokal ketika repositori adalah sebagian atau seluruhnya tidak dapat diakses. Selain tujuan tersebut, Coda mempertahankan tujuan aslinya dari AFS berkaitan dengan skalabilitas dan emulasi file semantik UNIX.     Berbeda dengan AFS, di mana baca tulis volume disimpan pada satu server, desain Coda bergantung pada replikasi volume berkas untuk mencapai throughput yang lebih tinggi dari operasi file akses dan tingkat yang lebih besar dari toleransi kesalahan. Selain itu, Coda bergantung pada perpanjangan dari mekanisme yang digunakan dalam AFS untuk caching salinan file pada klien komputer untuk mengaktifkan komputer mereka untuk beroperasi ketika mereka tidak terhubung ke jaringan.     Coda adalah seperti Bayou sejauh itu berikut strategi optimis Artinya, hal itu memungkinkan

klien untuk memperbarui data sementara sistem dipartisi, atas dasar bahwa konflik yang relatif tidak mungkin dan bahwa mereka dapat diperbaiki jika mereka terjadi. Seperti Bayou, mendeteksi konflik, tapi tidak seperti Bayou ia melakukan pemeriksaan ini tanpa memperhatikan semantik data yang disimpan dalam file. Juga tidak seperti Bayou, ia menyediakan dukungan sistem hanya terbatas untuk menyelesaikan replika yang bertentangan.

Coda arsitektur • Coda berjalan apa yang disebut proses ' Venus ' pada klien komputer dan proses ' Wakil ' di komputer server file , mengadopsi terminologi AFS. Wakil proses adalah apa yang kita sebut manajer replika. Proses Venus hibrida dari ujung depan dan manajer replika. Mereka memainkan peran ujung depan untuk menyembunyikan pelaksanaan layanan dari proses klien lokal, tapi karena mereka mengelola cache local file mereka juga manajer replika ( meskipun dari tipe yang berbeda kepada Wakil proses ).     Set server memegang replika dari volume file yang dikenal sebagai volume tersebut penyimpanan kelompok ( VSG ). Pada setiap saat, klien yang ingin membuka file dalam volume tersebut dapat mengakses beberapa subset dari VSG, yang dikenal sebagai kelompok penyimpanan volume yang tersedia ( AVSG ). Itu keanggotaan AVSG bervariasi sebagai server menjadi dapat diakses atau dibuat tidak dapat diakses oleh jaringan atau server kegagalan.     Biasanya, Coda mengajukan hasil akses dalam cara yang mirip dengan AFS, dengan cache salinan file yang diberikan ke komputer klien oleh salah satu dari server di AVSG saat ini. Seperti dalam AFS, klien akan diberitahu tentang perubahan melalui janji callback mekanisme, tapi ini sekarang tergantung pada mekanisme tambahan untuk distribusi update setiap replika. Pada dekat, salinan file diubah disiarkan secara paralel untuk semua server di AVSG tersebut.     Dalam Coda, operasi terputus dikatakan terjadi ketika AVSG kosong. Ini mungkin karena jaringan atau server kegagalan, atau mungkin konsekuensi dari yang disengaja pemutusan komputer klien, seperti dalam kasus laptop. efektif terputus operasi bergantung pada kehadiran dalam cache komputer klien dari semua file yang diperlukan untuk pekerjaan pengguna untuk melanjutkan. Untuk mencapai hal ini, pengguna harus bekerja sama dengan Coda untuk menghasilkan daftar file yang harus di cache. Sebuah alat yang disediakan yang mencatat daftar sejarah Penggunaan berkas sementara terhubung, dan ini berfungsi sebagai dasar untuk memprediksi penggunaan sementara terputus .      Ini adalah prinsip desain Coda bahwa salinan file yang berada di server lebih dapat diandalkan daripada mereka yang tinggal di cache dari komputer klien. Meskipun mungkin mungkin logis untuk membangun sebuah sistem file yang bergantung sepenuhnya pada salinan cache dari file di komputer klien, tidak mungkin bahwa kualitas yang memuaskan pelayanan akan dicapai. Server Coda ada untuk memberikan kualitas yang diperlukan layanan. Salinan file yang berada di klien cache komputer dianggap sebagai berguna hanya selama sebagai mereka valas dapat berkala divalidasi ulang terhadap salinan yang berada di server. Dalam kasus operasi terputus, revalidation terjadi ketika operasi terputus berhenti dan file cache yang diintegrasikan kembali dengan orang-orang di server . Dalam kasus terburuk,  ini mungkin membutuhkan beberapa intervensi manual untuk menyelesaikan inkonsistensi atau konflik .Strategi replikasi • strategi replikasi Coda adalah optimis memungkinkan modifikasi file untuk melanjutkan ketika jaringan dipartisi atau selama terputus operasi. Hal ini bergantung pada lampiran untuk setiap versi file dari vektor versi Coda( CVV ). Sebuah CVV adalah timestamp vektor dengan satu elemen untuk setiap server di relevan VSG. Setiap elemen dari CVV adalah perkiraan jumlah modifikasi dilakukan pada versi file yang diadakan di sesuai Server. Tujuan dari CVVs adalah untuk memberikan informasi yang cukup tentang sejarah update setiap replika berkas untuk memungkinkan potensi konflik untuk dideteksi dan diajukan untuk intervensi manual dan untuk replika basi diperbarui secara otomatis.     Jika CVV di salah satu situs lebih besar dari atau sama dengan semua yang sesuai CVVs di situs lain ( Bagian 14,4 mendefinisikan arti v untuk vektor cap waktu v 1dan v 21v2), Maka tidak ada konflik. replika yang lebih tua(dengan ketat kecil cap) termasuk semua update di replika baru dan mereka bisa secara otomatis menjadi membawa up-to -date dengan itu.    Ketika file dimodifikasi ditutup, setiap situs di AVSG saat dikirim update pesan oleh proses Venus pada klien, yang berisi CVV saat ini dan baru isi file. Wakil proses pada setiap situs memeriksa CVV dan, jika lebih besar dari yang saat ini dipegang , toko isi baru untuk file dan mengembalikan positif pengakuan. Proses Venus kemudian menghitung sebuah CVV baru dengan modifikasi jumlah meningkat untuk server yang merespon positif terhadap pesan update dan mendistribusikan CVV baru untuk para anggota AVSG.     Sejak pesan dikirim hanya kepada anggota yang AVSG dan tidak VSG, server yang tidak di AVSG saat ini tidak menerima CVV baru. Setiap CVV akan Oleh karena itu selalu mengandung hitungan modifikasi akurat untuk server lokal, tetapi jumlah untuk server non-lokal pada umumnya akan batas bawah, karena mereka akan diperbarui hanya ketika server menerima pesan pembaruan .     Dalam operasi normal, perilaku aplikasi Coda telinga mirip dengan AFS. Sebuah Cache miss transparan kepada pengguna dan hanya membebankan hukuman kinerja. Itu keuntungan yang berasal dari replikasi beberapa atau semua volume file di beberapa server adalah:

File dalam volume direplikasi tetap acces jawab untuk setiap klien yang dapat mengakses setidaknya salah satu replika.
Kinerja sistem dapat im terbukti dengan berbagi beberapa beban dari melayani permintaan klien pada volume direplikasi antara semua server yang terus replika.
Dalam operasi terputus( ketika tidak ada server untuk volume dapat diakses oleh klien ) cache miss mencegah progress dan perhitungan ditangguhkan sampai koneksi dilanjutkan atau pengguna dibatalkan proses. Oleh karena itu penting untuk memuat cache sebelum operasi terputus dimulai sehingga cache misses dapat dihindari.     Singkatnya, dibandingkan dengan AFS, Coda meningkatkan ketersediaan baik oleh replikasi file di server dan oleh kemampuan klien untuk beroperasi sepenuhnya dari cache mereka. Kedua metode tergantung pada penggunaan strategi optimis untuk deteksi konflik pembaruan di hadapan partisi jaringan. Mekanisme yang komplementer dan independen satu sama lain. Misalnya, pengguna dapat memanfaatkan manfaat dari operasi terputus meskipun volume file yang diperlukan disimpan pada server tunggalInformasi semantik • Jaminan mata uang yang ditawarkan oleh Coda ketika klien membuka file

lebih lemah daripada untuk AFS, mencerminkan strategi pembaruan optimis. Single Server S dimaksud dalam jaminan uang untuk AFS digantikan oleh seperangkat server S ( File ini VSG ) dan klien C dapat mengakses subset dari servers ( Yang AVSG untuk file dilihat oleh C ).

Informal, jaminan yang ditawarkan oleh terbuka yang sukses di Coda adalah bahwa ia menyediakan salinan terbaru dari F dari AVSG saat ini, dan jika ada server dapat diakses, secara lokal salinan cache dari F digunakan jika tersedia . Sebuah sukses dekat menjamin bahwa file tersebut telah disebarkan ke set saat ini dapat diakses dari server atau jika tidak ada server tersedia, bahwa file telah ditandai untuk propagasi pada kesempatan pertama .     Definisi yang lebih tepat dari jaminan tersebut, dengan rekening efek yang hilang callback, dapat dibuat dengan menggunakan perluasan dari notasi yang digunakan untuk AFS. Di setiap Definisi kecuali yang terakhir ada dua kasus: pertama, dimulai s Ø , mengacu pada semua situasi di mana AVSG tidak kosong, dan yang kedua berkaitan dengan terputus operasi:



Model ini mengasumsikan sistem sinkron : T adalah waktu terlama yang klien dapat tetap tidak menyadari update tempat lain ke file yang ada di cache: terbaru ( F ,s, T ) menunjukkan fakta bahwa nilai sekarang dari F di C adalah yang terbaru di semua server di s di beberapa instan dalam detik T terakhir dan bahwa tidak ada konflik antara salinan dari F pada saat itu: lostCallback ( s, T ) berarti bahwa callback dikirim oleh beberapa anggota dari s di detik T lalu dan tidak diterima di C: dan konflik ( F , s ) berarti bahwa nilai-nilai F pada beberapa server di s

Saat ini dalam konflik.

Mengakses replika • Strategi yang digunakan pada membuka dan menutup untuk mengakses replika file adalah varian dari read- satu / write semua pendekatan yang dijelaskan dalam Bagian 18.5. pada open, jika copy dari file tersebut tidak hadir dalam cache lokal klien mengidentifikasi server disukai dari AVSG untuk file . server disukai dapat dipilih secara acak, atau pada berdasarkan kriteria kinerja seperti kedekatan fisik atau beban server. Klien meminta salinan atribut berkas dan isi dari server disukai, dan pada menerima itu, ia akan mengecek dengan semua anggota lain dari AVSG untuk memverifikasi bahwa salinan tersebut versi terbaru yang tersedia . Jika tidak, anggota dari AVSG dengan versi terbaru dibuat situs yang lebih disuka,  isi file yang refetched dan anggota AVSG adalah diberitahu bahwa beberapa anggota memiliki replika basi, Ketika mengambil telah selesai, Janji callback didirikan pada server yang lebih disukai      Ketika sebuah file ditutup pada klien setelah modifikasi, isinya dan atribut yang ditransmisikan secara paralel untuk semua anggota AVSG menggunakan remote multicast Prosedur panggilan protocol. Ini memaksimalkan probabilitas bahwa setiap situs replikasi untuk

file memiliki versi saat ini setiap saat. Itu tidak menjamin itu, karena AVSG melakukan belum tentu mencakup semua anggota VSG. Ini meminimalkan beban server oleh memberikan klien tanggung jawab untuk menyebarkan perubahan pada situs replikasi di kasus normal ( server yang terlibat hanya ketika replika basi ditemukan di terbuka ).

Sejak mempertahankan negara callback di semua anggota sebuah AVSG akan Mahal, janji callback dipertahankan hanya pada server yang lebih disukai . Tapi ini memperkenalkan masalah baru: server yang lebih disukai untuk satu klien tidak perlu di AVSG yang dari klien lain. Jika hal ini terjadi, update by klien kedua tidak akan menyebabkan callback untuk klien pertama. Solusi diadopsi untuk masalah ini dibahas di depan ayat.Koherensi Cache • The Coda jaminan uang tersebut di atas berarti bahwa Venus Proses di setiap klien harus mendeteksi peristiwa berikut T detik dari mereka kejadian:

pembesaran sebuah AVSG ( karena acc yang essibility dari sebelumnya tidak dapat diakses server) ;
menyusut dari AVSG ( karena server menjadi tidak dapat diakses ) ;
acara callback hilang .
Untuk mencapai hal ini , Venus mengirimkan pesan probe untuk semua server di VSGs dari file yang memiliki dalam cache setiap T detik . Tanggapan akan diterima hanya dari diakses server. Jika Venus menerima respon dari server sebelumnya tidak dapat diakses itu membesar yang sesuai AVSG dan tetes janji-janji panggilan balik pada setiap file yang dimilikinya dari volume yang relevan . Hal ini dilakukan karena salinan cache mungkin tidak lagi terbaru versi yang tersedia di AVSG baru.    Jika gagal untuk menerima respon dari server sebelumnya dapat diakses Venus menyusut yang sesuai AVSG. Tidak ada perubahan callback diperlukan kecuali penyusutan ini disebabkan oleh hilangnya server yang lebih disukai, dalam hal ini semua callback menjanjikan itu server harus turun . Jika respon menunjukkan bahwa pesan callback dikirim tapi tidak diterima, callback janji pada file yang berkaitan dijatuhkan.     Kita sekarang kiri dengan masalah , yang disebutkan di atas , update yang terlewatkan oleh server karena tidak di AVSG dari klien yang berbeda yang melakukan update. Untuk menangani kasus ini, Venus mengirim Versi Volume vektor (volume CVV ) dalam menanggapi setiap pesan penyelidikan. Volume CVV berisi ringkasan dari CVVs untuk semua file dalam volume. Jika Venus mendeteksi ketidakcocokan apapun antara CVVs volume yang kemudian beberapa anggota AVSG harus memiliki beberapa versi file yang tidak up- to-date. Meskipun file usang mungkin tidak menjadi orang-orang yang berada di cache lokal, Venus membuat asumsi pesimis dan tetes janji-janji callback pada semua file yang dimilikinya dari volume yang relevan.     Perhatikan bahwa Venus hanya probe server di VSGs file yang dimilikinya cache salinan dan bahwa pesan probe tunggal berfungsi untuk memperbarui AVSGs dan memeriksa callback untuk semua file dalam volume. Ini, dikombinasikan dengan relatif large nilai T ( di urutan 10 menit dalam pelaksanaan percobaan), berarti bahwa probe bukan halangan untuk skalabilitas Coda ke nomor besar server dan lebar jaringan area.Operasi Terputus • Selama pemutusan singkat, seperti yang mungkin terjadi karena gangguan layanan yang tak terduga, penggantian cache yang paling terakhir digunakan kebijakan biasanya diadopsi oleh Venus mungkin cukup untuk menghindari cache misses pada volume terputus. Tetapi tidak mungkin bahwa klien dapat beroperasi dalam mode terputus untuk waktu yang lama tanpa menghasilkan referensi ke file atau direktori yang tidak cache kecuali kebijakan yang berbeda diadopsi .     Oleh karena itu Coda memungkinkan pengguna untuk menentukan daftar prioritas file dan direktori yang Venus harus berusaha untuk mempertahankan dalam cache. Benda di tingkat tertinggi diidentifikasi sebagai lengket dan ini harus dipertahankan dalam cache setiap saat. Jika disk lokal cukup besar untuk mengakomodasi semua dari mereka, pengguna yakin bahwa mereka akan tetap dapat diakses. Sejak seringkali sulit untuk tahu persis apa file yang akses yang dihasilkan oleh setiap urutan tindakan pengguna, alat ini disediakan yang memungkinkan pengguna untuk braket urutan tindakan: VEnus mencatat referensi file yang dihasilkan oleh urutan dan bendera mereka dengan diberikan prioritas.     Ketika operasi terputus berakhir, proses reintegrasi dimulai. Untuk setiap File cache atau direktori yang telah dimodifikasi, dibuat atau dihapus selama terputus operasi, Venus mengeksekusi urutan operasi update untuk membuat replika AVSG identik dengan salinan cache. Reintegrasi hasil top-down dari akar masing-masing Volume cache.Kinerja • Satyanarayanan et al. [1990] dibandingkan kinerja Coda dengan AFS bawah beban patokan dirancang untuk mensimulasikan populasi pengguna mulai dari 5 hingga 50 pengguna AFS khas.       Tanpa replikasi, tidak ada perbedaan yang signifikan antara kinerja AFS dan Coda. Dengan replikasi tiga kali lipat, waktu yang dibutuhkan untuk Coda untuk melakukan beban patokan setara dengan 5 pengguna khas melebihi dari AFS tanpa replikasi oleh hanya 5 %. Namun, dengan replikasi tiga kali lipat dan beban setara dengan 50 pengguna, waktu dibutuhkan untuk menyelesaikan benchmark meningkat sebesar 70 %, sedangkan untuk AFS tanpa replikasi hanya meningkat 16 %. Perbedaan ini disebabkan hanya sebagian untuk overhead yang terkait dengan replikasi-perbedaan tuning pelaksanaan dikatakan untuk memperhitungkan bagian dari perbedaan dalam kinerja .Diskusi • Kami menunjukkan di atas bahwa Coda mirip dengan Bayou dalam hal itu juga mempekerjakan pendekatan optimis untuk mencapai ketersediaan tinggi ( meskipun mereka berbeda dalam beberapa cara lain, paling tidak karena satu mengelola file dan database lainnya ). Kami juga menggambarkan bagaimana Coda menggunakan CVVs untuk memeriksa konflik, tanpa memperhatikan semantik dari data yang disimpan dalam file . Pendekatan ini dapat mendeteksi konflik write-write potensi tetapi tidak baca tulis konflik. Ini adalah ' potensi ' write-write konflik karena pada tingkat semantik aplikasi mungkin tidak ada konflik yang sebenarnya: klien mungkin telah diperbarui objek yang berbeda dalam file mensinergikan sehingga gabungan otomatis sederhana akan mungkin.     Pendekatan keseluruhan Coda untuk deteksi konflik semantik bebas dan manual Resolusi masuk akal dalam banyak kasus, terutama dalam aplikasi yang membutuhkan manusia penilaian atau dalam sistem tanpa pengetahuan semantik data ini.     Direktori adalah kasus khusus di Coda. mempertahankan otomatis integritas obyek utama melalui resolusi konflik kadang-kadang mungkin, karena mereka semantik relatif sederhana : satu-satunya perubahan yang dapat dibuat ke direktori adalah penyisipan atau penghapusan entri direktori. Coda menggabungkan metode sendiri untuk menyelesaikan direktori. Ini memiliki efek yang sama seperti pendekatan Bayou untuk transformasi operasional, tetapi Coda menggabungkan keadaan direktori yang bertentangan secara langsung, karena tidak memiliki catatan operasi yang klien dilakukan .Replikasi di Dynamo • Bagian 16.7 diperkenalkan Dynamo, layanan penyimpanan yang Amazon menggunakan untuk aplikasi seperti shopping cart yang membutuhkan akses hanya kunci / nilai. Dalam Dynamo [DeCandia et al . 2007], data dipartisi dan direplikasi: semua pembaruan mencapai semua replika akhirnya.     cap vektor digunakan untuk menentukan urutan kausal antara berbeda versi dari objek yang sama. Cap waktu dibandingkan seperti yang dijelaskan dalam Bagian 14.4. Ketika time stamp vektor dari satu versi lebih kecil dari yang lain, versi sebelumnya dibuang. Jika tidak, dua versi konflik dan harus diselesaikan. kedua versi dari data yang disimpan dan kemudian diberikan kepada klien sebagai hasil dari operasi baca.     Klien ini bertanggung jawab untuk menyelesaikan konflik. Dynamo memberikan baik Pendekatan aplikasi tingkat Bayou dan pendekatan sistem tingkat Coda. Mantan Pendekatan yang digunakan untuk shopping cart, di mana semua operasi add item dalam bentrok versi digabung dan kadang-kadang item yang dihapus bisa muncul kembali, ketika aplikasi semantik tidak dapat digunakan, Dynamo menggunakan resolusi berbasis timestamp sederhana obyek dengan nilai timestamp fisik terbesar dipilih sebagai versi yang benar.18.5 transaksi dengan data replikasi                     sistem Sejauh ini dalam bab ini kita telah dianggap di mana klien meminta tunggal operasi pada waktu pada set direplikasi objek. Bab 16 dan 17 menjelaskan bahwa transaksi urutan satu atau lebih operasi, diterapkan dengan cara seperti untuk menegakkan sifat ACID. Seperti dengan sistem dalam Bagian 18.4, objek di transaksional sistem dapat direplikasi untuk meningkatkan baik ketersediaan dan kinerja.    Dari sudut pandang klien , transaksi pada objek direplikasi harus muncul sama satu dengan benda-benda non direplikasi. Dalam sistem non direplikasi transaksi muncul harus dilakukan satu per satu dalam beberapa order. Hal ini dicapai dengan memastikan serial setara interleaving transaksi nasabah. Pengaruh dari seluruh transaksi yang dilakukan oleh klien pada objek direplikasi harus sama seperti jika mereka telah dilakukan satu per satu waktu pada satu set objek, Properti ini disebut satu copy serializability ini similar, tetapi tidak harus bingung dengan, konsistensi berurutan. konsistensi sekuensial menganggap eksekusi berlaku tanpa gagasan menggabungkan operasi client ke transaksi.     Setiap manajer replika menyediakan kontrol concurrency dan recovery sendiri Benda. Pada bagian ini, kita asumsikan bahwa penguncian dua fase digunakan untuk concurrency kontrol.    Pemulihan rumit oleh fakta bahwa seorang manajer replika gagal adalah anggota dari koleksi dan anggota lain terus memberikan layanan selama waktu yang itu tidak tersedia. Ketika seorang manajer replika pulih dari kegagalan, menggunakan informasi diperoleh dari mangers replika lainnya untuk mengembalikan benda-benda untuk nilai-nilai mereka saat ini, memperhitungkan semua perubahan yang telah terjadi selama waktu itu tidak tersedia.    Bagian ini pertama memperkenalkan arsitektur untuk transaksi dengan data direplikasi. pertanyaan arsitektur adalah apakah permintaan client dapat ditujukan kepada salah satu replika Managers: berapa banyak manajer replika yang diperlukan untuk sukses penyelesaian operasi: apakah manajer replika dihubungi oleh klien dapat menunda penyampaian permintaan sampai transaksi berkomitmen: dan bagaimana melaksanakan dua afase komit protokol.     Bagian ini kemudian membahas masalah pelaksanaan skema replikasi dikehadiran server crash dan pemulihan. Hal ini memperkenalkan salinan tersedia replikasi, varian dari read- satu / menulis semua skema replikasi di mana membaca operasi yang dilakukan oleh setiap manajer replika dan menulis operasi tunggal dilakukan oleh semua mereka yang tersedia.     Akhirnya, bagian ini menyajikan tiga skema replikasi yang bekerja dengan benar saat koleksi manajer replika dibagi menjadi subkelompok oleh partisi jaringan :

salinan Tersedia dengan validasi : salinan Tersedia replikasi diterapkan di masing-masing Partisi. Ketika partisi diperbaiki, prosedur validasi diterapkan dan setiap inkonsistensi yang ditangani.
Konsensus Kuorum : Sebuah subkelompok harus memiliki kuorum ( yang berarti bahwa ia memiliki anggota yang cukup ) untuk diizinkan untuk terus memberikan layanan dikehadiran partisi. Ketika partisi diperbaiki ( dan ketika manajer replika restart setelah kegagalan ), replika Managers mendapatkan benda mereka up- to-date dengan cara prosedur pemulihan .
partisi Virtual : Sebuah kombinasi dari konsensus kuorum dan salinan yang tersedia. Jika sebuah partisi virtual memiliki kuorum, dapat menggunakan tersedia replikasi salinan.
18.5.1 Arsitektur untuk transaksi replikasi    Seperti dengan berbagai sistem yang telah kita dipertimbangkan dalam bagian sebelumnya, depan sebuah end mungkin baik permintaan klien multicast kelompok manajer replika atau mengirim setiap permintaan untuk manajer replika tunggal, yang kemudian bertanggung jawab untuk memproses permintaan dan menanggapi klien. Wiesmann et al. [2000] dan Schiper dan Raynal [1996] mempertimbangkan kasus permintaan multicast, dan kami tidak akan membahasnya di sini. Untuk selanjutnya, kita berasumsi bahwa front end mengirimkan permintaan klien untuk salah satu kelompok manajer replika dari objek logis. Dalam pendekatan copy utama , semua berakhir depan berkomunikasi dengan dibedakan manager ' utama ' replika untuk melakukan operasi, dan replika yang Manajer membuat backup up- to-date . Atau , ujung depan dapat berkomunikasi dengan setiap manajer replika untuk perform operasi tapi koordinasi antara replikamanajer akibatnya lebih kompleks.      Manajer replika yang menerima permintaan untuk melakukan operasi pada tertentu objek bertanggung jawab untuk mendapatkan kerja sama dari para manajer replika lainnya di kelompok yang memiliki salinan dari objek itu. skema replikasi yang berbeda memiliki aturan yang berbeda untuk berapa banyak manajer replika dalam kelompok yang diperlukan untuk sukses selesainya operasi. Misalnya, dalam read- satu / menulis semua skema, read permintaan dapat dilakukan oleh seorang manajer replika tunggal, sedangkan permintaan tulis harus dilakukan oleh semua manajer replika dalam kelompok, seperti yang ditunjukkan pada Gambar 18.9 (ada dapat menjadi nomor yang berbeda dari replika dari berbagai objek). skema konsensus kuorum yang dirancang untuk mengurangi jumlah replika manajer yang harus melakukan operasi update, tapi dengan mengorbankan meningkatkan jumlah manajer replika yang dibutuhkan untuk melakukan read-only operasi .     Masalah lainnya adalah apakah manajer replika dihubungi oleh front end harus menunda forwarding update meminta kepada manajer replika lain dalam kelompok sampai setelah Transaksi melakukan yang disebut pendekatan malas untuk memperbarui propagasi  atau, gambar 18.9 Transaksi data replikasi      Sebaliknya, apakah manajer replika harus meneruskan setiap permintaan update ke semua manajer replika diperlukan dalam transaksi dan sebelum melakukan bersemangat pendekatan. Pendekatan malas adalah alternatif yang menarik karena mengurangi jumlah komunikasi antara manajer replika yang terjadi sebelum menanggapi memperbarui klien. Namun, kontrol konkurensi juga harus diperhatikan. Pemalas Pendekatan kadang-kadang digunakan dalam replikasi copy primer ( lihat di bawah ) , di mana satu Manajer replika utama serializes transaksi. Tetapi jika beberapa transaksi yang berbeda mungkin mencoba untuk mengakses objek yang sama pada manajer replika yang berbeda dalam kelompok, untuk memastikan bahwa transaksi dengan benar serial di semua manajer replika di kelompok, masing-masing manajer replika perlu tahu tentang permintaan yang dilakukan oleh orang lain. Pendekatan bersemangat adalah satu-satunya yang tersedia dalam kasus itu .Dua tahap melakukan protocol • dua tahap melakukan protokol menjadi dua tingkat bersarang dua fase komit protokol. Seperti sebelumnya, koordinator transaksi berkomunikasi dengan para pekerja. Tetapi jika salah satu koordinator atau pekerja adalah replika manager, itu akan berkomunikasi dengan manajer replika lain yang berlalu permintaan selama transaksi.    Artinya, pada tahap pertama, koordinator mengirimkan Cancommit ? permintaan ke pekerja, yang meneruskannya kepada manajer replika lainnya dan mengumpulkan jawaban mereka sebelum membalas koordinator. Pada tahap kedua, koordinator mengirimkan doCommit atau doAbort permintaan, yang diteruskan kepada para anggota kelompok manajer replika .Replikasi Salinan Utama • replikasi salinan utama dapat digunakan dalam konteks transaksi. Dalam skema ini, semua permintaan klien ( apakah atau tidak mereka hanya baca) adalah diarahkan ke manajer replika primer tunggal ( lihat Gambar 18.3 ). Untuk copy primer replikasi, kontrol konkurensi diterapkan di utama. Untuk melakukan transaksi, primer berkomunikasi dengan manajer replika cadangan dan kemudian, di bersemangat Pendekatan, balasan untuk klien . Bentuk replikasi memungkinkan manajer replika cadangan untuk mengambil alih secara konsisten jika primer gagal. Dalam alternatif malas, primer merespon untuk depan berakhir sebelum itu telah diperbarui backup  nya. Dalam hal ini, cadangan yang menggantikan gagal ujung depan tidak akan selalu memiliki negara terbaru dari database .Baca satu / write semua • Kami menggunakan skema replikasi sederhana ini untuk menggambarkan bagaimana dua fase penguncian pada setiap manajer replika dapat digunakan untuk mencapai satu- copy serializability, di mana ujung depan dapat berkomunikasi dengan manajer replika. Setiap operasi tulis harus dilakukan pada semua manajer replika , yang masing-masing menetapkan kunci menulis pada objek dipengaruhi oleh operasi . Setiap operasi baca dilakukan oleh seorang manajer replika tunggal, yang menetapkan kunci membaca pada objek yang terkena operasi .18.5.2 Tersedia salinan replikasi     Sederhana read- satu / menulis- semua replikasi bukan skema realistis, karena tidak bisa dilakukan jika beberapa manajer replika tidak tersedia, baik karena mereka memiliki jatuh atau karena kegagalan komunikasi. Skema salinan yang tersedia dirancang untuk memungkinkan beberapa manajer replika yang sementara tidak tersedia. Strategi ini adalah bahwa permintaan membaca klien pada objek logis dapat dilakukan oleh setiap replika yang tersedia Manajer tapi itu permintaan update klien harus dilakukan oleh semua replika tersedia manajer dalam kelompok dengan salinan objek. Ide dari ' anggota tersedia sekelompok manajer replika ' mirip dengan kelompok penyimpanan volume yang tersedia Coda ini, dijelaskan dalam Bagian 18.4.3 .     Dalam kasus normal, permintaan klien diterima dan dilakukan oleh fungsi yang Manajer replika. permintaan membaca dapat dilakukan oleh manajer replika yang menerima Mereka. menulis permintaan yang dilakukan oleh manajer replika menerima dan semua lainnya manajer replika yang tersedia dalam kelompok. Misalnya, pada Gambar 18.10, getBalance yang operasi transaksi T dilakukan oleh X, sedangkan operasi deposito dilakukan oleh M, kontrol N dan P. Concurrency pada setiap manajer replika mempengaruhi operasi dilakukan secara lokal. Misalnya, di X transaksi T telah membaca A dan karena transaksi U tidak diperbolehkan untuk memperbarui A dengan deposit operasi sampai transaksi T memiliki selesai. Selama set manajer replika yang tersedia tidak berubah , lokal kontrol konkurensi mencapai satu copy serializability dengan cara yang sama seperti di readone / menulis semua replikasi . Sayangnya, ini Tidak kasus jika replika Manajer gagal atau pulih Selama itu Kemajuan  dari bertentangan transaksi .Replika Kegagalan Manajer • Kami berasumsi bahwa manajer replika gagal benignly oleh menerjang. Namun, manajer replika jatuh diganti dengan proses baru, yang sembuh negara berkomitmen objek dari file recovery. Depan berakhir penggunaan time out untuk memutuskan bahwa seorang manajer replika saat ini tidak tersedia. Ketika klien membuat permintaan ke Manajer replika yang telah jatuh, kali ujung depan dan mencoba lagi permintaan di Manajer replika lain dalam kelompok. Jika permintaan tersebut diterima oleh seorang manajer replika di yang objek adalah dari tanggal karena manajer replika belum sepenuhnya pulih dari kegagalan, manajer replika menolak permintaan tersebut dan ujung depan retries permintaan di manager replika lain dalam kelompok .     Satu copy serializability mengharuskan crash dan pemulihan serial dengan sehubungan dengan transaksi. Menurut apakah itu dapat mengakses objek atau tidak, transaksi mengamati bahwa kegagalan terjadi setelah selesai atau sebelum dimulai. Satu copy serializability tidak tercapai ketika transaksi yang berbeda membuat kegagalan bertentangan pengamatan .











Gambar 18.10 salinan Tersedia

Pertimbangkan kasus pada Gambar 18.10 di mana manajer replika X gagal setelah T telah dilakukan getBalance dan manajer replika N gagal setelah U telah dilakukan getBalance. Asumsikan bahwa kedua manajer replika ini gagal sebelum T dan U memiliki dilakukan operasi deposito mereka. Ini berarti bahwa deposit T akan dilakukan pada manajer replika M dan P dan deposito U akan dilakukan pada replika manager Y. Sayangnya, kontrol konkurensi pada A pada manajer replika X tidak mencegah transaksi U dari memperbarui A pada manajer replika Y. Begitu juga concurrency yang kontrol pada B di manager replika N mencegah transaksi T memperbarui B di manajer replika M dan P.     Hal ini bertentangan dengan persyaratan untuk satu salinan serializability. Jika operasi ini yang akan dilakukan pada salinan tunggal dari objek, mereka akan serial baik dengan transaksi T sebelum U atau dengan transaksi U sebelum T. Hal ini memastikan bahwa salah satu transaksi akan membaca nilai yang ditetapkan oleh yang lain. kontrol konkurensi lokal pada salinan benda tidak cukup untuk memastikan satu copy serializability dalam salinan yang tersedia skema replikasi .     Seperti operasi menulis adalah directed untuk semua salinan yang tersedia, concurrency lokal kontroltidak memastikan bahwa bertentangan menulis pada objek yang serial. Sebaliknya, dibaca oleh satu transaksi dan menulis dengan yang lain tidak selalu mempengaruhi salinan yang sama dari sebuah objek. Oleh karena itu, skema memerlukan kontrol concurrency tambahan untuk mencegah ketergantungan antara operasi baca dari satu transaksi dan operasi tulis dari transaksi lain membentuk suatu siklus. dependensi tersebut tidak dapat timbul jika kegagalan dan pemulihan replika benda yang serial sehubungan dengan transaksi .Validasi Lokal • Kami mengacu pada tambahan prosedur kontrol konkurensi sebagai lokal validasi. Prosedur validasi lokal dirancang untuk memastikan bahwa setiap kegagalan atau Acara pemulihan tampaknya tidak terjadi selama proses transaksi. dalam kami Misalnya, seperti T telah membaca dari sebuah objek di X , kegagalan X harus setelah T. Demikian seperti T mengamati kegagalan N ketika mencoba untuk memperbarui objek, kegagalan N harus sebelum T. Itu adalah :   N gagal T berbunyi objek A di X: T menulis objek B di M dan P Tcommits X gagal Hal ini juga bisa dikatakan untuk transaksi U bahwa: X gagal U berbunyi objek B di N: U menulis objek A di Y Ucommits N gagal.    Prosedur validasi lokal memastikan bahwa dua seperti urutan kompatibel tidak bisa kedua terjadi. Sebelum transaksi melakukan cek untuk setiap kegagalan (dan pemulihan) dari manajer replika benda itu telah diakses. Dalam contoh, transaksi T akan memeriksa bahwa N masih tersedia dan X, M dan P masih tersedia. Jika hal ini terjadi, T bisa melakukan. Ini berarti bahwa X gagal setelah T divalidasi dan sebelum U divalidasi. di lain kata, validasi U adalah setelah validasi T,  validasi U gagal karena N memiliki sudah gagal.     Setiap kali transaksi telah mengamati fai iming-iming, prosedur validasi lokal mencoba untuk berkomunikasi dengan manajer replika gagal untuk memastikan bahwa mereka tidak belum pulih. Bagian lain dari validasi lokal, yang menguji replika yang manajer tidak gagal karena objek yang diakses, dapat dikombinasikan dengan twophase yang melakukan protokol.

Tersedia salinan algoritma tidak dapat digunakan dalam lingkungan di mana fungsi manajer replika tidak dapat berkomunikasi dengan satu sama lain.

18.5. partisi jaringan    skema replikasi perlu memperhitungkan kemungkinan partisi jaringan. Sebuah partisi jaringan memisahkan kelompok manajer replika menjadi dua atau lebih sub kelompok di sedemikian rupa sehingga para anggota satu sub kelompok dapat berkomunikasi dengan satu sama lain tapi anggota sub kelompok yang berbeda tidak dapat berkomunikasi dengan satu sama lain. Sebagai contoh, di Gambar 18.11, Manajer replika menerima permohonan deposit tidak dapat mengirimkannya ke manajer replika menerima w permintaan ithdraw .

skema replikasi dirancang dengan asumsi bahwa partisi akan akhirnya diperbaiki. Oleh karena itu, ia replika manajer dalam partisi keharusan tunggal memastikan bahwa setiap permintaan yang mereka jalankan selama partisi tidak akan membuat set replika tidak konsisten ketika partisi diperbaiki.

Gambar 18.11 partisi Jaringan



Davidson et al. [ 1985] membahas pendekatan yang berbeda , yang mereka kategorikan sebagai salah optimis atau pesimis berkenaan dengan apakah inkonsistensi cenderung terjadi. Skema optimis tidak membatasi ketersediaan selama partisi, sedangkan skema pesimis lakukan.

Pendekatan optimis memungkinkan update di semua partisi ini dapat menyebabkan inkonsistensi antara partisi yang harus diselesaikan ketika partisi diperbaiki. Contoh dari pendekatan ini adalah varian dari algoritma salinan tersedia di yang update yang diperbolehkan dalam partisi dan, setelah partisi telah diperbaiki, update divalidasi setiap pembaruan yang melanggar kriteria serializability satu copy yang dibatalkan.

Pesimis ketersediaan batas pendekatan bahkan ketika tidak ada partisi, tapi mencegah inkonsistensi yang terjadi selama partisi. Ketika partisi diperbaiki, semua yang perlu dilakukan adalah untuk memperbarui salinan dari objek. Konsensus kuorum Pendekatan pesimistis. Hal ini memungkinkan update di partisi yang memiliki mayoritas replika manajer dan Propag Atas update ke manajer replika lain ketika partisi diperbaiki .18.5.4  salinan tersedia dengan validasi   Algoritma salinan tersedia diterapkan dalam setiap partisi. Pendekatan optimis ini mempertahankan tingkat normal ketersediaan untuk operasi baca, bahkan selama partisi. Ketika partisi diperbaiki, transaksi mungkin bertentangan yang telah terjadi di partisi yang terpisah divalidasi. Jika validasi gagal, maka beberapa langkah harus diambil untuk mengatasi inkonsistensi. Jika tak ada partisi, salah satu dari sepasang transaksi dengan operasi yang saling bertentangan akan ditunda atau dibatalkan. Sayangnya, seperti yang telah ada partisi, pasang transaksi yang saling bertentangan telah diizinkan untuk melakukan di partisi yang berbeda. Satu-satunya pilihan setelah acara ini adalah untuk membatalkan satu dari mereka. Ini membutuhkan pembuatan perubahan dalam benda dan dalam beberapa kasus. kompensasi efek di dunia nyata, seperti berurusan dengan rekening bank tekor.  optimis Pendekatan ini hanya layak dengan aplikasi di mana tindakan kompensasi tersebut dapat

diambil .

vektor versi dapat digunakan untuk memvalidasi konflik antara pasangan write operasi. Ini digunakan dalam sistem file Coda dan dijelaskan dalam Bagian 18.4.3. Pendekatan ini tidak dapat mendeteksi baca tulis konflik tetapi bekerja dengan baik dalam file systems mana transaksi cenderung mengakses file tunggal dan membaca menulis konflik tidak penting. Bukan itu cocok untuk aplikasi seperti misalnya perbankan kita di mana baca tulis konflik yang penting.    Davidson [1984] digunakan grafik diutamakan untuk mendeteksi inkonsistensi antara Partisi. Setiap partisi mempertahankan log dari objek dipengaruhi oleh membaca dan menulis operasi transaksi. log ini digunakan untuk membangun grafik diutamakan yang node adalah transaksi dan yang ujung-ujungnya merupakan konflik antara membaca dan menulis operasi transaksi. Grafik tersebut tidak akan berisi siklus apapun, karena concurrency kontrol telah diterapkan dalam partisi. Prosedur validasi mengambil didahulukan grafik dari partisi dan menambahkan tepi,  mewakili konflik, antara transaksi dalam partisi yang berbeda. Jika grafik yang dihasilkan mengandung siklus maka validasi gagal.18.5.5 metode konsensus kuorum   Salah satu cara untuk mencegah transaksi di partisi yang berbeda dari memproduksi tidak konsisten Hasil ini membuat aturan bahwa operasi dapat dilakukan dalam hanya satu dari Partisi. Sebagai replika manajer di partisi yang berbeda tidak dapat berkomunikasi dengan satu Lain, sub kelompok manajer replika dalam setiap partisi harus mampu memutuskan independen apakah mereka diizinkan untuk melakukan operasi. Sebuah kuorum adalah subkelompok manajer replika yang ukurannya memberikan hak untuk melakukan operasi. Sebagai contoh, jika memiliki mayoritas adalah kriteria, sub kelompok yang memiliki mayoritas anggota dari kelompok akan membentuk kuorum karena tidak ada subkelompok lainnya bisa memiliki mayoritas.     Dalam skema replikasi konsensus kuorum operasi pembaruan pada obj logis dll dapat berhasil diselesaikan oleh subkelompok kelompoknya manajer replika. Itu anggota lain dari kelompok karena itu akan memiliki out-of -date salinan objek. Versi angka atau cap waktu dapat digunakan untuk menentukan apakah salinan up to–date. Jika versi yang digunakan, keadaan awal dari suatu objek adalah versi pertama, dan setelah setiap perubahan kita memiliki versi baru. Setiap salinan dari sebuah objek memiliki nomor versi, tetapi hanya salinan yang up to-date memiliki nomor versi saat ini, sedangkan out-of -date salinan memiliki nomor versi sebelumnya. Operasi harus diterapkan hanya untuk salinan dengan saat ini nomor versi .     Gifford [1979] mengembangkan skema replikasi file di mana sejumlah orang yang ditugaskan untuk setiap salinan fisik pada manajer replika file logis tunggal. Sebuah suara dapat dianggap sebagai bobot terkait dengan keinginan Using salinan tertentu. Setiap baca operasi pertama harus mendapatkan kuorum membaca dari R orang sebelum dapat melanjutkan untuk membaca dari setiap salinan up to-date, dan setiap operasi menulis harus mendapatkan tulis kuorum W memberikan suara sebelum dapat melanjutkan dengan operasi update. R dan W ditetapkan untuk sekelompok manajer replika seperti yang W > setengah total penilaian R + W > jumlah suara untuk group.Hal ini memastikan bahwa setiap pasang yang terdiri dari kuorum membaca dan menulis kuorum atau dua write Quora harus berisi salinan umum. Oleh karena itu jika ada partisi , itu tidak mungkin untuk melakukan operasi yang bertentangan pada salinan yang sama, tetapi dalam partisi yang berbeda.

Untuk melakukan operasi baca, kuorum baca dikumpulkan dengan membuat memadai nomor versi pertanyaan untuk menemukan satu set salinan, jumlah yang suaranya tidak kurang dari R. Tidak semua salinan tersebut perlu up- to-date. Karena setiap membaca kuorum tumpang tindih dengan setiap menulis kuorum, setiap baca kuorum yang pasti untuk menyertakan setidaknya satu salinan saat ini. Operasi membaca dapat diterapkan untuk setiap salinan up - to-date .

Untuk melakukan operasi write, kuorum tulis dikumpulkan dengan membuat memadai nomor versi pertanyaan untuk menemukan satu set manajer replika dengan up - to-date salinan, jumlah yang suaranya tidak kurang dari W. Jika ada cukup up- to-date eksemplar, maka File tidak lancar diganti dengan salinan file saat ini, untuk memungkinkan kuorum untuk menjadi mapan. Update ditentukan dalam operasi menulis kemudian diterapkan oleh masing-masing replika manager di tulis kuorum, nomor versi bertambah dan penyelesaian write dilaporkan ke klien.

File-file di manajer replika yang tersedia tersisa kemudian diperbarui oleh melakukan operasi write sebagai tugas latar belakang. Setiap manajer replika yang copy file memiliki nomor versi yang lebih tua dari yang digunakan oleh update tulis kuorum itu dengan mengganti seluruh file dengan salinan yang diperoleh dari seorang manajer replika yang up - todate .

Dua-fase baca-tulis penguncian dapat digunakan untuk kontrol concurrency di Gifford Reputasi Skema lication. The awal nomor versi penyelidikan untuk mendapatkan membaca kuorum,R, penyebab membaca kunci untuk ditetapkan pada masing-masing manajer replika dihubungi. Ketika operasi write diterapkan untuk menulis kuorum, W, kunci menulis diatur pada setiap manajer replika yang terlibat. (Kunci diterapkan dengan perincian yang sama seperti nomor versi). Kunci memastikan onecopy serializability, karena setiap baca kuorum tumpang tindih dengan apa saja write kuorum dan setiap dua menulis tumpang tindih Quora .Configurability kelompok manajer replika • Properti penting dari tertimbang algoritma voting adalah bahwa kelompok manajer replika dapat dikonfigurasi untuk memberikan kinerja atau keandalan yang berbeda karakteristik. Setelah keandalan umum dan kinerja kelompok manajer replika didirikan oleh konfigurasi voting nya, keandalan dan kinerja operasi tulis dapat ditingkatkan dengan menurunkan W dan juga untuk membaca dengan menurunkan R.    algoritma juga dapat memungkinkan untuk penggunaan copas file pada disk lokal di client komputer serta orang-orang di file server. Salinan dari file di komputer klien yang dianggap sebagai wakil lemah dan selalu dialokasikan nol orang . Hal ini memastikan bahwa mereka tidak termasuk dalam kuorum apapun. Sebuah operasi baca dapat dilakukan pada setiap up todate salinan, sekali kuorum membaca telah diperoleh. Oleh karena itu membaca operasi Mei menjadi Dilakukan keluar dari salinan lokal dari file jika itu adalah tanggal up-to.  Lemah perwakilan dapat bekas untuk mempercepat membaca operasi.Sebuah contoh dari Gifford • Gifford memberikan tiga contoh yang menunjukkan kisaran sifat yang dapat dicapai dengan mengalokasikan bobot untuk berbagai manajer replika dikelompok dan menugaskan R dan W tepat . Kami sekarang mereproduksi contoh Gifford, yang didasarkan pada tabel di bawah ini. Probabilitas blocking memberikan indikasi yang probabilitas bahwa kuorum tidak bisa didapatkan ketika membaca atau Permintaan tulis dibuat .



Contoh 1 dikonfigurasi untuk file dengan rasio baca-to-write tinggi dalam aplikasi dengan beberapa perwakilan lemah dan manajer replika tunggal. Replikasi digunakan untuk meningkatkan kinerja sistem, tidak keandalan. Ada satu manajer replika di jaringan lokal yang dapat diakses di 75 milidetik. Dua klien telah memilih untuk membuat perwakilan lemah pada disk lokal mereka, yang mereka dapat mengakses di 65 milidetik, sehingga latency rendah dan lalu lintas jaringan kurang.

Contoh 2 dikonfigurasi untuk file dengan read-to-write rasio moderat, yang diakses terutama dari satu jaringan lokal. Replika manajer di jaringan lokal menugaskan dua orang dan replikamanajer pada jaringan jarak jauh ditugaskan satu suara masing-masing. Membaca bisa puas dari manajer replika lokal, tapi menulis keharusan mengakses manajer replika lokal dan satu manajer replika terpencil. File akan tetap tersedia dalam modus read-only jika manajer replika lokal gagal. Klien bisa membuat lokal perwakilan lemah untuk membaca latency rendah.

Contoh 3 dikonfigurasi untuk file dengan rasio read -to - write sangat tinggi, seperti direktori sistem dalam lingkungan tiga - replika - manager . Klien dapat membaca dari setiap Manajer replik, dan probabilitas bahwa file tersebut akan tersedia kecil.  update harus diterapkan untuk semua salinan . Sekali lagi , klien bisa membuat perwakilan lemah pada mesin lokal mereka untuk latency membaca lebih rendah.

Herlihy [ 1986 ] mengusulkan perpanjangan metode konsensus kuorum untuk tipe data abstrak. Metode ini memungkinkan semantik operasi yang akan diambil ke dalam account, untuk meningkatkan ketersediaan objek. Metode Herlihy ini menggunakan cap bukannya nomor versi . Ini memiliki keuntungan bahwa tidak ada kebutuhan untuk membuat versi Jumlah pertanyaan untuk mendapatkan nomor versi baru sebelum melakukan write operasi. Keuntungan utama diklaim oleh Herlihy adalah bahwa penggunaan pengetahuan semantik dapat meningkatkan jumlah pilihan untuk kuorum.

konsensus kuorum di Dynamo • Dynamo menggunakan pendekatan kuorum seperti untuk menjaga konsistensi antara replika . Seperti skema Gifford , membaca dan menulis operasi harus menggunakan R dan W node masing-masing dan R + W > N. Dalam Dynamo, N adalah jumlah node dengan replika. Nilai-nilai W dan R mempengaruhi ketersediaan, daya tahan dan konsistensi. DeCandia et al. [2007 ] menyatakan bahwa konfigurasi umum di Dynamo memiliki

[ N , R , W ] = [ 3,2,2 ] .

Dalam kasus partisi, kuorum Gifford dapat beroperasi hanya dalam ' mayoritas ' partisi. Tapi Dynamo menggunakan’ceroboh kuorum’yang melibatkan N node, di mana replika Mei disimpan di node pengganti yang akan lulus pada nilai-nilai ketika node dimaksudkan pulih.18.5.6 algoritma partisi virtual     Algoritma ini, yang diusulkan oleh El Abbadi et al. [ 1985] menggabungkan kuorum Pendekatan konsensus dengan algoritma salinan tersedia. karya konsensus kuorum benar di hadapan partisi tetapi algoritma salinan tersedia kurang mahal untuk operasi baca. Sebuah partisi virtual adalah sebuah abstraksi dari partisi yang nyata dan berisi satu set manajer replika. Perhatikan bahwa istilah ' partisi jaringan ' mengacu pada.Gambar 18.12 Dua partisi jaringan

penghalang yang membagi manajer replika menjadi beberapa bagian , sedangkan istilah 'virtual partisi’ mengacu pada bagian sendiri. Meskipun mereka tidak terhubung dengan multicast komunikasi, partisi virtual yang mirip dengan tampilan kelompok, yang kita diperkenalkan pada Bagian 18.2.2. Sebuah transaksi dapat beroperasi dalam partisi virtual jika mengandung cukup manajer replika memiliki kuorum membaca dan menulis kuorum untuk objek diakses. Di hal ini, transaksi menggunakan algoritma salinan tersedia . Ini memiliki keuntungan bahwa baca operasi perlu hanya pernah mengakses satu salinan dari sebuah objek dan dapat meningkatkan kinerja dengan memilih copy terdekat. Jika seorang manajer replika gagal dan virtual perubahan partisi selama transaksi, maka transaksi dibatalkan. Hal ini memastikan onecopy serializability transaksi karena semua transaksi yang bertahan melihat kegagalan dan pemulihan manajer replika di sana memesan.

Anggaplah, misalnya , bahwa kita memiliki empat manajer replika, V, X, Y dan Z, masing-masing yang memiliki satu suara, dan bahwa membaca dan menulis Quora adalah R = 2 dan W = 3. Awalnya, semua manajer dapat menghubungi satu sama lain. Asalkan mereka tetap berhubungan, mereka dapat menggunakan algoritma salinan tersedia. Sebagai contoh, T transaksi yang terdiri dari read diikuti oleh operasi tulis akan melakukan membaca pada manajer replika tunggal ( untuk Misalnya V ) dan menulis operasi di keempat dari mereka .   Misalkan transaksi T dimulai dengan melakukan readnya di V pada saat V adalah masih berhubungan dengan X, Y dan Z. Sekarang anggaplah bahwa partisi jaringan terjadi seperti pada Gambar 18.12, Di mana V dan X berada di salah satu bagian dan Y dan Z berada dalam yang berbeda. Lalu kapan transaksi T mencoba menerapkan menulis nya, V akan melihat bahwa itu tidak dapat menghubungi Y dan Z.

Ketika seorang manajer replika tidak bisa menghubungi manajer yang sebelumnya bisa menghubungi, saya terus mencoba sampai bisa membuat partisi virtual baru. Misalnya, V akan terus mencoba untuk menghubungi Y dan Z sampai satu atau keduanya balasan-seperti, misalnya, pada Gambar 18.13, ketika Y dapat diakses. Kelompok manajer replika V, X dan Y terdiri partisi virtual karena mereka cukup untuk membentuk membaca dan menulis Quora .

Ketika sebuah partisi virtual yang baru dibuat selama transaksi yang telah melakukan operasi di salah satu manager replika ( seperti transaksi T ) transaksi harus dibatalkan . Selain itu, replika dalam partisi virtual baru harus dibawa up-to Tanggal dengan menyalin mereka dari replika lainnya. nomor versi dapat digunakan sebagai di Gifford algoritma untuk menentukan salinan up-to –date. Sangat penting bahwa semua replika upto-date, karena membaca Operasi dilakukan pada setiap tunggal replika .  Gambar 18.13 partisi Virtual Implementasi partisi virtual • Sebuah partisi virtual memiliki waktu penciptaan, satu set calon anggota dan satu set anggota yang sebenarnya. kali penciptaan adalah cap waktu logis. Para anggota yang sebenarnya dari partisi virtual tertentu memiliki ide yang sama untuk penciptaan waktu dan keanggotaan (pandangan bersama manajer replika dengan yang mereka dapat menyampaikan). Misalnya, pada Gambar 18.13 para anggota potensial V, X, Y, dan Z dan anggota yang sebenarnya adalah V, X dan Y.

Penciptaan partisi virtual baru dicapai dengan protokol koperasi dilakukan oleh orang-orang dari anggota potensial yang dapat diakses oleh replika manajer yang memprakarsai itu. Beberapa manajer replika mungkin mencoba untuk membuat virtual baru simultaneously. Misalnya, bahwa manajer replika Y dan Z ditampilkan pada Gambar 18.12 terus membuat upaya untuk hubungi orang lain, dan setelah beberapa saat jaringan partisi sebagian diperbaiki sehingga Y tidak dapat berkomunikasi dengan bu Z t dua kelompok V, X, Y dan V, X, Z dapat berkomunikasi di antara mereka sendiri. Maka ada bahaya bahwa dua partisi virtual tumpang tindih, seperti V Gambar 18.14 Dua partisi virtual yang tumpang tindih Virtual partisi V11 dan V2 ditunjukkan pada Gambar 18.14, Mungkin keduanya menjadi dibuat.

Mempertimbangkan efek dari EXECUT transaksi yang berbeda dalam dua partisi virtual. Membaca operasi transaksi di V, X, Y, diterapkan pada manajer replika Y, dalam hal kunci membaca yang tidak akan bertentangan dengan menulis kunci ditetapkan oleh operasi tulis dari transaksi di partisi virtual lainnya . partisi virtual tumpang tindih bertentangan satu-copy serializability.       Tujuan dari protokol adalah untuk membuat partisi virtual baru secara konsisten, bahkan jika nyatapartisi terjadi selama protokol . Protokol untuk membuat partisi virtual baru memilikidua  tahap. seperti yang ditunjukkan pada Gambar 18.15 .

Seorang manajer replika yang menjawab Ya di fase 1 bukan milik sebuah partisi virtual sampai menerima pesan Konfirmasi sesuai pada fase 2.

Gambar 18.14 Dua partisi virtual yang tumpang tindih

Gambar 18.15 Membuat partisi virtual

tahap 1 :

Inisiator mengirimkan Bergabung permintaan untuk masing-masing anggota potensial. Dalil Bergabung adalah timestamp logis diusulkan untuk partisi virtual baru .
Ketika seorang manajer replika menerima permintaan Bergabung, itu membandingkan diusulkan logis timestamp dengan yang dari partisi virtual saat ini.
- Jika timestamp logis diusulkan lebih besar itu setuju untuk bergabung dan balasan Ya ;

- Jika kurang , menolak untuk bergabung dan balasan No.

Tahap 2 :

Jika inisiator telah menerima cukup Ya balasan untuk membaca dan menulis Quora , it dapat menyelesaikan pembuatan partisi virtual baru dengan mengirimkan Konfirmasi pesan ke situs yang setuju untuk bergabung . Penciptaan timestamp dan daftar aktual anggota yang dikirim sebagai argumen .
manajer Replica menerima pesan Konfirmasi bergabung dengan virtual baru partisi dan merekam timestamp penciptaan dan daftar anggota yang sebenarnya. Dalam contoh di atas, manajer replika Y dan Z yang ditunjukkan pada Gambar 18.12 setiap mencoba untuk membuat partisi virtual, dan mana yang memiliki timestamp logis yang lebih tinggi akan menjadi salah satu yang digunakan pada akhirnya .
Ini merupakan metode yang efektif ketika partisi yang tidak kejadian umum. Setiap transaksi menggunakan algoritma salinan tersedia dalam partisi virtual.

18.6 ringkasan

Mereplikasi objek merupakan cara penting untuk mencapai layanan dengan kinerja yang baik,

ketersediaan tinggi dan toleransi kesalahan dalam sistem terdistribusi . Kami dijelaskan arsitektur

untuk layanan di mana manajer replika memegang replika benda, dan di mana ujung depan membuat replikasi ini transparan. Klien, ujung depan dan manajer replika mungkin proses terpisah atau ada di ruang alamat yang sama .

Bab ini dimulai dengan menggambarkan model sistem yang setiap objek logis adalah dilaksanakan oleh satu set replika fisik. Seringkali, update untuk replika ini dapat dibuat nyaman dengan komunikasi kelompok. Kami memperluas rekening kami dari kelompok komunikasi untuk memasukkan pandangan kelompok dan melihat synchronous komunikasi.

Kami mendefinisikan linearizability dan kontra berurutan istency sebagai kriteria kebenaran untuk layanan toleran . Kriteria ini mengungkapkan bagaimana layanan harus memberikan setara dengan satu gambar dari set objek logis, meskipun benda-benda yang direplikasi. Yang paling praktis yang signifikan dari kriteria adalah konsistensi berurutan .

Dalam pasif replikasi ( primary - backup ) oleransi kesalahan dicapai dengan mengarahkan semua permintaankasar manajer replika dibedakan dan memiliki replika cadangan Manajer mengambil alih jika ini gagal . Dalam replikasi aktif , semua manajer replika memproses semua permintaan secara independen . Kedua bentuk replikasi dapat dengan mudah diimplementasikan menggunakan komunikasi kelompok .

Selanjutnya kita dianggap layanan sangat tersedia. Gosip dan Bayou kedua memungkinkan klien untuk membuat update untuk replika lokal sementara dipartisi. Dalam setiap sistem, replika

manajer pertukaran informasi satu sama lain ketika mereka menjadi terhubung kembali. Gosip menyediakan ketersediaan tertinggi dengan mengorbankan santai, konsistensi kausal. Bagian sungai yg berawa memberikan jaminan konsistensi akhirnya kuat, mempekerjakan konflik otomatis deteksi dan teknik transformasi operasional untuk menyelesaikan konflik. Coda adalah sistem file sangat tersedia yang menggunakan versi vektor untuk mendeteksi berpotensi bertentangan update.

Akhirnya, kita dianggap kinerja transaksi terhadap data direplikasi. Kedua arsitektur utama-backup dan arsitektur di mana ujung depan mungkin communicate dengan manajer replika ada untuk kasus ini. Kami membahas bagaimana sistem transaksional memungkinkan untuk kegagalan manajer replika dan partisi jaringan. Itu teknik salinan yang tersedia, konsensus kuorum dan partisi virtual mengaktifkan operasi dalam transaksi untuk membuat kemajuan bahkan dalam beberapa keadaan di mana tidak semua replika yang dicapai.