Transaction log management in a disconnectable computer and network

• US 6,192,365 B1
• Filed: 09/03/1996
• Issued: 02/20/2001
• Est. Priority Date: 07/20/1995
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Draper, Stephen P. W., Collins, Brian J., Falls, Patrick T.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/700,490
• Time in Patent Office: 1,631 Days
• Field of Search: 707/2, 707/10, 707/100, 707/101, 707/200-204
• US Class Current: 707/648
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and apparatus are disclosed for managing a transaction log which contains updates representing operations performed on a database replica in a network of disconnectable computers. The invention provides for compression of the log by the identification and removal of redundant updates. Log compression removes apparent inconsistencies between operations performed on disconnected computers, reduces storage requirements on each computer, and speeds up transaction synchronization when the computers are reconnected. The invention also provides for restoration of prior versions of database objects using the log.

Claims

1. A method for managing a transaction log, the log representing a sequence of transactions in a network of connectable computers, each transaction containing at least one update targeting a target database object in a distributed hierarchical target database that contains convergently consistent replicas residing on separate computers in the network, the method comprising the steps of:

identifying an incompressible sequence of updates in the transaction log;

ruling out those updates in the incompressible sequence as candidates for removal from the transaction log;

identifying at least one redundant update in the transaction log which is not in the incompressible sequence; and

removing the redundant update from the transaction log.

2. The method of claim 1, comprising the step of identifying a transaction boundary within the transaction log.

3. The method of claim 2, comprising the steps of determining the most recent successfully merged transaction that updates a selected object, and then removing an update of the object that antedates the transaction.

4. The method of claim 1, wherein the transaction log resides on a first computer and the method comprises the steps of identifying an update in the transaction log that specifies an update location on a computer other than the first computer, and then removing that update.

5. The method of claim 1, wherein the identifying and removing steps are preceded by the step of creating a hierarchical log database representing at least a specified portion of the transaction log, the log database containing an object corresponding to an update in the specified portion and also containing an object corresponding to a transaction in the specified portion of the transaction log.

6. The method of claim 5, wherein the specified portion of the transaction log is the entire existing transaction log.

7. The method of claim 5, wherein the specified portion of the transaction log includes recent transactions and the remainder of the existing transaction log is represented by a compressed linearly accessed log.

8. The method of claim 5, wherein the method further comprises appending a transaction to the transaction log by inserting a transaction object into the log database.

9. The method of claim 8, wherein the appending step comprises inserting an update object into the log database.

10. The method of claim 8, wherein the appending step comprises accessing an unreplicated attribute in the log database to identify an earlier update, if any, which references an object in the target database that is also referenced by an update in the appended transaction.

11. The method of claim 8, wherein the appending step comprises accessing an update history structure in the log database to identify an earlier update, if any, which references an object in the target database that is also referenced by an update in the appended transaction, the update history structure associating each target database object with the log database objects, if any, that correspond to updates referencing the given target database object.

12. The method of claim 5, wherein the method further comprises adding a synchronization checkpoint to the transaction log by inserting a synchronization checkpoint object into the log database.

13. The method of claim 5, wherein the method further comprises removing a synchronization checkpoint from the transaction log by removing a synchronization checkpoint object from the log database and then compressing a previously incompressible region of the transaction log.

14. The method of claim 5, wherein each completed transaction in the transaction log has a corresponding transaction sequence number, the transaction sequence numbers are consecutive and monotonic for all completed transactions, and the method further comprises specifying a range of one or more transaction sequence numbers and then retrieving transactions from the transaction log in order according to their respective transaction sequence numbers.

15. A method for managing a transaction log, the log representing a sequence of transactions in a network of connectable computers, each transaction containing at least one update targeting a target database object in a distributed target database that contains replicas residing on separate computers in the network, the method comprising the steps of:

identifying an incompressible sequence of updates in the transaction log;

identifying for consolidation at least two target database updates in the log, the identified updates being not all adjacent one another, and the identified updates including at least one candidate redundant update which is not in the incompressible sequence;

repositioning for consolidation at least one of the identified updates so the repositioned update is adjacent to at least one other update which was identified for consolidation; and

consolidating at least two target database updates by replacing the repositioned update and an adjacent update by a single equivalent update, thereby removing the candidate redundant update from the transaction log.

16. The method of claim 15, wherein the network includes a server computer and a client computer, a server replica of the target database resides on the server computer, and a client replica of the target database resides on the client computer.

17. The method of claim 15, further comprising creating a hierarchical log database representing at least a specified portion of the transaction log, the log database containing an object corresponding to an update in the specified portion and also containing an object corresponding to a transaction in the specified portion of the transaction log.

18. The method of claim 17, wherein the specified portion of the transaction log is the entire existing transaction log.

19. The method of claim 17, wherein the specified portion of the transaction log includes recent transactions and the remainder of the existing transaction log is compressed.

20. The method of claim 17, wherein the method farther comprises appending a transaction to the transaction log by inserting a transaction object into the log database.

21. The method of claim 20, wherein the appending step comprises inserting an update object into the log database.

22. The method of claim 20, wherein the appending step comprises accessing an unreplicated attribute in the log database to identify an earlier update, if any, which references an object in the target database that is also referenced by an update in the appended transaction.

23. The method of claim 20, wherein the appending step comprises accessing an update history structure in the log database to identify an earlier update, if any, which references an object in the target database that is also referenced by an update in the appended transaction, the update history structure associating each target database object with the log database objects, if any, that correspond to updates referencing the given target database object.

24. The method of claim 17, wherein the method further comprises adding a synchronization checkpoint to the transaction log by inserting a synchronization checkpoint object into the log database.

25. The method of claim 17, wherein the method further comprises removing a synchronization checkpoint from the transaction log by removing a synchronization checkpoint object from the log database and then compressing a previously incompressible region of the transaction log.

26. A computer-readable storage medium having a configuration that represents data and instructions which cause a disconnectable computer to perform method steps for managing a transaction log, the log representing a sequence of transactions in a network of connectable computers, each transaction containing at least one update targeting a target database object in a distributed hierarchical target database that contains replicas residing on separate computers in the network, the method comprising the steps of:

identifying an incompressible sequence of updates in the transaction log;

creating a log database representing at least a specified portion of the transaction log, the log database containing a log database object corresponding to an update in the specified portion and also containing a log database object corresponding to a transaction in the specified portion of the transaction log; and

creating an update history structure which associates each target database object with the log database objects, if any, that correspond to updates referencing the given target database object.

27. The storage medium of claim 26, wherein the method further comprises the steps of of locating a transaction checkpoint, accessing the update history structure, and then constructing a prior version of a target database object.

28. A system for managing a transaction log, comprising:

a transaction log representing a sequence of transactions in a network of connectable computers, each transaction containing at least one update targeting a target database object in a distributed target database that contains convergently consistent replicas residing on separate computers in the network,

a computer means for storing the log; and

a computer means for executing programmed instructions for identifying at least one redundant update in the transaction log and removing the redundant update from the transaction log, comprising a means for identifying an incompressible sequence of updates in the transaction log.

29. The system of claim 28, wherein the system comprises a means for repositioning an update in the sequence of updates in the transaction log and for replacing the repositioned update and an adjacent update by a single equivalent update.

30. The system of claim 28, further comprising a means for creating a hierarchical log database representing at least a specified portion of the transaction log, the log database containing an object corresponding to an update in the specified portion and also containing an object corresponding to a transaction in the specified portion of the transaction log.

31. The system of claim 30, wherein the specified portion of the transaction log includes recent transactions and the remainder of the existing transaction log is represented by a compressed linearly accessed log.

32. The system of claim 30, further comprising a means for extending the transaction log by inserting an object into the log database.

33. The system of claim 30, further comprising a means for accessing an update history structure in the log database to identify an earlier update, if any, which references an object in the target database that is also referenced by an update in the appended transaction.

34. The system of claim 33, further comprising a means for constructing a prior version of a target database object.

35. The system of claim 30, further comprising a means for removing a synchronization checkpoint from the transaction log and a means for compressing a previously incompressible region of the transaction log.

36. The system of claim 30, wherein each completed transaction in the transaction log has a corresponding transaction sequence number, and the transaction sequence numbers are consecutive and monotonic for all completed transactions.