Seperti inilah redundansinya
Kode redundansi* banyak digunakan dalam sistem komputer untuk meningkatkan keandalan penyimpanan data. Di Yandex, mereka digunakan di banyak proyek. Misalnya, menggunakan kode redundansi alih-alih replikasi di penyimpanan objek internal kami menghemat jutaan tanpa mengorbankan keandalan. Namun meskipun digunakan secara luas, deskripsi yang jelas tentang cara kerja kode redundansi sangat jarang. Mereka yang ingin memahami dihadapkan pada hal-hal berikut (dari ):
Nama saya Vadim, di Yandex saya sedang mengembangkan MDS penyimpanan objek internal. Pada artikel ini, saya akan menjelaskan secara sederhana landasan teori kode redundansi (kode Reed-Solomon dan LRC). Saya akan memberi tahu Anda cara kerjanya, tanpa matematika rumit dan istilah langka. Pada akhirnya saya akan memberikan contoh penggunaan kode redundansi di Yandex.
Saya tidak akan membahas sejumlah detail matematika secara detail, tetapi saya akan memberikan link bagi yang ingin mendalami lebih dalam. Saya juga mencatat bahwa beberapa definisi matematika mungkin tidak ketat, karena artikel ini tidak ditujukan untuk ahli matematika, tetapi untuk insinyur yang ingin memahami inti masalahnya.
* Dalam literatur berbahasa Inggris, kode redundansi sering disebut kode penghapusan.
1. Inti dari kode redundansi
Inti dari semua kode redundansi sangat sederhana: menyimpan (atau mengirimkan) data agar tidak hilang jika terjadi kesalahan (kegagalan disk, kesalahan transfer data, dll.).
Di sebagian besar* kode redundansi, data dibagi menjadi n blok data, yang mana m blok kode redundansi dihitung, sehingga menghasilkan total n + m blok. Kode redundansi dibuat sedemikian rupa sehingga n blok data dapat dipulihkan hanya dengan menggunakan sebagian dari n + m blok. Selanjutnya, kita hanya akan mempertimbangkan kode redundansi blok, yaitu kode yang datanya dibagi menjadi beberapa blok.
Untuk memulihkan semua n blok data, Anda harus memiliki setidaknya n dari n + m blok, karena Anda tidak bisa mendapatkan n blok hanya dengan memiliki n-1 blok (dalam hal ini, Anda harus mengambil 1 blok βdari yang tipis udara"). Apakah n blok acak dari n + m blok cukup untuk memulihkan semua data? Hal ini bergantung pada jenis kode redundansi, misalnya, kode Reed-Solomon memungkinkan Anda memulihkan semua data menggunakan n blok arbitrer, tetapi kode redundansi LRC tidak selalu demikian.
Penyimpanan data
Dalam sistem penyimpanan data, sebagai aturan, setiap blok data dan blok kode redundansi ditulis ke disk terpisah. Kemudian, jika disk tertentu gagal, data asli masih dapat dipulihkan dan dibaca. Data dapat dipulihkan meskipun beberapa disk rusak secara bersamaan.
Transfer data
Kode redundansi dapat digunakan untuk mengirimkan data secara andal melalui jaringan yang tidak dapat diandalkan. Data yang dikirimkan dibagi menjadi beberapa blok, dan kode redundansi dihitung untuk blok tersebut. Blok data dan blok kode redundansi dikirimkan melalui jaringan. Jika kesalahan terjadi pada blok yang berubah-ubah (hingga jumlah blok tertentu), data masih dapat dikirimkan melalui jaringan tanpa kesalahan. Kode Reed-Solomon, misalnya, digunakan untuk mengirimkan data melalui jalur komunikasi optik dan komunikasi satelit.
* Ada juga kode redundansi yang datanya tidak dibagi menjadi beberapa blok, seperti kode Hamming dan kode CRC, yang banyak digunakan untuk transmisi data di jaringan Ethernet. Ini adalah kode untuk pengkodean koreksi kesalahan, mereka dirancang untuk mendeteksi kesalahan, dan bukan untuk memperbaikinya (kode Hamming juga memungkinkan koreksi sebagian kesalahan).
2. Kode Reed-Solomon
Kode Reed-Solomon adalah salah satu kode redundansi yang paling banyak digunakan, ditemukan pada tahun 1960an dan pertama kali digunakan secara luas pada tahun 1980an untuk produksi massal CD.
Ada dua pertanyaan kunci untuk memahami kode Reed-Solomon: 1) cara membuat blok kode redundansi; 2) cara memulihkan data menggunakan blok kode redundansi. Mari kita temukan jawabannya.
Untuk mempermudah, kita asumsikan lebih lanjut bahwa n=6 dan m=4. Skema lain dipertimbangkan dengan analogi.
Cara membuat blok kode redundansi
Setiap blok kode redundansi dihitung secara independen satu sama lain. Semua n blok data digunakan untuk menghitung setiap blok. Pada diagram di bawah, X1-X6 adalah blok data, P1-P4 adalah blok kode redundansi.
Semua blok data harus berukuran sama, dan bit nol dapat digunakan untuk penyelarasan. Blok kode redundansi yang dihasilkan akan berukuran sama dengan blok data. Semua blok data dibagi menjadi kata-kata (misalnya, 16 bit). Katakanlah kita membagi blok data menjadi k kata. Kemudian seluruh blok kode redundansi juga akan dibagi menjadi k kata.
Untuk menghitung kata ke-i dari setiap blok redundansi, akan digunakan kata ke-i dari semua blok data. Mereka akan dihitung berdasarkan rumus berikut:
Disini nilai x adalah kata dari blok data, p adalah kata dari blok kode redundansi, semua alpha, beta, gamma dan delta adalah angka yang dipilih secara khusus yang sama untuk semua i. Harus segera dikatakan bahwa semua nilai ini bukanlah bilangan biasa, tetapi elemen bidang Galois; operasi +, -, *, / bukanlah operasi yang kita semua kenal, tetapi operasi khusus yang diperkenalkan pada elemen Galois bidang.
Mengapa ladang Galois dibutuhkan?
Tampaknya semuanya sederhana: kita membagi data menjadi blok, blok menjadi kata-kata, menggunakan kata-kata dari blok data kita menghitung kata-kata dari blok kode redundansi - kita mendapatkan blok kode redundansi. Secara umum beginilah cara kerjanya, tetapi masalahnya ada pada detailnya:
- Sebagaimana dinyatakan di atas, ukuran kata tetap, dalam contoh kita 16 bit. Rumus kode Reed-Solomon di atas sedemikian rupa sehingga bila menggunakan bilangan bulat biasa, hasil penghitungan p mungkin tidak dapat direpresentasikan menggunakan kata dengan ukuran yang valid.
- Saat memulihkan data, rumus di atas akan dianggap sebagai sistem persamaan yang harus diselesaikan untuk memulihkan data. Selama proses penyelesaian, bilangan bulat mungkin perlu dibagi satu sama lain, sehingga menghasilkan bilangan real yang tidak dapat direpresentasikan secara akurat dalam memori komputer.
Masalah ini mencegah penggunaan bilangan bulat untuk kode Reed-Solomon. Penyelesaian soal tersebut orisinal, dapat dijelaskan sebagai berikut: mari kita buat bilangan-bilangan khusus yang dapat direpresentasikan menggunakan kata-kata dengan panjang yang diperlukan (misalnya 16 bit), dan hasil dari melakukan semua operasi yang (penjumlahan) , pengurangan, perkalian, pembagian) juga akan disajikan dalam memori komputer menggunakan kata-kata dengan panjang yang dibutuhkan.
Bilangan βkhususβ seperti itu telah dipelajari oleh matematika sejak lama; bilangan tersebut disebut bidang. Bidang adalah sekumpulan elemen dengan operasi penjumlahan, pengurangan, perkalian, dan pembagian yang ditentukan untuk elemen tersebut.
Bidang Galois* adalah bidang yang memiliki hasil unik dari setiap operasi (+, -, *, /) untuk dua elemen bidang mana pun. Bidang Galois dapat dibuat untuk bilangan berpangkat 2: 2, 4, 8, 16, dst. (sebenarnya pangkat dari bilangan prima p apa pun, tetapi dalam praktiknya kita hanya tertarik pada pangkat 2). Misalnya, untuk kata 16-bit, ini adalah bidang yang berisi 65 elemen, untuk setiap pasangannya Anda dapat menemukan hasil operasi apa pun (+, -, *, /). Nilai x, p, alpha, beta, gamma, delta dari persamaan di atas akan dianggap sebagai elemen bidang Galois untuk perhitungan.
Jadi, kita mempunyai sistem persamaan yang dengannya kita dapat menyusun blok kode redundansi dengan menulis program komputer yang sesuai. Dengan menggunakan sistem persamaan yang sama, Anda dapat melakukan pemulihan data.
* Ini bukan definisi yang ketat, melainkan deskripsi.
Bagaimana memulihkan data
Restorasi diperlukan ketika beberapa blok n + m hilang. Ini bisa berupa blok data dan blok kode redundansi. Tidak adanya blok data dan/atau blok kode redundansi berarti bahwa variabel x dan/atau p yang bersangkutan tidak diketahui dalam persamaan di atas.
Persamaan kode Reed-Solomon dapat dipandang sebagai sistem persamaan di mana semua nilai alfa, beta, gamma, delta adalah konstanta, semua x dan p yang sesuai dengan blok yang tersedia adalah variabel yang diketahui, dan sisanya x dan p tidak diketahui.
Misal blok data 1, 2, 3 dan blok kode redundansi 2 tidak tersedia, maka untuk kelompok kata ke-i akan ada sistem persamaan berikut (yang tidak diketahui ditandai dengan warna merah):
Kami memiliki sistem 4 persamaan dengan 4 hal yang tidak diketahui, yang berarti kami dapat menyelesaikannya dan memulihkan datanya!
Dari sistem persamaan ini, terdapat beberapa kesimpulan mengenai pemulihan data untuk kode Reed-Solomon (n blok data, m blok kode redundansi):
- Data dapat dipulihkan jika ada m blok atau kurang yang hilang. Jika m+1 atau lebih blok hilang, data tidak dapat dipulihkan: tidak mungkin menyelesaikan sistem persamaan m dengan m+1 yang tidak diketahui.
- Untuk memulihkan satu blok data saja, Anda perlu menggunakan n blok yang tersisa, dan Anda dapat menggunakan kode redundansi mana pun.
Apa lagi yang perlu Anda ketahui
Dalam uraian di atas, saya menghindari sejumlah masalah penting yang memerlukan pendalaman matematika lebih dalam untuk dipertimbangkan. Secara khusus, saya tidak mengatakan apa pun tentang hal berikut:
- Sistem persamaan kode Reed-Solomon harus mempunyai solusi (unik) untuk setiap kombinasi yang tidak diketahui (tidak lebih dari m yang tidak diketahui). Berdasarkan persyaratan ini, nilai alpha, beta, gamma dan delta dipilih.
- Suatu sistem persamaan harus dapat dibangun secara otomatis (tergantung pada blok mana yang tidak tersedia) dan diselesaikan.
- Kita perlu membangun bidang Galois: untuk ukuran kata tertentu, dapat menemukan hasil operasi apa pun (+, -, *, /) untuk dua elemen apa pun.
Di akhir artikel terdapat referensi literatur tentang isu-isu penting tersebut.
Pilihan n dan m
Bagaimana cara memilih n dan m dalam praktik? Dalam praktiknya, dalam sistem penyimpanan data, kode redundansi digunakan untuk menghemat ruang, sehingga m selalu dipilih kurang dari n. Nilai spesifiknya bergantung pada sejumlah faktor, termasuk:
- Keandalan penyimpanan data. Semakin besar m, semakin besar jumlah kegagalan disk yang dapat diatasi, sehingga semakin tinggi keandalannya.
- Penyimpanan berlebihan. Semakin tinggi rasio m/n, semakin tinggi redundansi penyimpanannya, dan semakin mahal biaya sistemnya.
- Waktu pemrosesan permintaan. Semakin besar jumlah n + m, semakin lama waktu respon terhadap permintaan. Karena pembacaan data (selama pemulihan) memerlukan pembacaan n blok yang disimpan di n disk berbeda, waktu baca akan ditentukan oleh disk paling lambat.
Selain itu, penyimpanan data di beberapa DC memberikan batasan tambahan pada pilihan n dan m: jika 1 DC dimatikan, data harus tetap tersedia untuk dibaca. Misalnya, saat menyimpan data dalam 3 DC, kondisi berikut harus dipenuhi: m >= n/2, jika tidak, mungkin ada situasi di mana data tidak tersedia untuk dibaca ketika 1 DC dimatikan.
3. LRC - Kode Rekonstruksi Lokal
Untuk memulihkan data menggunakan kode Reed-Solomon, Anda harus menggunakan n blok data arbitrer. Ini adalah kelemahan yang sangat signifikan untuk sistem penyimpanan data terdistribusi, karena untuk memulihkan data pada satu disk yang rusak, Anda harus membaca data dari sebagian besar disk lainnya, sehingga menimbulkan beban tambahan yang besar pada disk dan jaringan.
Kesalahan yang paling umum adalah tidak dapat diaksesnya satu blok data karena kegagalan atau kelebihan beban pada satu disk. Apakah mungkin untuk mengurangi kelebihan beban pemulihan data dalam kasus (paling umum) ini? Ternyata Anda bisa: ada kode redundansi LRC khusus untuk tujuan ini.
LRC (Kode Rekonstruksi Lokal) adalah kode redundansi yang ditemukan oleh Microsoft untuk digunakan di Windows Azure Storage. Ide LRC sesederhana mungkin: membagi semua blok data menjadi dua (atau lebih) grup dan membaca bagian dari blok kode redundansi untuk setiap grup secara terpisah. Kemudian beberapa blok kode redundansi akan dihitung menggunakan semua blok data (di LRC disebut kode redundansi global), dan beberapa - menggunakan salah satu dari dua kelompok blok data (disebut kode redundansi lokal).
LRC dilambangkan dengan tiga angka: nrl, dimana n adalah jumlah blok data, r adalah jumlah blok kode redundansi global, l adalah jumlah blok kode redundansi lokal. Untuk membaca data ketika satu blok data tidak tersedia, Anda hanya perlu membaca n/l blok - ini l kali lebih kecil dibandingkan kode Reed-Solomon.
Misalnya saja skema LRC 6-2-2. X1βX6 β 6 blok data, P1, P2 β 2 blok redundansi global, P3, P4 β 2 blok redundansi lokal.
Blok kode redundansi P1, P2 dihitung menggunakan semua blok data. Blok kode redundansi P3 - menggunakan blok data X1-X3, blok kode redundansi P4 - menggunakan blok data X4-X6.
Selebihnya dilakukan di LRC dengan analogi dengan kode Reed-Solomon. Persamaan untuk menghitung kata dari blok kode redundansi adalah:
Untuk memilih bilangan alfa, beta, gamma, delta, sejumlah kondisi harus dipenuhi untuk menjamin kemungkinan pemulihan data (yaitu, penyelesaian sistem persamaan). Anda dapat membaca lebih lanjut tentang mereka di .
Juga dalam praktiknya, operasi XOR digunakan untuk menghitung kode redundansi lokal P3, P4.
Sejumlah kesimpulan berikut dari sistem persamaan LRC:
- Untuk memulihkan 1 blok data apa pun, cukup membaca n/l blok (n/2 dalam contoh kita).
- Jika r + l blok tidak tersedia, dan semua blok termasuk dalam satu grup, maka data tidak dapat dipulihkan. Ini mudah dijelaskan dengan sebuah contoh. Biarkan blok X1βX3 dan P3 tidak tersedia: ini adalah blok r + l dari grup yang sama, 4 dalam kasus kita. Maka kita memiliki sistem 3 persamaan dengan 4 persamaan yang tidak diketahui yang tidak dapat diselesaikan.
- Dalam semua kasus lain ketika blok r + l tidak tersedia (bila setidaknya satu blok tersedia dari setiap grup), data di LRC dapat dipulihkan.
Dengan demikian, LRC mengungguli kode Reed-Solomon dalam memulihkan data setelah kesalahan tunggal. Dalam kode Reed-Solomon, untuk memulihkan satu blok data saja, Anda perlu menggunakan n blok, dan di LRC, untuk memulihkan satu blok data, cukup menggunakan n/l blok (n/2 dalam contoh kita). Di sisi lain, LRC lebih rendah daripada kode Reed-Solomon dalam hal jumlah maksimum kesalahan yang diperbolehkan. Dalam contoh di atas, kode Reed-Solomon dapat memulihkan data untuk 4 kesalahan apa pun, dan untuk LRC terdapat 2 kombinasi dari 4 kesalahan ketika data tidak dapat dipulihkan.
Hal yang lebih penting bergantung pada situasi spesifik, namun seringkali penghematan kelebihan beban yang diberikan LRC melebihi penyimpanan yang sedikit kurang dapat diandalkan.
4. Kode redundansi lainnya
Selain kode Reed-Solomon dan LRC, masih banyak kode redundansi lainnya. Kode redundansi yang berbeda menggunakan matematika yang berbeda. Berikut beberapa kode redundansi lainnya:
- Kode redundansi menggunakan operator XOR. Operasi XOR dilakukan pada n blok data, dan diperoleh 1 blok kode redundansi, yaitu skema n+1 (n blok data, 1 kode redundansi). Digunakan dalam , di mana blok data dan kode redundansi ditulis secara siklis ke semua disk dalam array.
- Algoritma ganjil genap berdasarkan operasi XOR. Memungkinkan Anda membuat 2 blok kode redundansi, yaitu skema n+2.
- Algoritma STAR berdasarkan operasi XOR. Memungkinkan Anda membuat 3 blok kode redundansi, yaitu skema n+3.
- Kode piramida adalah kode redundansi lainnya dari Microsoft.
5. Gunakan di Yandex
Sejumlah proyek infrastruktur Yandex menggunakan kode redundansi untuk penyimpanan data yang andal. Berikut beberapa contohnya:
- Penyimpanan objek internal MDS, yang saya tulis di awal artikel.
- β Sistem MapReduce dari Yandex.
- (Yandex DataBase) - database terdistribusi newSQL.
MDS menggunakan kode redundansi LRC, skema 8-2-2. Data dengan kode redundansi ditulis ke 12 disk berbeda di server berbeda di 3 DC berbeda: 4 server di setiap DC. Baca lebih lanjut tentang ini di .
YT menggunakan kode Reed-Solomon (Skema 6-3), yang pertama kali diterapkan, dan kode redundansi LRC (Skema 12-2-2), dengan LRC sebagai metode penyimpanan pilihan.
YDB menggunakan kode redundansi berbasis ganjil genap (Gambar 4-2). Tentang kode redundansi di YDB .
Penggunaan skema kode redundansi yang berbeda disebabkan oleh persyaratan sistem yang berbeda. Misalnya pada MDS, data yang disimpan menggunakan LRC ditempatkan di 3 DC sekaligus. Penting bagi kami bahwa data tetap tersedia untuk dibaca jika salah satu DC gagal, oleh karena itu blok harus didistribusikan ke seluruh DC sehingga jika ada DC yang tidak tersedia, jumlah blok yang tidak dapat diakses tidak lebih dari yang diizinkan. Pada skema 1-8-2, Anda dapat menempatkan 2 blok di setiap DC, kemudian ketika DC mana pun dimatikan, 4 blok tidak akan tersedia, dan data dapat dibaca. Apapun skema yang kita pilih ketika menempatkannya di 4 DC, bagaimanapun juga harus ada (r + l) / n >= 3, yaitu redundansi penyimpanan minimal 0,5%.
Di YT situasinya berbeda: setiap cluster YT seluruhnya berlokasi di 1 DC (cluster berbeda di DC berbeda), jadi tidak ada batasan seperti itu. Skema 12-2-2 memberikan redundansi 33%, yaitu menyimpan data lebih murah, dan juga dapat bertahan hingga 4 kali pemadaman disk secara bersamaan, seperti skema MDS.
Masih banyak lagi fitur penggunaan kode redundansi dalam sistem penyimpanan dan pemrosesan data: nuansa pemulihan data, dampak pemulihan pada waktu eksekusi kueri, fitur perekaman data, dll. Saya akan membahas ini secara terpisah dan fitur lainnya penggunaan kode redundansi dalam praktiknya, jika topiknya menarik.
6. Tautan
- Serangkaian artikel tentang kode Reed-Solomon dan bidang Galois:
Mereka melihat lebih dalam matematika dalam bahasa yang mudah diakses. - Artikel dari Microsoft tentang LRC:
Bagian 2 menjelaskan secara singkat teori dan kemudian membahas pengalaman LRC dalam praktiknya. - Skema ganjil genap:
- Skema BINTANG:
- Kode piramida:
- Kode redundansi di MDS:
- Kode redundansi di YT:
- Kode redundansi di YDB:
Sumber: www.habr.com