Merge, commit recovery protocol for real-time database management systems5497487Abstract A computer database method using data organized data into atomic data sets and transactions separated into a plurality of statements called projections which operate on only one said atomic data set. Statements such as read commands, write commands, assignment commands, transaction delimiting commands, and projection delimiting commands are executed, and a depends on graph is created during execution of the statements. Projection recovery data is stored during operation. When a statement requests commit the depends on graph is analyzed to determine if the projection is related to another projection in the transaction. The projection is committed if it is not related to another projection and delayed if related to another projection. Likewise, the system determines related projections and aborts them together if a transaction error occurs. The method can recover to a consistent database state after projection abortion. Claims What is claimed is: Description CROSS REFERENCE TO RELATED PATENT APPLICATIONS
______________________________________
S.sub.0 : v.sub.1 := r(x)
/*S.sub.0 defines v.sub.1 using data item x */
S.sub.1 : v.sub.2 := r(y)
/*S.sub.1 defines v.sub.2 using data item y */
S.sub.2 : v.sub.3 := f(v.sub.1)
/*S.sub.2 defines v.sub.3 using v.sub.1 */
S.sub.3 : v.sub.4 := f(v.sub.2)
/*S.sub.3 defines v.sub.4 using v.sub.2 */
S.sub.4 : v.sub.5 := f(v.sub.4)
/*S.sub.4 defines v.sub.5 using v.sub.4 */
S.sub.5 : w(y, v.sub.4)
/*S.sub.5 redefines data item y using v.sub.4
______________________________________
*/
S.sub.2 directly depends on S.sub.0 because S.sub.2 uses v.sub.1 from S.sub.0 to define v.sub.3. S.sub.3 directly depends on S.sub.1 because S.sub.3 uses v.sub.2 from S.sub.1 to define v.sub.4. S.sub.4 directly depends on S.sub.3 because S.sub.4 uses v.sub.4 from S.sub.3 to define v.sub.5, and S.sub.4 depends on S.sub.1 because S.sub.4 uses v.sub.4 from S.sub.3, which was defined using v.sub.2 defined in S.sub.1. If x and y belong to distinct atomic data sets A and B respectively then S.sub.0 is in a projection .pi..sub.A and S.sub.1, S.sub.5 are in a projection .pi..sub.B. Projections also exhibit dependency. If one statement in a first projection is dependent on data from a second projection then the first projection depends on the second projection. Projections are related if a dependency exists among two or more of them. A depends-on graph can be constructed during transaction run time using the projections as nodes and the dependency relationships between projections as edges. When a projection begins, a node for that projection is inserted in the depends on graph. When the projection executes a read statement a definition lock is placed on the result memory variable of the read statement. Execution of an assignment statement causes no change to the depends on graph; however, its operation must be considered because assignment statements can have transitive effects. A write statement causes a use lock to be placed on the result memory variable of the statement. Placing a definition lock on a variable causes the system to generate an edge between the projection's node and other projection's nodes which hold either a use lock or a definition lock on the variable. Placement of a use lock on a variable causes the system to generate an edge between the projection placing the use lock and any other projections which hold definition locks on that variable. When a projection requests commit, the system looks at the generated depends on graph. If any edges exist between the projection committing and another projection then the projections are related. Commit for the projection requesting commit must delay until all related projections have requested commit to ensure system consistency. Referring now to FIG. 1 there is shown pseudocode for a transaction in which one projection depends on another projection. In this figure, "Tbegin" indicates the start of the transaction and "Tend" indicates the end of the transaction projection. Hereinafter, "Tbegin" and "Tend" are referred to collectively as transaction delimiting commands. Projection A is referred to using the symbol .pi..sub.A, and projection B is referred to by .pi..sub.B. The beginning of a projection is indicated by sb(X) where X is the particular projection. Likewise, the commit time for a projection is indicated by sc(X) where X is the particular projection. Collectively, the commands sb(X) and sc(X) are known as projection delimiting commands. The projection delimiting statements, sb(X) and sc(X), are coded by an applications programmer or applications programming system. The programmer places the statement sc(X) to assure that preceding data is properly updated but also available to other concurrent transactions at an early time. Reading a variable from a database is indicated by the function r(x) where x is the database variable being read. Writing a particular variable from a database is indicated by the command w(x,y) where x is the variable being written to and y is the memory variable being written to the database. Each statement of the transaction is indicated with the notation S.sub.x where x is the number of the statement. In this example, database variables are referred to by the letters a, b, c, d, and e. Memory variables are referred to by v.sub.x where x is a number. Symbolic comments are delimited by "/*" and "*/". The transaction preserves a record of committed projections, and the current program counter position in stable storage. This information allows the transaction to begin after the last completed projection on an error. As the system executes the statements contained in FIG. 1, a depends on graph is created as shown in FIG. 2a-2c. In the transaction of FIG. 1, ADS A contains database variables a, b, and c, and ADS B contains database variables d and e. At S.sub.1 projection A, .pi..sub.A, is started, and a node 10 is created for .pi..sub.A in the depends on graph shown in FIG. 2a. S.sub.2 reads a into memory variable v.sub.1. This has no affect on the depends on graph because a is a variable from .pi..sub.A and v.sub.1 has not been used or defined by another projection. Likewise, S.sub.3 -S.sub.5 have no affect on the depends on graph because they have not been used or defined by another projection. S.sub.6 starts projection .pi..sub.B, and a new node 12 is inserted in the depends on graph as shown in FIG. 2b. S.sub.7 reads d into memory variable v.sub.4. This action has no affect on the depends on graph because v.sub.4 has not been defined or used by another projection. S.sub.8 causes an edge 14 to be inserted into the depends on graph between node .pi..sub.A 10 and node .pi..sub.B 12 because v.sub.4 is reassigned using v.sub.3 a variable which has been used in .pi..sub.A. At S.sub.9 projection .pi..sub.A requests commit. The system examines the depends on graph shown in FIG. 2c to determine if any other projections are related to .pi..sub.A. The systems finds that .pi..sub.B is related to .pi..sub.A because edge 14 exists between node .pi..sub.A 10 and node .pi..sub.B 12; therefore, .pi..sub.A commit must be merged with .pi..sub.B commit. S.sub.10 executes and has no affect on the graph. In S.sub.11, projection .pi..sub.B requests commit, and the system determines that .pi..sub.B is dependent on .pi..sub.A and on no other projections. .pi..sub.A is allowed to commit then .pi..sub.B is allowed to commit. After a transaction commits, its node and related edges are removed from the depends on graph. Referring now to FIG. 3, there is shown a diagram of a typical database for use with the merge-segment commit protocol of this invention. The database shown is the database of FIG. 1 after the execution of S.sub.7. Two atomic data sets are shown as ADS A 30 and ADS B 32. These are representations of the stable data storage area that will not be affected by a transaction or system failure. While a projection is being executed, each subject ADS has two indexes, a main index 34 and a copy index 36. These two indexes provide a reference table give the system the location of each specific data item in the ADS. At the start of a projection the system allocates copy index area 34 and copies index information from main index 34 to copy index 36. The location of the main index is maintained by the system in stable storage. Both indexes, therefore, contain the same index information. While the projection is active, a write command to the ADS causes the system to write data items to a clear area of the ADS, and the system changes copy index 36 to refer to the newly written data. This is shown by example in FIG. 3 wherein a new value 38 has been written to data item c in ADS A 30. Copy index 36 for ADS A 30 points to the new value for data item c 38, and main index 34 continues to reference the previously committed value for c 40. Upon commit the system changes an index pointer 42 to refer to copy index 36 as the main index. Space formerly taken by main index 34 can be released. ADS B 32 shows a database wherein the data items have not been changed. In an alternative embodiment, index information could be copied from the copy index to the main index; however, the use of a pointer is more efficient in most applications. This database structure is known in the art, but is included herein for reference purposes. A possible actual implementation for the database system is set forth in FIG. 4 and FIG. 5. Upon start of a transaction, the system allocates a recovery block table as shown in FIG. 4. When a projection begins as in S.sub.1 of FIG. 1 a recovery block 40 is created with the program counter for the projection, .pi..sub.A (pc) 42; the location of the projection's main index 44; the location of active variables at the start of the projection 46; and other projections which are active at the projection start 48. When a transaction is first started the system also allocates a variable lock table for that transaction as in FIG. 5. Lock tables are well known in the database art to avoid referencing data that is currently in use. For example, if one transaction reads data that a first transaction is in the process of updating, the data read is most likely going to be in error until the first transaction has completed its update. Lock tables provide a means for keeping data from being read while it is being updated. In the inventive database system, the lock table for a particular transaction is preserved only for the duration of that transaction. Locks stored in the lock table identify the projection or transaction entity obtaining the lock, the type of lock being obtained, and point to related locks, if any. When a lock is placed on a variable, the lock contains at least one pointer referring to previous locks placed on that variable and related locks placed on other variables. Lock tables are typically implemented in computer software by flags and a linked list of pointers, although other well known methods can be used. In the variable lock table of this invention, three types of locks can be placed on a variable. A use lock is placed on a variable when the variable is assigned. The symbolic syntax used herein for a use lock is U.sub.L (X) where X is the transaction or projection acquiring the use lock. A definition lock is placed on a variable when that variable is defined. The syntax for a definition lock is D.sub.L (X) where X is the projection acquiring the definition lock. A third type of lock, the inferred definition lock, is to allow the system to find possible definition conflicts without conducting a complete search of the lock table. For example, if a variable I is defined by a function of a variable J which was read from ADS X, the inferred definition lock should refer to ADS X. An inferred definition lock is indicated by the symbol inf D.sub.L (last(v)) where lastly) is used to indicate the identifier for the last projection having a lock on variable v. To evaluate last(v) the system references the lock table for the specified variable v, and determines which projection last locked the variable. If locks were placed on the variable by multiple projections during the last operation on that variable, then last(v) will be result in multiple references. Inferred definition locks are created during assignment statements. When an assignment statement executes, the transaction acquires use locks, U.sub.L (T), on the arguments of the assignment. The last projection used by the result variable and the last projections used by the argument variables acquire inferred definition locks, inf D.sub.L (last(v)), on the result variable. Links are added from the use locks to the inferred definition locks set by the system on the arguments. These links allow the system to trace an assignment back to previous variables to determine if a dependency is caused by transitivity. A read statement, v.sub.1 :=r(a), such as S.sub.2 in FIG. 1 causes the following lock table actions. The system inserts v.sub.1 's identifier in the lock table if v.sub.1 is not already in the lock table. Variable v.sub.1 has a definition lock, D.sub.L (.pi..sub.A) placed on it from projection .pi..sub.A because data is being read from that projection. An assignment statement, v.sub.3 :=f.sub.i (v.sub.1,v.sub.2) in S.sub.4, causes the system to insert v.sub.3 's identifier in the lock table if it is not already there. The transaction, T, acquires use locks, U.sub.L (T), on each of the arguments of the assignment, v.sub.1 and v.sub.2. The system attempts to establish inferred definition locks, inf D.sub.L (last(v.sub.1)), inf D.sub.L (last(v.sub.2)), and inf D.sub.L (last(v.sub.3)). Evaluation of the last(v.sub.1) function results in an inferred definition lock, inf D.sub.L (.pi..sub.A), being placed on v.sub.3. Because evaluation of last(v.sub.2) also gives .pi..sub.A, the same projection as the first argument, another inf D.sub.L (.pi..sub.A) is not placed on v.sub.3. When evaluated last(v.sub.3) is a null because v.sub.3 is a newly defined variable with no prior locks. An inferred definition lock does not need to be placed on the result variable of the assignment if the result variable is the same as one of the arguments, the result variable is being initially defined in the assignment, or the inferred definition lock would merely repeat a previous lock. After establishing locks on the affected variables, the system adds links to the variable lock table from the inferred definition locks back to the source use locks. One link will be from inf D.sub.L (.pi..sub.A) on v.sub.3 back to U.sub.L (T) on v.sub.1. Another link will be established from inf D.sub.L (.pi..sub.A) on v.sub.3 back to U.sub.L (T) on v.sub.2. A write statement, w(c,v.sub.3), such as S.sub.5 in FIG. 1 causes the system to insert v.sub.3 's identifier in the lock table if it is not already there. The system places a use lock, U.sub.L (.pi..sub.A), on v.sub.3 in the lock table. A projection .pi.'s subbegin statement, sb(.pi.), such as S.sub.1 in FIG. 1 causes the system to build a copy index for projection .pi. by copying index information from the main index to another location. See FIG. 2. The system also creates a recovery block for projection .pi.. The recovery block contains the program counter for the projection, the location of the projection's copy index, active variables at the start of the projection, other projections which are active at the projection .pi.'s start, and variables defined in the course of the projection. A read statement for a projection .pi. causes the system to append the variable to the defined variables section of projection .pi.'s recovery block. The defined variables section of the recovery block provides additional cross referencing between the recovery block and the lock table to speed the system. Write statements for a variable also append the variable to projection .pi.'s recovery block, if not already present there. Assignment statements do not have any affect on the recovery block because assignments do not affect the static store. A projection .pi.'s subcommit statement, sc(.pi.), such as S.sub.9 in FIG. 1 causes the system to determine if projection .pi. can commit without corrupting the database. Projections commit in the order that their subcommit commands arrive at the system scheduler. Projection .pi. must delay commit if projection .pi. depends on data from another projection or if another projection in the transaction is dependent on projection .pi.. In order to determine if projection .pi. can commit, the system examines the last lock on each variable defined by the committing projection. If the last lock was placed by another projection then the projection cannot commit until the locking projection requests commit. To preserve the commit order, the scheduler records the order of commit requests. When the scheduler receives a commit request from the dependent projection, the system analyzes the dependencies for the dependent projection. If the system determines that the dependent projection can commit but for the original projection then the original projection is allowed to commit. If the latest lock was not placed by another projection, the system examines all links to the current lock to determine if related locks are placed by another projection. The system then examines earlier locks on the variable and traces links back to all related variables. If no locks are held on any of the defined variables by other projections then the system will allow the current projection to commit. The system delays projection commit when the projection is dependent upon another projection or when another projection is dependent upon it. The first projection is allowed to commit immediately before any sibling projection. On commit, locks held by the committing projection are released, the copy index is made the main index, and the recovery block can be removed. A commit notice for the projection is placed in the transaction's commit list. When a projection is aborted because of a transaction error, the aborted transaction must first be examined to determine if any other projections depend on the aborted projection directly or indirectly. All currently dependent projections must be aborted with the originally aborted projection to insure database integrity. The system determines dependencies by examining the inferred definition locks held on the variables defined in the current projection. If a variable has an inferred definition lock placed on it that refers back to another projection or use-definition links which trace back to another projection then the projection is dependent on the other projection. When only one projection is aborted, that projection can be restarted without loss of serializability because no other projections depend on that projection. To restart the projection the program counter is reset to the value it contained at the start of the projection, and the main index is copied to the copy index. The projection then executes as initially. To restart projections which have been merged, both projections recovery blocks are used. The program counters, active variables, and active projections during the current transaction are retrieved. Recovery begins at the recovered program counter address of the earliest projection using the original data values upon the start of the projection from the original main index. New copy indexes are created for all projections involved. Execution follows as in the initial code execution. When the transaction ends, the system can commit all outstanding projections in the order received. Locks held by the transaction are released. The system deallocates the lock table and recovery block table. Operation of the recovery block table of FIG. 4 and the variable lock table of FIG. 5 shall now be explained with reference to the example transaction of FIG. 1. On receipt of the Tbegin statement, stable storage space is allocated for the variable lock table and the recovery block table. The subbegin command of S.sub.1 causes insertion of projection A's program counter in the recovery block table. The main index of ADS A is copied to the copy index. All currently active variables and projections are inserted into the recovery block table. The defined variables section of the recovery block table will initially be empty. In S.sub.2, execution of a read command from database variable a to memory variable v.sub.1 causes the system to record v1 in the recovery block table and then in the variable lock table apply a definition lock to v.sub.1 held by .pi..sub.A. Likewise in S.sub.3, v.sub.2 is recorded and a definition lock is applied to v.sub.2 which is held by .pi..sub.A. An assignment command, v.sub.3 :=f.sub.i (v.sub.1,v.sub.2) is executed in S.sub.4, assigning the result of f(v.sub.1, v.sub.2) to v.sub.3. The system inserts v.sub.3 's identifier in the lock table and the recovery block table. The transaction, T, acquires use locks, U.sub.L (T), in the lock table on each of the arguments of the assignment, v.sub.1 and v.sub.2. The system attempts to establish inferred definition locks, inf D.sub.L (last(v.sub.1)), inf D.sub.L (last(v.sub.2)), and inf D.sub.L (last(v.sub.3)). Evaluation of the last(v.sub.1) function results in an inferred definition lock, inf D.sub.L (.pi..sub.A), being placed on v.sub.3. Because evaluation of last(v.sub.2) also gives .pi..sub.A, the same projection as the first argument, another inf D.sub.L (.pi..sub.A) is not placed on v.sub.3. When evaluated last(v.sub.3) is a null because v.sub.3 is a newly defined variable not present in the recovery block table. An inferred definition lock does not need to be placed on the result variable of the assignment if the result variable is the same as one of the arguments, the result variable is being initially defined in the assignment, or the inferred definition lock would merely repeat a previous lock. After establishing locks on the affected variables, the system adds links to the variable lock table from the inferred definition locks back to the source use locks. These links are identified in FIG. 5 by the arrows pointing from the use locks U.sub.L (T) on v.sub.1 and v.sub.2 to inf D.sub.L (.pi..sub.A) on v.sub.3. S.sub.5 executes a write command to write memory variable v.sub.3 to database variable c. On receipt of this command, the system puts the location of v.sub.3 in the recovery lock table because the v.sub.3 location is not currently there. A use lock, U.sub.L (.pi..sub.A), is inserted for v.sub.3 in the lock table. Projection B is started by the subbegin command, sb(B), of S.sub.6. As in the S.sub.1 subbegin command the projection's program counter is inserted in the recovery block table, and the main index of ADS B is copied to the copy index. Currently active variables, v.sub.1, v.sub.2 and v.sub.3, and projection, .pi..sub.A, are inserted into the recovery block table. Initially, the defined variables section of the recovery block table is empty. S.sub.7 executes a read command reading d into v.sub.4. The location of v.sub.4 is written to the defined variables section of the recovery block table and to the variable lock table. A definition lock, D.sub.L (.pi..sub.B), is placed on v.sub.4 because v.sub.4 is defined by .pi..sub.B. S.sub.8 assigns the result of a function of v.sub.4 and v.sub.3 to v.sub.4. This has no effect on the recovery block table because v.sub.4 is already identified. In the lock table use locks, U.sub.L (T), are placed on the arguments of the function, v.sub.3 and v.sub.4. Inferred definition locks, inf D.sub.L (.pi..sub.A) and inf D.sub.L (.pi..sub.B), are placed on v.sub.4 after evaluation of last (v.sub.3) and last (v.sub.4). A pointer is created between the use lock on v.sub.3 and the inferred definition lock, inf D.sub.L (.pi..sub.A), on v.sub.4. A pointer is also created between the use lock on v.sub.4 and the inferred definition lock, inf D.sub.L (.pi..sub.B), on v.sub.4. The embodiment above uses a hierarchical lock table which allows the order of locking on each variable v to be determined. It is envisioned, however, that a non-hierarchical lock table would be effective for the purposes of this invention. The hierarchical lock table is preferred because it offers optimization in locating conflicts between projection. A subcommit command for projection A is issued in S.sub.9. The system must evaluate the lock table to determine if projection A is related to any other projections. To do this, the system must search the lock table for all variables defined by projection A. Starting with v.sub.1, the system analyzes the last lock on v.sub.1. Since this lock is a use lock, U.sub.L (T), held by the transaction, no conflicts are created. The system then follows the pointer from the use lock to the inferred definition lock, inf D.sub.L (.pi..sub.A), held by projection A on v.sub.3. No conflicts are created by this lock because it is held by .pi..sub.A, the projection that is currently attempting to commit. U.sub.L (.pi..sub.A) on v.sub.3 creates no conflicts for the same reason. U.sub.L (T) on v.sub.3 only locks against other transactions, and, therefore, does not create any conflicts. The system follows the pointer from U.sub.L (T) to the inferred definition lock, inf D.sub.L (.pi..sub.A). The system next encounters the inferred definition lock, inf D.sub.L (.pi..sub.B), held by projection B on v.sub.4. This indicates a use-definition conflict between projection A and projection B. Accordingly, commit for projection A must delay until projection B is ready to commit. If no conflict had been encountered, the system would have continued to analyze the backward path through the locks from v.sub.1 to determine if any conflicts exist. After analyzing all paths from v.sub.1, the system would proceed to analyze v.sub.2 and v.sub.3. Because commit for .pi..sub.A could not be accomplished, the projection's identifier is sent to the scheduler to indicate that the projection is ready to commit once .pi..sub.B issues a subcommit statement. Optionally, the system can continue to analyze the lock table to determine if the projection that failed commit is dependent on any other projections. This will allow the system to restart the failed commit only when all related projections are ready to commit. If the system does not continue to analyze the lock table, the system can determine whether the projection failing commit is ready to commit prior to commit of the known related projection and any subsequent projections. Statement S.sub.10 issues a write command to write v.sub.4 to e. Since e is a projection B database variable, a use lock, U.sub.L (.pi..sub.B), is placed on v.sub.4. In S.sub.11 subcommit command, sc(B) is issued for projection B. The system must determine if projection B is related to any other projections before projection B is allowed to commit. The system notes that projection A is related to projection B from the result of the sc(A) command issued in S.sub.6. The system also determines that no other projections are active; therefore, projection A is allowed to commit because it requested commit before projection B. On commit, the ADS A copy index becomes the new ADS A main index, all locks held by projection A are released, and the projection A recovery block table entry is deallocated. Projection A's identifier is written to the transaction's commit list. Likewise, when projection B commits the ADS B copy index becomes the new ADS B main index, all locks held are released, the recovery block table entry is deallocated, and projection B's identifier is placed on the transaction's commit list. When the system receives the transaction end command, Tend, it releases all locks, deallocates the lock table, and deallocates the recovery block table. What has thus been described is a merge, commit, recovery protocol for real-time database management systems. The protocol allows greater access to data by maintaining locking over atomic data sets and projections rather than by transactions as in the prior art. Obviously many modifications and variations of the present invention may become apparent in light of the above teachings. In light of the above, it is therefore understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described.
|
Same subclass Same class Consider this |
||||||||||