sion- 1]), you can view the version as immutable data. Each version becomes an
immutable thing to be kept. Using the
extended [Key, Version], you can reference immutable data in the store.
Version history may be linear, meaning one version supersedes the previous
one. This is achieved by using a
linearizable store. Version history may be a directed acyclic graph (DAG). This happens
when writing to a nonlinearizable store.
Imagine you have a notepad on
which to scribble stuff. But you really
have multiple notepads. You scribble
stuff on whichever notepad is closest
to you at the time. When you want to
read the information, you look at the
closest notepad even if it’s not the one
you wrote on most recently. Sometimes,
you get two notepads next to each other,
look at both, and write something in
both to consolidate the scribbles. This
is the kind of behavior that comes from
a nonlinearizable store. Updates do not
march forward in linear order.
Careful replacement and read your
writes. In careful replacement you need
to be careful about the ordering of what
you update. This is essential to handle
some failures, as discussed earlier. Predictable behavior across trust boundaries is needed when working with other
companies. It’s also essential when doing long-running workflows.
Careful replacement is predicated
on read-your-writes behavior, which
depends on a linearizable store. Linearizable stores almost always have the
property of occasionally stalling when
waiting for a bum server.
Some Example Application Patterns
Let’s look at some application patterns
and how they impact the management
of durable state (see Figure 7).
Workflow over key-value with careful replacement. This pattern demonstrates how applications perform workflow when the durable state is too large
to fit in a single database.
An object is uniquely identified by its
key. Work arrives from the outside via
human interaction or messaging. Workflow can be captured in the values. New
values replace old ones. The messages
are contained as data within the object. 9
Scalable workflow applications can
be built over key-value stores. You must
have single-item linearizability (read
your writes, see Figure 8.) With a linear
of these scalable key-value stores en-
sured linearizable, strongly consistent
updates to their single keys. Unfortu-
nately, these linearizable stores would
occasionally cause delays seen by users.
This led to the construction of nonlin-
earizable stores with the big advantage
that they have excellent response times
for reads and writes. In exchange, they
sometimes give a reader an old value.
Finally, this section points out that
some uses of data find the correct answer important enough to use careful replacement of the stored values.
These uses are not the best for nonlinearizable stores.
Honestly, it ain’t like it used to be.
Same process evolves to different
process. Applications and the database
used to run in the same process. A library call to the database code allowed
access to the data. Sometimes, multiple
applications were loaded together.
Later, the database and applications were split into different processes
connected by a session. The session
described the session state and had information about the user, transaction
in flight, the application being run, and
the cursor state and return values.
Later still, the application and database moved to different servers. The
session state made that possible.
Stateful sessions and transactions.
Stateful sessions were a natural outcome of shared processes. You knew
who you were talking to and you could
remember stuff about the other guy.
Stateful sessions worked well for
classic SOA. When talking to a ser-
vice, you expected a long session with
state on each side. Stateful sessions
meant the application could do mul-
tiple interactions within a transac-
tion. In many circumstances, rich and
complex transactions could occur
over N-tier environments, even across
multiple back-end databases using
Transactions, sessions, and microser-
vices. Microservices leave much to be de-
sired when it comes to session state. Re-
quests are load balanced through a router,
and one of many microservice instances is
selected. Usually, later traffic is sent to the
same instance but not always. You cannot
count on getting back to where you were.
Without session state, you can-
not easily create transactions cross-
ing requests. Typically, microservice
environments support a transaction
within a single request but not across
Furthermore, if a microservice ac-
cesses a scalable key-value store as it
processes a single request, the scalable
key-value store will usually support only
atomic updates to a single key. While it
won’t break the data by failing in the mid-
dle of updating a key as older file systems
did, programmers are on their own when
changing values tied to multiple keys.
Keys, versions, and nonlinear history. Each key is represented by some
number, string, key, or URI. That key
can reference something that’s immutable. For example, “The New York
Times, June 1, 2018, San Francisco Bay
Area edition” is immutable across space
and time. A key may also reference something that changes over time—for example, “today’s New York Times.”
When a key references something
that changes, it can be understood as
referencing a sequence of versions, each
of which is immutable. By first binding
the changing value of the key to a unique
version of the key (for example, [Key, Ver-
Figure 7. Applications patterns.
workflow over key-value A traditional workflow application over a scalable collection
of key-value data.
transactional blobs-by-ref A centralized and transactional system managing
very large collections of immutable blobs.
e-commerce—shopping cart The familiar but still surprising world of e-commerce
Consider a very large ecommerce product catalog with
enormous numbers of product descriptions and huge traffic
reading the catalog.
search Track a ginormous number of document (for example, the entire
Web) and organize searchable indices to locate documents by
words and phrases. Must scale to ever increasing read workload.