What's the correct database behavior when two transactions change the same row/value?

Question

I'm writing a database LRU cache in C++ for an embedded NoSQL database to solve a performance problem, and I'm trying to understand the correct assumed behavior and philosophy behind it.

Say there's a NoSQL database at a certain state X. We start transaction 1 (tx1) and start transaction 2 (tx2) from the same isolated state X. Both transactions attempt to change the same key/value pair. Each transaction changes the value to some value, and the two values are not equal. Tx1 commits, then tx2 commits. What's the correct behavior of the database?

1. The new value is the one committed from tx2, because it overwrites tx1
2. The new value is the one committed from tx1, because committing tx2 should fail

Or is the answer something else?

Can someone please elaborate on how such a system should be programmed if it's ACID compliant?

The DB I'm using that I want to cache over is LMDB, which claims to be ACID-compliant.

Answer 1

Background

The question asks about the I in ACID, which stands for isolation:

• Atomic: All components of a transaction succeed or fail as a unit.
• Consistent: A transaction leaves the database in a state that does not violate any active constraints.
• Isolated: Transactions are isolated from the effects of other concurrent transactions to the degree specified by the current isolation level.
• Durable: Committed changes to user data are persistent (recoverable).

The most isolated of the standard isolation levels is named serializable.

The definition of the serializable isolation level in the SQL-92 standard contains the following text:

A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions. A serial execution is one in which each SQL-transaction executes to completion before the next SQL-transaction begins.

There is an important distinction to be made here between truly serialized execution (where each transaction actually runs exclusively to completion before the next one starts) and serializable isolation, where transactions are only required to have the same effects as if they were executed serially (in some unspecified order).

A real database system is allowed to physically overlap the execution of serializable transactions in time (increasing concurrency) so long as the effects of those transactions still correspond to some possible order of serial execution.

The question

We start transaction 1 (tx1) and start transaction 2 (tx2) from the same isolated state X. Both transactions attempt to change the same key/value pair. Each transaction changes the value to some value, and the two values are not equal. Tx1 commits, then tx2 commits. What's the correct behavior of the database?

Either of two serial executions are possible:

1. T1 writes value V1. T2 writes value V2.
2. T2 writes value V2. T1 writes value V1.

The observed value after both transactions commit may be V1 or V2.

Both are correct according to a different serial schedule (T1 then T2 or T2 then T1).

---

As a second example, consider two transactions writing a value that depends on the original value. Say for example, the original value is 100, transaction T1 adds 10%, and transaction T2 adds 50%:

Serializable schedule A:

1. T1 reads 100, writes 110. (+10%)
2. T2 reads 110, writes 165. (+50%)

Serializable schedule B:

1. T2 reads 100, writes 150. (+50%)
2. T1 reads 150, writes 165. (+10%)

Now, it is possible for more complex operations to have effects that correspond to no possible serial schedule of transactions. In that case, one transaction will fail with an error and roll back.

(Some database engines may also raise an error and abort a transaction when the engine cannot determine that a serial schedule was possible, even when it logically was.)

According to the documentation for LMDB:

Writes are fully serialized; only one write transaction may be active at a time, which guarantees that writers can never deadlock.

That confirms LMDB implements the serializable isolation level.

An alternative question

It is possible you meant to ask instead about a Lost Update, where changes made by T1 are (undesirably) overwritten by T2 and hence 'lost'. If so, please see the Q & A UPDATE statement behavior.