  Asynchronously replicated primary-backup databases are commonly deployed to
improve availability and offload read-only transactions. To both apply
replicated writes from the primary and serve read-only transactions, the
backups implement a cloned concurrency control protocol. The protocol ensures
read-only transactions always return a snapshot of state that previously
existed on the primary. This compels the backup to exactly copy the commit
order resulting from the primary's concurrency control. Existing cloned
concurrency control protocols guarantee this by limiting the backup's
parallelism. As a result, the primary's concurrency control executes some
workloads with more parallelism than these protocols. In this paper, we prove
that this parallelism gap leads to unbounded replication lag, where writes can
take arbitrarily long to replicate to the backup and which has led to
catastrophic failures in production systems. We then design C5, the first
cloned concurrency protocol to provide bounded replication lag. We implement
two versions of C5: Our evaluation in MyRocks, a widely deployed database,
demonstrates C5 provides bounded replication lag. Our evaluation in Cicada, a
recent in-memory database, demonstrates C5 keeps up with even the fastest of
primaries.
