Last write wins (discards concurrent writes)

A scheme to achieve eventual convergence, where each replica always stores the latest value, allowing old values ​​to be overwritten and discarded.Assuming that every write request eventually syncs to all replicas, as long as it is determined which write is the latest, the replicas will eventually converge to the same value.

But how to define latest?In Figure-12, when a client sends a write request to a database node, neither client is aware of the other client, so it is unclear which happens first.It doesn't really make much sense to argue which happens first, when we say that writes are supported concurrently, we mean that their order is indeterminate.

We can enforce arbitrary ordering even if the "natural ordering" of write requests cannot be determined.For example, append a timestamp to each write request, then choose the latest or largest timestamp, and discard writes with earlier timestamps.This is LWW, last write wins, the only conflict resolution method Cassandra supports.

LWW achieves the ultimate convergence goal, but at the expense of durability: if there are multiple concurrent writes to the same K, even if they all notify the client of success (because w replicas completed the write), it is better toOnly one write will survive, the others will be silently discarded.LWW might even remove those non-concurrent writes.

In some scenarios, such as caching systems, overwrites are acceptable.If overwriting, loss of data is unacceptable, then LWW is not a good choice.

The only way to make LWW safe: write only once, then treat as immutable, avoid concurrent updates to the same K.For example, Cassandra recommends using UUID as K, so that each write operation provides a unique K.

Happens-before relationships and concurrency "happened before" relationships and concurrency

How to judge whether two operations are concurrent?

Cases

• As shown below, the two writes are non-concurrent: A's insertion precedes B's incremental modification, because B's incremented value is based on A's inserted value.That is, the B operation is built on the basis of A, so it happens after B.B is causally dependent on A

  

• The two writes in the figure below are concurrent: when each client initiates a write operation, it does not know whether another client is also performing the same K.Therefore, there is no causal relationship between operations

  

Operation A happens before operation B if B knows A or depends on A or builds on A in some way.Whether an operation occurs before another operation is the key to defining concurrency.It can also be stated simply that two operations are concurrent if neither occurs before the other (ie, neither operation knows about the other) [54].

Therefore, for two operations AB, there are three possibilities: A happens before B or B happens before A or AB is concurrent.We have an algorithm to tell us whether two operations are concurrent:

• If an operation occurs before another operation, the later operation can overwrite the earlier operation
• If these operations are concurrent, there are potential conflicts that need to be resolved