Patent Publication Number: US-7711713-B2

Title: System for deterministic database recovery time

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to data processing apparatus and methods for the storage and retrieval of data stored in computerized database management systems. More particularly, the invention relates to deterministically controlling the recovery of the data after a crash has disrupted the system. 
   2. Description of the Prior Art 
   A major problem today is providing high availability (HA) of database management system (DBMS) to its users. Increasingly, organizations with DBMSs, such as banks, brokerages, e-tailers, etc., are finding that they cannot tolerate long outages while a DBMS is unavailable or only available at a reduced performance level. 
   There are two aspects to this problem. The obvious first is the prevention of disruptions or “crashes” of a DBMS to begin with. This is significant, but it is not the subject of this discussion. Rather, we here address the second aspect, the pragmatic fact that disruptions in a DBMS will occur and that the DBMS needs to be recovered rapidly to its full performance level. 
     FIG. 1  (background art) is a block diagram conceptually depicting the basic elements and operation of a representative DBMS  10 . The DBMS  10  includes a database engine  12 , a database  14 , a buffer pool  16 , and a transaction log  18 . In operation, pages of data are “paged into” and “paged out” of the buffer pool or cache memory. A “page fault” occurs when a page to be paged into the buffer pool  16  because it is not already there. When a page contains updates that are not yet recorded in the database  14  it is a “dirty page.” The operation of paging out a dirty page from the buffer pool  16  into the database  14  is often referred to as “flushing.” Conversely, when a page with no updates is paged out, this operation is often referred to as “replacing.” Page faults and having to flush dirty pages are generally undesirable because they slow down operation of the DBMS  10 . 
   The buffer pool  16  resides in high speed, volatile memory and the rationale for using it, rather than simply working directly with the database  14 , is to increase the efficiency of the DBMS  10  based on the principles of probability. If the DBMS  10  is being used by an application to perform a query or to update a record in a page, that page is likely to contain other records that will soon also be the subject of queries or updates. Accordingly, it is usually desirable to not page out a page after a query or update finishes with it, but rather to retain it in the buffer pool  16  until it has not been accessed for some period of time or until the application using it ends. 
   Of particular present interest, when an update is performed the database engine  12  needs to page out dirty pages at some point and this is where things get complicated. Unplanned disruptions in the DBMS  10  can occur, causing the contents of the buffer pool  16  to not get properly flushed to the database  14 . Such an event is termed a “crash” and the process of restoring the data stored in the database  14  to a transactionally consistent state after such a crash is often referred to as “crash recovery.” 
   To facilitate crash recovery, a logical representation of each of the updates applied to the pages in the buffer pool  16  is entered into a transaction log  18  that resides in persistent storage. In the unfortunate even of a crash, the transaction log  18  can be replayed to redo all of the committed updates that were applied to pages in the buffer pool  16  but not flushed to the database  14 . If there is a large number of records in the transaction log  18  to replay during crash recovery or if the records are expensive in terms of system resources to replay, crash recovery can take a long time. 
     FIG. 2  (background art) is a block diagram depicting the transaction log  18  as a series of log records  20 . Here, “rec n ” represents the log record  20  that dirtied the oldest unflushed page in the buffer pool  16  and the series “rec n , rec l , . . . rec n+m ” then represent log records  20  that need to be replayed. 
   In passing, it should be noted that recovery time after a crash also includes time to roll back any uncommitted transactions that were open at the time of the crash, but this time is generally negligible compared to the time to do the roll forward portion of recovery. This is because in online transaction processing (OLTP) systems, transactions tend to be very short, so only a few seconds worth of rollback is needed, while in decision support systems (DSS), transactions tend to be long but also read-only, and read-only transactions do not generate any log records and require no rollback. 
   Various technologies have been developed in attempts to improve crash recovery handling. For example, U.S. Pat. No. 5,625,820 and U.S. Pat. No. 5,574,897 by Hermsmeir et al. disclose methods wherein a user chooses a length of time (an external threshold) that he or she is willing to spend recovering a database, and the system dynamically manages the logging of objects to meet this demand. The available CPU to run the process, the number of I/Os the process generates, and the quantity of lock wait time are taken into consideration. The shorter the time the user chooses the more objects the system will log, but the more the system performance is otherwise degraded in a tradeoff for this. As such, these references teach resource management to achieve a desired recovery time, but where resource management is rigid. 
   U.S. Published App. No. 2003/0084372 by Mock et al. discloses a Method and apparatus for data recovery optimization in a logically partitioned computer system. This is a method wherein a user may specify the maximum recovery time which can be tolerated for compiled data in a computer system having dynamically configurable logical partitions, and a protection utility manages the logging of indexes so that this maximum recovery time is not exceeded yet unnecessary logging is not performed. The compiled data may be multiple database indexes, which are selectively logged to reduce recovery time. Logging is selectively discontinued or extended responsive to changes in partition configuration, allowing a gradual migration to the target recovery time using the new set of configured resources. As such, however, this invention address recompiling database indexes, rather than the whole process of database recovery, and this invention does this in the context of computer system having dynamically configurable logical partitions. 
   U.S. Pat. No. 6,351,754 by Bridge, Jr. et al. discloses a method for controlling recovery downtime. A checkpoint value is maintained that indicates which records of a plurality of records have to be processed after the failure. The target checkpoint value is determined by calculating a maximum number of records that should be processed after the failure. As such, however, this approach is not deterministic and its checkpoint value may result in an undue allocation of system resources because of this. 
   U.S. Pat. No. 5,758,359 discloses a method for performing retroactive backups in a computer system. The retroactive backup mechanism employs a backup policy dictating that certain backups are to be performed at set times and for set backup levels. The total size of a save set is compared to the maximum size threshold and the backup is activated when the threshold is reached. As such, however, this approach is also clearly not deterministic. 
   In view of the current state of affairs, however, the present inventors determined that the users of DBMSs who have high availability (HA) requirements would still benefit greatly from the ability to specify a maximum crash recovery time (R max ) that they are willing to tolerate, and to then have the DBMS more efficiently automatically adjust its work of flushing dirty pages to the database after a crash as needed to guarantee that R max  will not take longer than specified. 
   SUMMARY OF THE INVENTION 
   Briefly, one preferred embodiment of the present invention is a method for limiting the amount of time for a database server to perform a crash recovery process. A maximum recovery time for the database server to perform the crash recovery process is specified. An estimated recovery time for the crash recovery process is calculated that is less than the maximum recovery time, with the estimated recovery time based on one of both of a deterministic analysis of cost accumulation during prior instances of the crash recovery process or an empirical analysis of cost accumulation during regular transaction processing in the database server. The crash recovery process is then conformed to the estimated recovery time. 
   Briefly, another preferred embodiment of the present invention is a method for updating an estimated recovery time to perform crash recovery in a database management system as a log record is generated during transaction processing. A record type for the current log record is determined, and an estimated record cost for that record type is retrieved from a set of pre-stored statistical data. This estimated record cost is then added to the estimated recovery time. 
   Briefly, another preferred embodiment of the present invention is a method for updating an estimated recovery time to perform crash recovery in a database management system after a dirty page is flushed by a page flusher. An estimated page cost for the dirty page is retrieved from a pre-stored set of the estimated page costs, where such an estimated page cost is based on either or both of a deterministic analysis of cost accumulation during prior instances of crash recovery in the database management system or an empirical analysis of cost accumulation during regular transaction processing in the database management system. The estimated page cost is then subtracted from the estimated recovery time. 
   It is an advantage of the present invention that it permits a user to deterministically set a “wall-clock” upper bound for crash recovery process times, particularly where high database availability is desired or needed. 
   It is another advantage of the present invention that it has flexible adaptability to needs across a wide range of database management systems as well as adaptability to be optimized when employed in individual database management systems. A deterministic analysis of cost accumulation during prior instances of crash recovery can be used, or an empirical analysis of cost accumulation during regular transaction processing can be used. Or both can be used. Other parameters can similarly be experimented with, for instance, the numbers (“granularity”) of or classes (“categorizations”) of record types can be changed and the effects analyzed. Deciding between two approaches in a particular case can thus be based on testing to see how accurate the estimates are for different configurations and the actual evidence as more recoveries are performed. 
   And it is another advantage of the present invention that the advantage in the adaptability achieved when this system/method is employed in individual database management systems and deployed on the multitude hardware platforms and storage subsystem that differ in performance. In other words the system adapts to the varying performance dimension of different hardware that the database management systems sit on to provide the optimal tradeoff of transaction rate and recovery time. 
   These and other features and advantages of the present invention will no doubt become apparent to those skilled in the art upon reading the following detailed description which makes reference to the several figures of the drawing. 

   
     IN THE DRAWINGS 
     The following drawings are not made to scale as an actual device, and are provided for illustration of the invention described herein. 
       FIG. 1  (background art) is a block diagram conceptually depicting the basic elements and operation of a representative database management system (DBMS). 
       FIG. 2  (background art) is a block diagram depicting the transaction log of  FIG. 1  as a series of log records. 
       FIG. 3  is a block diagram depicting an overview of how the inventive crash recovery system (CR system) can be added to a DBMS, such as that of  FIG. 1 . 
       FIG. 4  is a chart, nominally in the manner of a flow chart, providing a basic overview of a process for crash recovery in accord with the present invention. 
       FIG. 5  is a block diagram depicting a costs table in which the types of log records are matched with respective estimated costs to replay an individual log record of the respective types. 
       FIG. 6  is a block diagram depicting one approach to how the CR system can track the current estimated replay cost based on the costs table of  FIG. 5  and other available data. 
       FIG. 7  is a flow chart depicting a process for updating the recovery cost estimates of various types of log records during a crash recovery. 
       FIG. 8  is a flow chart depicting a process for updating the current estimated replay cost and the flushing algorithm when a new log record is generated during transaction processing. 
       FIG. 9A-B  is a flow chart depicting a process for updating the current estimated replay cost and the flushing algorithm after a dirty page is flushed by a page flusher. 
   

   In the various figures of the drawings, like references are used to denote like or similar elements or steps. 
   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The present invention provides methods and apparatus to provide a deterministic database recovery time. As illustrated in the various drawings herein, and particularly in the view of  FIG. 3 , embodiments of the invention are depicted by the general reference character  50 . 
     FIG. 3  is a block diagram depicting an overview of how the inventive crash recovery system (CR system  50 ) can be added to a database management system (DBMS), such as the DBMS  10  of  FIG. 1  (background art). As can be seen, the major features of the CR system  50  are a recovery manager  52  and statistical data  54 . 
   The CR system  50  provides the users of the DBMS  10  with the ability to specify a maximum time (R max ) that they are willing to tolerate for performing crash recovery. Using the CR system  50 , the DBMS  10  is made able to automatically adjust its workload as needed to guarantee that R max  is not exceeded. The CR system  50  permits this with a very high degree of accuracy—much higher than is possible with other techniques, such as hardwired time estimates, that do not collect statistics from actual recoveries or accumulate estimated recovery times based on such statistics during transaction processing. 
     FIG. 4  is a chart, nominally in the manner of a flow chart, providing a basic overview of a process  100  for crash recovery in accord with the present invention. In a step  102  the process  100  starts, and in a step  104  general initialization of the DBMS  10  is performed. In an optional step  106 , described in detail presently, a small sample workload can be run on the DBMS  10  by the CR system  50 . 
   In a step  108  the DBMS  10  performs conventional operations, as required for whatever end application or applications the DBMS  10  is being employed for. In a step  110 , as is the unfortunate course of affairs over time, the DBMS  10  crashes. Accordingly, in a step  112  the DBMS  10  undergoes crash recovery. And step  108  is then returned to, where the DBMS  10  carries on, potentially going through this scenario forever. 
   As described so far, steps  102 ,  104 , and  108 - 112  are normal operations in an entirely conventional DBMS. The addition of the CR system  50 , however, changes this. In accordance with the present invention, step  108  is modified so that it uses statistics generated by the CR system  50  to compute estimated crash recovery time R est  and dynamically select a flushing algorithm to maintain R est  as less than or equal to R max . Step  108  may also be modified to contribute inputs of time needed to perform individual transactional steps to statistics accumulation  116  discussed below. 
   In a step  114  the CR system  50  performs user configuration. This can be as little as specifying a value for R max , possibly even accepting an out-of-the box default value. One value can be provided, or multiple representative values can be provided for different DBMS applications. This is merely a matter of embodiment design. Many embodiments of the CR system  50  can be expected to permit additional configuration to be performed. In particular, this will often include letting the user “seed” the CR system  50  with initial data to start with before it has had the opportunity to collect actual statistical data for the specific DBMS  10 . Again as a matter of design, the CR system  50  can provide a single set of default initial seed data, or provide multiple representative sets from which the user can pick one, or the user can enter their own values to use. Alternately, in embodiments of the CR system  50  provided with this option, the user can let step  114  enable the optional step  106  and obtain “intelligent” seed data. This subject is covered further, below, after this overview discussion. 
   In a step  116  the CR system  50  accumulates statistics, storing these as the statistical data  54  in a persistent storage. In essence, this involves converting the seed data to actual data based on statistical analysis of the specific DBMS  10  in operation (i.e., data collected from step  106  if it was performed, and continually in step  108 ) and in crash recovery (i.e., prior instances of step  112 ). The accumulated statistics are applied continually during database operations (step  108 ) to update the estimated recovery time R est  and adjust the flushing algorithm in order to maintain R est  less than or equal to R max . 
   In  FIG. 4 , steps  114 - 118  have been intentionally made adjacent to emphasize that they can work closely together. For example, without limitation, step  114  can be used to set R max  to a different value at any time. It might, for instance, be desirable for an organization to reduce R max  during a peak sales season, or to increase it while some hardware in the DBMS  10  is taken off-line for maintenance or upgrade. Such a new value for R max  set in step  114  can then seamlessly be used by steps  116  and  118 . The operations in steps  114 - 118  are now discussed in more detail. 
   The CR system  50  can work to assure that R max  is not exceeded by using various mechanisms in steps  116  and  118 , with increasing levels of sophistication as needed. One such increase in sophistication is for the CR system  50  to accumulate statistics in step  116  based on the amount of time taken to replay or rollback different types of log records during real crash recovery events (step  112 ). These statistics are preferably stored in the statistical data  54  and, over time, used to improve the accuracy of the CR system  50  as more recoveries are experienced. The statistics can be captured and kept at various granularities, e.g. coarse-grained (“on average, 10,000 log records can be replayed per minute”) or fine-grained (“on average 8,000 inserts per minute, 12,000 updates per minute,” etc.). The most accurate estimates are obtained with finer-grained statistics, but coarse-grained statistics can be used when the number of records that have been replayed or rolled back in actual recovery events is small, to reduce the errors due to small sample-size. 
     FIG. 5  is a block diagram depicting a costs table  130  in which the types (t 1 , t 2 , . . . t i ) of log records  20  are matched with respective estimated costs (c 1 , c 2 , . . . c i ) to replay an individual log record  20  of the respective types. Such an estimated “record cost” includes the time to perform all of the recovery processing for a single record of the given type in the roll-forward recovery phase, i.e., reading the log record  20  from persistent storage, reading the pages it applies to from storage (if they are not already in the bufferpool  16 ), and applying the log record  20  if it is not already reflected in the pages. 
   These record cost statistics can be simple averages of the observed time to replay a given type of log record  20 . Preferably, however, these can be more sophisticated, such as each being a decaying average where more recent examples of the times taken to replay given types of records are weighted more strongly, or where each is a sliding window is used to store average information for only a number of the most recent replays of each type of log record  20 . Using such, more detailed, metrics permit the CR system  50  to adapt its estimates more quickly to changing workloads. 
     FIG. 6  is a block diagram depicting one approach to how the CR system  50  can track the current estimated replay cost, R est , based on the costs table  130  of  FIG. 5  and other available data. A double linked list  132  can be used to keep track of what contributes to R est , where the individual list entries (l n , l n+1 , . . . l n+m ) in the linked list  132  represent the pages that may need to be processed in a crash recovery. Each list entry (l n , l n+1 , . . . l n+m ) includes an estimated “page cost” (C n , C n+1 , . . . C n+m ; note, uppercase “C”) that is the sum of the estimated “record costs” (lowercase “c”) for all of the individual records (r) that might need to be replayed for that page during a crash recovery. Along with the double linked list  132 , a hash table  134  of hash buckets (h 1 , h 2 , . . . h j ) is provided, and populated based on the page identifiers used by the page flushers, to quickly find list entries (l) in the linked list  132 . 
     FIG. 7  is a flow chart depicting a process  150  for updating the recovery cost estimates of various types (t) of log records  20  during recovery. The process  150  starts in a step  152 , and in a step  154  a determination is made whether the transaction log  18  includes any log records  20  that need to be replayed. If not, in a step  156  the process  150  stops. 
   If there is part of the transaction log  18  yet to replay, in a step  158  the next log record  20  ( r ) is read and in a step  160  the type (t i ) of this log record  20  is determined. Next, in a step  162  this log record  20  ( r ) is replayed and the cost (c) of this replay event is measured. 
   In a step  164  the estimated cost (c i ) for type (t i ) is updated based on the observed cost (c). The estimated cost (c i ) can simply be replaced with the observed cost (c), but a more sophisticated approach is to accumulate the just observed cost (c) into a weighted average of the estimated cost (c i ). After step  164 , the process  150  returns to step  154 . 
     FIG. 8  is a flow chart depicting a process  200  for updating R est  and the flushing algorithm when a new log record  20  is generated during transaction processing. In a step  202  the process  200  starts. In a step  204  the type (t i ) of the present log record  20  is determined and in a step  206  the estimated cost (c i ) for a record of that type (t i ) is looked up in the statistical data  54 . In a step  208  this estimated cost (c i ) is added to R est , producing a new value for it. 
   In a step  210  a determination is made whether the page ID for the current log record  20  is present in the hash table  134 . If so, in a step  212  the pointer in the hash table entry (h) is followed to the corresponding linked list entry (l) and the estimated record cost (c i , a lowercase “c”) for the current log record  20  is added to the page cost (C, uppercase “C”) in that linked list entry (l). Otherwise, in a step  214  an entry (h) is added to the hash table  134  and an entry (l) is added to the linked list  132  with the estimated costs (C=c i  here). 
   Next, in a step  216  a determination is made whether R est  is less than a first pre-set percentage (x) of R max . If so, in a step  218  the flushing algorithm is set to optimize performance and in a step  220  the process  200  stops. 
   Otherwise, in a step  222  a determination is made whether R est  is less than a second pre-set percentage (y) of R max . If so, in a step  224  the flushing algorithm is set to optimize recovery time and in step  220  the process  200  now stops. 
   And otherwise, in a step  226  the flushing algorithm is set for emergency flushing and in step  220  the process  200  stops. 
     FIG. 9A-B  is a flow chart depicting a process  250  for updating R est  and the flushing algorithm after a dirty page is flushed by one of the page flushers. 
   In a step  252  the process  250  starts. In a step  254  the page ID is looked up in the hash table  134 , in a step  256  the pointer in the hash table entry (h) for this page is followed to the corresponding link list entry (l), and in a step  258  this list entry (l) is marked as flushed. 
   In a step  260  the page cost (C) for this list entry (l) (i.e., the cost of replaying the log records  20  that apply to this page) is noted and in a step  262  this is subtracted from R est , producing a new value for it. 
   Next, in a step  264  a determination is made whether R est  is less than the first pre-set percentage (x) of R max . If so, in a step  266  the flushing algorithm is set to optimize performance and the process  250  proceeds to step  274 . 
   Otherwise, in a step  268  a determination is made whether R set  is less than the second pre-set percentage (y) of R max . If so, in a step  270  the flushing algorithm is set to optimize recovery time and the process  250  now proceeds to step  274 . 
   And otherwise, in a step  272  the flushing algorithm is set for emergency flushing. 
   In step  274  ( FIG. 9B ) a determination is made whether the linked list entry (l) is at the head of the linked list  132  (i.e., whether it is the oldest entry). If not, in a step  276  the process  250  stops. 
   Otherwise, in a step  278  the next linked list entry (l′) is found and the pointer in it is followed to the corresponding next hash table entry (h′). Then, in a step  280  the current list entry (l) is removed from the linked list  132  and the current hash table entry (h) is removed from the hash table  134 . 
   In a step  282  a determination is made whether the “next” linked list entry (l′) is already marked as flushed. If not, in step  276  the process  250  now stops. 
   Otherwise, in a step  284  the “next” linked list entry (l′) is set to be the current linked list entry (l) and the next hash table entry (h′) is set to be the current hash table entry (h), and the process  250  returns to step  260  and carries on from there. 
   Summarizing, the number of each type of log record that needs to be replayed can be kept track of by maintaining an in-memory data structure, such as a linked list of the types that have been generated, in the same order as they were generated, as well as a hash index into the linked list that is hashed on the ID of the in-memory data page that the log record applies to. 
   The current estimated recovery time, R est  starts at 0 at system boot time. As each new log record is generated, its type is added to the tail of the linked list, its corresponding memory page ID is added to the hash index (which in turn points to the entry in the linked list), and the estimated time to replay it is added to R est . 
   As dirty pages are flushed by page flushers, their hash index entries are used to find their entry in the linked list, and these entries are marked as flushed. Finally, if the oldest (head) entry on the linked list is marked as flushed, a scan is performed on the list from the oldest end. The scan stops when it reaches the first entry that is not flushed. This entry then represents the new start of log replay to employ in the event of a crash. For all of the entries encountered before the first un-flushed entry in the scan, the list entry and its corresponding hash entry are removed, and the estimated time to replay that entry&#39;s type of log record is subtracted from R est . 
   In this manner, the CR system  50  has an up-to-date recovery time estimate, R est , at all times. Note that because the estimated recovery times for each type of log record are captured from actual recovery events, this approach permits the CR system  50  to provide extremely accurate estimates that match the exact workload, hardware configuration, database configuration, etc., of the particular DBMS  10 , and R est  adapts over time—especially if a decaying or windowed average is used in the statistics. 
   Returning briefly to step  114  of  FIG. 4 , since the statistics used to calculate R est  are developed over time, the CR system  50  still needs a set of initial estimates for each type of log record when it is first installed. Any reasonable set of guesses can be used for this, since the CR system  50  is self adapting, but more sophistication can also be applied. The inventors prefer to run a small sample workload (i.e., to run optional step  106 ) that generates a few of each type of log record, and then go through crash recovery for that sample log. This sample workload can be run automatically, behind the scenes, at database creation time to populate the CR system  50  with initial statistics. Such a workload typically should only take a few seconds to run. 
   Turning now also to step  112  of  FIG. 4 , the CR system  50  here employs the maximum tolerable recovery time, R max , that has typically been provided as a configuration parameter by the user of the DBMS  10  in step  114 . 
   As described above, the current estimated recovery time, R est , is continually kept current, and the goal is to guarantee that it never becomes greater than R max . The inventors&#39; presently preferred approach to doing this is to define estimated recovery time threshold values x and y, where 0&lt;x&lt;y&lt;R max . The values for x and y split the allowable range of recovery times into three intervals where the current R est  may fall. The first interval (I 1 ) is then used for performance-oriented flushing; the second interval (I 2 ) is used for recovery time-oriented flushing; and the third interval (I 3 ) is used for emergency flushing. Algebraically,
 
I 1 :0&lt;=R est &lt;x
 
I 2 :x&lt;=R est &lt;y
 
I 3 :y&lt;=R est &lt;=R max  
 
In the inventors&#39; experience, x and y should preferably be close to R max , for example, x=0.90*R max  and y=0.95*R max .
 
   While R est  is in the first interval, I 1 , the normal background dirty page flushing algorithm of the DBMS  10  is used. Such algorithms are typically designed to maximize performance. An example is a least-recently-used (LRU) page flushing algorithm. In the first interval, I 1 , this type of page flushing algorithm is appropriate. 
   If R est  enters the second interval, I 2 , however, this means that the estimated recovery time, R est , is unacceptably increasing toward the maximum allowable time, R max . In this interval, the background flushing algorithm is switched from a performance-oriented flushing algorithm to a flushing algorithm that is geared more toward reducing the recovery time. For instance, a first-in-first-out (FIFO) algorithm that flushes the dirty pages in the order in which they are dirtied is more suitable now. The recovery time, which R est  is estimating, is now dominated by the time it takes to replay the log from the oldest un-flushed dirty page forward to the end of the log, so that flushing of the oldest dirty pages reduces the amount of log replay needed for recovery, thus reducing the recovery time and the current value of R est . 
   In normal circumstances, R est  should stay in the first interval, I 1 , most of the time, with only occasional entry into the second interval, I 2 . If the recovery time cannot be kept down even with the more aggressive flushing algorithm used in the second interval, I 2 , and R est  enters the third interval, I 3 , then emergency flushing is performed. When R est  is in the third interval, I 3 , no further write operations are allowed to proceed until the background flushers (e.g., still using a FIFO algorithm) reduce R est  back once again into the second interval, I 2 . In other words, write activity in the DBMS  10  is momentarily blocked while the flushers catch up, to guarantee that the estimated recovery time, R est , never goes above the user-specified maximum allowable recovery time, R max . 
   The CR system  50  has the advantages of learning over time, automatically self-tuning, and taking into account the exact configuration of database, hardware, and workload in use by the DBMS  10 . In real world scenarios, it would be impossible to assemble accurate tables of estimates for all possible combinations of parameters a priori (i.e., using a non-adaptive approach) for use in prior art crash recovery systems, and it would also be impossible for such systems to achieve comparable recovery time levels and accuracy with more generic qualitative estimates. 
   While various embodiments have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the invention should not be limited by any of the above described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.