Códigos de redundância: em palavras simples, sobre como armazenar dados de maneira confiável e barata



É assim que a redundância se parece



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





, 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 . X1-X6 — , P1–P4 — .





, . , . (, 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. X1–X6 — 6 , P1, P2 — 2 , P3, P4 — 2 .





P1, P2 . P3 — X1–X3, P4 — X4–X6.



LRC — . :





, , , , ( ). .

P3, P4 XOR.



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 — . — 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



All Articles