Sistem Peer-To-Peer

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

Sistem peer-to-peer mewakili paradigma untuk pembangunan sistem terdistribusi dan aplikasi di mana data dan komputasi sumber daya disumbangkan oleh banyak host di Internet, semua yang berpartisipasi dalam penyediaan layanan seragam. Mereka Munculnya merupakan konsekuensi dari pertumbuhan yang sangat cepat dari Internet, merangkul banyak jutaan komputer dan nomor yang sama dari pengguna yang membutuhkan akses ke sumber daya bersama.


Masalah utama untuk peer-to-peer sistem adalah penempatan data objek di banyak host dan penyediaan berikutnya untuk akses ke mereka dengan cara yang menyeimbangkan beban kerja dan memastikan ketersediaan tanpa menambahkan overhead yang tidak semestinya. Kami menjelaskan beberapa baru-baru ini mengembangkan sistem dan aplikasi yang dirancang untuk mencapai hal ini.

Peer-to-peer sistem middleware muncul yang memiliki kapasitas untuk berbagi sumber daya komputasi, penyimpanan dan menyajikan data dalam komputer 'di tepi Internet' pada skala global. Mereka mengeksploitasi ada penamaan, routing, replikasi data dan keamanan teknik dalam cara-cara baru untuk membangun lapisan berbagi sumber daya yang handal melalui diandalkan dan Koleksi dipercaya komputer dan jaringan.

Peer-to-peer aplikasi telah digunakan untuk menyediakan file sharing, web caching, distribusi informasi dan layanan lainnya, mengeksploitasi sumber daya puluhan ribu mesin di Internet. Mereka pada mereka yang paling efektif bila digunakan untuk menyimpan sangat koleksi besar data berubah. desain mereka mengurangi efektivitas mereka untuk aplikasi yang menyimpan dan memperbarui data objek bisa berubah.

Permintaan untuk layanan di internet dapat diharapkan tumbuh untuk skala yang terbatas hanya dengan ukuran populasi dunia. Tujuan dari peer-to-peer sistem adalah untuk mengaktifkan berbagi data dan sumber daya pada skala yang sangat besar dengan menghilangkan persyaratan untuk server dikelola secara terpisah dan infrastruktur yang terkait.

Ruang lingkup untuk memperluas layanan populer dengan menambahkan jumlah yang komputer hosting yang mereka terbatas ketika semua host harus dimiliki dan dikelola oleh penyedia layanan. Administrasi dan pemulihan kesalahan biaya cenderung mendominasi. Itu bandwidth jaringan yang dapat diberikan ke situs server tunggal lebih fisik  yang tersedia Link juga merupakan kendala utama. layanan sistem-tingkat seperti Sun NFS (Bagian 12.3), Andrew File System (Bagian 12,4) atau server video (Bagian 20.6.1) dan layanan aplikasi-tingkat seperti Google, Amazon atau eBay semua menunjukkan masalah ini ke berbagai derajat.

sistem peer-to-peer bertujuan untuk mendukung layanan terdistribusi berguna dan aplikasi menggunakan data dan sumber daya komputasi yang tersedia di komputer pribadi dan workstation yang hadir di Internet dan jaringan lain di yang terus meningkat angka. Hal ini semakin menarik sebagai perbedaan kinerja antara desktop dan mesin server menyempit dan koneksi jaringan broadband berkembang biak.

Tapi ada yang lain, tujuan yang lebih luas: satu penulis [Shirky 2000] telah didefinisikan peer-topeer aplikasi sebagai 'aplikasi yang mengeksploitasi sumber daya yang tersedia di tepi Internet - penyimpanan, siklus, konten, kehadiran manusia '. Setiap jenis berbagi sumber daya disebutkan dalam definisi yang sudah diwakili oleh aplikasi terdistribusi yang tersedia untuk sebagian besar jenis komputer pribadi. Tujuan bab ini adalah untuk menjelaskan beberapa teknik umum yang mempermudah pembangunan aplikasi peer-to-peer dan meningkatkan skalabilitas, kehandalan dan keamanan.

Sistem client-server tradisional mengelola dan menyediakan akses ke sumber daya seperti file, halaman web atau objek informasi lainnya yang berada di komputer server tunggal atau kelompok kecil server ketat ditambah. Dengan desain terpusat seperti, beberapa keputusan yang diperlukan tentang penempatan sumber daya atau pengelolaan hardware server sumber daya, tetapi skala layanan dibatasi oleh kapasitas hardware server dan konektivitas jaringan. sistem peer-to-peer menyediakan akses ke sumber daya informasi terletak pada komputer di seluruh jaringan (apakah itu Internet atau perusahaan yang jaringan). Algoritma untuk penempatan dan pengambilan berikutnya objek informasi merupakan aspek utama dari desain sistem. Tujuannya adalah untuk memberikan layanan yang sepenuhnya desentralisasi dan mengorganisir diri, dinamis menyeimbangkan penyimpanan dan pengolahan beban antara semua komputer yang berpartisipasi sebagai komputer bergabung dan meninggalkan layanan.

sistem peer-to-peer berbagi karakteristik ini:

Desain mereka memastikan bahwa setiap pengguna kontribusi sumber daya ke sistem.
Meskipun mereka mungkin berbeda dalam sumber daya yang mereka berkontribusi, semua node dalam peer-to-peer sistem memiliki kemampuan fungsional yang sama dan tanggung jawab.
operasi yang benar mereka tidak tergantung pada keberadaan setiap terpusat sistem diberikan.
Mereka dapat dirancang untuk menawarkan tingkat yang terbatas anonimitas untuk penyedia dan pengguna sumber daya.
Masalah utama untuk operasi yang efisien adalah pilihan algoritma untuk penempatan data di banyak host dan akses berikutnya untuk itu dengan cara yang menyeimbangkan beban kerja dan memastikan ketersediaan tanpa menambahkan overhead yang tidak semestinya.


Komputer dan koneksi jaringan yang dimiliki dan dikelola oleh banyak berbeda pengguna dan organisasi adalah sumber daya tentu stabil; pemiliknya tidak menjamin untuk menjaga mereka diaktifkan, terhubung dan kesalahan-bebas. Jadi ketersediaan proses dan komputer yang berpartisipasi dalam peer-to-peer sistem tidak dapat diprediksi. Peer-to-peer layanan karena itu tidak dapat mengandalkan dijamin akses ke sumber daya individu, meskipun mereka dapat dirancang untuk membuat kemungkinan kegagalan untuk mengakses salinan direplikasi objek sewenang-wenang kecil. Perlu dicatat bahwa kelemahan ini peer-to-peer sistem dapat berubah menjadi kekuatan jika replikasi sumber daya yang menyerukan dimanfaatkan untuk mencapai tingkat ketahanan terhadap gangguan oleh node berbahaya (misalnya, melalui teknik toleransi kesalahan Bizantium; lihat Bab 18).

Beberapa layanan berbasis Internet awal, termasuk DNS (Bagian 13.2.3) dan Netnews / Usenet [Kantor dan Lapsley 1986], mengadopsi multi-server scalable dan faulttolerant arsitektur. Layanan pengiriman Xerox Grapevine nama pendaftaran dan surat [Birrell et al. 1982, Schroeder et al. 1984] memberikan contoh awal yang menarik dari scalable, kesalahan-toleran didistribusikan layanan. algoritma parlemen paruh waktu Lamport untuk didistribusikan konsensus [Lamport 1989], Bayou direplikasi sistem penyimpanan (lihat Bagian 18.4.2) dan algoritma interdomain routing IP tanpa kelas (lihat Bagian 3.4.3) semua contoh algoritma terdistribusi untuk penempatan atau lokasi informasi dan dapat dianggap sebagai anteseden dari peer-to-peer sistem.

Tapi potensi untuk penyebaran layanan peer-to-peer menggunakan sumber daya di tepi Internet muncul hanya ketika sejumlah besar pengguna telah mengakuisisi selalu-on, koneksi broadband ke jaringan, membuat komputer desktop mereka platform cocok untuk berbagi sumber daya. Ini terjadi pertama kali di Amerika Serikat sekitar 1999. Pada pertengahan 2004 jumlah seluruh dunia dari koneksi Internet broadband memiliki nyaman melebihi 100 juta [Internet World Stats 2004]. Tiga generasi sistem peer-to-peer dan pengembangan aplikasi dapat diidentifikasi. Generasi pertama diluncurkan oleh layanan pertukaran musik Napster [OpenNap 2001], yang kami jelaskan pada bagian berikutnya. Sebuah generasi kedua dari filesharing aplikasi menawarkan skalabilitas yang lebih besar, anonimitas dan toleransi kesalahan cepat diikuti termasuk Freenet [Clarke et al. 2000, freenetproject.org], Gnutella, Kazaa [Leibowitz et al. 2003] dan BitTorrent [Cohen 2003].

Peer-to-peer middleware • Generasi ketiga ditandai dengan munculnya lapisan middleware untuk aplikasi manajemen independen sumber daya didistribusikan pada skala global. Beberapa tim peneliti telah menyelesaikan pengembangan, evaluasi dan penyempurnaan dari peer-to-peer platform middleware dan menunjukkan atau dikerahkan mereka dalam berbagai layanan aplikasi. Yang paling terkenal dan paling penuh contoh maju termasuk Pastry [Rowstron dan Druschel 2001], Tapestry [Zhao et Al. 2004], CAN [Ratnasamy et al. 2001], Chord [Stoica et al. 2001] dan Kademlia [Maymounkov dan Mazieres 2002].

Platform ini dirancang untuk menempatkan sumber daya (obyek data, file) pada set komputer yang didistribusikan secara luas di seluruh Internet dan pesan rute ke mereka atas nama klien, menghilangkan klien dari kebutuhan untuk membuat keputusan tentang menempatkan sumber daya dan untuk menyimpan informasi tentang keberadaan sumber daya yang mereka butuhkan. Berbeda dengan sistem generasi kedua, mereka memberikan jaminan pengiriman untuk permintaan di sejumlah dibatasi hop jaringan. Mereka menempatkan replika sumber daya pada host yang tersedia komputer secara terstruktur, dengan mempertimbangkan ketersediaan volatil mereka, mereka variabel kepercayaan dan persyaratan untuk load balancing dan lokalitas informasi penyimpanan dan penggunaan.

Sumber diidentifikasi oleh pengidentifikasi unik global (GUID), biasanya berasal sebagai hash aman (dijelaskan dalam Bagian 11.4.3) dari beberapa atau semua negara sumber daya ini. Penggunaan hash aman membuat sumber daya 'diri sertifikasi' - klien menerima sumber daya dapat memeriksa validitas hash. Ini melindungi terhadap gangguan oleh node tidak dipercaya yang mungkin disimpan, tapi teknik ini mengharuskan negara-negara dari sumber daya yang berubah, karena perubahan ke negara akan menghasilkan nilai hash yang berbeda. Oleh karena itu peerto- sistem penyimpanan rekan secara inheren paling cocok untuk penyimpanan objek abadi (Seperti musik atau file video). penggunaannya untuk objek dengan mengubah nilai-nilai yang lebih menantang, tapi ini dapat diakomodasi dengan penambahan server dipercaya untuk mengelola urutan versi dan mengidentifikasi versi saat ini (seperti yang dilakukan misalnya dalam OceanStore dan Ivy, yang dijelaskan dalam Bagian 10.6.2 dan 10.6.3).

Penggunaan peer-to-peer sistem untuk aplikasi yang menuntut tingkat tinggi ketersediaan untuk benda yang tersimpan membutuhkan desain aplikasi-hati untuk menghindari situasi di mana semua replika dari sebuah objek yang bersamaan tidak tersedia. Ada risiko ini untuk objek yang tersimpan pada komputer dengan kepemilikan yang sama, lokasi geografis, administrasi, konektivitas jaringan, negara atau yurisdiksi. Penggunaan secara acak didistribusikan GUIDs assist dengan mendistribusikan objek replika secara acak terletak node dalam jaringan yang mendasarinya. Jika jaringan yang mendasari mencakup banyak organisasi di seluruh dunia, maka risiko ketidaktersediaan simultan jauh berkurang. Overlay Routing vs IP routing • Pada pandangan pertama, lapisan routing yang berbagi banyak karakteristik dengan IP infrastruktur routing paket yang merupakan primer mekanisme komunikasi Internet (lihat Bagian 3.4.3). Oleh karena itu sah untuk bertanya mengapa mekanisme level aplikasi routing yang tambahan diperlukan dalam peer-to-peer sistem. Jawabannya terletak pada beberapa perbedaan yang diidentifikasi dalam Gambar 10.1. mungkin dikatakan bahwa beberapa perbedaan ini timbul dari sifat 'warisan' dari IP sebagai protokol utama Internet, tetapi dampaknya warisan ini terlalu kuat untuk itu harus diatasi dalam rangka mendukung aplikasi peer-to-peer yang lebih langsung.

Komputasi terdistribusi • Eksploitasi daya komputasi cadangan pada end-user komputer telah lama menjadi topik yang menarik dan percobaan. Bekerja dengan pertama komputer pribadi di Xerox PARC [Shoch dan Hupp 1982] menunjukkan kelayakan melakukan longgar ditambah tugas menghitung-intensif dengan menjalankan proses latar belakang pada ~ 100 komputer pribadi yang terhubung dengan jaringan lokal. Baru-baru ini, jauh lebih besar jumlah komputer telah dimanfaatkan untuk melakukan beberapa perhitungan ilmiah yang membutuhkan jumlah yang hampir tak terbatas daya komputasi.

Upaya yang paling banyak dikenal dari jenis ini adalah SETI @ proyek rumah [Anderson et al. 2002], yang merupakan bagian dari proyek yang lebih luas yang disebut Search for Extra-Terrestrial Intelijen. SETI @ home partisi aliran data teleskop radio digital ke 107- unit kerja kedua, masing-masing sekitar 350 kbytes dan mendistribusikan mereka ke komputer klien daya komputasi yang merupakan kontribusi relawan. Setiap unit kerja didistribusikan berlebihan untuk 3-4 komputer pribadi untuk menjaga terhadap keliru atau berbahaya node dan diperiksa untuk pola sinyal yang signifikan. Distribusi unit kerja dan koordinasi hasil ditangani oleh satu server yang bertanggung jawab untuk komunikasi dengan semua klien. Anderson et al. [2002] melaporkan bahwa 3.910.000 komputer pribadi telah berpartisipasi dalam SETI @ proyek rumah dengan Agustus 2002, mengakibatkan pengolahan 221 juta unit kerja dan mewakili rata-rata 27,36 teraflops kekuatan komputasi selama 12 bulan sampai Juli 2002. Pekerjaan selesai sampai saat ini yang mewakili perhitungan tunggal terbesar dalam catatan.

SETI @ home perhitungan tidak biasa dalam hal itu tidak melibatkan komunikasi atau koordinasi antar komputer sementara mereka memproses pekerjaan unit; hasilnya dikomunikasikan ke server pusat dalam pesan singkat tunggal yang mungkindikirimkan setiap kali klien dan server yang tersedia. Beberapa tugas ilmiah lain Sifat ini telah diidentifikasi, termasuk mencari bilangan prima besar dan mencoba di brute-force dekripsi, tapi melepaskan dari daya komputasi di Internet untuk lebih luas tugas akan tergantung pada pengembangan terdistribusi platform yang mendukung berbagi data dan koordinasi perhitungan antara berpartisipasi komputer dalam skala besar. Itu adalah tujuan dari proyek Grid, dibahas dalam Bab 19.

Dalam bab ini kita fokus pada algoritma dan sistem yang dikembangkan sampai saat ini untuk berbagi data dalam jaringan peer-to-peer. Dalam Bagian 10.2 kita meringkas Napster merancang dan meninjau pelajaran dari itu. Dalam Bagian 10.3 kita menggambarkan umum persyaratan untuk peer-to-peer lapisan middleware. Bagian berikut mencakup desain dan aplikasi peer-to-peer platform middleware, dimulai dengan abstrak spesifikasi dalam Bagian 10.4, diikuti oleh deskripsi rinci dari dua sepenuhnya dikembangkan contoh dalam Bagian 10.5 dan beberapa aplikasi dari mereka dalam Bagian 10.6.





10.2 Napster dan warisannya

Aplikasi pertama di mana permintaan untuk penyimpanan informasi secara global scalable dan pengambilan layanan muncul adalah pengunduhan file musik digital. Kedua kebutuhan dan kelayakan solusi peer-to-peer yang pertama kali ditunjukkan oleh filesharing Napster sistem [OpenNap 2001] yang menyediakan sarana bagi pengguna untuk berbagi file. Napster menjadi sangat populer untuk pertukaran musik segera setelah peluncuran pada tahun 1999. Pada nya puncak, beberapa juta pengguna terdaftar dan ribuan orang bertukar file musik serentak.

Arsitektur Napster termasuk indeks terpusat, namun pengguna disediakan file, yang disimpan dan diakses pada komputer pribadi mereka. Metode Napster dari Operasi ini digambarkan dengan urutan langkah-langkah yang ditunjukkan pada Gambar 10.2. Perhatikan bahwa pada langkah 5 klien diharapkan untuk menambahkan file musik mereka sendiri ke kolam sumber daya bersama oleh transmisi link ke layanan pengindeksan Napster untuk setiap file yang tersedia. Jadi motivasi untuk Napster dan kunci keberhasilannya adalah pembuatan tersedia dari besar, secara luas didistribusikan set file ke pengguna di seluruh Internet, memenuhi diktum Shirky ini dengan menyediakan akses ke 'sumber daya bersama di tepi Internet'.

Napster ditutup akibat proses hukum dilembagakan terhadap operator layanan Napster oleh pemilik hak cipta di beberapa material (Yaitu, musik digital dikodekan) yang dibuat tersedia di atasnya (lihat kotak di bawah).

Anonimitas untuk penerima dan penyedia data bersama dan sumber daya lainnya adalah kekhawatiran untuk para perancang peer-to-peer sistem. Dalam sistem dengan banyak node, routing permintaan dan hasil dapat dibuat cukup berliku-liku untuk menyembunyikan sumber mereka dan isi dari file dapat didistribusikan di beberapa node, menyebarkan tanggung jawab untuk membuat mereka tersedia. Mekanisme untuk komunikasi anonim yang tahan terhadap kebanyakan bentuk analisis lalu lintas tersedia [Goldschlag et al. 1999]. Jika file juga dienkripsi sebelum mereka ditempatkan pada server, pemilik server masuk akal dapat menyangkal pengetahuan tentang isi. Tapi teknik anonimitas ini menambahkan dengan biaya berbagi sumber daya, dan karya terbaru telah menunjukkan bahwa anonimitas tersedia lemah terhadap beberapa serangan [Wright et al. 2002].

The Freenet [Clarke et al. 2000] dan FreeHaven [Dingledine et al. 2000] proyekberfokus pada penyediaan layanan file internet-lebar yang menawarkan anonimitas untuk penyedia dan pengguna file bersama. Ross Anderson telah mengusulkan Layanan Keabadian [Anderson 1996], sebuah layanan penyimpanan yang menyediakan jaminan jangka panjang data

Peer-to-peer sistem dan masalah kepemilikan hak cipta

Para pengembang Napster berpendapat bahwa mereka tidak bertanggung jawab atas pelanggaran yang hak pemilik hak cipta 'karena mereka tidak berpartisipasi dalam proses penyalinan, yang dilakukan seluruhnya antara mesin pengguna. Argumen mereka gagal karena indeks server dianggap bagian penting dari proses. Karena server indeks berada di alamat terkenal, operator mereka tidak dapat tetap anonim dan dapat ditargetkan dalam gugatan.

Sebuah layanan file-sharing lebih sepenuhnya didistribusikan mungkin telah mencapai yang lebih baikpemisahan tanggung jawab hukum, menyebarkan tanggung jawab di semua pengguna dan dengan demikian membuat mengejar upaya hukum sangat sulit, jika tidak mustahil. Apapun pandangan seseorang membutuhkan waktu sekitar legitimasi menyalin file untuk tujuan berbagi materi yang dilindungi hak cipta, ada yang sah sosial dan politik pembenaran untuk anonimitas klien dan server dalam beberapa konteks aplikasi. Pembenaran yang paling persuasif muncul ketika anonimitas digunakan untuk mengatasi sensor dan mempertahankan kebebasan berekspresi bagi individu di menindas masyarakat atau organisasi.

Hal ini diketahui bahwa email dan web situs telah memainkan peran penting dalam mencapai kesadaran masyarakat di saat krisis politik di masyarakat seperti; peran mereka bisa diperkuat jika penulis dapat dilindungi oleh anonimitas. 'Whistle-blowing' adalah kasus terkait: a 'whistle-blower' adalah seorang karyawan yang mempublikasikan atau melaporkan mereka kesalahan majikan kepada otoritas tanpa mengungkapkan identitas mereka sendiri karena takut sanksi atau pemecatan. Dalam beberapa keadaan itu wajar untuk tindakan tersebut untuk dilindungi oleh anonimitas. Ketersediaan melalui perlawanan terhadap segala macam kehilangan data disengaja dan penolakan layanan serangan. Dia mendasarkan kebutuhan untuk layanan tersebut pada pengamatan bahwa sedangkan publikasi adalah negara permanen untuk informasi tercetak - itu hampir tidak mungkin untuk menghapus materi setelah telah diterbitkan dan didistribusikan ke beberapa ribu perpustakaan di beragam organisasi dan yurisdiksi di seluruh dunia - publikasi elektronik tidak bisa dengan mudah mencapai tingkat yang sama dari perlawanan terhadap sensor atau penekanan. Anderson mencakup persyaratan teknis dan ekonomi untuk memastikan integritas toko dan juga menunjukkan bahwa anonimitas sering merupakan persyaratan penting untuk kegigihan informasi, karena memberikan pertahanan terbaik terhadap tantangan hukum, serta tindakan ilegal seperti sebagai suap atau serangan terhadap pencetusnya, pemilik atau penjaga data.

Pelajaran dari Napster • Napster menunjukkan kelayakan membangun Layanan skala besar yang berguna yang tergantung hampir sepenuhnya pada data dan komputer yang dimiliki oleh pengguna Internet biasa. Untuk menghindari membanjiri sumber daya komputasi pengguna individu (Misalnya, pengguna pertama yang menawarkan chart-topping lagu) dan koneksi jaringan mereka, Napster mengambil akun lokalitas jaringan - jumlah hop antara klien dan server - ketika mengalokasikan server ke klien meminta sebuah lagu. loaddistribution sederhana ini mekanisme diaktifkan layanan untuk skala untuk memenuhi kebutuhan jumlah besar pengguna.

Keterbatasan: Napster menggunakan (direplikasi) indeks terpadu dari semua file musik yang tersedia. Untuk aplikasi yang bersangkutan, persyaratan untuk konsistensi antara replika itu tidak yang kuat, jadi ini tidak menghambat kinerja, tetapi untuk banyak aplikasi itu akan merupakan pembatasan. Kecuali jalan akses ke objek data didistribusikan, objek penemuan dan menangani cenderung menjadi hambatan.

Aplikasi dependensi: Napster mengambil keuntungan dari karakteristik khusus dari aplikasi untuk yang dirancang dengan cara lain:

File musik tidak pernah diperbarui, menghindari kebutuhan untuk memastikan semua replika file tetap konsisten setelah update.
Tidak ada jaminan yang diperlukan mengenai ketersediaan file individual – jika File musik untuk sementara tidak tersedia, dapat didownload nanti. Hal ini mengurangi persyaratan untuk keandalan masing-masing komputer dan koneksi mereka untuk Internet.






10.3 Peer-to-peer middleware

Masalah utama dalam desain aplikasi peer-to-peer adalah menyediakan mekanisme untuk memungkinkan klien untuk mengakses sumber daya data dengan cepat dan dependably dimanapun mereka berada terletak di seluruh jaringan. Napster mempertahankan indeks terpadu dari file yang tersedia untuk tujuan ini, memberikan alamat jaringan host mereka. Generasi kedua peer-topeer sistem penyimpanan file seperti Gnutella dan Freenet mempekerjakan dipartisi dan didistribusikan indeks, tetapi algoritma yang digunakan khusus untuk setiap sistem.

Masalah lokasi ini ada di beberapa layanan yang mendahului peer-to-peer Paradigma juga. Misalnya, Sun NFS alamat kebutuhan ini dengan bantuan dari file virtual Sistem lapisan abstraksi pada setiap klien yang menerima permintaan untuk mengakses file yang tersimpan di beberapa server dalam hal referensi file virtual (yaitu, v-node, lihat Bagian 12.3). Ini solusi bergantung pada sejumlah besar preconfiguration di setiap klien dan manual intervensi ketika pola distribusi file atau perubahan ketentuan Server. Hal ini jelas tidak scalable luar layanan dikelola oleh satu organisasi. AFS (Bagian 12,4) memiliki sifat yang mirip.

Peer-to-peer sistem middleware dirancang khusus untuk memenuhi  kebutuhan penempatan otomatis dan lokasi berikutnya dari objek terdistribusi dikelola oleh peer-to-peer sistem dan aplikasi.

persyaratan fungsional • Fungsi peer-to-peer middleware adalah untuk menyederhanakan pembangunan layanan yang diterapkan di banyak host di didistribusikan secara luas jaringan. Untuk mencapai hal ini ia harus memungkinkan klien untuk mencari dan berkomunikasi dengan sumber daya individu yang dibuat tersedia untuk layanan, meskipun sumber daya secara luas didistribusikan antara tuan rumah. Persyaratan penting lainnya mencakup kemampuan untuk menambahkan sumber daya baru dan untuk menghapusnya di akan dan untuk menambahkan host ke layanan dan menghapus mereka. Seperti middleware lainnya, peer-to-peer middleware harus menawarkan sederhana pemrograman antarmuka untuk programmer aplikasi yang independen dari jenis didistribusikan sumber daya bahwa aplikasi memanipulasi.

kebutuhan non-fungsional • Untuk melakukan secara efektif, peer-to-peer middleware harus juga mengatasi kebutuhan non-fungsional berikut [lih Kubiatowicz 2003]:

skalabilitas global: Salah satu tujuan dari aplikasi peer-to-peer adalah untuk mengeksploitasi sumber daya perangkat keras dari jumlah yang sangat besar dari host terhubung ke Internet. Peer-topeer middleware karena itu harus dirancang untuk mendukung aplikasi yang mengakses jutaan objek pada puluhan ribu atau ratusan ribu host.

Load balancing: Kinerja dari setiap sistem yang dirancang untuk mengeksploitasi sejumlah besar komputer tergantung pada distribusi yang seimbang dari beban kerja di antara mereka. Untuk sistem yang kami pertimbangkan, ini akan dicapai dengan penempatan acak sumber bersama-sama dengan penggunaan replika sumber daya banyak digunakan.

Optimasi untuk interaksi lokal antara rekan-rekan tetangga: The 'jaringan jarak' antara node yang berinteraksi memiliki dampak besar pada latency individu interaksi, seperti permintaan klien untuk akses ke sumber daya. lalu lintas jaringan beban juga dipengaruhi oleh itu. middleware harus bertujuan untuk menempatkan sumber dekat ke kelenjar yang paling mengaksesnya.

Menampung ketersediaan tuan rumah yang sangat dinamis: Kebanyakan sistem peer-to-peer yang dibangun dari host komputer yang bebas untuk bergabung atau meninggalkan sistem pada setiap saat. Host dan segmen jaringan yang digunakan dalam peer-to-peer sistem yang tidak dimiliki atau dikelola oleh otoritas tunggal; tidak kehandalan mereka atau mereka yang terus menerus partisipasi dalam penyediaan layanan dijamin. Sebuah tantangan besar bagi peerto- peer adalah untuk menyediakan layanan yang dapat diandalkan meskipun fakta-fakta ini. Sebagai tuan rumah bergabung sistem, mereka harus diintegrasikan ke dalam sistem dan beban harus didistribusikan untuk mengeksploitasi sumber daya mereka. Ketika mereka meninggalkan sistem apakah secara sukarela atau tanpa sadar, sistem harus mendeteksi keberangkatan mereka dan mendistribusikan beban mereka dan sumber.

Studi aplikasi peer-to-peer dan sistem seperti Gnutella dan Overnet telah menunjukkan omset yang cukup besar dari host yang berpartisipasi [Saroiu et al. 2002, Bhagwan et al. 2003]. Untuk sistem file-sharing Overnet peer-to-peer, dengan 85.000 host yang aktif di seluruh Internet, Bhagwan et al. diukur sesi rata-rata panjang 135 menit (dan median dari 79 menit) untuk sampel acak dari 1.468 host selama 7 hari, dengan 260-650 dari 1.468 host yang tersedia untuk layanan kapan saja. (Sesi merupakan periode di mana tuan rumah tersedia sebelum secara sukarela atau mau tidak mau terputus.)

Di sisi lain, peneliti Microsoft diukur panjang sesi dari 37,7 jam untuk sampel acak dari 20.000 mesin yang terhubung ke perusahaan Microsoft jaringan, dengan antara 14.700 dan 15.600 mesin yang tersedia untuk layanan di waktu tertentu [Castro et al. 2003]. Pengukuran ini didasarkan pada kelayakan suatu belajar untuk Farsite sistem file peer-to-peer [Bolosky et al. 2000]. Varians besar antara angka yang diperoleh dalam penelitian ini terutama disebabkan oleh perbedaan dalam perilaku dan lingkungan jaringan antara pengguna internet individu dan pengguna di jaringan perusahaan seperti Microsoft.

Keamanan data dalam lingkungan dengan kepercayaan yang heterogen: Dalam sistem berskala global dengan berpartisipasi host kepemilikan beragam, kepercayaan harus dibangun oleh penggunaan mekanisme otentikasi dan enkripsi untuk memastikan integritas dan privasi informasi.

Anonimitas, penyangkalan dan ketahanan terhadap sensor: Kami telah mencatat (dalam kotak di Halaman 429) bahwa anonimitas bagi pemegang dan penerima data merupakan keprihatinan yang sah dalam banyak situasi menuntut ketahanan terhadap sensor. Persyaratan terkait adalah bahwa host yang menyimpan data harus dapat masuk akal menyangkal tanggung jawab untuk memegang atau memasok. Penggunaan sejumlah besar host di peer-to-peer sistem dapat membantu dalam mencapai sifat ini.

Cara terbaik untuk desain lapisan middleware untuk mendukung berskala global sistem peer to-peer adalah Oleh karena itu masalah sulit. Persyaratan untuk skalabilitas dan ketersediaan membuatnya tidak layak untuk menjaga database di semua node klien memberikan lokasi dari semua sumber (objek) yang menarik.

Pengetahuan tentang lokasi objek harus dipartisi dan didistribusikan seluruh jaringan. Setiap node dibuat bertanggung jawab untuk menjaga rinci pengetahuan tentang lokasi dari node dan benda-benda di sebagian namespace juga sebagai pengetahuan umum dari topologi dari seluruh namespace (Gambar 10.3). Tinggi tingkat replikasi pengetahuan ini diperlukan untuk memastikan kehandalan di wajah ketersediaan volatile host dan konektivitas jaringan intermiten. Dalam sistem kami jelaskan di bawah, faktor replikasi setinggi 16 biasanya digunakan.





10.4 hamparan Routing

Perkembangan middleware yang memenuhi fungsional dan non-fungsional persyaratan yang diuraikan dalam bagian sebelumnya adalah bidang penelitian aktif, dan beberapa sistem middleware yang signifikan telah muncul. Dalam Bab ini menjelaskan beberapa dari mereka secara rinci.

Dalam peer-to-peer sistem algoritma terdistribusi dikenal sebagai overlay routing yang dibutuhkan tanggung jawab untuk mencari node dan benda-benda. Nama menunjukkan fakta bahwa middleware mengambil bentuk lapisan yang bertanggung jawab untuk permintaan routing apapun klien untuk host yang memegang objek yang permintaan ditujukan. Objek bunga dapat ditempatkan di dan kemudian pindah ke setiap node dalam jaringan tanpa Keterlibatan klien. Hal ini disebut overlay karena menerapkan mekanisme routing dalam lapisan aplikasi yang cukup terpisah dari mekanisme routing lainnya dikerahkan di tingkat jaringan seperti IP routing. Pendekatan ini untuk manajemen dan lokasi benda direplikasi pertama kali dianalisis dan terbukti efektif untuk jaringan yang melibatkan cukup banyak node dalam sebuah makalah terobosan dengan Plaxton et al. [1997].

Overlay routing yang memastikan bahwa setiap node dapat mengakses objek apapun dengan routing masing-masing meminta melalui urutan node, pemanfaatan pengetahuan di masing-masing untuk mencari objek tujuan. sistem peer-to-peer biasanya menyimpan beberapa replika benda untuk menjamin ketersediaan. Dalam hal ini, overlay routing yang mempertahankan pengetahuan lokasi dari semua replika yang tersedia dan memberikan permintaan ke terdekat 'hidup' simpul (satu yaitu yang tidak gagal) yang memiliki salinan dari objek yang relevan.

GUID digunakan untuk mengidentifikasi node dan objek adalah contoh nama-nama 'murni' sebagaimana dimaksud dalam Pasal 13.1.1. Ini juga dikenal sebagai pengidentifikasi buram, karena mereka mengungkapkan apa-apa tentang lokasi dari objek yang mereka lihat.





Tugas utama dari overlay routing berikut:

Routing permintaan ke objek: Seorang klien yang ingin memanggil operasi pada objek mengajukan permintaan termasuk GUID objek untuk overlay routing yang, yang rute permintaan ke node di mana replika dari objek berada.

Tapi routing overlay juga harus melakukan beberapa tugas lainnya:

Penyisipan objek: Sebuah simpul yang ingin membuat objek baru tersedia untuk peer peer-to- Layanan menghitung GUID untuk objek dan mengumumkan untuk routing overlay, efyang kemudian memastikan bahwa benda dicapai oleh semua klien lain.

Gambar 10.4 antarmuka pemrograman Basic untuk tabel hash didistribusikan (DHT) seperti yang diterapkan oleh API PAST lebih Pastry

menempatkan (GUID, data)

Menyimpan data di replika di semua node bertanggung jawab atas objek yang diidentifikasi oleh GUID.

menghapus (GUID)

Menghapus semua referensi untuk GUID dan data yang terkait.

value = mendapatkan (GUID)

Mengambil data yang terkait dengan GUID dari salah satu simpul yang bertanggung jawab untuk itu.

Penghapusan objek: Ketika klien meminta penghapusan objek dari layanan tersebut routing yang overlay harus membuat mereka tidak tersedia.

Selain node dan penghapusan: Nodes (yaitu, komputer) dapat bergabung dan meninggalkan layanan. Ketika sebuah node bergabung layanan, overlay routing yang mengatur untuk itu untuk menganggap beberapa tanggung jawab node lain. Ketika sebuah node daun (baik secara sukarela atau sebagai Hasil dari sistem atau kesalahan jaringan), tanggung jawab didistribusikan di antara node lain.

GUID obyek dihitung dari seluruh atau sebagian dari keadaan objek menggunakan fungsi yang memberikan nilai yang, dengan probabilitas yang sangat tinggi, unik. Keunikan diverifikasi dengan mencari objek lain dengan GUID yang sama. Sebuah fungsi hash (seperti SHA-1, lihat Bagian 11.4) digunakan untuk menghasilkan GUID dari nilai objek. karena ini pengidentifikasi didistribusikan secara acak digunakan untuk menentukan penempatan objek dan mengambil mereka, overlay routing sistem kadang-kadang digambarkan sebagai hash didistribusikan tabel (DHT). Hal ini tercermin dengan bentuk sederhana dari API yang digunakan untuk mengaksesnya, sebagai ditunjukkan pada Gambar 10.4. Dengan API ini, put () operasi digunakan untuk mengirimkan data item untuk disimpan bersama-sama dengan GUID nya. Lapisan DHT bertanggung jawab untuk memilih lokasi untuk itu, menyimpannya (dengan replika untuk memastikan ketersediaan) dan menyediakan akses ke sana melalui get () operasi.

Sebuah bentuk yang sedikit lebih fleksibel dari API disediakan oleh lokasi objek terdistribusi dan routing (DOLR) lapisan, seperti yang ditunjukkan pada Gambar 10.5. Dengan interface ini benda-benda dapat disimpan di mana saja dan lapisan DOLR bertanggung jawab untuk menjaga pemetaan antara pengidentifikasi objek (GUID) dan alamat node di mana replika dari objek berada. Benda dapat direplikasi dan disimpan dengan GUID sama pada host yang berbeda, dan routing overlay bertanggung jawab untuk permintaan routing ke terdekat yang tersedia replika.

Dengan model DHT, item data dengan GUID X disimpan di node yang GUID adalah numerik terdekat X dan pada r host yang GUIDs berikutnya terdekat untuk itu numerik, di mana r adalah faktor replikasi yang dipilih untuk memastikan probabilitas yang sangat tinggi tersedianya. Dengan model DOLR, lokasi untuk replika objek data yang diputuskan luar lapisan routing dan lapisan DOLR diberitahu tentang alamat host masing-masing replika menggunakan mempublikasikan () operasi.

Antarmuka pemrograman dasar untuk lokasi didistribusikan objek dan routing (PINTU) sebagai dilaksanakan oleh Tapestry

mempublikasikan (GUID)

GUID dapat dihitung dari objek (atau beberapa bagian dari itu, misalnya, namanya). Ini Fungsi membuat node melakukan operasi mempublikasikan tuan rumah untuk objek sesuai dengan GUID.



membatalkan publikasi (GUID)

Membuat objek sesuai dengan GUID tidak dapat diakses.

sendTo obj (msg, GUID, [n])

Setelah paradigma berorientasi objek, pesan doa dikirim ke obyek untuk mengaksesnya. Ini mungkin permintaan untuk membuka koneksi TCP untuk data mentransfer atau kembali pesan yang berisi semua atau bagian dari negara objek. Akhir opsional parameter [n], jika ada, meminta pengiriman pesan yang sama ke n replika dari objek.

Antarmuka pada Gambar 10.4 dan 10.5 didasarkan pada satu set abstrak representasi diusulkan oleh Dabek et al. [2003] menunjukkan bahwa sebagian besar peer-to-peer routing yang implementasi overlay dikembangkan sampai saat ini menyediakan fungsionalitas sangat mirip.

Penelitian tentang desain sistem overlay routing yang dimulai pada tahun 2000 dan telah mencapaiberbuah pada tahun 2005, dengan pengembangan dan evaluasi beberapa prototipe sukses. Evaluasi menunjukkan bahwa kinerja dan kehandalan mereka yang memadai untuk digunakan di banyak lingkungan produksi. Pada bagian berikutnya kita menggambarkan dua ini secara rinci: Pastry, yang menerapkan didistribusikan hash table API mirip dengan yang disajikan pada Gambar 10.4, dan Tapestry, yang mengimplementasikan API mirip dengan yang ditampilkan pada Gambar 10.5. Kedua Pastry dan Tapestry mempekerjakan mekanisme routing yang dikenal sebagai awalan routing untuk menentukan rute untuk pengiriman pesan berdasarkan nilai-nilai GUIDs yang mereka ditangani. Routing prefix mempersempit pencarian node berikutnya sepanjang rute dengan menerapkan masker biner yang memilih peningkatan jumlah heksadesimal digit dari tujuan GUID setelah setiap hop. (Teknik ini juga dipekerjakan dalam routing interdomain tanpa kelas untuk paket IP, seperti diuraikan dalam Bagian 3.4.3.)

Skema routing lain telah dikembangkan yang mengeksploitasi langkah-langkah yang berbeda dari jarak untuk mempersempit pencarian tujuan hop berikutnya. Chord [Stoica et al. 2001] mendasarkan pilihan pada perbedaan numerik antara GUID dari node yang dipilih dan node tujuan. CAN [Ratnasamy et al. 2001] menggunakan jarak di d-dimensi hyperspace ke node ditempatkan. Kademlia [Maymounkov dan Mazieres 2002] menggunakan XOR pasang GUID sebagai metrik untuk jarak antara node. karena XOR simetris, Kademlia dapat mempertahankan tabel routing peserta sangat sederhana; mereka selalu menerima permintaan dari node yang sama yang terdapat dalam tabel routing mereka.

GUIDs tidak terbaca-manusia, sehingga aplikasi client harus mendapatkan GUID untuk sumber yang menarik melalui beberapa bentuk layanan pengindeksan menggunakan manusia-dibaca nama atau permintaan pencarian. Idealnya, indeks ini juga disimpan dengan cara peer-to-peer untuk mengatasi kelemahan dari indeks terpusat dibuktikan oleh Napster. Tapi di sederhana kasus, seperti file musik atau publikasi yang tersedia untuk peer-to-peer download, mereka bisa hanya diindeks pada halaman web (lih BitTorrent [Cohen 2003]). Dalam BitTorrent web pencarian indeks mengarah ke file stub berisi rincian dari sumber daya yang diinginkan, termasuk yang GUID dan URL pelacak - host yang memegang daftar up-to-date jaringan alamat untuk penyedia bersedia untuk memasok file (lihat Bab 20 untuk rincian lebih lanjut dari BitTorrent protocol).

Uraian di atas routing hamparan mungkin akan menimbulkan pertanyaan dalam pikiran pembaca tentang kinerja dan kehandalan mereka. Jawaban untuk pertanyaan ini akan muncul dari deskripsi sistem overlay routing yang praktis dalam berikutnya bagian.

10,5 studi kasus Overlay: Pastry, Tapestry

Pendekatan prefix routing diadopsi oleh Pastry dan Tapestry. Pastry adalah pesan routing infrastruktur dikerahkan di beberapa aplikasi termasuk PAST [Druschel dan Rowstron 2001], sebuah arsip (berubah) sistem penyimpanan file diimplementasikan sebagai tabel hash didistribusikan dengan API pada Gambar 10.4, dan Squirrel, sebuah peerto- rekan layanan web caching dijelaskan dalam Bagian 10.6.1. Pastry memiliki sederhana tetapi desain yang efektif yang membuatnya pertama yang baik contoh bagi kita untuk mempelajari secara rinci.

Tapestry adalah dasar untuk sistem penyimpanan OceanStore, yang kami jelaskan di Bagian 10.6.2. Memiliki arsitektur yang lebih kompleks daripada Pastry karena bertujuan untuk mendukung lebih luas wilayah pendekatan. Kami menjelaskan Tapestry dalam Bagian 10.5.2.

Kami juga melihat pendekatan terstruktur alternatif dalam Bagian 10.5.3, cari di rinci pada gaya overlay diadopsi oleh Gnutella.





10.5.1 Pastry

Pastry [Rowstron dan Druschel 2001, Castro et al. 2002a, freepastry.org] adalah routing overlay dengan karakteristik yang kita diuraikan dalam Bagian 10.4. Semua node dan benda-benda yang dapat diakses melalui Pastry ditugaskan GUID 128-bit. Untuk node, ini dihitung dengan menerapkan fungsi hash aman (seperti SHA-1; lihat Bagian 11.4.3) untuk kunci publik yang masing-masing simpul disediakan. Untuk objek seperti file, yang GUID dihitung dengan menerapkan fungsi hash yang aman untuk nama benda atau beberapa bagian dari negara yang tersimpan objek. GUID yang dihasilkan memiliki sifat biasa aman nilai-nilai hash - yaitu, mereka didistribusikan secara acak di kisaran 0 sampai 2128-1. Mereka tidak memberikan petunjuk tentang nilai dari mana mereka dihitung, dan bentrokan antara GUID untuk node atau objek yang berbeda sangat tidak mungkin. (Jika bentrokan terjadi, Pastry mendeteksi dan mengambil tindakan perbaikan.)

Dalam sebuah jaringan dengan N berpartisipasi node, algoritma routing Pastry akan benar rute pesan yang ditujukan kepada setiap GUID di O (log N) langkah. Jika GUID mengidentifikasi node yang saat ini aktif, pesan tersebut disampaikan ke node itu; jika tidak, pesan dikirim ke node aktif yang GUID adalah numerik paling dekat dengan itu. Aktif node bertanggung jawab untuk memproses permintaan ditujukan kepada semua objek di mereka lingkungan numerik.

langkah Routing melibatkan penggunaan protokol transport yang mendasari (biasanya UDP) untuk mentransfer pesan ke node Pastry yang 'dekat' ke tujuannya. Tetapi perhatikan bahwa kedekatan dimaksud di sini adalah dalam ruang seluruhnya buatan - ruang GUIDs. Itu Titik-titik menggambarkan node hidup. Ruang ini dianggap sebagai lingkaran: node 0 berdekatan dengan simpul (2128-1). Diagram menggambarkan routing pesan dari node 65A1FC ke D46A1C menggunakan informasi daun mengatur sendiri, dengan asumsi set daun ukuran 8 (l = 4). Ini adalah jenis merosot

routing yang akan skala sangat buruk; tidak digunakan dalam praktek. transportasi nyata dari pesan di Internet antara dua node Pastry mungkin memerlukan sejumlah besar IP hop. Untuk meminimalkan risiko transportasi tidak perlu diperpanjang jalur, Pastry menggunakan metrik wilayah berdasarkan jarak jaringan di jaringan yang mendasarinya (Seperti jumlah hop atau pengukuran latency round-trip) untuk memilih yang tepat tetangga saat menyiapkan tabel routing yang digunakan pada setiap node.

Ribuan host terletak di situs tersebar luas dapat berpartisipasi dalam Pastry sebuah hamparan. Hal ini sepenuhnya mengorganisir diri: ketika node baru bergabung overlay mereka mendapatkan data diperlukan untuk membangun sebuah tabel routing dan negara lainnya yang diperlukan dari anggota yang ada di O (log N) pesan, di mana N adalah jumlah host yang berpartisipasi dalam overlay. Dalam terjadi kegagalan node atau keberangkatan, node yang tersisa dapat mendeteksi adanya dan kooperatif mengkonfigurasi ulang untuk mencerminkan perubahan yang diperlukan dalam struktur routing dalam sebuah jumlah yang sama pesan.

Algoritma routing • Algoritma routing yang penuh melibatkan penggunaan tabel routing di setiap node pesan dengan efisien, tapi untuk tujuan penjelasan, kami menjelaskan routing algoritma dalam dua tahap. Tahap pertama menggambarkan bentuk sederhana dari algoritma yang rute pesan benar tetapi tidak efisien tanpa tabel routing, dan Tabel routing terletak pada simpul yang ID dimulai 65A1. Digit dalam heksadesimal. Ns merupakan [GUID, alamat IP] pasangan yang bertindak sebagai simpul menangani menentukan hop berikutnya yang akan diambil oleh pesan yang ditujukan ke GUID yang cocok setiap awalan yang diberikan. Grey-berbayang entri dalam tubuh tabel menunjukkan bahwa awalan cocok dengan GUID saat ini hingga yang diberikan nilai p: baris berikutnya ke bawah atau set daun harus diperiksa untuk menemukan rute.

Meskipun ada maksimum 128 baris dalam tabel, hanya log16 N baris akan diisi rata-rata dalam jaringan dengan N node yang aktif. tahap kedua menjelaskan algoritma routing penuh, yang rute permintaan untuk setiap node di O (log N) pesan:

Tahap I: Setiap node aktif menyimpan daun set - vektor L (ukuran 2l) yang berisi GUID dan alamat IP dari node yang memiliki anak numerik terdekat di kedua sisi sendiri (l di atas dan l bawah). Daun set dikelola oleh Pastry sebagai node bergabung dan pergi. Bahkan setelah kegagalan node, mereka akan diperbaiki dalam waktu singkat. (Kesalahan recovery dibahas di bawah.) Oleh karena itu invarian dari sistem Pastry bahwa set daun mencerminkan keadaan terbaru dari sistem dan bahwa mereka berkumpul di keadaan saat dalam menghadapi kegagalan hingga beberapa tingkat maksimum kegagalan.

Ruang GUID diperlakukan sebagai melingkar: tetangga GUID 0 lebih rendah adalah 2128-1. Gambar 10.6 memberikan pandangan node aktif didistribusikan di ruang alamat melingkar ini. Karena setiap daun set termasuk GUID dan alamat IP dari node saat ini ini tetangga dekat, sistem Pastry dengan set daun benar ukuran minimal 2 kaleng pesan rute ke setiap GUID sepele sebagai berikut: setiap node A yang menerima pesan M dengan alamat tujuan D-rute pesan dengan membandingkan D dengan GUID sendiri A dan dengan masing-masing GUID di set daun dan forwarding M ke node antara mereka yang numerik terdekat D.

Gambar 10.6 mengilustrasikan ini untuk sistem Pastry dengan l = 4. (Dalam nyata khas instalasi Pastry, l = 8.) Berdasarkan definisi set daun kita dapat menyimpulkan bahwa di setiap langkah M diteruskan ke node yang lebih dekat dengan D dari node saat ini dan yang Proses ini pada akhirnya akan memberikan M untuk aktif simpul terdekat D. Tapi seperti Skema routing jelas sangat tidak efisien, membutuhkan ~ N / 2l hop untuk menyampaikan pesan dalam jaringan dengan N node.

Tahap II: Bagian kedua dari penjelasan kami menggambarkan algoritma Pastry penuh dan menunjukkan seberapa efisien routing dicapai dengan bantuan tabel routing.

Setiap node Pastry mempertahankan tabel routing pohon-terstruktur memberikan panduan dan Alamat IP untuk satu set node tersebar di seluruh rentang 2128 mungkin nilai GUID, dengan peningkatan kepadatan cakupan untuk panduan numerik dekat dengan nya sendiri.

Gambar 10.7 menunjukkan struktur dari tabel routing untuk node tertentu, dan Gambar 10.8 menggambarkan tindakan dari algoritma routing. Tabel routing disusun sebagai berikut: GUID dipandang sebagai nilai-nilai heksadesimal dan meja mengklasifikasikan GUID berdasarkan awalan heksadesimal mereka. tabel memiliki banyak baris sebagai ada heksadesimal digit dalam GUID, sehingga untuk sistem Pastry prototipe yang kita yang menggambarkan, ada 128/4 = 32 baris. Setiap baris n berisi 15 entri - satu untuk setiap nilai yang mungkin dari digit heksadesimal n, tidak termasuk nilai di lokal

Proses routing pada setiap simpul A menggunakan informasi dalam tabel routing R dan daun set L untuk menangani setiap permintaan dari aplikasi dan setiap pesan yang masuk dari node lain sesuai dengan algoritma yang ditunjukkan pada Gambar 10.9.

Kita dapat yakin bahwa algoritma akan berhasil dalam memberikan M ke tujuan karena baris 1, 2 dan 7 melakukan tindakan yang diuraikan di Tahap I dari uraian di atas, dan kami telah menunjukkan ini menjadi, algoritma routing yang lengkap, meskipun tidak efisien. Itu langkah yang tersisa dirancang untuk menggunakan tabel routing untuk meningkatkan algoritma kinerja dengan mengurangi jumlah hop yang diperlukan.

Baris 4-5 ikut bermain kapanpun D tidak jatuh dalam kisaran angka dari daun node saat ini mengatur dan relevan entri tabel routing yang tersedia. Seleksi dari tujuan untuk hop berikutnya melibatkan membandingkan angka heksadesimal D dengan orang-orang dari A (GUID node saat ini) dari kiri ke kanan untuk menemukan panjang, p, dari prefix umum terpanjang mereka. Panjang ini kemudian digunakan sebagai baris offset, bersama-sama dengan pertama digit non-pencocokan D sebagai kolom offset, untuk mengakses elemen yang diperlukan dari tabel routing. Pembangunan meja memastikan bahwa unsur ini (jika tidak kosong) berisi alamat IP dari node yang GUID memiliki p + 1 digit prefix yang sama dengan D. Baris 7 digunakan ketika D jatuh di luar rentang numerik dari set daun dan tidak ada entri tabel routing yang relevan. Kasus ini jarang terjadi; itu hanya muncul ketika node baru-baru ini gagal dan meja belum diperbarui. Algoritma routing dapat melanjutkan dengan pemindaian kedua set daun dan tabel routing dan forwarding M ke node lain yang GUID memiliki p pencocokan digit prefix tapi numerik lebih dekat dengan D. Jika node yang ada di L, maka kita mengikuti prosedur Tahap I diilustrasikan pada Gambar 10.6. Jika dalam R, maka itu harus lebih dekat ke D dari setiap node di L, maka kita meningkatkan pada Tahap I. integrasi tuan rumah • node New menggunakan protokol bergabung dalam rangka memperoleh routing meja dan daun set isi dan memberitahukan node lain dari perubahan mereka harus membuat untuk mereka tabel. Pertama, simpul baru menghitung GUID cocok (biasanya dengan menerapkan SHA-1 fungsi hash untuk kunci publik node), maka itu membuat kontak dengan node Pastry terdekat. (Di sini kita menggunakan istilah terdekat untuk merujuk pada jarak jaringan, yaitu, sejumlah kecil hop jaringan atau keterlambatan transmisi rendah; lihat kotak di bawah.)

Misalkan node baru GUID adalah X dan itu kontak simpul terdekat telah GUID A. Node X mengirimkan bergabung pesan permintaan khusus untuk A, memberikan X sebagai tujuan. SEBUAH despatches bergabung pesan melalui Pastry dengan cara biasa. Pastry kehendak rute bergabung pesan ke node yang ada yang GUID adalah numerik terdekat X; mari kita sebut ini node tujuan Z.

A, Z dan semua node (B, C, ...) melalui mana bergabung pesan yang diarahkan pada perusahaan cara untuk Z menambahkan langkah tambahan untuk algoritma Pastry routing yang normal, yang mengakibatkan transmisi dari isi bagian yang relevan dari tabel routing mereka dan set daun untuk X. X meneliti mereka dan membangun sendiri tabel routing dan daun set dari mereka, meminta beberapa informasi tambahan dari node lain jika diperlukan.

Untuk melihat bagaimana X membangun tabel routing, perhatikan bahwa baris pertama dari tabel tergantung pada nilai GUID X, dan untuk meminimalkan jarak routing, tabel harus dibangun untuk rute pesan melalui node tetangga bila memungkinkan. A adalah tetangga X, sehingga baris pertama dari tabel A adalah pilihan awal yang baik untuk baris pertama table X, X0. Di sisi lain, meja A mungkin tidak relevan untuk baris kedua, X1, karena X dan GUID A mungkin tidak berbagi sama digit heksadesimal pertama. Itu algoritma routing memastikan bahwa X dan B GUID jangan berbagi digit pertama yang sama, meskipun, yang menyiratkan bahwa baris kedua dari B tabel routing, B1, adalah nilai awal yang cocok untuk X1. Demikian pula, C2 cocok untuk X2, dan sebagainya.

Selanjutnya, mengingat sifat dari set daun, perhatikan bahwa karena Z GUID adalah numerik terdekat X, set daun X harus sama dengan Z. Bahkan, yang ideal set daun X akan berbeda dari Z dengan hanya satu anggota. set daun Z karena itu diambil sebagai memadai Perkiraan awal, yang pada akhirnya akan dioptimalkan melalui interaksi dengan yang tetangga seperti yang dijelaskan dalam toleransi kesalahan ayat di bawah ini.

Akhirnya, setelah X telah dibangun daun yang ditetapkan dan tabel routing dengan cara yang diuraikan di atas, ia akan mengirimkan isinya ke semua node diidentifikasi pada set daun dan routing meja dan mereka menyesuaikan meja mereka sendiri untuk menggabungkan node baru. Seluruh tugas menggabungkan simpul baru ke dalam infrastruktur Pastry memerlukan transmisi O (log N) pesan.

Tuan rumah gagal atau keberangkatan • Nodes dalam infrastruktur Pastry mungkin gagal atau pergi tanpa peringatan. Sebuah node Pastry dianggap gagal ketika tetangga terdekatnya (di GUID ruang) tidak bisa lagi berkomunikasi dengannya. Ketika ini terjadi, perlu untuk memperbaiki daun set yang berisi GUID node gagal ini.

algoritma tetangga terdekat

Node baru harus memiliki alamat node Pastry setidaknya sudah ada, tapi mungkin tidak di dekatnya. Untuk memastikan bahwa node terdekat dikenal Pastry mencakup 'Tetangga terdekat' algoritma untuk menemukan node terdekat dengan rekursif mengukur round-trip delay untuk pesan penyelidikan dikirim secara berkala untuk setiap anggota himpunan daun dari terdekat simpul Pastry saat ini dikenal.

Untuk memperbaiki nya daun set L, node yang menemukan kegagalan mencari node hidup dekat dengan node gagal dalam L dan meminta salinan simpul yang daun set, L '. L 'akan berisi urutan GUID yang sebagian tumpang tindih mereka di L, termasuk satu dengan yang sesuai Nilai untuk menggantikan node gagal. node tetangga lainnya kemudian diberitahu tentang kegagalan dan mereka melakukan prosedur yang sama. prosedur perbaikan ini menjamin daun yang set akan diperbaiki kecuali l node adjacently bernomor gagal secara bersamaan.

Perbaikan untuk tabel routing yang dibuat pada 'ketika ditemukan' dasar. Routing pesan dapat melanjutkan dengan beberapa entri tabel routing yang tidak lagi hidup – gagal upaya routing yang mengakibatkan penggunaan entri berbeda dari baris yang sama dari routing meja.

Lokalitas • Struktur Pastry routing yang sangat berlebihan: ada banyak rute antara masing-masing pasangan node. Pembangunan tabel routing bertujuan untuk mengambil keuntungan dari redundansi ini untuk mengurangi sebenarnya kali transmisi pesan dengan memanfaatkan sifat lokalitas node dalam jaringan transportasi yang mendasari (yang biasanya subset node di internet).

Ingatlah bahwa setiap baris dalam tabel routing berisi 16 entri. Entri dalam engan baris memberikan alamat dari 16 node dengan GUID dengan i-1 digit heksadesimal awal yang cocok GUID node saat ini dan digit engan yang mengambil masing-masing mungkin nilai-nilai heksadesimal. Sebuah Pastry overlay baik penduduknya akan berisi lebih banyak node daripada yang bisa terkandung dalam tabel routing individu; setiap kali tabel routing baru sedang dibangun pilihan dibuat untuk setiap posisi antara beberapa kandidat (diambil dari informasi routing yang diberikan oleh node lain) berdasarkan pada tetangga dekat algoritma seleksi [Gummadi et al. 2003]. Sebuah metrik lokalitas (jumlah IP hop atau diukur latency) digunakan untuk membandingkan kandidat dan tersedia simpul terdekat adalah terpilih. Karena informasi yang tersedia tidak komprehensif, mekanisme ini tidak bisa menghasilkan routings global yang optimal, namun simulasi menunjukkan bahwa hasil dalam rute yang rata-rata hanya sekitar 30-50% lebih lama dari yang optimal.

Toleransi kesalahan • Seperti dijelaskan di atas, algoritma Pastry routing yang mengasumsikan bahwa semua entri dalam tabel routing dan set daun merujuk untuk hidup, benar berfungsi node. semua node mengirim 'detak jantung' pesan (misalnya, pesan yang dikirim pada interval waktu yang tetap untuk menunjukkan bahwa pengirim hidup) ke node tetangga di set daun mereka, tetapi informasi tentang gagal node terdeteksi dengan cara ini mungkin tidak disebarluaskan cukup cepat untuk menghilangkan kesalahan routing. Juga tidak menjelaskan node berbahaya yang mungkin mencoba untuk mengganggu routing yang benar. Untuk mengatasi masalah ini, klien yang bergantung pada pesan terpercaya pengiriman diharapkan untuk mempekerjakan mekanisme pengiriman di-setidaknya-sekali (lihat Bagian 5.3.1) dan ulangi permintaan mereka beberapa kali dengan tidak adanya tanggapan. Ini akanmemungkinkan Pastry lagi jendela waktu untuk mendeteksi dan kegagalan perbaikan simpul.

Untuk menangani setiap kegagalan yang tersisa atau node berbahaya, tingkat kecil keacakan dimasukkan ke dalam algoritma pemilihan rute yang dijelaskan pada Gambar 10.9. Pada dasarnya, langkah sejalan 5 dari Gambar 10.9 dimodifikasi kecil dipilih secara acak Proporsi kasus untuk menghasilkan awalan umum yang kurang dari panjang maksimum. Ini Hasil dalam penggunaan routing diambil dari baris sebelumnya dari tabel routing, memproduksi kurang optimal tetapi berbeda routing yang dari versi standar dari algoritma. Dengan ini variasi acak dalam algoritma routing yang, transmisi ulang klien harus akhirnya berhasil bahkan di hadapan sejumlah kecil node berbahaya.

Ketergantungan • Penulis Pastry telah mengembangkan versi terbaru yang disebut Pastry [Castro et al. 2003] yang menggunakan algoritma routing yang sama dan tuan rumah yang serupa metode manajemen, tetapi juga mencakup beberapa langkah ketergantungan tambahan dan beberapa optimasi kinerja dalam algoritma manajemen tuan rumah.

Tindakan ketergantungan termasuk penggunaan ucapan terima kasih pada setiap hop di algoritma routing. Jika tuan rumah pengiriman tidak menerima pengakuan setelah batas waktu yang ditentukan, ia memilih rute alternatif dan mentransmisikan kembali pesan. Node yang gagal untuk mengirim sebuah pengakuan kemudian dicatat sebagai kegagalan dicurigai.

Seperti disebutkan di atas, untuk mendeteksi node gagal setiap node Pastry berkala mengirimkan pesan detak jantung ke tetangga terdekatnya ke kiri (yaitu, dengan GUID rendah) di daun ditetapkan. Setiap node juga mencatat waktu pesan detak jantung terakhir yang diterima dari-nya segera tetangga di sebelah kanan (dengan GUID yang lebih tinggi). Jika interval sejak terakhir detak jantung melebihi ambang batas waktu, node mendeteksi memulai prosedur perbaikan yang melibatkan menghubungi node yang tersisa di set daun dengan pemberitahuan tentang gagal node dan permintaan untuk penggantian yang disarankan. Bahkan dalam kasus beberapa kegagalan simultan, prosedur ini berakhir dengan semua node di sisi kiri gagal simpul memiliki daun set yang berisi l hidup node dengan GUIDs terdekat.

Kita telah melihat bahwa algoritma routing dapat berfungsi dengan benar menggunakan set daun sendirian; tapi pemeliharaan tabel routing penting untuk kinerja. Tersangka node gagal dalam tabel routing yang diselidiki dengan cara yang sama dengan yang digunakan untuk set daun dan jika mereka gagal untuk merespon, entri tabel routing mereka diganti dengan yang sesuai alternatif yang diperoleh dari node terdekat. Selain itu, protokol gosip sederhana (lihat Bagian 18.4.1) digunakan untuk secara berkala bertukar informasi tabel routing antara node untuk memperbaiki entri gagal dan mencegah kerusakan lambat lokalitas properti. Protokol gosip dijalankan setiap 20 menit.

evaluasi kerja • Castro dan rekan-rekannya telah melakukan suatu yang lengkap evaluasi kinerja MSPastry, bertujuan untuk menentukan dampak pada kinerja dan ketergantungan dari tuan rumah bergabung tingkat / cuti dan ketergantungan terkait mekanisme [Castro et al. 2003].

Evaluasi ini dilakukan dengan menjalankan sistem MSPastry bawah kendali simulator berjalan pada mesin tunggal yang mensimulasikan jaringan besar host, dengan message passing digantikan oleh penundaan transmisi simulasi. simulasi realistis dimodelkan bergabung / meninggalkan perilaku host dan penundaan transmisi IP berdasarkan parameter dari instalasi nyata. Semua mekanisme ketergantungan dari MSPastry dimasukkan, dengan realistis interval untuk penyelidikan dan pesan detak jantung. Pekerjaan simulasi divalidasi oleh perbandingan dengan pengukuran yang dilakukan dengan MSPastry menjalankan beban aplikasi nyata di jaringan internal dengan 52 node.

Di sini kita merangkum hasil kunci.

Ketergantungan: Dengan tingkat kerugian pesan diasumsikan IP 0%, MSPastry gagal memberikan 1,5 100.000 permintaan (mungkin karena tidak tersedianya tujuan host), dan semua permintaan yang disampaikan tiba di node yang benar.

Dengan tingkat kerugian pesan diasumsikan IP dari 5%, MSPastry kehilangan sekitar 3,3 di 100.000 permintaan dan 1,6 di 100.000 permintaan dikirim ke node yang salah. Itu penggunaan pengakuan per-hop di MSPastry memastikan bahwa semua hilang atau salah arah pesan akhirnya dipancarkan kembali dan mencapai node yang benar.

Kinerja: Metrik digunakan untuk mengevaluasi kinerja Pastry disebut relatif penundaan hukuman (RDP) [Chu et al. 2000], atau peregangan. RDP adalah ukuran langsung dari tambahan biaya yang dikeluarkan dalam mempekerjakan lapisan overlay routing. Ini adalah rasio antara keterlambatan rata-rata dalam memberikan permintaan oleh routing overlay dan dalam memberikan pesan serupa antara dua node yang sama melalui UDP / IP. Nilai-nilai RDP diamati untuk MSPastry bawah beban simulasi berkisar dari ~ 1,8 dengan pesan jaringan nol kerugian ~ 2.2 dengan 5% loss pesan jaringan.

Overhead: The beban jaringan ekstra yang dihasilkan oleh lalu lintas kontrol - pesan yang terlibat dalam mempertahankan set daun dan tabel routing - kurang dari 2 pesan per menit per simpul. RDP dan pengendalian lalu lintas yang baik meningkat secara signifikan untuk sesi panjang kurang dari 60 menit karena overhead pengaturan awal.

Secara keseluruhan hasil ini menunjukkan bahwa overlay routing yang lapisan dapat dibangun yang mencapai kinerja yang baik dan kehandalan yang tinggi dengan ribuan node yang beroperasi di realistis lingkungan. Bahkan dengan rata-rata durasi sesi yang lebih pendek dari 60 menit dan tinggi kesalahan jaringan tarif sistem degradasi anggun, terus memberikan yang efektif layanan.

Mengoptimalkan overlay lookup latency • Zhang et al. [2005a] telah menunjukkan bahwa lookup kinerja kelas penting dari jaringan overlay (termasuk Pastry, Chord dan Tapestry) dapat secara substansial ditingkatkan dengan dimasukkannya algoritma pembelajaran sederhana yang mengukur latency benar-benar mengalami dalam mengakses node overlay dan dengan demikian secara bertahap memodifikasi overlay tabel routing untuk mengoptimalkan latency akses.

10.5.2 Tapestry

Tapestry mengimplementasikan tabel hash didistribusikan dan rute pesan ke kelenjar berdasarkan GUID terkait dengan sumber daya menggunakan prefix routing dalam cara yang mirip dengan Pastry. Tapi API permadani ini menyembunyikan tabel hash didistribusikan dari aplikasi belakang DOLR a antarmuka seperti yang ditunjukkan pada Gambar 10.5. Node yang memegang sumber daya menggunakan mempublikasikan (GUID) primitif untuk membuat mereka dikenal Tapestry, dan pemegang sumber tetap bertanggung jawab untuk menyimpan mereka. sumber direplikasi diterbitkan dengan sama GUID oleh setiap node yang memegang replika, mengakibatkan beberapa entri di Tapestry yang struktur routing.

Hal ini memberikan aplikasi Tapestry fleksibilitas tambahan: mereka dapat menempatkan replika dekat (dalam jarak jaringan) untuk pengguna yang sering sumber daya untuk mengurangi latency dan meminimalkan beban jaringan atau untuk memastikan toleransi jaringan dan host kegagalan. Tapi ini perbedaan antara Pastry dan Tapestry tidak mendasar: aplikasi Pastry bisa mencapai fleksibilitas yang sama dengan membuat objek yang terkait dengan GUID hanya bertindak sebagai proxy untuk lebih level aplikasi objek yang kompleks dan Tapestry dapat digunakan untuk mengimplementasikan tabel hash didistribusikan dalam hal API DOLR nya [Dabek et al. 2003].

Dalam Tapestry 160-bit pengenal yang digunakan untuk merujuk baik ke objek dan ke kelenjar yang melakukan tindakan routing. Pengidentifikasi yang baik NodeIds, yang merujuk pada komputer yang melakukan operasi routing, atau GUIDs, yang merujuk pada objek. Untuk sumber daya apapun dengan GUID G ada simpul akar unik dengan GUID RG yang numerik terdekat G. Host H memegang replika G berkala memanggil mempublikasikan (G) untuk memastikan bahwa baru tiba host menyadari keberadaan G. Pada setiap permintaan dari mempublikasikan (G) a mempublikasikan pesan disalurkan dari Invoker menuju simpul RG. Pada penerimaan mempublikasikan RG pesan masuk (G, IPH), pemetaan antara G dan alamat IP host pengirim di tabel routing, dan setiap node sepanjang jalur publikasi cache pemetaan yang sama. Proses ini diilustrasikan pada Gambar 10.10. Ketika node tahan beberapa (G, IP) pemetaan untuk GUID yang sama, mereka diurutkan menurut jarak jaringan (round-trip time) ke IP alamat. Untuk obyek direplikasi hasil ini dalam pemilihan replika terdekat yang tersedia dari objek sebagai tujuan untuk pesan berikutnya dikirim ke objek.

Zhao et al. [2004] memberikan rincian lengkap dari algoritma Tapestry routing dan yang manajemen tabel routing Tapestry dalam menghadapi node kedatangan dan keberangkatan. Mereka kertas termasuk data evaluasi kinerja yang komprehensif berdasarkan simulasi jaringan Tapestry skala besar, yang menunjukkan bahwa kinerjanya mirip dengan Pastry ini. Di Bagian 10.6.2 kita menggambarkan toko berkas OceanStore, yang telah dibangun dan disebarkan lebih Tapestry.

10.5.3 Dari terstruktur untuk tidak terstruktur peer-to-peer

diskusi sejauh ini telah difokuskan secara eksklusif pada apa yang dikenal sebagai terstruktur peer-topeer pendekatan. Dalam pendekatan terstruktur, ada yang mengatur kebijakan global secara keseluruhan topologi jaringan, penempatan obyek dalam jaringan dan routing atau fungsi pencarian digunakan untuk menemukan objek dalam jaringan. Dengan kata lain, ada yang spesifik (Didistribusikan) struktur data yang mendasari overlay terkait dan satu set algoritma operasi lebih dari struktur data. Ini jelas dapat dilihat dalam contoh Pastry dan Tapestry berdasarkan tabel hash didistribusikan mendasari dan struktur cincin yang terkait. Karena struktur dikenakan, algoritma tersebut efisien dan menawarkan batas waktu lokasi objek, tetapi pada biaya pemeliharaan struktur yang mendasari, sering di lingkungan yang sangat dinamis.

Karena argumen perawatan ini, pendekatan peer-to-peer tidak terstruktur juga telah dikembangkan. Dalam pendekatan terstruktur, tidak ada kontrol secara keseluruhan atas topologi atau penempatan obyek dalam jaringan. Sebaliknya, overlay adalah dibuat secara ad hoc, dengan setiap node yang bergabung jaringan berikut beberapa sederhana, aturan lokal untuk membangun konektivitas. Secara khusus, node bergabung akan membentuk kontak dengan satu set tetangga mengetahui bahwa tetangga juga akan terhubung ke tetangga lebih lanjut dan sebagainya, membentuk jaringan yang secara fundamental desentralisasi dan mengorganisir diri dan karenanya tahan terhadap kegagalan node. Untuk menemukan suatu objek tertentu, hal ini kemudian diperlukan untuk melaksanakan pencarian dari topologi jaringan yang dihasilkan; jelas, pendekatan ini tidak dapat menawarkan jaminan untuk bisa menemukan objek dan kinerja akatak terduga.

Selain itu, ada risiko nyata menghasilkan lalu lintas pesan yang berlebihan untuk

menemukan benda. Ringkasan kekuatan relatif dari terstruktur dan tidak terstruktur peer-to-peer sistem disediakan pada Gambar 10.11. Sangat menarik untuk mencerminkan bahwa, meskipun jelas kelemahan terstruktur sistem peer-to-peer, pendekatan ini adalah yang dominan di Internet, khususnya dalam mendukung peer-to-peer file sharing (dengan sistem seperti Gnutella, FreeNet dan BitTorrent semua mengadopsi pendekatan terstruktur). Seperti yang akan dilihat, kemajuan signifikan telah dibuat dalam sistem tersebut untuk meningkatkan kinerja pendekatan terstruktur dan pekerjaan ini adalah signifikan mengingat jumlah lalu lintas yang dihasilkan oleh peer-to-peer file sharing di Internet (misalnya, sebuah studi dilakukan di tahun-tahun 2008/9 menunjukkan bahwa peer-to-peer file sharing aplikasi account untuk antara 43% dan 70% dari semua lalu lintas internet, tergantung pada bagian dari dunia sedang dipertimbangkan [www.ipoque.com]).

Strategi untuk pencarian yang efektif • Dalam peer-to-peer file sharing, semua node dalam jaringan menawarkan file ke lingkungan yang lebih besar. Seperti disebutkan di atas, masalah mencari file kemudian memetakan ke pencarian dari seluruh jaringan untuk mencari file yang sesuai. Jika diimplementasikan naif, ini akan dilaksanakan oleh banjir jaringan dengan permintaan. Ini adalah tepatnya strategi yang diterapkan dalam versi awal Gnutella. Secara khusus, di Gnutel la0,4, setiap simpul diteruskan permintaan untuk setiap tetangganya, yang kemudian pada gilirannya berlalu ni ke tetangga mereka, dan seterusnya sampai pertandingan ditemukan. Setiap pencarian juga dibatasi dengan bidang time-to-live membatasi jumlah hop. Pada saat Gnutella 0,4 ditempatkan, konektivitas rata-rata adalah sekitar 5 tetangga per node. Ini Pendekatan sederhana tapi tidak skala dan cepat banjir jaringan dengan pencarian terkait lalu lintas.

Sejumlah perbaikan telah dikembangkan untuk pencarian di terstruktur jaringan [Lv et al. 2002, Tsoumakos dan Roussopoulos 2006], termasuk:

Memperluas pencarian cincin: Dalam pendekatan ini, node memulai melakukan serangkaian Pulang dengan meningkatnya nilai di bidang time-to-live, mengakui bahwa signifikan jumlah permintaan akan dipenuhi secara lokal (terutama jika digabungkan dengan efektif strategi replikasi, seperti dibahas di bawah).

Acak berjalan: Dengan random berjalan, node memulai set off sejumlah pejalan kaki yang mengikuti jalur acak mereka sendiri melalui grafik yang saling berhubungan yang ditawarkan oleh overlay terstruktur.

Bergosip: Dalam pendekatan bergosip, node mengirimkan permintaan ke tetangga diberikan dengan probabilitas tertentu, dan karenanya permintaan merambat melalui jaringan dengan cara mirip dengan virus melalui populasi (seperti, protokol gosip juga disebut protokol epidemi). probabilitas dapat baik diperbaiki untuk jaringan tertentu atau dihitung secara dinamis berdasarkan pengalaman sebelumnya dan / atau konteks saat ini. (Perhatikan bahwa bergosip adalah teknik umum dalam sistem terdistribusi; lanjut aplikasi dapat ditemukan dalam Bab 6 dan 18).

Strategi tersebut dapat secara signifikan mengurangi overhead pencarian di jaringan terstruktur dan karenanya meningkatkan skalabilitas dari algoritma. Strategi tersebut juga sering didukung oleh teknik replikasi yang sesuai. Dengan mereplikasi konten di nomor dari rekan-rekan, probabilitas penemuan efisien file tertentu secara signifikan ditingkatkan. Teknik meliputi seluruh replikasi file dan hamburan fragmen file di Internet - pendekatan yang digunakan secara efektif dalam BitTorrent, misalnya, untuk mengurangi beban pada satu rekan dalam men-download file besar (lihat Bab 20).

Studi kasus: Gnutella • Gnutella awalnya diluncurkan pada tahun 2000 dan sejak itu memiliki berkembang menjadi salah satu yang dominan dan paling berpengaruh peer-to-peer file- sharing aplikasi. Seperti disebutkan di atas, awalnya protokol mengadopsi banjir agak sederhana Strategi yang tidak skala sangat baik. Menanggapi ini, Gnutella 0,6 memperkenalkan berbagai modifikasi yang telah secara signifikan meningkatkan kinerja protokol.

Perubahan besar pertama adalah untuk pindah dari arsitektur peer-to-peer murni di mana semua node yang sama dengan satu di mana semua rekan-rekan masih bekerja sama untuk menawarkan layanan tetapi beberapa node, yang ditunjuk untuk memiliki sumber daya tambahan, yang terpilih sebagai ultrapeers, dan bentuk jantung jaringan, dengan rekan-rekan lainnya mengambil peran node daun (atau daun). Daun menghubungkan diri ke sejumlah kecil ultrapeers yang sangat terhubung untuk ultrapeers lain (dengan lebih dari 32 koneksi masing-masing). Hal ini secara dramatis mengurangi jumlah maksimum hop diperlukan untuk pencarian lengkap. Ini gaya peer-to-peer arsitektur disebut sebagai arsitektur hybrid dan juga pendekatan yang digunakan dalam Skype (seperti dibahas dalam Bagian 4.5.2).

Peningkatan utama lainnya adalah pengenalan Protocol Query Routing (QRP) dirancang untuk mengurangi jumlah permintaan yang dikeluarkan oleh kelenjar. Protokol ini didasarkan pada pertukaran informasi tentang file yang terdapat pada node dan karenanya hanya forwarding query ke jalan di mana sistem berpikir akan ada hasil yang positif. Agak dari berbagi informasi tentang file secara langsung, protokol menghasilkan satu set nomor dari hashing pada kata-kata individu dalam nama file. Misalnya, nama file seperti "Bab sepuluh pada P2P" akan diwakili oleh empat nomor, mengatakan <65, 47, 09, 76>. Sebuah node menghasilkan Table Query Routing (QRT) yang mengandung nilai-nilai hash yang mewakili masing-masing file yang terdapat pada simpul yang kemudian mengirimkan ke semua teman ultra terkait. Ultra Peer kemudian menghasilkan Tabel Query Routing mereka sendiri berdasarkan kesatuan dari semua entri dari semua daun yang terhubung bersama-sama dengan entri untuk file yang terdapat dalam node, dan pertukaran ini dengan ultrapeers terhubung lainnya. Dengan cara ini, ultrapeers bisa menentukan jalur menawarkan rute yang valid untuk query yang diberikan, sehingga secara signifikan mengurangi jumlah lalu lintas yang tidak perlu. Lebih khusus, sebuah ultrapeer akan meneruskan query ke node jika kecocokan ditemukan (menunjukkan node yang memiliki file) dan akan melaksanakan cek yang sama sebelum diteruskan ke ultrapeer lain jika itu adalah hop terakhir ke file. Catatan bahwa, untuk menghindari overloading dari ultrapeers, node akan mengirim permintaan ke satu ultrapeer pada satu waktu dan kemudian menunggu untuk jangka waktu tertentu untuk melihat apakah mereka mendapatkan respon yang positif.

Akhirnya, permintaan di Gnutella berisi alamat jaringan memulai ultrapeer, yang menyiratkan bahwa setelah file ditemukan dapat dikirim langsung ke terkait ultrapeer (menggunakan UDP), menghindari traversal sebaliknya melalui grafik.

Unsur-unsur utama yang terkait dengan Gnutella 0,6 dirangkum dalam Gambar 10.12. The lapisan routing overlay dijelaskan di bagian sebelumnya telah dimanfaatkan dalam beberapa percobaan aplikasi dan aplikasi yang dihasilkan telah secara ekstensif dievaluasi. Kami telah memilih tiga dari mereka untuk studi lebih lanjut, web caching Squirrel layanan berdasarkan Pastry, dan OceanStore dan Ivy toko berkas.

web cache 10.6.1 Squirrel

Para penulis dari Pastry telah mengembangkan Squirrel peer-to-peer layanan web caching untuk digunakan dalam jaringan lokal dari komputer pribadi [Iyer et al. 2002]. Dalam menengah dan besar lokal jaringan web caching biasanya dilakukan dengan menggunakan komputer dedicated server atau gugus. Sistem Squirrel melakukan tugas yang sama dengan memanfaatkan penyimpanan dan sumber daya komputasi sudah tersedia di komputer desktop di jaringan lokal. Kami pertama memberikan gambaran umum singkat tentang pengoperasian layanan web caching, maka kita garis desain Squirrel dan meninjau efektivitas.

caching web • Web browser menghasilkan permintaan HTTP GET untuk objek internet seperti halaman HTML, gambar, dll ini dapat dilayani dari cache browser pada klien mesin, dari cache web proxy (layanan yang berjalan pada komputer lain dalam yang sama jaringan lokal atau pada node terdekat di internet) atau dari asal web server ( Server yang nama domain termasuk dalam parameter permintaan GET), tergantung yang berisi salinan dari objek. Cache lokal dan Proxy masing-masing berisi mengatur objek baru diambil diselenggarakan untuk pencarian cepat dengan URL. Beberapa benda yang uncacheable karena mereka dihasilkan secara dinamis oleh server dalam menanggapi setiap permintaan.

Ketika cache browser atau web cache proxy yang menerima permintaan GET, ada tiga kemungkinan: objek yang diminta uncacheable, ada cache miss atau objek yang ditemukan dalam cache. Dalam dua kasus pertama permintaan tersebut diteruskan ke tingkat berikutnya menuju asal web server. Ketika objek yang diminta ditemukan dalam cache, cache copy harus diuji untuk kesegaran.

objek web disimpan dalam server web dan server tembolok dengan beberapa tambahan nilai-nilai metadata termasuk cap waktu memberikan tanggal modifikasi terakhir (T) dan mungkin waktu-to-live (t) atau ETag (hash dihitung dari isi halaman web). item metadata ini disediakan oleh server asal setiap kali sebuah objek dikembalikan untuk klien.

Objek yang memiliki terkait waktu-to-live t, dianggap segar jika T + t adalah kemudian daripada real time saat ini. Untuk obyek tanpa waktu-ke-hidup, perkiraan nilai untuk t adalah digunakan (sering hanya beberapa detik). Jika hasil evaluasi kesegaran ini positif, objek cache dikembalikan ke klien tanpa menghubungi asal web server. Jika tidak, GET bersyarat (cGET) permintaan dikeluarkan ke tingkat berikutnya untuk validasi. Ada dua tipe dasar permintaan cGET: sebuah Jika-Diubah-Sejak permintaan yang berisi timestamp modifikasi terakhir yang diketahui, dan permintaan Jika-Tidak-Match mengandung etag mewakili isi objek. Permintaan cGET ini dapat dilayani baik oleh web cache lain atau oleh server asal. Cache web yang menerima permintaan cGET dan tidak memiliki salinan dari objek meneruskan permintaan terhadap web asal Server. Tanggapan mengandung baik seluruh objek, atau pesan tidak dimodifikasi jika objek cache tidak berubah.

Setiap kali sebuah objek disimpan di cache baru dimodifikasi diterima dari server asal, itu akan ditambahkan ke set dari objek dalam cache lokal (menggusur benda tua yang masih valid jika perlu) bersama-sama dengan catatan waktu, waktu-untuk-hidup dan etag jika tersedia. Skema yang dijelaskan di atas adalah dasar dari operasi untuk proxy terpusat layanan web caching dikerahkan di sebagian besar jaringan lokal yang mendukung sejumlah besar web klien. Proxy cache web biasanya diimplementasikan sebagai proses multi-threaded berjalan pada host yang berdedikasi tunggal atau satu set proses yang berjalan pada sekelompok komputer dan membutuhkan kuantitas besar sumber daya yang berdedikasi komputasi dalam kedua kasus.

Tupai • The Squirrel layanan web caching melakukan fungsi yang sama menggunakan kecil

bagian dari sumber daya dari setiap komputer client pada jaringan lokal. SHA-1 hash aman

fungsi diterapkan pada URL dari setiap objek cache untuk menghasilkan 128-bit Pastry GUID. Karena GUID tidak digunakan untuk memvalidasi isi, hal ini tidak perlu didasarkan pada seluruh orang keberatan isinya, seperti di aplikasi Pastry lainnya. Para penulis Squirrel mendasarkan mereka pembenaran untuk ini pada argumen end-to-end (Bagian 2.3.3), dengan alasan bahwa keaslian suatu halaman web dapat dikompromikan di banyak titik di perjalanannya dari tuan rumah untuk klien; otentikasi halaman cache menambahkan sedikit untuk jaminan keseluruhan keaslian dan protokol HTTPS (menggabungkan Transport Layer end-to-end Keamanan, dibahas dalam Bagian 11.6.3) harus digunakan untuk mencapai jaminan yang lebih baik bagi mereka interaksi yang memerlukannya.

Dalam pelaksanaan sederhana Squirrel - yang terbukti menjadi yang paling efektif satu - node yang GUID adalah numerik paling dekat dengan GUID dari sebuah objek menjadi simpul rumah yang objek, yang bertanggung jawab untuk memegang salinan cache dari objek ketika ada satu.

Node klien dikonfigurasi untuk menyertakan proses Squirrel proxy lokal, yang mengambil Tanggung jawab untuk kedua caching lokal dan remote objek web. Jika salinan dari objek diperlukan tidak dalam cache lokal, rute Squirrel permintaan Dapatkan atau permintaan cGet (Bila ada salinan basi objek dalam cache lokal) melalui Pastry ke node rumah. Jika node rumah memiliki salinan, langsung merespon klien dengan tidak dimodifikasi pesan atau salinan, yang sesuai. Jika node rumah memiliki salinan basi atau tidak ada salinan objek, mengeluarkan cGet atau Dapatkan untuk server asal masing-masing. Asal Server mungkin merespon dengan pesan tidak dimodifikasi atau salinan objek. Dalam kasus yang pertama, yang rumah simpul revalidates entri cache dan meneruskan salinan objek untuk klien. Di kasus terakhir, itu meneruskan salinan nilai baru untuk klien dan menempatkan salinan di nya cache lokal jika objek disimpan di cache.

Evaluasi Squirrel • Squirrel dievaluasi dengan simulasi menggunakan beban dimodelkan berasal dari jejak aktivitas cache web proxy yang terpusat yang ada di dua nyata lingkungan kerja dalam Microsoft, satu dengan 105 klien aktif (di Cambridge) dan yang lainnya dengan lebih dari 36.000 (di Redmond). evaluasi membandingkan kinerja cache web Squirrel dengan satu terpusat di tiga hal:

Penurunan total bandwidth yang eksternal digunakan: Bandwidth eksternal total berbanding terbalik dengan rasio hit, karena hanya cache misses yang menghasilkan permintaan ke server web eksternal. Rasio hit diamati cache server web terpusat adalah 29% (untuk Redmond) dan 38% (untuk Cambridge). Ketika aktivitas log yang sama digunakan untuk menghasilkan beban simulasi untuk cache Squirrel, dengan setiap klien kontribusi 100 Mbytes penyimpanan disk, rasio hit sangat mirip dari 28% (Redmond) dan 37% (Cambridge) dicapai. Ini mengikuti bahwa bandwidth eksternal akan dikurangi dengan proporsi yang sama.

Latency dirasakan oleh pengguna untuk akses ke objek web: Penggunaan routing Hasil overlay di beberapa transfer pesan (Routing hop) di jaringan lokal untuk mengirimkan permintaan dari klien untuk tuan rumah bertanggung jawab untuk caching yang relevan objek (node ​​rumah). Angka rata routing hop diamati dalam simulasi yang 4.11 hop untuk menyampaikan permintaan GET dalam kasus Redmond dan 1,8 hop dalam kasus Cambridge, sedangkan hanya transfer pesan tunggal diperlukan untuk mengakses layanan tembolok terpusat.

Namun transfer lokal mengambil hanya beberapa milidetik dengan Ethernet modern yang hardware, termasuk koneksi TCP waktu setup, sedangkan luas pesan TCP transfer di Internet membutuhkan 10-100 ms. Oleh karena itu penulis Squirrel berpendapat bahwa latency untuk akses ke benda yang ditemukan dalam cache dibanjiri oleh banyak latency lebih besar dari akses ke objek tidak ditemukan dalam cache, memberikan pengguna yang sama Pengalaman dengan yang disediakan dengan cache terpusat.

The komputasi dan penyimpanan beban yang dikenakan pada client node: Jumlah rata-rata permintaan cache yang disajikan untuk node lain oleh setiap node seluruh periode Evaluasi sangat rendah, hanya 0,31 per menit (Redmond), menunjukkan bahwa proporsi keseluruhan sumber daya sistem yang dikonsumsi sangat rendah.

Berdasarkan pengukuran yang dijelaskan di atas, penulis Squirrel menyimpulkan bahwa yang kinerja adalah sebanding dengan cache terpusat. Tupai mencapai pengurangan dalam latency diamati untuk akses halaman web dekat dengan yang dicapai oleh terpusat cache server dengan cache khusus berukuran hampir sama. Beban tambahan yang dikenakan pada node klien rendah dan cenderung tidak terlihat oleh pengguna. Sistem Squirrel adalah selanjutnya digunakan sebagai cache web utama dalam jaringan lokal dengan 52 klien mesin menggunakan Squirrel, dan hasilnya dikonfirmasi kesimpulan mereka.

toko File 10.6.2 OceanStore

Para pengembang Tapestry telah dirancang dan dibangun prototipe untuk file peer-to-peer toko. Tidak seperti MASA LALU, mendukung penyimpanan file bisa berubah. The OceanStore desain [Kubiatowicz et al. 2000; Kubiatowicz 2003; Rhea et al. 2001, 2003] bertujuan untuk memberikan skala yang sangat besar, fasilitas penyimpanan persisten secara bertahap terukur untuk data bisa berubah objek dengan ketekunan jangka panjang dan kehandalan dalam lingkungan terus-menerus mengubah jaringan dan sumber daya komputasi. OceanStore dimaksudkan untuk digunakan dalam berbagai a aplikasi termasuk pelaksanaan layanan NFS file-seperti, surat elektronik hosting, database dan aplikasi lainnya yang melibatkan berbagi dan penyimpanan persisten sejumlah besar objek data.

Desain mencakup ketentuan untuk penyimpanan direplikasi kedua bisa berubah dan objek data berubah. Mekanisme untuk menjaga konsistensi antara replika dapat disesuaikan dengan kebutuhan aplikasi dengan cara yang terinspirasi oleh sistem Bayou (Bagian 18.4.2). Privasi dan integritas yang dicapai melalui enkripsi data dan penggunaan protokol perjanjian Bizantium (lihat Bagian 15.5) untuk update ke direplikasi benda. Hal ini diperlukan karena kepercayaan dari host individu tidak dapat diasumsikan.

Sebuah OceanStore prototipe, disebut kolam [Rhea et al. 2003], telah dibangun. Ini cukup lengkap untuk mendukung aplikasi dan kinerjanya telah dievaluasi terhadap berbagai tolok ukur untuk memvalidasi desain Samudra Store dan bandingkan kinerjanya dengan pendekatan yang lebih tradisional. Dalam sisa bagian ini kita memberikan gambaran tentang desain OceanStore / kolam dan merangkum hasil evaluasi.

Kolam menggunakan mekanisme Tapestry routing yang overlay untuk menempatkan blok data pada simpul yang tersebar di internet dan untuk pengiriman permintaan kepada mereka.

Organisasi penyimpanan benda • OceanStore / Data kolam analog ke file, dengan mereka data yang disimpan dalam satu set blok. Tapi setiap objek direpresentasikan sebagai memerintahkan urutan versi abadi yang (pada prinsipnya) terus selamanya. Setiap pembaruan untuk hasil objek dalam generasi versi baru. Versi berbagi blok tidak berubah, berikut copy-on-write teknik untuk membuat dan memperbarui objek yang dijelaskan dalam Bagian 7.4.2. Jadi perbedaan kecil antara versi hanya membutuhkan sejumlah kecil tambahan penyimpanan.

Benda yang terstruktur dengan cara yang mengingatkan pada sistem pengarsipan Unix, dengan blok data yang terorganisir dan diakses melalui blok metadata disebut akar blok dan blok tipuan tambahan jika diperlukan (lih Unix i-node). tingkat lain tipuan digunakan untuk mengaitkan tekstual persisten atau nama eksternal terlihat lain (untuk Misalnya, nama path untuk file) dengan urutan versi dari objek data. Figureobjects. Hal ini diperlukan karena kepercayaan dari host individu tidak dapat diasumsikan.  10.13 menggambarkan organisasi ini. GUID terkait dengan objek (sebuah Aguid), blok root untuk setiap versi dari objek (VGUID a), blok tipuan dan blok data (membangun). Beberapa replika setiap blok disimpan di node rekan yang dipilih sesuai dengan kriteria wilayah dan ketersediaan penyimpanan, dan GUID mereka diterbitkan (Menggunakan mempublikasikan () primitif Gambar 10.5) oleh masing-masing node yang memegang replika sehingga Tapestry dapat digunakan oleh klien untuk mengakses blok.

Tiga jenis GUID digunakan, seperti yang dirangkum dalam Gambar 10.14. Dua yang pertama adalah GUID dari jenis yang biasanya ditugaskan untuk objek yang tersimpan dalam Tapestry - mereka dihitung dari isi dari blok yang relevan dengan menggunakan fungsi hash aman sehingga mereka dapat digunakan kemudian untuk mengotentikasi dan memverifikasi integritas dari isi. Blok yang mereka referensi yang selalu berubah, karena setiap perubahan isi dari blok akan membatalkan penggunaan GUID sebagai token otentikasi.

Jenis ketiga identifier yang digunakan adalah AGUIDs. Ini merujuk (secara tidak langsung) ke seluruh orang aliran versi obyek, memungkinkan klien untuk mengakses versi terbaru dari objek atau versi sebelumnya. Karena benda yang tersimpan yang bisa berubah, GUID digunakan untuk mengidentifikasi mereka tidak dapat diturunkan dari isinya, karena itu akan membuat GUID diselenggarakan di indeks, dll, usang setiap kali sebuah objek berubah.

Sebaliknya, setiap kali objek penyimpanan baru dibuat sebuah Aguid permanen dihasilkan dengan menerapkan fungsi hash yang aman untuk nama aplikasi-spesifik (misalnya, file nama yang) yang disediakan oleh klien menciptakan objek dan kunci publik yang mewakili pemilik objek (lihat Bagian 11.2.5). Dalam aplikasi sistem pengarsipan, sebuah Aguid akan disimpan di direktori terhadap setiap nama file.

Hubungan antara Aguid dan urutan versi dari objek bahwa mengidentifikasi beberapa tercatat dalam sertifikat yang ditandatangani yang disimpan dan direplikasi oleh Skema replikasi copy primer (juga disebut replikasi pasif; lihat Bagian 18.3.1). sertifikat termasuk VGUID dari versi saat ini dan blok root untuk setiap Versi berisi VGUID dari versi sebelumnya, sehingga ada rantai referensi memungkinkan klien yang memegang sertifikat untuk melintasi seluruh rantai versi (Gambar 10.13). Sebuah sertifikat yang ditandatangani diperlukan untuk memastikan bahwa hubungan tersebut adalah otentik dan memiliki telah dibuat oleh seorang kepala yang berwenang. Klien diharapkan untuk memeriksa ini. Setiap kali Versi baru dari sebuah objek dibuat, sertifikat baru dihasilkan memegang VGUID yang dari versi baru bersama-sama dengan timestamp dan nomor urut versi.

Model kepercayaan untuk peer-to-peer sistem mengharuskan pembangunan setiap baru sertifikat disepakati (seperti dijelaskan di bawah) di antara sekelompok kecil host disebut inner cincin. Setiap kali objek baru disimpan dalam OceanStore, satu set host dipilih untuk bertindak sebagai cincin batin untuk objek. Mereka menggunakan Tapestry ini mempublikasikan () primitif untuk membuat Aguid untuk objek diketahui Tapestry. Klien kemudian dapat menggunakan Tapestry permintaan dengan untuk sertifikat objek untuk salah satu simpul di cincin bagian dalam.

Sertifikat baru menggantikan salinan utama yang lama diadakan di setiap node cincin dalam dan disebarluaskan ke sejumlah besar salinan sekunder. Hal tersebut diserahkan kepada klien untuk menentukan seberapa sering mereka memeriksa versi baru (keputusan yang sama harus diambil untuk cache salinan file di NFS; kebanyakan instalasi beroperasi dengan jendela konsistensi 30 detik antara klien dan server; lihat Bagian 12.3).

Seperti biasa di peer-to-peer sistem, kepercayaan tidak dapat ditempatkan di semua host individu. Memperbarui salinan primer membutuhkan kesepakatan konsensus antara host di lingkar dalam. Mereka menggunakan versi dari algoritma kesepakatan Bizantium negara-mesin berbasis dijelaskan oleh Castro dan Liskov [2000] untuk memperbarui objek dan menandatangani sertifikat. Itu penggunaan protokol perjanjian Bizantium memastikan bahwa sertifikat tersebut dipertahankan dengan benar bahkan jika beberapa anggota cincin batin gagal atau berperilaku jahat. Karena komputasi dan komunikasi biaya kenaikan kesepakatan Bizantium dengan kuadrat jumlah host yang terlibat, jumlah host di cincin bagian disimpan kecil dan dihasilkan sertifikat direplikasi secara lebih luas menggunakan skema copy utama disebutkan atas.

Melakukan update juga melibatkan memeriksa hak akses dan serialisasi informasi dengan menulis tertunda lainnya. Setelah proses update selesai untuk copy primer, hasilnya disebarluaskan ke replika sekunder yang tersimpan di host luar cincin bagian dalam menggunakan pohon multicast routing yang dikelola oleh Tapestry.

Karena mereka bersifat read-only, blok data yang direplikasi oleh yang berbeda, lebih storage-efisien mekanisme. Mekanisme ini didasarkan pada pembagian setiap blok ke m sama besar fragmen, yang dikodekan menggunakan kode penghapusan [Weatherspoon dan Kubiatowicz 2002] untuk n fragmen, di mana n> m. Properti kunci penghapusan coding adalah bahwa adalah mungkin untuk merekonstruksi blok dari setiap m dari fragmen-nya. Dalam sistem yang menggunakan penghapusan coding semua objek data tetap tersedia dengan kerugian hingga n-m host. Dalam pelaksanaan kolam m = 16 dan n = 32, jadi untuk dua kali lipat dari biaya penyimpanan, sistem dapat mentolerir kegagalan hingga 16 host tanpa kehilangan data. Tapestry digunakan untuk menyimpan fragmen dan mengambil mereka dari jaringan.

Tingkat tinggi toleransi kesalahan dan ketersediaan data dicapai pada beberapa biaya dalam hal merekonstruksi blok dari fragmen penghapusan-kode. Untuk meminimalkan dampak ini, seluruh blok juga disimpan dalam jaringan menggunakan Tapestry. Karena mereka bisa direkonstruksi dari fragmen mereka, blok ini diperlakukan sebagai cache - mereka tidak kesalahan toleran dan mereka dapat dibuang ketika ruang penyimpanan yang diperlukan.

Kinerja • kolam dikembangkan sebagai prototipe untuk membuktikan kelayakan scalable peer-to-peer layanan file, bukan sebagai pelaksanaan produksi. Hal ini dilaksanakan di Jawa dan mencakup hampir semua desain yang diuraikan di atas. Hal itu dievaluasi terhadap beberapa tujuan-dirancang benchmark dan emulasi sederhana dari klien NFS dan server dalam hal objek OceanStore. Para pengembang menguji emulasi NFS terhadap Andrew patokan [Howard et al. 1988], yang mengemulasi pengembangan perangkat lunak beban kerja. Tabel pada Gambar 10.15 menunjukkan hasil untuk yang terakhir. Mereka diperoleh menggunakan 1 GHz Pentium III PC yang menjalankan Linux. Tes LAN yang dilakukan menggunakan Gigabit Ethernet dan hasil WAN diperoleh dengan menggunakan dua set node dihubungkan oleh Internet.

Kesimpulan yang ditarik oleh penulis adalah bahwa kinerja OceanStore / kolam ketika beroperasi melalui jaringan area luas (yaitu, Internet) substansial melebihi dari NFS untuk membaca dan dalam faktor tiga dari NFS untuk memperbarui file dan direktori; hasil LAN secara substansial lebih buruk. Secara keseluruhan, Hasil penelitian menunjukkan bahwa layanan file internet skala peer-to-peer berdasarkan OceanStore desain akan menjadi solusi efektif untuk distribusi file yang tidak berubah sangat cepat (seperti salinan cache dari halaman web). potensinya untuk digunakan sebagai alternatif untuk NFS dipertanyakan bahkan untuk jaringan wide-area dan jelas tidak kompetitif untuk murni penggunaan lokal.

Hasil ini diperoleh dengan blok data yang disimpan tanpa penghapusan-kode berbasis fragmentasi dan replikasi. Penggunaan kunci publik kontribusi besar terhadap biaya komputasi operasi Ponds. Angka-angka yang ditampilkan adalah untuk kunci 512-bit, yang keamanan baik tapi kurang sempurna. Hasil untuk kunci 1024-bit secara substansial buruk untuk fase mereka tolok ukur yang terlibat file update. hasil lainnya diperoleh dengan tolok ukur tujuan-dirancang termasuk pengukuran dampak Proses kesepakatan Bizantium pada latency update. Ini berada di kisaran 100 ms sampai 10 detik. Sebuah tes pembaruan throughput yang dicapai maksimal 100 update / detik.

sistem file 10.6.3 Ivy

Seperti OceanStore, Ivy [Muthitacharoen et al. 2002] adalah sistem membaca / menulis berkas pendukung beberapa pembaca dan penulis dilaksanakan lebih dari satu lapisan overlay routing dan didistribusikan menyimpan data hash-ditangani. Tidak seperti OceanStore, sistem file Ivy mengemulasi Sun NFS Server. Ivy menyimpan keadaan file sebagai log dari permintaan file update yang dikeluarkan oleh ivy klien dan merekonstruksi file dengan memindai log setiap kali tidak dapat memenuhi akses meminta dari cache lokal. Catatan log diadakan di DHash didistribusikan hashaddressed layanan penyimpanan [Dabek et al. 2001]. (Log pertama kali digunakan untuk merekam file yang update di sistem operasi Sprite didistribusikan [Rosenblum dan Ooosterhout 1992], seperti yang dijelaskan secara singkat dalam Bagian 12.5, tapi ada mereka digunakan hanya untuk mengoptimalkan pembaruan kinerja sistem file.)

Desain Ivy menyelesaikan beberapa isu sebelumnya yang belum terselesaikan yang timbul dari perlu meng-host file di mesin sebagian terbesar atau tidak dapat diandalkan, termasuk:

Pemeliharaan metadata file yang konsisten (lih isi i-node di Unix / berkas NFS sistem) dengan update file yang berpotensi bersamaan pada node yang berbeda. Penguncian tidak digunakan karena kegagalan node atau konektivitas jaringan mungkin menyebabkan tidak terbatas pemblokiran.
kepercayaan parsial antara peserta dan kerentanan terhadap serangan dari peserta mesin. Pemulihan dari kegagalan integritas yang disebabkan oleh serangan tersebut didasarkan pada Gagasan dilihat dari sistem file. Pandangan adalah representasi dari negara dibangun dari kayu dari update yang dibuat oleh satu set peserta. Peserta dapat dihapus dan tampilan menghitung ulang tanpa update mereka. Sehingga file bersama sistem dipandang sebagai hasil penggabungan semua pembaruan yang dilakukan oleh (Dinamis yang dipilih) menetapkan peserta.
Operasi Lanjutan selama partisi dalam jaringan, yang dapat mengakibatkan update bertentangan dengan file bersama. update bertentangan diselesaikan menggunakan metode terkait dengan yang digunakan dalam sistem file Coda (Bagian 18.4.3).
Ivy mengimplementasikan API di setiap node klien yang didasarkan pada protokol NFS server (Mirip dengan set operasi yang tercantum dalam Bagian 12.3, Gambar 12.9). node klien termasuk sebuah proses server Ivy yang menggunakan DHash untuk menyimpan dan catatan akses log di node seluruh area jaringan lokal atau wide berdasarkan kunci (GUID) yang dihitung sebagai hash dari isi rekaman (lihat Gambar 10.16). DHash mengimplementasikan pemrograman antarmuka seperti yang ditunjukkan pada Gambar 10.4 dan ulangan semua entri di beberapa node untuk ketahanan dan ketersediaan. Ivy penulis mencatat bahwa ini bisa pada prinsipnya digantikan oleh toko hash-ditujukan lain terdistribusi seperti Pastry, Tapestry atau CAN.

Sebuah file toko Ivy terdiri dari satu set update log, salah satu log per peserta. setiap Ivy peserta menambahkan hanya untuk log sendiri tetapi dapat membaca dari semua log yang terdiri dari berkas sistem. Update disimpan dalam terpisah log per-peserta sehingga mereka dapat digulung kembali kasus pelanggaran keamanan atau kegagalan konsistensi.

Log Ivy adalah linked list terbalik waktu-memerintahkan entri log. Setiap entri log adalah catatan timestamped dari permintaan klien untuk mengubah isi atau metadata dari file atau direktori. DHash menggunakan 160-bit SHA-1 hash dari rekor sebagai kunci untuk menempatkan dan mengambil catatan. Setiap peserta juga mempertahankan blok DHash bisa berubah (disebut log-head) yang menunjuk ke record log terbaru peserta. blok bisa berubah ditugaskan sepasang kunci publik kriptografi oleh pemiliknya. Isi blok yang ditandatangani dengan kunci pribadi dan karena itu dapat dikonfirmasi dengan yang sesuai kunci publik. Ivy menggunakan versi vektor (yaitu, cap waktu vektor; lihat Bagian 14.4) untuk memaksakan agar total pada entri log ketika membaca dari beberapa log.

DHash menyimpan catatan log menggunakan SHA-1 hash isinya sebagai kunci. Log catatan dirantai agar timestamp menggunakan kunci DHash sebagai link. Log-head memegang kunci untuk masuk log terbaru. Untuk menyimpan dan mengambil log-kepala, kunci publik Pasangan dihitung oleh pemilik log. Nilai kunci publik digunakan sebagai kunci DHash nya dan kunci pribadi digunakan oleh pemilik untuk menandatangani log-kepala. Setiap peserta yang memiliki kunci publik dapat mengambil log-kepala dan menggunakannya untuk mengakses semua catatan dalam log.

Dengan asumsi sistem file terdiri dari log tunggal untuk saat ini, kanonik Metode eksekusi untuk permintaan untuk membaca urutan byte dari sebuah file membutuhkan scan sekuensial log untuk menemukan catatan log yang berisi update untuk relevan porsi file. Log dari panjang tak terbatas, tapi scan berakhir ketika pertama record atau catatan yang ditemukan yang mencakup urutan diperlukan byte.

Algoritma kanonik untuk mengakses multi-user, sistem file multi-log melibatkan perbandingan cap waktu vektor dalam catatan log untuk menentukan urutan update (Sejak jam global tidak dapat diasumsikan).

Waktu yang dibutuhkan untuk melakukan proses ini untuk sebuah operasi yang sederhana seperti permintaan membaca berpotensi sangat panjang. Hal ini dikurangi menjadi durasi lebih ditoleransi dan predicable melalui penggunaan kombinasi cache lokal dan snapshot. Snapshots adalah representasi dari sistem file dihitung dan disimpan secara lokal oleh masing-masing peserta sebagai oleh-produk dari mereka menggunakan log. Mereka merupakan representasi lunak dari sistem file dalam arti bahwa mereka mungkin diremehkan jika peserta dikeluarkan dari sistem.

Update konsistensi dekat-to-terbuka; yaitu, update dilakukan pada sebuah file oleh Aplikasi tidak terlihat proses lain sampai file ditutup. Penggunaan closeto- sebuah Model konsistensi terbuka memungkinkan operasi menulis pada file yang akan disimpan di klien simpul sampai file ditutup; maka seluruh rangkaian operasi write ditulis sebagai tunggal log record dan catatan log-kepala baru dihasilkan dan ditulis (perluasan ke NFS protokol memungkinkan terjadinya operasi dekat dalam aplikasi yang akan diberitahukan kepada server Ivy).

Karena ada Ivy server terpisah di setiap node dan setiap otonom menyimpan nya update dalam log yang terpisah tanpa koordinasi dengan server lain, serialisasi update harus dilakukan pada saat log dibaca dalam rangka untuk membangun isi file. Vektor versi tertulis dalam catatan log dapat digunakan untuk memesan paling update, tapi metode otomatis atau manual, seperti yang dilakukan di Coda (lihat Bagian 18.4.3).

Integritas data dicapai dengan kombinasi mekanisme yang kita miliki telah disebutkan: log catatan abadi dan alamat mereka adalah hash aman dari mereka isi; log-kepala diverifikasi dengan memeriksa tanda tangan public-key isinya. Tapi model trust memungkinkan untuk kemungkinan bahwa peserta berbahaya dapat mendapatkan akses ke sistem file. Misalnya, mereka mungkin akan menghapus file yang mereka sendiri jahat. ketika ini adalah terdeteksi, peserta berbahaya dikeluarkan dari pandangan; log mereka tidak lagi digunakan untuk menghitung isi dari sistem file dan file yang mereka telah dihapus sekali lagi terlihat dalam tampilan baru.

Ivy penulis menggunakan Andrew patokan dimodifikasi [Howard et al. 1988] untuk membandingkan kinerja Ivy dengan server NFS standar di daerah lokal dan luas lingkungan jaringan. Mereka menganggap (a) Ivy menggunakan server DHash lokal dibandingkan dengan satu server dan NFS lokal (b) Ivy menggunakan server Dash terletak di beberapa terpencil situs internet dibandingkan dengan server remote NFS tunggal. Mereka juga menganggap karakteristik kinerja sebagai fungsi dari jumlah peserta dalam tampilan, jumlah peserta menulis secara bersamaan dan jumlah server DHash digunakan untuk menyimpan log.

Mereka menemukan bahwa Ivy eksekusi kali berada dalam faktor dua eksekusi NFS kali untuk sebagian besar tes di benchmark dan dalam faktor tiga untuk mereka semua. Eksekusi kali untuk penyebaran jaringan area luas melebihi orang-orang untuk lokal kasus dengan faktor 10 atau lebih, tetapi rasio yang serupa diperoleh untuk server NFS jauh. rincian lengkap tentang evaluasi kinerja dapat ditemukan di koran Ivy [Muthitacharoen et al. 2002]. Perlu dicatat, meskipun, bahwa NFS tidak dirancang untuk digunakan luas; Sistem Andrew berkas dan berbasis server-sistem yang lebih baru-baru ini dikembangkan lain seperti sebagai xfs [Anderson et al. 1996] menawarkan kinerja yang lebih tinggi dalam penyebaran luas dan mungkin telah membuat basis lebih baik untuk perbandingan. Kontribusi utama dari Ivy adalah di pendekatan baru terhadap manajemen keamanan dan integritas dalam lingkungan parsial kepercayaan - fitur yang tak terelakkan dari sistem terdistribusi sangat besar yang span banyak organisasi dan yurisdiksi.

10.7 Ringkasan

Peer-to-peer arsitektur pertama kali ditunjukkan untuk mendukung sangat besar berbagi data skala dengan penggunaan internet macam Napster dan keturunannya untuk berbagi musik digital. Faktanya yang banyak penggunaannya bertentangan dengan hukum hak cipta tidak mengurangi teknis mereka signifikansi, meskipun mereka juga memiliki kelemahan teknis yang membatasi mereka deployment untuk aplikasi di mana jaminan integritas data dan ketersediaan yang tidak penting.

Penelitian selanjutnya mengakibatkan pengembangan peer-to-peer middleware platform yang memberikan permintaan untuk objek data di mana pun mereka berada di Internet. Dalam pendekatan terstruktur, objek yang ditangani dengan menggunakan GUIDs, yang nama murni tidak mengandung informasi alamat IP. Benda ditempatkan pada node menurut beberapa fungsi pemetaan yang khusus untuk setiap sistem middleware. Pengiriman dilakukan oleh overlay routing dalam middleware yang mempertahankan tabel routing dan ke depan permintaan sepanjang rute yang ditentukan dengan menghitung jarak sesuai dengan pemetaan yang dipilih fungsi. Dalam pendekatan terstruktur, node membentuk diri menjadi jaringan ad hoc dan kemudian merambat pencarian melalui tetangga untuk menemukan sumber daya yang tepat. Beberapa strategi telah dikembangkan untuk meningkatkan kinerja fungsi pencarian ini dan meningkatkan skalabilitas keseluruhan sistem. Platform middleware menambahkan jaminan integritas berdasarkan pada penggunaan yang aman fungsi hash untuk menghasilkan panduan dan ketersediaan jaminan berdasarkan replikasi dari objek di beberapa node dan pada algoritma routing yang toleran. Platform telah dikerahkan di beberapa aplikasi percontohan skala besar, halus dan dievaluasi. Hasil evaluasi baru-baru ini menunjukkan bahwa teknologi siap penyebaran dalam aplikasi yang melibatkan sejumlah besar pengguna berbagi objek banyak data.

Manfaat peer-to-peer sistem meliputi:

kemampuan mereka untuk mengeksploitasi sumber daya yang tidak terpakai (penyimpanan, pengolahan) di host komputer;
skalabilitas untuk mendukung sejumlah besar klien dan host dengan sangat baik menyeimbangkan dari beban pada link jaringan dan sumber daya komputasi tuan rumah;
sifat self-mengorganisir platform middleware yang mengakibatkan dukungan biaya yang sebagian besar tergantung pada jumlah klien dan host dikerahkan.
Kelemahan dan subyek penelitian saat ini meliputi:

penggunaannya untuk penyimpanan data bisa berubah relatif mahal dibandingkan dengan yang terpercaya, layanan terpusat;
dasar menjanjikan bahwa mereka menyediakan untuk klien dan anonimitas tuan rumah belum mengakibatkan jaminan yang kuat anonimitas.