Chain Replication for Supporting High Throughput and Availability

✨ Summary

Main contribution

The paper introduces chain replication, a replication protocol for storage services that need high throughput, high availability, and strong consistency simultaneously. Replicas for each object are arranged in a linear chain. Updates enter at the head, are computed once, and are propagated through the chain to the tail. Queries are served by the tail, which is the replica guaranteed to contain all completed updates. This organization provides a single serialization point for operations while separating update and query workloads between the head and tail. The paper was published as part of OSDI ’04 in December 2004. (usenix.org)

Protocol and fault handling

The protocol assumes fail-stop servers and reliable FIFO communication between neighboring replicas. A master service detects failures and reconfigures chains. When the head fails, its successor becomes the new head. When the tail fails, its predecessor becomes the new tail; because the predecessor may contain updates not yet present at the failed tail, those updates become completed as part of the reconfiguration. When an internal replica fails, the predecessor forwards any potentially unpropagated updates to the successor before normal processing resumes. New replicas are added at the tail and initialized from the current tail while concurrent updates are tracked and forwarded.

Evaluation and findings

The prototype and simulations compare chain replication with primary/backup replication and weaker variants that allow queries at arbitrary replicas. Chain replication generally matches or exceeds primary/backup throughput because query processing is assigned to the tail rather than competing with update processing at a single primary. The weaker variants perform better for highly query-dominated workloads, but can perform worse once updates exceed roughly 15 percent of requests and do not provide the same strong consistency guarantees. Replication factor has little effect on throughput when requests can be pipelined, although it affects availability and recovery behavior.

The availability experiments show that replica placement and recovery parallelism are critical. Consecutive placement on a hash ring limits parallel recovery and requires increasing the replication factor as the system grows to maintain a target mean time between unavailability. Random placement can provide more recovery parallelism; with sufficient servers and parallel recovery, it eventually offers better availability than ring-based placement. The paper therefore treats placement and repair scheduling as central parts of reliable large-scale storage design, rather than as independent implementation details.

Subsequent research and industry use

The paper’s design was directly extended by CRAQ, which describes itself as an improvement on chain replication intended to increase read throughput by allowing replicas other than the tail to serve reads while preserving strong consistency. (usenix.org) Later work such as Harmonia explicitly implements and evaluates chain replication as a target protocol, addressing the tail’s read-throughput bottleneck with in-network conflict detection; its evaluation reports near-linear read scalability and up to 10× throughput improvement at a replication factor of 10. (arxiv.org)

The design has also been used in industry. Meta’s Delta storage service is described as a highly available, strongly consistent system based on chain replication. Its later design adds apportioned queries so that all chain members can serve reads after checking whether their local versions are committed, while retaining the chain’s consistency properties. (engineering.fb.com) These examples show a continuing pattern: chain replication’s core update path and failure-recovery model are retained, while later systems optimize read scalability, automated repair, placement, and geo-replication.