Storage, organization and searching of data stored on a storage medium

• US 8,271,445 B2
• Filed: 06/08/2007
• Issued: 09/18/2012
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Arrouye, Yan, Hörnkvist, John
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US11/760,511
• Publication Number:
  US 20080307016A1
• Time in Patent Office: 1,929 Days
• Field of Search: None
• US Class Current: 707/649
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

Methods and apparatuses for storing, organizing and searching files stored in a storage device. Backup files may be stored in snapshot-dependent and/or snapshot-independent paths. The backup files may be stored with additional attributes that can be used for searching and/or indexing purposes.

Claims

1. A computer-implemented method comprising:

storing a new snapshot file on a non-transitory storage medium, the new snapshot file having a corresponding path name, the corresponding path name having a unique portion and a non-unique portion,

wherein, if a data file is created or modified after a previous most recent snapshot file was stored, the new snapshot file includes a copy of the data file,

wherein, if the data file remains unmodified after the previous most recent snapshot file was stored, the new snapshot file includes a link to a most recent snapshot file including a copy of the data file, and

wherein each snapshot file includes content associated with only one data file;

creating a snapshot-independent path name for the new snapshot file, the snapshot-independent path name comprising the non-unique portion of the corresponding path name and excluding the unique portion;

generating or updating an entry in an index for the new snapshot file using the snapshot-independent path name;

associating attributes with the data file to indicate a first snapshot file stored for the data file and a last snapshot file stored for the data file;

generating search results for a search within a plurality of snapshot files; and

limiting the generated search results to a subset of the snapshot files based on at least one of;

the indexed snapshot-independent path name, and

the attributes associated with the data file.

2. A method as in claim 1 wherein the unique portion of the corresponding path name comprises a date the new snapshot file was stored.

3. A method as in claim 1 wherein the data files are stored on a first storage medium and the snapshot files are stored on a second storage medium.

4. A method as in claim 1, wherein:

the attribute indicating the first snapshot file stored for the data file is a date the first snapshot file was stored; and

the attribute indicating the last snapshot file stored for the data file is a date the last snapshot file was stored.

5. A method as in claim 1 wherein the non-unique portion of the corresponding path name comprises a name of a directory in which the data file is stored.

6. A method as in claim 1, wherein the subset of snapshot files to which the generated search results are limited are snapshot files existing in a directory, the directory'"'"'s name based on the snapshot-independent path name.

7. A method as in claim 1, wherein the subset of snapshot files to which the generated search results are limited are snapshot files as they existed on a particular date based on the attributes associated with the data file.

8. A method as in claim 1, wherein the subset of snapshot files to which the generated search results are limited is a snapshot file in which the data file last appeared, the method further comprising:

sorting the attributes associated with the data file in order by values of the attributes;

determining which of the snapshot files is the snapshot file in which the data file last appeared based on the attribute having the most recent value; and

limiting generating search results to the snapshot file in which the data file last appeared.

9. An article comprising a non-transitory computer-readable medium having stored thereon instructions that, when executed cause one or more processors to:

store a new snapshot file on a non-transitory storage medium, the new snapshot file having a corresponding path name, the corresponding path name having a unique portion and a non-unique portion,

wherein, if a data file is created or modified after a previous most recent snapshot file was stored, the new snapshot file includes a copy of the data file,

wherein, if the data file remains unmodified after the previous most recent snapshot file was stored, the new snapshot file includes a link to a most recent snapshot file including a copy of the data file, and

wherein each snapshot file includes content associated with only one data file;

create a snapshot-independent path name for the new snapshot file, the snapshot-independent path name comprising the non-unique portion of the corresponding path name and excluding the unique portion;

generating or updating an entry in an index for the new snapshot file using the snapshot-independent path name;

associate attributes with the data file to indicate a first snapshot file stored for the data file and a last snapshot file stored for the data file;

generate search results for a search within a plurality of snapshot files; and

limit the generated search results to a subset of the snapshot files based on at least one of;

the indexed snapshot-independent path name, and

the attributes associated with the data file.

10. An article as in claim 9 wherein the unique portion of the corresponding path name comprises a date the new snapshot file was stored.

11. An article as in claim 9 wherein the data files are stored on a first storage medium and the snapshot files are stored on a second storage medium.

12. An article as in claim 9, wherein:

the attribute indicating the first snapshot file stored for the data file is a date the first snapshot file was stored; and

the attribute indicating the last snapshot file stored for the data file is a date the last snapshot file was stored.

13. An article as in claim 9 wherein the non-unique portion of the corresponding path name comprises a name of a directory in which the data file is stored.

14. An article as in claim 9, wherein the subset of snapshot files to which the generated search results are limited are snapshot files existing in a directory, the directory'"'"'s name based on the snapshot-independent path name.

15. An article as in claim 9, wherein the subset of snapshot files to which the generated search results are limited are snapshot files as they existed on a particular date based on the attributes associated with the data file.

16. An article as in claim 9, wherein the subset of snapshot files to which the generated search results are limited is a snapshot file in which the data file last appeared, and the instructions, when executed, further cause the one or more processors to:

sort the attributes associated with the data file in order by values of the attributes;

determine which of the snapshot files is the snapshot file in which the data file last appeared based on the attribute having the most recent value; and

limit search results generated for the query against the index to the snapshot file in which the data file last appeared.

17. An apparatus comprising:

means for storing a new snapshot file, the new snapshot file having a corresponding path name, the corresponding path name having a unique portion and a non-unique portion

wherein, if a data file is created or modified after a previous most recent snapshot file was stored, the new snapshot file includes a copy of the data file,

wherein, if the data file remains unmodified after the previous most recent snapshot file was stored, the new snapshot file includes a link to a most recent snapshot file including a copy of the data file, and

wherein each snapshot file includes content associated with only one data file;

means for creating a snapshot-independent path name for the new snapshot file, the snapshot-independent path name comprising the non-unique portion of the corresponding path name and excluding the unique portion;

means for generating or updating an entry in an index for the new snapshot file using the snapshot-independent path name;

means for associating attributes with the data file to indicate a first snapshot file stored for the data file and a last snapshot file stored for the data file;

means for generating search results for a search within a plurality of snapshot files; and

means for limiting the generated search results based on at least one of;

the indexed snapshot-independent path name, and

the attributes associated with the data file.

18. A system comprising:

one or more input/output devices;

a processor coupled to receive input from at least one of the input/output devices;

a non-transitory storage medium having stored thereon an index of snapshot files;

a backup agent coupled to communicate with the processor,

the backup agent to cause the processor;

to store a new snapshot file, the new snapshot file having a corresponding path name, the corresponding path name having a unique portion and a non-unique portion,

wherein, if a data file is created or modified after a previous most recent snapshot file was stored, the new snapshot file includes a copy of the data file,

wherein, if the data file remains unmodified after the previous most recent snapshot file was stored, the new snapshot file includes a link to a most recent snapshot file including a copy of the data file, and

wherein each snapshot file includes content associated with only one data file;

to create a snapshot-independent path name for the new snapshot file, the snapshot-independent path name comprising the non-unique portion of the corresponding path name and excluding the unique portion;

to generate or update an entry in the index for the new snapshot file using the snapshot-independent path name;

to associate attributes with the data file to indicate a first snapshot file stored for the data file and a last snapshot file stored for the data file;

to generate search results for a search within a plurality of snapshot files; and

to limit the generated search results to a subset of the snapshot files based on at least one of;

the indexed snapshot-independent path name, and

the attributes associated with the data file.

19. A system as in claim 18 wherein the backup agent comprises one or more software routines executed by the processor to cause the search results to be output to at least one of the input/output devices.

20. A system as in claim 18 wherein the backup agent comprises one or more circuits coupled with the processor to cause the search results to be output to at least one of the input/output devices.

21. A system as in claim 18 wherein the backup agent comprises a combination of one or more software routines executed by the processor and one or more circuits coupled with the processor to cause the search results to be output to at least one of the input/output devices.

22. A system as in claim 18 wherein the backup agent comprises a snapshot organization module to cause the snapshot files to be stored, generate the snapshot-independent path names, perform the indexing, and to associate the attributes with the data file.

23. A system as in claim 18 wherein the backup agent comprises a snapshot search module to limit generating the search results for the query again the index to the subset of the snapshot files based on the snapshot-independent path names.

24. A system as in claim 18 wherein the backup agent comprises a file attribute search module to limit the generated search results to the subset of the snapshot files based on the attributes associated with the data file.

25. A system as in claim 18, wherein:

the attribute indicating the first snapshot file stored for the data file is a date the first snapshot file was stored; and

the attribute indicating the last snapshot file stored for the data file is a date the last snapshot file was stored.

26. A system as in claim 18 wherein the non-unique portion of the corresponding path name comprises a name of a directory in which the data file is stored.

27. A system as in claim 18, wherein the subset of snapshot files to which the generated search results are limited are snapshot files existing in a directory, the directory'"'"'s name based on the snapshot-independent path name.

28. A system as in claim 18 wherein the subset of snapshot files to which the generated search results are limited are snapshot files as they existed on a particular date based on the attributes associated with the data file.

29. A system as in claim 18, wherein the subset of snapshot files to which the generated search results are limited is a snapshot file in which the data file last appeared, and further wherein the backup agent further causes the processor to:

sort the attributes associated with the data file in order by values of the attributes;

determine which of the snapshot files is the snapshot file in which the data file last appeared based on the attribute having the most recent value; and

limit search results generated for the query against the index to the snapshot file in which the data file last appeared.