System and method for restoring a distributed checkpointed database

• US 5,845,292 A
• Filed: 12/16/1996
• Issued: 12/01/1998
• Est. Priority Date: 12/16/1996
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Parker, James Allen, Rastogi, Rajeev, Bohannon, Philip L., Silberschatz, Abraham
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/766,096
• Time in Patent Office: 715 Days
• Field of Search: 707/8, 707/201, 707/202, 707/200, 707/182.13, 707/182.14, 707/182.17, 707/182.18, 395/182.13, 395/182.14, 395/182.17, 395/182.18
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

For use with a central database associated with a server of a network, the central database having distributed counterparts stored in volatile memories of clients of the network to allow operations to be performed locally thereon, the central database further having multiple checkpoints and a stable log stored in the server for tracking operations on the central database to allow corresponding operations to be made to the multiple checkpoints, the stable log having tails stored in the volatile memories to track operations on corresponding ones of the distributed counterparts, the distributed counterparts to corruption, a system for, and method of, restoring a distributed counterpart stored in one of the volatile memories. The system includes: (1) a checkpoint determination controller that determines which of the multiple checkpoints is a most recently completed checkpoint and copies the most recently completed checkpoint to the one of the volatile memories to serve as an unrevised database for reconstructing the distributed counterpart and (2) an operation application controller that retrieves selected ones of the operations from the stable log and a tail corresponding to the distributed counterpart and applies the operations to the unrevised database thereby to restore the distributed counterpart.

Claims

1. For use with a central database associated with a server of a network, said central database for operation with at least one distributed counterpart stored in a volatile memory of at least one respective client of said network to allow operations to be performed locally thereon, said central database further having multiple checkpoints and a stable log stored in said server for tracking operations on said central database to allow corresponding operations to be made to said multiple checkpoints, said stable log having a tail stored in said volatile memory to track operations on said distributed counterpart, said distributed counterpart subject to corruption, a system for restoring said distributed counterpart stored in said volatile memory, comprising:

a checkpoint determination controller that determines which of said multiple checkpoints is a most recently completed checkpoint and copies said most recently completed checkpoint to said volatile memory to serve as an unrevised database for reconstructing said distributed counterpart; and

an operation application controller that retrieves selected ones of said operations from said stable log and said tail corresponding to said distributed counterpart and applies said operations to said unrevised database thereby to restore said distributed counterpart.

2. The system as recited in claim 1 wherein said applied operations include log records at an operation level, and said operation application controller, using memory locks while restoring said distributed counterpart, releases ones of said memory locks as a function of applying ones of said log records.

3. The system as recited in claim 1 wherein log records, having been communicated by said client, are received at said server.

4. The system as recited in claim 1 wherein said client requests a region lock from said server.

5. The system as recited in claim 1 wherein said server grants a region lock to said client.

6. The system as recited in claim 1 wherein said server communicates validity information to said client concerning said distributed counterparts.

7. The system as recited in claim 1 wherein said multiple checkpoints are checkpointed alternately.

8. The system as recited in claim 1 wherein said central database and said multiple checkpoints each contain an active transaction table, said checkpoint determination controller copying said active transaction table from said most recently completed checkpoint to said volatile memory.

9. The system as recited in claim 1 wherein said stable log and said tail cooperate to form a global log, said operation application controller applying said operations as a function of a temporal pointer associated with said global log.

10. The system as recited in claim 1 wherein said operation application controller retrieves operations from said stable log and said tail corresponding to said distributed counterpart that were not made to said most recently completed checkpoint.

11. The system as recited in claim 1 wherein said multiple checkpoints and said stable log are stored on a nonvolatile storage device.

12. The system as recited in claim 1 wherein said central database further has an undo log for tracking operations to be undone in said distributed counterpart, said operation application controller retrieving said selected ones of said operations as a function of a content of said undo log.

13. For use with a central database associated with a server of a network, said central database for operation with at least one distributed counterpart stored in a volatile memory of at least one respective client of said network to allow operations to be performed locally thereon, said central database further having multiple checkpoints and a stable log stored in said server for tracking operations on said central database to allow corresponding operations to be made to said multiple checkpoints, said stable log having a tail stored in said volatile memory to track operations on said distributed counterpart, said distributed counterpart subject to corruption, a method of restoring said distributed counterpart stored in said volatile memory comprising the steps of:

determining which of said multiple checkpoints is a most recently completed checkpoint;

copying said most recently completed checkpoint to said volatile memory to serve as an unrevised database for reconstructing said distributed counterpart;

retrieving selected ones of said operations from said stable log and a tail corresponding to said distributed counterpart; and

applying said operations to said unrevised database thereby to restore said distributed counterpart.

14. The method as recited in claim 13 wherein said applied revisions include log records, said method further including the steps of:

using memory locks while restoring said distributed counterpart, and

releasing ones of said memory locks as a function of applying ones of said log records.

15. The method as recited in claim 13 further including the step of receiving log records communicated from said client at said server.

16. The method as recited in claim 13 further including the step of requesting a region lock from said server by said client.

17. The method as recited in claim 13 further including the step of granting a region lock to said client by said server.

18. The method as recited in claim 13 further including the step of communicating validity information from said server to said client concerning said distributed counterpart.

19. The method as recited in claim 13 wherein said multiple checkpoints are checkpointed alternately.

20. The method as recited in claim 13 wherein said central database and said multiple checkpoints each contain an active transaction table, said method further comprising the step of copying said active transaction table from said most recently completed checkpoint to said volatile memory.

21. The method as recited in claim 13 wherein said stable log and said tail cooperate to form a global log, said step of applying comprising the step of applying said operations as a function of a temporal pointer associated with said global log.

22. The method as recited in claim 13 wherein said step of retrieving comprises the step of retrieving operations from said stable log and said tail corresponding to said distributed counterpart that were not made to said most recently completed checkpoint.

23. The method as recited in claim 13 wherein said multiple checkpoints and said stable log are stored on a nonvolatile storage device.

24. The method as recited in claim 13 wherein said central database further has an undo log for tracking operations to be undone in said distributed counterpart, said step of retrieving comprising the step of retrieving said selected ones of said operations as a function of a content of said undo log.

25. A network, comprising:

a server having a volatile memory that contains a central database therein;

at least one client associated with said server, said client having a volatile memory that contains a distributed counterpart of said central database to allow said distributed counterpart to be directly revised, said distributed counterpart subject to corruption;

at least one nonvolatile storage unit, coupled to said server, that contains multiple alternative checkpoints of said central database and a stable log, having a tail stored in said volatile memory of said client, for tracking operations to said distributed counterpart to allow corresponding operations to be made to said multiple alternative checkpoints; and

a processor, associated with said network, that executes routines for revising said central database and distributed counterpart and for restoring said distributed counterpart if said distributed counterpart is corrupted, said routines for restoring said distributed counterpart including;

a checkpoint determination controller that determines which of said multiple checkpoints is a most recently completed checkpoint and copies said most recently completed checkpoint to said volatile memory to serve as an unrevised database for reconstructing said distributed counterpart, and

an operation application controller that retrieves selected ones of said operations from said stable log and said tail corresponding to said distributed counterpart and applies said operations to said unrevised database thereby to restore said distributed counterpart.

26. The network as recited in claim 25 wherein said applied operations include log records, and said operation application controller, using memory locks while restoring said distributed counterpart, releases ones of said memory locks as a function of applying ones of said log records.

27. The network as recited in claim 25 wherein log records, having been communicated by said client, are received at said server.

28. The network as recited in claim 25 wherein said client requests a region lock from said server.

29. The network as recited in claim 25 wherein said server grants a region lock to said client.

30. The network as recited in claim 25 wherein said server communicates validity information to said client concerning said distributed counterpart.

31. The network as recited in claim 25 wherein said multiple checkpoints are checkpointed alternately.

32. The network as recited in claim 25 wherein said central database and said multiple checkpoints each contain an active transaction table, said checkpoint determination controller copying said active transaction table from said most recently completed checkpoint to said volatile memory.

33. The network as recited in claim 25 wherein said stable log and said tail cooperate to form a global log, said operation application controller applying said operations as a function of a temporal pointer associated with said global log.

34. The network as recited in claim 25 wherein said operation application controller retrieves operations from said stable log and said tail corresponding to said distributed counterpart that were not made to said most recently completed checkpoint.

35. The network as recited in claim 25 wherein said central database further has an undo log for tracking operations to be undone in said distributed counterpart, said operation application controller retrieving said selected ones of said operations as a function of a content of said undo log.