Capstone: Choosing a Replication and Ordering Design for a Workload

• Turn a workload into the questions that decide a design: what must be ordered, where the replicas live, which invariants exist, how contended the data is, and what the network allows.
• Match each answer to a family of designs from this discipline, and name what that family assumes.
• Compute a design's cost for a concrete workload from round trips, quorum sizes, and conflict odds.
• Split one system into data sets with different designs, and defend each choice against its failure modes.

This discipline has covered a dozen ways to order and replicate data, and each lesson ended with a price. None of them won. multi-paxos-from-one-decision-to-a-replicated-log is simple and strong, and it charges a round trip to a majority for every write. causal-consistency answers locally, and transactional-causal-consistency shows that it still cannot protect an invariant. deterministic-transactions-calvin removes commit votes and requires declared read and write sets.

The working skill is reading a workload closely enough to know which price it can pay. This capstone applies that skill to a single system, the way capstone-designing-a-cloud-storage-system-for-a-workload did for storage. The conclusion is that one system rarely has one answer.

Five questions

1. What has to be ordered? A replicated state machine needs one order for everything it holds, while a set of independent keys needs far less. Asking this first prevents buying a global order for data that only needs per-key order.

2. Is there an invariant across concurrent operations? "A seat is sold once" and "a username is unique" cannot be checked by two sites that each act alone. transactional-causal-consistency shows two datacenters each approving an action that is individually legal and jointly illegal. If the invariant must hold, those operations need agreement, and no amount of causal metadata replaces it.

3. Where are the replicas relative to the clients? Inside one datacenter a round trip is cheap. Across regions the speed of light sets a floor, and any write that must reach a majority pays it.

4. How contended is the data? Contention decides between optimistic designs, which pay in aborts, and pessimistic or deterministic ones, which pay in waiting.

5. What do you control? Network-ordered designs need ordered delivery, and their best results use a sequencer in a switch or middlebox. An end-host sequencer avoids that hardware at a latency cost. Calvin needs transactions whose sets can be declared or cheaply predicted. A design is only available if its assumptions can be met.

The families and what they assume

Failure detection and membership sit underneath all of them. failure-detectors explains why suspicion is enough for liveness, and reconfiguration-changing-membership-in-paxos-and-raft shows why changing replicas needs the same care as the data path.

Read every published number with its condition

The lessons here report throughput and latency from papers, and each figure belongs to one testbed, workload, and payload. A number from one paper cannot be set against a number from another as if both were measured together. For a design decision, use papers for the shape of the trade-off and measure your own workload for the quantity.

A ticketing platform has four data sets. All latencies, rates, and contention figures below are assumptions for this exercise, and each calculation was run in a script.

Example 1: Control plane

The shard map and feature flags change a few times a minute, must be read consistently, and live in one region on five replicas. Writes are rare, there are no multi-key transactions, and availability during two crashes matters.

A consensus log fits directly. Flexible quorums are worth checking, because fast-paxos-and-flexible-quorums shows that only phase 1 and phase 2 quorums must intersect:

text
Q1  Q2  intersect?  crashes writes survive, leader alive  crashes an election survives
3   3   yes         2                                     2
4   2   yes         3                                     1
5   1   yes         4                                     0
3   2   no

A smaller phase 2 quorum helps a workload that writes constantly. This one barely writes, and if the leader is among the crashed nodes, writes stop until an election, which with Q1 = 4 survives only one crash. Plain majorities win, and the optimization is declined.

Example 2: Seat inventory

Sixteen shards in one region hold seats. A purchase takes several seats that can span shards, and a popular on-sale makes a few keys extremely hot. "Sold once" is an invariant, so question 2 rules out causal stores.

Certification holds no lock across sites during agreement, so it seems attractive. Take write sets of k keys among D hot keys, and c concurrent transactions:

text
D          k  c    P(two transactions overlap)  P(at least one overlap)
1,000,000  5  200  0.000025                     0.0050
100        5  200  0.2304                       1.0000

On a large, cold key space certification is excellent. During an on-sale, a transaction almost always meets a conflict, and the aborted work is retried into the same contention.

Compare two lock-based paths on one hot key, assuming a one-way delay of 0.25 ms and 0.1 ms of execution. In this simple model, 2PC over consensus groups holds locks across prepare, replication, the vote, and replicating the decision, which is 6 one-way delays. A deterministic design holds them for the read exchange and execution, about 2 delays, because the order was fixed first. Both counts are rough:

text
2PC over consensus:  hold 1.60 ms -> at most 625 transactions/s on that key
Deterministic:       hold 0.60 ms -> at most 1,667 transactions/s on that key

Read 1,667 as a ceiling, because it assumes all participants start together. deterministic-transactions-calvin lists execution skew and multipartition CPU as the costs in exactly this regime. The deterministic path also pays in latency: with Calvin's 10 ms epochs a request waits 5 ms on average for its batch, plus replication. Seat IDs are in the request, so the sets can be declared, and a few milliseconds are acceptable to someone buying a ticket. A deterministic design fits.

Network ordering looks like a further gain, but a purchase conditional on seats in another shard is not an independent transaction in Eris's model, so it would take the slower general path. The in-network sequencers behind the best results in network-ordered-consensus-nopaxos-eris-and-hydra also need an operator who controls the network. The platform runs on a public cloud, where only an end-host sequencer is possible, and none of these sources measures that setting, so question 5 sets the option aside.

Example 3: Profiles and follows

Three regions serve users, and writes must feel instant. Assume round trips of 70 ms between Virginia and Ireland, 150 ms between Virginia and Tokyo, and 210 ms between Ireland and Tokyo. Consensus with a leader in Virginia and a majority of two gives:

text
Client in   Consensus write   Causal write acknowledged
Virginia    70 ms             local
Ireland     140 ms            local
Tokyo       220 ms            local

Causal replication acknowledges in the local region, and a write becomes visible elsewhere after at least the one-way delay: 35 ms from Virginia to Ireland, 75 ms to Tokyo, 105 ms from Ireland to Tokyo. Profiles and follows have no cross-site invariant, and a follow that appears 100 ms later harms nobody, so transactional causal consistency fits. causal-metadata-for-geo-replication-saturn matters if metadata grows into a visibility or throughput problem.

There is one exception inside this data set. Usernames must be unique, and question 2 applies. Username claims go through a consensus log. Using the control plane's log means a round trip to its region, which is a cross-region cost for most users, and claims stop if that region is lost. Claims are rare, so both costs are acceptable here.

Example 4: Order events

Every sale produces events that many consumers replay, and replay needs one total order. Assume 40 storage shards at 15,000 appends per second each, 600,000 in total, and a single sequencer capped at 200,000 tokens per second:

text
Offered 600,000/s, delivered min(600,000, 200,000) = 200,000/s
Shards the sequencer can feed: 13 of 40

The sequencer becomes the bottleneck long before storage does. scaling-shared-logs-fuzzylog-and-scalog offers two exits. FuzzyLog removes the global order, which replay needs here, so it is out. Scalog keeps the total order by ordering records already replicated, at the cost of waiting for a cut. If a consumer later needs lower end-to-end latency, low-latency-shared-logs-lazylog-and-speclog shows where that wait can move. It does not disappear.

The result

• "Pick the strongest guarantee to be safe." Example 3 shows the strongest option adding 220 ms to a write that needed none of it. Strength has a price, and paying it where nothing depends on it is a design error.
• "Causal consistency is nearly as good as consensus." It is a good fit until an invariant appears. The username in Example 3 cannot be protected by metadata, however rich.
• "Certification is always cheaper because it avoids distributed locks." Example 2 shows it depends entirely on contention: the same protocol went from 0.5% to near certainty of conflict.
• "This paper reached a million operations per second, so my system will." That figure carries a testbed, a payload, and often a missing replication factor. Use it for shape, not for planning.
• "A faster network sequencer solves it." Only for operators who can deploy one. An end-host sequencer avoids the hardware and gives back part of the latency gain.
• "One system should have one replication design." Four data sets with different answers is the normal result, not a failure of architecture.

A design follows from five questions: what must be ordered, which invariants span concurrent operations, where replicas sit, how contended the data is, and what you control. Each family answers some of these and assumes the rest. In this example, consensus held rare, critical data, a deterministic design took the contended inventory, causal replication kept global profiles fast, and a cut-based shared log carried events past a sequencer's limit. Compute the cost for your own workload, read published numbers with their conditions, and name what would change your mind.