Database management systems (DBMS) are the complex engine helping power transactional and analytical applications across every industry today. From mainframe databases supporting thousands of concurrent users to emerging real-time Big Data platforms, scheduling the execution of transactions plays a pivotal role in system capabilities.
This guide will provide readers an in-depth walkthrough of the most essential scheduling approaches used in modern database architectures. We’ll cover how schedules impact performance, consistency and failure resiliency. Our journey will reveal that no single “best” schedule exists – each comes with unique advantages and tradeoffs to consider.
Overview of DBMS Scheduling
At the heart of any database system is the DBMS – specialized data management software allowing users to define, construct, access and administer databases. The DBMS determines much of the system’s capabilities for performance, scalability, reliability and more.
One key responsibility of a DBMS is transaction scheduling – the execution coordinator for transactions sent to the system. Transactions represent discrete units of work (data read/write operations) performed against the database. Based on scheduling approach, the DBMS will interleave the execution of concurrent transactions in a particular manner it believes optimal.
Why does scheduling matter so much? Two key reasons:
1. Performance – The sequence transactions run influences overall throughput and responsiveness, especially with multiple concurrent transactions.
2. Consistency – If transactions manipulating the same data execute in an uncontrolled manner, conflicting updates can occur that produce inconsistent data.
Balancing these two considerations is the hallmark of quality DBMS scheduling. Next we survey common scheduling approaches seen in modern database systems.
Serial Scheduling
The simplest scheduling technique is serial scheduling, where transactions line up and execute sequentially without any overlap, essentially “one at a time”.
While simple in logic, serial scheduling has glaring performance limitations. With all concurrency eliminated, transaction processing capability cannot scale with additional transactions – all must wait in line behind earlier ones. Performance is likely only sufficient for very simple single-user database systems with minimal data contention.
Early single-user databases of the 1960s often relied on straight serial transaction batch processing due to the limitations of early computing infrastructure. For modern dynamic OLTP and analytical workloads, pure serial scheduling simply cannot keep pace. However, it remains relevant as we’ll see later when extremely high consistency guarantees must be maintained.
Concurrent Scheduling
Concurrent scheduling addresses the performance pitfalls of serial processing by allowing the interleaving of multiple transactions, enabling parallel execution:
By working on transactions simultaneously, resource utilization increases significantly, along with dramatic throughput gains. However, the danger now exists of multiple transactions accessing and manipulating the same data in an uncoordinated, conflicting manner.
This risk requires DBMS developers to implement sophisticated concurrency control techniques to orchestrate cooperative access. Methods like locks, timestamps, validation and multi-version concurrency allow transactions to proceed independently yet prevent scenarios where interleaved steps produce database inconsistencies (e.g. lost updates).
While complex, virtually all enterprise database systems like Oracle, SQL Server leverage optimistic and pessimistic locking to maximize transaction concurrency. Performance could otherwise suffer enormously given exploding user populations and data volumes. Reviewing manufacturer guidance helps configure isolation levels and conflict resolution policies appropriately for one’s application.
Conflict Serializable Schedules
Conflict serializability offers another approach where transactions obtain a serializable execution – behaving as if executed in some sequential order despite concurring. The onus resides with the DBMS scheduler to properly interleave operations to avoid conflicts, rather than burdening application developers as seen with lock-based concurrency control.
A classic concurrency control protocol guaranteeing conflict serializability is strict two-phase locking (2PL). Transactions only unlock data after completely finishing – effectively serializing executions. This coordination through scheduling ensures consistency yet prevents pathways for conflicting access.
Some database platforms extend upon 2PL applying multi-version concurrency for added performance. Postgres and Oracle for example allow transactions to access both current and prior database “versions”, expanding opportunities for concurrency. SQL Server takes this further with “snapshot isolation” transactions that read from a consistent snapshot frozen at start.
While avoiding dirty reads and lost updates, conflict serializability does lower concurrency from maximum theoretical limits. Finding optimal scheduling policies means balancing such precision guarantees and throughput needs of target applications. Online transaction processing (OLTP) and analytical (OLAP) workloads often mandate different priorities.
Recoverable Schedules
Mission-critical applications demand resilience to all types of failures – both hardware and software. Recoverable scheduling offers durability by guaranteeing consistent database state will be maintained even should the DBMS catastrophically crash or fail in the midst of transaction processing.
This capability stems from write-ahead logging (WAL) forcing every transaction data change to be recorded in permanent log storage before actually writing to main database storage:
Only upon successful commit will changes leave the log and update actual database pages. This ensures that whatever failure might strike, the log serves as record to either “roll forward” committed changes restored post-recovery or “roll back” pending changes of uncommitted failed transactions.
Popular transaction log implementations include ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) and shadow paging copy-on-write to accelerate logging performance. When availability 24/7/365 is an imperative, recoverable scheduling is foundational. Financial markets, healthcare systems, e-commerce and more mandate this durability.
Cascadeless Schedules
Complex transaction processing risks triggering a devastating cascading rollback where a single failed or cancelled transaction bringing down other dependent transactions already committed. This ruinous ripple effect threatens database consistency protections:
Cascadeless scheduling mitigates this vulnerability using “cascading abort prevention” to cautiously defer dependent transaction commits until the originating transaction has completely finished. Failed transactions bluntly rollback in isolation without collateral impact on others already finalized.
Distributed transaction processing heightens exposure to cascading rollbacks as multi-node database commits requires coordination. Schedulers must recognized nested interdependencies across global transactions to avoid widespread contamination when failures strike individual nodes. While averting worst case scenarios, performance suffers somewhat given additional bookkeeping.
Strict Scheduling
For the most rigorous data consistency guarantees without compromise, strict scheduling constraints transactions to follow highly structured sequencing rules:
By imposing strict ordering, interleaving anomalies are eliminated by design. Traditional conflict strict scheduling ensures transaction reads and writes never access dirty or unstable data from concurrent transactions.
The stricter recoverable strict scheduling further makes all transactions output available following a failure – offering both conflict and recoverability safety. Implementation requires costly coordination signaling across all transactions to enforce ordering.
As Table 1 shows, strict schedules offer unmatched isolation yet with significant concurrency impact:
| Isolation Level | Dirty Reads | Non-Repeatable Reads | Phantoms | Concurrency |
|---|---|---|---|---|
| Read uncommitted | Allowed | Allowed | Allowed | Highest |
| Read committed | Not allowed | Allowed | Allowed | |
| Repeatable read | Not allowed | Not allowed | Allowed | |
| Serializable | Not allowed | Not allowed | Not allowed | Lowest |
Table 1 – Transaction isolation levels and impact on concurrency
Strictness comes at the expense of throughput. Thus strict schedulers generally only suit specialized systems valuing unquestioned consistency over performance. Financial general ledgers are one such example willing to pay this price to completely prevent race conditions between account debit/credits.
Conclusion
We have explored foundational scheduling approaches leveraged in modern database systems striving to balance transactional performance and coordination:
- Serial – Simple yet slow, no concurrency
- Concurrent – Broadly adopted, risks inconsistencies
- Conflict Serializable – Simulates serializability
- Recoverable – Resilient to all failures
- Cascadeless – Limits failure cascades
- Strict – Eliminates anomalies but costly
Today’s intensive transaction loads would quickly overwhelm purely serial scheduling. Concurrent and conflict serializable options persistent, using multi-versioning and snapshot isolation to minimize locking bottlenecks. We see recoverable and cascadeless properties combined to construct robust platforms like Apache Kafka. Lastly strict scheduling persists for niche needs demanding absolute data integrity.
There exists no ideal one-size-fits all schedule – each application bears unique technical and business requirements. Thankfully database architects have rich portfolio of scheduling approaches to evaluate when planning new analytical or transactional database platforms.
