Keeping A Mission-Critical Deterministic DBMS On Time
September 20, 2021
Blog
Open-source and commercial database management systems (DBMSs) have been used in embedded systems for more than 20 years. For the most part, developers don't even debate whether to buy or build their own DBMS for embedded systems; that component is almost always bought.
However, one subset of the embedded systems space remained off-limits for commercial vendors, including certain medical systems, radiation monitoring, aircraft navigation, avionics, pilot assistance, and most recently, autonomous driving. Altogether, they can be called mission-critical or safety-critical systems with hard real-time constraints, where system failure is likely to cause harm.
Many mission-critical software teams are looking at commercial off-the-shelf (COTS) software to speed up development. An embedded DBMS could help, but only if it’s deterministic, predictable, and controllable. A deterministic DBMS architecture for mission-critical systems should provide ACID (atomicity, consistency, isolation, durability) compliance with temporal validity.
Doesn’t every DBMS enforce ACID properties? ACID-compliant databases are common, but are architected for transaction throughput, not determinism. Consistency is the most important property; transactions should only change the database from one valid state to another. In a real-time system, either an atomic set of statements in a transaction should commit successfully, or should all abort, but should never be in progress after deadline. “Late” brings an inconsistent state, with temporally invalid data and possible dire consequences.
A Critical Temporal Assertion for Consistency
Ensuring internal database consistency under all conditions is critical for temporal validity. Embedded databases offer some improvement in execution efficiency, but more architectural steps are needed for a deterministic DBMS to stay on time.
First, pessimistic concurrency control should be used. It locks all or part of the database before granting one task access, cutting the indeterminate overhead of copying in the optimistic model. Read-only (RO) transactions can occur in parallel, while a read-write (RW) transaction has exclusive access, reducing resources for lock arbitration and deadlock prevention.
Next, a critical temporal assertion accounts for workload and rollback against a deadline:
The time to reverse any modifications up to any point in a transaction cannot exceed the time to apply those modifications, regardless of transaction complexity.
RO transactions have index lookup and cursor movement operations; rollback undoes any incrementing or decrementing of internal counters in an equal interval.
Simpler RW transactions are easy to rollback. Creating an object allocates pages from the free memory pool depending on object size; reversal simply returns those pages to the pool. Other transactions don’t need reversal at all. Removing an object marks it for deletion in an atomic operation, so if the transaction aborts, the deletion at commit doesn’t occur. Adding or removing objects into and from indexes has tree rebalancing or hash reallocation which take effect only at commit and don’t require reversal.
Updating objects looks more complex but turns out to be an efficient operation. The first time a transaction updates an object, a temporary object is allocated, then the original object is copied to the temporary one. Subsequent updates go faster with the copy already created. A rollback recreates the original object from the copy in reverse order, then releases the allocated memory pages, with rollback time for an object being independent of the number of updates to that object.
Verifying Transactions Against Real-Time Deadlines
With each transaction ensured to commit or abort safely, scheduling a stream of transactions comes next. Recall pessimistic concurrency; RW transactions must be executed sequentially, while RO transactions can be parallelized. For example, dynamic, time-aware Earliest Deadline First (EDF) scheduling in McObject’s eXtremeDB/rt assigns priorities to transactions according to the absolute deadline.
Verification points in the transaction manager code indicate how far transaction statements have progressed. If a transaction reaches the control point—the time at which database rollback is no longer guaranteed to make the deadline—before committing, a “transaction interrupted” error status returns to the application. The transaction manager restores the database to the consistent state existing prior to the start of the transaction.
In eXtremeDB/rt, applications can use two verification methods: an application callback passed to the database runtime, or an asynchronous event handler. The following examples set the control point to half of the deadline interval, which can be adjusted.
Callback Method Pseudo-Code
If asynchronous primitives such as a system timer or hardware watchdog timer are not available, the callback method can be used. There are slight differences between operating systems in obtaining system time, but the code flow is otherwise like the following pseudo-code. First, a callback function is registered:
Next, the callback is created, with polling returning an “OK” or “interrupted” state.
Then, a real-time transaction is started, with the “interrupted” flag periodically verified by the database runtime in an atomic operation.
Timer Method Code Snippets in C
Most mission-critical systems have hardware timers; using them provides greater precision. Three common code snippets in C set up timer variables, a real-time transaction, and the initialization routine. First, the timer variables:
Next, the real-time transaction:
And a simple initialization routine:
Hardware timer facilities vary significantly across operating systems. As an example, in VxWorks, any task can create a watchdog timer and use it to run a specified routine in the context of the system-clock ISR, after a specified delay.
Looking Ahead to More Controllability
Replacing conventional concurrency control and scheduling methods help eXtremeDB/rt achieve deterministic, predictable behavior needed for mission-critical systems. Future research aims at more controllability in the EDF scheduler. For example, an explicit priority parameter on a transaction would help ordering and preemption. Individual transactions could also carry a rollback time parameter, rather than the deadline/2 default.
Making the leap from an embedded database to a deterministic DBMS ensuring temporally valid data extends potential use cases. Mission-critical software teams who master this new COTS deterministic DBMS technology can gain advantages in development schedules, risk reduction, and application flexibility.
McObject co-founder and CTO Andrei Gorine leads the company’s product engineering. Gorine’s background includes senior positions with leading embedded systems and database software companies; his experience in providing embedded storage solutions in such fields as industrial control, industrial preventative maintenance, satellite and cable television, and telecommunications equipment is highly recognized in the industry. Gorine has published articles and spoken at many conferences on topics including real-time database systems, high availability, and memory management. He holds a Master’s degree in Computer Science from the Moscow Institute of Electronics and Mathematics
