Communications of the ACM

action by transaction. This leads to messaging semantics.

Messaging semantics. In transactional messaging a transaction makes a bunch of changes to its data and then expresses a desire to send a message. This desire is atomically recorded with the transaction. A transaction may atomically consume an incoming message. That means the work of the transaction, including changes to the application data, occurs if, and only if, the incoming message is consumed.

It is possible to support the semantics of exactly-once delivery. The desire to send is atomically committed with the sending transaction. A committed desire to send a message causes one or more transmissions. The system retries until the destination acknowledges it has received the message in its queue. The message must be processed at the receiver at most once. This means it must be idempotently processed (see Figure 4).

There are challenges with at-most-once processing at the destination. To accomplish this, you need to remember the messages you have processed so you don’t process them twice. But how do you remember the messages? You have to detect duplicates. How long do you remember? Does the destination split? Does the destination move? If you mess this up, will the application process the message more than once? What if the message is being delivered to a microservice-based application? Where is the knowledge of the set of processed messages kept?

Read your writes? Yes? No? It used
to be, back in the day, if you wrote
something, you could read it. Now,
it’s not always that simple. Consider
the following:
Linearizable stores offer read-
your-write behavior. In a linearizable
store each update creates a new ver-
sion of the value, and the store never
returns an old value or a different
value. It always returns the latest in a
linear series of values.

Linearizable stores will sometimes delay for a looooong time.

To ensure they always give the correct value, they will always update every replica.

action system for a database, it’s really bad to lose the most recently committed transactions because the partially full last block of your transaction log is being rewritten. One trick to avoid this is to take turns writing to mirrored logs on different disks. Only after knowing for sure that mirror A has the new block do you write it to mirror B. After a crash, you rewrite the last block of the log onto both mirrors to ensure a consistent answer.

Another well-known technique, especially for the tail of the log, is called ping-pong. 4 In this approach, the last (and incomplete) block of the log is left where it lies at the end of the log. The next version of that block, containing the previous contents and more, is written to a later block. Only after the extended contents are durable on the later block will the new version overwrite the earlier version. In this fashion, there are no windows in which a power failure will lose the contents of the log (see Figure 3).

Careful replacement for record
writes. Updates to records in pre-data-
base days didn’t have transactions. As-
suming each record write was atomic,
you still couldn’t update two records
and get any guarantees they would both
be updated. Typically, you would write
to record X, wait to know it’s perma-
nent, and then write to record Y.

So, could you untangle the mess if a crash happened?

Frequently, there was an application-dependent pattern that provided insight into the order you needed to write. After a crash and restart:

˲ If record A was updated but record B was not written, the application can clean up the mess.

˲ If record B was updated but record A was not written, the application could not cope and could not recover.

An example of careful replacement for records is message queuing. If the application writes and confirms the presence of a message in a queue (call it record A), and the work to process that message is idempotent, then the application can cope with crashes based on careful replacement for records. Idempotent means it is correct if restarted. 4, 7

Transactions and careful replacement. Transactions bundle and solve careful record replacement. Multiple application records may be updated in a single transaction, and they are all-or-nothing. The database system ensures the record updates are atomic.

˲Databases automatically handle any challenges with careful storage replacement. Users are not aware of the funky failure behaviors that may occur when systems crash or power fails. If present, databases also support distributed transactions over a small number of intimate database servers.

˲ Work across time (that is, workflow) needs careful transactional replacement. While the set of records in a transaction is atomically updated with the help of the database, long-running workflows3, 4 are essential to accomplish correct work over time. Failures, restarts, and new work can advance the state of the application transaction by transaction. Work across time leverages message processing.

˲ Work across space (that is, across boundaries) also needs careful transactional replacement. Different systems, applications, departments, and/or companies have separate trust boundaries and typically do not do transactions across them. Work across space necessitates work across time, trans-