Basic Timestamp Protocol

In lock-based concurrency control, we prevent conflicts by forcing transactions to wait. But what if we could detect conflicts after they occur and simply abort the offending transaction? This is the fundamental insight behind timestamp-based protocols, and it begins with a deceptively simple question: When was this data item last read?

The Read Timestamp (RTS) is the answer to this question—a metadata field maintained for every data item in the database that records the largest timestamp of any transaction that has successfully read that item. Understanding RTS is essential because it forms half of the conflict detection mechanism that enables timestamp ordering to guarantee serializability without ever blocking a transaction.

Every data item in a timestamp-based system maintains metadata about when it was last accessed. The Read Timestamp (RTS) of a data item X, denoted RTS(X), stores the largest timestamp of any transaction that has successfully read X.

Consider what this means: if RTS(X) = 100, we know that some transaction with timestamp 100 has read X, and no transaction with a timestamp larger than 100 has read X since the current value was written. This seemingly simple piece of information has profound implications for conflict detection.

Formal Definition:

For any data item X in the database:

RTS(X) = max{TS(Ti) | Ti has successfully read X}

This definition captures the essential property: RTS tracks the "youngest" (highest timestamp) transaction that has read the current value of the data item. When a new transaction T reads X:

• If TS(T) > RTS(X), then RTS(X) is updated to TS(T)
• If TS(T) ≤ RTS(X), then RTS(X) remains unchanged (a younger transaction has already read X)

The read timestamp is initialized when a data item is first written—typically set to the write timestamp of the creating transaction.

The read timestamp serves a specific and critical purpose: detecting write-after-read conflicts that would violate serializability. To understand why, we must think about what it means for a schedule to be serializable.

In timestamp ordering, we're trying to ensure that the schedule is equivalent to running all transactions in timestamp order—T1 before T2 if TS(T1) < TS(T2). Now consider what happens if:

1. Transaction T2 (timestamp 20) reads data item X
2. Later, transaction T1 (timestamp 10) tries to write X

In a serial schedule respecting timestamp order, T1 would execute completely before T2 starts. T2 would read the value written by T1. But in our actual execution, T2 has already read X—potentially an old value that T1 hasn't yet updated. This is a temporal violation: T2 has read a value that, in the equivalent serial schedule, wouldn't exist yet.

How RTS Enables Detection:

When transaction T wants to write data item X, the protocol checks:

If TS(T) < RTS(X), then T is trying to write a value that a younger transaction has already read.

This is precisely the write-after-read violation described above. The transaction T must be aborted and restarted with a new (larger) timestamp, giving it a chance to execute without violating the intended serialization order.

Let's trace through a concrete example:

In this example, T1's original attempt to write X fails because T2 (a younger transaction) has already read X. When T1 restarts as T1' with a new timestamp of 25, it becomes younger than T2, and the write is allowed—the serialization order is now T2 before T1', which is consistent with T2 reading before T1' writes.

Understanding exactly when and how RTS is updated is essential for correctly implementing and reasoning about timestamp protocols. The mechanics are straightforward but have important nuances.

The RTS Update Rule:

When transaction T successfully reads data item X:

if TS(T) > RTS(X) then
    RTS(X) := TS(T)
end if

Note the key word successfully. If a read operation is rejected (which, as we'll see, can happen in certain cases), the RTS is not updated. Only reads that actually return data to the transaction affect the timestamp.

Implementation Considerations:

In practice, maintaining read timestamps introduces storage overhead—every data item needs an additional field. For tuple-level granularity, this means every row in every table has an RTS field. The update operation must also be atomic, which can create contention on frequently-read items.

Some systems optimize by:

1. Lazy RTS Updates: Batching updates to reduce write amplification
2. Approximate RTS: Using epoch-based timestamps rather than precise values
3. Probabilistic Tracking: Only tracking RTS for "hot" data items
4. Hybrid Approaches: Combining RTS with locks for specific access patterns

These optimizations trade precision for performance, but must be carefully designed to preserve correctness.

Read timestamps don't work in isolation—they're one half of a dual-timestamp system. Each data item maintains both:

• RTS(X): The largest timestamp of any transaction that has read X
• WTS(X): The largest timestamp of any transaction that has written X

Together, these timestamps form a complete picture of how a data item has been accessed, enabling the protocol to detect both write-after-read and read-after-write conflicts.

The Serialization Principle:

The combination of RTS and WTS enforces a fundamental invariant: operations occur in timestamp order. Specifically:

• If T2 reads X after T1 wrote X, then TS(T2) > TS(T1) (enforced by WTS)
• If T1 writes X after T2 read X, then TS(T1) > TS(T2) (enforced by RTS)

Any violation of these conditions indicates a non-serializable access pattern and triggers an abort. The beauty of this approach is that we never block—we either allow the operation immediately or abort and retry.

This is in stark contrast to locking protocols where transactions wait for locks. Timestamp ordering trades potential blocking for potential aborts, which can be advantageous in systems where most transactions don't conflict and waiting is costly.

Let's work through several examples to solidify understanding of how RTS behaves in various scenarios.

Example 1: Sequential Reads by Increasingly Younger Transactions

In this simple case, each successive read is by a younger transaction, so RTS is updated each time. After all reads, RTS(X) = 50, indicating that no transaction with TS < 50 can safely write X.

Example 2: Out-of-Order Reads

This example shows that once a young transaction reads, RTS "locks in" that high value. Older transactions can still read (reads almost always succeed in basic timestamp ordering), but they don't affect RTS.

Example 3: Write Rejection Due to RTS

Example 4: Same-Timestamp Tie-Breaking

What if two transactions have the same timestamp? In practice, true timestamp collisions are prevented by:

1. Sufficient Resolution: Nanosecond clocks or logical counters ensure uniqueness
2. Transaction ID Tie-Breaking: If TS(T1) = TS(T2), use transaction ID as secondary sort
3. Hybrid Timestamps: Combine physical time with logical sequence numbers

For theoretical analysis, we assume all timestamps are unique. In implementation, the system must guarantee this property.

Maintaining read timestamps has real performance costs that database designers must carefully consider. Unlike write timestamps (which are updated only on writes), RTS is updated on every read—and reads are typically far more common than writes.

The Write Amplification Problem:

Consider a pure read-only analytics query scanning a million rows. In a naive timestamp implementation, this query would:

1. Read 1,000,000 tuples
2. Compare TS(T) with RTS for each
3. Update RTS for many of them (potentially all)
4. Write 1,000,000 RTS updates back to storage

What should be an I/O-read-only workload becomes half reads, half writes—drastically increasing latency and system load.

Optimization Strategies:

We've explored the first critical component of the Basic Timestamp Protocol. Let's consolidate the key concepts:

What's Next:

Now that we understand read timestamps, the next page examines Write Timestamps (WTS)—the complementary mechanism that tracks when data items were last written. Together, RTS and WTS form the foundation upon which the complete timestamp ordering protocol is built.