Quartz 4

26.5 Real-Time Transaction Systems

4 min read

Introduction and Core Concepts

  • Definition: Real-time systems are systems where the correctness of the system depends not only on the logical result of computation (database consistency) but also on the time at which the results are produced. Meeting deadlines is crucial.

  • Contrast with Traditional Systems: In traditional database systems, the primary focus is on maintaining data integrity and consistency (ACID properties). While speed is important, meeting specific time constraints is not the primary goal.

  • Integrity Constraints: Traditional integrity constraint concern with the values stored in database.

Deadlines

  • Definition: A deadline is a time constraint by which a task (or transaction) must be completed. Failure to meet a deadline has varying consequences depending on the type of deadline.

  • Types of Deadlines:

    • Hard Deadline:
      • Definition: If a task misses a hard deadline, catastrophic consequences or system failure may occur.
      • Example: A critical control system in a nuclear power plant failing to respond within a specific time window.
    • Firm Deadline:
      • Definition: If a task misses a firm deadline, the result of the task has zero value. It’s as if the task never happened.
      • Example: A system processing stock trades. If a trade order is not executed by its deadline, the opportunity is lost, and the order is useless.
    • Soft Deadline:
      • Definition: If a task misses a soft deadline, the value of the result diminishes over time. The value may approach zero as the lateness increases.
      • Example: A weather forecasting system. A forecast delivered late is less useful than one delivered on time, but it might still have some value. The value decreases the later it gets.

Transaction Management with Deadlines

  • Key Challenge: Standard transaction management techniques (locking, timestamping, etc.) can introduce delays that cause transactions to miss deadlines. The primary goal is to minimize missed deadlines while still ensuring some level of data consistency.

  • Priority Inversion Problem: A higher-priority transaction (with a nearer deadline) might be blocked by a lower-priority transaction holding a required lock. This is a major issue in real-time systems.

  • Pre-emption:

    • Definition: Interrupting a currently running transaction (that holds a needed resource) to allow a higher-priority transaction (with a closer deadline) to proceed.
    • Trade-offs:
      • Benefit: The higher-priority transaction is more likely to meet its deadline.
      • Drawback: The pre-empted transaction may also miss its deadline due to the time lost (rollback and restart). It’s difficult to determine the optimal strategy in all cases.

  • Rollback vs. Waiting: When a transaction needs a resource held by another, the system must decide whether to make the requesting transaction wait or to roll back (abort) the transaction holding the resource. This decision is complex and depends on factors like deadlines, remaining execution time, and the criticality of the transactions.

Challenges with Variance in Execution Time

  • Source of Variance: The execution time of a transaction in a database system can vary significantly. This variance makes it extremely difficult to predict whether a transaction will meet its deadline. Sources include:

    • Best Case: All required data is in the database buffer (main memory). No disk I/O is needed. Execution is fast.
    • Worst Case: Every data access requires a disk I/O (reading the data page, possibly after writing a dirty page to disk first, and potentially preceded by writing log records). Disk I/O is orders of magnitude slower than main memory access.
    • Other Factors: Lock waits, transaction aborts (and subsequent restarts), network delays (in distributed systems).
    • Lock wait, transaction abort, and so on.

  • Impact on Real-Time Systems: This high variance makes it challenging to guarantee that deadlines will be met. Traditional database systems, with their unpredictable disk I/O times, are often unsuitable for hard real-time applications.

  • Mitigation Strategies:

    • Main-Memory Databases: Storing the entire database (or the critical parts) in main memory eliminates the major source of variance (disk I/O). This is a common approach in real-time systems.
    • Concurrency Control: Using extended locking protocols to provide higher priority for transaction with early deadlines.
    • Optimistic Concurrency: Using Optimistic concurrency protocols.

  • Design Considerations: Even with mitigation, designing real-time systems involves:

    • Sufficient Processing Power: Ensuring that the system has enough computational resources to handle the workload and meet deadlines, even with some variance in execution times.
    • Resource Allocation: Carefully managing system resources to minimize the chances of deadline misses. This is a complex optimization problem.

Concurrency Control

  • Researchers have devoted considerable effort to concurrency control for real-time databases.
  • Locking: They have extended locking protocols to provide higher priorities for transactions with early deadlines.
  • Optimistic Concurrency: They have found that optimistic concurrency protocols perform well in real-time databases. These protocol results in fewer missed deadlines than even the extended locking protocols.

Graph View

Backlinks