Methods and apparatuses for data protection

• US 8,239,356 B2
• Filed: 10/29/2009
• Issued: 08/07/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,968
• Publication Number:
  US 20100114847A1
• Time in Patent Office: 1,013 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:

concurrently executing multiple applications, said concurrently executing of said multiple applications including making multiple data changes to 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, a same transaction identifier exists on changes made to different items of data of said multiple items 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, wherein, a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers exists;

continuing with said concurrent execution of said multiple applications including making changes to some but not all of said items of data relative to the state of said items of data as of said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data having associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier;

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

,

in response to said crash, restoring said set of data items to said consistent point such that said versions thereof are not recognized.

2. The method of claim 1 wherein said applications execute on a multi-tasking operating system.

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

4. The method of claim 1 wherein said restoring further comprises comparing said global transaction identifier against said associated transaction identifiers of said changes made to some but not all of said items of data to flag and eliminate said versions thereof.

5. 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:

concurrently executing multiple applications, said concurrently executing of said multiple applications including making multiple data changes to 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, a same transaction identifier exists on changes made to different items of data of said multiple items 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, wherein, a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers exists;

continuing with said concurrent execution of said multiple applications including making changes to some but not all of said items of data relative to the state of said items of data as of said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data having associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier;

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

,

in response to said crash, restoring said set of data items to said consistent point such that said versions thereof are not recognized.

6. The machine readable storage medium of claim 5 wherein said applications execute on a multi-tasking operating system.

7. The machine readable storage medium of claim 5 wherein said method further comprises keeping versions of the same data item proximate to one another.

8. The machine readable storage medium of claim 5 wherein said restoring further comprises comparing said global transaction identifier against said associated transaction identifiers of said changes made to some but not all of said items of data to flag and eliminate said versions thereof.

9. 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:

concurrently executing multiple applications, said concurrently executing of said multiple applications including making multiple data changes to 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, a same transaction identifier exists on changes made to different items of data of said multiple items 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, wherein, a maximum limit on the number of transactions that correspond to a transaction identifier between consecutive markings of global transaction identifiers exists;

continuing with said concurrent execution of said multiple applications including making changes to some but not all of said items of data relative to the state of said items of data as of said flushing and keeping versions thereof, wherein, said changes to some but not all of said items of data having associated transaction identifiers that are recognizable as being made after said assignment of said global transaction identifier;

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

,

in response to said crash, restoring said set of data items to said consistent point such that said versions thereof are not recognized.

10. The computing system of claim 9 wherein said applications execute on a multi-tasking operating system.

11. The computing system of claim 9 wherein said method further comprises keeping versions of the same data item proximate to one another.

12. The computing system of claim 9 wherein said restoring further comprises comparing said global transaction identifier against said associated transaction identifiers of said changes made to some but not all of said items of data to flag and eliminate said versions thereof.