Database computer system using logical logging to extend recovery6978279Abstract This invention concerns a database computer system and method for making applications recoverable from system crashes. The application state (i.e., address space) is treated as a single object which can be atomically flushed in a manner akin to flushing individual pages in database recovery techniques. To enable this monolithic treatment of the application, executions performed by the application are mapped to logical loggable operations that can be posted to the stable log. Any modifications to the application state are accumulated and the application state is periodically flushed to stable storage using an atomic procedure. The application recovery integrates with database recovery, and effectively eliminates or at least substantially reduces the need for check pointing applications. In addition, optimization techniques are described to make the read, write, and recovery phases more efficient. Atomic flush sets, whether generated from cyclic flush dependencies or otherwise, can be broken apart. This enables an ordered flushing sequence of first flushing a first object and then flushing a second object, rather than having to flush both the first and second objects simultaneously and atomically. Claims 1. In a database computer system having a non-volatile memory, a volatile main memory, and a first object which executes from the main memory, wherein the non-volatile memory includes a stable log, a computer-implemented method comprising the following steps: Description TECHNICAL FIELD
Atomic Flush of Operation Consistent Application State As part of application recovery, the database computer system 50 treats each executing application as a single object, which can be flushed from time to time to stable state in order to preserve snapshots of the application's address space. The database computer system 50 flushes the application state (which can be quite large) in an atomic operation. FIG. 4 shows a portion of the database computer system 50 to illustrate a technique for atomically flushing the application state as a single object. The technique is known as "shadowing." The cache manager 66 maintains two versions of the application state: a current application state 80 kept in cache 64 and a lagging application state 82 kept in stable database 72. The lagging version 82 is the most recent version of the application state that has been flushed to the stable database 72. When the cache manager 66 decides to flush the current cached version 80 of the large application state, the cache manager 66 first writes the current cached version 80 to the stable database to form a copy 80′. When the entire current version of application object has been written to the stable medium 72, the cache manager 66 moves a pointer (as represented by arrow 84) from the lagging version 82 to the new updated version 80′ to place it logically within the stable database. Since the pointer 84 is small, it can be changed with a single page write. This enables the pointer to be moved between the two versions in an atomic operation. The earlier version 82 can then be discarded or overwritten. Mapping Application Executions to Logical Loggable Operations To ensure that operations are replayable during recovery, the operations are atomic and deterministic. An operation is said to be "atomic" if the external world that the operation sees during its execution appears to be constant, and the external world does not see the results of the execution until the operation completes. The operations are said to be "serializable" in that their execution is equivalent to an execution of the operations one at a time. An operation is said to be "deterministic" if, given the same system state as input, the result of execution against this state will always be the same output state. To satisfy the atomic and deterministic criteria, all interactions between an application 60 and the external world (e.g., an end user, a database, a file, another application, etc.) are mediated by the resource manager 62. In this manner, the application is treated as a black box whose internal changes are not visible to the external world. These internal changes are not captured nor recorded in the volatile log. The application address space is intermittently exposed or impacted, however, every time the application interacts with the external world via the resource manager 62. Interactions with the resource manager thereby give rise to loggable operations that reflect different transitions between application states as the application executes. The application state transformations between interaction are hence logged as operations in the volatile log 68. At recovery, these logged state transformation operations are replayed, with the affect being that the hidden internal changes leading to each logged state are repeated. FIG. 5 shows the system architecture of the database computer system 50 in more detail. Individual application programs 60(1)-60(N) are executing on the computer. The resource manager 62 provides an interface layer between each application and the external world. In this illustration, the resource manager 62 mediates all communication to and from the applications 60(1)-60(N) with respect to an end user at a terminal 86, a data file in the cache 64, or another application. To interact with any external component, an application calls to the resource manager 62 and the resource manager 62 facilitates the task requested by the application. It does this by logging the application operation(s) and then calling the requested system service that performs the requested task. This intervening resource manager layer is said to "wrap" the requested task. Execution of an application 60 is characterized as a series of loggable atomic operations whose replay can recover the application. To capture application execution as a series of loggable operations, the computer system 50 treats the code execution between calls in the application as the log operation. Said another way, the resource manager 62 logs the operations as if it were calling the application, rather than the application calling to the resource manager. This change in perspective results in an application operation being "called" via a return from the resource manager 62 to the application 60. The application operation "returns" to the resource manager via the application's next call. Given this shift in perspective, application execution is mapped into one of five logical operations that are loggable in the volatile log 68. The five logical operations are execute, initiate, terminate, read, and write. 1. Execute: A call from an application 60 to the resource manager 62 is treated by the system 50 as a return from an application operation. A return to the application 60 from the resource manager 62 is treated as a call to an application operation. The application execution between these interactions with the resource manager (i.e., starting at a return from the resource manager and ending at the next call from the application to the resource manager) is mapped to an execute operation. FIG. 6 shows the logical execute operation. Suppose that the application is at a state A1 following a return from the resource manager. The application executes instructions internal to the application, whose effects are hidden from the external world. This execution transforms the application from a state A1 to a state A2. Following this execution, the application calls to the resource manager. The resource manager logs the application Execute operation Ex(A1) denoting the transformation of application A from state A1 to state A2 to the volatile log for subsequent posting by the log manager into the stable log. As denoted in FIG. 6, the resource manager logs the application identifier A, its state ID 2, and the execute operation Ex that resulted in the application state A2. 2. Initiate: This logical operation represents the application's first state transition prior to the initial call to the resource manager 62. The resource manager 62 is notified when the application is launched. The initial application state, e.g. its static code and data structures, is read from stable memory during the launch. This action is mapped to a loggable initiate operation. The initiate operation ends when the resource manager makes the initial invocation of the application. The resource manager logs the In(A) to the volatile log for subsequent posting to the stable log. 3. Terminate: The terminate logical operation represents the application's final call to the resource manager, instructing the resource manager to terminate the application. This final application state transformation generates a "final state" for the application that can be written back to the stable memory. When control returns to the application, the application is expected to terminate cleanly and free up its resources. It is not expected to call the resource manager again. The resource manager logs the Terminate(A) operation to the volatile log for subsequent posting to the stable log. 4. Read: The application 60 calls the resource manager 62 to read from an external system state, such as from a database page, perhaps in the cache 64. The resource manager 62 performs the read task, constructs a log record for this as a read operation that includes in the logged information the data values read and sufficient information so that the data read can be moved to the appropriate input buffers of the application state. The data is then moved to the application's input buffers and the log record is posted to the volatile log 68 and subsequently to the stable log. The return parameters of the read (i.e. the parameters that do not modify application state until control is returned to the application) become part of the log record for the next execute operation. FIG. 7 shows a logical read operation following the execute operation described above with respect to FIG. 6. Suppose that the call made by the application to the resource manager at state A2 is a call for a read task. The resource manager performs the read task and returns the values read from the object to the application. This return creates a change in application state to state A3. The resource manager logs the application identifier A and state identifier 3, the value of object O1, and the read operation R resulting in the application state A3. Thereafter, the log manager writes this log record to the volatile log and subsequently posts it into the stable log. 5. Write: The application 60 calls the resource manager 62 to write to external system state, such as to a database page that might already be in a buffer in cache 64. The resource manager 64 performs the write, logs the values written O. Val and the identity of the object o written in the log record in the volatile log 68. Any return parameters become part of the log record for the following execute operation. FIG. 8 shows a write operation following the execute operation described above with respect to FIG. 6. Suppose that the call made by the application to the resource manager at state A2 is a call for a write task. The resource manager performs the write task, logs the object identity O, its state ID 2, the values written O2, and the write operation W that results in the object state O2. The resource manager then returns any parameters resulting from the write task to the application. These return parameters are part of the input to the next execute operation. One benefit of mapping the application execution into loggable operations is that these operations can be expressed entirely in terms of the application states. For the execute operation, for example, the application begins in one state and is transformed to another state by internal executions of the application. To the outside world, the execute operation can therefore be expressed as reading a first application state before the internal executions, and writing a transformed application state resulting from the internal executions. Table 1 shows the application operations characterized in terms of application states.
It is noted that there may be interactions that cannot be mapped into these five operations. For example, reading a message may consume the message as well; i.e. the application writes to the message queue by removing the message. This interaction is both a read and a write that cannot be optimized as above. FIG. 9 shows an example series of loggable operations that are mapped from application executions. The loggable operations are designated by a circle: the legend "Int" within a circle stands for an initiate operation; the legend "Ex" within a circle represents an execute operation; the legend "R" within a circle stands for a read operation; the legend "W" within a circle represents a write operation; and the legend "T" within a circle stands for a terminate operation. The initiate operation 90 writes the initial application state A1. The resource manager includes in a single log record an application identity A, its state ID 1, and the name of the operation Int. The log record is written in the volatile log and subsequently posted to the stable log. An execute operation 92 reads the application state A1, performs some internal executions, and writes the application state A2 by means of the application executing beginning in at state A1 and the execution resulting in state A2. The resource manager logs the application identifier A, a state ID 2, and the execution operation Ex that resulted in the application state A2. A read operation 94 reads the application state A2 and an object O1. As above, the shorthand notation "O1" means an object with an identifier O taken at a state ID "1." The object value O1 is read into the application buffers and results in a next application state A3. The resource manager logs the application identifier A, its state ID 3, and the read operation R that resulted in the application state A3. In addition, the resource manager includes the object value O1 in the log record. Writing the values read from the object into the log record ensures that the values are available for redo of the application operations during recovery in the event that the object O has been subsequently updated and a subsequent value flushed to the stable database. Unfortunately, in some cases, the values read from the object O can be large and hence logging the entire object value is not desirable. Moreover, the log record containing the object values is separate from, and often duplicative of, the data pages holding the object O1 which are occasionally flushed to the stable database. The system and methods described herein address this problem by optimizing the read operation to reduce the amount of data placed on the log. This optimization involves development of a new cache manager, a topic that is discussed below with reference to FIGS. 10-14 in more detail. An execute operation 96 transforms the application state from state A3 to state A4. The resource manager logs the application identifier A, a state ID 4, and the execution operation Ex that resulted in the application state A4. A write operation 98 writes a modified version of the previously read object, designated as O2. The resource manager logs the object identifier O, its state ID 2, the value O2 written, and the write operation W that resulted in object state O2. This ensures that the write parameters are available on the log for redo of the application operations during recovery in the event that the object O2 is not flushed to the stable database. Similar to the read case, the value O2 can be large and duplicated elsewhere in the system, and thus logging the entire object value is not desirable. The system and methods described herein address this problem by optimizing the write operation to avoid logging the value of O, by logging the application state that provided the data value for O. This write optimization involves development of a new cache manager, a topic that is discussed below with reference to FIGS. 15-23 in more detail. An execute operation 100 transforms the application state from state A4 to state A5. The resource manager logs the application identifier A, a state ID 5, and the execution operation Ex that resulted in the application state A5. A terminate operation 102 writes the final application state A6. The resource manager writes in a log record the application identifier A, a state ID 6, and the termination operation T that resulted in the application state A6. The changes to the application during these operations are accumulated in the application state stored in the volatile cache. From time to time, the cache manager flushes the application state to stable storage. The flushed application state is tagged with a state ID. The flushing of the application state effectively installs all application operations which have been logged in the stable log that have a state ID less than the state ID of the flushed application state. General Recovery Following a system failure, the database computer system invokes a recovery manager 71 to recover the data pages (and other data objects) and application state lost during the crash. During redo recovery, the recovery manager 71 retrieves the most recently flushed data objects and application objects in the stable database and replays the operations in the log against the stable objects. The recovery manager 71 can be implemented as a conventional recovery manager which replays the stable log, beginning at a point known to be earlier than the oldest logged operation that was not yet installed. The recovery manager compares the state ID of each logged operation in the stable log with the state ID of a retrieved data object or application object. If the state ID of the logged operation is later than the state ID of the stable object, the recovery manager redoes that logged operation. This redo process returns the database computer system to the previous state in which it was operating immediately prior to the crash, including the recovered applications. Another aspect of this invention involves techniques to optimize recovery to avoid replaying operations that are rendered obsolete by subsequent operations. In this case, the recovery manager is implemented to handle the recovery optimization techniques, as is described in more detail below with reference to FIGS. 24-27. Read Optimization In the recovery scheme described above, the read operation involves writing all of the contents read from the object to the stable log in association with the read operation. The logged operation can then described as reading and writing application state. This type of operation, in which only a single object is written, and at most that object is read, is referred to as a "physiological operation." These operations are useful in that using only such operations, recovery can be implemented using conventional cache managers and cache management techniques. The cache manager need not be concerned about object flushing sequence or preserving a certain object state because any data value obtained from an object which was read, and hence which is needed to redo an application operation is available directly from the stable log. The benefits accruing to cache management as a result of logging only physiological operations come at a cost. Treating an application read as a physiological operation requires writing data, and often large amounts of data, to the stable log. This reduces efficiency in the logging process and consumes I/O resources. Moreover, the data written to the stable log is a copy of data in an object, which is maintained in volatile cache and occasionally flushed to the stable database. It is wasteful to duplicate large data objects in log records when these objects are available elsewhere. Accordingly, an aspect of this invention is to optimize the logged read operation to avoid writing the object's data to the log record. Generally, the optimizing technique eliminates logging the read values by substituting, for the read values, names of the objects from where the values are read in the log record. That is, rather than logging the object value that is read, the read optimization technique involves logging the identity of the object that is the source of the values being read. We call this a "logical read" and denote it by R(A,O), indicating that application A reads data object O for the input value needed to transform application A's state; it does not get this input value from the log record. For instance, a log record for the logical read operation includes the application object's identifier A, its state ID, A.SID, the data object's identifier O the data object's state ID, O.SID, and an indication that a read operation was performed: Other information may also be included, such as an index to a specific value set contained in the object. Posting information that names the source of a data value, rather than the value itself, substantially reduces the amount of information placed on the stable log. When redoing a logged operation during recovery, the recovery manager 71 uses the object name to locate the object and reads the value from that object. Unfortunately, substituting object names for the actual values comes at a cost of introducing dependencies between the objects in the cache. Attention must now be paid to the order in which objects are flushed to stable storage. If objects are flushed out of proper sequence, a particular state of an object may be irretrievably lost. An object name contained in a logged operation would not enable restoration of the object values needed by the operation if the data value for the object is not the same as the value that was originally read from the object during normal execution. FIG. 10 illustrates the dependency issue introduced by the read optimization technique. FIG. 10 shows a sequence of operations comprising a read operation 110, an execute operation 112, a write operation 114, and an execute operation 116. These operations are identical to the operations 94-100 in FIG. 9. However, unlike the procedure in FIG. 9, the value of the object that is read at operation 110 is not posted to the log. Instead, only the object identifier O and state ID are posted. The object identifier and state ID identify the exact data value needed by the logged operation. The operation sequence in FIG. 10 introduces a dependency between the application object A and the data object O. Assume, for example, that the cache manager flushes the data object O to stable memory at state O2 after the write operation 114 without having previously flushed the application object A to install the operations 110 and 112 preceding the write operation 114. Then, before the cache manager has an opportunity to flush the application object A, the system crashes. Upon replay of the log, the computer database system is unable to redo the operations to resurrect the true application states A2-A4 because the object state O1 is not available. That is, the stable database only contains the flushed object O at state 2, not at its initial state 1. (Note that we do not describe the write 114 as reading application state A3. Rather, write 114 is a physical write that gets the value written as O2 from the log record. This avoids additional flush dependencies.) This dependency is explained in the context of an installation graph as a "read-write edge." That is, the write operation writes data into a read variable set which is read in an operation preceding the write operation, thereby overwriting needed data to carry out the read operation during recovery. Installation graphs and the read-write edge case are described in detail in a publication by David B. Lomet and Mark R. Tuttle, entitled "Redo Recovery after System Crashes," Proceedings of the 21st VLDB Conference, Zurich Switzerland, 1995. This publication is incorporated by reference. To manage dependencies, the database computer system is equipped with a cache manager that is attentive to flushing sequence. The cache manager is designed to ensure that an application object is flushed to stable memory, thereby installing its operations, before any modified data objects from which the application has read are flushed to stable memory. The cache manager implements an object table which tracks active objects in the volatile cache, and monitors flush order dependencies between those objects. FIG. 11 shows a cache manager 120 with an object table 122. The object table 122 holds a list of objects that are presently stored, in the volatile cache or that have flush dependencies with objects presently stored. These objects may be in the form of application objects or data objects. Typically, the data objects have volatile (i.e. cache) locations that are identified as memory pages. With regard to data objects, the object table 122 is similar to prior art "page tables." However, unlike prior art page tables, the object table 122 also maintains a list of application objects, with each application object comprising the application address space, and information with each entry that is used to manage flush dependencies. The object table 122 shows an entry 124 for the application object A and an entry 126 for the data object O which reflect respective object states following the read operation 110. These entries contain information pertaining to the objects which is organized in data structures 128 and 130. Each data structure has an object identifier field 131, 132 to hold the object identifier (e.g., A or O), a state identifier field 133, 134 to hold the state ID for the value of the object, a dirty flag field 135, 136 which holds a flag bit indicating whether or not the object has been modified in volatile cache without those modifications being flushed to stable memory, and a cache location field 137, 138 to hold an address to a location in volatile cache where the current cached value of the object physically resides. The data structure may further have a stable location field to hold an address of the object in stable memory, although this field is not shown in this example. Alternatively, the stable location may be derivable from the object identifier, objectID, in field 131, 132. Each data structure 128, 130 also has a predecessor field 139, 140 to hold information for any predecessor object. An object is a "predecessor object" to a subject object if that object must be flushed prior to flushing the subject object. The predecessor field 139, 140 enables the object table 120 to track dependencies between the operations. For the read operation, the dependency cases can be resolved into two rules: (1) only an application object can be a predecessor; and (2) an application object has no predecessor. The underlying reason for these rules can be better understood with a brief introduction to a "write graph," which is a graph derived from an "installation graph," and is described in the above incorporated article by Lomet and Tuttle. FIG. 12 shows a write graph 144 for a read-write edge in which a read operation reads a data object O at a first state during execution of the application object A, and subsequently a write operation writes the data object O to create a second state of that data object. In write graph notation, the circles represent nodes. A write graph node n is characterized by a set of operations ops(n) and a set vars(n) of variables (i.e., objects) written by the operations in ops(n). There is an edge between write graph nodes m and n if there is an installation graph edge between an operation in ops(m) and an operation in ops(n). The cache manager installs the operations of ops(n) by flushing the objects of vars(n) atomically. Write graph 144 has two nodes, an application node 146 with vars(146)={A} and a node 148 with vars(148)={O}. The application node 146 shows that the read operation has been performed which changes the application state (by reading values into the application buffers) and that the application has continued its execution with an Ex(A) operation. The data node 148 shows that the write operation affects the object state. Write graph 144 demonstrates a flush order dependency between the application object and data object. To ensure correct recovery of the application, the cache manager flushes the application object represented by node 146, thereby installing the read operation, prior to flushing the data object represented by node 148. This write graph further illustrates that, for a logical read operation, an application object A has no predecessor for which it is concerned. All paths between nodes 146 and 148 are at most a length of one. Only the data object O has a predecessor and that predecessor is the application object A (which read it). The logical read operation, by itself, thus reduces to a straightforward result. With reference again to FIG. 11, the predecessor field 140 denotes a list of predecessors for the object O entry 130. The 19 predecessor entry shown contains the identifier for the application object A data record 128, denoted as the predecessor object PO. This predecessor is established when the read operation 110 (FIG. 10) is encountered. The predecessor entry also includes a state identifier for the originating object O, i.e., O.SID. That is, in the general case, an entry on the predecessor list is represented as: It is noted that a data object may have more than one predecessor. Hence, the predecessor field 140 may contain a set of entries for multiple predecessor objects. Since FIG. 11 illustrates a read operation, the application object has no predecessor. As a result, the predecessor field 139 for the application A data structure 128 contains a null pointer, denoting the empty list. Each data structure 128, 130 further includes a successor field 141, 142 to hold information for any successor object. An object is a "successor object" of a subject object if the subject object must be flushed before the successor object is flushed. The successor field 141, 142 is primarily used as a bookkeeping function, to track successor 1 objects, as it adds no additional information that is not already contained in the predecessor field. When flushing an object, the cache manager ensures that all real predecessors are flushed beforehand. After flushing, the cache manager uses successors only to clean up by removing the flushed object as a predecessor in other predecessor lists. Less information is needed for successors, for example, object state ID, O.SID is not needed. The cleanup is unconditional, taking place regardless of whether the predecessor/successor is real or potential. It is noted, however, in an alternative implementation, the successor field may be primarily relied upon, with the predecessor field serving a secondary bookkeeping role. The first statement of the read operation is that only an application object can be a predecessor. The converse to this statement is that only an application object can have a successor. In FIG. 11, the successor field 141 of the application A data structure 128 contains an entry for the object O data record 130. The successor entry is established when the read operation 110 (FIG. 10) is encountered. The data object O has no successor. As a result, the successor field 142 for the object O data structure 130 contains a null pointer indicating an empty list. Through the predecessor and successor fields in the object table, the cache manager 120 tracks dependencies between the objects. When the cache manager 120 decides to flush an object to stable memory, the cache manager first checks the object table 122, and particularly, the predecessor field of the object entry to determine whether or not the object to be flushed has any predecessors. If a predecessor is listed for that object, the cache manager will flush the predecessor object, assuming it is "real," prior to flushing the subject object. The cache manager 120 distinguishes between "real" and "potential" predecessors. A "real" predecessor object is one that has read an object whose state has been changed by subsequent operations since the time the object was read by the predecessor. A real predecessor must be flushed prior to the subject object to ensure retention of a correct state in the stable database. In contrast, a "potential" predecessor object is one that has read an object whose state has not changed since the time the object was recorded as a predecessor. A potential predecessor does not require priority flushing, although the cache manager continues to track potential predecessors because they may turn into real predecessors. These are tracked by retaining object table entries for objects with predecessors, even if they themselves are flushed and their values removed from the cache. FIG. 10 demonstrates the difference between real and potential predecessors. At the read operation 110, the cache manager updates the predecessor list for the data object O in the object table to reflect that the application object A is a predecessor. At this point, however, application object A is only a "potential" predecessor because object O's value is still the same. Hence, application object A does not require flushing prior to the data object O as the same application state can be recovered from re-reading data object O. However, at the write operation 114, the predecessor becomes a "real" predecessor. Here, the data object O is modified by the write operation 114, thus changing the state of O that the application object A read previously in the read operation 110. Now, application object A needs to be flushed prior to the data object O, or else application object A will not be restored to the same application state during recovery because the state 1 of data object O is irretrievably lost. The cache manager determines whether a predecessor is "real" or "potential" by comparing the current state identifier of the object to be flushed against the state identifier of the same object as recorded in the entry of the predecessor list. For example, suppose the cache manager 120 decides to flush data object O following the execute operation 112 (FIG. 10). The cache manager compares the current state ID of the data object O, which is still state 1 at that point, with the state ID recorded in the entry for the predecessor application object A contained in the predecessor field 140. In this case, object O's state ID in the entry is also 1. The state IDs match and thus, the application object A is only a potential predecessor at this point. The cache manager is free to flush the data object O at this point without first flushing application A. The predecessor entry for application object A is maintained, however, in the predecessor field 140 of the object O entry 128. Now, suppose that the cache manager decides to flush the data object O following the write operation 114 (FIG. 10). The cache manager compares the current state ID of the data object O, which is now state 2 following the write operation, with the state ID recorded in the entry for the predecessor application object A contained in the predecessor field 140. As before, the object state ID in the entry is 1. The state IDs no longer match. Thus, the application object A has now become a real predecessor. When faced with a real predecessor, the cache manager must first flush the predecessor, in this case the application object A, prior to flushing the data object O. Flushing the application object A effectively installs all of the operations (which in the example, all update application A) through the write operation 114 (which accounts for the new object state O2). Once the application object A is flushed, the predecessor entry contained in the data object O's predecessor list 140 is removed. The cache manager deletes the predecessor entry from the predecessor list 140. Since application object A may also be a predecessor for other objects, the cache manager uses the application object A's successor list 141 to inform any successor data objects (including data object O) that application object A has been flushed and is no longer a predecessor to them. When an application terminates, the cache manager scans the successor field 141 of the application object A to remove from the predecessor field of successor objects any entries to the terminated application. FIG. 13 shows an alternative construction of the object table. In FIG. 13, the object table 150 contains an entry 152 for a data object O at state 1. This entry includes a data structure 154 having an object identifier field 156, a dirty flag field 158, a cache location field 160, a predecessor field 162, and a successor field 164. In data structure 154, the predecessor field 162 contains an index to a separate predecessor table 166. For each predecessor object, the predecessor field 162 contains a unique index to an entry in the predecessor table 166 containing information used to identify and locate the predecessor object. In this example, the entry in the predecessor table 166 contains a real bit and an object identifier of the predecessor (i.e., objectIDPred=A). The real bit which is set (i.e., to a binary value 1) if the predecessor object is a "real" predecessor and is reset (i.e., to a binary value 0) if the predecessor object is a "potential" predecessor. When the cache manager decides to flush the data object O, the cache manager no longer compares state IDs to determine whether a predecessor is real or potential. Instead, the cache manager examines the real bit. If the real bit is set, the cache manager knows it must flush the associated predecessor object before flushing the subject object. The "real" bit is initialized to zero when an object O is read by an application. At the time that the object O is subsequently written, all current potential predecessors (which have real bit set to zero) have this bit set to one. The read optimization techniques described in this section are beneficial because they eliminate having to post the values obtained during a read operation onto the log. Instead, the log only contains information to identify the object that was read. While this reduced the amount of data to be logged, the read optimization techniques introduced flush dependencies between objects. The cache manager thus keeps an object table which tracks dependencies to ensure a proper flushing order. Write Optimization In the general recovery scheme introduced at the beginning of this detailed disclosure, a write operation involves posting, to the stable log in association with the write operation, all of the values that are written to an object. The logged operation can be described as simply writing the object state of a data object. This yields a physiological operation that can be handled using conventional cache managers and cache management techniques. The conventional cache manager need not be concerned with object flushing sequence or preserving a certain object state because any data value written to an object, and hence is needed during recovery, is available directly from the stable log. However, the data values written to the stable log are duplicative of values in the application object's output buffers. Thus, the logging effort is inefficient and computationally expensive. Accordingly, an aspect of this invention is to optimize the logged write operation to avoid posting the written values to the log record. Generally, the write optimizing technique eliminates logging the written values by logging the identity of the object from where the values are obtained, along with its state ID. Posting information that names the source object and its state ID, rather than the values themselves, substantially reduces the amount of information placed on the stable log. Such writes are called "logical writes," and are denoted by W(A,O) indicating that application A is writing data object O. A logical write operation results in the posting of a single log record to the stable log, wherein the log record contains the data object identifier O, the data object O's state ID, O.SID, the application object identifier A, its state ID, A.SID, and an indication that a write operation W was performed: At recovery, operations on that source object (typically, an application object) are replayed to its state at the time of the execution of the write operation. The regenerated application state inherently includes the state of the output buffers needed to replay the write operation. Hence, logging the after-image of the data object resulting from the write can be avoided. FIG. 14 shows the sequence of operations identical to FIG. 10, including the read operation 110, the execute operation 112, the write operation 114, and the execute operation 116. The write operation 114 involves reading application state A3 and writing data object state O2. Unlike FIG. 10, however, the value written to object O (i.e., O2) at the write operation 114 is not posted to the log. Instead, the cache manager logs the identify of the data object that is written (i.e., O), the data object's state ID 2, the identity of the application object A which is the source of the values written, object A's state ID 3, and the write operation W which results in object state O2. Posting these objects' identities consumes much less memory and fewer I/O resources than posting the entire value of the object state O2 to the stable log. The application object identifier A and its state ID identify the exact data value needed by the logged write operation. The write optimization technique comes at the expense of introducing more flush order dependencies to ensure proper installation of operations. In the read optimization case described in the preceding section, flush order dependencies are comparatively easy to handle. The dependency chain is at most one link in length. The application state in a read dependency has no predecessors, and hence nothing ever needs to be flushed before the application state itself. When the cache manager decides to flush an object, it flushes all predecessor objects (i.e., any predecessor application objects) and then the subject object. The read dependencies are thus "acyclic," meaning that each object can be flushed atomically independently of other objects in a prescribed order, without requiring the simultaneous atomic flushing of multiple objects. Unfortunately, flush dependencies arising from write operations, when combined with dependencies arising from read operations, can result in "cyclic" flush dependencies. This means that an object that is both read and written by an application must be flushed both before (actually, not later than) and after (actually, not earlier than) the application object. Cyclic flush dependencies require atomically flushing both the data object and the application object simultaneously, which presents significant complications. FIG. 15 illustrates a cyclic dependency introduced by the write optimization technique. FIG. 15 shows a sequence of operations and how the operations are represented as write graphs. The sequence of logical operations includes a read operation 190, an execute operation 192, a write operation 194, an execute operation 196, a read operation 198, and a write operation 200. Corresponding write graphs 202-212 are provided below each operation. The write graphs consist of nodes. Each node n identifies a set of uninstalled operations (i.e., the abbreviations above the dotted line within the nodes), denoted ops(n), in correlation with a set of data or application objects written by the operations (i.e., the abbreviations below the dotted line within the nodes), denoted vars(n). The cache manager usually sees the operations in serialization order. Including the operations in the write graphs in that order is fine because serialization is stronger than installation order. At the read operation 190, the corresponding write graph 202 consists of a node containing application object A. The read operation 190 reads application state Al and data object state O1 and writes application state A2. This is reflected in the write graph 202 as involving two nodes: one node containing the application object A and one node containing the data object O. The read operation is registered in the node containing the application object A because the operation writes the application state. The notation R190 (i.e., read operation 190) in the node containing the application object A indicates that the read operation writes object A. No operation is placed in the node containing object O, because the read operation does not write the object state. When a new operation occurs, the operation is added to the write graph as follows: 1. Merge into a single node n all nodes n for which vars(n) intersect (write(Op) intersect read(Op)) is not null, where write(Op) is the set of variables written by operation Op, and read(Op) is the set of variables read by Op. 2. For each node p≠m, set vars(p)=(vars(p)-nx(Op)). This removes from vars(p) objects that become not exposed, where nx(Op)=write(Op)-Read(Op). 3. Include a write-write edge so that unexposed objects that were removed from vars(p) are ordered to flush to the stable database after exposed objects remaining in vars(p) are flushed to the stable database. 4. Include a 'reverse' or 'inverse' write-read edge to ensure that objects in node p are not exposed when they are flushed to install their operations. In other words, an edge is defined from each node q to a node p, where the operation from q reads the final version of the object in the node p. Previously, each node p had node q as a potential predecessor. 5. If the resulting graph has a cycle, collapse each strongly connected region of the graph into a single node. Each such node n has ops(n) that equals the union of ops(p) of nodes p contained in its strongly connected region and vars(n) that equals the union of vars(p). The read operation 190 introduces a potential read-write edge in write graph 202 from the node containing A to the node containing O. This potential edge (shown as a dashed arrow) indicates that a subsequent write or update of data object O to change its state will create a real edge, thereby establishing a flush order dependency between objects A and O. The direction of the arrow represents the flushing sequence in the flush order dependency. The arrow points from the node containing object A to the node containing object O (i.e., A→O) to represent that the application object A must be flushed before the data object O. The execute operation 192 reads the application state A2 and writes the application state A3. The node containing the object A in the write graph 204 is expanded to include the execute operation (i.e., Ex192) because the execute operation 196 writes application state A3. The node containing object O remains void of any operations. The write operation 194 reads application state A3 and writes the object state O2. The write operation is reflected in the write graph 206 by placing the notation W194 (i.e., write operation 194) in the node containing the data object O. Notice that the write operation 194 does not write the application state, and thus the write operation is not added to the node containing application A. The write graph 206 also shows a real read-write edge caused by the read and write operations 190 and 194. That is, the previous potential edge has now been converted to a real edge by virtue of the sequence of read-write operations 190 and 194. This read-write edge introduces a flush order dependency between application object A and data object O. To ensure correct recovery of the application, the cache manager must flush the application object A, thereby installing the read operation R190, prior to flushing the data object O. The read-write edge is indicated by a solid arrow, the direction of which indicates the flushing sequence in the flush order dependency. Here, the application object A must be flushed before the data object O and thus, the arrow points from the node containing object A to the node containing object O (i.e., A→O). The write operation 194 also introduces a potential edge in write graph 206 from the node containing O to the node containing A. This potential edge indicates that a subsequent write or update of data object A to change its state will create a real edge, thereby establishing a flush order dependency between objects A and O. The execute operation 196 reads application state A3 and writes application state A4. Since the execute operation 196 writes application object A, the application node A of the write graph 208 is expanded to include that operation (i.e., Ex196). The execute operation 196 does not write the data object state, and thus the execute operation is not added to the node containing data object O. The execute operation 196 introduces a real dependency between the data object O and the application object A, as indicated by the write-execute edge. This dependency arises because the data object state O2 can only be regenerated from values found in the output buffers at application state A3, which is about to change as a result of the execute operation 196. Since the write optimization technique eliminates logging of the write values to the stable log, the recovery manager must obtain those values from the output buffers of application state A3 to replay the write operation 194. To ensure correct recovery of the data object O, the cache manager must flush the data object O, thereby installing the write operation 194 which produces state O2, prior to flushing the application object A. The write-execute edge is indicated by the solid arrow pointing from the node containing O to the node containing A, thereby indicating an O→A flushing sequence in the flush order dependency. Unfortunately, the two dependencies between objects A and O are cyclic (i.e., A→O→A). As shown in the write graph 208, application object A must be installed before data object O (i.e., A→O) to ensure recovery of the application and the data object O must be installed before the application object A (i.e., O→A) to enable replay of the write operation 194. This cycle can only be handled in full by flushing both objects A and O simultaneously and atomically. This poses a problem. To break such cycles, the cache manager 66 assumes an active role by timely introducing "blind writes" that effectively preserve the state of data object on a log record. In a blind write operation, the current value of the data object O is written to the log in a manner similar to the general unoptimized write case discussed earlier in this disclosure. The blind write leaves the value of data object O unchanged, but writes an after-image of its value on the stable log. As a result, the data object O can be regenerated from this log record, rather than relying on regeneration of a specific state of the application object A. Accordingly, the dependency cycle is broken. This enables an ordered flushing sequence of first flushing the application object A and then flushing the data object O. That is, once the cycle is broken, the cache manager can atomically flush objects one-by-one one, rather than having to flush multiple objects simultaneously and atomically. The cache manager flushes the objects one-by-one according to a predetermined acyclic flushing sequence. Preferably, as described above, the application object A is flushed before the data object O is flushed. Thus, for example, a method in accordance with the present invention comprises the step of flushing the data object O to the non-volatile memory (i.e., the stable database) after the application object A has been flushed to the non-volatile memory. However, according to another embodiment of the present invention, the acyclic flushing sequence is arranged such that it is the application object that is written to the log so that the data object O is flushed before the application object A is flushed. The way the cache manager identifies cycles and actively imposes blind writes is best understood in the context of the write graphs. The process, as it pertains to write graphs, involves three general steps. Also introduced is the "intermediate write graph," which is the graph formed before the cycles are collapsed. 1. Add each new operation to the intermediate write graph, either including it in a node with existing operations or giving it a node of its own. The intermediate write graph can have cycles. 2. Collapse nodes affected by cycles into a single node n (i.e. all intermediate write graph nodes of the strongly connected region are collapsed into a single write graph node.). The resulting node n has vars(n) consisting of multiple objects. 3. Remove all objects, but one, from the single node. This reduces vars(n) to containing a single object that needs to be flushed in order to install the operations of the node n. The removal of objects can be accomplished through normal write operations, or through a series of blind writes. These three steps result in a new write graph containing nodes p with vars(p) having a single variable that can be flushed by itself. The edges connecting these nodes impose an order to the flushing of the objects, but the need to atomically flush multiple objects is removed. The additional log operations that make the flush sequence possible must be on the stable log. In other words, the operations must be on the stable log before the write graph node operations can be installed. This is a new refinement of the write-ahead log protocol, which we now interpret as requiring that all operations that played a role in defining a write node n (the operations of ops(n) and the operations that make Write(n)-vars(n) unexposed) must be on the log prior to flushing vars(n). The edges that impose a flushing order are determined by a predetermined acyclic flushing sequence. The acyclic flushing sequence is structured such that the object that is removed from the cycle dependency by the blind write is flushed to the stable database after the other object of the original cycle dependency. In other words, the object that is not removed from the cycle dependency by the blind write is flushed to the stable database before the object that is removed from the cycle dependency is flushed to the stable database. The inventor has determined that such an acyclic flushing sequence ensures recovery while providing effective cache management. Step 1: Build the Intermediate Write Graph The intermediate write graph is constructed by the cache manager 66 by performing the following steps for each operation: Merge into a single node m all nodes n for which vars(n) intersect (write(Op) intersect read(Op)) is not null, where write(Op) is the set of variables written by operation Op, and read(Op) is the set of variables read by Op. 1. Intersect the object(s) of step 1 with each set of existing objects associated with a present write graph node n, i.e. objects in vars(n). 1.2. If all intersections are null, put the operation into its own node. 1.3. If an intersection is not null, merge all nodes with non-null intersections with the objects of step 1 into a single node. 1.4. Form edges between the new or changed intermediate write graph node n and any other node m based on when edges exist between the operations of ops(m) and ops(n) in the installation graph. 2. Remove the objects nx(Op)=write(Op)-read(Op) from vars(p) of any other node that currently contains them. 3. Include a write-write edge so that unexposed objects that were removed from vars(p) are ordered to flush to the stable database after exposed objects remaining in vars(p) are flushed to the stable database. 4. Include a 'reverse' or 'inverse' write-read edge to ensure that objects in node p are not exposed when they are flushed to install their operations. In other words, an edge is defined from each node q to a node p, where the operation from q reads the final version of the object in the node p. Previously, each node p had node q as a potential predecessor. This method is repeated as new operations are executed and the intermediate write graph is built one operation at a time in operation execution order. A more detailed construction of one exemplary cache manager, and an object table which tracks write dependencies in a manner which effectively handles multi-object nodes and blind write strategies, is described below with reference to FIGS. 18-23. Step 2: Collapse Intermediate Write Graph Cycles When a cycle is created, such as the cycle between the nodes containing A and O in the intermediate write graph 208 of FIG. 15, the affected nodes are collapsed into a single node. That is, all intermediate write graph nodes of a strongly connected region are collapsed into a single write graph node. Write graph 210 shows a combined node containing both objects A and O. This combined node contains the union of all operations and objects from the original two nodes. Collapsing intermediate write graph 208 results in the upper node of write graph 210. (The write graph is defined to be acyclic, while the intermediate write graph has cycles.) Step 3: Reduce Objects in Node to One Object Forming a combined node containing both A and O has not removed the dependency cycle; rather, both A and O must still be installed atomically together. To break the cycle so that variables can be flushed one by one, all but one object is removed from the node containing multiple objects. This can be done as a result of normal operation, or through a series of blind writes imposed by the cache manager. With continuing reference to FIG. 15, the read operation 198 involves reading both the data object state O2 and a new application state B1, and writing application state B2. The read operation 198 is reflected in the write graph 210 by addition of a node to contain object B and the inclusion of R198 (i.e., read operation 198) in that node. Additionally, the read operation 198 introduces a potential read-write edge from the node containing B to the node containing A, O. This potential edge indicates that a subsequent write or update of data object O to change its state will establish a flush order dependency between objects B and O in which the read operation 198 must be installed (by flushing object B) before installation of the operations 190-196. The write operation 200 reads the application state A4 and writes object state O3. The corresponding write graph 212 is expanded to include a third node which contains object O and W200 (i.e., write operation 200). This operation does not join the existing node containing A,O because write(200) intersect read(200) is null. The potential read-write edge becomes a real "inverse write-read" edge as a result of this write operation 200. The read operation 198 (R198) has read the last version of O written by write operation 194 (W194). This means that a real flush order dependency now exists because data object O's state has been changed in the write operation 200. The flush order dependency dictates that the operation 198 in the node containing object B must be installed prior to the operations 190-196 in the node containing objects A,O. A second flush order dependency is also created by a read-write edge resulting from the write operation. In this dependency, the application object B must be flushed, thereby installing the read operation 198, prior to flushing the data object O. The purpose of the inverse write-read edge is to ensure that data object O is not exposed when the node with operations 190-196 has no predecessors. This permits the operations 190-196 to be installed by flushing only A. Notice that the result of write operation 200 removes data object O from the node containing operations 190-196. An object can only reside in one write graph node, which is the last node to write the object. Data object O is in nx(200) and hence is removed from the node containing operations 190-196. Here, the node containing write operation 200 is the last node to write object O, and hence, data object O resides only in that node. No subsequent operation can remove it from that node without also writing it. Because W194 and W200 both write data object O, and replay of W194 does not guarantee the ability to replay W200, there is an installation edge from W194 to W200. This edge results in a write graph edge from the node with operations 190-196 to the node with operation 200. There is also an edge from R190 to W200 so this is a case where a write graph edge results from two installation graph edges. This is a case in which an object is removed from a multi-object node as a result of normal operation. As a result of the write operation 200, the dependency cycle that existed in the intermediate write graph 208 is now broken. That is, a single object A can now be flushed to install all operations 190-196 in the node, including the write operation 194 that originally affected the data object O. In terms of the write graph, the write operation renders the data object O "unexposed" in the collapsed node of the write graph 212. An "unexposed" object of a write graph node is one that has a write operation for it in a succeeding node and no read operations following the current node that also do not follow the succeeding write. As a result, an unexposed object does not need to be flushed in order to install the operations in the preceding node that wrote that object as no succeeding operation needs the value that it wrote. Conversely, an "exposed" object in a node is an object that needs to be flushed to install the operations in the node that wrote that object. In the FIG. 15 example, the application object A is "exposed" in the collapsed node. Although an unexposed object does not need to be flushed, it is still preferably flushed to the stable database after the exposed object is flushed. In this manner, recovery is ensured while providing effective cache management. FIG. 16 shows the corresponding log records for the sequence of operations 190-200 from FIG. 15. As a result of the log optimization technique, the log record for the write operation 194 does not contain the value written to the data object O (i.e., O2). Instead, the log record for write operation 194 contains only the data object identifier O, the data object O's state ID 2, the application object identifier A, its state ID 3, and the write operation W that resulted in data object state O2. FIG. 16 also shows another technique for reducing the number of objects in a multi-object combined node. The cache manager may not wish to wait for a subsequent write operation of one of the objects in the write graph node, such as write operation 200, because such operations cannot be foreseen and are not guaranteed to occur. Accordingly, the cache manager can impose its own write of an object in the multi-object node. The cache manager performs a "blind identity" write which writes the value of the object onto the stable log. FIG. 16 shows a blind write operation 216 which writes the values of the data object O at state 3, i.e., O3, to the log record. The blind write creates an after-image of the data object O on the log. That is, the blind write in this case is an identity write because the identical value of data object O, which is the same at both states 2 and 3, is written to the log. The state ID is stepped from 2 to 3 to maintain the convention introduced earlier in this disclosure. Once the value O3 is posted to stable log and all nodes that precede the node with operations 190-196 have been installed, i.e. the node with R198, the cache manager is free to flush the application object A, thereby installing operations 190-196. If the system crashes after object A is flushed and application state A3 is irretrievably lost, subsequent operations involving the data object O at state 3, can be replayed using the values O3 on the stable log, rather than the values from the output buffers of a regenerated application state A3. Blind writes come at a cost of writing larger amounts of data to the log, but this cost is minimal in comparison to the advantages gained by the write optimization techniques in which a high percentage of writes do not result in posting entire object values to the log. Although data object O does not need to be flushed to the stable database because it is written to the stable log, it is still preferably flushed to the stable database, and more preferably, it is flushed to the stable database after the exposed object A is flushed. This subsequent flush is used to manage the cache. That is, the object is flushed when it is desired to drop the object value from the cache. This allows the object to be stored somewhere other than the cache where it can be retrieved if it is needed to be read or updated again in the future. Therefore, in a database computer system having a non-volatile memory, a volatile main memory, and an application object which executes from the main memory, wherein the non-volatile memory includes a stable log, a computer-implemented method in accordance with the present invention comprises the following steps: executing the application object to perform operations which read data from, and write data to, a data object; posting to the stable log a log record for each operation involving the reading or writing of data, the log record containing a reference to either the application object or the data object to identify that referenced object as a source for the data that is read from or written to; establishing flush order dependencies between the application object and the data object, wherein some of the flush order dependencies become cyclic indicating a condition in which the application object should be flushed not later than the data object and the data object should be flushed not later than the application object; detecting a dependency cycle; and following detection of the dependency cycle, writing one of the application object or the data object to the stable log to break the dependency cycle to enable the application and data objects to be flushed sequentially according to an ordered flushing sequence. Preferably, the writing step comprises writing the data object to the stable log. More preferably, the method comprises the step of flushing the application object to the non-volatile memory after the data object is written to the stable log. More preferably, the method comprises the step of flushing the data object to the non-volatile memory after the application object has been flushed to the non-volatile memory. Alternatively, one can write the application object to the stable log, and then flush the data object first to non-volatile memory and then flush the application object to the non-volatile memory. The cache manager-imposed blind write has the same affect of removing an object from the collapsed node in the write graph as a normal write operation. But such a write is under the control of the cache manager, and hence the cache manager can use such writes to help it manage the cache. FIG. 17 illustrates the effect of a blind write on the combined node in the write graph 210 of FIG. 15. In a blind write, the cache manager posts the current value of the data object O to the stable log. This is represented in a write graph 211 as a new node containing the object O and a blind write operation (i.e., W216). Since the value of O is written to the log, the data object O does not need to be flushed concurrently with the flushing of application object A, and hence the O→A dependency is removed. The blind write thereby breaks the dependency cycle. In write graph terms, the data object O is no longer "exposed" in the combined node and is withdrawn from that node. The cache manager no longer needs to flush object O as part of the installation of the operations 190-196 in the combined node because it does not matter what object O's value is. The cache manager need only flush the exposed application object A to install all operations in the node, including those that had written data object O, even though data object O is not flushed. Preferably, however, data object O is flushed to the stable database after the application object A in order to provide effective cache management. It | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||