  We address the problem of compactly storing a large number of versions
(snapshots) of a collection of keyed documents or records in a distributed
environment, while efficiently answering a variety of retrieval queries over
those, including retrieving full or partial versions, and evolution histories
for specific keys. We motivate the increasing need for such a system in a
variety of application domains, carefully explore the design space for building
such a system and the various storage-computation-retrieval trade-offs, and
discuss how different storage layouts influence those trade-offs. We propose a
novel system architecture that satisfies the key desiderata for such a system,
and offers simple tuning knobs that allow adapting to a specific data and query
workload. Our system is intended to act as a layer on top of a distributed
key-value store that houses the raw data as well as any indexes. We design
novel off-line storage layout algorithms for efficiently partitioning the data
to minimize the storage costs while keeping the retrieval costs low. We also
present an online algorithm to handle new versions being added to system. Using
extensive experiments on large datasets, we demonstrate that our system
operates at the scale required in most practical scenarios and often
outperforms standard baselines, including a delta-based storage engine, by
orders-of-magnitude.
