Basic Timestamp Protocol

With the concepts of Read Timestamp (RTS) and Write Timestamp (WTS) established, we can now formalize the Read Rules of the Basic Timestamp Protocol. These rules define precisely when a read operation is allowed, when it must be rejected, and what updates occur on success.

The read rules embody a simple but powerful principle: a transaction should only read values that existed at the time the transaction logically began. Since transaction timestamps define their position in the serialization order, a transaction with timestamp TS(T) should see the database state as it was at logical time TS(T)—meaning it should only read values written by transactions with smaller timestamps.

Before formalizing the rules, let's understand the underlying principle. In timestamp ordering, we want the execution to be equivalent to running all transactions serially in timestamp order. For reads, this means:

A transaction T with timestamp TS(T) should read the value of X that was most recently written by a transaction with timestamp < TS(T).

But here's the challenge: we're not actually running transactions serially. They're interleaved. So when T tries to read X, the current value might have been written by a transaction T' where TS(T') > TS(T). In this case, T would be reading a "future" value—one that shouldn't exist yet from T's perspective.

The Core Insight:

The Write Timestamp WTS(X) tells us the timestamp of the transaction that wrote the current value of X. If TS(T) < WTS(X), then a younger transaction wrote the current value, and T cannot read it without violating serializability.

Conversely, if TS(T) ≥ WTS(X), the current value was written by an older or equal-aged transaction, which is consistent with T's position in the serialization order.

We now present the complete, formal read rules for the Basic Timestamp Protocol. When transaction T requests to read data item X:

Algorithm: Read(X) by Transaction T

1. IF TS(T) < WTS(X) THEN
       // T is trying to read a value written in T's "future"
       Abort T and restart with new, larger timestamp
       RETURN FAILURE
   END IF

2. // Read is allowed
   Let v = current value of X
   
3. IF TS(T) > RTS(X) THEN
       RTS(X) := TS(T)    // Update read timestamp
   END IF
   
4. RETURN v (success)

Atomicity Requirement:

Steps 1-3 should be atomic (or at least serialized for each data item). Consider what could go wrong without atomicity:

1. T checks WTS(X) = 10, TS(T) = 20, check passes
2. Before T completes the read, T' writes X, setting WTS(X) = 30
3. T reads the new value written by T' (TS(T') = 30 > TS(T) = 20)

T has now read a "future" value despite the initial check passing. Proper implementation requires either:

• Short-lived locks on the timestamp metadata during read processing
• Atomic compare-and-read-and-update operations
• Careful use of memory barriers and atomic primitives

Let's trace the read rules through several scenarios to build intuition.

Example 1: Simple Successful Read

T successfully reads X because its timestamp (25) is greater than the writer's timestamp (15). The RTS is updated to 25, protecting the value from writes by transactions with timestamps between 15 and 25.

Example 2: Read Rejection

T cannot read X because the current value was written by a transaction with timestamp 40, which is greater than T's timestamp 20. After restarting with a larger timestamp (50), the read succeeds.

Example 3: Multiple Concurrent Reads

Real systems must handle various edge cases. Let's examine some important scenarios.

Edge Case 1: Reading After Your Own Write

What happens when a transaction reads data it has previously written?

A transaction can always read its own writes because TS(T) = WTS(X) after T writes X. This is consistent with the intuition that transactions should see their own changes.

Edge Case 2: Reading Newly Inserted Data

When a transaction inserts a new row:

• WTS(X) = TS(T) where T is the inserting transaction
• RTS(X) = TS(T) (initialized to writer's timestamp)

Only transactions with TS ≥ TS(T) can read the new row. This makes sense: the row didn't exist before T, so transactions "older" than T shouldn't see it.

Edge Case 3: Cascading Read Failures

If a transaction reads multiple data items, each read is checked independently. If any read fails, the entire transaction aborts:

1. T(TS=15) reads X — WTS(X) = 10 — Success
2. T(TS=15) reads Y — WTS(Y) = 10 — Success
3. T(TS=15) reads Z — WTS(Z) = 20 — FAIL
4. Abort T, including the effects of reading X and Y

In basic timestamp ordering, the "work" done before the failed read (reads don't modify data, but might have influenced later writes) must be carefully handled during abort.

Edge Case 4: Equal Timestamps

What if TS(T) = WTS(X) exactly?

The condition is TS(T) ≥ WTS(X), so TS(T) = WTS(X) is allowed. This typically happens when:

• T is reading its own write (discussed above)
• Two transactions get identical timestamps (should be prevented by timestamp allocation)

For the second scenario, implementation must ensure unique timestamps through:

• Sub-millisecond clock resolution
• Logical counters appended to physical time
• Tie-breaking using transaction IDs

Read-only transactions present an interesting optimization opportunity. Since they never write, they can never cause write-after-read conflicts. This observation leads to potential optimizations.

The Problem with Naive Read-Only Handling:

In basic timestamp ordering, every read updates RTS(X) (if the reader is younger than all previous readers). For read-only analytical queries scanning millions of rows, this creates massive write amplification—turning read-only workloads into write-heavy workloads.

Correctness of Skipping RTS Updates:

Why is it safe for read-only transactions to skip RTS updates? Consider:

1. RTS(X) is used to check: "Has a younger transaction read X?"
2. This check protects against write-after-read conflicts
3. If T is read-only, it will never write
4. Therefore, no write-after-read conflict can occur involving T
5. RTS(X) doesn't need to record T's read

Caveat: This optimization requires reliable identification of read-only transactions. If a transaction initially appears read-only but later writes, the optimization fails. Systems may require explicit READ ONLY declarations or use speculative execution with fallback.

Implementing the read rules correctly requires careful attention to several practical concerns.

Interaction with Buffer Pool:

When a transaction reads a data item:

1. The page containing X must be in the buffer pool
2. If not, a disk read is required (I/O)
3. The timestamps (WTS, RTS) are part of the tuple or page metadata
4. Timestamps may be updated even for "read-only" page accesses
5. This can cause pages to become dirty (requiring write-back)

Logging Considerations:

For durability and recovery:

• WTS changes are logged with write operations (already part of normal logging)
• RTS changes are more problematic—should read-only transactions generate log records?
• Some systems skip RTS logging and accept approximate RTS after recovery
• Others log RTS updates, increasing log volume but ensuring exact recovery

The read rules we've formalized are one half of the Basic Timestamp Protocol. Let's understand how they fit into the complete picture.

The Asymmetry:

Notice that reads only check WTS (one condition) while writes check both RTS and WTS (two conditions). This asymmetry reflects the different conflict scenarios:

• Reads conflict with: Younger writes (read-after-write)
• Writes conflict with: Younger reads (write-after-read) AND younger writes (write-after-write)

This is why writes are more likely to be rejected than reads—there are more ways for a write to conflict.

The No-Wait Property:

A key feature of the read rules is that they never wait. The decision is immediate:

• If the check passes, proceed immediately
• If the check fails, abort immediately

There's no queue of waiting transactions as in lock-based protocols. This eliminates deadlocks entirely (transactions never wait for each other) but introduces the cost of aborts and restarts.

We've now formalized the complete read rules of the Basic Timestamp Protocol. Let's consolidate the key concepts:

What's Next:

With the read rules complete, the next page formalizes the Write Rules—the more complex algorithm that handles write operations. Write rules must check both RTS and WTS, making them the stricter half of the protocol. We'll also see how the Thomas Write Rule can relax one of these checks to reduce unnecessary aborts.