Hubbry Logo
Algorithms for Recovery and Isolation Exploiting SemanticsAlgorithms for Recovery and Isolation Exploiting SemanticsMain
Open search
Algorithms for Recovery and Isolation Exploiting Semantics
Community hub
Algorithms for Recovery and Isolation Exploiting Semantics
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Algorithms for Recovery and Isolation Exploiting Semantics
Algorithms for Recovery and Isolation Exploiting Semantics
Algorithms for Recovery and Isolation Exploiting Semantics
View on Wikipedia
from Wikipedia

In computer science, Algorithms for Recovery and Isolation Exploiting Semantics, or ARIES, is a recovery algorithm designed to work with a no-force, steal database approach; it is used by IBM Db2, Microsoft SQL Server and many other database systems.[1] IBM Fellow Chandrasekaran Mohan is the primary inventor of the ARIES family of algorithms.[2]

Three main principles lie behind ARIES:

  • Write-ahead logging: Any change to an object is first recorded in the log, and the log must be written to stable storage before changes to the object are written to disk.
  • Repeating history during Redo: On restart after a crash, ARIES retraces the actions of a database before the crash and brings the system back to the exact state that it was in before the crash. Then it undoes the transactions still active at crash time.
  • Logging changes during Undo: Changes made to the database while undoing transactions are logged to ensure such an action isn't repeated in the event of repeated restarts.

Logging

[edit]

The ARIES algorithm relies on logging of all database operations with ascending Sequence Numbers. Usually the resulting logfile is stored on so-called "stable storage", that is a storage medium that is assumed to survive crashes and hardware failures.

To gather the necessary information for the logs, two data structures have to be maintained: the dirty page table (DPT) and the transaction table (TT).

The dirty page table keeps record of all the pages that have been modified, and not yet written to disk, and the first Sequence Number that caused that page to become dirty. The transaction table contains all currently running transactions and the Sequence Number of the last log entry they created.

We create log records of the form (Sequence Number, Transaction ID, Page ID, Redo, Undo, Previous Sequence Number). The Redo and Undo fields keep information about the changes this log record saves and how to undo them. The Previous Sequence Number is a reference to the previous log record that was created for this transaction. In the case of an aborted transaction, it's possible to traverse the log file in reverse order using the Previous Sequence Numbers, undoing all actions taken within the specific transaction.

Every transaction implicitly begins with the first "Update" type of entry for the given Transaction ID, and is committed with "End Of Log" (EOL) entry for the transaction.

During a recovery, or while undoing the actions of an aborted transaction, a special kind of log record is written, the Compensation Log Record (CLR), to record that the action has already been undone. CLRs are of the form (Sequence Number, Transaction ID, Page ID, Redo, Previous Sequence Number, Next Undo Sequence Number). The Redo field contains application of Undo field of reverted action, and the Undo field is omitted because CLR is never reverted.

Recovery

[edit]

The recovery works in three phases. The first phase, Analysis, computes all the necessary information from the logfile. The Redo phase restores the database to the exact state at the crash, including all the changes of uncommitted transactions that were running at that point in time. The Undo phase then undoes all uncommitted changes, leaving the database in a consistent state.

Analysis

[edit]

During the Analysis phase we restore the DPT and the TT as they were at the time of the crash.

We run through the logfile (from the beginning or the last checkpoint) and add all transactions for which we encounter Begin Transaction entries to the TT. Whenever an End Log entry is found, the corresponding transaction is removed. The last Sequence Number for each transaction is also maintained.

During the same run we also fill the dirty page table by adding a new entry whenever we encounter a page that is modified and not yet in the DPT. This however only computes a superset of all dirty pages at the time of the crash, since we don't check the actual database file whether the page was written back to the storage.

Redo

[edit]

From the DPT, we can compute the minimal Sequence Number of a dirty page. From there, we have to start redoing the actions until the crash, in case they weren't persisted already.

Running through the log file, we check for each entry, whether the modified page P on the entry exists in the DPT. If it doesn't, then we do not have to worry about redoing this entry since the data persists on the disk. If page P exists in the DPT table, then we see whether the Sequence Number in the DPT is smaller than the Sequence Number of the log record (i.e. whether the change in the log is newer than the last version that was persisted). If it isn't, then we don't redo the entry since the change is already there. If it is, we fetch the page from the database storage and check the Sequence Number stored on the page to the Sequence Number on the log record. If the former is smaller than the latter, the page needs to be written to the disk. That check is necessary because the recovered DPT is only a conservative superset of the pages that really need changes to be reapplied. Lastly, when all the above checks are finished and failed, we reapply the redo action and store the new Sequence Number on the page. It is also important for recovery from a crash during the Redo phase, as the redo isn't applied twice to the same page.

Undo

[edit]

After the Redo phase, the database reflects the exact state at the crash. However the changes of uncommitted transactions have to be undone to restore the database to a consistent state.

For that we run backwards through the log for each transaction in the TT (those runs can of course be combined into one) using the Previous Sequence Number fields in the records. For each record we undo the changes (using the information in the Undo field) and write a compensation log record to the log file. If we encounter a Begin Transaction record we write an End Log record for that transaction.

The compensation log records make it possible to recover during a crash that occurs during the recovery phase. That isn't as uncommon as one might think, as it is possible for the recovery phase to take quite long. CLRs are read during the Analysis phase and redone during the Redo phase.

Checkpoints

[edit]

To avoid re-scanning the whole logfile during the analysis phase it is advisable to save the DPT and the TT regularly to the logfile, forming a checkpoint. Instead of having to run through the whole file it is just necessary to run backwards until a checkpoint is found. From that point it is possible to restore the DPT and the TT as they were at the time of the crash by reading the logfile forward again. Then it is possible to proceed as usual with Redo and Undo.

The naive way for checkpointing involves locking the whole database to avoid changes to the DPT and the TT during the creation of the checkpoint. Fuzzy logging circumvents that by writing two log records. One Fuzzy Log Starts Here record and, after preparing the checkpoint data, the actual checkpoint. Between the two records other log records can be created. During recovery it is necessary to find both records to obtain a valid checkpoint.

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Algorithms for Recovery and Isolation Exploiting Semantics

View on Grokipedia
from Grokipedia
Algorithms for Recovery and Isolation Exploiting Semantics (ARIES) is a robust transaction recovery method designed for database management systems (DBMS) that employs (WAL) to ensure the and consistency of transactions while supporting fine-granularity locking, partial , and high-concurrency operations. Developed by researchers at , ARIES addresses the challenges of crash recovery in environments using steal/no-force buffer management policies, where modified pages may be written to disk before transaction commit and uncommitted changes can be forced to disk. By "repeating history" during recovery—redoing all logged updates regardless of commit status and then undoing only uncommitted transactions—ARIES minimizes recovery time and exploits semantic information from log records to optimize isolation and processes. The core of ARIES relies on a structured mechanism that records all changes before they are applied to the database, using log sequence numbers (LSNs) to track the state of each page and ensure idempotent operations. This WAL protocol logs not only forward updates but also compensation log records (CLRs) during rollbacks, which are redo-only to prevent duplicate undos and bound log growth. ARIES supports fine-granularity locking at the record or field level, combined with latches for physical consistency, enabling high concurrency by allowing multiple transactions to access the same page simultaneously without interference. It also accommodates partial rollbacks through savepoints, where transactions can roll back to a specific point, releasing locks early and logging CLRs to maintain recovery correctness. Recovery in ARIES proceeds in three distinct phases to restore the database to a consistent state after a crash. The analysis phase scans the log from the last checkpoint to reconstruct the set of dirty pages (those with uncommitted changes) and active transactions, determining the restart redo point (RedoLSN) to avoid unnecessary work. In the redo phase, ARIES performs a page-oriented forward pass starting from RedoLSN, reapplying all logged updates to pages if their page-LSN is older than the log record's LSN, ensuring committed changes are durable without re-logging. The undo phase then rolls back loser (uncommitted) transactions in reverse chronological order using a single backward log scan, leveraging logical undo operations and CLRs to skip already-processed records and support semantically rich actions like index structure modifications. By exploiting semantics, ARIES enhances isolation through operation-specific that enables advanced lock modes, such as increment/decrement counters without exclusive locks, and logical undos that preserve during concurrent executions. This approach also facilitates fuzzy checkpoints, selective restarts (focusing on affected pages), and media recovery for disk failures, making it adaptable to various DBMS architectures. Originally published in 1992 by , Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz, ARIES has influenced modern database implementations, including , due to its efficiency in handling real-world workloads with minimal assumptions about data structures or buffer sizes.

Background and Principles

Historical Development

The ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) recovery algorithm originated at the IBM Almaden Research Center during the mid-1980s, spearheaded by along with key contributors Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. This development addressed the evolving demands of systems, particularly the challenges of implementing efficient recovery mechanisms that could handle high concurrency without compromising performance or reliability. The primary motivation for ARIES stemmed from limitations in prior recovery approaches, such as those in System R (which relied on page-level locking), DB2/MVS (using but lacking flexibility for finer locks), and SQL/DS (employing shadow paging). These systems struggled to fully support the steal —allowing uncommitted (dirty) data pages to be written to disk for better buffer utilization—and the no-force —avoiding the need to flush all dirty pages to disk upon transaction commit—especially in environments with fine-granularity locking at the record level. ARIES was designed to overcome these issues by providing a robust framework that exploited transaction semantics to enable partial rollbacks and efficient , thereby improving in multi-user database scenarios. The algorithm's foundational concepts were first publicly documented in , culminating in the seminal paper titled "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using ," published in the ACM Transactions on Database Systems. This work formalized ARIES as a general-purpose recovery method applicable beyond databases to areas like persistent object-oriented systems and recoverable file systems. Early implementations and testing of ARIES occurred in prototypes, including the Starburst rule-based query optimizer and rewriter system in the mid-1980s, as well as the Extended Edition Database Manager. These efforts paved the way for its integration into production systems, influencing recovery enhancements in DB2/390 for shared-disk environments and DB2 Universal Database (UDB) prototypes during the early 1990s. ARIES builds on as a foundational concept to ensure log durability precedes data changes.

Core Policies and Semantic Exploitation

The ARIES recovery algorithm incorporates two fundamental buffer management policies known as steal and no-force, which enhance system performance by allowing flexible handling of dirty pages during transaction execution. The steal policy permits the flushing of modified (dirty) buffer pages to non-volatile storage before the associated transaction commits, thereby preventing buffer pool overflow and supporting high concurrency even under constraints; however, this necessitates a robust redo capability during recovery to reapply any lost changes. Complementing this, the no-force policy avoids mandating the immediate writing of modified data pages to disk upon transaction commit, deferring such I/O for better throughput; however, log records for committed transactions are synchronously forced to disk, which requires a thorough phase in recovery to identify and restore consistency for committed but unflushed updates. Central to ARIES's efficiency is its exploitation of operation semantics, which leverages the inherent properties of database operations to minimize redundant work during recovery. Redo operations are designed to be idempotent, applying updates only if the page's recovery log sequence number (recLSN) indicates they have not yet been persisted, thus ensuring repeatable execution without side effects from multiple applications. For actions, ARIES employs compensation log records (CLRs), which reverse the effects of prior operations in a manner that is itself idempotent and does not generate further CLRs during subsequent rollbacks, thereby preventing cascading aborts and enabling efficient partial rollbacks of subtransactions or specific actions. These semantic mechanisms also bolster transaction isolation by supporting fine-granularity locking, such as at the record level, and allowing selective rollbacks without necessitating a full system restart or transaction-level atomicity violations. By exploiting operation semantics, ARIES maintains serializability guarantees while permitting nested transactions and incremental , reducing lock hold times and contention in multi-user environments. Developed by researchers at the Almaden Research Center, these policies and techniques represent a significant advancement in balancing performance, reliability, and concurrency in database systems.

Logging System

Write-Ahead Logging Protocol

The (WAL) protocol serves as the foundational mechanism in ARIES for ensuring transaction durability and facilitating efficient recovery by guaranteeing that all changes are recorded durably before they impact the database state. Under the WAL rule, log records describing modifications to a data page must be flushed to stable storage prior to the corresponding updated page being written to nonvolatile storage. This discipline is enforced by storing a log sequence number (LSN) on each page, which corresponds to the LSN of the most recent log record affecting that page, allowing the system to verify consistency during recovery. By adhering to this protocol, ARIES prevents even in the event of a crash, as the logs provide a complete for reconstructing the database state. A key benefit of the WAL protocol in ARIES is its enablement of flexible buffer management policies, specifically the steal and no-force strategies. The steal policy permits dirty pages—those modified by uncommitted transactions—to be written to disk at any time to manage buffer space, while the no-force policy avoids flushing committed transaction pages immediately upon commit, thereby reducing I/O overhead and improving performance. These policies are viable because the WAL rule ensures that recovery can always reconstruct the committed state from the logs or roll back uncommitted changes without relying on the physical location of pages, thus minimizing the risk of incomplete or inconsistent data on disk. In terms of flush management, ARIES forces the log tail up to and including the commit log record to stable storage at transaction commit time, guaranteeing atomicity and as per the properties, but defers flushing of the associated data pages. This approach leverages semantic properties of operations to ensure that the redo phase of recovery is idempotent: updates are applied only if the page's LSN is older than the log record's LSN, preventing redundant or erroneous modifications even if a page was partially flushed before a crash. The protocol thus balances performance with reliability by minimizing synchronous I/O during normal operation while preserving recoverability. The integration of semantics into the WAL protocol further enhances ARIES by designing operations to be logically repeatable, which is crucial for handling complex actions like inserts and deletes during recovery. For instance, insert operations log the insertion details in a way that allows redo to safely re-insert if needed without creating duplicates, exploiting the semantic understanding that the operation either fully succeeds or is undone. Similarly, delete semantics ensure that during redo, missing records are not erroneously re-deleted by checking existence via log analysis, thereby avoiding data inconsistencies. This semantic exploitation allows ARIES to support fine-grained concurrency and partial rollbacks efficiently, as the logs capture not just physical changes but also the logical intent of operations.

Types of Log Records

In the ARIES recovery algorithm, log records are structured to capture the essential state changes and metadata necessary for ensuring transaction atomicity and durability while exploiting operation semantics to optimize recovery. These records adhere to the (WAL) protocol, where updates are written to the log before being applied to the database pages. Each log record includes a log sequence number (LSN) that monotonically increases to order operations chronologically. Update log records form the core of ARIES logging for data modifications, capturing changes to individual pages to support both redo and operations during recovery. Each update record contains the transaction identifier (XID), page identifier (PageID), the before-image (used for information, if applicable), the after-image (used for redo information, if applicable), and the record's own LSN, along with a previous LSN (PrevLSN) for chaining records within the transaction. These fields enable precise reversal or reapplication of modifications, with the before- and after-images varying in size based on whether the record is undo-redo, redo-only, or undo-only, depending on the operation semantics. Compensation log records (CLRs) are specialized entries generated during the phase of recovery to log the effects of rolling back prior updates, ensuring that these compensating actions are idempotent and never require further undoing. A CLR includes the XID, PageID, its LSN, PrevLSN, and crucially, an undoNextLSN pointer that directs recovery to the next log record to process in the transaction's , effectively skipping the compensated record. As redo-only records, CLRs contain only after-image data to reapply the compensating change if needed, preventing infinite loops and bounding the log volume during cascading rollbacks. Transaction control records manage the lifecycle of transactions within the log. The Begin_Xact record initiates a transaction, typically implicit with a PrevLSN of zero to mark the starting point. The End_Xact record signifies completion, distinguishing between commit and abort outcomes; for commits, it triggers the WAL rule to force all preceding log records of the transaction to stable storage, guaranteeing . These records lack extensive payloads, focusing instead on metadata like XID and LSN to delineate transaction boundaries. Checkpoint and state records periodically snapshot the system's recovery state to accelerate restarts by limiting the log scan scope. During a checkpoint, a master checkpoint record is written, followed by dumps of the transaction table—which lists active transactions with their states and last LSN—and the dirty , which enumerates modified pages alongside their recLSN values. These records serve no direct redo or purpose but provide a consistent view of ongoing work and buffer states at the checkpoint's dirty LSN. ARIES log records incorporate semantic awareness to enhance efficiency, tailoring content to the nature of operations rather than applying uniform logging. For instance, insert operation records may include flags marking the target page as allocated or partially filled (e.g., indicating 0% full in a CLR for space management), preventing redundant re-insertions during redo while allowing logical undo decisions based on index structures like B-trees. This exploitation of semantics reduces unnecessary I/O and supports fine-grained concurrency without compromising recovery guarantees.

Recovery Algorithm Phases

Analysis Phase

The analysis phase serves as the initial step in the ARIES recovery algorithm, where the system performs a forward scan of the write-ahead log starting from the log sequence number (LSN) of the most recent checkpoint record up to the point of the system crash. It begins by reading the most recent checkpoint record to initialize the Dirty Page Table (DPT) and Transaction Table (TT) with their states at the checkpoint time. This scan reconstructs the state of the database at the time of failure by processing log records such as updates and commits, thereby identifying the necessary actions for subsequent recovery without requiring a full historical log traversal. During this forward pass, the algorithm updates the Dirty Page Table (DPT), which maintains entries for all pages that were modified by active transactions and remain potentially inconsistent on disk. Each DPT entry includes the page identifier, the recLSN (the lowest log sequence number that must be applied during redo to ensure the page reflects all updates up to the time of the crash), and the page LSN (the log sequence number of the last update to that page in the log). When an update log record is encountered for a page not yet in the DPT, a new entry is created with the current record's LSN as the initial recLSN; for subsequent updates to the same page, the recLSN is updated to the minimum of its current value and the new record's LSN, while the page LSN is set to the latest update LSN. This structure exploits the semantic ordering of log records to precisely delineate the scope of redo operations, avoiding unnecessary page redos. Concurrently, the analysis phase builds the Transaction Table (TT), which tracks all transactions active at the time of the crash. Each TT entry contains the transaction identifier, its status (designated as a "winner" if committed or a "loser" if active or aborted), the lastLSN (the sequence number of the most recent log record written by the transaction), and the undoNextLSN (the sequence number of the next log record to be undone for losers). The table is initialized with active transactions from the checkpoint record and updated as commit, abort, or update records are processed during the scan; for instance, upon encountering a commit record, the transaction's status is marked as winner, and its lastLSN is advanced. This classification of winners and losers enables targeted recovery: winners' updates are prepared for redo to ensure , while losers' changes are flagged for to maintain atomicity, all without redundant processing of completed transactions. The semantic efficiency of the analysis phase stems from its exploitation of the log's structured format and checkpoint metadata, which confines the scan to a recent log tail rather than the entire log history. By deriving the DPT and TT in a single pass, ARIES minimizes I/O overhead and computational cost, as these tables guide the bounded redo and phases that follow, preventing repeated scans or full database traversals. This approach has been foundational in modern database systems, balancing recovery speed with correctness in high-concurrency environments.

Redo Phase

The redo phase in the ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) recovery algorithm ensures that the database pages reflect all committed and potentially uncommitted updates from the log since the last checkpoint, thereby restoring a consistent state that matches the point of failure. This phase begins by scanning the log forward starting from the minimum recovery log sequence number (recLSN) identified in the Dirty Page Table (DPT), which is constructed during the preceding analysis phase. By reapplying updates for all transactions—both winners (committed) and losers (uncommitted)—the redo phase effectively repeats the entire history of modifications that occurred after the last checkpoint, guaranteeing durability without regard to transaction status at crash time. The core of the redo process is idempotent application of updates, achieved through comparison of the log record's LSN with the page's LSN on disk. For each relevant log record encountered during the forward scan, the affected page is fetched into the buffer; if the page's LSN is less than the log record's LSN, the after-image (the new value) from the log is applied to the page, ensuring that only necessary changes are made. This LSN-based check prevents redundant operations, as any update already persisted on disk (reflected by a higher or equal page LSN) is skipped. Upon successful application, the page's LSN is updated to match the log record's LSN, maintaining synchronization between the database state and the log. No new log entries are generated during redo, and pages are not forced to disk, allowing for efficient recovery. Compensation log records (CLRs), which document the effects of undo actions during partial rollbacks, are treated as regular redo records in this phase. Since CLRs contain only after-images and represent committed undo operations (for winner transactions) or necessary corrections, they are reapplied idempotently if the LSN condition is met, ensuring that the database accurately reflects the pre-crash execution history. This handling preserves the semantics of prior undos without requiring reversal. ARIES exploits semantics to enhance idempotence, particularly for operations like inserts and deletes, where blind reapplication could lead to inconsistencies such as duplicates or erroneous removals. For inserts, the redo routine checks for the record's existence before insertion, skipping if already present to avoid duplication; similarly, deletes verify the record's presence prior to removal. These semantic checks leverage the operation's context and current page state, ensuring safe repetition without side effects, and align with ARIES's design philosophy of using application-level knowledge to optimize recovery. Upon completion of the redo scan, all dirty pages in the DPT have been brought up to the state at the time of the crash, with their LSNs updated accordingly. This establishes a consistent starting point for subsequent phases, confirming that the database embodies the effects of all logged actions without loss.

Undo Phase

The undo phase of the ARIES recovery algorithm performs a backward of loser transactions—those that were active but uncommitted at the time of the crash—to ensure atomicity by reversing their effects on the database. This phase follows the redo phase, which has already restored the database to a consistent state reflecting all committed transactions up to the crash point. Loser transactions are identified from the Dirty Page Table and Transaction Table produced during the analysis phase, and they are processed in descending order of their last log sequence number (lastLSN) to avoid conflicts and ensure orderly . For each loser transaction, the undo process begins at its lastLSN and proceeds backward through the log records, applying compensating actions based on the before-images stored in each update record to restore the prior state of affected data items. Each undo operation generates a compensation log record (CLR), which is a redo-only record that logs the compensating action and sets the undoNextLSN field to point to the LSN of the previous (earlier) log record in the transaction's history, allowing the system to skip already-processed records during potential restarts. This continues iteratively until the transaction's Begin_Xact record is reached, at which point the transaction is marked as aborted in the Transaction Table. The use of CLRs ensures that rollbacks are durable, as they are written to the log before the actual undo actions are applied to the database pages, and idempotent, meaning that re-executing the undo phase after another crash will not repeat or incorrectly reverse prior compensating actions due to the chaining via undoNextLSN. A key feature of ARIES is the exploitation of operation semantics during to handle cases where naive reversal might fail, such as when a item has been modified by multiple transactions. For example, to an insert operation, the system deletes the inserted record only if it still exists (to avoid errors if it was subsequently modified or deleted by another transaction); conversely, to a delete, it reinserts the record using its before-image only if the record is absent. This semantic approach allows for robust recovery without requiring the database to maintain strict before-and-after consistency across all operations. ARIES also supports nested transactions and partial rollbacks through the use of savepoints, which are recorded in the log as special markers allowing to a specific point within a transaction rather than a full abort. During the phase, the system respects these savepoints by truncating the undo chain at the appropriate nested transaction boundary, using the undoNextLSN to efficiently skip sub-transactions that have already been rolled back. This enables fine-grained recovery in complex, hierarchical transaction structures common in advanced database applications.

Checkpointing and State Management

Checkpoint Procedures

In ARIES, checkpoint procedures utilize fuzzy checkpoints to periodically capture a snapshot of the database system's state without requiring the system to or halt ongoing . This approach allows active transactions to continue executing concurrently, ensuring and minimal disruption to normal operations. Fuzzy checkpoints are particularly suited to the steal/no-force buffer management policy, as they do not mandate flushing dirty pages to stable storage during the process; instead, they rely on the (WAL) protocol to guarantee that all necessary log records precede any committed changes. The procedure for taking a fuzzy checkpoint begins with flushing the log buffer to ensure prior log records are on stable storage, followed by writing a begin-chkpt log record to mark the start. Next, the system constructs an end-chkpt log record containing snapshots of the transaction table (TT), which lists active transactions along with their states and most recent update log sequence numbers (LSNs), and the dirty page table (DPT), which tracks modified pages in the buffer pool. The end-chkpt record also includes file mapping information for open database objects. Once the end-chkpt record reaches stable storage, the LSN of the begin-chkpt record is stored in a master checkpoint record on stable storage, serving as the recovery starting point. During this process, the recLSN for each dirty page in the DPT is set to the LSN of the log record containing the most recent update to that page, enabling efficient redo operations. The entire procedure is designed to be incremental and non-blocking, gathering TT and DPT contents asynchronously to avoid contention. Fuzzy checkpoints are typically initiated periodically during normal system operation to bound recovery time, or in response to triggers such as buffer pool pressure when the number of dirty pages approaches a threshold, prompting without forcing immediate disk writes. This frequency helps limit the volume of log that must be scanned during the phase of recovery. The primary benefits include significantly reducing the length of the log scan required for by providing a recent consistent starting point, while the semantic guarantees of ARIES ensure that recovery correctness is maintained without the overhead of synchronizing all dirty pages. As a result, recovery times are more predictable and shorter, even in high-throughput environments.

Dirty Page and Transaction Tables

In the ARIES recovery algorithm, the Dirty Page Table (DPT) is an in-memory structure maintained by the buffer manager to track pages that have been modified but not yet flushed to nonvolatile storage. Each entry in the DPT consists of a page identifier (PageID), the recovery log sequence number (RecLSN)—which represents the lowest LSN from which updates to the page might need to be redone—and the page LSN, indicating the highest LSN reflected in the page's current in-memory copy. During normal database operation, the DPT is updated whenever a clean page is modified for the first time, at which point its RecLSN is set to the LSN of the corresponding log record; subsequent updates to the page advance the page LSN but do not alter the RecLSN unless the page is flushed to disk, in which case the entry is removed or the RecLSN is updated to the page LSN if it exceeds the prior value. The Transaction Table (TT) complements the DPT by maintaining state for each active transaction, enabling precise tracking of transaction progress and requirements. Each TT entry includes the transaction identifier (XID), the transaction status (e.g., active/unprepared denoted as 'U', committed as 'C', or aborted), the LastLSN pointing to the most recent log record written by the transaction, and the UndoNxtLSN, which chains to the next log record to be undone during . ARIES supports nested transactions through this structure, where subtransactions inherit and update fields from their parent while maintaining separate entries for independent tracking. The TT is updated during normal operation on every log record generation (advancing LastLSN and potentially UndoNxtLSN for compensation log records during partial rollbacks), as well as on commit or abort actions, which modify the status and may initiate undo chains. Both tables are maintained dynamically to reflect ongoing system state and are persisted by inclusion in checkpoint log records, ensuring their contents survive crashes. By exploiting the semantics of and transaction boundaries, the DPT and TT allow recovery processes to pinpoint exact redo starting points (via the minimum RecLSN across all dirty pages) and undo targets (via transaction-specific chains), thereby avoiding exhaustive log scans and enabling efficient, semantically aware restoration of database consistency.

Extensions and Applications

Support for Fine-Grained Concurrency

ARIES integrates fine-granularity locking into its recovery mechanism by incorporating lock information directly into log records, allowing the system to regenerate and reacquire necessary locks during the recovery process to prevent conflicts with ongoing transactions. Specifically, each log record contains identifiers such as PageID and log sequence numbers (LSNs) that enable the recovery to identify affected items and their associated locks, ensuring that uncommitted updates are protected even at the row or field level. During the redo and undo phases, ARIES reacquires locks for in-doubt transactions based on this logged information, either from explicit prepare records or by deriving lock names from the operation logs themselves. The further supports partial rollbacks to savepoints, leveraging its semantic exploitation to handle sub-transaction undos without full transaction abortion. Compensation log records (CLRs) play a key role here, as they are generated during partial undos and marked as redo-only, with an UndoNxtLSN field chaining them to subsequent actions and preventing re-undo of already processed operations. This approach bounds the log growth during nested or partial rollbacks, allowing early release of locks after the first undo action in a sub-transaction while maintaining recovery correctness. To guarantee isolation, ARIES maintains serializability by enforcing locking protocols during recovery, particularly for uncommitted changes, which ensures that the effects of failed transactions do not violate invariants. It exploits operation semantics, such as commutativity in increment or decrement operations, to permit higher concurrency through logical logging modes that reduce physical update overhead and allow multiple transactions to interleave safely on the same data items. Compared to page-level locking, fine-grained locking in ARIES significantly reduces lock contention, especially around hot-spot data items, by allowing concurrent access to unrelated portions of a page. The precise log-based undo mechanism, supported by CLRs and LSN tracking, preserves atomicity at the finer without introducing additional recovery complexity or performance penalties.

Implementations in Database Systems

The ARIES recovery algorithm has been widely adopted in production database systems, enhancing crash recovery reliability through its write-ahead logging and semantic analysis mechanisms. IBM DB2 integrated ARIES starting in its versions from the early 1990s, leveraging it for robust transaction recovery in enterprise environments. Microsoft SQL Server employs ARIES as the foundation for its write-ahead logging protocol, ensuring durable and consistent recovery operations. Customizations of ARIES in these systems address specific operational needs while preserving core recovery guarantees. In , ARIES is extended to handle distributed transactions via integration with two-phase commit protocols, enabling coordinated recovery across multiple nodes without compromising atomicity. adapts ARIES for Always On Availability Groups by applying its redo phase to log replay on secondary replicas, facilitating automatic and minimizing in clustered setups. Empirical evaluations demonstrate ARIES's efficiency in production settings, with recovery time scaling linearly with the log volume generated since the last checkpoint rather than the entire database size, thereby avoiding full scans during restarts. This property significantly reduces mean time to recovery, as validated in simulations and real-world deployments where redo operations target only modified pages. Modern extensions of ARIES maintain its semantic exploitation in evolving architectures, particularly cloud-native and in-memory environments. In Azure SQL Database, ARIES is augmented with multi-version to achieve near-constant recovery times, decoupling active transactions from historical log processing for scalable operations. These adaptations ensure high reliability in distributed systems while supporting fine-grained isolation without reimplementing core semantics.
Add your contribution
Related Hubs
User Avatar
No comments yet.