METHOD AND APPARATUS FOR EFFICIENTLY MERGING, STORING AND RETRIEVING INCREMENTAL DATA

• US 20080222219A1
• Filed: 02/20/2008
• Published: 09/11/2008
• Est. Priority Date: 03/05/2007
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: AppAssure Software, Inc. (Dell Technologies Inc.)
• Inventors: Varadarajan, Srinidhi
• Granted Patent: US 9,690,790 B2
• Time in Patent Office: Days
• US Class Current: 707/204
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16

Abstract

In a method and apparatus for retrieving data from a snapshot data storage system, for each epoch, a snapshot including (i) all changed data, and (ii) an index is created. The index includes an entry for each page that has changed during the epoch. For rapidly retrieving the data as of any given time, the method creates a hash table that includes an entry for each data page that has changed since the baseline was created. The hash table entry indicates the epoch in which the data most recently changed and an offset corresponding to the location of the changed data in the corresponding snapshot. The hash table is created by inserting an entry for each page in the most recent index, and then examining the remaining indices for all other snapshots from the most recent to the oldest snapshot and adding any non-duplicate entries into the table.

Claims

1. A method for identifying the latest data for a plurality of pages in a set of incrementally stored data as of a desired time, the incrementally stored data including a base archive and a plurality of snapshots, each snapshot including a copy of each page of data that was changed in a corresponding epoch and an index that indicates an identity of each page that was changed during the corresponding epoch and a location of the copy, the method comprising the steps of:

processing an index of a snapshot for each epoch corresponding to a time period later than creation of the base archive and no later than the desired time to identify a location of a most recent copy of each page of data in the plurality of pages that was changed during the time period; and

storing a location of each most recent copy identified in the searching step in a memory.

2. The method of claim 1, wherein each location identified in the searching step is stored in a data structure.

3. The method of claim 2, wherein the data structure is a hash table.

4. The method of claim 1, wherein the searching and storing steps for each snapshot corresponding to the time period are performed before a request for data in a corresponding epoch is received.

5. The method of claim 1, wherein the searching and storing steps for each snapshot corresponding to the time period are performed after a request for data in a corresponding epoch is received.

6. The method of claim 1, wherein the plurality of pages corresponds to all pages stored on one or more physical devices.

7. The method of claim 1, wherein the plurality of pages corresponds to a logical division of pages stored on one or more physical devices.

8. The method of claim 7, wherein the logical division is a folder.

9. The method of claim 1, wherein data is stored in variable length pages.

10. The method of claim 1, further comprising the step of using information stored in the memory during the storing step to retrieve a most recent version of a desired page.

11. The method of claim 10, wherein retrieving the most recent version of the desired page includes the steps of:

identifying in the memory an entry corresponding to the desired page;

if an entry corresponding to the desired page is identified, retrieving the data from the snapshot corresponding to the epoch identified by the entry; and

if an entry is not found in the hash table, retrieving the data from the base archive.

12. A device for identifying the latest data for a plurality of pages in a set of incrementally stored data as of a desired time, the device comprising:

a processor;

a memory connected to the processor; and

an interface connected to the processor, the interface being operable to communicate on a storage device on which the incrementally stored data is stored, the incrementally stored data including a base archive and a plurality of snapshots, each of the snapshots including a copy of each page of data that was changed in a corresponding epoch and an index that includes an identifier and a location for each page in the plurality of pages that was changed during the corresponding epoch, the incrementally stored data including a base archive and a plurality of snapshots, each of the snapshots including a copy of each page of data that was changed in a corresponding epoch and an index that includes an identifier and a location for each page that was changed during the corresponding epoch;

wherein the processor is configured to perform the steps of

processing a index of a snapshot for each epoch corresponding to a time period later than creation of the base archive and no later than the desired time to identify a location of a most recent copy of each page of data in the plurality of pages that was changed during the time period; and

storing a location of each most recent copy identified in the searching step in a memory.

13. The device of claim 12, wherein each location identified in the searching step is stored in a data structure.

14. The device of claim 13, wherein the data structure is a hash table.

15. The device of claim 12, wherein the searching and storing steps for each snapshot corresponding to the time period are performed before a request for data in a corresponding epoch is received.

16. The device of claim 12, wherein the searching and storing steps for each snapshot corresponding to the time period are performed after a request for data in a corresponding epoch is received.

17. The device of claim 12, wherein the plurality of pages corresponds to all pages stored on one or more physical devices.

18. The device of claim 12, wherein the plurality of pages corresponds to a logical division of pages stored on one or more physical devices.

19. The device of claim 18, wherein the logical division is a folder.

20. The device of claim 12, wherein data is stored in variable length pages.

21. The device of claim 12, further comprising the step of using information stored in the memory during the storing step to retrieve a most recent version of a desired page.

22. The device of claim 21, wherein retrieving the most recent version of the desired page includes the steps of:

identifying in the memory an entry corresponding to the desired page;

if an entry corresponding to the desired page is identified, retrieving the data from the snapshot corresponding to the epoch identified by the entry; and

if an entry is not found in the hash table, retrieving the data from the base archive.