2022-11-06 The essence of Reed-Solomon coding

Let’s say we want to store some data on multiple drives, so that we can recover from drive failures.

One obvious (and valid!) first attempt is to just store everything multiple times – usually called “mirroring”. The most common form of mirroring is to store things twice: if one drive fails, the data is still in the other.1

Reed-Solomon coding gives us much more flexibility, allowing us to store our data over n = k + t drives, so that any t drives can fail while still not losing data.2

For instance, with \mathrm{RS}(10, 4) we can store data over 14 drives, and any 4 drives can fail at once, without incurring data loss. The data is split over 10 equal blocks, and then 4 additional blocks (“parity” blocks) are generated in a such a way that any 4 blocks can be recovered from the other 10.34

The main idea behind Reed-Solomon is easy to visualize. We’ll focus on the task of durably storing k numbers y_1, ..., y_k. We’ll plot them as (1, y_1), ..., (k, y_k). For instance, with k = 4, we might have:

  1. This is often known as RAID1.↩︎

  2. This post presents a specific way to perform Reed-Solomon coding, using Lagrange interpolation. See the Wikipedia article for more information.↩︎

  3. RAID4 and RAID6 fit in this framework as \mathrm{RS}(3,1) and \mathrm{RS}(4,2) respectively.↩︎

  4. The “parity” terminology comes from other error detecting or correcting codes which use parity bits.↩︎

For any distinct k points, there’s a unique polynomial of degree d < k passing through them.5 This fact should not be too surprising, and is apparent when k = 2: given two distinct points, there’s only one line passing through them.

Here’s the unique third-degree polynomial passing through our four points:

  1. A polynomial of degree d is a something of the form

    a_0 + a_1 x + a_2 x^2 + ... + a_d x^d↩︎

Armed with this fact, we can pick an additional t points on the same polynomial. Again, with k = 4 and t = 2, we would have:

Sampled points are in gold. Since the interpolating polynomial is unique given any k points it passes through, we can drop any t points, and we’ll still be able to recover the polynomial. Once we’ve done that, we can just resample it to recover the numbers we’re storing.

To recap, our procedure to durably store k numbers is as follows:

At this point, you already understand a key idea powering Reed-Solomon coding.

The other key idea allows us to store bits, rather than numbers. I won’t properly explain it here, but the gist of it is to use finite fields of order 2^{\mathrm{bits}} as our number type.6

Such finite fields are numeric types working differently from the usual integers modulo 2^{\mathrm{bits}} that we’re used to program with, but still easy to implement in hardware, and importantly numbers for which the considerations in this blog post about polynomials hold.7

Once we have such a numeric type, all we need to do to durably store some blob of data is to split it in a series of 2^{\mathrm{bits}} numbers (each \mathrm{bits} wide), group them in sets of k, and then store them durably as described in this post, tuning t based on how redundant we want to be.

The final trick worth mentioning is that this kind of Reed-Solomon encoding can be implemented efficiently given that we have fixed the x coordinates, no matter what numbers we want to store. Or in other words, the definition for \ell_j which we use to generate the unique polynomial only depends on the x coordinates, which allows us to do the heavy lifting once for any k numbers we want to store.

  1. Head over to Peter Cawley’s blog for details on how the finite field machinery works on modern CPUs.↩︎

  2. As the name suggests, finite fields are fields, which is handy since generating polynomials passing through a set of points involves divisions.

    Integers modulo 2^\mathrm{bits}, which is what we’re used to program with, are not closed under division, which jams the maths required to perform the operations we described.↩︎

[email protected] · twitter · mastodon · source