Optimistic Concurrency Control

Optimistic concurrency control (OCC) is a way of letting several writers change shared data without holding locks while they work. Each writer does its work assuming no one else will interfere, then checks at commit time whether that assumption held. If it did, the change is applied. If another writer got there first, the change is rejected and the writer tries again.

The alternative, pessimistic concurrency control, takes locks before working so that conflicts cannot happen in the first place. The two approaches spend their cost in different places: locking pays to acquire and release locks on every operation, and waits when a conflict occurs. Optimism pays for tracking what was read and for validating and committing atomically on every transaction, and pays again, in retries and unusable work, when a conflict actually occurs.

Where the idea comes from

H. T. Kung and John T. Robinson set out the approach in a 1981 paper in ACM Transactions on Database Systems. Their starting point was a list of problems with locking: maintaining locks is overhead even for read-only queries, deadlocks have to be detected, a lock held on a busy node while waiting for disk lowers concurrency, and locks generally cannot be released until the transaction ends. Most importantly, they argued, locking may only be needed in the worst case — if conflicts are rare, most of that cost buys nothing.

Their methods rely instead on transaction backup, “hoping” conflicts will not occur. A transaction runs in three phases:

1. Read phase. The transaction reads freely and makes its writes to local copies, not to shared data.
2. Validation phase. It checks whether its changes can be applied without breaking integrity given what other transactions committed in the meantime.
3. Write phase. Only if validation succeeds are the local copies made global. If validation fails, the transaction is backed up and restarted as a new one.

Within the paper’s method, where no locks are taken at all, deadlock cannot occur. The paper notes that starvation can — a transaction that keeps failing validation — and discusses how to handle it. It also observes that when most transactions are read-only, validation is often trivial, which is where the optimistic approach looks best.

What it looks like in practice

The pattern is far more common than the name. Any “compare the version, then write” operation is optimistic concurrency control in miniature: an update that includes WHERE version = 7 and fails if another writer already moved it to 8, or an HTTP request with an If-Match header carrying the ETag the client last saw. Amazon S3 supports exactly that precondition on object writes, rejecting a mismatch with 412 Precondition Failed.

Open table formats apply it to whole tables. The Apache Iceberg specification describes writers creating new table metadata optimistically, assuming the current version will not change before they commit, and then committing by swapping the table’s metadata pointer from the version they started from to the new one. If the base snapshot is no longer current, the writer must retry on top of the new current version. Delta Lake’s protocol follows the same shape: write data files first, then claim the next log version.

Some work can be reused after a commit conflict, provided its assumptions still hold. Iceberg’s reliability documentation uses appends as an example: prepared data and manifests can often be included in a new metadata commit. A compaction output is reusable only if the files it replaces remain valid inputs; a concurrent rewrite may instead require failure or replanning and recomputation. Whether optimism is cheaper than holding a lock depends on conflict frequency, reusable work, retry cost, and the blocking or serialization a lock would impose. An expensive retry alone does not decide that comparison.

Iceberg’s specification also shows that “retry” is not always “start over.” Many changes can be re-applied to the new version after checking a condition:

• an append has no requirements and can always be re-applied,
• a replace, such as compaction, must verify that the files it is replacing are still in the table,
• a delete of specific files must verify those files still exist, while a delete by expression can always be applied,
• a schema or partition change must verify that the schema has not changed in between.

Those validation rules are what decide which concurrent operations can coexist, and the specification notes that what a write chooses to validate determines the isolation it provides.

When optimism stops paying

The weakness is contention. If two jobs routinely modify the same data at the same time, writers can repeatedly lose validation, and a failed assumption may make prepared work unusable. One way this shows up in a lakehouse is a compaction job running alongside frequent updates or deletes that rewrite the same files: the compaction’s validation fails because files it meant to replace are no longer in the table, and it retries repeatedly. The usual remedies are to reduce overlap — schedule or partition the work so writers do not collide — and to retry with backoff and a limit rather than immediately and forever.

The other practical point is that the check must itself be atomic. Optimistic control is only safe if “is the version still what I started from” and “install my version” happen as one indivisible step, whether that step is a database update, a conditional write, or a catalog’s check-and-put. How that step is supplied in a lakehouse stack, and why it cannot be taken for granted on object storage, is worked through in Storage, Compute, and Metadata: What Each Layer Actually Owns. Related background: transaction isolation and database deadlocks.

References

• Kung and Robinson, On Optimistic Methods for Concurrency Control (ACM TODS, 1981)
• Apache Iceberg, Table Spec
• Amazon S3 User Guide, Conditional writes
• Apache Iceberg: Reliability — Cost of retries and Retry validation