Kami terus mempertimbangkan contoh penggunaan replikasi rantai. Definisi dasar dan arsitektur diberikan di bagian pertama , saya sarankan Anda membiasakan diri dengan itu sebelum membaca bagian kedua.

Pada artikel ini, kita akan mempelajari sistem berikut:

• Hibari adalah repositori toleransi kesalahan yang didistribusikan yang ditulis dalam bahasa erlang.
• HyperDex - penyimpanan nilai kunci terdistribusi dengan dukungan untuk pencarian cepat dengan atribut sekunder dan pencarian jangkauan.
• ChainReaction - konsistensi kausal + dan replikasi-geo.
• Membangun sistem terdistribusi tanpa menggunakan proses pemantauan / konfigurasi ulang eksternal tambahan.

5. Hibari

Hibari adalah repositori KV toleran-kesalahan yang didistribusikan yang ditulis dalam bahasa erlang. Menggunakan replikasi rantai (pendekatan dasar), yaitu mencapai konsistensi yang ketat. Dalam pengujian, Hibari menunjukkan kinerja tinggi - beberapa ribu pembaruan per detik dicapai pada server dua unit (permintaan 1Kb)

5.1 Arsitektur

Hashing yang konsisten digunakan untuk menempatkan data. Dasar penyimpanan adalah blok fisik dan logis. Bata fisik adalah server dengan Linux, mungkin instance EC2 dan, secara umum, VM secara keseluruhan. Bata logis adalah contoh penyimpanan yang dengannya proses utama cluster bekerja, dan setiap blok adalah simpul dalam satu rantai. Dalam contoh di bawah ini, cluster dikonfigurasikan dengan 2 blok logis pada setiap blok fisik dan dengan panjang rantai 2. Perhatikan bahwa node rantai "dioleskan" di atas blok fisik untuk meningkatkan keandalan.

Proses master (lihat definisi di bagian pertama) disebut server Admin .

Data disimpan dalam "tabel", yang hanya dibagi menjadi ruang nama, setiap tabel disimpan dalam setidaknya satu rantai, dan setiap rantai menyimpan data hanya dalam satu tabel.

Klien Hibari menerima pembaruan dari server Admin dengan daftar semua kepala dan ujung semua rantai (dan semua tabel). Dengan demikian, pelanggan segera tahu simpul logis mana yang akan dikirimi permintaan.

5.2 Hashing

Hibari menggunakan pasangan $$$\ {T, K \}$ untuk menentukan nama rantai yang menyimpan kunci $$$K$ di atas meja $$$T$ : kunci $$$K$ dipetakan ke interval $$$[0,1, 1,0)$ (menggunakan MD5), yang dibagi menjadi beberapa bagian di mana satu rantai bertanggung jawab. Bagian dapat memiliki lebar yang berbeda, tergantung pada "berat" rantai, misalnya:



Jadi, jika beberapa blok fisik sangat kuat, maka rantai yang terletak di atasnya dapat diberikan bagian yang lebih luas (maka lebih banyak kunci akan jatuh pada mereka).

6. HyperDex

Tujuan dari proyek ini adalah untuk membangun penyimpanan nilai kunci terdistribusi, yang, tidak seperti solusi populer lainnya (BigTable, Cassandra, Dynamo), akan mendukung pencarian cepat untuk atribut sekunder dan dapat dengan cepat melakukan pencarian jangkauan. Misalnya, dalam sistem yang sebelumnya dianggap, untuk mencari semua nilai dalam rentang tertentu Anda harus melalui semua server, yang, jelas, tidak dapat diterima. HyperDex memecahkan masalah ini menggunakan Hyperspace Hashing .

6.1 Arsitektur

Ide hashing hyperspace adalah membangun $$$n$ ruang -dimensi di mana setiap atribut sesuai dengan satu sumbu koordinat. Misalnya, untuk objek (nama depan, nama belakang, nomor telepon), ruang mungkin terlihat seperti ini:



Hyperplane abu-abu melewati semua kunci, di mana nama belakang = Smith, kuning - di semua kunci, di mana nama depan = John. Perpotongan pesawat-pesawat ini membentuk respons terhadap nomor telepon permintaan pencarian orang-orang dengan nama John dan nama keluarga Smith. Jadi permintaan untuk $$$k$ atribut kembali $$$(n-k)$ subruang -dimensi.

Ruang pencarian dibagi menjadi $$$n$ Wilayah terpisah -dimensi, dan masing-masing wilayah ditugaskan ke satu server. Objek dengan koordinat dari suatu daerah disimpan di server wilayah ini. Jadi, sebuah hash dibangun antara objek dan server.

Permintaan pencarian (berdasarkan rentang) akan menentukan wilayah yang termasuk dalam hyperplane yang dihasilkan dan, dengan demikian, mengurangi jumlah server yang disurvei menjadi minimum.

Ada satu masalah dengan pendekatan ini - jumlah server yang diperlukan tumbuh secara eksponensial dari jumlah atribut, yaitu jika atribut $$$k$ maka kamu perlu $$$O (2 ^ k)$ server. Untuk mengatasi masalah ini, HyperDex menerapkan partisi hyperspace ke dalam subruang (dengan dimensi yang lebih rendah), masing-masing dengan subset atribut:

6.2 Replikasi

Untuk memastikan konsistensi yang ketat, penulis mengembangkan pendekatan khusus berdasarkan rantai replikasi - rantai nilai tergantung , di mana setiap node berikutnya ditentukan dengan hashing atribut yang sesuai. Misalnya kuncinya $$$("John", "Smith")$ pertama akan di-hash ke dalam ruang kunci (kita mendapatkan rantai kepala, juga disebut point leader ), kemudian hash dari$$ $ inline $ "John" $ inline $ ke koordinat pada sumbu yang sesuai dan sebagainya. (Lihat gambar di bawah untuk contoh pembaruan. $$$u_1$ )

Semua pembaruan melewati pemimpin titik, yang memesan permintaan (linearitas).



Jika pembaruan mengarah ke perubahan di kawasan, maka pertama versi baru ditulis segera setelah yang lama (lihat pembaruan $$$u_2$ ), dan setelah menerima ACK dari ekor, tautan ke versi lama dari server sebelumnya akan diubah. Untuk permintaan bersamaan (mis. $$$u_2$ dan $$$u_3$ ) tidak melanggar pemimpin titik konsistensi menambahkan versi dan informasi meta lainnya ke server, jika diterima $$$u_3$ sebelumnya $$$u_2$ dapat menentukan bahwa pesanan rusak dan Anda harus menunggu $$$u_2$ .

7. ChainReaction

Model sebab akibat + konvergensi digunakan, yang menambahkan kondisi untuk konvergensi bebas konflik ke konvergensi kausal (kausal). Untuk memenuhi konvergensi kausal, metadata ditambahkan ke setiap permintaan, yang menunjukkan versi semua kunci dependen kausal. ChainReaction memungkinkan Anda untuk melakukan replikasi-geo di beberapa pusat data dan merupakan pengembangan lebih lanjut dari gagasan CRAQ.

7.1 Arsitektur

Arsitektur dari FAWN digunakan dengan perubahan kecil - setiap DC terdiri dari server data - backend (penyimpanan data, replikasi, bentuk cincin DHT) dan proxy klien - frontends (mengirim permintaan ke node tertentu). Setiap kunci direplikasi ke simpul R berturut-turut, membentuk rantai. Permintaan baca diproses dengan ekor, dan ditulis oleh kepala.

7.2 Satu pusat data

Kami mencatat satu properti penting yang timbul dari replikasi rantai - jika simpul $$$k$ kausal-konsisten dengan beberapa operasi klien, maka semua node sebelumnya - juga. Jadi kalau operasi $$$Op$ terakhir kali terlihat oleh kami di situs $$$j$ , maka semua tergantung kausal (dari $$$Op$ ) operasi baca hanya dapat dilakukan pada node dari kepala ke $$$j$ . Begitu $$$Op$ akan dieksekusi pada ekor - tidak akan ada batasan baca. Sebutkan operasi penulisan yang dilakukan dengan ekor di DC $$$d$ seperti DC-Write-Stable (d) .

Setiap klien menyimpan daftar (metadata) dari semua kunci yang diminta oleh klien dalam format (kunci, versi, chainIndex), di mana chainIndex adalah posisi simpul dalam rantai yang menjawab permintaan terakhir untuk kunci kunci. Metadata disimpan hanya untuk kunci yang klien tidak tahu apakah itu DC-Write-Stable (d) atau tidak .

7.2.1 Operasi tulis

Perhatikan bahwa begitu operasi menjadi DC-Write-Stable (d), maka tidak ada permintaan baca yang dapat membaca versi sebelumnya.

Untuk setiap permintaan tulis, daftar semua kunci di mana operasi baca dilakukan sebelum operasi penulisan terakhir ditambahkan. Segera setelah proksi klien menerima permintaan, ia melakukan pemblokiran membaca pada ekor semua kunci dari metadata (kami sedang menunggu konfirmasi kehadiran versi yang sama atau lebih baru, dengan kata lain, kami memenuhi kondisi konsistensi sebab akibat). Segera setelah konfirmasi diterima, permintaan tulis dikirim ke kepala rantai terkait.



Setelah nilai baru disimpan $$$k$ simpul rantai, pemberitahuan dikirim ke klien (dengan indeks simpul terakhir). Klien memperbarui chainIndex dan menghapus metadata dari kunci yang dikirim, sebagai diketahui bahwa mereka adalah DC-Write-Stable (d). Secara paralel, rekaman terus berlanjut - propagasi malas . Jadi, prioritas diberikan untuk menulis operasi pada yang pertama $$$k$ node. Segera setelah tail menyimpan versi baru kunci, pemberitahuan dikirim ke klien dan dikirim ke semua node rantai sehingga mereka menandai kunci sebagai stabil.

7.2.2 Baca operasi

Proksi klien mengirimkan permintaan baca ke $$$index: = rand (1, chainIndex)$ simpul di sirkuit, saat mendistribusikan beban. Sebagai tanggapan, node mengirimkan nilai dan versi dari nilai ini. Respons dikirim ke klien, sementara:

• Jika versinya stabil, maka chainIndex baru sama dengan ukuran rantai.
• Jika versinya lebih baru, maka chainIndex = indeks baru.
• Kalau tidak, chainIndex tidak berubah.

7.2.3 Kegagalan simpul

Ini hampir sepenuhnya identik dengan pendekatan dasar, dengan beberapa perbedaan dalam kenyataan bahwa dalam beberapa kasus chainIndex pada klien menjadi tidak valid - ini mudah ditentukan ketika menjalankan permintaan (tidak ada kunci dengan versi ini) dan permintaan diarahkan ke kepala rantai untuk mencari node dengan versi yang diinginkan.

7.3 Beberapa ( $$$N$ ) pusat data (replikasi-geo)

Kami mengambil sebagai algoritma dasar dari arsitektur server tunggal dan mengadaptasinya seminimal mungkin. Sebagai permulaan, dalam metadata, alih-alih hanya versi dan nilai chainIndex, kita membutuhkan vektor berversi dari dimensi N.

Kami mendefinisikan Global-Write-Stable dengan cara yang mirip dengan DC-Write-Stable (d) - operasi penulisan dianggap Global-Write-Stable jika dilakukan dengan berurutan di semua DC.

Komponen baru muncul di setiap DC - remote_proxy , tugasnya adalah menerima / mengirim pembaruan dari DC lain.

7.3.1 Melakukan operasi penulisan (di server $$$i$ )

Permulaannya mirip dengan arsitektur server tunggal - kami melakukan pemblokiran membaca, menulis ke yang pertama $$$k$ simpul rantai. Pada titik ini, proksi klien mengirimkan kepada klien vektor chainIndex baru, di mana nol ada di mana-mana, kecuali untuk posisinya $$$i$ - ada artinya $$$k$ . Selanjutnya - seperti biasa. Operasi tambahan di akhir - pembaruan dikirim ke remote_proxy, yang mengakumulasikan beberapa permintaan dan kemudian mengirimkan semuanya.

Dua masalah muncul di sini:

• Bagaimana cara memastikan ketergantungan antara pembaruan yang berbeda yang datang dari DC yang berbeda?
  
  Setiap remote_proxy menyimpan vektor versi lokal $$$rvp$ dimensi $$$N$ , yang menyimpan jumlah pembaruan yang dikirim dan diterima, dan mengirimkannya di setiap pembaruan. Jadi, ketika menerima pembaruan dari DC lain, remote_proxy memeriksa penghitung, dan jika penghitung lokal kurang, operasi diblokir sampai pembaruan yang sesuai diterima.
• Bagaimana cara menyediakan dependensi untuk operasi ini di DC lain?
  
  Ini dicapai menggunakan filter Bloom. Saat melakukan operasi tulis / baca dari proksi klien, selain metadata, filter bloom juga dikirimkan untuk setiap kunci (disebut filter respons). Filter ini disimpan dalam daftar AccessedObjects , dan ketika meminta operasi tulis / baca, metadata juga mengirimkan ATAU filter kunci yang terkirim (disebut filter ketergantungan). Demikian pula, setelah operasi penulisan, filter yang sesuai dihapus. Saat mengirim operasi tulis ke DC lain, filter ketergantungan dan filter respons untuk permintaan ini juga dikirimkan.
  
  Lebih jauh, DC jarak jauh, setelah menerima semua informasi ini, memeriksa bahwa jika bit-bit set dari filter respon bertepatan dengan bit-bit set dari beberapa filter permintaan, maka operasi-operasi semacam itu berpotensi bergantung pada kasual. Berpotensi - karena filter mekar.

7.3.2 Baca operasi

Demikian pula dengan arsitektur server tunggal, disesuaikan untuk menggunakan vektor chainIndex alih-alih skalar dan kemungkinan kunci yang hilang di DC (karena pembaruan tidak sinkron), maka tunggu atau arahkan permintaan ke DC lain.

7.3.3 Resolusi Konflik

Berkat metadata, operasi yang bergantung pada sebab-akibat selalu dilakukan dalam urutan yang benar (kadang-kadang Anda harus memblokir proses untuk ini). Tetapi perubahan kompetitif di DC yang berbeda dapat menyebabkan konflik. Untuk mengatasi situasi seperti itu, Last Write Wins digunakan, untuk mana pasangan hadir dalam setiap operasi pembaruan $$$(jam, s)$ dimana $$$c$ - jam pada proxy, dan $$$s$ - id DC.

7.3.4 Menangani kegagalan simpul

Mirip dengan arsitektur server tunggal.

8. Memanfaatkan Sharding dalam Desain Protokol Replikasi Skalabel

Tujuan dari penelitian ini adalah untuk membangun sistem terdistribusi dengan pecahan dan dengan replikasi tanpa menggunakan proses master eksternal untuk mengkonfigurasi ulang / memantau cluster.

Dalam pendekatan utama saat ini, penulis melihat kelemahan berikut:

Replikasi:

• Utama / Cadangan - mengarah ke perbedaan di negara bagian jika Pratama keliru diidentifikasi sebagai gagal.
• Persimpangan Kuorum - dapat menyebabkan ketidaksesuaian status selama konfigurasi ulang kluster.

Konsistensi yang ketat:

• Protokol bergantung pada algoritma pemungutan suara mayoritas (mis. Paxos) jika diperlukan $$$2 * N + 1$ jatuhkan simpul $$$N$ node.

Deteksi kegagalan simpul:

• P / B dan CR menyiratkan adanya deteksi ideal node gagal dengan model gagal-berhenti, yang dalam praktiknya tidak mungkin tercapai dan Anda harus memilih interval pemindaian yang sesuai.
• ZooKeeper mengalami masalah yang sama - dengan sejumlah besar klien, diperlukan sejumlah besar waktu (> 1 detik) bagi mereka untuk memperbarui konfigurasi.

Pendekatan yang diajukan oleh penulis, yang disebut replikasi elastis , tidak memiliki kekurangan ini, dan memiliki karakteristik sebagai berikut:

• Konsistensi yang ketat.
• Untuk menahan jatuh $$$N$ node harus memiliki $$$N + 1$ simpul
• Konfigurasi ulang tanpa kehilangan konsistensi.
• Tidak perlu protokol konsensus berdasarkan suara terbanyak.

Piring ringkasan:

8.1 Organisasi replika

Setiap pecahan menentukan urutan konfigurasi $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ misalnya, konfigurasi baru tidak mengandung semacam replika jatuh $$$\ mathcal {C} = \ mathcal {C}: :( Replika \ setminus R_j)$

Setiap elemen dari urutan konfigurasi terdiri dari:

• replika - satu set replika.
• orderer - id dari replika dengan peran khusus (lihat di bawah).

Setiap pecahan diwakili oleh satu set replika (dengan konstruksi - $$$N$ ), yaitu kami tidak membagi peran "beling" dan "replika".

Setiap replika menyimpan data berikut:

• konfigurasi konfigurasi milik replika ini.
• orderer - yang merupakan replika dari konfigurasi ini.
• mode - mode replika, satu dari tiga: $$$PENDING$ (semua replika dari $$$C_1$ ), $$$AKTIF$ (semua replika dari $$$C_1$ ), $$$IMMUTABLE$ .
• history - urutan operasi pada data replika yang sebenarnya $$$op_1 :: op_2 :: \ dots$ (atau hanya suatu syarat).
• stable - panjang maksimum awalan riwayat yang diperbaiki oleh replika ini. Jelas, $$$0 <= stable <= panjang (histori)$ .

Tujuan utama pemesan replika adalah mengirim permintaan ke seluruh replika dan mempertahankan awalan sejarah terbesar:

8.2 Organisasi pecahan

Pecahan digabungkan menjadi cincin yang disebut pita elastis . Setiap pecahan hanya memiliki satu cincin. Cikal bakal dari setiap pecahan $$$X$ melakukan peran khusus - dia adalah sequencer untuknya. Tugas sequencer adalah untuk memberikan penggantinya konfigurasi baru jika terjadi kegagalan replika.


Dibutuhkan dua kondisi:

• Setiap band elastis memiliki setidaknya satu beling dan satu replika yang berfungsi.
• Setiap band elastis memiliki setidaknya satu beling, di mana semua replika bekerja.

Kondisi kedua tampaknya terlalu ketat, tetapi ini setara dengan kondisi "tradisional" yang proses masternya tidak pernah jatuh.

8.3 Menggunakan replikasi rantai

Seperti yang mungkin sudah Anda duga, replika disusun sebagai rantai (pendekatan dasar) - pemesan akan menjadi kepala, dengan sedikit perbedaan:

• Dalam kasus kegagalan CR, node dilempar keluar dari rantai (dan diganti dengan yang baru), di ER - rantai baru dibuat.
• Permintaan baca di CR diproses dengan ekor, di ER, mereka melewati seluruh rantai dengan cara yang sama seperti permintaan menulis.

8.5 Konfigurasi ulang jika terjadi kegagalan

• Replika dipantau oleh replika beling Anda dan replika beling sequencer.
• Segera setelah kegagalan terdeteksi, replika mengirim perintah tentang ini.
• Sequencer mengirimkan konfigurasi baru (tanpa replika yang gagal).
• Replika baru dibuat yang mensinkronkan keadaannya dengan pita elastis.
• Setelah itu, sequencer mengirimkan konfigurasi baru dengan replika yang ditambahkan.

Referensi

• Hibari
• hyperdex.orgerdex.org
• HyperDex: Toko Nilai-Kunci Terdistribusi dan Dapat Dicari
• Reaksi berantai
• Memanfaatkan Sharding dalam Desain Protokol Replikasi Skalabel