PERTEMUAN X (SISTEM TERDISTRIBUSI)

CHAPTER 6
CONSISTENCY AND REPLICATION

6.3.2 Monotonic Reads

            Klien-sentris model konsistensipertama adalahmonotonmembaca. Sebuah datatokodikatakanuntuk memberikanmonoton-baca konsistensijika kondisiberikutmemegang:

            Jikaprosesmembacanilaibarangyangx data, setiapoperasi bacaberturut-turutpada xoleh prosesyangakan selalu kembalibahwa nilaiyang samaataulebihterakhirnilai dengan kata lain, monoton-baca konsistensimenjamin bahwajika suatu prosestelah melihatnilai xpada waktu t, makatidak akan pernah melihatversi lamadari xdi lain waktu.

            Sebagaicontohdi manadibacamonotonberguna, mempertimbangkanemaildidistribusikandatabase.Dalamdatabase, setiap kotak suratpenggunadapatdidistribusikandandireplikasidi beberapa mesin. Mail dapatdimasukkan ke dalamkotak suratdisetiap lokasi. Namun, pembaruandisebarkandengan cara(yaitu, on demand) malas. Hanyaketikasalinanmemerlukan datatertentuuntuk konsistensiyangmerekadata yangdisebarkan keyangsalin. Misalkanpenggunamembacasurat-suratnyadiSanFrancisco. Asumsikan bahwamembacahanyamail tidakmempengaruhikotak surat, yaitu, pesan tidakdihapus, disimpan dalamsubdirektori, atau bahkanditandaisebagai yangsudahdibaca, dansebagainya. Ketikapenggunakemudianterbang keNewYorkdan membukakotaklagi, monoton-baca konsistensijaminanbahwapesan yangada dikotak suratdiSanFranciscoakanjugaberada dikotak suratketikadibukadi NewYork.

            Menggunakannotasiserupa dengandata-centric modelkonsistensi, monoton-membaca konsistensidapatdiwakiligrafisseperti yang ditunjukkanpada Gambar. 6-12. Sepanjang sumbu vertikal, dua salinanlokal yang berbedadari tokodata yangditampilkan, LIdanL2. Waktu ditampilkandi sepanjangsumbuhorisontalseperti sebelumnya. Dalamsemua kasus.

 

            tertarikdalam operasiyang dilakukan olehprosesP.tunggalinioperasi khususditampilkan dalamhuruf tebaldihubungkan olehgaris putus-putusmewakiliurutandi mana merekadilakukan olehP.

            Gambar6-12. Readoperasi yang dilakukanolehPproses tunggaldi duaberbedalokalsalinanmenyimpan datayang sama. (a) monoton-baca yang konsistendatumenyimpan. (b) Sebuah tokodata yangtidak menyediakanmonotonmembaca.

            Dalam Gambar. 6-l2 (a), prosesPpertamamelakukan operasibacapada xdiLI, kembalinilaiXl(pada waktu itu). Ini hasilnilai darioperasimenulis di
WS(x I) dilakukan padaLI. Kemudian, Pmelakukan operasibacapada xdiL2, ditampilkan sebagaiR(X2) 'Untuk menjaminmonoton-baca konsistensi, semua operasidiWS(x 1) harustelahdisebarkan keL2sebelum operasimembacakeduaberlangsung. dilainkata, kita perlumengetahui dengan pasti bahwaWS(xI) adalahbagian dariWS(x 2) 'yang dinyatakan sebagaiWS(xI;X2) '

            Sebaliknya, Gambar. 6-l2 (b) menunjukkansituasi di manamonoton-baca konsistensitidak dijamin. SetelahprosesPtelah membacax IdiLI, nantimelakukanoperasiR(X2) diL2. Namun, hanya operasimenulisdiWS(X2) telah dilakukandiL2•Tidak adajaminanyangdiberikanbahwaset inijuga berisisemua operasiterkandung dalamWS(xI) '.

6.3.3 Monotonic Writes

            Dalam banyak situasi, penting bahwa operasi menulis disebarkan dalam
yang benar untuk semua salinan menyimpan data. Properti ini dinyatakan dalam monoton- menulis konsistensi. Dalam sebuah toko monoton-menulis yang konsisten, berikut Kondisi memegang:

            Sebuahoperasi menulisdengan prosespadaxitem dataselesaisebelum
menulisberturutoperasi padaXolehproses yang sama sehingga menyelesaikanoperasi tulisberartibahwa salinanyangoperasiberturut-turutdilakukanmencerminkanefek darioperasi penulisansebelumnya olehyang samaProses, tidak peduli di manaoperasiyang diprakarsai. Dengan kata lain, operasiwritepada salinanitemxdilakukan hanyajika salinanyang telahdibawa ketanggaldengan carasetiapmenulis operasisebelumnya, yangmungkintelah terjadipadalainnyasalinandari x. Jikaperlumenjadi,menulisbaru harusmenungguyang lamauntuk menyelesaikan.

            Perhatikan bahwamonoton-menulis konsistensimenyerupaidata-centric konsistensiFIFO. Inti darikonsistensiFIFOadalah bahwamenulis operasiolehproses yang samadilakukandalam urutan yang benardi mana-mana. Inikendalajugamemesanberlaku untukmonotonmenulis, kecuali bahwakita sekarangmempertimbangkankonsistensihanyauntukproses tunggalbukanuntuk koleksiproses konkuren.

            Membawasalinandari xmutakhirtidak perludiperlukan ketikasetiap operasimenulisbenar-benarmenimpanilai sekarangdari x. Namun, operasi menulisadalahsering dilakukanpada bagian-satunya negaradariitem data. Perhatikan, misalnya,software perpustakaan. Dalambanyak kasus, memperbaruisepertiperpustakaandilakukan denganmengganti satuatau lebihfungsi, yang mengarah keversi berikutnya. Denganmonoton-menulis konsistensi, jaminanyangdiberikanbahwa jikapembaruan tersebutdilakukan padasalinanperpustakaan, semuaupdatesebelumnyaakandilakukan pertama. Perpustakaanyang dihasilkanakanmaka sesungguhnyamenjadiversi terbarudan akanmencakup semuapembaruan yangtelah menyebabkansebelumnyaversiperpustakaan.

           

6.3.4 Read Your Writes

            Seorang klien-sentris konsistensimodel yangberkaitan erat denganmonotonmembacaadalah sebagaiberikut. Sebuah tokoDatadikatakanuntuk menyediakanbaca-tulis-Anda konsistensi, jikaKondisiberikut ini berlaku:

            Efek darioperasi penulisanoleh prosespada xitem dataakan selalu
dilihat olehoperasibacaberuntunpada xolehproses yang samadengan kata lain, operasi tulisselaluselesai sebelumoperasi bacaberturut-turutolehproses yang sama, di mana punbahwa operasimembacaberlangsung.

            Tidak adanyaread--Anda menuliskonsistensikadang-kadangdialami saat
memperbaruidokumenWebdan kemudianmelihatefek. Perbaruioperasiseringterjadidengan carapengolahkataeditor ataustandar, yangmenyimpanversi barupada sistemfile yangdibagioleh serverWeb. Itubrowser Webpenggunamengaksesfile yang sama, mungkin setelah meminta itudariWeb serverlokal. Namun, setelahfile tersebuttelahdiambil, baikserveratauBrowserseringcachesalinanlokal untukaksesberikutnya. Akibatnya, ketika
halamanwebdiperbarui, pengguna tidakakanmelihatefekjika browseratauServermengembalikansalinan cachebukandari file asli. Baca-Anda-menulis konsistensidapat menjaminbahwa jikaeditordan browseryang terintegrasimenjadi satuprogram,cachetidak validketika halamandiperbarui, sehinggadiperbaruifilediambildan ditampilkan.

            Efek yang samaterjadi ketikamemperbaruipassword. Misalnya, untuk memasukkandigitalPerpustakaandi Web, itu sering perluuntukmemiliki accountdenganmenyertainyasandi. Namun, mengubahpasswordmembuat mengambilbeberapa waktuuntuk datangberlaku, dengan hasil bahwaperpustakaanmungkindapat diakses bagi penggunauntuk beberapamenit. Penundaandapat disebabkankarenaserver terpisahyangdigunakanuntuk mengelolapassworddanmungkin diperlukanbeberapa waktuuntuk kemudianmenyebarkan(dienkripsi) passwordkeberbagai serveryang merupakanperpustakaan.

         

6.3.5 Writes Follow Reads

            Modelkonsistensiklien-sentristerakhir adalahsatu di manaupdatedisebarkansebagai hasil darioperasi membacasebelumnya.Sebuah tokodata yangdikatakanuntuk memberikanmenulis-tindak membacakonsistensi,

Sebuahoperasi menulisdenganprosespadaxitem datasetelahmembaca sebelumnyaoperasi padax olehproses yang samadijaminuntuk mengambiltempat disama ataunilaiyang lebih barudari xyang dibacakan.

            Dengan kata lain, setiapmenulis operasiberturut-turutoleh suatu prosespadaxitem dataakandilakukan padasalinandari xyangup to date dengannilai yang palingbaru-baru inidibaca olehbahwa proses

            Menulis-tindak membacakonsistensidapat digunakan untukmenjamin bahwapenggunajaringannewsgroupmelihatpostingreaksi terhadapsebuah artikelhanya setelahmereka telah melihatartikel asli(Terry etaI., 1994). Untukmemahami masalah, menganggap bahwapengguna pertamamembaca sebuahartikelA.Kemudian, iabereaksidengan mem-postingB.responDengan mensyaratkanmenulis-tindak membacakonsistensi, Bakanditulisuntuk setiapsalinannewsgrouphanya setelahAtelahditulisjuga.Perhatikan bahwapengguna yanghanya membacaartikelperlutidak memerlukanmodel klien-sentris konsistensitertentu. Menulis-followsreads konsistensimenjamin bahwareaksi terhadapartikeltersebutdisimpandi sebuahsalinan lokalhanyajikaaslidisimpandi sana juga.

         

6.4 DISTRIBUTION PROTOCOLS

6.4.1 REPLICA MANAGEMENT

Marikita sekarangmenjauhdari penempatanserver danberkonsentrasi padakontenpenempatan. Ketika datang kereplikasikontendan penempatan, tiga berbedajenisreplikadapat dibedakansecara logisseperti ditunjukkan pada Gambar. 6 – 16

Replikapermanendapat dianggapsebagaiset awalreplikayang merupakantokodata terdistribusi. Dalambanyak kasus, jumlahreplikapermanenkecil. Perhatikan, misalnya, sebuah situsWeb. Distribusidari sebuah situsWebumumdatang dalamsalah satudaridua bentuk. Jenis pertama daridistribusiadalah satu di manafileyang merupakansitusyangdireplikasi disejumlahserverdi satulokasi. Setiap kalipermintaan datang, ituditeruskan kesalah satu server, untukMisalnya, menggunakan strategiround-robin.

            BentukkeduasitusWebterdistribusi adalahapa yang disebutmirroring. dalamhal inikasus, sebuah situsWebakan disalin kesejumlahserver, disebutsitusmirror. yangsecara geografistersebar diInternet. Dalamkebanyakan kasus, klienhanyapilihsalah satudarisitus mirorberbagaidari daftaryang ditawarkan kepada mereka. Cerminv. 'Eb situsmemiliki kesamaandengan clusterberbasissitusWeb yangadahanya sejumlahbeberapareplika, yanglebih atau kurangstatisdikonfigurasi.

            Organisasi-organisasistatisserupa jugamuncul dengandatabasedidistribusikan(OSZu danValduriez, 1999). Sekali lagi, databasedapat didistribusikandandireplikasidi seluruh~\jumlah serveryang bersama-samamembentuksebuah clusterofserver, sering disebut sebagai~\berbagiapa-apa-arsitektur, menekankanbahwa baikdiskmaupunmemori utama dibagi olehprosesor. Atau, databasedidistribusikandan mungkindireplikasidisejumlah situsgeografis. Arsitektur iniumumnyadikerahkan difederasidatabase(Sheth danLarson, 1990).

Server-Initiated Replicas

            Berbeda denganreplikapermanen, serverdimulaireplikaadalah salinandaridata yangtoko yangada untukmeningkatkankinerja danyangdibuatatas inisiatifdengan(pemilik) menyimpan data. Perhatikan, misalnya, serverWebplacedinNewYork. Biasanya, server inidapat menanganipermintaan yang masukcukupmudah, tetapimungkinterjadi bahwaselama beberapahariledakan tiba-tibapermintaandatangdaritak terdugalokasijauh dariserver. Dalam hal ini, mungkinakan bermanfaat untukmenginstalsejumlahreplikasementaradi daerah di manapermintaanberasal.

            Masalahreplikadinamismenempatkanjuga sedangdibahasdi Web
layanan hosting. Layanan inimenawarkan koleksi(relatif statis) dariservertersebar diInternet yangdapatmemelihara danmenyediakan akseske fileWebmilikpihak ketiga. Untukmenyediakan fasilitasyang optimallayanan hostingtersebutbisadinamismereplikasifile keserverdi manafile-fileyang diperlukanuntuk meningkatkankinerja, yaitu,dekat denganmenuntut(kelompok) klien.

            Mengingatbahwaserverreplikasudah di tempat, memutuskanmanauntuk menempatkankontenlebih mudah daripadadalam kasuspenempatan server. Sebuahpendekatandinamisreplikasifile dalamhallayananWeb hostingdijelaskan dalamRabinovichetal. (1999). Algoritmaini dirancanguntuk mendukunghalamanwebyang untuk alasan inimengasumsikan bahwaupdaterelatif jarangdibandingkan denganmembaca permintaan. Menggunakanubinsebagaiunitdata, algoritma bekerjasebagai berikut.

            Algoritma untukreplikasidinamismembutuhkandua isuke rekening.pertama,
replikasidapat berlangsunguntuk mengurangibeban padaserver. Kedua, khususfile padaserverdapatbermigrasiataudireplikasike serverditempatkan didekatklienIsubahwa banyakpermintaan untukfile-file. Pada halaman berikut, kami berkonsentrasihanya padamasalahkedua. Kami jugameninggalkansejumlah rincian, yang dapatditemukan diRabinovichetal. (1999).

            Setiap servermelacakjumlahaksesper file, dan di manapermintaan akses
berasal dari. Secara khusus, diasumsikan bahwa, diberiCclient, server masing-masingdapatmenentukanmana dariserverdalam layananWeb hostingpaling dekat denganC.(seperti Informasidapat diperoleh, misalnya, dari routingdatabase.) Jika klienC1dan klienC2berbagisama"paling dekat" server P, permintaan aksessemua untukFatberkasServerQ darielandC2bersama-samaterdaftar diQsebagaijumlahakses tunggalcntQ(P, F). Situasi iniditunjukkan pada Gambar. 6-18.

            KetikajumlahpermintaanuntukFfile tertentudi serverSturun di bawah
penghapusanambangdel(S, F), file yangdapatdihapus dariS.Akibatnya, jumlahreplikadari fileyangberkurang, mungkin mengarah kepekerjaanyang lebih tinggi

bebandiserver lain. Langkah-langkah khususdiambiluntuk memastikanbahwa setidaknyasatu salinansetiap fileteruseksis.

            Ambang batas replikasi rep (5, F), yang selalu dipilih lebih tinggi dari
ambang penghapusan, menunjukkan bahwa jumlah permintaan untuk file tertentu begitu tinggi yang mungkin bermanfaat replikasi di server lain. Jika jumlahpermintaan terletak di suatu tempat antara ambang penghapusan dan replikasi, file tersebut diperbolehkan hanya untuk bermigrasi. Dengan kata lain, dalam kasus ini penting untuk setidaknya menjaga jumlah replika untuk file yang sama.

            Ketika server Q memutuskan untuk mengevaluasi kembali penempatan file menyimpan, itu memeriksa jumlah akses untuk setiap file. Jika jumlah permintaan akses untuk F di Q turun di bawah ambang batas penghapusan del (Q, F), akan menghapus F kecuali itu adalah lalu copy. Selanjutnya, jika untuk beberapa server P, cntQ (p, F) melebihi lebih dari setengah permintaan total untuk F di Q, server P diminta untuk mengambil alih salinan F. Dalam Dengan kata lain, server Q akan mencoba untuk bermigrasi ke F P.

            MigrasiFfile ke serverPmungkin tidak selaluberhasil, misalnya, karena
Psudahbanyak dimuatataukeluar dariruang disk. Dalam hal ini, QakanuntukmeniruFpada server lain. Tentu saja, replikasidapat terjadihanya jikatotaljumlah permintaanakses untukFdi Qmelebihiambangreplikasirep(Q, F). ServerQmemeriksasemua serverlainnyadalamlayanan Webhosting,dimulai dengansatuterjauh. Jika, untukbeberapa serverR, cntQ(R, F) ex-Ceeds sebagiantertentu darisemua permintaanuntukFdi Q, dilakukan usahauntuk meniruFkeR.

            Server-replikasi dimulaiTerusMENINGKATpopularitasnyadiwaktu, terutamaIllustrasikonteksLAYANANweb hostingsepertiYangBaruSajadijelaskan. PT BUMIbahwaselamaJaminandapatdiberikanbahwasetiapitem datadi-host olehsetidaknyaSatuserver,mungkincukupuntukmenggunakanreplikasiServerdimulaiSajaDantidakmemilikipermanenreplika. Namundemikian, replikapermanenMasihseringbergunasebagaiback-upfasilitas, atauuntukdigunakansebagaireplikasatunyaYangdiijinkanuntukdiubahuntukmenjaminkonsistensi. ReplikaServer-diprakarsai kemudiandigunakanuntukmenempatkandibacasalinanDekatArtikel BaruKlien.

Client-Initiated Replicas

            Suatujenispenting darireplikaadalahsalah satudiprakarsai olehklien. Klien-diprakarsai replikayanglebih dikenal sebagai(client) cache. Pada dasarnya, cache adalah sebuahfasilitas penyimpananlokal yangdigunakan olehklienuntuk sementaramenyimpansalinandataitu baru sajadiminta. Pada prinsipnya, mengelolacachesepenuhnya diserahkan kepadaklien. Menyimpan datadari manadatatelahdiambiltidak ada hubungannyadengan menjagacachedata yang konsisten. Namun, seperti yang akan kitalihat, adabanyak kesempatandimana klien dapatmengandalkanpartisipasi darithe.datatoko untukmenginformasikanketikaDatacachetelah menjadibasi.

            Cacheklienhanya digunakanuntuk meningkatkanwaktu akseske data. Biasanya, ketikaklien inginakses kebeberapa data, terhubung kesalinanterdekatdarimenyimpan datadari mana iamengambil datayangingin membaca, atauke tempat itumenyimpan dataituhanya diubah. Ketikaoperasipaling melibatkandata hanyamembaca, kinerjabisaditingkatkandengan membiarkantokoclientmeminta datadalam cachedekatnya. SepertiCachedapatterletakpada mesinklien, ataupada mesin yang terpisahdilokal yang sama-area jaringan sebagai klien. Lain kalidata yang samaperlubaca, klien hanyadapatmengambilnya daricache lokalini. Skemainibekerja dengan baikasalkandatadiambilbelumdimodifikasiuntuk sementara.

            Dataumumnyadisimpandalam cacheuntukwaktu terbatas, misalnya,
untuk mencegahdata yang sangatbasidari yang digunakan, atau hanyauntuk membuat ruang untuklainnyaData. Setiap kali datayang dimintadapat diambildaricache lokal, sedikitcachedikatakan telah terjadi. Untukmeningkatkanjumlahcache hits, cachedapat dibagiantara klien. Asumsi yang mendasarinya adalahbahwa permintaandata dariclientC1mungkin jugaberguna untukpermintaan dariklien lainterdekatC2·

            Apakahasumsiini benarsangat tergantungpada jenisdata yangmenyimpan. Sebagai contoh, dalam sistemfile tradisional, file datajarangberbagisama sekali(lihat, misalnya, MuntzdanHoneyman, 1992, dan Blaze, 1993)rendercachebersamaberguna. Demikian juga, ternyatamenggunakancachewebuntuk berbagidata jugakehilanganbeberapa tanah, sebagian jugakarenapeningkatanjaringan dankinerja server. SkemareplikasiSebaliknya, server-diprakarsai menjadilebih efektif.

            Penempatancacheklienrelatif sederhana: cachebiasanyaditempatkan padamesin yang sama sebagaiklien, ataupada mesinbersama olehklienpadalokal yang sama-area network. Namun, dalam beberapakasus, tingkattambahancachingdalahdiperkenalkan olehadministrator sistemdengan menempatkancachedibagi antaranomordepartemenatau organisasi, atau bahkanmenempatkanshared cacheuntukseluruhwilayahsepertiprovinsiatau negara.

            Namunpendekatan lainadalah untuk menempatkan(cache) serverpada titik-titiktertentu dalamWideareajaringan danbiarkanklienmencariserverterdekat. Ketikaserverberada, dapatdimintauntuk memegangsalinandataklienyang sebelumnyamengambildari tempat lain, seperti yang dijelaskan dalamaletNoble. (1999). Kamiakan kembali kecachingkemudian dalambab iniketika membahasprotokolkonsistensi.

6.4.2 Pembaruan Propagasi (update Propagation)

Pembaruan operasi pada sebuah penyimpanan  data terdistribusi dan replikasi umumnya diinisiasi  pada klien dan kemudian diteruskan ke salah satu salinan. Dari sana, pembaruan harus disebarkan ke salinan lain, sementara pada saat yang sama memastikan konsistensi. Ada isu desain yang berbeda untuk dipertimbangkan sehubungan dengan propagating update, yang akan kita bahas selanjutnya.

State  versus Operasi

Suatu hal penting menyangkut apa yang sebenarnya harus disebarkan. Pada dasarnya, ada tiga kemungkinan;

·         Menyebarkan hanya pemberitahuan pembaruan.

·         Mentransfer data dari satu salinan ke yang lainnya.

·         Menyebarkan operasi update untuk salinan lain.

Propagasi adalah sebuah pemberitahuan pembatalan yang  protokol lakukan. Dalam invalidation protokol, salinan lainnya diberitahu bahwa update telah terjadi dan bahwa Data yang dikandungnya tidak lagi berlaku. Pembatalan dapat menentukan bagian mana dari menyimpan data telah diperbarui, sehingga hanya sebagian dari salinan sebenarnya tidak valid. Isu penting adalah bahwa tidak lebih dari pemberitahuan disebarkan. Kapan saja operasi pada salinan batal diminta, copy yang umumnya perlu diperbarui pertama, tergantung pada model konsistensi tertentu yang akan didukung.

Keuntungan utama dari protokol pembatalan adalah bahwa mereka menggunakan jaringan kecil bandwidth. Satunya-satunya informasi yang perlu ditransfer adalah spesifikasi Data yang tidak lagi berlaku. Protokol seperti umumnya bekerja terbaik ketika ada operasi update banyak dibandingkan dengan membaca operasi, yaitu, read-to-write rasio relatif kecil.

Perhatikan, misalnya menyimpan data di mana update yang disebarkan oleh pengirim  data dimodifikasi untuk semua replika. Jika ukuran data yang dimodifikasi besar, dan update sering terjadi dibandingkan dengan operasi baca, kita mungkin memiliki situasi bahwa dua update terjadi setelah satu sama lain tanpa operasi membaca menjadi terbentuk antara mereka. Akibatnya, penyebaran update pertama untuk semua replika secara efektif tidak berguna, karena akan ditimpa oleh update kedua. Sebaliknya, pengiriman pemberitahuan bahwa data telah dimodifikasi akan lebih efisien.

Mentransfer data modifikasi antara replika adalah alternatif kedua, dan berguna ketika rasio tindak baca tulis relatif tinggi. Dalam hal ini, probabilitas bahwa update akan efektif dalam arti bahwa data modifikasi akan dibaca sebelum update berikutnya terjadi sangat tinggi. Alih-alih data yang dimodifikasi menyebar, ini juga memungkinkan untuk log perubahan dan transfer log hanya untuk menghemat bandwidth. Selain itu, transfer sering dikumpulkan dalam arti beberapa modifikasi dikemas ke dalam satu pesan, sehingga menghemat overhead komunikasi.

Pendekatan ketiga adalah untuk tidak mentransfer data modifikasi sama sekali, tapi untuk memberitahu setiap replika yang memperbarui operasi itu harus tampil. Pendekatan ini, juga disebut sebagai replikasi aktif, mengasumsikan bahwa setiap replika diwakili oleh Proses mampu "aktif" menjaga data yang terkait up to date dengan performa operasi. Manfaat utama dari replikasi aktif adalah bahwa update sering dapat diperbanyak dengan biaya bandwidth yang minim, memberikan ukuran parameter yang terkait dengan operasi yang relatif kecil. Di sisi lain tangan, kekuatan pemrosesan yang lebih mungkin diperlukan oleh setiap replika, terutama ketika operasi relatif kompleks.

Pull vs Push Protocol

Isu lain desain adalah apakah update ditarik atau didorong. Dalam pendekatan push-based, juga disebut sebagai server berbasis protokol. pembaruan propagasi dengan replika lain tanpa mereka replika bahkan meminta pembaruan. Push-based pendekatan yang sering digunakan antara pemianent dan server-dimulai replika, tetapi juga dapat digunakan untuk mendorong pembaruan ke cache klien. Server berbasis protocols diterapkan saat replika umumnya perlu untuk mempertahankan tingkat yang relatif tinggi konsistensi. Dengan kata lain, replika harus disimpan identik.

Hal ini perlu untuk tingkat tinggi konsistensi berkaitan dengan fakta bahwa permanent dan server dimulai replika, serta cache bersama besar, sering bersama oleh banyak klien, yang, pada gilirannya, terutama melakukan operasi baca. Akibatnya, baca-to-update rasio di setiap replika relatif tinggi. Dalam kasus ini, push-based protokol yang efisien dalam arti bahwa setiap update mendorong dapat diharapkan penggunaan untuk satu atau lebih pembaca. Selain itu. push-based protokol membuat konsisten Data segera tersedia ketika meminta. Sebaliknya, dalam pendekatan pull-based, sebuah permintaan server atau klien lain server untuk mengirim update itu pada saat itu. Tarik-berbasis protokol, jugadisebut client berbasis protokol, sering digunakan oleh cache klien. Misalnya, Strategi umum diterapkan untuk cache Web, adalah pertama untuk memeriksa apakah data cache item masih ujung sampai saat ini. Ketika cache menerima permintaan untuk barang-barang yang masih
tersedia secara lokal, cache memeriksa dengan server Web aslinya apakah mereka
item data telah dimodifikasi sejak mereka cache. Dalam kasus modifikasition, data dimodifikasi yang pertama dipindahkan ke cache, dan kemudian kembali ke
meminta klien. Jika tidak ada modifikasi berlangsung, data cache yang retumed. Di
Dengan kata lain, klien server jajak pendapat untuk melihat apakah pembaruan tersebut diperlukan.

Pendekatan tarik berbasis efisien ketika rasio read-to-update relatif rendah. Hal ini sering terjadi dengan (nonshared) cache klien, yang hanya memiliki satuclient. Namun. bahkan ketika cache dibagi oleh banyak klien, Pendekatan berbasis tarikini juga mungkin terbukti menjadi efisien ketika item data cache jarangberbagi. Kelemahan utama dari strategi tarik-berbasis dibandingkan dengan push-Pendekatan berbasis, adalah bahwa waktu respon meningkat dalam kasus cache miss.Ketika membandingkan solusi berbasis push dan pull-based, ada sejumlahtrade-off yang akan dibuat, seperti ditunjukkan pada Gambar. 6-26. Untuk mempermudah, menganggap klien sistem server yang terdiri dari satu, server nondistributed, dan sejumlah klien proses, masing-masing memiliki cache mereka sendiri.
"U2Push-based Isu Pull-based

Gambar : Sebuah perbandingan antara protokol berbasis push dan berbasis pull pada
kasus beberapa klien, sistem server tunggal.

Suatu hal yang penting adalah bahwa dalam push-based protokol, server perlu untuk menjaga melacak dari semua cache klien. Terlepas dari kenyataan bahwa server stateful sering kurang fault tolerant, seperti yang kita bahas dalam Bab. 3, melacak semua cache klien mungkin memperkenalkan overhead yang cukup di server. Sebagai contoh, dalam sebuah Pendekatan berbasis push, server Web mungkin perlu untuk melacak puluhan ribu client cache. Setiap kali sebuah halaman web diperbarui, server akan perlu melalui daftar dari cache klien memegang salinan halaman tersebut, dan kemudian menyebarkan update. Lebih parah lagi, jika klien pembersihan halaman karena kurangnya ruang, itu harus menginformasikan server, yang mengarah ke komunikasi bahkan lebih. Pesan yang perlu dikirim antara klien dan server juga berbeda. Dalam pendekatan berbasis push, komunikasi satunya adalah bahwa server akan mengirimkan pembaruan untuk setiap klien. Ketika update sebenarnya invalidations saja, tambahan komunikasi- kation yang dibutuhkan oleh klien untuk mengambil data dimodifikasi. Dalam pendekatan pull-based, a klien akan harus polling server, dan, jika perlu, mengambil data dimodifikasi. Akhirnya, waktu respon di klien juga berbeda. Ketika server mendorong dimodifikasi data ke cache klien, jelas bahwa waktu respon pada klien Sisi adalah nol. Ketika invalidations didorong, waktu respon adalah sama seperti dalam pendekatan tarik-based, dan ditentukan oleh waktu yang dibutuhkan untuk mengambil modi- fied data dari server.

Ini trade-off telah mengarah ke bentuk hibrida propagasi pembaruan berdasarkan sewa. Sewa adalah janji oleh server yang akan mendorong pembaruan kepada klien untuk waktu yang ditentukan. Ketika sewa berakhir, klien dipaksa untuk polling server untuk update dan menarik dalam data dimodifikasi jika perlu. Sebuah alternatif adalah bahwa klien permintaan sewa baru untuk mendorong pembaruan ketika sewa sebelumnya berakhir. Sewa awalnya diperkenalkan oleh Gray dan Cheriton (1989). Mereka pro- vide mekanisme nyaman untuk secara dinamis beralih antara push-based dan pull-based strategi. Duvvuri et al. (2000) menggambarkan sistem sewa yang fleksibel yang memungkinkan waktu kedaluwarsa untuk secara dinamis disesuaikan tergantung pada berbagai sewa kriteria. Mereka membedakan tiga jenis berikut sewa. (Perhatikan bahwa dalam semua kasus, pembaruan didorong oleh server asalkan sewa belum berakhir.)

Pertama, usia berbasis sewa yang diberikan pada item data tergantung pada waktu terakhir item telah dimodifikasi. Asumsi yang mendasarinya adalah bahwa data yang belum dimodifikasi untuk waktu yang lama dapat diharapkan untuk tetap dimodifikasi untuk beberapa waktu lagi untuk datang. Asumsi ini telah terbukti akal dalam kasus berbasis Web Data. Dengan pemberian jangka panjang sewa untuk item data yang diperkirakan akan tetap dimodifikasi, jumlah pesan pembaruan dapat sangat berkurang dibandingkan dengan kasus di mana semua sewa memiliki waktu kedaluwarsa yang sama. Kriteria lain sewa adalah seberapa sering sebuah permintaan klien tertentu salinan cache harus diperbarui. Dengan perpanjangan sewa frekuensi berbasis, server akan membagikan sebuah tahan lama sewa untuk klien yang cache yang sering perlu refresh. Di sisi lain, seorang klien yang meminta hanya kadang-kadang untuk item data tertentu akan menyerahkan sewa jangka pendek untuk item tersebut. Efek dari strategi ini adalah bahwa Server pada dasarnya hanya melacak dari klien-klien berdasarkan data yang populer; apalagi, klien-klien akan disuguhi konsistensi tingkat tinggi. Kriteria terakhir adalah bahwa negara-space overhead pada server. Ketika server menyadari bahwa itu secara bertahap menjadi kelebihan beban, menurunkan waktu berakhirnya baru sewa itu tangan ke klien. Efek dari strategi ini adalah bahwa server perlu melacak klien sedikit sebagai sewa berakhir lebih cepat. Dengan kata lain, server secara dinamis beralih ke modus yang lebih bernegara operasi, sehingga pembongkaran sendiri sehingga dapat menangani permintaan lebih efisien.

Unicasting versus Multicasting

Terkait dengan mendorong atau menarik update memutuskan apakah unicasting atau multicasting harus digunakan. Dalam komunikasi unicast, ketika sebuah server yang merupakan bagian dari menyimpan data mengirimkan pembaruan untuk server N lainnya, ia melakukannya dengan mengirimkan pesan untuk N secara terpisah, satu untuk setiap server. Dengan multicasting, jaringan yang mendasari mengambil perawatan mengirim pesan ke beberapa penerima efisien.

Dalam banyak kasus, lebih murah untuk menggunakan fasilitas multicasting. Sebuah Situasi ekstrim adalah ketika semua replika yang terletak di jaringan lokal-daerah yang sama dan tersedia penyiaran hardware. Dalam hal ini, penyiaran atau multicasting pesan tidak lebih mahal daripada pesan point to point tunggal. Unicasting update kemudian akan kurang efisien. Multicasting sering dapat efisien dikombinasikan dengan pendekatan berbasis push untuk menyebarkan update. Dalam hal ini, sebuah server yang memutuskan untuk mendorong pembaruan untuk sebuah jumlah server lain hanya menggunakan grup multicast tunggal untuk mengirim pembaruan tersebut. Sebaliknya, dengan pendekatan pull-based, itu umumnya hanya klien tunggal atau server yang meminta salinannya harus diperbarui. Dalam hal ini, unicasting mungkin adalah  solusi paling efisien.

6.4.3 Epidemi Protokol

Tadi telah dijelaskan bahwa untuk memberikan konsistensi sudah cukup untuk menyimpan banyak data. Dengan kata lain, tanpa adanya pembaruan, maka akan menjadi replika yang identik. Pembaruan propagasi dalam data yang konsisten memiliki pembekalan yang sering diimplementasikan oleh kelas algoritma dan dikenal sebagai protokol epidemi. Algoritma epidemi tidak memecahkan setiap update solusi konflik yang terpisah digunakan. Sebaliknya, satu-satunya kekhawatiran mereka adalah propagating update untuk semua replika sebagai pesan sesedikit mungkin. Untuk tujuan ini, update sering dikumpulkan ke dalam satu pesan, dan kemudian dipertukarkan antara dua server. Algoritma epidemi membentuk dasar untuk sistem Bayou dijelaskan sebelumnya.

Untuk menjelaskan prinsip-prinsip umum dari algoritma ini, kita asumsikan bahwa semua update untuk item data tertentu dimulai pada server tunggal. Dengan cara ini, kita hanya menghindari konflik tulis-menulis.

Update Model Propagasi

Seperti namanya, algoritma epidemi didasarkan pada teori epidemics, yang mempelajari penyebaran penyakit menular. Dalam kasus repli- kombatan menyimpan data, bukan penyakit menyebar, mereka menyebar update. Penelitian tentang epidemi untuk menyimpan data juga memiliki tujuan yang sama sekali berbeda: bahwa kesehatan organisasi akan melakukan yang terbaik untuk mencegah penyebaran penyakit menular dari seluruh kelompok besar orang, perancang algoritma epidemi terdistribusi menyimpan data akan mencoba untuk menginfeksi'' semua replika dengan update baru secepat mungkin. Menggunakan terminologi dari epidemi, server yang merupakan bagian dari terdistribusi menyimpan data disebut infeksi jika memegang update bahwa mereka bersedia untuk menyebar ke lainnya server. Sebuah server yang belum diperbarui, disebut rentan. Akhirnya, server diperbarui yang tidak mau atau mampu untuk menyebarkan pembaruan nya, dikatakan dihapus. Sebuah model propagasi populer adalah bahwa anti-entropi. Dalam model ini, server P mengambil lain Q Server secara acak, dan kemudian pertukaran update dengan Q. Ada tiga pendekatan untuk bertukar update:

1. P hanya mendorong pembaruan sendiri untuk Q

2. P hanya menarik update baru dari Q

3. P dan Q mengirim pembaruan satu sama lain (misalnya, pendekatan push-pull)

Ketika update cepat menyebar, hanya update mendorong ternyata menjadi pilihan yang buruk. Secara intuitif, ini dapat dipahami sebagai berikut. Pertama, perhatikan bahwa dalam pendekatan berbasis push murni, update dapat diperbanyak hanya oleh server infektif. Namun, jika server banyak infeksi, kemungkinan masing-masing memilih Server rentan relatif kecil. Akibatnya, kemungkinan bahwa tertentu server tetap rentan untuk jangka panjang hanya karena tidak dipilih oleh server infektif. Sebaliknya, pendekatan berbasis tarik bekerja lebih baik ketika banyak server yang infektif. Dalam hal ini, update menyebarkan pada dasarnya dipicu oleh rentan server. Kemungkinan besar bahwa seperti server akan menghubungi salah satu infeksi ke sub- sequently menarik di update dan menjadi infektif juga. Hal ini dapat menunjukkan bahwa jika hanya server tunggal adalah infeksi, update gilirannya akan- sekutu tersebar di semua server baik menggunakan bentuk anti-entropi. Namun, untuk memastikan bahwa update menyebar dengan cepat, masuk akal untuk menggunakan tambahan mekanisme di mana setidaknya sejumlah server segera menjadi lebih atau kurang infektif. Biasanya, secara langsung mendorong update ke sejumlah server membantu. Salah satu varian tertentu dari pendekatan ini disebut rumor menyebar, atau hanya bergosip. Ia bekerja sebagai berikut. Jika server P baru saja diperbarui untuk item data x, maka kontak yang Q server yang sewenang-wenang lainnya dan mencoba untuk mendorong update ke Q. Namun, Ada kemungkinan bahwa Q sudah diperbarui oleh server lain. Dalam hal ini, P akan kehilangan minat menyebarkan update lebih lanjut, mengatakan dengan probabilitas 1 / k. Di lain kata, kemudian menjadi dihapus.

Menghapus data

Algoritma epidemi yang baik untuk menyebarkan update di akhir-konsisten menyimpan data. Namun, mereka memiliki efek samping yang agak aneh: menyebarkan deletion dari item data yang sulit. Inti dari masalah terletak pada kenyataan bahwa penghapusan dari item data yang menghancurkan semua informasi pada item tersebut. Akibatnya, ketika data item dihapus dari server, server yang pada akhirnya akan menerima salinan item lama data dan menafsirkan sebagai update pada sesuatu yang tidak dimiliki sebelumnya.

Caranya adalah dengan mencatat penghapusan item data hanya sebagai update saja. Dengan cara ini, salinan lama tidak akan ditafsirkan sebagai update baru, tetapi hanya diperlakukan sebagai versi yang telah diperbarui oleh suatu operasi. Pencatatan penghapusan ini dilakukan dengan menyebarkan sertifikat penghapusan. Tentu saja, masalah dengan sertifikat penghapusan adalah bahwa mereka akhirnya harus dibersihkan, atau server masing masing secara bertahap akan membangun sebuah local database besar sejarah informasi pada item data yang dihapus yang lain tidak digunakan. Demers et al. mengusulkan untuk menggunakan apa yang mereka sebut sertifikat penghapusan aktif. Setiap sertifikasi penghapusan yang timestamped ketika dibuat. Jika dapat diasumsikan bahwa update merambat untuk semua server dalam waktu yang terbatas, oleh karena itu sertifikat penghapusan dapat dihapus setelah waktu propagasi maksimum telah berlalu. Namun, untuk memberikan jaminan penghapusan keras yang memang menyebar ke seluruh server, server hanya sangat sedikit mempertahankan sertifikat kematian aktif yang tidak pernah dibuang. Asumsikan Server P memiliki seperti sertifikat untuk x item data. Jika oleh kesempatan update usang untuk mencapai x P, P akan bereaksi dengan hanya menyebarkan kematian sertifikat untuk x lagi.

6.5 CONSISTENCY PROTOCOLS

 Dalam bagian ini, kita berkonsentrasi pada pelaksanaan aktual dari model konsistensi dengan mengambil melihat beberapa contoh protokol konsistensi. Sebuah protokol konsistensi menggambarkan sebuah implementasi dari model konsistensi tertentu. Oleh dan besar, model konsistensi di mana operasi  secara global serial adalah model yang paling penting dan banyak digunakan. Model-model ini termasuk konsistensi sekuensial, konsistensi lemah dengan variabel sinkronisai serta transaksi atom. Dalam bagian ini, kami mempertimbangkan berbagai cara untuk menerapkan model konsistensi.

Menggunakanpendekatanawaldijelaskan dalam(Stumm danZhou, 1990), protokoluntuk konsistensisekuensialdapat diklasifikasikandengan mempertimbangkanapakahatau tidakada salinanutamadatayangmenulissemuaoperasiharusditeruskan. Bila tidak adasalinanprimerseperti itu ,menulis operasidapatdimulai padasetiapreplika.

6.5.1 Primary-Based Protocols

Dalamprimerberbasisprotokol, setiap item dataxdalammenyimpan datamemilikidiasosiasikanprimerdiciptakan, yang bertanggung jawabuntuk mengkoordinasikanmenulisoperasi pada x. Sebuahperbedaan dapat dibuatsebagai utamatetap padaremote serveratau jikaoperasimenulisdapatdilakukansecara lokalsetelah memindahkanutama untukprosesdi manamenulis operasidimulai.

Remote-WriteProtocol

Protokol utamaberbasissederhanaadalahsalah satudi mana semuamembaca dan menulisoperasi dilakukanpadaserver(remote) tunggal.Akibatnya, data tidakdireplikasikansama sekali, melainkanditempatkandi sebuahserver tunggaldi manamereka tidakdapat dipindahkan. Model inisecara tradisionaldigunakan dalamsistem client-server, di manaservermungkin dapatdidistribusikan. Protokol iniditunjukkan pada Gambar. 6-27.

W1. Write request W2. Forward request to server for x W3. Acknowledge write completed W4. Acknowledge write completed R1. Read request R2. Forward request to server for x R3. Return response R4. Return response

Figure 6-27. Primary-based remote-write protocol with a fixed server to which all read and write operations are forwarded.

Yangutamamelakukanupdate padasalinanlokaldari x, dan kemudianmeneruskanupdate keservercadangan. Setiapserver cadanganmelakukanupdatejuga, danmengirimkanpengakuankembali kedasar. Ketika semuabackupsalinan lokalmerekaprimermengirimkanpengakuankembali keproses awal.

W1. Write request                     R1. Read request                                      

W2. Forward request to primary         R2. Response to read

W3. Tell backups to update

W4. Acknowledge update

W5. Acknowledge write completed

Figure 6-28. The principle of a primary-backup protocol.

Masalahkinerja potensialdengan skemainiadalah bahwa hal itumungkinmemakanwaktu yangrelative lama sebelumprosesyang mulaidiupdatediperbolehkanuntuk melanjutkan.
Akibatnya, updatediimplementasikansebagai operasimemblokir. Sebuah alternatifadalah dengan menggunakanpendekatannonblocking. Segera setelahutamatelahdiperbaruisalinanlokaldari x, ia mengembalikanpengakuan.Setelah itu, ia memberitahuservercadangan untukmelakukan updatejuga.. Nonblockingutama-backup protokolyangdibahas dalamBudhirajadanMarzullo, 1992).

Masalahutama dengannonblockingprimer-backup protokolharus dilakukan dengantoleransi kesalahan. Dalamskemamemblokir, proses klientahu pastibahwaoperasi updatedidukung olehserverlainnya.Initidak terjadidengansolusinonblocking. Kita kembali kemasalahtoleransi kesalahansecara ekstensifdalam bab berikutnya.Primer-backup protokolmenyediakan implementasilangsung darikonsistensisekuensial, sebagaiprimer dapatmemesan semuamasukmenulis. Terbukti, semua prosesmelihat semuamenulis operasidalam urutan yang sama, tidak peduli yangbackupserver yang mereka gunakanuntuk melakukanoperasi baca. Juga, denganmemblokirprotokol, prosesakan selalumelihat efek darimenulis operasiterbarumereka(catatan bahwa hal ini tidakdapat dijamindengan protokolnonblocking, tanpa mengambiltindakanspecial).

Lokal-WriteProtocol

Ada duajenisutamaberbasislokalwrite protocol. Jenis yang pertama adalahsatu di manahanya adasatu salinandarisetiap xitem data. Dengan kata lain, tidak adareplika. Setiap kali suatu prosesinginmelakukan operasipada beberapaitem data, salinantunggalbahwa itemdatapertamaditransfer keproses, setelahoperasi dilakukan. Protokol inipada dasarnyamenetapkanversipenuhdisnonreplicatedtributeddarimenyimpan data. Konsistensisangat mudahkarena selalu adahanyasatu salinandari setiapitem data. Protokol iniditunjukkan pada Gambar. 6-29.

Salah satu masalahutama denganpendekatan inisepenuhnyamigrasi, yangmelacakdi manasetiap item datasaat ini. Seperti telah dibahasdalam Bab. 4, untuk lokal-daerah  solusiyang mendasarisiaranfasilitasdapat digunakan. Alternatifsolusiadalahpenggunaanpointerforwardingdan rumahberbasis pendekatan. Solusitersebuttelah diterapkan diterdistribusisistemmemori bersama(lihat, misalnya, LidanHudak, 1989). Namun, ketikamenyimpan dataskala besardanluas-terdistribusi digunakan, mekanisme lainyangdiperlukan, seperti layananlokasihirarkisseperti yangdibahasdalam Bab. 4.
Sebuah variandari protokolsetempat-menulis saja dijelaskanadalahdasar-backup protocoldi manacopyutamabermigrasiantara prosesyanginginmelakukan operasimenulis. Seperti sebelumnya, setiap kaliprosesingin memperbaruix dataitem,itumenempatkansalinanutamax,dan kemudianbergerak kelokasi sendiri, seperti yang ditunjukkanpada Gambar. 6-30. Keuntunganutama daripendekatan ini adalah bahwabeberapa, keberhasilan¬Operasi tuliskomprehensifdapatdilakukansecara lokal, sedangkanprosesmembacamasih dapat mengaksessalinan lokalmereka.Namun, sepertiperbaikandapat dicapaihanya jikaprotokolnonblockingdiikuti olehyang updateyangdisebarkankereplikasetelahutamatelah menerimaupdate, seperti yang kitajelaskan di atas. Protokol initelah diterapkan untukberbagai sistemmemoriterdistribusibersama.

 

Figure 6-29. Primary-based local-write protocol in which a single copy is mi­grated between processes.

6.5.2  Replicated-Write Protocols

Dalam direplikasi-menulis protokol, menulis operasi dapat dilakukan pada beberapa replika, bukan hanya satu, seperti dalam kasus primer berbasis replika. Perbedaan dapat dibuat antara replikasi aktif, di mana operasi diteruskan ke semua replika, dan protokol konsistensi berdasarkan suara mayoritas.

Aktif Replikasi

Dalam replikasi aktif, replika masing-masing memiliki proses terkait yang melakukan operasi update. Berbeda dengan protokol lain, update umumnya diperbanyak dengan cara menulis operasi yang menyebabkan update. Dengan kata lain, operation dikirim ke setiap replika. Namun, hal ini juga memungkinkan untuk mengirim update, seperti didiskusikan sebelumnya.

Salah satu potensi masalah dengan replikasi aktif adalah bahwa operasi harus dilakukan dalam urutan yang sama di mana-mana. Akibatnya, apa yang dibutuhkan adalah mekanisme multicast benar-memerintahkan. Seperti multicast dapat diimplementasikan dengan menggunakan cap waktu Lamport, seperti yang dibahas dalam bab sebelumnya. Sayangnya, menggunakan cap waktu Lamport tidak skala baik dalam sistem terdistribusi yang besar. Sebagai asli, pemesanan total dapat dicapai dengan menggunakan koordinator pusat, juga disebut sebuah sequencer. Salah satu pendekatan adalah untuk pertama meneruskan setiap operasi ke sequencer, yang memberikan sebuah nomor urut yang unik dan kemudian ke depan operasi untuk semua replika. Operasi dilakukan dalam urutan nomor urut mereka. Jelas, ini pelaksanaan multicasting benar-memerintahkan sangat mirip primer berbasis protokol konsistensi.

Perhatikan bahwa menggunakan sequencer yang tidak memecahkan masalah skalabilitas. Bahkan, jika multicasting benar-memerintahkan diperlukan, kombinasi multicasting simetris menggunakan cap waktu Lamport dan sequencer mungkin diperlukan. Solusi seperti dijelaskan dalam (et al Rodrigues, 1996.). Masalah lain yang perlu dipecahkan adalah bahwa doa direplikasi. Pertimbangkan obyek A menyerukan lain B objek seperti ditunjukkan pada Gambar. 6-31. Obyek B diasumsikan untuk memanggil yang lain C. Jika objek objek B direplikasi, setiap replika B akan, pada prinsipnya, memanggil C objek independen. Masalahnya adalah bahwa obyek C kini dipanggil beberapa kali, bukan hanya sekali. Jika metode dipanggil pada hasil C dalam transfer sebesar $ 100.000, maka jelas, seseorang akan mengeluh cepat atau lambat.

Figure 6-29. Primary-based local-write protocol in which a single copy is mi­grated between processes.

6.5.2  Replicated-Write Protocols

Dalam direplikasi-menulis protokol, menulis operasi dapat dilakukan pada beberapa replika, bukan hanya satu, seperti dalam kasus primer berbasis replika. Perbedaan dapat dibuat antara replikasi aktif, di mana operasi diteruskan ke semua replika, dan protokol konsistensi berdasarkan suara mayoritas.

Aktif Replikasi

Dalam replikasi aktif, replika masing-masing memiliki proses terkait yang melakukan operasi update. Berbeda dengan protokol lain, update umumnya diperbanyak dengan cara menulis operasi yang menyebabkan update. Dengan kata lain, operation dikirim ke setiap replika. Namun, hal ini juga memungkinkan untuk mengirim update, seperti didiskusikan sebelumnya.

Salah satu potensi masalah dengan replikasi aktif adalah bahwa operasi harus dilakukan dalam urutan yang sama di mana-mana. Akibatnya, apa yang dibutuhkan adalah mekanisme multicast benar-memerintahkan. Seperti multicast dapat diimplementasikan dengan menggunakan cap waktu Lamport, seperti yang dibahas dalam bab sebelumnya. Sayangnya, menggunakan cap waktu Lamport tidak skala baik dalam sistem terdistribusi yang besar. Sebagai asli, pemesanan total dapat dicapai dengan menggunakan koordinator pusat, juga disebut sebuah sequencer. Salah satu pendekatan adalah untuk pertama meneruskan setiap operasi ke sequencer, yang memberikan sebuah nomor urut yang unik dan kemudian ke depan operasi untuk semua replika. Operasi dilakukan dalam urutan nomor urut mereka. Jelas, ini pelaksanaan multicasting benar-memerintahkan sangat mirip primer berbasis protokol konsistensi.

Perhatikan bahwa menggunakan sequencer yang tidak memecahkan masalah skalabilitas. Bahkan, jika multicasting benar-memerintahkan diperlukan, kombinasi multicasting simetris menggunakan cap waktu Lamport dan sequencer mungkin diperlukan. Solusi seperti dijelaskan dalam (et al Rodrigues, 1996.). Masalah lain yang perlu dipecahkan adalah bahwa doa direplikasi. Pertimbangkan obyek A menyerukan lain B objek seperti ditunjukkan pada Gambar. 6-31. Obyek B diasumsikan untuk memanggil yang lain C. Jika objek objek B direplikasi, setiap replika B akan, pada prinsipnya, memanggil C objek independen. Masalahnya adalah bahwa obyek C kini dipanggil beberapa kali, bukan hanya sekali. Jika metode dipanggil pada hasil C dalam transfer sebesar $ 100.000, maka jelas, seseorang akan mengeluh cepat atau lambat.

Kuorum Berbasis Protokol

Sebuah pendekatan yang berbeda untuk mendukung direplikasi menulis adalah dengan menggunakan suara sebagai original diusulkan oleh Thomas (1979) dan umum oleh Gifford (1979). Ide dasarnya adalah untuk meminta klien untuk meminta dan memperoleh izin dari beberapa server sebelum baik membaca atau menulis item data direplikasi. Sebagai contoh sederhana tentang bagaimana algoritma bekerja, mempertimbangkan sistem file terdistribusi dan menganggap bahwa sebuah file direplikasi pada server N. Kita bisa membuat aturan yang menyatakan bahwa untuk memperbarui file, klien harus terlebih dulu menghubungi setidaknya setengah ditambah satu server (mayoritas) dan membuat mereka setuju untuk melakukan update. Begitu mereka telah sepakat, file berubah dan sejumlah versi baru dikaitkan dengan file baru. Nomor versi yang digunakan untuk mengidentifikasi versi dari file dan adalah sama untuk semua file yang baru diperbarui.

Untuk membaca file direplikasi, klien juga harus menghubungi setidaknya setengah ditambah satu server dan meminta mereka untuk mengirim nomor versi yang terkait dengan file tersebut. Jika semua nomor versi setuju, ini harus menjadi versi terbaru karena upaya untuk memperbarui hanya server yang tersisa akan gagal karena tidak ada cukup dari mereka.
Misalnya, jika ada lima server dan klien menentukan bahwa tiga dari mereka memiliki versi 8, tidak mungkin bahwa dua lainnya memiliki versi 9. Setelah semua,
setiap update sukses dari versi 8 ke versi 9 membutuhkan mendapatkan tiga server setuju untuk itu, bukan hanya dua.

Skema Gifford sebenarnya agak lebih umum daripada ini. Di dalamnya, untuk membaca file yang ada replika N, klien perlu merakit kuorum membaca, sebuah koleksi trary dari setiap server NR, atau lebih. Demikian pula, untuk memodifikasi file, kuorum menulis setidaknya server Nw diperlukan. Nilai-nilai NR dan Nw tunduk pada dua kendala berikut:

1. Nr + Nw> N

2. Nw> N / 2

Kendala pertama digunakan untuk mencegah baca-tulis konflik, sedangkan sccond mencegah tulis-menulis konflik. Hanya setelah jumlah yang tepat dari server telah setuju untuk berpartisipasi dapat file dibaca atau ditulis. Untuk melihat bagaimana algoritma ini bekerja, pertimbangkan Gambar. 6-33 (a), yang memiliki NR = 3 dan Nw = 10. Bayangkan bahwa kuorum menulis terbaru terdiri dari 10 server C melalui L. Semua ini mendapatkan versi baru dan nomor versi baru. Setiap kuorum membaca selanjutnya dari tiga server harus mengandung setidaknya satu anggota dari himpunan ini. Ketika klien melihat nomor versi, ia akan tahu yang terbaru dan mengambil yang satu