eXtremeDB/rt Transaction Scheduling

Scheduling transactions in a real-time database system is not a simple task and is quite different from scheduling transactions in a non-real-time database system. There are quite a few challenges, but let’s emphasize two of the most challenging:

• Non-real-time database systems optimize for the number of transactions per second or the average query time. A real-time database system’s performance is judged by its worst-case transaction time. This is a key differentiator between real-time and non-real-time database systems. For instance, the worst-case transaction time for a non-real-time DBMS is something that most users don’t care about (and is not specified). On the other hand, the number of transactions per second (TPS) is an often bragged about benchmark for many traditional DBMS.
• Non-real-time databases use transactions to enforce logical consistency, which presents a view on data consistent with some predefined constraints of the database. Each real-time transaction is assigned an execution deadline to make sure that the data used by them reflects the current physical environment. These deadlines can be successfully satisfied, or missed (in which case the transaction is aborted). In a real-time database system, transactions must never pass their assigned deadlines. The eXtremeDB/rt database kernel guarantees the database’s logical consistency, and schedule transactions to meet their deadlines, all while minimizing the number of transactions that miss their deadlines.

Furthermore, real-time transaction scheduling goals vary from application to application. For example, one application could seek to schedule transactions to minimize the number of “aborted” transactions (those that “miss” their deadlines) and may or may not allow preemption by a “higher priority” transaction; another application could aim to maximize the total “weight” (deadline + priority) of successful transactions while another application might simply prioritize transactions with the earliest deadline.

eXtremeDB/rt provides two alternative implementations of transaction managers (schedulers). Both managers are based on the standard eXtremeDB MURSIW (Multiple Read Single Write) policy.

High Priority Earliest Deadline First (EDF) algorithm

The eXtremeDB/rt EDF-TM (Earliest Deadline First Transaction Manager) implements a wait-list of transactions, in other words a “transaction queue“ in the database kernel. Transaction requests are sorted first on their priority and then within the same priority by deadline.

Priority Inheritance (PI) algorithm

The eXtremeDB/rt PI-TM (Priority Inheritance Transaction Manager) relies on the underlying real-time operating system’s scheduling, and provides necessary “hints” via specific usage of the RTOS’s synchronization primitives: Upon the start of a transaction, the thread grabs one or more mutex and releases them when the transaction ends. As a result, the underlying operating system scheduler is fully aware of which thread holds a mutex that is needed for a high-priority transaction and may apply the “priority inheritance” algorithm when necessary, i.e. temporarily raise the priority of a thread that is “in the way” to let it finish the transaction “faster” so it can release the “highly needed” mutex.

EDF- based vs PI-based transaction managers — which is better and when?

The major difference between the EDF and PI TMs is that in the case of the EDF manager, the database kernel organizes the queue and determines transaction execution order. In the PI-TM case, the execution order is determined by the operating system and is normally based on the corresponding OS task priorities. Different application patterns can take advantage of different transaction schedulers.

Now, let’s consider a pattern when all thread priorities are the same and the underlying OS gets access to the database lock in FIFO order. The picture illustrates an execution scenario in which two transactions have arrived while a single transaction (the lowest one on the picture) is executing. In this scenario the PI-TM would execute all three in the order they were registered with the system. Yet it is possible that the deadline of the third transaction (the highest on the picture) is lower than the deadline of the second transaction. It will be aborted then. If on the other hand the EDF-TM is used, the third transaction will be allowed to run despite that fact it has arrived into the system after the second one because its deadline is shorter. As a result both would fit into their deadlines.

Preemption rules

Once scheduled, a transaction’s execution is controlled by the transaction manager, which ensures proper serialization (“read-write” transactions are executed sequentially and “read-only” transactions are executed in parallel while no “read-write” transactions are executing). EDF-TM verifies the rules just once at the time a new transaction arrives (is entered into the waiting queue), while PI-TM checks the rules also when a transaction is finalized.

The preemption rules are as follows:

Learn more about eXtremeDB/rt