What is Timestamp-Based Concurrency Control?

Timestamp-based concurrency control is a technique used in databases to ensure that transactions are executed in a serializable order based on their timestamps. Each transaction is assigned a unique timestamp when it starts, which determines its logical order. Transactions must follow this order to prevent conflicts and ensure consistency.

• Key Idea: Transactions are executed as if they were processed sequentially, based on their timestamps.
• Guarantee: This method ensures serializability, which means the results of concurrent transactions are the same as if they were executed one after another.

Key Concepts in Timestamp-Based Concurrency

• Transaction Timestamp (TS):

  • A unique identifier assigned to each transaction at its start time.
  • Ensures the logical order of execution.

• Read Timestamp (RTS) and Write Timestamp (WTS):

  • Associated with each data item in the database.
  • RTS: The highest timestamp of any transaction that successfully read the data.
  • WTS: The highest timestamp of any transaction that successfully wrote to the data.

How Timestamp Ordering Works

The flowchart illustrates the process of timestamp-based ordering:

1. Transaction Begins:

   • A transaction is initiated and assigned a unique timestamp (e.g., based on the system clock).

2. Validation Phase:

   • Before execution, the transaction checks for conflicts with other transactions based on timestamps.
   • Validation Logic:
     • If a transaction's timestamp is lower than another transaction's timestamp, it must execute before the conflicting transaction.
     • If the condition is not met, the transaction is rolled back or restarted.

3. Execution Phase:

   • If validated, the transaction proceeds to execute its operations (read/write).
   • During execution:
     • Read Operation: Allowed if the transaction's timestamp is greater than or equal to the data's WTS.
     • Write Operation: Allowed if the transaction's timestamp is greater than or equal to the data's RTS.

4. Conflict Resolution:

   • If a conflict is detected during validation or execution:
     • A conflict resolution strategy is applied.
     • The conflicting transaction may be aborted and restarted with a new timestamp.

5. Successful Execution:

   • If no conflicts occur, the transaction successfully completes and updates the database.

How Read and Write Operations Work

• Read Operation:

  • If a transaction's timestamp (TS) is ≥ WTS of the data item:
    • The transaction is allowed to read, and the RTS of the data is updated.
  • If TS is < WTS:
    • The transaction is aborted because it is trying to read outdated data.

• Write Operation:

  • If TS is ≥ RTS and ≥ WTS:
    • The transaction writes to the data, and the WTS is updated.
  • If TS is < RTS:
    • The transaction is aborted to prevent overwriting data read by newer transactions.

Advantages of Timestamp-Based Concurrency Control

• No Deadlocks: As no locks are used, the system avoids deadlocks entirely.

• Ensures Serializability: Transactions are processed logically in the order of their timestamps, maintaining consistency.

• Simple Conflict Resolution: Conflicts are easily detected and resolved by aborting the conflicting transaction.

Disadvantages of Timestamp-Based Concurrency Control

• High Rollback Rates: Transactions with outdated timestamps may frequently fail and need to restart, leading to wasted resources.

• Starvation: Older transactions might repeatedly get aborted if newer transactions conflict with them.

• Overhead: Maintaining timestamps and checking read/write conditions add computational overhead.

Example Scenario of Online Ticket Booking System

• Transaction A starts at 10:00 AM and tries to read the available tickets.
• Transaction B starts at 10:01 AM and books one ticket, reducing availability.
• Transaction A tries to book tickets after reading outdated data. The system detects a conflict and rolls back Transaction A to prevent inconsistency.