Storage Concepts: Erasure Coding (EC)

What is Erasure Coding?

Wikipedia: “In information theory, an erasure code is a forward error correction code for the binary erasure channel, which transforms a message of k symbols into a longer message with n symbols such that the ...”

The Wikipedia entry is probably not the best place to start, let’s look at it from above the algorithms and formulae. What does Erasure Coding mean broadly, in terms of data storage? Well, erasure coding is a method of securing data on disk and can be thought of as an evolution of RAID in some respects, so to touch on RAID briefly before we look at Erasure Coding, traditional RAID will secure data by either mirroring it across one or more disks (RAID 1) or will write parity to one or more disks in a RAID set (RAID 5, RAID 6 aka RAID DP etc.) in order to ensure data is not lost in the event of a disk failure. Hot spares are kept in order to write the data from the failed disk onto, until the original disk is replaced. There are obvious benefits to this way of protecting data but the downside is becoming more evident as data volumes, and perhaps more pertinently, disk sizes increase. Mirroring and parity will require more and more disk as data volumes grow and replacing failed disks means  times on these vast disks is greatly increased, exposing the data to further risk.

Example: File F is split into 9(k) parts, 

which are themselves encoded into

 12(n) further parts, each containing 

effectively 1/9th of the data (it’s not quite

 as simple as that, but helps

 illustrate the principle). As long

 as we still have 9 of the 12 x 1/9th parts 

the original data can be reconstituted.

On to Erasure Coding. Data is split up, expanded with redundant data and sent to a target device in another location, which can be on the same array, local arrays in the same DC and/or remote arrays nationally or geographically. The data at the other ends can be decoded from this source or any other source of the data from any other location meaning that if this particular packet of data is lost, it can be retrieved from a subset of the same data from the other locations. To use a rather tenuous analogy, if you pack elements of your holiday wardrobe across three suitcases, you will arrive in Barbados safe in the knowledge that you will have something to wear even if one of your suitcases ends up in Luton. If two cases are lost, you may end up wearing just speedos and a smile all week. In other words, your suitcase fault tolerance is 2 out of 3.


In a little more detail, Erasure Coding splits data and shares it across locations to be reconstructed in the event of a corruption or loss of data in one or a number of the others. The concept is actually relatively simple to get a handle on. A file or object, F, is split up into k parts, which are then themselves encoded into n parts. To recreate F we would need k out of n parts to recreate the data. An EC configuration might require 9(k) from 12(n)parts, meaning that any 9 subsets of the data out of 12 can be used to reconstruct your original data (see example, right). Any less than that and you can’t reconstruct.

This number can be lower, for example 6 from 12, but then you would need a lot more space and bandwidth to accommodate the fact that all of the data needs to be retrievable from less locations, so therefore contain more redundant* data for the other locations – you might as well mirror or replicate.

* Redundant in this case taking the high availability meaning, as opposed to 'unused'

Is Erasure Coding new?

The theory isn’t. As is often the case with new technology, the principle has been around for some time in the form of Forward Error Correction, first proposed by Reed and Solomon in 1960. In order to ensure that transmissions were received, they were split and encoded, along with redundant data, with an algorithm. As long as the algorithm is known at the other end, any errors can be corrected accordingly. Put horribly simply, if I sent a transmission containing C1H2R3I4S5, and my fiendishly complex algorithm of adding a number to each letter was known at the other end, the receiver would know there was a problem if they received D4A3V2E1 along with the C1H2R3I4S5 in the same transmission. Erasure coding is Forward Error Correction for data replication, storage and security, but instead of correcting errors we are protecting against data loss.

Security

There is an inherent security in Erasure Coding. The fact that the data is broken up and recreated using an algorithm means that, unless that algorithm is known, the data is meaningless. This lends the data transmission an in-flight security of its’ own.

Who has implemented it?

There are a number of storage that have taken up Erasure Coding, often in conjunction with Object Based Storage:

•         SwiftStack
•         EMC Atmos
•         DDN ObjectAssure
•         Scality
•         Hadoop
•         NetApp
•         Cleversafe