– Paul Carpentier, CTO and Founder of Caringo, says:
In the course of IT history, many schemes have been devised and deployed to protect data against storage system failure, especially disk drive hardware. These protection mechanisms have nearly always been variants on two themes: duplication of files or objects (backup, archiving, synchronization, remote replication come to mind); or parity-based schemes at disk level (RAID) or at object level (erasure coding, often also referred to as Reed-Solomon coding). Regardless of implementation details, the latter always consists of the computation and storage of “parity” information over a number of data entities (whether disks, blocks or objects). Many different parity schemes exist, offering a wide range of protection trade-offs between capacity overhead and protection level – hence their interest.
Erasure coding:
As of late, erasure coding has received a lot of attention in the object storage field as a ‘one-size-fits-all’ approach to content protection. This is a stretch. Erasure coding is a solid approach to storage footprint reduction for an interesting but bounded field of use cases, involving BOTH large streams AND large clusters, but at the cost of sacrificing the numerous use cases that involve small streams, small clusters, or a combination of the two.
Most readers will be familiar with the concept of RAID content protection on hard disk drives. For example, the contents of a set of 5 drives is used to compute the contents of what is called a parity drive adding one more drive to the RAID set for a total of 6 drives. Of the total set of 6, if any single drive fails, the content that is lost can be rebuilt from the 5 remaining drives. Aside such a 5+1 scheme, many others are possible, where even multiple drives can fail simultaneously and yet the full content can be rebuilt: there is a continuum in the trade-off between footprint and robustness.
More recently, the same class of algorithms that is used for RAID has been applied to the world of object storage: they are commonly called Erasure Codes (http://en.wikipedia.org/wiki/Erasure_code). The concept is similar: imagine an object to be stored in a cluster. Now, rather than storing and replicating it wholly we will cut the incoming stream into (say) 6 segments in a 5:1 scheme each with parity information. Similar to the RAID mechanism above, any missing segment out of the 6 can be rebuilt from the 5 remaining ones, hence the 1. This provides a mechanism to survive a failed disk drive without making a full replica: the footprint overhead is just 20% here rather than 100% with comparable data durability.
Beyond this “5+1” scheme, many more Erasure Coding (EC) schemes are possible. They can survive as many disk failures as their number of parity segments: a 10+6 scheme can survive 6 simultaneous segment failures without data loss, for instance. Here the overhead will be 60% ((10+6)/10).
Erasure coding comes with trade-offs
The underlying objective is clear: provide protection against failure at lower footprint cost. However, as usual, there is no such thing as a ‘free lunch.’ There are trade-offs to be considered when compared to replication. The key is to have the freedom to choose the best protection for each particular use case.
When chopping up objects to store the resulting segments across a number of nodes, the “physical” object count of the underlying storage system is multiplied (e.g., for a 10:6 scheme, it’s multiplied by 16). Not all competing object storage systems handle high object count well. It is also clear that the granularity (i.e., minimum file size) of the underlying file system or object storage system will play a role in suggesting how small an object can be to be economically stored using erasure coding. It doesn’t really make sense from an efficiency perspective to store, say, a 50K object using a 10:6 erasure coding scheme if there is a file system at the core of a storage system. This is because file systems still segment files into blocks with minimum block sizes. A common threshold for this block size for a Linux file system is 32K so the resulting storage needed for a 50K file using a 10:6 erasure coding scheme would be would be 512K (32K * 16 segments) or a 10X increase in footprint. As we will see replication is a much better approach for small files.
Replication:
The simplest form of protective data redundancy is replication, with one or more additional copies of an “original” object being created and maintained to be available if that original somehow gets damaged or lost. In spite of the recent hype around erasure coding, we will see that there still are substantial use case areas where replication clearly is the superior option. For the sake of the example, imagine a cluster of a 100 CPUs with one disk drive each, and 50 million objects with 2 replicas each, 100 million objects grand total. When we speak of replicas in this context, we mean an instance – any instance – of an object; there is no notion of “original” or “copy.” 2 replicas equal a grand total of 2 instances of a given object, somewhere in the cluster, on 2 randomly different nodes. When an object loss is detected a recovery cycle begins. Data loss only occurs if both replicas are lost which is why it is important to store replicas on different nodes and if possible different locations. It is also important to have efficient and rapid recovery cycles; you want to ensure that your objects are quickly replicated in case of an overlapping recovery cycle which may lead to data loss. If there are three replicas per object, three overlapping recovery cycles (a very low probability event) will be required to cause any data loss.
Replication and Erasure combined is the answer
As so often in IT, there is no single perfect solution to a wide array of use cases. In object storage applications, cluster sizes run the gamut between just a few nodes built into a medical imaging modality to thousands of nodes spanning multiple data centers, with object sizes ranging between just a few Kilobytes for an email message and hundreds of Gigabytes for seismic activity data sets. If we want to fulfill the economic and manageability promises of the single unified storage, we need technology that is fully capable of seamlessly adapting between those use cases.
To deal with the velocity and variability of unstructured information, organizations are increasingly turning to cloud storage infrastructures to manage their data in a cost-effective, just-in-time manner, while others may need the robustness of Big Data repositories to handle the volume that today’s boundless storage requires. A combination of both replication and erasure coding, combined into a singular object storage solution, will provide the best option to access and analyze data regardless of object size, object count or storage amount while ensuring data integrity aligned with business value. Traditional file systems simply cannot provide the ease of management and accessibility required for cloud storage, nor will they provide the massive scalability and footprint efficiency required for Big Data repositories. The future of both cloud storage and Big Data remain firmly entrenched in an object storage solution that incorporates both replication and erasure coding into its architecture to overcome the limitations of either one technology.
To see an in depth paper on “Replication and Erasure Coding Explained” please visit http://www.caringo.com/
