Methods and apparatus for recording write requests directed to a data store

• US 20050066118A1
• Filed: 08/24/2004
• Published: 03/24/2005
• Est. Priority Date: 09/23/2003
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Perry, Robert, Passerini, Ron, Rowan, Michael
• Granted Patent: US 7,904,428 B2
• Time in Patent Office: Days
• US Class Current: 711/112
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• 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

Abstract

A storage management device records write requests that are directed to a data store. In one embodiment, the storage management device records a plurality of write request entries, each one of which includes information relating to a write request, in at least one first database table, and maintains, for each first database table, at least one record in a second database table. The one or more records in the second database table include data representing the effects of the write requests on a state of at least one portion of the data store. In one such embodiment, each time that one write request entry is recorded in one first database table, the storage management device updates at least one record in the second database table.

Claims

1. A method for recording write requests directed to a data store, the method comprising:

recording in at least one first database table a plurality of write request entries, each write request entry comprising information relating to a write request that was directed to a data store;

maintaining, for each first database table, at least one record in a second database table, the one or more records comprising data representing the effects of the write requests on a state of at least one portion of the data store; and

updating, each time that one write request entry is recorded in one first database table, at least one record in the second database table.

2. The method of claim 1, wherein each record comprises a plurality of bit entries, each bit entry being set or unset.

3. The method of claim 2, wherein each bit entry corresponds to at least one unit of storage located within the at least one portion of the data store.

4. The method of claim 3, wherein each bit entry that is set indicates that the at least one unit of storage located within the at least one portion of the data store to which that bit entry corresponds has been overwritten at least once.

5. The method of claim 3, wherein each bit entry that is unset indicates that the at least one unit of storage located within the at least one portion of the data store to which that bit entry corresponds has not been overwritten at least once.

6. The method of claim 2, wherein updating at least one record in the second database table comprises setting each bit entry in the at least one record that is unset and that corresponds to a unit of storage located within the at least one portion of the data store that is overwritten.

7. The method of claim 2, wherein each record comprises at least one byte of bit entries.

8. The method of claim 2, wherein each record comprises at least one word of bit entries.

9. The method of claim 1, wherein the data of each record comprises a binary representation.

10. The method of claim 1, wherein the data of each record comprises a hexadecimal representation.

11. The method of claim 1, wherein each record further comprises an identifier for identifying a first database table with which that record is associated.

12. The method of claim 1, wherein the data representing the effects of the write requests on the state of the at least one portion of the data store identifies at least one unit of storage located within the at least one portion of the data store that was overwritten by the write requests.

13. The method of claim 1 further comprising identifying at least one first database table to search by interpreting the one or more records in the second database table.

14. The method of claim 13, wherein each record in the second database table comprises a plurality of bit entries, each bit entry corresponding to at least one unit of storage located within the at least one portion of the data store and each bit entry being set or unset, and wherein identifying at least one first database table to search comprises, for each of the at least one units of storage located within the at least one portion of the data store that has at least one corresponding bit entry, determining whether at least one record has a bit entry for that at least one unit of storage that is set.

15. The method of claim 14, wherein, upon determining, for a particular at least one unit of storage located within the at least one portion of the data store, that at least one record has a bit entry for that particular at least one unit of storage that is set, identifying at least one first database table to search further comprises identifying the one or more records that have a bit entry that is set for that particular at least one unit of storage.

16. The method of claim 15, wherein, upon identifying the one or more records that have a bit entry that is set for the particular at least one unit of storage, identifying at least one first database table to search further comprises identifying the one or more first database tables for which those identified records are maintained.

17. The method of claim 14, wherein determining, for a particular at least one unit of storage located within the at least one portion of the data store, whether at least one record has a bit entry for that particular at least one unit of storage that is set comprises performing the Boolean OR operation on the bit entries that correspond to that particular at least one unit of storage.

18. The method of claim 14, wherein determining, for a particular at least one unit of storage located within the at least one portion of the data store, whether at least one record has a bit entry for that particular at least one unit of storage that is set comprises performing the Boolean AND operation on the bit entries that correspond to that particular at least one unit of storage.

19. The method of claim 13 further comprising searching the at least one identified first database table.

20. The method of claim 19 further comprising generating at least a portion of a time map of the at least one portion of the data store for a past time.

21. The method of claim 20, wherein each record in the second database table comprises a plurality of bit entries, each bit entry corresponding to at least one unit of storage located within the at least one portion of the data store and each bit entry being set or unset, and wherein searching the at least one identified first database table comprises, for each at least one unit of storage located within the at least one portion of the data store that has a corresponding bit entry that is set, determining a first time following the past time at which previous data stored at that at least one unit of storage was copied to a new location and overwritten at that at least one unit of storage.

22. The method of claim 21, wherein searching the at least one identified first database table further comprises determining the new location to which the previous data was copied.

23. The method of claim 22, wherein generating at least a portion of a time map of at least one portion of the data store for the past time comprises using the new location.

24. The method of claim 19 further comprising responding to a read request for data stored in at least one specified unit of storage located within the at least one portion of the data store at a past time.

25. The method of claim 24, wherein each record in the second database table comprises a plurality of bit entries, each bit entry corresponding to at least one unit of storage located within the at least one portion of the data store and each bit entry being set or unset, and wherein searching the at least one identified first database table comprises, for each at least one unit of storage specified in the read request that has a corresponding bit entry that is set, determining a first time following the past time at which previous data stored at that specified unit of storage was copied to a new location and overwritten at that specified unit of storage.

26. The method of claim 25, wherein searching the at least one identified first database table further comprises determining the new location to which the previous data was copied.

27. The method of claim 26, wherein responding to the read request comprises reading the previous data from the new location.

28. The method of claim 27, wherein responding to the read request further comprises transmitting the previous data.

29. The method of claim 1, wherein the information of each write request entry comprises an identification of at least one unit of storage located within the data store to which the write request was directed.

30. The method of claim 1, wherein each write request results in previous data, previously stored at at least one unit of storage located within the data store, being copied to a new location and being overwritten at the at least one unit of storage located within the data store.

31. The method of claim 30, wherein the information of each write request entry comprises the new location to which the previous data is copied.

32. The method of claim 1, wherein the information of each write request entry comprises a time at which the write request was received.

33. A device for recording write requests directed to a data store, the device comprising:

at least one first database table for recording a plurality of write request entries, each write request entry comprising information relating to a write request that was directed to a data store;

a second database table comprising at least one record for each first database table, the one or more records comprising data representing the effects of the write requests on a state of at least one portion of the data store; and

an updating module for updating, each time that one write request entry is recorded in one first database table, at least one record in the second database table.