version history, one new version always
supersedes the earlier one. A nonlinear
history has a DAG version history. In this
case, the linearizable behavior of the
store also implies that a stall within one
of the store servers will stall the write
to the store. This is the “must be right”
even if it’s not “right now” case.
The workflow implemented by careful
replacement will be a mess if you can’t
read the last value written. Hence, this
usage pattern will stall and not be stale.
Transactional blobs-by-ref. This is a
pretty common application pattern. The
application runs using transactions and
a relational database. It also stores big
blobs such as documents, photos, PDFs,
videos, music, and more. The blobs can
be large and numerous. Hence, these are
a challenge to implement directly in the
Each of these blobs is an immutable
set of bits. To modify a blob (for example, editing a photo), you always create a
new blob to replace the old one. The immutable blobs typically have a universally unique identifier (UUID) as their
key in a scalable key-value store.
Storing immutable blobs in a non-linearizable database does not have any
problems with returning a stale version.
Since there’s only one immutable version, there are no stale versions.
Storing immutable data in a nonlinearizable store enjoys the best of both
worlds: it’s both right and right now.
E-commerce shopping cart. In e-commerce, each shopping cart is for a separate customer. There’s no need or desire
for cross-cart consistency. Each shopping
cart has a unique identity or key.
Customers are very unhappy if their
access to a shopping cart stalls. Large
e-commerce sites can measure the percentage of abandoned carts and customer sessions when they get slow. Slow
carts correspond to a large drop-off in
business. Product catalogs, reviews,
and more must be fast and responsive
or customers leave.
Shopping carts should be right now
even if they are not right. It is measurably better for business and the customer experience to return a stale or
otherwise incorrect answer if it can be
done quickly. Users are asked to verify
the contents of the shopping cart before
confirming the sale.
In a nonlinearizable store, some-
times multiple old versions of the cart
exist in the version history DAG. Rela-
tively simple shopping-cart semantics
facilitate combining different versions
of a single user’s shopping cart. 2
Product catalogs for large e-commerce
sites are processed offline and stuffed
into large scalable caches. Feeds from
partners and crawls of the Web are
crunched to produce a sanitized
and hopefully consistent collection of
Each product in the catalog has a
unique identifier. Typically, the identifi-
er takes you to a partition of the catalog.
The partition has a bunch of replicas,
each containing many product descrip-
tions (see Figure 9). One typical imple-
mentation of a scalable product cache
has partitions with replicas. In this
depiction, the columns are partitions
and the rows depict replicas. The back-
end processing produces new product
descriptions that are distributed with
pub-sub. Incoming requests are sent to
the partition for the product identifier
and then load-balanced across replicas.
Back-end processing of the feeds
and crawls, as well as the pub-sub distribution of updates to the caches, are
throughput sensitive, not latency-sensitive. Different replicas may be updated
Figure 9. Partitions with replicas.
Automatic Pub-sub Distribution
(Feed and Crawl)
Incoming Read Requests
Figure 8. Linear vs. nonlinear histories.
Directed Acyclic Graph