Log-structured temporal shadow store

• US 7,257,690 B1
• Filed: 10/15/2004
• Issued: 08/14/2007
• Est. Priority Date: 10/15/2004
• Status: Expired due to Fees

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Operating Corporation (Gen Digital Inc.)
• Inventors: Baird, Robert
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US10/966,968
• Time in Patent Office: 1,033 Days
• Field of Search: 707/210, 707/204, 711/162
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2056 by mirroring
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A log-structured temporal shadow store may comprise a logical storage aggregation including a plurality of blocks, a log-structured storage device, and shadow management software. The log-structured storage device may include a plurality of log entries, where each log entry includes one or more modified blocks of the logical storage aggregation and an index to the modified blocks. In response to a new batch of changes to the logical storage aggregation, the shadow management software may be configured to append a new log entry to the log-structured storage device, including newly modified blocks and an index to the newly modified blocks. The index may be organized as a modified B+ tree, and the log-structured storage device may be a logical volume, such as a mirrored logical volume.

Claims

1. A shadow store comprising:

a logical storage aggregation including a plurality of blocks;

a log-structured storage device; and

shadow management software,

wherein the log-structured storage device includes a plurality of log entries;

wherein each log entry of the plurality of log entries comprises one or more modified blocks of the logical storage aggregation and an index to the one or more modified blocks;

and wherein, in response to a new batch of changes to the logical storage aggregation, the shadow management software is configured to append a new log entry to the log-structured storage device, wherein the new log entry comprises one or more newly modified blocks of the logical storage aggregation and a new index to the one or more newly-modified blocks.

2. The shadow store as recited in claim 1, wherein the log-structured storage device further comprises a current-pointer indicative of a current log entry.

3. The shadow store as recited in claim 2, wherein each log entry of the plurality of log entries further comprises a previous-pointer indicative of a previous log entry.

4. The shadow store as recited in claim 3, wherein, in response to the request, the shadow management software is further configured to:

set the previous-pointer of the new log entry to the current log entry; and

set the current-pointer to the new log entry.

5. The shadow store as recited in claim 1, wherein the index within each log entry is organized as a modified B+ tree.

6. The shadow store as recited in claim 1, wherein the logical storage aggregation is a collection of one or more volumes.

7. The shadow store as recited in claim 6, wherein the collection of one or more volumes contains data of a file system.

8. The shadow store as recited in claim 1, wherein the collection of one or more volumes contains one or more database tables and associated metadata.

9. The shadow store as recited in claim 1, wherein the log-structured storage device is a logical volume.

10. The shadow store as recited in claim 1, wherein the log-structured storage device is a mirrored logical volume.

11. The shadow store as recited in claim 1, wherein each log entry of the plurality of log entries includes a timestamp indicative of a time at which a batch of changes is committed.

12. The shadow store as recited in claim 1, wherein the shadow management software is further configured to maintain a use count for each log entry of the plurality of log entries, indicative of a number of concurrent users of the log entry.

13. The shadow store as recited in claim 1, wherein the index at each log entry comprises one or more index entries, and wherein the shadow management software is further configured to copy one or more index entries from a previous log entry to the new index, and to leave out one or more obsolete index entries from the new index.

14. A system comprising:

a logical storage aggregation including a plurality of blocks;

a data producer;

a log-structured storage device; and

a shadow storage manager;

wherein the shadow storage manager is configured to;

maintain one or more entries in the log-structured storage device, wherein each entry of the one or more entries includes one or more modified blocks of the logical storage aggregation and an index to the one or more modified blocks;

and wherein, in response to a new batch of write operations targeted at the logical storage aggregation by the data producer, the shadow storage manager is further configured to append a new entry to the log-structured storage device.

15. The system as recited in claim 14, further comprising a first and a second physical storage device, wherein the log-structured storage device is a mirrored logical volume comprising a first and a second mirror, wherein the first mirror utilizes storage within the first physical storage device, and the second mirror utilizes storage within the second physical storage device.

16. The system as recited in claim 15, wherein, in response to a failure, the shadow storage manager is further configured to:

copy the contents of the current-pointer from the first mirror to the second mirror; and

restore an in-memory copy of an index of the most recently committed entry.

17. The system as recited in claim 15, further comprising a third physical storage device and repository management software, wherein the repository management software is configured to:

maintain a repository containing a baseline version of the logical storage aggregation at the third physical storage device; and

merge an entry of the one or more entries with the repository in accordance with a merge policy.

18. The system as recited in claim 14, wherein the log-structured storage device includes a current-pointer indicative of a most recently committed entry.

19. A method comprising:

maintaining a log-structured storage device including a plurality of log entries, wherein each log entry of the plurality of log entries comprises one or more modified blocks of a logical storage aggregation and an index to the one or more modified blocks; and

responding to a new batch of changes to the logical storage aggregation by appending a new log entry to the log-structured storage device, wherein the new log entry comprises one or more newly modified blocks of the logical storage aggregation and a new index to the one or more newly-modified blocks.

20. The method as recited in claim 19, wherein the index within each log entry is organized as a modified B+ tree.

21. The method as recited in claim 19, wherein the logical storage aggregation is a collection of one or more logical volumes.

22. The method as recited in claim 19, wherein the log-structured storage device is a mirrored logical volume.

23. The method as recited in claim 19, wherein each log entry of the plurality of log entries includes a timestamp indicative of a time at which a batch of changes is committed.

24. A computer-accessible storage medium comprising program instructions, wherein the program instructions are executable to:

maintain a log-structured storage device including a plurality of log entries, wherein each log entry of the plurality of log entries comprises one or more modified blocks of a logical storage aggregation and an index to the one or more modified blocks; and

respond to a new batch of changes to the logical storage aggregation by appending a new log entry to the log-structured storage device, wherein the new log entry comprises one or more newly modified blocks of the logical storage aggregation and a new index to the one or more newly-modified blocks.

25. The computer-accessible storage medium as recited in claim 24, wherein the index within each log entry is organized as a modified B+ tree.

26. The computer-accessible storage medium as recited in claim 24, wherein the logical storage aggregation is a collection of one or more logical volumes.

27. The computer-accessible storage medium as recited in claim 24, wherein the log-structured storage device is a mirrored logical volume.

28. The computer-accessible storage medium as recited in claim 24, wherein each log entry of the plurality of log entries includes a timestamp indicative of a time at which a batch of changes is committed.