Inilah yang kelihatan seperti redundansi
Kod redundansi* digunakan secara meluas dalam sistem komputer untuk meningkatkan kebolehpercayaan storan data. Dalam Yandex mereka digunakan dalam banyak projek. Contohnya, menggunakan kod redundansi dan bukannya replikasi dalam storan objek dalaman kami menjimatkan berjuta-juta tanpa mengorbankan kebolehpercayaan. Tetapi walaupun penggunaannya meluas, penerangan yang jelas tentang cara kod redundansi berfungsi sangat jarang berlaku. Mereka yang ingin memahami berhadapan dengan lebih kurang perkara berikut (dari ):
Nama saya Vadim, di Yandex saya sedang membangunkan storan objek dalaman MDS. Dalam artikel ini, saya akan menerangkan secara ringkas asas teori kod redundansi (kod Reed-Solomon dan LRC). Saya akan memberitahu anda bagaimana ia berfungsi, tanpa matematik yang rumit dan istilah yang jarang berlaku. Pada akhirnya saya akan memberikan contoh menggunakan kod redundansi dalam Yandex.
Saya tidak akan mempertimbangkan beberapa butiran matematik secara terperinci, tetapi saya akan menyediakan pautan untuk mereka yang ingin menyelam lebih dalam. Saya juga akan ambil perhatian bahawa beberapa definisi matematik mungkin tidak ketat, kerana artikel itu tidak bertujuan untuk ahli matematik, tetapi untuk jurutera yang ingin memahami intipati isu itu.
* Dalam kesusasteraan bahasa Inggeris, kod redundansi selalunya dipanggil kod pemadaman.
1. Intipati kod redundansi
Intipati semua kod redundansi adalah sangat mudah: simpan (atau hantar) data supaya ia tidak hilang apabila ralat berlaku (kegagalan cakera, ralat pemindahan data, dll.).
Dalam kebanyakan* kod redundansi, data dibahagikan kepada n blok data, yang mana m blok kod redundansi dikira, menghasilkan sejumlah n + m blok. Kod redundansi dibina sedemikian rupa sehingga n blok data boleh dipulihkan menggunakan hanya sebahagian daripada n + m blok. Seterusnya, kami akan mempertimbangkan hanya kod redundansi blok, iaitu kod di mana data dibahagikan kepada blok.
Untuk memulihkan semua n blok data, anda perlu mempunyai sekurang-kurangnya n daripada n + m blok, kerana anda tidak boleh mendapatkan n blok dengan hanya mempunyai n-1 blok (dalam kes ini, anda perlu mengambil 1 blok "daripada nipis udaraβ). Adakah n blok rawak n + m blok cukup untuk memulihkan semua data? Ini bergantung pada jenis kod redundansi, contohnya, kod Reed-Solomon membenarkan anda memulihkan semua data menggunakan blok n arbitrary, tetapi kod redundansi LRC tidak selalunya.
Simpanan data
Dalam sistem penyimpanan data, sebagai peraturan, setiap blok data dan blok kod redundansi ditulis pada cakera berasingan. Kemudian, jika cakera sewenang-wenangnya gagal, data asal masih boleh dipulihkan dan dibaca. Data boleh dipulihkan walaupun beberapa cakera gagal pada masa yang sama.
Pemindahan data
Kod redundansi boleh digunakan untuk menghantar data dengan pasti melalui rangkaian yang tidak boleh dipercayai. Data yang dihantar dibahagikan kepada blok, dan kod redundansi dikira untuknya. Kedua-dua blok data dan blok kod redundansi dihantar melalui rangkaian. Jika ralat berlaku dalam blok sewenang-wenangnya (sehingga bilangan blok tertentu), data masih boleh dihantar melalui rangkaian tanpa ralat. Kod Reed-Solomon, sebagai contoh, digunakan untuk menghantar data melalui talian komunikasi optik dan dalam komunikasi satelit.
* Terdapat juga kod redundansi di mana data tidak dibahagikan kepada blok, seperti kod Hamming dan kod CRC, yang digunakan secara meluas untuk penghantaran data dalam rangkaian Ethernet. Ini adalah kod untuk pengekodan pembetulan ralat, ia direka untuk mengesan ralat, dan bukan untuk membetulkannya (kod Hamming juga membenarkan pembetulan separa ralat).
2. Kod Reed-Solomon
Kod Reed-Solomon ialah salah satu kod redundansi yang paling banyak digunakan, dicipta pada tahun 1960-an dan pertama kali digunakan secara meluas pada 1980-an untuk pengeluaran besar-besaran cakera padat.
Terdapat dua soalan utama untuk memahami kod Reed-Solomon: 1) cara membuat blok kod redundansi; 2) bagaimana untuk memulihkan data menggunakan blok kod redundansi. Mari cari jawapan kepada mereka.
Untuk kesederhanaan, kita selanjutnya akan menganggap bahawa n=6 dan m=4. Skim lain dipertimbangkan dengan analogi.
Cara membuat blok kod redundansi
Setiap blok kod redundansi dikira secara berasingan daripada yang lain. Semua n blok data digunakan untuk mengira setiap blok. Dalam rajah di bawah, X1-X6 ialah blok data, P1-P4 ialah blok kod redundansi.
Semua blok data mestilah saiz yang sama, dan sifar bit boleh digunakan untuk penjajaran. Blok kod redundansi yang terhasil akan mempunyai saiz yang sama dengan blok data. Semua blok data dibahagikan kepada perkataan (contohnya, 16 bit). Katakan kita membahagikan blok data kepada k perkataan. Kemudian semua blok kod redundansi juga akan dibahagikan kepada k perkataan.
Untuk mengira perkataan ke-i bagi setiap blok redundansi, perkataan ke-i bagi semua blok data akan digunakan. Mereka akan dikira mengikut formula berikut:
Di sini nilai x ialah perkataan blok data, p ialah perkataan blok kod redundansi, semua alpha, beta, gamma dan delta ialah nombor yang dipilih khas yang sama untuk semua i. Ia mesti dikatakan dengan segera bahawa semua nilai ini bukan nombor biasa, tetapi elemen medan Galois; operasi +, -, *, / bukan operasi biasa kepada kita semua, tetapi operasi khas yang diperkenalkan pada elemen Galois padang.
Mengapa medan Galois diperlukan?
Nampaknya segala-galanya adalah mudah: kami membahagikan data kepada blok, blok menjadi perkataan, menggunakan perkataan blok data kami mengira perkataan blok kod redundansi - kami mendapat blok kod redundansi. Secara umum ini adalah cara ia berfungsi, tetapi syaitan ada dalam butirannya:
- Seperti yang dinyatakan di atas, saiz perkataan adalah tetap, dalam contoh kami 16 bit. Formula di atas untuk kod Reed-Solomon adalah sedemikian rupa sehingga apabila menggunakan integer biasa, hasil pengiraan p mungkin tidak boleh diwakili menggunakan perkataan dengan saiz yang sah.
- Apabila memulihkan data, formula di atas akan dianggap sebagai sistem persamaan yang mesti diselesaikan untuk memulihkan data. Semasa proses penyelesaian, mungkin perlu untuk membahagikan integer antara satu sama lain, menghasilkan nombor nyata yang tidak dapat diwakili dengan tepat dalam ingatan komputer.
Masalah ini menghalang penggunaan integer untuk kod Reed-Solomon. Penyelesaian masalah itu adalah asal, ia boleh diterangkan seperti berikut: mari kita tampilkan nombor khas yang boleh diwakili menggunakan kata-kata dengan panjang yang diperlukan (contohnya, 16 bit), dan hasil daripada melaksanakan semua operasi yang (penambahan). , penolakan, pendaraban, pembahagian) juga akan dipersembahkan dalam ingatan komputer menggunakan perkataan dengan panjang yang diperlukan.
Nombor "istimewa" sedemikian telah dipelajari oleh matematik untuk masa yang lama, ia dipanggil medan. Medan ialah satu set elemen dengan operasi tambah, tolak, darab dan bahagi yang ditakrifkan untuknya.
Medan Galois* ialah medan yang mempunyai hasil unik bagi setiap operasi (+, -, *, /) untuk mana-mana dua elemen medan. Medan Galois boleh dibina untuk nombor yang merupakan kuasa 2: 2, 4, 8, 16, dsb. (sebenarnya kuasa mana-mana nombor perdana p, tetapi dalam amalan kita hanya berminat dengan kuasa 2). Sebagai contoh, untuk perkataan 16-bit, ini adalah medan yang mengandungi 65 elemen, untuk setiap pasangan anda boleh mencari hasil daripada sebarang operasi (+, -, *, /). Nilai x, p, alpha, beta, gamma, delta daripada persamaan di atas akan dianggap sebagai elemen medan Galois untuk pengiraan.
Oleh itu, kita mempunyai sistem persamaan yang dengannya kita boleh membina blok kod redundansi dengan menulis program komputer yang sesuai. Menggunakan sistem persamaan yang sama, anda boleh melakukan pemulihan data.
* Ini bukan takrifan yang ketat, sebaliknya huraian.
Bagaimana untuk memulihkan data
Pemulihan diperlukan apabila beberapa blok n + m hilang. Ini boleh menjadi kedua-dua blok data dan blok kod redundansi. Ketiadaan blok data dan/atau blok kod redundansi akan bermakna pembolehubah x dan/atau p yang sepadan tidak diketahui dalam persamaan di atas.
Persamaan untuk kod Reed-Solomon boleh dilihat sebagai sistem persamaan di mana semua nilai alfa, beta, gamma, delta adalah pemalar, semua x dan p yang sepadan dengan blok yang tersedia adalah pembolehubah yang diketahui, dan baki x dan p tidak diketahui.
Sebagai contoh, biarkan blok data 1, 2, 3 dan blok kod redundansi 2 tidak tersedia, maka untuk kumpulan perkataan ke-i akan terdapat sistem persamaan berikut (tidak diketahui ditandakan dengan warna merah):
Kami mempunyai sistem 4 persamaan dengan 4 yang tidak diketahui, yang bermaksud kami boleh menyelesaikannya dan memulihkan data!
Daripada sistem persamaan ini, beberapa kesimpulan mengikuti tentang pemulihan data untuk kod Reed-Solomon (n blok data, m blok kod redundansi):
- Data boleh dipulihkan jika mana-mana blok m atau kurang hilang. Jika m+1 atau lebih blok hilang, data tidak boleh dipulihkan: adalah mustahil untuk menyelesaikan sistem persamaan m dengan m + 1 tidak diketahui.
- Untuk memulihkan walaupun satu blok data, anda perlu menggunakan mana-mana n daripada blok yang tinggal dan anda boleh menggunakan mana-mana kod redundansi.
Apa lagi yang perlu anda ketahui
Dalam huraian di atas, saya mengelakkan beberapa isu penting yang memerlukan kajian matematik yang lebih mendalam untuk dipertimbangkan. Khususnya, saya tidak mengatakan apa-apa tentang perkara berikut:
- Sistem persamaan untuk kod Reed-Solomon mesti mempunyai penyelesaian (unik) untuk sebarang kombinasi yang tidak diketahui (tidak lebih daripada m yang tidak diketahui). Berdasarkan keperluan ini, nilai alfa, beta, gamma dan delta dipilih.
- Sistem persamaan mesti boleh dibina secara automatik (bergantung pada blok mana yang tidak tersedia) dan diselesaikan.
- Kita perlu membina medan Galois: untuk saiz perkataan tertentu, dapat mencari hasil daripada sebarang operasi (+, -, *, /) untuk mana-mana dua elemen.
Di akhir artikel terdapat rujukan kepada literatur mengenai isu-isu penting ini.
Pilihan n dan m
Bagaimana untuk memilih n dan m dalam amalan? Dalam amalan, dalam sistem penyimpanan data, kod redundansi digunakan untuk menjimatkan ruang, jadi m sentiasa dipilih kurang daripada n. Nilai khusus mereka bergantung pada beberapa faktor, termasuk:
- Kebolehpercayaan penyimpanan data. Semakin besar m, semakin besar bilangan kegagalan cakera yang boleh diselamatkan, iaitu, semakin tinggi kebolehpercayaan.
- Penyimpanan berlebihan. Semakin tinggi nisbah m/n, semakin tinggi redundansi storan, dan semakin mahal sistem tersebut.
- Minta masa pemprosesan. Lebih besar jumlah n + m, lebih lama masa respons kepada permintaan. Memandangkan membaca data (semasa pemulihan) memerlukan bacaan n blok yang disimpan pada n cakera yang berbeza, masa baca akan ditentukan oleh cakera yang paling perlahan.
Di samping itu, menyimpan data dalam beberapa DC mengenakan sekatan tambahan pada pilihan n dan m: jika 1 DC dimatikan, data mesti masih tersedia untuk dibaca. Sebagai contoh, apabila menyimpan data dalam 3 DC, syarat berikut mesti dipenuhi: m >= n/2, jika tidak, mungkin terdapat situasi di mana data tidak tersedia untuk dibaca apabila 1 DC dimatikan.
3. LRC - Kod Pembinaan Semula Tempatan
Untuk memulihkan data menggunakan kod Reed-Solomon, anda perlu menggunakan n blok data sewenang-wenangnya. Ini adalah kelemahan yang sangat ketara untuk sistem penyimpanan data yang diedarkan, kerana untuk memulihkan data pada satu cakera yang rosak, anda perlu membaca data dari kebanyakan yang lain, mewujudkan beban tambahan yang besar pada cakera dan rangkaian.
Ralat yang paling biasa ialah ketidakbolehcapaian satu blok data disebabkan oleh kegagalan atau beban berlebihan satu cakera. Adakah mungkin untuk mengurangkan beban berlebihan untuk pemulihan data dalam kes (paling biasa) ini? Ternyata anda boleh: terdapat kod redundansi LRC khusus untuk tujuan ini.
LRC (Kod Pembinaan Semula Tempatan) ialah kod redundansi yang dicipta oleh Microsoft untuk digunakan dalam Windows Azure Storage. Idea LRC adalah semudah mungkin: bahagikan semua blok data kepada dua (atau lebih) kumpulan dan baca sebahagian daripada blok kod redundansi untuk setiap kumpulan secara berasingan. Kemudian beberapa blok kod redundansi akan dikira menggunakan semua blok data (dalam LRC ia dipanggil kod redundansi global), dan beberapa akan dikira menggunakan salah satu daripada dua kumpulan blok data (ia dipanggil kod redundansi tempatan).
LRC dilambangkan dengan tiga nombor: nrl, dengan n ialah bilangan blok data, r ialah bilangan blok kod redundansi global, l ialah bilangan blok kod redundansi tempatan. Untuk membaca data apabila satu blok data tidak tersedia, anda perlu membaca hanya n/l blok - ini l kali kurang daripada dalam kod Reed-Solomon.
Sebagai contoh, pertimbangkan skim LRC 6-2-2. X1βX6 β 6 blok data, P1, P2 β 2 blok redundansi global, P3, P4 β 2 blok redundansi tempatan.
Blok kod redundansi P1, P2 dikira menggunakan semua blok data. Blok kod redundansi P3 - menggunakan blok data X1-X3, blok kod redundansi P4 - menggunakan blok data X4-X6.
Selebihnya dilakukan dalam LRC dengan analogi dengan kod Reed-Solomon. Persamaan untuk mengira perkataan blok kod redundansi ialah:
Untuk memilih nombor alfa, beta, gamma, delta, beberapa syarat mesti dipenuhi untuk menjamin kemungkinan pemulihan data (iaitu, menyelesaikan sistem persamaan). Anda boleh membaca lebih lanjut tentang mereka dalam .
Juga dalam amalan, operasi XOR digunakan untuk mengira kod redundansi tempatan P3, P4.
Beberapa kesimpulan berikut daripada sistem persamaan untuk LRC:
- Untuk memulihkan mana-mana 1 blok data, sudah cukup untuk membaca blok n/l (n/2 dalam contoh kami).
- Jika blok r + l tidak tersedia, dan semua blok disertakan dalam satu kumpulan, maka data tidak boleh dipulihkan. Ini mudah dijelaskan dengan contoh. Biarkan blok X1βX3 dan P3 tidak tersedia: ini adalah blok r + l daripada kumpulan yang sama, 4 dalam kes kami. Kemudian kita mempunyai sistem 3 persamaan dengan 4 tidak diketahui yang tidak dapat diselesaikan.
- Dalam semua kes lain ketiadaan blok r + l (apabila sekurang-kurangnya satu blok tersedia daripada setiap kumpulan), data dalam LRC boleh dipulihkan.
Oleh itu, LRC mengatasi kod Reed-Solomon dalam memulihkan data selepas ralat tunggal. Dalam kod Reed-Solomon, untuk memulihkan walaupun satu blok data, anda perlu menggunakan n blok, dan dalam LRC, untuk memulihkan satu blok data, cukup menggunakan blok n/l (n/2 dalam contoh kami). Sebaliknya, LRC adalah lebih rendah daripada kod Reed-Solomon dari segi bilangan maksimum ralat yang dibenarkan. Dalam contoh di atas, kod Reed-Solomon boleh memulihkan data untuk sebarang 4 ralat, dan untuk LRC terdapat 2 gabungan 4 ralat apabila data tidak dapat dipulihkan.
Apa yang lebih penting bergantung pada situasi tertentu, tetapi selalunya penjimatan lebihan beban yang LRC sediakan melebihi storan yang kurang dipercayai.
4. Kod redundansi lain
Selain kod Reed-Solomon dan LRC, terdapat banyak kod redundansi lain. Kod redundansi yang berbeza menggunakan matematik yang berbeza. Berikut ialah beberapa kod redundansi lain:
- Kod redundansi menggunakan operator XOR. Operasi XOR dilakukan pada n blok data, dan 1 blok kod redundansi diperolehi, iaitu skema n+1 (n blok data, 1 kod redundansi). Digunakan dalam , di mana blok data dan kod redundansi ditulis secara kitaran kepada semua cakera tatasusunan.
- Algoritma genap-ganjil berdasarkan operasi XOR. Membolehkan anda membina 2 blok kod redundansi, iaitu skema n+2.
- Algoritma STAR berdasarkan operasi XOR. Membolehkan anda membina 3 blok kod redundansi, iaitu skema n+3.
- Kod piramid ialah kod redundansi lain daripada Microsoft.
5. Gunakan dalam Yandex
Sebilangan projek infrastruktur Yandex menggunakan kod redundansi untuk penyimpanan data yang boleh dipercayai. Berikut adalah beberapa contoh:
- Storan objek dalaman MDS, yang saya tulis pada permulaan artikel.
- β Sistem MapReduce Yandex.
- (Yandex DataBase) - pangkalan data teragih newSQL.
MDS menggunakan kod redundansi LRC, skema 8-2-2. Data dengan kod redundansi ditulis kepada 12 cakera berbeza dalam pelayan berbeza dalam 3 DC berbeza: 4 pelayan dalam setiap DC. Baca lebih lanjut tentang ini dalam .
YT menggunakan kedua-dua kod Reed-Solomon (Skim 6-3), yang merupakan yang pertama dilaksanakan dan kod redundansi LRC (Skim 12-2-2), dengan LRC sebagai kaedah penyimpanan pilihan.
YDB menggunakan kod redundansi berasaskan genap-ganjil (Rajah 4-2). Mengenai kod redundansi dalam YDB sudah .
Penggunaan skema kod redundansi yang berbeza adalah disebabkan oleh keperluan yang berbeza untuk sistem. Sebagai contoh, dalam MDS, data yang disimpan menggunakan LRC diletakkan dalam 3 DC sekaligus. Adalah penting bagi kami bahawa data kekal tersedia untuk dibaca jika 1 daripada mana-mana DC gagal, oleh itu blok mesti diedarkan ke seluruh DC supaya jika mana-mana DC tidak tersedia, bilangan blok yang tidak boleh diakses adalah tidak lebih daripada yang dibenarkan. Dalam skema 8-2-2, anda boleh meletakkan 4 blok dalam setiap DC, kemudian apabila mana-mana DC dimatikan, 4 blok akan tidak tersedia, dan data boleh dibaca. Apa sahaja skim yang kita pilih apabila meletakkannya dalam 3 DC, dalam apa jua keadaan harus ada (r + l) / n >= 0,5, iaitu, lebihan penyimpanan akan sekurang-kurangnya 50%.
Dalam YT keadaannya berbeza: setiap kluster YT terletak sepenuhnya dalam 1 DC (kluster berbeza dalam DC berbeza), jadi tiada sekatan sedemikian. Skim 12-2-2 menyediakan 33% lebihan, iaitu, menyimpan data adalah lebih murah, dan ia juga boleh bertahan sehingga 4 gangguan cakera serentak, sama seperti skim MDS.
Terdapat banyak lagi ciri penggunaan kod redundansi dalam sistem storan dan pemprosesan data: nuansa pemulihan data, kesan pemulihan pada masa pelaksanaan pertanyaan, ciri rakaman data, dll. Saya akan bercakap secara berasingan tentang ciri ini dan ciri lain penggunaan kod redundansi dalam amalan, jika topik itu akan menarik.
6. Pautan
- Satu siri artikel tentang kod Reed-Solomon dan medan Galois:
Mereka melihat dengan lebih mendalam tentang matematik dalam bahasa yang boleh diakses. - Artikel daripada Microsoft tentang LRC:
Bahagian 2 menerangkan secara ringkas teori dan kemudian membincangkan pengalaman dengan LRC secara praktikal. - Skim ganjil genap:
- Skim STAR:
- Kod piramid:
- Kod redundansi dalam MDS:
- Kod redundansi dalam YT:
- Kod redundansi dalam YDB:
Sumber: www.habr.com