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 relational database.

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
E-commerce—Product catalog.
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
product-catalog entries.
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.

a-e
a-e
a-e
a-e
f-j
f-j
f-j
f-j
k-o
k-o
k-o
k-o
p-t
p-t
p-t
p-t
u-z
u-z
u-z
u-z
Automatic Pub-sub Distribution
Backend Processing
(Feed and Crawl)

Incoming Read Requests
crawl
the Web
feeds from
partners

Figure 8. Linear vs. nonlinear histories.

Linear
Version History
Directed Acyclic Graph
Version History