METHODS AND APPARATUS FOR POINT IN TIME DATA ACCESS AND RECOVERY

• US 20070162513A1
• Filed: 12/12/2006
• Published: 07/12/2007
• Est. Priority Date: 12/21/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Israel Development Center Limited (Dell Technologies Inc.)
• Inventors: Heller, Yair, Lewin, Michael, Weber, Oded, Angel, Efrat, Shoshan, Avi, Drukh, Evgeny, Natanzon, Assaf, Kedem, Ziv, Ahal, Shlomo
• Granted Patent: US 7,774,565 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27

Abstract

Methods and systems for accessing data from a previous point in time, including receiving data stored in a storage system of addressable memory, the storage system including a plurality of addresses, receiving a journal history of write transactions for the storage, each write transaction including (i) a plurality of designated memory addresses, (ii) a corresponding plurality of current data to write in the designated memory addresses for storage, and (iii) a time indicator, generating a data structure that represents a virtual interface to the storage at a specified point in time, based on the write transactions in the journal history having a time subsequent to the specified point in time, and enabling a user to process the data from the specified point in time, via the virtual interface and the journal history.

Claims

1. A method for accessing data from a previous point in time, comprising:

receiving data stored in a storage system of addressable memory, the storage system including a plurality of addresses;

receiving a journal history of write transactions for the storage, each write transaction including (i) a plurality of designated memory addresses, (ii) a corresponding plurality of current data to write in the designated memory addresses for storage, and (iii) a time indicator;

generating a data structure that represents a virtual interface to the storage at a specified point in time, based on the write transactions in the journal history having a time subsequent to the specified point in time; and

enabling a user to process data from the specified point in time, via the virtual interface and the journal history.

2. The method of claim 1 further comprising rolling back the storage to the data that was stored therein at the specified point in time, based on the write transactions in the journal history having a data and time subsequent to the specified point in time, while the user is using the virtual interface to the storage.

3. The method of claim 2 further comprising switching from the virtual storage interface via the journal history, over to a direct interface to the rolled back storage, after completion of said rolling back, thereby enabling the user to continue data processing without interruption.

4. The method of claim 3 further comprising:

generating a journal of auxiliary write transactions while the user is processing data via the virtual interface; and

applying at least a portion of the auxiliary write transactions after said rolling back and prior to said switching.

5. The method of claim 1 wherein the data structure that represents the virtual interface includes a binary tree data structure.

6. The method of claim 5 further comprising:

generating a multiplicity of non-overlapping intervals of contiguous memory addresses, based on the pluralities of designated memory addresses in the write transactions in the journal history that have a date and time subsequent to the specified point in time; and

organizing the multiplicity of non-overlapping intervals into the binary tree data structure.

7. The method of claim 6 further comprising, for each write transaction in the journal history having a time subsequent to the specified point in time, examining the write transaction, comprising:

extracting the plurality of designated memory addresses within the write transaction currently being examined;

comparing the extracted plurality of designated memory addresses with previously extracted pluralities of memory addresses, to identify overlap therewith;

decomposing the plurality of designated memory addresses currently being examined into at least one overlapping part and at least one non-overlapping part;

appending the at least one non-overlapping part to a list of pluralities of memory addresses; and

associating the at least one non-overlapping part with the write transaction currently being examined.

8. The method of claim 6 wherein said enabling comprises identifying data that was stored in the storage at a requested memory address at the specified point in time, comprising:

searching for an interval of contiguous memory addresses in the binary tree data structure that contains the requested memory address; and

finding the last data written to the interval identified by said searching, within the journal history.

9. The method of claim 1 wherein the data structure that represents the virtual interface includes at least one sorted list.

10. The method of claim 9 further comprising:

defining a partition of the storage memory into a multiplicity of bins, each bin corresponding to a contiguous range of memory addresses;

for each bin of the partition, initializing a sorted list of pluralities of memory addresses for such bin; and

for each write transaction in the journal history having a data and time subsequent to the specified point in time, examining the write transaction, comprising;

extracting the plurality of designated memory addresses within the write transaction currently being examined;

allocating the plurality of designated memory addresses into an appropriate one of the multiplicity of bins; and

recording the plurality of designated memory addresses within the sorted list of the appropriate bin.

11. The method of claim 10 further comprising, for each bin of the partition, recording selected ones of the pluralities of memory addresses into a filtered list for such bin.

12. The method of claim 11 wherein said enabling comprises identifying data that was stored in the storage at a requested memory address at the specified point in time, comprising:

identifying a relevant bin to which the requested memory address corresponds;

locating two pluralities of memory addresses, within the filtered list for the relevant bin, which bound the requested memory address; and

searching a portion of the sorted list for the relevant bin, for pluralities of memory addresses that include the requested memory address, wherein the portion is limited to those pluralities of memory addresses situated between the bounding pluralities provided by said locating.

13. A data access system, comprising:

a storage system of addressable memory, the storage system including data stored at a plurality of addresses;

a journal history of write transactions for said storage system, each write transaction including (i) a plurality of designated memory addresses, (ii) a corresponding plurality of current data to write in the designated memory addresses for storage, and (iii) a time indicator;

a data protector, comprising;

a data protector memory;

a journal processor for generating a data structure, stored within said data protector memory, which represents a virtual interface to the storage at a specified point in time, based on the write transactions in the journal having a data and time subsequent to the specified point in time;

a storage manager for rolling back the storage to the data that was stored therein at the specified point in time, based on the journal of write transactions, while a user is using the virtual interface to the storage; and

a data protector switcher for switching from the virtual storage interface via the journal history, over to a direct interface to the rolled back storage, after completion of said rolling back, thereby enabling the user to continue data processing without interruption; and

a host application driver for enabling a user to process data from the specified point in time, via the virtual interface and the journal history, via the virtual interface and the journal history.

14. The data access system of claim 13 wherein said storage protector further comprises a storage manager for rolling back the storage to the data that was stored therein at the specified point in time, based on the journal of write transactions, while the user is using the virtual interface to the storage.

15. The data access system of claim 14 wherein said data protector further comprises a data protector switcher for switching from the virtual storage interface via the journal history, over to a direct interface to the rolled back storage, after completion of said rolling back, thereby enabling the user to continue data processing without interruption.

16. A computer-readable storage medium storing program code for causing a computing device:

to receive data stored in a storage system of addressable memory, the storage system including a plurality of addresses;

to receive a journal history of write transactions for the storage, each write transaction including (i) a plurality of designated memory addresses, (ii) a corresponding plurality of current data to write in the designated memory addresses for storage, and (iii) a time indicator;

to generate a data structure that represents a virtual interface to the storage at a specified point in time, based on the write transactions in the journal history having a time subsequent to the specified point in time; and

to enable a user to process the data from the specified point in time, via the virtual interface and the journal history.

17. The article according to claim 16, further comprising program code for rolling back the storage to the data that was stored therein at the specified point in time, based on the write transactions in the journal history having a data and time subsequent to the specified point in time, while the user is using the virtual interface to the storage.

18. The article according to claim 17 further comprising program code switching from the virtual storage interface via the journal history, over to a direct interface to the rolled back storage, after completion of said rolling back, thereby enabling the user to continue data processing without interruption.

19. The article of claim 18 further comprising program code for:

generating a journal of auxiliary write transactions while the user is processing data via the virtual interface; and

applying at least a portion of the auxiliary write transactions after said rolling back and prior to said switching.

20. The article of claim 19 further comprising program code for:

generating a multiplicity of non-overlapping intervals of contiguous memory addresses, based on the pluralities of designated memory addresses in the write transactions in the journal history that have a date and time subsequent to the specified point in time; and

organizing the multiplicity of non-overlapping intervals into the binary tree data structure.