Real-Time Database Systems Aren't Actually Real-Time. Unless They Are.

What you'll learn:

• Why external consistency is so important for a hard real-time database.
• Maintaining a transaction timeline.
• The impact of a transaction-scheduling policy.
  

A real-time database-management system (DMBS) for mission- and safety-critical systems is substantially different from a DBMS that’s used in other embedded systems, so perhaps we should start by defining a few terms for our purposes.

Hard real-time software fails if a timing deadline isn’t met. Mission-critical software can cause catastrophic consequences (such as someone dying, damage to property, severe financial losses, etc.) if it fails. An advanced driver-assistance system (ADAS) is mission-critical and hard real-time. An electronic trading system is mission-critical, but not hard real-time. An inkjet printer is hard real-time, but not mission-critical.

In other words, in hard real-time systems, there’s a line in the sand with significant consequences. In the context of a real-time database system, the line in the sand is the transaction deadline (Fig. 1). Crossing the line means the transaction was late, so the real-time system wasn’t able to respond to an event within the predefined timing constraint. In an ADAS, system failure might mean a car accident.

External Consistency

Therefore, a key tenet for a hard real-time database is deadline management, or external consistency. External consistency means that the content of the database reflects the real world within some time constraint. To achieve this, transactions must be completed within pre-set deadlines.

In a hard real-time database system, “complete” means meeting the deadline by successfully committing or successfully aborting before the deadline. Transactions can never be late; they must meet deadlines to reflect the state of the real-world or notify interested systems that the transaction missed the deadline (was aborted, but within the deadline). For the sake of reliability, a hard real-time database management should (but isn’t required to) enforce internal consistency just like any other ACID (atomicity, consistency, isolation, durability) database.

Real-Time Database System Performance Metric

Hard real-time doesn’t mean real fast. Database and software vendors have been using the term real-time synonymously with instant or live for years. A mission-critical hard real-time data manager might want speed but must be deterministic. In other words, it must work with a RTOS to set and enforce transaction deadlines.

Performance is measured by the ratio of transactions that meet their deadline (are successfully committed) to the number of transactions that miss their deadline (are successfully aborted before the deadline). Speed isn’t a metric used to rate a real-time database system.

Transaction Timeline

As you know, a database transaction is not necessarily a single operation, though it may be. It may be a sequence of operations such as looking up one record, deleting five related records, and updating a field within the original record that must all succeed or fail together. Likewise, a single update or delete command that affects 1 or 100 records must succeed for all, or for none.

A transaction begins when the application code invokes it. If the database system is busy with one or more other conflicting transactions, the newly created transaction will be put in a waiting queue, but the clock on its deadline has already started. It’s theoretically possible that a transaction will timeout without ever getting scheduled for execution, but not in a well-designed real-time system. Figure 2 illustrates the timeline of a real-time transaction.

Once scheduled, the transaction begins executing the workload interval. The database runtime can’t be a black hole from which emergence is indeterminate. In other words, when the system makes a call to the database runtime, the task can’t disappear inside the database runtime for an indeterminate amount of time, possibly exceeding the deadline before the database runtime returns control to the application (Fig. 3).

The database runtime needs to be aware of the deadline. It must be constantly looking at the clock and be able to return control to the application before it’s too late to abort the transaction and allow it to finalize before the deadline. This is the deadline control point.

The ability to deterministically establish the deadline control point depends on being able to know with certainty the time required to abort a transaction. Through implementation of new real-time database transaction schedulers, we can assert that the time required to roll back the changes within a transaction isn’t more than the time required to apply those same changes.

Therefore, if the transaction deadline is T, the deadline control point is T/2. In reality, aborting a transaction can be substantially faster than the time taken to apply the transaction up to a point in time. So, half of the real deadline is a worst-case scenario that can be adjusted based on empirical data collected during testing and simulations (Fig. 4).

Real-Time Transaction Scheduling

The transaction-scheduling policy has an impact on the ratio of completed to aborted transactions. First and foremost, a transaction scheduler must enforce the transaction deadline. Then it must attempt to maximize the number of tasks that successfully commit their transactions relative to the number of tasks that have their transactions aborted.

One such policy is high priority/earliest deadline first (EDF), and a second is priority inheritance (PI). With EDF, transactions are scheduled according to priority, and within the same priority by the earliest deadline. A transaction’s priority is another parameter passed to the transaction scheduler through the transaction start command, along with the deadline.

Priority inheritance schedules transactions that have the same priority in first-in-first-out (FIFO) order, without regard to their deadlines.

The major difference between the EDF and PI TMs is that with the EDF manager, the database kernel organizes the queue and determines transaction execution order. In the PI case, the execution order is FIFO without respect to deadlines.

However, PI raises a lower priority task’s priority to that of a higher priority task when the higher priority task begins a database transaction—it lets the lower priority task preempt tasks of lower priority than the new high priority task. This, in turn, enables the lower priority transaction to be completed quickly and get out of the way of the high priority task. Different application patterns can take advantage of different transaction schedulers.

Conclusion

In summary, a real-time database may be fast, but must be deterministic and guarantee external consistency. When discussing data management, speed is always a performance metric.

However, in hard real-time databases, the performance metric that counts most is the number of transactions that successfully commit instead of successfully rolling back on time so that the system can always react instantaneously to mission-critical events. If a database can’t guarantee external consistency, it’s not hard real-time, and could cause the failure of a mission-critical system.