PrompTCC: Transactional Causally Consistent Reads Can Be Fast and Fresh

Transactional Causal Consistency (TCC) is the strongest consistency model compatible with availability and, therefore, it avoids the pitfalls of the CAP theorem while simplifying the programming of cloud applications. Unfortunately, with previous implementations, TCC came at the cost of expensive reads. TCC has been implemented either using conservative approaches, that always require two communication rounds, or using optimistic approaches that, in good cases, require just one round, but in face of skewed workloads, that are common in real applications, can require three communication rounds. In this paper we propose a novel algorithm, named PrompTCC, that in most cases offers reads in just one round and that, even in face of skewed workloads, never takes more than two rounds. As a result, PrompTCC is able to closely approximate the performance of an eventually consistent system while providing stronger guarantees, achieving only 12% throughput and 20% latency penalty in realistic scenarios, outperforming state-of-the-art systems which present up to 37% and 60% throughput and latency degradation respectively.