Practical Reed-Solomon for Programmers (opens in new tab)

(author here) Nice! Added that to the page, very worthwhile. Thanks.

We're not using floppies anymore, and media is extremely reliable.

On the internet you can just retransmit if something went wrong, and if you're worried about the media specifically then there are media specific measures, like RAID and filesystem level checksums.

> uses cases for Reed-Solomon at the application level

Hadoop has an RS implementation inside the filesystem (called "erasure coding"), instead of storing 3 copies of the same data, it can actually instead store ~1.5 copies as (6+3) or (10+4).

Previously, I've run into this tech in satellite internet gateways, but distributed filesystems is where I've gone through the math & probabilities of failure properly.

I work on perf & the extra network hops (with 3 replicas, you read 100% of data local, when you stripe it that doesn't work) and math for the error correction are hot spots when you are trying to keep all cores busy.

Linux RAID-6: RS(10,8) Google File System II (Colossus): RS(9,6) Quantcast File System: RS(9,6) Intel & Cloudera’ HDFS-EC: RS(9,6) Yahoo Cloud Object Store: RS(11,8) Backblaze’s online backup: RS(20,17) Facebook’s f4 BLOB storage system: RS(14,10) Baidu’s Atlas Cloud Storage: RS(12, 8) .....

I worked on a research project in undergrad that used Reed-Solomon -- we showed a series of images to users, who would later pick those images out of a set of un-trained images in order to authenticate or access some privileged data, sans encryption. the error-correcting allowed for some degree of misremembering or forgetfulness, as is normal in human image recognition tasks.

The professor later spun up a startup that has since been acquired by Dropbox, but I'm unaware what kind of product they're currently working on.

Parchive 2 was, I believe, an implementation of Reed-Solomon at the application level; mostly used (when it was introduced) to counter loss from missing chunks on binary newsgroups. I think RAR might have picked up a similar feature around that time too?

I believe parchive version 1 was simple XOR parity.

You may want to be able to run highly resilient databases even on non-error-detecting hardware. (Most consumer disks, and even a lot of enterprise disks, don't reliably detect/report disk corruption)

You might also be building a distributed system, where blocks are spread across multiple disks. In that case, an "error" you're trying to correct might be the loss of a disk or server in the distributed system; there is no one single disk or OS responsible for all the relevant blocks in that case.

But, both of these are assuming you're building some kind of data-store, which is not a typical user application. Writing robust data-stores is hard for many reasons, error correcting is just one of them.

i used a reed solomon library recently in a project that encodes and decodes binary data stored in a video channel. i added it to compensate for compression/noise introduced in the re-encoding process on third party sites like youtube. here's an example of what it looks like: [0]

[0] https://cicada.jollo.org/xg/sp.mp4

QR codes use Reed Solomon codes

If you need to transmit data over an unreliable link where retransmission isn't practical you will want some sort of FEC. If hardware isn't available to do the job then it gets done in software.

s3, dropbox - https://dropbox.tech/infrastructure/inside-the-magic-pocket

Doesn’t seem too hard actually, given enough example input. The parity is just a linear combination of the input so you can set up a linear system and solve for those things encoding matrix rows pretty easily. From there you may need to make some assumptions about what type of matrix was used (e.g. vandermonde is popular) and perhaps the field size being used (e.g. GF(2^8), and with those, it should be easy to determine the reducing polynomial. Some of these choices are small enough to be able to brute force (finite fields used for practical problems tend to be small, naturally). If you have a dataset, I might actually toy with it myself.. sounds fun.

Problem with that is, as the article states, RAID6 _can_ use RS as its error correction method, which turns this description into something a bit too circular for my taste

Hamming Codes can only recover from 2 wrong bits per byte, with RS it's configurable.

No. TCP, IP and UDP are all using Internet Checksum (RFC 1071). Ethernet uses CRC.

TCP doesn't do forward error correction at all. It uses a retransmission scheme instead. TCP's error correction is not only to insure a consistent datastream, but also to more equitably share limited bandwidth.

Forward error correction is usually at the PHY layer, not the transport layer. So the more appropriate question is, does 10GbE/100GbE/WLAN/etc use RS coding? (and yes some of them do.)

No, but Reed-Solomon codes are used on on CDs.