So sieht Redundanz aus

* . . , . , , , . ( ):

, MDS. ( — LRC). , , . .

, , . , , , , .

* « » «erasure codes».

1.

: ( ) , ( , . .).

* n , m , n + m . , n , n + m . , , .

n , n n + m , n , n-1 ( 1 « »). n n + m ? , — n , LRC — .

, , . . .

. , . , . ( ), . — , , .

* , , CRC, Ethernet. , , ( ).

2. —

— — , 1960- 1980- -.

— : 1) ; 2) . .

, n=6 m=4. .

. n . X₁-X₆ — , P₁–P₄ — .

, . , . (, 16 ). , k . k .

i- i- . :

x — , p — , , , — , i. , — , , +, -, *, / — , , .

, : , — , — . , :

1. , — , 16 . — , p .
2. , , . , , .

— . , : , (, 16 ), (, , , ) .

«» , . — , , .

* — , (+, -, *, /) . , 2: 2, 4, 8, 16 . . ( p, 2). , 16 , 65 536 , (+, -, *, /). x, p, , , , .

, , , . .

* , .

, n + m . , . / , x / p.

— , , , , — , x p, , — , x p — .

, 1, 2, 3 2 , i- ( ):

4 4 , !

— (n , m ):

• m . m+1 : m m + 1 .
• n , .

, . , :

• — () ( m ). , , .
• ( , ) .
• : (+, -, *, /) .

.

n m

n m? , m n. , :

• . m, , .
• . m / n, , .
• . n + m, . ( ) n , n , .

, n m: 1 . , 3 : m >= n/2, , 1 .

3. LRC — Local Reconstruction Codes

— n . , , .

— - . - ( ) ? , : LRC.

LRC (Local Reconstruction Codes) — , Microsoft Windows Azure Storage. LRC : ( ) . ( LRC ), — ( ).

LRC : n-r-l, n — , r — , l — . n/l — l , — .

LRC 6-2-2. X₁–X₆ — 6 , P₁, P₂ — 2 , P₃, P₄ — 2 .

P₁, P₂ . P₃ — X₁–X₃, P₄ — X₄–X₆.

LRC — . :

, , , , ( ). .

P₃, P₄ XOR.

LRC :

• 1 n/l (n/2 ).
• r + l , , . . X₁–X₃ P₃: r + l , 4 . 3 4 , .
• r + l ( ) LRC .

, LRC — . — n , LRC n/l (n/2 ). , LRC — . — 4 , LRC 2 4 , .

— , , LRC, .

4.

— LRC, . . :

• XOR. XOR n , 1 , n+1 (n , 1 ). RAID 5, .
• even-odd, XOR. 2 , n+2.
• STAR, XOR. 3 , n+3.
• Pyramide codes — Microsoft.

5.

. :

• MDS, .
• YT — MapReduce- .
• YDB (Yandex DataBase) — newSQL.

MDS LRC, 8-2-2. 12 3 : 4 . .

YT — ( 6-3), , LRC ( 12-2-2), LRC — .

YDB , even-odd ( 4-2). YDB Highload.

, . , MDS , LRC, 3 . , 1 , , . 8-2-2 4 , 4 , . 3 , (r + l) / n >= 0,5, 50%.

YT : YT 1 ( ), . 12-2-2 33%, , 4 , MDS.

: , , . . , .

6.

1. — : https://habr.com/ru/company/yadro/blog/336286/
   
   https://habr.com/ru/company/yadro/blog/341506/
   
   .
2. Microsoft LRC: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   
   2 , LRC .
3. even-odd: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. STAR: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. Pyramid codes: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. MDS: https://habr.com/ru/company/yandex/blog/311806
7. YT: https://habr.com/ru/company/yandex/blog/311104/
8. YDB: https://www.youtube.com/watch?v=dCpfGJ35kK8