Tiered Replication: A Cost-effective Alternative to Full Cluster Geo-replication
📜 Abstract
Cloud storage systems typically use three-way random replication to guard against data loss within the cluster, and utilize cluster geo-replication to protect against correlated failures. This paper presents a much lower cost alternative to full cluster geo-replication. We demonstrate that in practical settings, using two replicas is sufficient for protecting against independent node failures, while using three random replicas is inadequate for protecting against correlated node failures. We present Tiered Replication, a replication scheme that splits the cluster into a primary and backup tier. The first two replicas are stored on the primary tier and are used to recover data in the case of independent node failures, while the third replica is stored on the backup tier and is used to protect against correlated failures. The key insight of our paper is that, since the third replicas are rarely read, we can place the backup tier on separate physical infrastructure or a remote location without affecting performance. This separation significantly increases the resilience of the storage system to correlated failures and presents a low cost alternative to geo-replication of an entire cluster. In addition, the Tiered Replication algorithm optimally minimizes the probability of data loss under correlated failures. Tiered Replication can be executed incrementally for each cluster change, which allows it to supports dynamic environments in which nodes join and leave the cluster, and it facilitates additional data placement constraints required by the storage designer, such as network and rack awareness. We have implemented Tiered Replication on HyperDex, an open-source cloud storage system, and demonstrate that it incurs a small performance overhead. Tiered Replication improves the cluster-wide MTTF by a factor of 20,000 compared to random replication and by a factor of 20 compared to previous non-random replication schemes, without increasing the amount of storage.
✨ Summary
Summary
The paper argues that conventional three-way replication is poorly matched to the different failure modes faced by large storage clusters. Under the paper’s analytical model, two replicas are generally sufficient for independent node failures, whereas three replicas placed randomly provide limited protection against correlated failures. The proposed solution, Tiered Replication, keeps the replicas needed for normal recovery in a primary tier and places an additional durability replica in a physically or geographically separated backup tier. Because the backup replica is rarely read, it can use lower-cost, write-oriented storage and need not impose the performance requirements of the primary tier.
The placement algorithm constructs copysets that minimize overlap while satisfying tier, scatter-width, topology, rack, power-management, and chain-replication constraints. It operates incrementally as nodes join or leave the cluster. An implementation in HyperDex showed small throughput and latency costs and recovery times comparable to the system’s default replication scheme. Under the authors’ model, the technique improved cluster-wide mean time to failure by approximately 20,000 times over random replication and 20 times over earlier non-random replication schemes, without increasing the number of stored replicas.
A later research extension, Popularity-Aware Multi-Failure Resilient and Cost-Effective Replication (PMCR), explicitly builds on the primary-tier/backup-tier design. It adds data-popularity classes and compression for backup replicas to reduce storage and bandwidth costs while retaining protection against independent and correlated failures. (mds.marshall.edu)
Industry-oriented patent literature also describes geographically distributed data stores using tiered replication, replication groups, failure-aware reconfiguration, and separate local and regional replication paths. This provides evidence that the paper’s central architectural idea continued to appear in subsequent designs, although the available search results do not establish deployment of the exact HyperDex implementation in a commercial product. (patents.justia.com)
The paper was published in the 2015 USENIX Annual Technical Conference, and its bibliographic metadata and author ordering are independently confirmed by USENIX and DBLP. (usenix.org)