Chain Replication for Supporting High Throughput and Availability

Published6th Symposium on Operating Systems Design and Implementation (OSDI 04)

It appeared in a journal, conference or book, which normally review work before accepting it. Even so, one study is never the final word.

Abstract

Chain replication is a new approach to coordinating clusters of fail-stop storage servers. The approach is intended for supporting large-scale storage services that exhibit high throughput and availability without sacrificing strong consistency guarantees. Besides outlining the chain replication protocols themselves, simulation experiments explore the performance characteristics of a prototype implementation. Throughput, availability, and several object-placement strategies (including schemes based on distributed hash table routing) are discussed.

Research Analysis

Written by Kurz, not by the authors of the paper. The abstract above is the authors' own.

Last revised
Version
1.0

Overview

In 2004 large online services (the paper names Amazon.com, Google and FAST, the authors' own search company) needed storage that sat between a file system and a database: objects with queries on a single object and atomic updates of a single object. Designers of such systems often gave up strong consistency to keep throughput and availability, and the paper uses the Google File System as its example of that choice. The authors argue the trade is not forced.

Chain replication is presented as a form of primary/backup, which is itself an instance of the state machine approach (Schneider wrote that tutorial and is a coauthor here). The prototype also relies on Paxos, cited as The Part-Time Parliament, to make its configuration service fault tolerant, so Paxos Made Simple is useful background. For the vocabulary of strong consistency see linearizability; this paper defines its own two-part guarantee instead (operations on an object run in some sequential order, and updates are visible to later queries), which for single objects is close in spirit to linearizability, though the paper does not use that word.

Worth knowing first: the fail-stop failure model (a server halts instead of misbehaving, and the halt can be detected), the idea of primary/backup replication, and why a replica must apply updates in a single order.

Contribution

  • The chain. The servers holding an object are linearly ordered. Updates go to the head and travel along reliable FIFO links to the tail. Every reply is generated by the tail, and every query is sent to the tail and processed there.
  • Strong consistency by construction. Queries and updates are all processed serially at one server, the tail. The new value is computed once, by the head, and forwarded, so the other replicas only perform a write and an update can be non-deterministic.
  • A master for reconfiguration. A master service detects server failures, tells servers their new predecessor or successor, and tells clients who the head and tail are. The paper treats it as a single process that never fails for the exposition, and says the prototype replicates it using Paxos.
  • Failure handling with two invariants. The Update Propagation Invariant says each server's history is a prefix of its predecessor's. The Inprocess Requests Invariant says a server's history equals its successor's history plus the list of updates it forwarded but the tail has not yet acknowledged. Together they cover removing the head, the tail or a middle server, and adding a new tail.
  • A comparison with primary/backup in message delays and in simulation, plus a study of how replica placement affects availability.

Methodology

The argument has two parts. First, a specification: the client's view of an object is a history of updates and a set of pending requests, with three transitions (request arrives, request ignored, request processed). The paper then shows that every server action in a chain is a no-op or one of those transitions, including each reconfiguration case. Footnote 2 says a real implementation would store the current value instead of the update sequence; the sequence is used to make the consistency argument easier.

Second, simulation. The prototype ran on a simulated network with infinite bandwidth and 1 ms per message, with a "null service". Query latency at a server was set to 5 ms, update latency at the head to 50 ms and processing an object-difference message to 20 ms, numbers the paper says come from a web search index. Four variants were compared: chain, p/b, weak-chain and weak-p/b (the weak ones send queries to any random server). Later experiments used 5000 volumes with 3 replicas, failure injection with 24 servers, and a mean-time-between-unavailability study of three placement strategies.

Findings

  • Single chain, no failures. Chain replication has equal or better throughput than primary/backup for every update percentage and for t equal to 2, 3 and 10, because head and tail share work the primary does alone. With 3 servers an update takes 94 ms and a query 7 ms. Throughput of both is unaffected by t when enough requests are pipelined.
  • Weak variants. They win on query-heavy loads but do worse than chain replication above 15% updates, since queries served at the head compete with the slow update work there. The paper sees few settings where they would be preferred.
  • Outage after a failure, counted in message delays. Head failure: updates unavailable for 2 delays. Tail failure: queries and updates unavailable for 2 delays. A middle failure causes no outage, but a delayed update (4 delays). For primary/backup a primary failure costs 5 delays and a backup failure at most 1. The worst case of chain replication is shorter than the worst case of primary/backup.
  • Many chains. With 5000 volumes replicated three times, the four variants showed little or no difference.
  • Failures under load. With 24 servers and 150 GB per server, the simulated master took a bit over 10 seconds to detect a failure and delete the server, and throughput was zero for about that long. After that update throughput was better than before, because some chains had shrunk to length 2. Query throughput stayed lower after recovery, because the recovered server is the tail of every chain it joins and load is no longer balanced.
  • Placement. With a server MTBF of 24 hours, ring placement (DHT style) needed a longer chain as servers grow, roughly logarithmically. Random placement with limited parallel recovery (rndseq) was worse than ring for t above 1, but random placement with full parallel recovery (rndpar) eventually beat both.
  • Size. The prototype is 1500 lines of Java plus 2300 lines of Java for a Paxos library.

Critical Analysis

The idea is simple and the paper is honest about its limits, but these are worth keeping in mind.

  • Everything hangs on failure detection. The model is fail-stop and the master is assumed never to fail. Real systems have slow servers and partitions; the paper says chain replication does not offer graceful handling of partitioned operation. Taking servers out of a chain on a wrong suspicion is what makes the master delicate in practice.
  • The numbers are simulated. Infinite bandwidth, a null service and fixed latencies mean the results show protocol shape, not production behavior. There is no real-hardware experiment.
  • Serial dissemination costs latency. The paper admits an update waits for the sum of the hops, against the maximum with parallel primary/backup. The simulations show throughput at least as good as primary/backup anyway.
  • The tail is a hot spot. All queries for a chain go to one server, and the paper's own failure experiment shows load imbalance from tails.
  • Single-object operations only, with no transactions across objects (footnote 1).
  • Informal proof. The invariants are argued in prose, not mechanized.

Later literature, not part of this paper: Terrace and Freedman's CRAQ (USENIX ATC 2009) starts from exactly the tail bottleneck. It lets any node answer reads for clean object versions and sends a read for a dirty version to the tail, and it uses ZooKeeper to manage chain membership. Compare also how the Chubby lock service and ZooKeeper fill the role the master plays here, and how Dynamo and Brewer's conjecture frame the choice this paper makes (consistency over partition tolerance).

Further Research

  • Wide-area or heterogeneous deployments, where the authors say placement would depend on access patterns, network proximity and observed host reliability, and where protocols to reorder a chain would be needed.
  • Balancing reads across replicas without losing strong consistency, as CRAQ does.
  • Replacing the assumed fail-stop detector and the never-failing master with a fully specified, fault-tolerant configuration service.
  • Support for operations over several objects.
  • Comparing chain replication with consensus-based protocols such as Raft on real hardware.

Full text

Loading the paper…

Discussion · 0

No posts yet. Be the first to start the discussion.