Loading learning content...
In the previous page, we explored Read Timestamps (RTS)—metadata that tracks which transactions have read a data item. RTS detects write-after-read conflicts. But what about the complementary scenario: a transaction trying to read a value that was written by a transaction that should come after it in the serial order?
This is a read-after-write conflict, and detecting it requires knowing when data was last written. Enter the Write Timestamp (WTS)—the second half of our timestamp-based conflict detection mechanism. Together with RTS, WTS completes the picture that allows the Basic Timestamp Protocol to guarantee serializability.
By the end of this page, you will understand what write timestamps are, how they differ from read timestamps, when and how they're updated, and how they enable detection of read-after-write and write-after-write conflicts. You'll see how RTS and WTS together form a complete conflict detection system.
Every data item in a timestamp-based system maintains a Write Timestamp (WTS), denoted WTS(X), which stores the timestamp of the transaction that wrote the current value of X.
Unlike RTS, which tracks the maximum timestamp across all readers, WTS records the timestamp of a single transaction—specifically, the one that produced the current value. When a new transaction writes X, the WTS is updated to that transaction's timestamp, effectively "tagging" the value with its creator's identity.
Formal Definition:
For any data item X in the database:
WTS(X) = TS(Ti) where Ti is the transaction that last wrote the current value of X.
This is simpler than RTS because there's always exactly one writer of the current value. When transaction T writes X:
The write timestamp establishes the "birth time" of the current value. Any transaction trying to read this value must have a timestamp at least as large as WTS(X) to maintain serialization order.
| Property | Description | Significance |
|---|---|---|
| Single Writer | WTS identifies exactly one transaction | Unlike RTS which tracks maximum of many |
| Value-Coupled | WTS changes when value changes | Old WTS lost when new write occurs |
| Establishes Read Floor | TS(T) must be ≥ WTS(X) to read X | Prevents reading 'future' values |
| Write Ordering | Controls which writes are accepted | Older writes of newer values rejected |
RTS tracks the 'youngest reader' (largest timestamp), representing a constraint on future writers. WTS tracks the 'creator' of the current value, representing a constraint on all readers. RTS is about 'who has seen this,' while WTS is about 'who made this.'
Write timestamps serve two critical purposes in the Basic Timestamp Protocol:
Purpose 1: Detecting Read-After-Write Conflicts
Consider this scenario:
In a serial schedule respecting timestamp order, T1 would execute completely before T2 starts. T1 would read the value of X that existed before T2's write. But in our actual execution, T2 has already written X—T1 would be reading T2's value, which shouldn't exist yet from T1's perspective.
When an older transaction (smaller timestamp) tries to read a data item that a younger transaction (larger timestamp) has already written, we have a temporal violation. The older transaction would be reading a 'future' value. WTS(X) lets us detect exactly this: if TS(T) < WTS(X), T is trying to read a value written in its 'future.'
Purpose 2: Detecting Write-After-Write Conflicts
WTS also detects when an older transaction tries to overwrite a value written by a younger transaction:
If we allowed T1's write, we'd be replacing T2's value with T1's—but T2 is supposed to come after T1 in any equivalent serial schedule. The final value should be T2's, not T1's.
The WTS check for writes:
If TS(T) < WTS(X), then T is trying to overwrite a value written by a younger transaction.
This scenario has two possible resolutions:
| Scenario | Condition | Meaning | Action |
|---|---|---|---|
| T reads X | TS(T) < WTS(X) | T trying to read future value | Abort T |
| T writes X | TS(T) < WTS(X) | T trying to overwrite future value | Abort T (or ignore via Thomas Write Rule) |
| T reads X | TS(T) ≥ WTS(X) | T reading appropriately old value | Allow read |
| T writes X | TS(T) ≥ WTS(X) | T writing as expected | Check RTS, then allow |
Understanding the precise mechanics of WTS updates is essential for implementing and reasoning about timestamp protocols. Unlike RTS which accumulates information across reads, WTS is simply replaced on each write.
The WTS Update Rule:
When transaction T successfully writes data item X with value v:
X := v
WTS(X) := TS(T)
RTS(X) := TS(T) // Reset read timestamp
The write operation completely replaces the old value and its metadata. The new value is "born" with:
Why Reset RTS on Write?
When transaction T writes X, any previous reads of X were reads of the old value. Those read timestamps are associated with the old value, not the new one. Resetting RTS to TS(T) effectively starts fresh—the new value has only been "seen" by its creator.
This is conceptually different from RTS's behavior during reads. Reads accumulate information (capturing the youngest reader), while writes discard old information (since the old value no longer exists).
Practical Consideration: Write Visibility
In many implementations, the WTS update isn't immediately visible to other transactions. The new value might be buffered until transaction commit. This introduces complexity around when exactly WTS(X) reflects the pending write vs. the committed value—a topic we'll revisit when discussing strict timestamp protocols.
Think of WTS as a signature. Just as an author signs their work, a transaction 'signs' the data it writes with its timestamp. This signature tells future transactions exactly when this value came into existence, allowing them to determine if reading it would violate serialization order.
With both timestamps defined, we can now see the complete conflict detection mechanism. For each data item X, we maintain:
These two timestamps work in concert to enforce timestamp-ordered execution without locks.
| Operation | Check Against | Condition for Success | On Failure |
|---|---|---|---|
| T reads X | WTS(X) | TS(T) ≥ WTS(X) | Abort T |
| T writes X | RTS(X) | TS(T) ≥ RTS(X) | Abort T |
| T writes X | WTS(X) | TS(T) ≥ WTS(X) | Abort T (or Thomas Write Rule) |
Understanding the Checks:
For Reads:
For Writes:
By enforcing that all operations respect timestamp order (older transactions see older values, newer transactions see newer values), the protocol guarantees that the resulting schedule is equivalent to executing all transactions serially in timestamp order. No locks, no waiting—just checks and potential aborts.
Let's work through several examples to solidify understanding of WTS behavior and its interaction with RTS.
Example 1: Sequential Writes by Increasingly Younger Transactions
| Step | Transaction | Operation | WTS(X) Before | WTS(X) After | RTS(X) After |
|---|---|---|---|---|---|
| 1 | T10 (TS=10) | Write(X, 'A') | 0 | 10 | 10 |
| 2 | T25 (TS=25) | Write(X, 'B') | 10 | 25 | 25 |
| 3 | T40 (TS=40) | Write(X, 'C') | 25 | 40 | 40 |
In this ideal scenario, writes occur in timestamp order. Each write succeeds, and both WTS and RTS are updated to the writer's timestamp.
Example 2: Read-After-Write Conflict
| Step | Transaction | Operation | Check | Result |
|---|---|---|---|---|
| 1 | T30 (TS=30) | Write(X, 'V') | TS(30) ≥ WTS(0)? Yes | Success, WTS(X)=30 |
| 2 | T10 (TS=10) | Read(X) | TS(10) ≥ WTS(30)? No | ABORT T10 |
| 3 | T10 restarts as T40 | — | New timestamp | — |
| 4 | T40 (TS=40) | Read(X) | TS(40) ≥ WTS(30)? Yes | Success, RTS(X)=40 |
T10 cannot read the value written by T30 because T10 is "older" and shouldn't see T30's work. After restart with timestamp 40, T40 > T30, so the read is allowed.
Example 3: Write-After-Write Conflict
| Step | Transaction | Operation | Check | Result |
|---|---|---|---|---|
| 1 | T50 (TS=50) | Write(X, 'New') | TS(50) ≥ WTS(0)? Yes, TS(50) ≥ RTS(0)? Yes | Success, WTS(X)=50 |
| 2 | T20 (TS=20) | Write(X, 'Old') | TS(20) ≥ RTS(50)? No | ABORT T20 |
In Example 3, T20 fails the RTS check (TS(20) < RTS(50)), not the WTS check. This is because when T50 wrote, it reset RTS to 50. T20's write would affect a reader (T50 itself) that already 'saw' the new value. The WTS check would also fail (20 < 50), providing a second reason to reject.
Example 4: Complex Interleaving
Let's trace a more complex scenario with multiple data items:
| Step | Transaction | Operation | X State | Y State | Result |
|---|---|---|---|---|---|
| 1 | Initial | — | WTS=0, RTS=0 | WTS=0, RTS=0 | — |
| 2 | T20 | Read(X) | RTS→20 | — | Success |
| 3 | T30 | Write(Y, v1) | — | WTS→30, RTS→30 | Success |
| 4 | T10 | Write(X, v2) | Check: 10 ≥ RTS(20)? | — | ABORT T10 |
| 5 | T40 | Read(Y) | — | RTS→40 | Success (40 ≥ WTS(30)) |
| 6 | T25 | Read(Y) | — | RTS remains 40 | Success (25 ≥ WTS(30)) |
This example shows:
Notice how the timestamps create a consistent ordering despite the interleaved execution.
Understanding how WTS behaves across a data item's entire lifecycle—from creation through multiple updates—provides deeper insight into timestamp-based concurrency control.
Initial Creation:
When a data item X is first created (e.g., inserting a new row):
The item is "born" with both timestamps set to its creator's timestamp.
Successive Updates:
Each write operation completely replaces the old value and its metadata:
[Value: old_v, WTS: old_ts, RTS: old_rts]
→ [Value: new_v, WTS: TS(T), RTS: TS(T)]
The old value and its entire access history are discarded. This is a fundamental difference from MVCC, where old versions are retained.
Deletion:
Deleting a data item in basic timestamp ordering is treated as a write with a special "tombstone" value:
Unlike lock state (which persists across a transaction's lifetime), timestamp metadata represents a snapshot of 'who has accessed what.' Each write resets this state. This means timestamp protocols don't suffer from lock accumulation effects, but also can't leverage prior lock acquisition for optimization.
Version History (Preview of MVCC):
In basic timestamp ordering, writes destroy previous values. This creates a problem: if a transaction is aborted, its writes must be undone, but the old value is gone. Solutions include:
The inefficiency of options 1 and 2, combined with the elegance of option 3, is why MVCC has largely superseded pure timestamp ordering in modern systems.
Having explored both timestamps in depth, let's directly compare their characteristics and roles in the protocol.
| Characteristic | RTS (Read Timestamp) | WTS (Write Timestamp) |
|---|---|---|
| Semantics | Largest TS of any reader | TS of the writer |
| Updates On | Successful reads | Successful writes |
| Update Type | max(current, new) | Replace with new |
| Constrains | Write operations | Read and write operations |
| Conflict Detected | Write-after-read | Read-after-write, Write-after-write |
| Reset Behavior | Reset by new writes | Set by each write |
| Monotonicity | Non-decreasing until write | Changes with each write |
| Cardinality | Tracks multiple transactions | Tracks single transaction |
RTS and WTS are perfectly complementary: RTS handles the 'read before write' ordering, while WTS handles the 'write before read' ordering. Together, they ensure that all operations, both reads and writes, occur in a sequence consistent with timestamp order.
We've now explored both halves of the timestamp-based conflict detection mechanism. Let's consolidate the key concepts about WTS:
What's Next:
With both RTS and WTS understood, we're ready to see how they're used in practice. The next page formalizes the Read Rules of the Basic Timestamp Protocol—the complete algorithm for handling read operations, including when to allow, when to abort, and how to update timestamps.
You now understand both timestamp types used in the Basic Timestamp Protocol. RTS tracks the youngest reader (constraining writes), while WTS identifies the value's creator (constraining reads). Next, we'll formalize how these timestamps are used in the protocol's read rules.