If a server is slow or dead and contains one of the replicas, it may take
tens of seconds to decide what to do …
Meanwhile, the user waits.
Nonlinearizable stores do not offer
to read your writes. A nonlinearizeable
store means there’s no guarantee that a
write will update all the replicas. Sometimes, a read may find an old value.
Reading and writing a nonlinearizable
store has a very consistent response
time with much higher probability.
A read or write can skip over a sick or
dead server. Occasionally, this results
in an older value coming back from the
skipped server. But, hey, it’s fast—and
Imagine a key/value store where key-K has value V1 and the store keeps it
on servers S1, S2, and S3. You decide to
update the value to V2. The store tries
to change the values on its three servers, but S2 does not answer because it
is down. Therefore, the store decides
to write V2 onto S1, S3, and S4 so that
the new value is always written to three
servers. Later, when S2 comes up, a
read might find the old value V1. This
has the following trade-offs:
˲ The write of three stores always
˲ The store is not linearizable and
sometimes returns an old value.
This very useful technique underlies
a number of scalable storage systems
such as Dynamo2 and Cassandra. 11
Cached data offers scalable read
throughput with great response time.
Key-value pairs live in many servers
and are updated by propagating new
versions. Each read hits one of the
servers and returns one of the versions
(see Figure 5).
Different Stores for Different Uses
OK to stall on reads?
OK to stall on writes?
OK to return stale versions?
You can’t have everything!
Immutability: A solid rock to stand
on. When you store immutable data,
each lookup always returns the same
result. 8 Immutable stores do not ever
exhibit update anomalies because you
never update them. All you can do is
store a brand-new value for an identi-
fier and, later on, delete it. Many ap-
plication patterns are based on immu-
Imagine a system where you are sim-
ply recording stuff you have seen. Ev-
erything you know is based on observa-
tions. The past is never changed—sort
of like an accountant’s ledger where
nothing is updated. You can put a
unique ID on each artifact and look at it
later but never change it. This is an ex-
tremely common pattern.
When keeping immutable objects
or values in a key/value store, you
never get a stale answer. There’s only
one immutable value for the unique
key. That means a nonlinearizable
store offers the one and only correct
answer. All the store types give the
correct answer, just with different
characteristics for read and write la-
tencies (see Figure 6). Storing immu-
table data means you never get a stale
version because there is not one.
Slip-Slidin’ Away …
This section looks at a number of guar-
antees that are slipping away. Everyone
wishes they had a computational mod-
el such as a von Neumann machine, 12
which provides computation, storage,
and predictable linear behavior. Once
distribution kicks in, however, that’s in-
deed only a wish.
Single-process computation as John
von Neumann conceived has evolved
to multiprocess- and multiserver-using
sessions and session state. These state-
ful sessions supported composable
transactions that spanned multiple
records and multiple servers working
together. As the work started decom-
posing into microservices, however, it
became hard to use transactions the
way they had been used.
To cope with scalable environments,
data had to be busted up into key values. Scalable stores worked well for updating a single key at a time but not for
atomic transactions across keys. Most
Figure 5. Different types of storage offer different guarantees.
Linearizable Store No No Yes
Non-Linearizable Store Yes Yes No
Scalable Cache Yes w/Scale No No
Figure 6. Immutable data allows “read-your-write-behavior.”
LinearizableStore No No Immutable
Non-Linearizable Store Yes Yes Immutable
Scalable Cache Yes w/Scale No Immutable
Figure 4. Transaction messaging.
Writes To Data
Transaction T1 Transaction T2
Z YX W
Writes To Data