Илүүдэл гэдэг ийм л харагдаж байна
Мэдээллийн хадгалалтын найдвартай байдлыг нэмэгдүүлэхийн тулд илүүдэл кодыг* компьютерийн системд өргөн ашигладаг. Yandex-д тэдгээрийг олон төсөлд ашигладаг. Жишээлбэл, дотоод объектын санд хуулбарлахын оронд илүүдэл кодыг ашиглах нь найдвартай байдлыг алдагдуулахгүйгээр сая саяыг хэмнэдэг. Гэхдээ өргөн хэрэглэгддэг хэдий ч илүүдэл кодууд хэрхэн ажилладаг талаар тодорхой тайлбар маш ховор байдаг. Ойлгохыг хүссэн хүмүүс ойролцоогоор дараах байдалтай тулгардаг ( ):
Намайг Вадим гэдэг, Yandex дээр би MDS-ийн дотоод объектын санах ойг боловсруулж байна. Энэ нийтлэлд би илүүдэл кодын (Рид-Соломон ба LRC код) онолын үндэслэлийг энгийн үгээр тайлбарлах болно. Энэ нь нарийн төвөгтэй математик, ховор нэр томьёогүйгээр хэрхэн ажилладагийг би танд хэлье. Төгсгөлд нь би Yandex дахь илүүдэл кодыг ашиглах жишээг өгөх болно.
Би хэд хэдэн математикийн нарийн ширийн зүйлийг нарийвчлан авч үзэхгүй, харин гүнзгий шумбахыг хүсч буй хүмүүст зориулсан холбоосыг өгөх болно. Нийтлэл нь математикчдад зориулагдаагүй, харин асуудлын мөн чанарыг ойлгохыг хүсч буй инженерүүдэд зориулагдсан тул зарим математикийн тодорхойлолтууд хатуу биш байж магадгүй гэдгийг би тэмдэглэх болно.
* Англи хэл дээрх уран зохиолд илүүдэл кодыг ихэвчлэн устгах код гэж нэрлэдэг.
1. Илүүдэл кодын мөн чанар
Бүх илүүдэл кодын мөн чанар нь маш энгийн: алдаа гарсан үед (дискний эвдрэл, өгөгдөл дамжуулах алдаа гэх мэт) алдагдахгүйн тулд өгөгдлийг хадгалах (эсвэл дамжуулах).
Ихэнх* нэмэлт кодуудад өгөгдөл нь n өгөгдлийн блокт хуваагддаг бөгөөд үүнд зориулж m блок илүүдэл кодыг тоолж, нийт n + m блок үүсгэдэг. Илүүдэл кодууд нь n + m блокуудын зөвхөн нэг хэсгийг ашиглан n блок өгөгдлийг сэргээх боломжтой байдлаар бүтээгдсэн. Дараа нь бид зөвхөн блокийн илүүдэл кодыг, өөрөөр хэлбэл өгөгдлийг блок болгон хуваасан кодуудыг авч үзэх болно.
Бүх n блок өгөгдлийг сэргээхийн тулд дор хаяж n блок n + m блоктой байх шаардлагатай, учир нь та зөвхөн n-1 блоктой байж n блок авах боломжгүй (энэ тохиолдолд та 1 блок "нимгэнээс" авах хэрэгтэй болно. агаар"). Бүх өгөгдлийг сэргээхэд n + m блок бүхий n санамсаргүй блок хангалттай юу? Энэ нь илүүдэл кодын төрлөөс шалтгаална, жишээлбэл, Рид-Соломон кодууд нь дурын n блок ашиглан бүх өгөгдлийг сэргээх боломжийг олгодог боловч LRC нэмэлт код нь үргэлж байдаггүй.
Өгөгдөл хадгалах
Өгөгдөл хадгалах системд дүрмээр бол өгөгдлийн блок болон нэмэлт кодын блок тус бүрийг тусдаа дискэнд бичдэг. Дараа нь дурын диск бүтэлгүйтвэл анхны өгөгдлийг сэргээж уншиж болно. Хэд хэдэн диск зэрэг доголдсон ч өгөгдлийг сэргээх боломжтой.
Мэдээлэл дамжуулах
Илүүдэл кодыг найдваргүй сүлжээгээр өгөгдлийг найдвартай дамжуулахад ашиглаж болно. Дамжуулсан өгөгдлийг блокуудад хувааж, тэдгээрийн нөөцийн кодыг тооцдог. Өгөгдлийн блок болон нэмэлт кодын блок хоёулаа сүлжээгээр дамждаг. Хэрэв дурын блокуудад алдаа гарвал (тодорхой тооны блок хүртэл) өгөгдлийг сүлжээгээр алдаагүйгээр дамжуулах боломжтой. Жишээлбэл, Рид-Соломон кодыг оптик холбооны шугамаар болон хиймэл дагуулын холбоогоор өгөгдөл дамжуулахад ашигладаг.
* Мөн Ethernet сүлжээнд өгөгдөл дамжуулахад өргөн хэрэглэгддэг Хаммингийн код, CRC код зэрэг өгөгдлийг блок болгон хуваадаггүй нэмэлт кодууд байдаг. Эдгээр нь алдааг засах кодчилол бөгөөд алдааг илрүүлэхэд зориулагдсан бөгөөд тэдгээрийг засах биш (Хэммингийн код нь алдааг хэсэгчлэн засах боломжийг олгодог).
2. Рид-Соломон кодууд
Рид-Соломон код нь 1960-аад онд зохион бүтээгдсэн хамгийн өргөн хэрэглэгддэг нэмэлт кодуудын нэг бөгөөд 1980-аад онд анх удаа компакт диск үйлдвэрлэхэд өргөн хэрэглэгддэг.
Рид-Соломон кодыг ойлгох хоёр гол асуулт байна: 1) илүүдэл кодын блокуудыг хэрхэн үүсгэх; 2) нөөц кодын блок ашиглан өгөгдлийг хэрхэн сэргээх. Тэдэнд хариулт хайцгаая.
Хялбар болгохын тулд бид цаашдаа n=6 ба m=4 гэж үзнэ. Бусад схемүүдийг аналоги байдлаар авч үздэг.
Илүүдэл кодын блокуудыг хэрхэн үүсгэх
Илүүдэл кодын блок бүрийг бусдаас үл хамааран тоолно. Блок бүрийг тоолоход бүх n өгөгдлийн блок ашигладаг. Доорх диаграммд X1-X6 нь өгөгдлийн блокууд, P1-P4 нь илүүдэл кодын блокууд юм.
Бүх өгөгдлийн блокууд ижил хэмжээтэй байх ёстой бөгөөд тэг битийг зэрэгцүүлэхэд ашиглаж болно. Үүссэн илүүдэл кодын блокууд нь өгөгдлийн блокуудтай ижил хэмжээтэй байх болно. Бүх өгөгдлийн блокууд нь үгэнд хуваагддаг (жишээлбэл, 16 бит). Өгөгдлийн блокуудыг k үг болгон хуваасан гэж бодъё. Дараа нь илүүдэл кодын бүх блокууд нь бас k үгэнд хуваагдана.
Илүүдэл блок бүрийн i-р үгийг тоолохдоо бүх өгөгдлийн блокуудын i-р үгийг ашиглана. Тэдгээрийг дараахь томъёогоор тооцоолно.
Энд x утгууд нь өгөгдлийн блокуудын үгс, p нь нэмэлт кодын блокуудын үгс, бүх альфа, бета, гамма, дельта нь тусгайлан сонгосон тоонууд бөгөөд бүх i-д ижил байна. Эдгээр бүх утгууд нь энгийн тоо биш, харин Галуагийн талбайн элементүүд гэдгийг шууд хэлэх ёстой; +, -, *, / үйлдлүүд нь бид бүгдэд танил болсон үйлдлүүд биш, харин Галуагийн элементүүдэд нэвтрүүлсэн тусгай ажиллагаа юм. талбар.
Галуагийн талбайнууд яагаад хэрэгтэй вэ?
Бүх зүйл энгийн мэт санагдаж байна: бид өгөгдлийг блок болгон, блокуудыг үг болгон хувааж, өгөгдлийн блокуудын үгсийг ашиглан илүүдэл кодын блокуудын үгсийг тоолдог - илүүдэл кодын блокуудыг авдаг. Ерөнхийдөө энэ нь хэрхэн ажилладаг вэ, гэхдээ чөтгөр нарийн ширийн зүйлд байдаг:
- Дээр дурдсанчлан үгийн хэмжээ нь тогтмол, бидний жишээнд 16 бит байна. Дээрх Рид-Соломон кодын томъёонууд нь энгийн бүхэл тоонуудыг ашиглах үед p-г тооцоолох үр дүнг хүчинтэй хэмжээтэй үгээр илэрхийлэх боломжгүй байх болно.
- Өгөгдлийг сэргээх үед дээрх томьёог өгөгдлийг сэргээхийн тулд шийдвэрлэх ёстой тэгшитгэлийн систем гэж үзнэ. Шийдвэрлэх явцад бүхэл тоонуудыг хооронд нь хуваах шаардлагатай болж, улмаар компьютерийн санах ойд үнэн зөв дүрслэгдэх боломжгүй бодит тоо гарч ирдэг.
Эдгээр асуудлууд нь Рид-Соломон кодуудад бүхэл тоо ашиглахаас сэргийлдэг. Асуудлын шийдэл нь анхны бөгөөд үүнийг дараах байдлаар тодорхойлж болно: шаардлагатай урттай үгсийг (жишээлбэл, 16 бит) ашиглан илэрхийлж болох тусгай тоонуудыг гаргаж ирцгээе, бүх үйлдлүүдийн үр дүнг (нэмэлт) гаргацгаая. , хасах, үржүүлэх, хуваах) мөн шаардлагатай урттай үгсийг ашиглан компьютерийн санах ойд үзүүлнэ.
Ийм "тусгай" тоог математик удаан хугацаанд судалж ирсэн бөгөөд тэдгээрийг талбар гэж нэрлэдэг. Талбар нь нэмэх, хасах, үржүүлэх, хуваах үйлдлүүд бүхий элементүүдийн багц юм.
Galois* талбарууд нь талбарын дурын хоёр элементийн үйлдэл бүрийн өвөрмөц үр дүн (+, -, *, /) байдаг талбарууд юм. 2: 2, 4, 8, 16 гэх мэт тоонуудын хувьд Галуагийн талбаруудыг байгуулж болно (үнэндээ ямар ч p анхны тооны зэрэглэлүүд, гэхдээ практик дээр бид зөвхөн 2-ын зэрэглэлийг сонирхож байна). Жишээлбэл, 16 битийн үгсийн хувьд энэ нь 65 элемент агуулсан талбар бөгөөд хос тус бүрээс та аливаа үйлдлийн үр дүнг олох боломжтой (+, -, *, /). Дээрх тэгшитгэлээс x, p, альфа, бета, гамма, дельта утгуудыг тооцоололд Галуагийн талбайн элементүүд гэж үзнэ.
Тиймээс бид тохирох компьютерийн программ бичих замаар илүүдэл кодын блокуудыг барьж болох тэгшитгэлийн системтэй болсон. Ижил тэгшитгэлийн системийг ашиглан та өгөгдлийг сэргээх ажлыг хийж болно.
* Энэ бол хатуу тодорхойлолт биш, харин тайлбар юм.
Мэдээллийг хэрхэн сэргээх вэ
Зарим n + m блок байхгүй үед сэргээн засварлах шаардлагатай. Эдгээр нь өгөгдлийн блок болон илүүдэл кодын блок хоёулаа байж болно. Өгөгдлийн блок ба/эсвэл илүүдэл кодын блок байхгүй нь дээрх тэгшитгэлд харгалзах x ба/эсвэл p хувьсагч тодорхойгүй байна гэсэн үг юм.
Рид-Соломон кодын тэгшитгэлийг бүх альфа, бета, гамма, дельта утгууд нь тогтмол, боломжтой блокуудад харгалзах бүх x ба p нь мэдэгдэж буй хувьсагч, үлдсэн x ба p нь тэгшитгэлийн систем гэж үзэж болно. үл мэдэгдэх.
Жишээлбэл, өгөгдлийн блок 1, 2, 3 болон нэмэлт кодын блок 2-ыг ашиглах боломжгүй бол i-р бүлгийн үгсийн хувьд дараахь тэгшитгэлийн систем байх болно (үл мэдэгдэхийг улаанаар тэмдэглэсэн):
Бидэнд 4 үл мэдэгдэх 4 тэгшитгэлийн систем байгаа бөгөөд энэ нь бид үүнийг шийдэж, өгөгдлийг сэргээж чадна гэсэн үг юм!
Энэхүү тэгшитгэлийн системээс Reed-Solomon кодын өгөгдлийг сэргээх талаар хэд хэдэн дүгнэлт гаргав (n өгөгдлийн блок, m илүүдэл кодын блок):
- Хэрэв m блок буюу түүнээс цөөн блок алдагдсан бол өгөгдлийг сэргээх боломжтой. Хэрэв m+1 ба түүнээс дээш блок алдагдсан бол өгөгдлийг сэргээх боломжгүй: m+1 үл мэдэгдэх m тэгшитгэлийн системийг шийдэх боломжгүй.
- Нэг ч гэсэн өгөгдлийн блокыг сэргээхийн тулд та үлдсэн блокуудын аль нэг n-ийг ашиглах шаардлагатай бөгөөд нэмэлт кодуудын аль нэгийг ашиглаж болно.
Та өөр юу мэдэх хэрэгтэй вэ
Дээрх тайлбарт би математикт илүү гүнзгий орох шаардлагатай хэд хэдэн чухал асуудлаас зайлсхийсэн. Ялангуяа би дараахь зүйлийн талаар юу ч хэлэхгүй байна.
- Рид-Соломон кодын тэгшитгэлийн систем нь үл мэдэгдэх (м-ээс ихгүй үл мэдэгдэх) хослолын (өвөрмөц) шийдэлтэй байх ёстой. Энэ шаардлагад үндэслэн альфа, бета, гамма, дельта утгуудыг сонгоно.
- Тэгшитгэлийн системийг автоматаар (ямар блок ашиглах боломжгүй байгаагаас хамаарч) байгуулж, шийдвэрлэх боломжтой байх ёстой.
- Бид Galois талбарыг бий болгох хэрэгтэй: өгөгдсөн үгийн хэмжээний хувьд дурын хоёр элементийн аль ч үйлдлийн үр дүнг (+, -, *, /) олох боломжтой.
Өгүүллийн төгсгөлд эдгээр чухал асуудлын талаархи уран зохиолын ишлэлүүд байна.
n ба m-ийн сонголт
Практикт n ба m-ийг хэрхэн сонгох вэ? Практикт өгөгдөл хадгалах системд орон зайг хэмнэхийн тулд нөөцийн кодыг ашигладаг тул m-ийг үргэлж n-ээс бага сонгоно. Тэдний тодорхой үнэ цэнэ нь хэд хэдэн хүчин зүйлээс хамаардаг, үүнд:
- Мэдээллийн хадгалалтын найдвартай байдал. m том байх тусам дискний эвдрэлийг даван туулах боломжтой, өөрөөр хэлбэл найдвартай байдал өндөр байх болно.
- Илүүдэл хадгалах. m/n харьцаа өндөр байх тусам хадгалалтын илүүдэл нь өндөр байх бөгөөд систем нь илүү үнэтэй байх болно.
- Хүсэлтийг боловсруулах хугацаа. n + m нийлбэр их байх тусам хүсэлтэд хариу өгөх хугацаа урт байх болно. Мэдээллийг (сэргээх явцад) уншихад n өөр диск дээр хадгалагдсан n блокыг унших шаардлагатай байдаг тул унших хугацааг хамгийн удаан дискээр тодорхойлно.
Нэмж дурдахад хэд хэдэн DC-д өгөгдөл хадгалах нь n ба m-ийн сонголтод нэмэлт хязгаарлалт тавьдаг: хэрэв 1 DC унтарсан бол өгөгдөл унших боломжтой хэвээр байх ёстой. Жишээлбэл, 3 DC-д өгөгдөл хадгалахдаа дараах нөхцөлийг хангасан байх ёстой: m >= n/2, эс бөгөөс 1 DC унтарсан үед өгөгдөл унших боломжгүй нөхцөл байдал үүсч болно.
3. LRC - Орон нутгийн сэргээн босголтын дүрэм
Reed-Solomon кодыг ашиглан өгөгдлийг сэргээхийн тулд та n дурын өгөгдлийн блок ашиглах хэрэгтэй. Энэ нь тархсан өгөгдөл хадгалах системүүдийн хувьд маш чухал сул тал юм, учир нь нэг эвдэрсэн диск дээрх өгөгдлийг сэргээхийн тулд та бусад ихэнхээс өгөгдлийг унших хэрэгтэй бөгөөд энэ нь диск болон сүлжээнд их хэмжээний нэмэлт ачаалал үүсгэдэг.
Хамгийн нийтлэг алдаа бол нэг дискний эвдрэл, хэт ачааллаас болж нэг блок өгөгдөлд нэвтрэх боломжгүй байдаг. Энэ (хамгийн түгээмэл) тохиолдолд өгөгдөл сэргээх илүүдэл ачааллыг ямар нэгэн байдлаар бууруулах боломжтой юу? Та дараах зүйлийг хийх боломжтой болж байна: энэ зорилгоор тусгайлан зориулсан LRC илүүдэл кодууд байдаг.
LRC (Орон нутгийн сэргээн босголтын кодууд) нь Microsoft-оос Windows Azure Storage-д ашиглах зорилгоор зохион бүтээсэн нэмэлт кодууд юм. LRC-ийн санаа нь аль болох энгийн: бүх өгөгдлийн блокуудыг хоёр (эсвэл түүнээс дээш) бүлэгт хувааж, бүлэг тус бүрийн хувьд илүүдэл кодын блокуудын хэсгийг тусад нь уншина уу. Дараа нь зарим нэмэлт кодын блокуудыг бүх өгөгдлийн блокуудыг (LRC-д тэдгээрийг глобал нөөцийн код гэж нэрлэдэг), заримыг нь хоёр бүлгийн өгөгдлийн блокуудын аль нэгийг (тэдгээрийг орон нутгийн нөөцийн код гэж нэрлэдэг) ашиглан тоолох болно.
LRC-ийг гурван тоогоор тэмдэглэнэ: nrl, энд n нь өгөгдлийн блокуудын тоо, r нь дэлхийн нөөцийн кодын блокуудын тоо, l нь орон нутгийн илүүдэл кодын блокуудын тоо юм. Нэг өгөгдлийн блок боломжгүй үед өгөгдлийг уншихын тулд та зөвхөн n/l блокуудыг унших хэрэгтэй - энэ нь Рид-Соломон кодтой харьцуулахад л дахин бага юм.
Жишээлбэл, LRC 6-2-2 схемийг авч үзье. X1–X6 — 6 өгөгдлийн блок, P1, P2 — 2 глобал нөөцийн блок, P3, P4 — 2 орон нутгийн илүүдэл блок.
Илүүдэл кодын блок P1, P2 нь бүх өгөгдлийн блокуудыг ашиглан тоологддог. Илүүдэл кодын блок P3 - X1-X3 өгөгдлийн блокуудыг ашиглан, P4 нэмэлт кодын блок - X4-X6 өгөгдлийн блокуудыг ашиглан.
Үлдсэнийг нь Рид-Соломон кодтой адилтгах замаар LRC-д хийдэг. Илүүдэл кодын блокуудын үгсийг тоолох тэгшитгэл нь:
Альфа, бета, гамма, дельта тоонуудыг сонгохын тулд өгөгдлийг сэргээх боломжийг баталгаажуулахын тулд хэд хэдэн нөхцлийг хангасан байх ёстой (өөрөөр хэлбэл тэгшитгэлийн системийг шийдэх). Та тэдгээрийн талаар илүү ихийг уншиж болно .
Мөн практикт XOR үйлдлийг орон нутгийн нөөцийн P3, P4 кодыг тооцоолоход ашигладаг.
LRC-ийн тэгшитгэлийн системээс хэд хэдэн дүгнэлт гарч байна.
- Аливаа 1 өгөгдлийн блокийг сэргээхийн тулд n/l блокуудыг уншихад хангалттай (бидний жишээнд n/2).
- Хэрэв r + l блокууд байхгүй бөгөөд бүх блокууд нэг бүлэгт багтсан бол өгөгдлийг сэргээх боломжгүй болно. Үүнийг жишээгээр тайлбарлахад хялбар байдаг. X1–X3 ба P3 блокуудыг ашиглах боломжгүй байг: эдгээр нь нэг бүлгийн r + l блокууд бөгөөд манай тохиолдолд 4 байна. Дараа нь шийдвэрлэх боломжгүй 3 үл мэдэгдэх 4 тэгшитгэлийн системтэй болно.
- r + l блок ашиглах боломжгүй бусад бүх тохиолдолд (бүлэг бүрээс дор хаяж нэг блок байгаа тохиолдолд) LRC дахь өгөгдлийг сэргээх боломжтой.
Ийнхүү LRC нь ганц алдаа гарсны дараа өгөгдлийг сэргээхдээ Рид-Соломон кодуудаас давсан байна. Рид-Соломон кодуудад нэг блок өгөгдлийг сэргээхийн тулд та n блок ашиглах хэрэгтэй, LRC-д нэг блок өгөгдлийг сэргээхийн тулд n/l блок ашиглахад хангалттай (манай жишээнд n/2). Нөгөөтэйгүүр, LRC нь зөвшөөрөгдөх хамгийн их алдааны тоогоор Reed-Solomon кодуудаас доогуур байдаг. Дээрх жишээнүүдэд Reed-Solomon кодууд нь дурын 4 алдааны өгөгдлийг сэргээх боломжтой бөгөөд LRC-д өгөгдлийг сэргээх боломжгүй үед 2 алдааны 4 хослол байдаг.
Илүү чухал зүйл бол тухайн нөхцөл байдлаас шалтгаална, гэхдээ ихэнхдээ LRC-ийн өгсөн илүүдэл ачааллын хэмнэлт нь бага зэрэг найдвартай хадгалалтаас давж гардаг.
4. Бусад илүүдэл кодууд
Рид-Соломон болон LRC кодуудаас гадна өөр олон нэмэлт кодууд байдаг. Өөр өөр илүүдэл кодууд өөр өөр математик ашигладаг. Энд зарим нэмэлт кодууд байна:
- XOR оператор ашиглан нөөцийн код. XOR үйлдлийг n өгөгдлийн блок дээр хийж, 1 блок илүүдэл код, өөрөөр хэлбэл n+1 схем (n өгөгдлийн блок, 1 нөөц код) авна. -д ашигласан , энд өгөгдлийн блокууд болон илүүдэл кодууд нь массивын бүх дискэнд циклээр бичигддэг.
- XOR үйлдэл дээр суурилсан тэгш сондгой алгоритм. Илүүдэл кодуудын 2 блок, өөрөөр хэлбэл n+2 схемийг бүтээх боломжийг танд олгоно.
- XOR үйлдэл дээр суурилсан STAR алгоритм. 3 блок илүүдэл код, өөрөөр хэлбэл n+3 схемийг бүтээх боломжийг танд олгоно.
- Пирамид кодууд нь Майкрософтоос гаргасан өөр нэг нэмэлт код юм.
5. Yandex-д ашиглах
Yandex-ийн дэд бүтцийн хэд хэдэн төслүүд найдвартай өгөгдөл хадгалахын тулд нөөц кодыг ашигладаг. Энд зарим жишээ байна:
- Өгүүллийн эхэнд миний бичсэн MDS дотоод объектын хадгалалт.
- — Yandex-ийн MapReduce систем.
- (Yandex DataBase) - newSQL тараагдсан мэдээллийн сан.
MDS нь LRC илүүдэл код, 8-2-2 схемийг ашигладаг. Илүүдэл код бүхий өгөгдлийг 12 өөр DC-ийн өөр өөр серверүүд дэх 3 өөр дискэнд бичдэг: DC тус бүрт 4 сервер. Энэ талаар дэлгэрэнгүй уншина уу .
YT нь хамгийн түрүүнд хэрэгжүүлсэн Reed-Solomon код (Схем 6-3) болон LRC-ийн нөөцийн кодыг (Схем 12-2-2) хоёуланг нь ашигладаг бөгөөд LRC нь хадгалах хамгийн тохиромжтой арга юм.
YDB нь тэгш сондгойд суурилсан илүүдэл кодыг ашигладаг (Зураг 4-2). YDB дахь илүүдэл кодын талаар аль хэдийн .
Өөр өөр илүүдэл кодын схемийг ашиглах нь системд тавигдах өөр өөр шаардлагаас үүдэлтэй. Жишээлбэл, MDS-д LRC ашиглан хадгалсан өгөгдлийг 3 DC-д нэг дор байрлуулдаг. Аль нэг DC-ийн 1 нь амжилтгүй болсон тохиолдолд өгөгдөл унших боломжтой хэвээр байх нь бидний хувьд чухал тул блокуудыг DC-д тараах ёстой бөгөөд хэрэв DC боломжгүй бол нэвтрэх боломжгүй блокуудын тоо зөвшөөрөгдөх хэмжээнээс хэтрэхгүй байх ёстой. 8-2-2 схемд та DC тус бүрт 4 блок байрлуулж болно, дараа нь ямар ч DC унтрах үед 4 блок боломжгүй болж, өгөгдлийг унших боломжтой болно. Бид үүнийг 3 DC-д байрлуулахдаа ямар ч схемийг сонгохоос үл хамааран ямар ч тохиолдолд (r + l) / n >= 0,5 байх ёстой, өөрөөр хэлбэл хадгалах сангийн илүүдэл дор хаяж 50% байх болно.
YT-д байдал өөр байна: YT кластер бүр бүхэлдээ 1 DC-д байрладаг (өөр өөр DC-д өөр өөр кластерууд), тиймээс тэнд ийм хязгаарлалт байхгүй. 12-2-2 схем нь 33% нөөцийг хангадаг, өөрөөр хэлбэл өгөгдөл хадгалах нь хямд бөгөөд MDS схемийн нэгэн адил 4 хүртэлх дискний тасалдлыг даван туулах чадвартай.
Өгөгдөл хадгалах, боловсруулах системд нэмэлт кодыг ашиглах өөр олон боломжууд байдаг: өгөгдлийг сэргээх нюансууд, хүсэлтийг гүйцэтгэх хугацаанд сэргээх нөлөө, өгөгдөл бичих онцлог гэх мэт. Би эдгээр болон бусад онцлогуудын талаар тусад нь ярих болно. Хэрэв сэдэв нь сонирхолтой байх юм бол практикт илүүдэл кодыг ашиглах тухай.
6. Холбоос
- Рид-Соломон код болон Галуагийн талбайн тухай цуврал нийтлэлүүд:
Тэд математикийг хүртээмжтэй хэлээр гүнзгийрүүлэн хардаг. - Майкрософтоос LRC-ийн талаарх нийтлэл:
2-р бүлэгт онолыг товч тайлбарлаж, дараа нь практик дээр ГХХ-ны туршлагыг хэлэлцэнэ. - Тэгш сондгой схем:
- STAR схем:
- Пирамид кодууд:
- MDS дахь илүүдэл кодууд:
- YT дахь илүүдэл кодууд:
- YDB дахь илүүдэл кодууд:
Эх сурвалж: www.habr.com