Causal Consistency and Latency Optimality: Friend or Foe? [Extended Version]

Diego Didona, Rachid Guerraoui, Jingjing Wang, Willy ZwaenepoelInfoscience 2018

Abstract

Causal consistency is an attractive consistency model for geo-replicated data stores. It is provably the strongest model that tolerates network partitions. It avoids the long latencies associated with strong consistency, and, especially when using read-only transactions (ROTs), it prevents many of the anomalies of weaker consistency models. Recent work has shown that causal consistency allows "latency-optimal'' ROTs, that are nonblocking, single-round and single-version in terms of communication. On the surface, this latency optimality is very appealing, as the vast majority of applications are assumed to have read-dominated workloads. In this paper, we show that such "latency-optimal'' ROTs induce an extra overhead on writes that is so high that it actually jeopardizes performance even in read-dominated workloads. We show this result from a practical as well as from a theoretical angle. We present the Contrarian protocol that implements "almost latency-optimal'' ROTs, but that does not impose on the writes any of the overheads present in latency-optimal protocols. In Contrarian, ROTs are nonblocking and single-version, but they require two rounds of client-server communication. We experimentally show that this protocol not only achieves higher throughput, but, surprisingly, also provides better latencies for all but the lowest loads and the most read-heavy workloads. We furthermore prove that the extra overhead imposed on writes by latency-optimal ROTs is inherent, i.e., it is not an artifact of the design we consider, and cannot be avoided by any implementation of latency-optimal ROTs. We show in particular that this overhead grows linearly with the number of clients.

Introduction

In geo-replicated data stores, Causal Consistency (CC) is highly prized because it is the strongest consistency model that remains available even during network partitions. To maximize performance, researchers previously developed "Latency-Optimal" (LO) read-only transactions (ROTs). An LO transaction is nonblocking, requires only one round of communication, and returns only a single version of the data. On paper, LO ROTs seem like the holy grail for read-heavy applications. However, this paper reveals a "performance trap": the mechanisms required to ensure one-round reads impose a massive overhead on writes that cripples overall system performance.

The Problem: The Hidden Tax of One-Round Reads

To ensure that a one-round read is consistent, LO systems must perform a "readers check" during every write. This check forces writers to track which transactions have read old versions of data, creating a massive metadata burden.

The "readers check" in latency-optimal systems forces writers to coordinate with readers, creating significant metadata overhead.

This "readers check" induces high CPU and network utilization, leading to resource contention that actually increases read latency under moderate to high loads. The authors prove that this write overhead isn't just a design choice—it's inherent. Any system providing one-round, one-version, nonblocking ROTs must exchange information about readers that grows linearly with the number of clients.

The Contrarian Protocol

The authors introduce Contrarian, a protocol that is "almost" latency-optimal. It sacrifices a single round of communication for reads to achieve significantly higher throughput and lower latency in realistic workloads. Contrarian remains nonblocking and single-version but requires two rounds of communication for reads: one to coordinate a consistent snapshot timestamp and one to fetch the data. Crucially, it removes all extra overhead from the write path. It uses Hybrid Logical Clocks (HLC) and a background stabilization protocol to keep snapshots fresh without blocking.

Key Results

The authors evaluated Contrarian against an optimized LO design (CC-LO) using YCSB-modeled workloads (95% reads) on AWS across three regions.

  • Throughput: Contrarian achieved 3.7x to 5x higher throughput than the latency-optimal CC-LO system.
  • Latency: While CC-LO is slightly faster at extremely low loads, Contrarian provides lower 95th-percentile latencies for almost all practical load levels. In geo-replicated setups, Contrarian became faster than CC-LO once the system reached just 12% of its maximum capacity.
  • Scalability: Experimental results confirmed the theoretical proof: the overhead of the LO "readers check" grows linearly with the number of clients, whereas Contrarian’s overhead remains constant.
Performance comparison showing Contrarian's superior throughput and latency scaling, alongside the linear growth of metadata in CC-LO.

Conclusion

The "latency-optimal" label for one-round reads is often a misnomer in practice. By accepting a second round of communication, Contrarian avoids the systemic bottlenecks of "readers checks," providing a more scalable and performant solution for real-world distributed databases. This work highlights that optimizing for a single metric (like read rounds) can create bottlenecks elsewhere that negate the intended benefits.

Summary updated

Abstract

Causal consistency is an attractive consistency model for geo-replicated data stores. It is provably the strongest model that tolerates network partitions. It avoids the long latencies associated with strong consistency, and, especially when using read-only transactions (ROTs), it prevents many of the anomalies of weaker consistency models. Recent work has shown that causal consistency allows "latency-optimal'' ROTs, that are nonblocking, single-round and single-version in terms of communication. On the surface, this latency optimality is very appealing, as the vast majority of applications are assumed to have read-dominated workloads. In this paper, we show that such "latency-optimal'' ROTs induce an extra overhead on writes that is so high that it actually jeopardizes performance even in read-dominated workloads. We show this result from a practical as well as from a theoretical angle. We present the Contrarian protocol that implements "almost latency-optimal'' ROTs, but that does not impose on the writes any of the overheads present in latency-optimal protocols. In Contrarian, ROTs are nonblocking and single-version, but they require two rounds of client-server communication. We experimentally show that this protocol not only achieves higher throughput, but, surprisingly, also provides better latencies for all but the lowest loads and the most read-heavy workloads. We furthermore prove that the extra overhead imposed on writes by latency-optimal ROTs is inherent, i.e., it is not an artifact of the design we consider, and cannot be avoided by any implementation of latency-optimal ROTs. We show in particular that this overhead grows linearly with the number of clients.
BibTeX
@inproceedings{didona2018causal,
  author = {Diego Didona and Rachid Guerraoui and Jingjing Wang and Willy Zwaenepoel},
  title = {{Causal Consistency and Latency Optimality: Friend or Foe? [Extended Version]}},
  booktitle = {Infoscience},
  year = {2018},
}
Figure