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
distributed transactions.
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
multiple requests.
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 shopping carts.

e-commerce—product
catalog
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.