  This paper studies the costs and trade-offs of providing transactional
consistent reads in a distributed storage system. We identify the following
dimensions: read consistency, read delay (latency), and data freshness. We show
that there is a three-way trade-off between them, which can be summarised as
follows: (i) it is not possible to ensure at the same time order-preserving
(e.g., causally-consistent) or atomic reads, Minimal Delay, and maximal
freshness; thus, reading data that is the most fresh without delay is possible
only in a weakly-isolated mode; (ii) to ensure atomic or order-preserving reads
at Minimal Delay imposes to read data from the past (not fresh); (iii) however,
order-preserving minimal-delay reads can be fresher than atomic; (iv) reading
atomic or order-preserving data at maximal freshness may block reads or writes
indefinitely. Our impossibility results hold independently of other features of
the database, such as update semantics (totally ordered or not) or data model
(structured or unstructured). Guided by these results, we modify an existing
protocol to ensure minimal-delay reads (at the cost of freshness) under
atomic-visibility and causally-consistent semantics. Our experimental
evaluation supports the theoretical results.
