Methods and apparatuses for data protection

• US 8,255,371 B2
• Filed: 10/29/2009
• Issued: 08/28/2012
• Est. Priority Date: 06/10/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Giampaolo, Dominic Benjamin, Mackovitch, Michael Steven
• Primary Examiner(s): Breene, John E
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US12/608,981
• Publication Number:
  US 20100049751A1
• Time in Patent Office: 1,034 Days
• Field of Search: 707/640, 707/661, 707/674, 707/695, 707/703, 707/827, 707/826, 715/229, 713/151, 713/160, 713/165, 713/189, 713/193, 726/26, 726/27, 726/34, 709/204, 709/224
• US Class Current: 707/695
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Methods and apparatuses for data protection against corrupted write operations. In one embodiment, a technique of crash protection uses an atomically updated global transaction indicator to switch a set of data structures from one set of versions to another set. In one embodiment, the storage space for multiple versions of a data structure is allocated at the time the data structure is created on the storage device so that the multiple versions of the data structure can be kept close by. Between two consistent points, some data structures are modified to create new versions without changing the corresponding previous versions; and unmodified data structures are not copied. At a consistent point, the global transaction indicator is updated to indicate a set of consistent versions of the data structures, such as metadata of a file system.

Claims

1. A method, comprising:

allocating respective storage space for multiple versions of each of multiple items of data;

making multiple data changes to said multiple items of data where more than one of said items of data is changed multiple times, wherein, changes made to a same item of data have respective transaction identifiers such that a previous change to said same item of data is recognizable as having been made earlier than a later change to said same item of data through analysis of the previous and later changes'"'"' respective transaction identifiers, and wherein, changes made to said same item of data are kept so as to create different kept versions of said same item of data, and wherein, storage space needed to keep all of said different kept versions exceeds storage space allocated for said same item of data'"'"'s multiple versions, said method therefore further including writing a newest version of said same item of data over an oldest version of said same item of data;

flushing said items of data from a cache to a non volatile storage;

marking said flushing of said items of data as a consistent point of said multiple items of data including assigning a global transaction identifier to said items of data;

making additional changes to some but not all of said items of data after said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data have associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier, and, recording on a list respective transaction identifiers for said changes made to some but not all of said items of data in a list;

experiencing a crash before a next global transaction identifier is assigned for said items of data; and

,

in response to said crash, referring to said list to remove said versions thereof so as to restore said set of data items to said consistent point such that said versions thereof are not recognized.

2. The method of claim 1 wherein a same transaction identifier exists on changes made to different items of data of said multiple items of data.

3. The method of claim 2 further comprising having a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers.

4. The method of claim 1 further comprising keeping versions of the same data item proximate to one another.

5. The method of claim 1 wherein said list is kept on a non volatile storage device.

6. The method of claim 1 further comprising, in response to said crash:

calculating a range of invalid transaction identifiers from said global transaction identifier and a maximum number of transactions allowed after consistent point has been reached; and

,

comparing said range of invalid transaction identifiers against said list to identify said respective transaction identifiers.

7. A machine readable storage medium containing stored program code that when processed by a central processing unit of a computing system causes a method to be performed, said method comprising:

allocating respective storage space for multiple versions of each of multiple items of data;

making multiple data changes to said multiple items of data where more than one of said items of data is changed multiple times, wherein, changes made to a same item of data have respective transaction identifiers such that a previous change to said same item of data is recognizable as having been made earlier than a later change to said same item of data through analysis of the previous and later changes'"'"' respective transaction identifiers, and wherein, changes made to said same item of data are kept so as to create different kept versions of said same item of data, and wherein, storage space needed to keep all of said different kept versions exceeds storage space allocated for said same item of data'"'"'s multiple versions, said method therefore further including writing a newest version of said same item of data over an oldest version of said same item of data;

flushing said items of data from a cache to a non volatile storage;

marking said flushing of said items of data as a consistent point of said multiple items of data including assigning a global transaction identifier to said items of data;

making additional changes to some but not all of said items of data after said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data have associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier, and, recording on a list respective transaction identifiers for said changes made to some but not all of said items of data in a list;

experiencing a crash before a next global transaction identifier is assigned for said items of data; and

,

in response to said crash, referring to said list to remove said versions thereof so as to restore said set of data items to said consistent point such that said versions thereof are not recognized.

8. The machine readable storage medium of claim 7 wherein a same transaction identifier exists on changes made to different items of data of said multiple items of data.

9. The method of claim 8 further comprising having a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers.

10. The machine readable storage medium of claim 7 further comprising keeping versions of the same data item proximate to one another.

11. The machine readable storage medium of claim 7 wherein said list is kept on a non volatile storage device.

12. The machine readable storage medium of claim 7 further comprising, in response to said crash:

calculating a range of invalid transaction identifiers from said global transaction identifier and a maximum number of transactions allowed after consistent point has been reached; and

,

comparing said range of invalid transaction identifiers against said list to identify said respective transaction identifiers.

13. A computing system having a storage medium and a central processing unit, said storage medium containing stored program code that when processed by said central processing unit causes a method to be performed, said method comprising:

allocating respective storage space for multiple versions of each of multiple items of data;

making multiple data changes to said multiple items of data where more than one of said items of data is changed multiple times, wherein, changes made to a same item of data have respective transaction identifiers such that a previous change to said same item of data is recognizable as having been made earlier than a later change to said same item of data through analysis of the previous and later changes'"'"' respective transaction identifiers, and wherein, changes made to said same item of data are kept so as to create different kept versions of said same item of data, and wherein, storage space needed to keep all of said different kept versions exceeds storage space allocated for said same item of data'"'"'s multiple versions, said method therefore further including writing a newest version of said same item of data over an oldest version of said same item of data;

flushing said items of data from a cache to a non volatile storage;

marking said flushing of said items of data as a consistent point of said multiple items of data including assigning a global transaction identifier to said items of data;

making additional changes to some but not all of said items of data after said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data have associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier, and, recording on a list respective transaction identifiers for said changes made to some but not all of said items of data in a list;

experiencing a crash before a next global transaction identifier is assigned for said items of data; and

,

in response to said crash, referring to said list to remove said versions thereof so as to restore said set of data items to said consistent point such that said versions thereof are not recognized.

14. The computing system of claim 13 wherein a same transaction identifier exists on changes made to different items of data of said multiple items of data.

15. The computing system of claim 14 further comprising having a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers.

16. The computing system of claim 13 further comprising keeping versions of the same data item proximate to one another.

17. The computing system of claim 13 wherein said list is kept on a non volatile storage device.

18. The computing system of claim 13 further comprising, in response to said crash:

calculating a range of invalid transaction identifiers from said global transaction identifier and a maximum number of transactions allowed after consistent point has been reached; and

,

comparing said range of invalid transaction identifiers against said list to identify said respective transaction identifiers.