Concurrency Control, Part III: How Databases Finalise a Conflict-Free Schedule

In my last post, we saw how databases handle conflicts through different philosophies i.e., prevention, validation, versioning, and observation, allowing transactions to run concurrently without violating serializability.

But avoiding or resolving conflicts isn’t the end of the story. Even after all conflicts are managed, the database still has one more job: deciding the final serial order, the single sequence of transactions that the world will observe as if they ran one after another.

Conflict-free execution keeps the system consistent, but only an agreed order makes it deterministic.

What does it means to “Finalize a Schedule”?

In my earlier post, we discussed what conflict-free schedules really are. Let’s briefly revisit that idea.

Given four operations:

The only conflict is on Y between T1′ and T2 (WW). Everything touching X and Z is independent.

This gives us two kinds of constraints defining a conflict-free schedule:
1. Intra-transaction order: T1 < T1′, and T2 < T2′
2. Conflict constraint on Y:
  • If the serial order is T1 -> T2, then T1′ < T2
  • If the serial order is T2 -> T1, then T2 < T1′

Conflict-serializable interleavings can therefore be defined as:

1. Equivalent to serial order T1 -> T2:
Only one schedule satisfies all constraints: T1, T1′, T2, T2′

2. Equivalent to serial order T2 -> T1:
Five valid interleavings:
  1. T1, T2, T1′, T2′
  2. T1, T2, T2′, T1′
  3. T2, T1, T1′, T2′
  4. T2, T1, T2′, T1′
  5. T2, T2′, T1, T1′

Now when we say a schedule is serializable, we mean it’s equivalent to some serial order i.e., either T1 -> T2 or T2 -> T1, but not which one. At runtime, any of these valid schedules could become reality, finalizing one of the two serial orders.

Deciding Order Without Time

Most real systems infer the serial order order causally, not temporally. That is, they don’t use physical clocks to decide who came first; they deduce it from how transactions interact. This distinction is what separates practical concurrency control from timestamp-based idealism.

Early database theory imagined a world where timestamps alone could define serial order i.e., assign every transaction a global timestamp and enforce that all reads and writes follow that order. This approach, known as Timestamp Ordering (TO), looks elegant on paper but collapses in practice. The moment clocks drift, transactions overlap, or causal dependencies contradict assigned timestamps, the system ends up aborting correct transactions simply because time said they were out of order.

Thomas Write Rule (TWR) tried to soften this rigidity by allowing obsolete writes from older transactions to be ignored but its rested on a flawed assumption i.e., that order can be assigned ahead of time, rather than discovered through causality.

Real systems learned that time doesn’t define order, dependencies do. Hence, modern concurrency control infers serial order from observed interactions, not from timestamps.

Different concurrency-control mechanisms do this differently, each establishing serial order through the rules it enforces.

Pessimistic Control: Serial by Construction

Two-Phase Locking (2PL) finalizes serial order through ownership. Whoever acquires the lock first goes first.

Transactions acquire all necessary locks before modifying data, and release them only after commit. This ensures that later transactions can’t reorder past earlier ones i.e., the lock acquisition order defines the serial order directly.

It’s serial-by-construction. Its safe, predictable, but potentially blocking.

Pros: Strong isolation, deterministic order
Cons: Contention and deadlocks under heavy concurrency

Optimistic Control: Order by Validation

Optimistic Concurrency Control (OCC) takes the opposite approach. It doesn’t decide order during execution but discovers it at commit time.

Each transaction executes freely, recording what it read and wrote. At commit, the validator checks for overlaps. If two transactions wrote or read the same data, it decides which one logically came first and aborts the other if needed.

Thus, the commit phase defines the serial order. The winner’s commit time marks its position; the loser restarts.

Pros: High concurrency for low-contention workloads
Cons: Abort-heavy under high write overlap

MVCC: Order Through Snapshots

Multi-Version Concurrency Control (MVCC) finalizes order more subtly. Instead of choosing who comes first, it gives each transaction its own consistent past.

Every transaction reads from a snapshot, a version of the database containing only the commits visible at its start. When it finally commits, the system checks whether its writes still make sense given the current state. If yes, it becomes the next commit in that order; if not, it aborts and retries.

In this way, snapshots themselves define a partial order, and the database finalizes it at commit by ensuring each snapshot can still fit into a consistent serial story.

MVCC doesn’t pre-assign order, it discovers it naturally, one consistent snapshot at a time.

Pros: Non-blocking reads, great scalability
Cons: Doesn’t detect all anomalies (e.g., write skew) without extra tracking

Dependency Tracking: Order by Observation

While MVCC gives each transaction its own consistent snapshot, it doesn’t verify whether all those snapshots can coexist in a single serial history.
This is what leads to write skew, the subtle anomaly we explored in my previous blog.

Dependency tracking fills that gap. It continuously observes read-write dependencies between transactions and maintains a directed graph of who depends on whom.

If the graph ever forms a cycle, meaning two transactions can’t both exist in any serial order, the system aborts one to break the loop. The remaining graph defines a valid topological order, which becomes the finalized serial schedule.

This is how Serializable Snapshot Isolation (SSI) works: MVCC gives isolation; dependency tracking enforces order.

Pros: Achieves serializability without blocking
Cons: More bookkeeping; possible “serialization failures”

Conclusion

Concurrency control ensures transactions don’t break consistency while finalizing a schedule that turns concurrency into order.

Together, concurrency control mechanisms make concurrent execution look serial without relying on clocks, global order, or coordination. The order is infered causally, through dependencies formed between reads and writes, not by the ticking of time.

It is important to realise here that conflict-free doesn’t mean order-free. Every serializable schedule still needs a final sequence, one discovered through dependencies, not dictated by timestamps.

That said, time isn’t entirely irrelevant. While it plays no part in deciding transaction order at commit, it becomes essential soon afterwards i.e., to preserve that established order during replication and recovery.

In replication, each committed transaction is assigned a logical or physical timestamp (like a Log Sequence Number) so that followers can replay updates in the exact same causal order. During recovery, the same timestamps ensure the database can rebuild state deterministically from logs, maintaining the precise sequence of effects that existed before a crash.

References

1. Database Internals
2. Designing Data-Intensive Applications