> Consider a company that stores users’ emails in the cloud — that is, on a vast array of servers. You can think of the whole collection of emails as one long message. Now suppose one server crashes. With a Reed-Solomon code, you’d need to perform a massive computation involving all the encoded data to recover your emails from that one lost server. “You would have to look at everything,” said Zeev Dvir, a computer scientist at Princeton University. “That could be billions and billions of emails — it could take a really long time.”<p>I have to take issue with the above characterization. It seems to imply that a server crash means the user has to wait for the data to be reconstructed, or that it will necessarily take a long time for the data to be reconstructed. But I don't think either of these claims are true in the general case.<p>We can look at Backblaze for a real world example of how an actual file storage company uses Reed-Solomon for error correction:<p>> Every file uploaded to a Backblaze Vault is broken into pieces before being stored. Each of those pieces is called a “shard.” Parity shards are added to add redundancy so that a file can be fetched from a Backblaze Vault even if some of the pieces are not available.<p>> Each file is stored as 20 shards: 17 data shards and three parity shards. Because those shards are distributed across 20 storage pods in 20 cabinets, the Backblaze Vault is resilient to the failure of a storage pod, power loss to an entire cabinet, or even a cabinet-level networking outage.<p>> Files can be written to the Backblaze Vault when one pod is down, and still have two parity shards to protect the data. Even in the extreme and unlikely case where three storage pods in a Backblaze Vault are offline, the files in the vault are still available because they can be reconstructed from the 17 pieces that are available.<p>So BackBlaze splits each file into 20 shards, with 3 of those being parity shards so that only 17 out of 20 shards are necessary to reconstruct the original file.<p>Regardless of whether you store each email in a separate file, or if you store all your emails in one giant file, the point is that your emails will be divided into 20 pieces across 20 separate physical machines, so that the loss of any one machine (or even an entire cabinet) will not impact your access to your emails.<p>I would be extremely surprised if any real company that was actually in the business of storing user data (e.g. AWS, Azure, GCP, Backblaze etc) would store user data in such a way that the crash of a single server would require a "really long time" for the user data to be recovered. Rather, I think it's most likely that the loss of a single server should not have any noticeable impact on the time that it takes for a user to access the data that was stored on that server.<p>As for the second claim, I don't think it should take "a really long time" to recover even billions of emails. I know that (depending on the parameters) the Intel ISA-L Reed-Solomon implementation can achieve a throughput of multiple GB/s on a single core. So even if you were storing all your emails in a single, really huge file that was tens of gigabytes in size, it still shouldn't take more than a few minutes to recover it from the available shards and to regenerate the shard that was lost.
The article didn't mention erasure coding (fountain/raptor codes) and I'm wondering if the significance of this result applies to their usability or not.
One of my favorite talks on this subject: <a href="https://www.youtube.com/watch?v=xE4jEKx9fTM" rel="nofollow">https://www.youtube.com/watch?v=xE4jEKx9fTM</a>
This is a really interesting article for anyone interested in error correcting codes.<p>My TL;DR is that there are some codes that are able to reconstruct data with a fixed number of queries (i.e., limiting the fan out of reads for reconstruction). There are two types of these, locally correctable and locally decodable codes. Locally decodable codes allow reconstructing any part of the original message with a fixed number of reads, while locally correctable codes allow reconstructing parts of the code words in the same way.<p>In particular, the article discusses two query and three queries. The best known algorithms in the past for both of these (two and three queries) for either locally correctable codes or locally decodable codes was the Reed-Muller code, however these codes are exponential in length wrt the length of the original message. In 2003 it was found that it's not possible to do better for two queries than Reed-Muller codes, but in ~2009, Yekhanin and Efremenko independently discovered algorithms that allow for locally decodable three query codes shorter than this (though not linear in length, I think).<p>Now, it's been shown that there are no locally correctable three query codes that are better than Reed-Muller in length, using a technique based on satisfiability.