Asynchronously replicated primary-backup databases are the beating heart of many large applications. The backups provide availability if the primary fails and may serve read-only transactions to increase throughput for all clients and reduce latency for clients in other geographic regions. However, to retain the correctness of overlying applications despite their read-only transaction returning stale values, backups should appear virtually indistinguishable from the primary. Thus, backups must guarantee monotonic prefix consistency, where they present a progressing sequence of the primary's recent states. But monotonic prefix consistency severely constrains a backup's execution because it must exactly copy (or clone) the commit order resulting from the primary's concurrency control. Existing cloned concurrency control protocols guarantee this order by limiting the backup's parallelism, but as a result, a parallelism gap exists between them and the primary.

In this paper, we prove this parallelism gap leads to unbounded replication lag, where changes committed by the primary may take infinitely long to propagate to the backup, for some workloads. Unbounded lag recently caused catastrophic failures (i.e., user data loss) and outages in production systems, and thus, our proof reveals such catastrophes are potentially lurking behind every workload change. We then design FDR, the first cloned concurrency protocol to guarantee both monotonic prefix consistency and bounded replication lag. Further, we provide an implementation of FDR that is backward-compatible with existing production databases, making it possible to thwart these potential failures immediately. We demonstrate formally and experimentally FDR provides bounded replication lag under a variety of workloads.