Dalam artikel ini, kami akan mempertimbangkan arsitektur penyimpanan KV sederhana dan efisien menggunakan replikasi rantai, yang secara aktif diselidiki dan berhasil digunakan dalam berbagai sistem.

Ini adalah bagian pertama dari artikel replikasi rantai. Bagian kedua ada di sini . Pada awalnya akan ada sedikit teori, kemudian beberapa contoh penggunaan dengan berbagai modifikasi.

Tujuannya adalah pernyataan masalah dan perbandingan dengan protokol utama / cadangan.
Replikasi rantai adalah pendekatan dasar.
Replikasi berantai - permintaan terdistribusi.
FAWN: Array Cepat untuk Node Wimpy.

1. Pendahuluan

1.1 Tujuan

Misalkan kita ingin merancang toko kunci-nilai sederhana. Repositori akan memiliki antarmuka yang sangat minim:

tulis (kunci, objek): menyimpan / memperbarui nilai nilai dengan kunci tombol.
baca (kunci): mengembalikan nilai yang disimpan dengan kunci tombol.

Kita juga tahu bahwa ukuran data relatif kecil (semuanya cocok pada satu server, tidak ada kebutuhan untuk sharding), tetapi mungkin ada banyak permintaan tulis / baca.

Tujuan kami adalah untuk menahan sejumlah besar permintaan ( throughput tinggi, HT ), memiliki ketersediaan tinggi ( HA ) dan konsistensi yang ketat ( SC ).

Dalam banyak sistem, SC dikorbankan untuk HA + HT, karena memenuhi ketiga sifat adalah tugas yang tidak sepele. Amazon Dynamo telah menjadi lompatan besar ke depan dan melahirkan sejumlah basis data gaya Dynamo seperti Cassandra, Riak, Voldemort, dll.

1.2 Utama / Cadangan

Salah satu pendekatan yang paling umum dan sederhana untuk membangun sistem penyimpanan seperti itu adalah dengan menggunakan replikasi primer / cadangan.
Kami memiliki 1 server utama, beberapa server cadangan, operasi tulis / baca hanya melalui server utama.

Di sini gambar menunjukkan salah satu protokol interaksi yang mungkin (primer menunggu ack dari semua cadangan sebelum mengirim ack ke klien), ada opsi lain (tidak saling eksklusif), misalnya:

Pratama secara ketat mengorganisasi permintaan tulis.
Utama mengirimkan ack segera setelah salah satu cadangan merespons dengan ack.
Kuorum yang ceroboh dan mengisyaratkan handoff.
Dll

Proses terpisah juga diperlukan untuk memantau keadaan cluster (mendistribusikan konfigurasi kepada para peserta) dan, ketika server host crash, membuat (memulai) pemilihan yang baru, dan juga menentukan apa yang harus dilakukan jika otak terpecah. Sekali lagi, tergantung pada persyaratan, bagian dari logika ini dapat dieksekusi sebagai bagian dari algoritma replikasi, bagian sebagai aplikasi pihak ketiga (misalnya, penjaga kebun binatang untuk menyimpan konfigurasi), dll.

Jelas, cepat atau lambat, kinerja replikasi primer / cadangan akan dibatasi oleh dua hambatan:

Kinerja server utama.
Jumlah server cadangan.

Semakin banyak persyaratan keandalan / konsistensi yang disajikan ke sebuah cluster, semakin cepat momen ini akan datang.

Adakah cara lain untuk mencapai tujuan kita?

1.3 Replikasi berantai

Secara umum, replikasi rantai terdiri dari urutan (rantai) server, dengan peran khusus KEPALA (server yang berkomunikasi dengan klien) dan TAIL (akhir rantai, jaminan SC). Rantai setidaknya memiliki properti berikut:

Tahan turun ke server n - 1.
Kecepatan tulis tidak jauh berbeda dari SC Primer / Cadangan.
Konfigurasi ulang cluster dalam hal terjadi KEPALA terjadi jauh lebih cepat daripada Primer, seluruh server relatif atau lebih cepat daripada di Primer / Cadangan.

Titik kecil tapi signifikan - diperlukan koneksi FIFO antar server.

Mari kita teliti lebih lanjut berbagai metode membangun replikasi rantai.

2. Pendekatan dasar

2.1 Algoritma operasional

Klien mengirim permintaan tulis ke simpul kepala, dan membaca permintaan mengirim ke simpul ekor. Jawabannya selalu datang dari ekor. Head, setelah menerima permintaan perubahan, menghitung perubahan status yang diperlukan, menerapkannya, dan mengirimkannya ke node berikutnya. Segera setelah ekor memprosesnya, respons ACK dikirim kembali ke rantai. Jelas, jika permintaan baca mengembalikan beberapa nilai x, maka itu disimpan di semua node.

2.2 Protokol Replikasi

Kami memberi nomor server dari kepala ke ekor, kemudian pada setiap node

i

$i$ kami juga akan menyimpan:

$Pending_i$ - daftar permintaan yang diterima oleh simpul yang belum diproses oleh tail.
$Sent_i$ - daftar permintaan yang dikirim oleh server ke penggantinya yang belum diproses secara berurutan.
$History_i (key)$ - riwayat perubahan nilai kunci (Anda dapat menyimpan baik riwayat dan hanya nilai total). Perhatikan bahwa:
$H i s t o r y_{j} (k e y) s u b s e t e q H i s t o r y_{i} (k e y), f o r a l l j > i$
$History_j (key) \ subseteq History_i (key), \ forall j> i$
Dan juga:
$S e n t_{i} s u b s e t e q P e n d i n g_{i} H i s t o r y_{i} (k e y) = H i s t o r y_{i + 1} (k e y) c u p S e n t_{i}$
$Sent_i \ subseteq Pending_i \\ History_i (key) = History_ {i + 1} (key) \ cup Sent_i$

2.3 Server Failover

Seperti disebutkan dalam pendahuluan, kita membutuhkan semacam proses master yang:

Mengidentifikasi server yang gagal.
Memberitahu pendahulunya dan penerus perubahan di sirkuit.
Jika server tail atau head, itu memberi tahu klien tentang perubahan mereka.

Kami percaya bahwa proses master stabil dan tidak pernah crash. Pilihan proses semacam itu berada di luar cakupan artikel ini.

Asumsi kedua yang sangat penting adalah kita menganggap server gagal-berhenti:

Dalam hal terjadi kegagalan (internal), server berhenti bekerja, dan tidak memberikan hasil yang salah.
Kegagalan server selalu ditentukan oleh proses master.

Mari kita lihat bagaimana server baru ditambahkan:
Secara teoritis, server baru dapat ditambahkan ke sembarang tempat dalam rantai, menambah ekor tampaknya yang paling sulit - Anda hanya perlu menyalin status ekor saat ini ke server baru, beri tahu wizard tentang perubahan rantai dan beri tahu ekor lama bahwa permintaan sekarang perlu dikirim lebih lanjut.

Akhirnya, pertimbangkan tiga kemungkinan skenario kegagalan:

2.3.1 Kepala jatuh
Hapus saja server dari rantai dan tetapkan kepala baru berikutnya. Hanya hilangnya permintaan itu dari

P e n d i n g_{h e a d}

$Pending_ {head}$ yang tidak dikirim lebih lanjut -

P e n d i n g_{h e a d} s e t m i n u s S e n t_{h e a d}

$Pending_ {head} \ setminus Sent_ {head}$

2.3.2 Jatuh ekor
Kami menghapus server dari rantai dan menetapkan yang sebelumnya ke ekor yang baru, sebelum itu

S e n t_{t a i l - 1}

$Sent_ {tail - 1}$ dibersihkan (semua operasi ini ditandai sebagai ekor yang diproses), masing-masing

P e n d i n g_{t a i l - 1}

$Pending_ {tail - 1}$ berkurang.

2.3.3 Jatuh simpul menengah

k

$k$
Wizard menginformasikan node

k - 1

$k-1$ dan

k + 1

$k + 1$ tentang pemesanan ulang dalam suatu rantai.
Kemungkinan kerugian

S e n t_{k - 1}

$Sent_ {k-1}$ jika simpul

k

$k$ Saya tidak berhasil mengirim mereka lebih jauh ke penerus saya, karena itu, setelah menghapus simpul

k

$k$ dari rantai hal pertama dikirim lagi

S e n t_{k - 1}

$Sent_ {k - 1}$ dan hanya setelah simpul itu

k - 1

$k - 1$ terus memproses permintaan baru.

2.4 Perbandingan dengan cadangan / protokol utama

Dalam replikasi berantai, hanya satu server (ekor) yang terlibat dalam pelaksanaan permintaan baca, dan itu memberikan jawaban segera, sementara di P / B primer itu bisa menunggu konfirmasi penyelesaian permintaan tulis.
Dalam kedua pendekatan, permintaan tulis dijalankan pada semua server, P / B melakukannya lebih cepat karena eksekusi paralel.

Keterlambatan replikasi rantai kegagalan:

Head: eksekusi permintaan baca tidak terganggu, permintaan tulis ditunda oleh 2 pesan - dari master ke semua server tentang head baru dan dari master ke semua klien tentang head baru.
Server perantara: permintaan baca tidak terputus. Permintaan rekaman mungkin tertunda saat runtime $Sent_i$ Tidak ada kerugian pembaruan.
Buntut: Penundaan permintaan baca dan tulis untuk dua pesan - pemberitahuan $tail - 1$ tentang ekor baru dan memberi tahu pelanggan tentang ekor baru.

Kegagalan P / B Penundaan:

Utama: 5 penundaan pesan untuk memilih status primer dan sinkronisasi baru.
Cadangkan: tidak ada penundaan baca jika tidak ada permintaan tulis. Saat permintaan rekaman muncul, penundaan 1 pesan dimungkinkan.

Seperti yang Anda lihat, kegagalan ekor terburuk untuk replikasi rantai lebih cepat daripada yang terburuk untuk P / B (Primer).

Para penulis pendekatan ini melakukan tes beban, yang menunjukkan kinerja yang sebanding dengan protokol P / B.

3. Kueri Terdistribusi (Replikasi Rantai dengan Kueri yang Dibagikan - CRAQ)

Pendekatan dasar memiliki kelemahan yang jelas - ekor, yang menangani semua permintaan baca. Ini dapat menyebabkan dua masalah:

Ekor menjadi hotspot, mis. server yang menangani permintaan jauh lebih banyak daripada node lainnya.
Saat menempatkan rantai di beberapa pusat data, tail bisa sangat jauh, yang akan memperlambat permintaan penulisan.

Gagasan CRAQ cukup sederhana - biarkan permintaan baca datang ke semua server kecuali tail, dan untuk memastikan konsistensi, kami akan menyimpan vektor versi objek untuk permintaan tulis, dan jika terjadi ambiguitas, node akan membuat permintaan untuk mengikuti untuk mendapatkan versi tetap terbaru.

3.1 CRAQ

Kami meresmikan arsitektur CRAQ:
Setiap node, kecuali tail, memproses permintaan baca dan mengembalikan respons, dan head mengembalikan respons dari permintaan tulis (bandingkan dengan pendekatan dasar).

Pada setiap simpul non-ekor, beberapa versi dari objek yang sama dapat disimpan, dan versi tersebut membentuk urutan yang meningkat secara monoton. Untuk setiap versi, atribut tambahan ditambahkan "bersih" atau "kotor". Awalnya, semua versi bersih.

Segera setelah node menerima permintaan tulis, node menambahkan versi yang diterima ke daftar versi, dan kemudian:

Jika simpul ekor, maka itu menandai versi sebagai bersih, pada saat ini versi dianggap tetap, dan mengirimkan konfirmasi kembali ke rantai.
Kalau tidak, itu menandai versi sebagai kotor dan mengirimkan permintaan lebih jauh ke bawah rantai.

Segera setelah simpul menerima konfirmasi dari penerus, itu menandai versi sebagai bersih dan menghapus semua versi sebelumnya.

Segera setelah simpul menerima permintaan baca:

Jika versi terakhir dari objek yang dikenal ke node bersih, maka ia mengembalikannya.
Jika tidak, ia membuat permintaan untuk mengikuti untuk mendapatkan versi terbaru dari objek, yang ia kembalikan ke klien. (Dengan konstruksi, versi seperti itu akan selalu ada di node).

Untuk aplikasi dengan dominasi permintaan baca, kinerja CRAQ tumbuh secara linear dengan pertumbuhan node , dalam kasus dominasi permintaan tulis, kinerja tidak akan lebih buruk daripada pendekatan dasar.

CRAQ dapat ditemukan di satu atau di beberapa pusat data. Ini memungkinkan pelanggan untuk memilih simpul terdekat untuk meningkatkan kecepatan permintaan baca.

3.2 Konsistensi dalam CRAQ

CRAQ memberikan konsistensi yang kuat, kecuali dalam satu kasus: ketika node menerima versi commit terbaru dari tail, tail dapat mengkomit versi baru sebelum node merespon klien. Dalam situasi ini, CRAQ memberikan bacaan yang monoton (permintaan membaca berurutan tidak akan menjadi bagian dari masa lalu, tetapi dapat mengembalikan data lama) di seluruh rantai .

Konsistensi yang lemah juga dimungkinkan:

Konsistensi Akhirnya: node tidak akan meminta versi terbaru dari tail. Ini akan mengganggu pembacaan monoton pada seluruh rantai, tetapi tetap membaca monoton pada node yang sama . Selain itu, dapat menahan toleransi partisi jaringan .
Bounded Konsistensi Akhir: kembalikan versi kotor hanya sampai titik tertentu. Misalnya, perbedaan antara versi kotor dan bersih tidak boleh melebihi revisi N. Atau batas waktu.

3.3 Server failover

Mirip dengan pendekatan dasar.

3.4 Opsional

CRAQ memiliki satu fitur menarik - Anda dapat menggunakan multicast selama operasi perekaman. Misalkan head mengirimkan perubahan dengan multicast dan mengirimkan ke rantai hanya beberapa pengidentifikasi untuk acara ini. Jika pembaruan itu sendiri belum tiba di node, maka itu bisa menunggu dan menerimanya dari node berikutnya ketika Tail mengirimkan pesan konfirmasi perubahan. Demikian pula, ekor dapat mengirim konfirmasi fiksasi dengan multicast.

4. FAWN: Array Cepat untuk Node Wimpy

Sebuah studi yang sangat menarik, tidak terkait langsung dengan topik artikel ini, tetapi berfungsi sebagai contoh penggunaan replikasi rantai.

Penyimpanan nilai kunci berkinerja tinggi (Dynamo, memcached, Voldemort) memiliki karakteristik yang sama - mereka memerlukan I / O, minimum komputasi, akses paralel paralel ke kunci acak dalam jumlah besar, dan nilai kunci kecil hingga 1Kb.

Server dengan HDD tidak cocok untuk cluster seperti itu karena operasi pencarian yang lama (waktu akses acak), dan server dengan sejumlah besar DRAM mengkonsumsi daya yang sangat besar - DRAM 2GB setara dengan 1 TB HDD.

Pembangunan cluster (bandwidth) yang efektif dengan konsumsi daya minimal adalah tujuan dari studi awal. 50% dari biaya server selama tiga tahun adalah biaya listrik, dan mode hemat energi modern tidak seefektif yang diiklankan - dalam pengujian pada beban 20%, konsumsi CPU tetap pada 50%, ditambah komponen server lainnya tidak memiliki mode hemat energi sama sekali ( DRAM, misalnya, sudah berfungsi minimal). Penting untuk dicatat bahwa dalam klaster seperti itu kesenjangan antara CPU dan I / O melebar - CPU yang kuat dipaksa untuk menunggu operasi I / O selesai.

4.1 Arsitektur

Cluster FAWN dibangun pada server lama dengan harga $ 250 (harga 2009), dengan CPU 500MHz terintegrasi, RAM 512Mb, SSD 32Gb. Jika Anda terbiasa dengan arsitektur Amazon Dynamo atau hashing yang konsisten, maka Anda akan terbiasa dengan arsitektur FAWN:

Setiap server fisik berisi beberapa node virtual, masing-masing memiliki VID sendiri.
VID membentuk cincin, masing-masing VID bertanggung jawab untuk rentang "di belakang itu sendiri" (misalnya, A1 bertanggung jawab atas kunci dalam rentang R1).
Untuk meningkatkan keandalan, data direplikasi ke R dari simpul-simpul berikut searah jarum jam. (misalnya, dengan R = 2, kunci pada A1 direplikasi ke B1 dan C1), jadi kami mendapatkan replikasi rantai (pendekatan dasar).
Baca permintaan pergi ke rantai ekor, mis. Membaca kunci dari A1 akan menuju ke C1.
Tulis permintaan pergi ke rantai kepala dan pergi ke akhir.

Peta server disimpan pada sekelompok server frontend, yang masing-masing bertanggung jawab atas daftar VID spesifiknya, dan dapat mengarahkan permintaan ke server frontend lain.

4.2 Hasil Tes

Dalam pengujian beban, FAWN mencapai QPS (Permintaan per detik) dari 90% QPS pada flash drive baca acak.

Tabel berikut membandingkan Total Biaya Kepemilikan (TCO) dari berbagai konfigurasi, di mana dasar untuk Tradisional adalah server $ 1000 dengan konsumsi 200W (harga 2009):

Jadi, jika:

Data besar, beberapa pertanyaan: FAWN + 2Tb 7200 RPM
Sejumlah kecil data, banyak permintaan: FAWN + 2GB DRAM
Nilai rata-rata: FAWN + 32GB SSD

Replikasi berantai: membangun repositori KV yang efektif (bagian 1/2)