by Arvind Krishnamurthy

Today's Internet services are characterized by a few clear trends. An increasingly large fraction of the services are hosted in the cloud, there is progressively greater use of cheap and off-the-shelf hardware inside cloud data centers, and users are generating increasingly larger volumes of data. Given these trends, a cloud storage system has to meet a number of demanding requirements: the platform needs to be scalable, it has to provide strong consistency semantics, and it has to be robust to a broad class of failures. Numerous systems exist that partially satisfy some of the aforementioned requirements. For example, BFT-based systems provide strong robustness but at the cost of scalability, DHTs are highly scalable but fail to provide consistency and robustness, and systems such as BigTable and HBase provide moderate levels of scalability but not reliability in the face of data corruption.

It is in this context that the authors develop a system that provides a fresh perspective on building scalable and robust storage systems. The authors design and implement Salus, the first block store that is scalable and robust to commission failures. It is similar to Amazon's Elastic Block Store (EBS), providing a virtual block-level device that can be read/write mounted by a single client at a time. Salus's implementation descends from HBase but differs in two key respects. HBase can support many clients, but is robust only to omission failures (e.g., crashes or dropped messages) rather than the commission failures (e.g., data corruption) that Salus can tolerate. Crucially, Salus comes up with the surprising result that robustness and scalability are not necessarily trade-offs and that a carefully designed system can tolerate many types of failures and provide end-to-end correctness guarantees without incurring high replication costs.

Salus is able to achieve this result using a combination of techniques. Its scalability arises from the traditional technique of striping a volume across many storage servers, but, unlike most such striping, supports totally-ordered operations that can be executedconcurrently across servers without a single serialization point. Salus replicates both the storage and the computation layer to safeguard against data corruption. It provides end-to-end reliability by maintaining a Merkle tree for each volume that a client can consult in order to validate data retrieved from the storage system. While elements of the approach have been proposed before, the key contribution is the unique combination of ideas that work quite well together.