Artıqlıq belə görünür
Məlumatların saxlanmasının etibarlılığını artırmaq üçün ehtiyat kodları* kompüter sistemlərində geniş istifadə olunur. Yandex-də onlar bir çox layihələrdə istifadə olunur. Məsələn, daxili obyekt yaddaşımızda təkrarlama əvəzinə ehtiyat kodlarından istifadə etibarlılığı itirmədən milyonlarla insana qənaət edir. Lakin onların geniş istifadəsinə baxmayaraq, ehtiyat kodlarının necə işlədiyinə dair aydın təsvirlər çox nadirdir. Anlamaq istəyənlər təxminən aşağıdakılarla qarşılaşırlar (dan ):
Mənim adım Vadim, Yandex-də daxili obyekt saxlama MDS inkişaf etdirirəm. Bu yazıda mən artıqlıq kodlarının (Reed-Solomon və LRC kodları) nəzəri əsaslarını sadə sözlərlə təsvir edəcəyəm. Mən sizə mürəkkəb riyaziyyat və nadir terminlər olmadan bunun necə işlədiyini söyləyəcəyəm. Sonda Yandex-də artıqlıq kodlarından istifadə nümunələri verəcəyəm.
Bir sıra riyazi təfərrüatları ətraflı nəzərdən keçirməyəcəyəm, lakin daha dərinə dalmaq istəyənlər üçün linklər təqdim edəcəyəm. Onu da qeyd edim ki, məqalə riyaziyyatçılar üçün deyil, məsələnin mahiyyətini anlamaq istəyən mühəndislər üçün nəzərdə tutulduğundan bəzi riyazi təriflər sərt olmaya bilər.
* İngilis dilli ədəbiyyatda artıqlıq kodları çox vaxt silmə kodları adlanır.
1. Artıqlıq kodlarının mahiyyəti
Bütün ehtiyat kodlarının mahiyyəti son dərəcə sadədir: səhvlər baş verdikdə (disk nasazlığı, məlumat ötürülməsi xətaları və s.) itirilməməsi üçün məlumatları saxlamaq (və ya ötürmək).
Əksər* ehtiyat kodlarında verilənlər n məlumat blokuna bölünür, bunun üçün m artıqlıq kodu bloku hesablanır və nəticədə cəmi n + m blok alınır. Artıqlıq kodları elə qurulmuşdur ki, n məlumat bloku yalnız n + m blokdan istifadə etməklə bərpa oluna bilər. Bundan sonra, yalnız blok artıqlıq kodlarını, yəni məlumatların bloklara bölündüyü kodları nəzərdən keçirəcəyik.
Bütün n məlumat blokunu bərpa etmək üçün ən azı n ədəd n + m bloka sahib olmalısınız, çünki yalnız n-1 bloka malik olmaqla n blok əldə edə bilməzsiniz (bu halda siz 1 blok “nazikdən” götürməli olacaqsınız. hava"). Bütün məlumatları bərpa etmək üçün n + m blokdan ibarət n təsadüfi blok kifayətdirmi? Bu, ehtiyat kodlarının növündən asılıdır, məsələn, Reed-Solomon kodları ixtiyari n bloklardan istifadə edərək bütün məlumatları bərpa etməyə imkan verir, lakin LRC ehtiyat kodları həmişə olmur.
Məlumat saxlama
Məlumatların saxlanması sistemlərində, bir qayda olaraq, verilənlər bloklarının və ehtiyat kod bloklarının hər biri ayrıca diskə yazılır. Sonra, ixtiyari disk uğursuz olarsa, orijinal məlumatlar hələ də bərpa edilə və oxuna bilər. Bir neçə disk eyni anda uğursuz olsa belə, məlumatlar bərpa edilə bilər.
Məlumat ötürülməsi
Etibarlılıq kodları etibarsız şəbəkə üzərindən etibarlı şəkildə məlumat ötürmək üçün istifadə edilə bilər. Ötürülmüş məlumatlar bloklara bölünür və onlar üçün artıqlıq kodları hesablanır. Həm məlumat blokları, həm də ehtiyat kod blokları şəbəkə üzərindən ötürülür. Əgər ixtiyari bloklarda (müəyyən sayda bloka qədər) xətalar baş verərsə, məlumatlar yenə də şəbəkə üzərindən səhvsiz ötürülə bilər. Məsələn, Reed-Solomon kodları optik rabitə xətləri və peyk rabitələrində məlumat ötürmək üçün istifadə olunur.
* Ethernet şəbəkələrində məlumatların ötürülməsi üçün geniş istifadə olunan Hamming kodları və CRC kodları kimi verilənlərin bloklara bölünmədiyi ehtiyat kodları da mövcuddur. Bunlar səhvləri düzəltmək üçün kodlaşdırma üçün kodlardır, onlar səhvləri aşkar etmək üçün nəzərdə tutulmuşdur, onları düzəltmək üçün deyil (Hamming kodu həmçinin səhvləri qismən korreksiya etməyə imkan verir).
2. Reed-Solomon kodları
Reed-Solomon kodları 1960-cı illərdə icad edilmiş və ilk dəfə 1980-ci illərdə kompakt disklərin kütləvi istehsalı üçün geniş şəkildə istifadə edilən ən çox istifadə edilən ehtiyat kodlarından biridir.
Reed-Solomon kodlarını başa düşmək üçün iki əsas sual var: 1) ehtiyat kodları bloklarının necə yaradılması; 2) ehtiyat kod bloklarından istifadə edərək məlumatları necə bərpa etmək olar. Gəlin onlara cavab tapaq.
Sadəlik üçün daha sonra n=6 və m=4 olduğunu fərz edəcəyik. Digər sxemlər analoji olaraq nəzərdən keçirilir.
Artıq kod bloklarını necə yaratmaq olar
Artıqlıq kodlarının hər bir bloku digərlərindən asılı olmayaraq hesablanır. Hər bloku saymaq üçün bütün n məlumat blokundan istifadə olunur. Aşağıdakı diaqramda X1-X6 məlumat blokları, P1-P4 ehtiyat kod bloklarıdır.
Bütün məlumat blokları eyni ölçüdə olmalıdır və düzləşdirmə üçün sıfır bit istifadə edilə bilər. Yaranan ehtiyat kod blokları məlumat blokları ilə eyni ölçüdə olacaq. Bütün verilənlər blokları sözlərə bölünür (məsələn, 16 bit). Deyək ki, verilənlər bloklarını k sözünə böldük. Onda artıqlıq kodlarının bütün blokları da k sözünə bölünəcək.
Hər bir ehtiyat blokunun i-ci sözünü saymaq üçün bütün məlumat bloklarının i-ci sözləri istifadə olunacaq. Onlar aşağıdakı düsturla hesablanacaq:
Burada x dəyərləri məlumat bloklarının sözləridir, p artıqlıq kod bloklarının sözləridir, bütün alfa, beta, qamma və delta xüsusi seçilmiş və bütün i üçün eyni olan nömrələrdir. Dərhal demək lazımdır ki, bütün bu dəyərlər adi rəqəmlər deyil, Qalua sahəsinin elementləridir; +, -, *, / əməliyyatları hamımıza tanış olan əməliyyatlar deyil, Qalua elementləri üzərində tətbiq olunan xüsusi əməliyyatlardır. sahə.
Qalua sahələri nə üçün lazımdır?
Görünür ki, hər şey sadədir: biz məlumatları bloklara, blokları sözlərə bölürük, məlumat bloklarının sözlərindən istifadə edərək, artıqlıq kod bloklarının sözlərini sayırıq - ehtiyat kod bloklarını alırıq. Ümumiyyətlə, bu necə işləyir, amma şeytan təfərrüatlardadır:
- Yuxarıda qeyd edildiyi kimi, sözün ölçüsü sabitdir, nümunəmizdə 16 bit. Reed-Solomon kodları üçün yuxarıdakı düsturlar elədir ki, adi tam ədədlərdən istifadə edərkən p-nin hesablanmasının nəticəsi etibarlı ölçülü sözdən istifadə etməklə təqdim edilə bilməz.
- Məlumatları bərpa edərkən yuxarıdakı düsturlar məlumatları bərpa etmək üçün həll edilməli olan tənliklər sistemi kimi nəzərdən keçiriləcəkdir. Həll prosesi zamanı tam ədədləri bir-birinə bölmək lazım gələ bilər ki, nəticədə kompüterin yaddaşında dəqiq şəkildə təmsil oluna bilməyən real ədəd yaranır.
Bu problemlər Reed-Solomon kodları üçün tam ədədlərin istifadəsinə mane olur. Problemin həlli orijinaldır, onu aşağıdakı kimi təsvir etmək olar: tələb olunan uzunluqdakı sözlərdən (məsələn, 16 bit) və üzərində olan bütün əməliyyatların yerinə yetirilməsinin nəticəsini (əlavə) istifadə edərək təmsil oluna bilən xüsusi nömrələrlə tanış olaq. , çıxma, vurma, bölmə) də tələb olunan uzunluqdakı sözlərdən istifadə etməklə kompüter yaddaşında təqdim olunacaq.
Bu cür "xüsusi" nömrələr riyaziyyat tərəfindən uzun müddət öyrənilmişdir, onlara sahələr deyilir. Sahə onlar üçün müəyyən edilmiş toplama, çıxma, vurma və bölmə əməliyyatları olan elementlər toplusudur.
Galois* sahələri sahənin istənilən iki elementi üçün hər bir əməliyyatın unikal nəticəsi (+, -, *, /) olan sahələrdir. Qalua sahələri 2: 2, 4, 8, 16 və s. dərəcələri olan ədədlər üçün tikilə bilər (əslində hər hansı bir sadə p ədədinin səlahiyyətləri, lakin praktikada bizi yalnız 2-nin səlahiyyətləri maraqlandırır). Məsələn, 16 bitlik sözlər üçün bu, 65 elementdən ibarət bir sahədir, hər bir cüt üçün hər hansı bir əməliyyatın nəticəsini tapa bilərsiniz (+, -, *, /). Yuxarıdakı tənliklərdən x, p, alfa, beta, qamma, delta dəyərləri hesablamalar üçün Galois sahəsinin elementləri hesab ediləcəkdir.
Beləliklə, uyğun bir kompüter proqramı yazmaqla artıqlıq kodları bloklarını qura biləcəyimiz tənliklər sistemimiz var. Eyni tənliklər sistemindən istifadə edərək, məlumatların bərpasını həyata keçirə bilərsiniz.
* Bu, ciddi tərif deyil, daha çox təsvirdir.
Məlumatları necə bərpa etmək olar
Bəzi n + m blokları əskik olduqda bərpa tələb olunur. Bunlar həm məlumat blokları, həm də ehtiyat kod blokları ola bilər. Məlumat bloklarının və/və ya ehtiyat kod bloklarının olmaması yuxarıdakı tənliklərdə müvafiq x və/və ya p dəyişənlərinin naməlum olması deməkdir.
Reed-Solomon kodları üçün tənliklərə bütün alfa, beta, qamma, delta dəyərlərinin sabit olduğu, mövcud bloklara uyğun gələn bütün x və p-nin məlum dəyişənlər, qalan x və p-nin olduğu tənliklər sistemi kimi baxmaq olar. bilinmir.
Məsələn, 1, 2, 3 məlumat blokları və artıqlıq kodu bloku 2 əlçatmaz olsun, onda i-ci sözlər qrupu üçün aşağıdakı tənliklər sistemi olacaq (naməlumlar qırmızı ilə işarələnmişdir):
Bizdə 4 naməlum olan 4 tənlik sistemimiz var, yəni biz onu həll edə və məlumatları bərpa edə bilərik!
Bu tənliklər sistemindən Reed-Solomon kodları (n məlumat bloku, m ehtiyat kodu bloku) üçün məlumatların bərpası ilə bağlı bir sıra nəticələr əldə edilir:
- Hər hansı m və ya daha az blok itirildikdə məlumat bərpa edilə bilər. Əgər m+1 və ya daha çox blok itirilərsə, verilənləri bərpa etmək mümkün deyil: m+1 naməlum olan m tənliklər sistemini həll etmək mümkün deyil.
- Hətta bir məlumat blokunu bərpa etmək üçün siz qalan bloklardan hər hansı n istifadə etməlisiniz və artıqlıq kodlarından hər hansı birini istifadə edə bilərsiniz.
Bildiyiniz başqa nədir?
Yuxarıdakı təsvirdə mən riyaziyyata daha dərindən girməyi tələb edən bir sıra vacib məsələlərdən qaçıram. Xüsusilə, aşağıdakılar haqqında heç nə demirəm:
- Reed-Solomon kodları üçün tənliklər sistemi naməlumların hər hansı birləşməsi üçün (unikal) həllə malik olmalıdır (m-dən çox olmayan). Bu tələb əsasında alfa, beta, qamma və delta dəyərləri seçilir.
- Tənliklər sistemi avtomatik olaraq qurulmalı (hansı blokların mövcud olmadığından asılı olaraq) və həll edilməlidir.
- Biz Galois sahəsi qurmalıyıq: verilmiş söz ölçüsü üçün istənilən iki element üçün hər hansı əməliyyatın nəticəsini (+, -, *, /) tapa bilək.
Məqalənin sonunda bu mühüm məsələlərə dair ədəbiyyata istinadlar verilmişdir.
n və m seçimi
Praktikada n və m-ni necə seçmək olar? Təcrübədə məlumatların saxlanması sistemlərində yer qənaət etmək üçün ehtiyat kodlarından istifadə olunur, ona görə də m həmişə n-dən az seçilir. Onların xüsusi dəyərləri bir sıra amillərdən asılıdır, o cümlədən:
- Məlumatların saxlanmasının etibarlılığı. Daha böyük m, xilas ola biləcək disk uğursuzluqlarının sayı, yəni etibarlılıq bir o qədər yüksəkdir.
- Lazımsız saxlama. m/n nisbəti nə qədər yüksək olsa, saxlama ehtiyatı bir o qədər yüksək olacaq və sistem daha bahalı olacaq.
- Sorğunun emal müddəti. n + m məbləği nə qədər böyükdürsə, sorğulara cavab müddəti bir o qədər uzun olacaq. Məlumatların oxunması (bərpa zamanı) n müxtəlif diskdə saxlanılan n blokun oxunmasını tələb etdiyindən, oxuma vaxtı ən yavaş disk tərəfindən müəyyən ediləcək.
Bundan əlavə, məlumatların bir neçə DC-də saxlanması n və m seçiminə əlavə məhdudiyyətlər qoyur: əgər 1 DC söndürülürsə, verilənlər hələ də oxumaq üçün mövcud olmalıdır. Məsələn, məlumatları 3 DC-də saxlayarkən aşağıdakı şərt yerinə yetirilməlidir: m >= n/2, əks halda 1 DC söndürüldükdə verilənlərin oxunması üçün əlçatan olmayan vəziyyət yarana bilər.
3. LRC - Yerli Yenidənqurma Kodları
Reed-Solomon kodlarından istifadə edərək məlumatları bərpa etmək üçün n ixtiyari məlumat blokundan istifadə etməlisiniz. Bu, paylanmış məlumat saxlama sistemləri üçün çox əhəmiyyətli bir çatışmazlıqdır, çünki bir pozulmuş diskdə məlumatları bərpa etmək üçün disklərdə və şəbəkədə böyük bir əlavə yük yaradaraq, digərlərinin əksəriyyətindən məlumatları oxumalı olacaqsınız.
Ən çox yayılmış səhvlər, bir diskin nasazlığı və ya həddindən artıq yüklənməsi səbəbindən bir məlumat blokunun əlçatmazlığıdır. Bu (ən çox yayılmış) vəziyyətdə məlumatların bərpası üçün artıq yükü bir şəkildə azaltmaq mümkündürmü? Belə çıxır ki, edə bilərsiniz: xüsusi olaraq bu məqsəd üçün LRC ehtiyat kodları var.
LRC (Yerli Yenidənqurma Kodları) Windows Azure Storage-də istifadə üçün Microsoft tərəfindən icad edilmiş ehtiyat kodlarıdır. LRC ideyası mümkün qədər sadədir: bütün məlumat bloklarını iki (və ya daha çox) qrupa bölün və hər bir qrup üçün əlavə kod bloklarının bir hissəsini ayrıca oxuyun. Sonra bəzi ehtiyat kod blokları bütün məlumat bloklarından istifadə etməklə (LRC-də onlar qlobal ehtiyat kodları adlanır), bəziləri isə iki qrup məlumat blokundan birini istifadə etməklə (bunlara yerli ehtiyat kodları deyilir) hesablanacaq.
LRC üç rəqəmlə işarələnir: nrl, burada n məlumat bloklarının sayı, r qlobal ehtiyat kod bloklarının sayı, l yerli ehtiyat kod bloklarının sayıdır. Bir məlumat bloku mövcud olmadıqda məlumatları oxumaq üçün yalnız n/l bloklarını oxumaq lazımdır - bu, Reed-Solomon kodlarından XNUMX dəfə azdır.
Məsələn, LRC 6-2-2 sxemini nəzərdən keçirək. X1–X6 — 6 məlumat bloku, P1, P2 — 2 qlobal ehtiyat bloku, P3, P4 — 2 yerli ehtiyat bloku.
P1, P2 ehtiyat kod blokları bütün məlumat bloklarından istifadə etməklə hesablanır. Əlavə kod bloku P3 - X1-X3 məlumat bloklarından istifadə etməklə, P4 ehtiyat kodu bloku - X4-X6 məlumat bloklarından istifadə etməklə.
Qalanları LRC-də Reed-Solomon kodlarına bənzətməklə həyata keçirilir. Artıqlıq kod bloklarının sözlərini hesablamaq üçün tənliklər aşağıdakı kimi olacaq:
Alfa, beta, qamma, delta nömrələrini seçmək üçün məlumatların bərpası (yəni tənlik sisteminin həlli) imkanlarını təmin etmək üçün bir sıra şərtlər yerinə yetirilməlidir. Onlar haqqında ətraflı oxuya bilərsiniz .
Həmçinin praktikada XOR əməliyyatı P3, P4 yerli ehtiyat kodlarını hesablamaq üçün istifadə olunur.
LRC üçün tənliklər sistemindən bir sıra nəticələr çıxır:
- Hər hansı 1 məlumat blokunu bərpa etmək üçün n/l bloklarını oxumaq kifayətdir (nümunəmizdə n/2).
- r + l blokları mövcud deyilsə və bütün bloklar bir qrupa daxildirsə, məlumat bərpa edilə bilməz. Bunu bir nümunə ilə izah etmək asandır. X1–X3 və P3 blokları əlçatmaz olsun: bunlar eyni qrupdan olan r + l bloklarıdır, bizim vəziyyətimizdə 4 blokdur. Onda həlli mümkün olmayan 3 naməlumlu 4 tənlik sistemimiz var.
- r + l bloklarının mövcud olmadığı bütün digər hallarda (hər qrupdan ən azı bir blok mövcud olduqda) LRC-dəki məlumatlar bərpa edilə bilər.
Beləliklə, LRC tək xətalardan sonra məlumatların bərpasında Reed-Solomon kodlarını üstələyir. Reed-Solomon kodlarında hətta bir blok məlumatı bərpa etmək üçün n blokdan istifadə etmək lazımdır, LRC-də isə bir blok məlumatı bərpa etmək üçün n/l bloklarından istifadə etmək kifayətdir (nümunəmizdə n/2). Digər tərəfdən, LRC icazə verilən səhvlərin maksimum sayı baxımından Reed-Solomon kodlarından daha aşağıdır. Yuxarıdakı nümunələrdə Reed-Solomon kodları hər hansı 4 səhv üçün məlumatları bərpa edə bilər və LRC üçün məlumat bərpa edilə bilməyəndə 2 səhvdən ibarət 4 kombinasiya mövcuddur.
Daha vacib olan, konkret vəziyyətdən asılıdır, lakin çox vaxt LRC-nin təmin etdiyi artıq yükdə qənaət bir az daha az etibarlı saxlamadan üstündür.
4. Digər ehtiyat kodları
Reed-Solomon və LRC kodlarından başqa bir çox başqa ehtiyat kodları var. Fərqli ehtiyat kodları fərqli riyaziyyatdan istifadə edir. Budur, bəzi digər ehtiyat kodları:
- XOR operatorundan istifadə edərək ehtiyat kodu. XOR əməliyyatı n verilənlər blokunda yerinə yetirilir və 1 blok artıqlıq kodu, yəni n+1 sxemi (n məlumat bloku, 1 ehtiyat kodu) alınır. -də istifadə olunub , burada məlumat blokları və ehtiyat kodları siklik olaraq massivin bütün disklərinə yazılır.
- XOR əməliyyatına əsaslanan cüt-tək alqoritm. 2 blok artıqlıq kodunu, yəni n+2 sxemini qurmağa imkan verir.
- XOR əməliyyatına əsaslanan STAR alqoritmi. 3 blok artıqlıq kodunu, yəni n+3 sxemini qurmağa imkan verir.
- Piramida kodları Microsoft-un başqa bir ehtiyat kodlarıdır.
5. Yandex-də istifadə edin
Bir sıra Yandex infrastruktur layihələri məlumatların etibarlı saxlanması üçün ehtiyat kodlarından istifadə edir. Budur bəzi nümunələr:
- Məqalənin əvvəlində yazdığım MDS daxili obyekt yaddaşı.
- — Yandex-in MapReduce sistemi.
- (Yandex DataBase) - newSQL paylanmış verilənlər bazası.
MDS LRC ehtiyat kodlarından, 8-2-2 sxemindən istifadə edir. Artıqlıq kodları olan məlumatlar 12 fərqli DC-də müxtəlif serverlərdə 3 fərqli diskə yazılır: hər DC-də 4 server. Bu barədə ətraflı oxuyun .
YT həm ilk tətbiq olunan Reed-Solomon kodlarından (Sxem 6-3), həm də LRC ehtiyat kodlarından (Sxem 12-2-2) istifadə edir, LRC isə üstünlük verilən saxlama üsuludur.
YDB cüt-tək əsaslı artıqlıq kodlarından istifadə edir (Şəkil 4-2). Artıq YDB-də artıqlıq kodları haqqında .
Müxtəlif ehtiyat kod sxemlərinin istifadəsi sistemlər üçün müxtəlif tələblərlə bağlıdır. Məsələn, MDS-də LRC-dən istifadə etməklə saxlanılan məlumatlar bir anda 3 DC-də yerləşdirilir. Hər hansı bir DC-dən 1-i uğursuz olarsa, məlumatların oxunmaq üçün əlçatan olması bizim üçün vacibdir, buna görə də bloklar DC-lər arasında paylanmalıdır ki, hər hansı bir DC mövcud deyilsə, əlçatmaz blokların sayı icazə veriləndən çox olmasın. 8-2-2 sxemində hər DC-də 4 blok yerləşdirə bilərsiniz, sonra hər hansı DC söndürüldükdə 4 blok əlçatmaz olacaq və məlumatlar oxuna bilər. Onu 3 DC-də yerləşdirərkən hansı sxemi seçsək də, istənilən halda (r + l) / n >= 0,5 olmalıdır, yəni saxlama ehtiyatı ən azı 50% olacaqdır.
YT-də vəziyyət fərqlidir: hər bir YT klasteri tamamilə 1 DC-də yerləşir (müxtəlif DC-lərdə müxtəlif klasterlər), ona görə də belə məhdudiyyət yoxdur. 12-2-2 sxemi 33% ehtiyat təmin edir, yəni məlumatların saxlanması daha ucuzdur və eyni zamanda MDS sxemi kimi 4-ə qədər eyni vaxtda disk kəsilməsinə dözə bilər.
Məlumatların saxlanması və emalı sistemlərində ehtiyat kodlarının istifadəsinin daha bir çox xüsusiyyətləri var: məlumatların bərpası nüansları, bərpanın sorğunun icra müddətinə təsiri, məlumatların qeydinin xüsusiyyətləri və s. Bu və digər xüsusiyyətlər haqqında ayrıca danışacağam. Mövzu maraqlı olarsa, praktikada artıqlıq kodlarının istifadəsi.
6. Bağlantılar
- Reed-Solomon kodları və Qalua sahələri haqqında bir sıra məqalələr:
Onlar əlçatan dildə riyaziyyata daha dərindən nəzər salırlar. - Microsoft-dan LRC haqqında məqalə:
Bölmə 2 qısaca nəzəriyyəni izah edir və sonra praktikada LRC ilə təcrübələri müzakirə edir. - Cüt tək sxem:
- STAR sxemi:
- Piramida kodları:
- MDS-də artıqlıq kodları:
- YT-də artıqlıq kodları:
- YDB-də artıqlıq kodları:
Mənbə: www.habr.com