4 ms·
On the one hand, this is a great "brute force" method to learn how one implementation of RAID6 could happen. This blogpost achieves understanding of error-corre
by dragontamer 6y ago
On the one hand, this is a great "brute force" method to learn how one implementation of RAID6 could happen. This blogpost achieves understanding of error-correction in the 2-parity case through brute force alone, and that's actually quite commendable.
On the other hand, its a very, very bad way to learn Reed Solomon codes. Reed Solomon codes "in general" are a concept that's broader than just 2-parity symbols... and also broader than just "protection vs erasures". Reed Solomon is designed to correct errors as well (a far "harder" computation than simply an erasure).
I've fortunately found a good "ELI5" version of Reed Solomon: https://www.youtube.com/watch?v=xE4jEKx9fTM https://www.youtube.com/watch?v=xE4jEKx9fTM
That's a very non-technical talk, but that talk gives the full concepts of "Polynomial in Finite Field" that Reed Solomon codes are based off of.
For a proper computer-based Reed Solomon code, you choose the GF(2^8) extension field for 8-bit symbols (Pararchive uses 2^16 for 16-bit symbols). Extension fields are extremely complicated to understand however, this will take a few days of Abstract Algebra study to understand how extension fields work.
But once you know how a finite extension field works, you then extend a polynomial into the extension field, and bam, you have Reed Solomon codes.
That is: a Quadratic equation can protect 3-data. All quadratic equations are ax^2 + bx + c, so any 3-points define a quadratic equation. Generate (x,y) coordinates on a graph as (0, data0), (1, data1), (2, data2).
Then, solve for a quadratic equation f(x) = ax^2 + bx + c.
Then, to generate parity, f(3) is your first parity symbol, f(4) is your next parity symbol, f(5) is the parity symbol after that. Etc. etc. Note in a 8-bit finite field, you can only go up to f(255) before "looping back" to f(0).
From there: 2-check symbols will protect against either 2-erasures or 1-error. So Quadratic Equation with 4-check symbols (aka: 4 "other points" of the quadratic equation passed with the data) can protect against 4 erasures... or 2-errors, or 2-erasures + 1 error.
- klodolph 6y agoNote that the size of the field only has to be as large as the size of the redundancy set (data + code). So if you are striping across 16 or fewer disks, you can use GF(2^4), but if you are striping across 17 disks you can’t use GF(2^4). Well, if I remember the math correctly.
- dragontamer 6y ago> Well, if I remember the math correctly. You're off by one. There's a "minus 1" because Reed Solomon is over the cyclical multiplication group, not over the cyclical additive group. (TL;DR: The number 0 cannot participate in... some portion of the formulation of the polynomials) GF(2^3) is over blocksize of 7. GF(2^4) is over blocksize of 15. GF(2^8) is over 255. --------- GF(2^8) is the smallest size in practice, because most people's data is organized into 8-bits-at-a-time today. (aka: a byte). But you're mostly right (once you account for the off-by-one error): there's a limit to 255 elements per block in GF(2^8) Reed Solomon. But GF(2^3) or GF(2^4) are great for hand-exercises, the smaller size makes it far easier to compute calculations by hand and allow for the human to gain understanding. (aka: Octal 2^3 numbers or Hexadecimal 2^4 numbers). GF(2^2) is technically possible... but all the matrix math is over 1x1 matricies and not really a good opportunity to learn from. GF(2^1) is literally impossible for Reed Solomon to work in. So GF(2^3) is the smallest practical hand-exercise size (RS(7, 5) over GF(2^3) has a 5x7 generator matrix and a 7x2 check matrix. Small enough to do by hand though a bit tedious). If you actually wanted to "split symbols up" so that you better detect bit-errors, then LDPC or Turbocodes are straight up superior over Reed Solomon for "small symbol sets". Reed Solomon is best used over "large symbols" (aka: 2^8 or larger). ---------- Any Reed Solomon code can be punctured (aka: fewer parity symbols), or shortened (aka: fewer data symbols) by simply setting locations of the Reed-Solomon generator and/or check matrix to 0. As such, if you organize "smaller sets" into 2^8 (aka: 8-bit bytes), its just very natural to use a punctured + shortened Reed Solomon code instead of trying to get a 2^4 Reed Solomon code to work.
- klodolph 6y agoYou’re right! Off by one. > GF(2^8) is the smallest size in practice, because most people's data is organized into 8-bits-at-a-time today. IIRC GF(2^4) is actually used in practice. Long story short, the CPU overhead of rebuilding data is a real concern.
- dragontamer 6y ago> IIRC GF(2^4) is actually used in practice. Long story short, the CPU overhead of rebuilding data is a real concern. Interesting. I don't know about how these systems are implemented in practice, but I'd be surprised if GF(2^8) was "too big". GF(2^8) was small enough that it was implemented in 1977 on the Voyager probe project. Yeah, it took a literal supercomputer to decode that RS-code in the 1980s, but modern computers are basically as fast as 1980s-era supercomputers. Modern papers are talking about GF(2^32) to GF(2^128) these days. (https://www.ccis.northeastern.edu/home/alina/papers/tos-gf.pdf https://www.ccis.northeastern.edu/home/alina/papers/tos-gf.p...). Most implementations don't need anything near that size, so GF(2^8) is sufficient. --------- I mean, I've done GF(2^4) RS codes by hand. That's a very, very, very small system, human calculable with just pen and paper. So you're right that its far easier to calculate. I'm just kind of surprised that anyone would bother with a computer RS code of that miniscule size. Ex: RS(15, 9) is a 9x15 generator matrix and a 6x15 check matrix over GF(2^4). Its on the large-side of hand-doable calculations, but absolutely doable by pen-and-paper (I recommend graph paper). Every symbol is a 2^4 hexadecimal symbol, so a single hand-written character (0123456789ABCDEF) is stored on a single cell in graph paper. ------- Are you sure those systems are working in GF(16) fields? Not GF(2^16) AKA gf(65536) fields? GF(2^16) is more of the size I'd expect a computer to do, more so than GF(2^4).