Single instance store for file systems

• US 6,477,544 B1
• Filed: 07/16/1999
• Issued: 11/05/2002
• Est. Priority Date: 07/16/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rashid, Richard F., Goebel, David A., Myhrvold, Nathan P., Bolosky, William J., Douceur, John R., Cutshall, Scott M.
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Truong, Cam Y T
• Application Number:
  US09/354,624
• Time in Patent Office: 1,208 Days
• Field of Search: 707/1, 707/3, 707/10, 707/100, 707/200, 707/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and system for storing the data of files having duplicate content, by maintaining a single instance of the data, and providing logically separate links to the single instance. Files of duplicate content have their data stored in a common store file by a single instance store (SIS) facility, which also converts the original file or files to links to that common store file and creates additional links thereto as needed. The SIS facility may reside above a file system as a filter driver. File system requests directed to the link file (e.g., open, write, read, close and delete) reach the SIS filter, which then transparently handles each request as if the link file was a normal file. To preserve logical separation, writes to a SIS link file are to the link file, and the written portion recorded as dirty. The SIS filter intercepts SIS read requests, and reads clean portions from the common store file and any dirty portions from the link file. When the link file is closed, the common store file also may be closed, and, if the link file has been written, the non-dirtied portions of the link file are filled in with clean data from the common store file, and the link file reconverted to a normal file. Security is provided to prevent unauthorized access to the common store files, as is a volume check facility that repairs any inconsistencies in SIS metadata.

Claims

1. In a computer system having a file system of files, a method of storing data of first and second files having duplicate data, comprising the steps of:

maintaining a single instance of the data;

for the first file, providing a link file to the single instance of the data, the link file representing the first file to provide logically separate file system access to the single instance representation of the file data, the link file logically separate from the second file such that file system actions via the link file do not affect the data of the second file; and

reclaiming storage space that was occupied by the duplicate data of the first file.

2. The method of claim 1 wherein the step of maintaining the single instance of the data comprises the step of copying the data from the first file to a file in a common store.

3. The method of claim 1 wherein the step of providing the link file comprises the step of converting the first file to the link file.

4. The method of claim 3 wherein the step of converting the first file to the link file comprises the step of deallocating data space of the first file.

5. The method of claim 3 wherein the step of converting the first file to the link file comprises the step of associating information including a special identifier with the link file.

6. The method of claim 5 wherein the step of associating information including the special identifier to the link file includes associating a reparse point with the link file.

7. The method of claim 5 wherein the information further includes data for identifying the single instance of data pointed to by the link file.

8. The method of claim 6 wherein the reparse point includes a reparse tag and reparse data.

9. The method of claim 8 further comprising the steps of computing a signature using the data of the first file, and storing the signature with the reparse data.

10. The method of claim 1 further comprising the step of receiving a request to open the link file.

11. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the steps of, receiving a request to open the link file, and passing to the file system a request to open the common store file.

12. The method of claim 11 further comprising the step of passing to the file system a request to open the link file.

13. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the steps of, computing a signature, associating the signature with the link file, associating the signature with the common store file, receiving a request to open the link file, comprising the signature associated with the link file with the signature associated with the common store file, and if the signatures match, passing to the file system a request to open the link file.

14. The method of claim 1 further comprising the steps of, opening the link file, and associating a context with the link file.

15. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the step of, storing a backpointer in the common store file for each link pointing thereto.

16. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the steps of, receiving a request to read from the link file, and passing to the file system a request to read from the common store file.

17. The method of claim 16 further comprising the steps of, receiving data read from the common store file, and returning the data read from the common store file in response to the request to read from the link file.

18. The method of claim 1 further comprising the steps of, receiving a request to read from the link file, determining that the request is to an allocated portion of the link file, and passing to the file system a request to read from the link file.

19. The method of claim 18 further comprising the steps of associating a context with the link file, and wherein the step of determining that the request is to an allocated portion of the link file comprises the step of evaluating information in the context.

20. The method of claim 1 further comprising the steps of, receiving a request to read from the link file, determining that the request is directed to at least one allocated portion of the link file and at least one unallocated portion of the link file, passing to the file system at least one request that corresponds to the unallocated portion to read from a file in a common store, passing to the file system at least one request that corresponds to the allocated portion to read from the link file, receiving data from the file system in response to each request passed thereto, merging the data from each read request into merged data, and returning the merged data in response to the request to read from the link file.

21. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the steps of, receiving a request to write data to the link file, and passing the request to the file system.

22. The method of claim 21 further comprising the steps of, associating a context with the link file, receiving status information from the file system indicative of a successful write to the link file, and recording in the context the location in the link file to which data was written.

23. The method of claim 21 further comprising the steps of, receiving status information from the file system indicative of a successful write to the link file, and closing the link file.

24. The method of claim 1 further comprising the steps of, receiving a request to close the link file, determining that the link file has data written thereto, reading data from the single instance corresponding to the link, merging the data with the data written to the link file as merged data, converting the link file to a converted file that is no longer linked to the single instance of data, including storing the merged data with the converted file, and closing the converted file.

25. The method of claim 24 wherein the step of converting the link file includes the step of removing a reference to the single instance from the converted file.

26. The method of claim 1 further comprising the steps of, receiving a request to close the link file, determining that the link file has data written thereto, attempting to allocate space in the link file for copying at least some data from the single instance thereto, and if not successful, closing the link file.

27. The method of claim 1 wherein the single instance of the data is maintained in a common store file, and further comprising the steps of, storing a backpointer in the common store file for each link file pointing thereto to identify that link file, receiving a request to delete a selected link file, deleting the backpointer in the common store file corresponding to that selected link file, and deleting the selected link file.

28. The method of claim 27 further comprising the steps of, determining if the step of deleting the backpointer in the common store file resulted in no remaining backpointers remaining in the common store file, and if so, deleting the common store file.

29. The method of claim 1 wherein the single instance of the data is maintained in a common store file of a volume, and further comprising the steps of, comparing each link file on the volume against each link pointer identified in a backpointer of a common store file, and if a selected backpointer does not correspond to a link file, deleting the backpointer.

30. The method of claim 1 wherein the single instance of the data is maintained in a common store file of a volume, and further comprising the steps of, comparing each link file on the volume against each link pointer identified in a backpointer of a common store file, and if a link file does not have a backpointer therefor in its corresponding common store file, adding a backpointer identifying that link file to its corresponding common store file.

31. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

32. In a computer system, a system for storing the data of files having at least some duplicate data, comprising, a non-volatile storage for storing data including files of a file system, and a facility for maintaining a single instance of the duplicate data as a common store file of the file system, the facility providing a logically separate link file to the common store file for each file having duplicate data and deallocating storage space that stores the duplicate data, each link file logically separate from each other link file such that file system actions associated with one link file do not affect the data accessible via another link file, and the facility handling input and output requests to each link file to manage the linking of the link file to the common store file.

33. The system of claim 32 wherein the facility comprises a filter driver which receives input and output requests directed to the file system.

34. The system of claim 32 wherein the facility maintains the common store file by copying the data from a source file to a file in a common store, and converts the source file to a link file.

35. The system of claim 32 wherein the link file has a reparse point associated therewith, the reparse point including information identifying the link file as associated with the facility and identifying the common store file pointed to by the link file.

36. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by intercepting each request to open the link file, and passing to the file system a request to open the common store file and the request to open the link file.

37. The system of claim 32 wherein the facility further includes a security mechanism for computing a signature, associating the signature with the link file, associating the signature with the common store file, and comparing the signature associated with the link file with the signature associated with the common store file.

38. The system of claim 32 further comprising a context associated with the link file.

39. The system of claim 32 wherein the facility stores a backpointer in the common store file for each link file pointing thereto to identify that link file.

40. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by intercepting each request to read from the link file, passing to the file system a request to read from the common store file, and returning the data read from the common store file in response to the request.

41. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by intercepting each request to read from the link file, determining that the request is to an allocated portion of the link file, and passing to the file system a request to read from the link file.

42. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by intercepting each request to read from the link file, determining that the request is directed to at least one allocated portion of the link file and at least one unallocated portion of the link file, passing to the file system at least one request that corresponds to the unallocated portion to read from the common store file, passing to the file system at least one request that corresponds to the allocated portion to read from the link file, receiving data from the file system in response to each request passed thereto, merging the data from each read request into merged data, and returning the merged data in response to the request to read from the link file.

43. The system of claim 32 further comprising a context associated with the link file, and wherein the facility manages the linking of the link file to the common store file by passing each request to write to the link file to the file system, receiving status information from the file system indicative of a successful write to the link file, and recording in the context the location in the link file to which data was written.

44. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by receiving a request to close the link file, passing the request to close the link file to the file system, and passing a request to close the common store file to the file system.

45. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by receiving a request to close the link file, determining that the link file has data written thereto, reading data from the single instance corresponding to the link, merging the data with the data written to the link file as merged data, converting the link file to a converted file that is no longer linked to the single instance of data, including storing the merged data with the converted file, and closing the converted file.

46. The system of claim 32 wherein the facility manages the linking of the link file to the common store file by receiving a request to close the link file, determining that the link file has data written thereto, attempting to allocate space in the link file for copying at least some data from the single instance thereto, and if not successful, closing the link file.

47. The system of claim 32 further comprising a backpointer stored in the common store file for each link file pointing thereto, and wherein the facility manages the linking of the link file to the common store file by receiving a request to delete a selected link file, deleting the backpointer in the common store file corresponding to that selected link file, deleting the selected link file, determining if the step of deleting the backpointer in the common store file resulted in no remaining backpointers remaining in the common store file, and if so, deleting the common store file.

48. The system of claim 32 wherein the link file and the common store file are stored in a volume of the file system, and further comprising a volume check procedure for comparing each link file on the volume against each link pointer identified in a backpointer of a common store file, and if a selected backpointer does not correspond to a link file, deleting the backpointer.

49. The system of claim 32 wherein the link file and the common store file are stored in a volume of the file system, and further comprising a volume check procedure for comparing each link file on the volume against each link pointer identified in a backpointer of a common store file, and if a link file does not have a backpointer therefor in its corresponding common store file, adding a backpointer identifying that link file to its corresponding common store file.

50. In a computer system having a file system, a method of storing the data of a selected plurality of files of the file system, wherein each of the selected plurality of files have at least partially identical contents with one another, comprising the steps of, maintaining a single instance file representing at least part of the file contents that are partially identical in each of the plurality of files, reclaiming at least some of the storage space that was identical in the selected plurality of files and providing a link file to the single instance file for each file having contents represented thereby, each link file logically separate from one another.

51. The method of claim 50 wherein the selected plurality of files of the file system comprise two files having identical contents.

52. The method of claim 50 wherein the single instance file maintains the entire identical contents.

53. The method of claim 50 wherein the single instance file is maintained in a common store with at least one other single instance file.

54. The method of claim 50 further comprising the steps of, receiving a request to open the link file, passing to the file system a request to open the single instance file, and passing to the file system a request to open the link file.

55. The method of claim 50 further comprising the step of, storing a backpointer in association with the single instance file for each link pointing thereto.

56. The method of claim 50 further comprising the steps of, receiving a request to read from the link file, passing to the file system a request to read from the single instance file, receiving data read from the single instance file, and returning the data read from the single instance file in response to the request to read from the link file.

57. The method of claim 50 further comprising the steps of, receiving a request to read from the link file, determining that the request is directed to at least one allocated portion of the link file and at least one unallocated portion of the link file, passing to the file system at least one request that corresponds to the unallocated portion to read from the single instance file, passing to the file system at least one request that corresponds to the allocated portion to read from the link file, receiving data from the file system in response to each request passed thereto, merging the data from each read request into merged data, and returning the merged data in response to the request to read from the link file.

58. The method of claim 50 further comprising the steps of, associating a context with the link file, receiving a request to write data to the link file, passing the request to the file system, receiving status information from the file system indicative of a successful write to the link file, and recording in the context the location in the link file to which data was written.

59. The method of claim 50 further comprising the steps of, receiving a request to close the link file, determining that the link file has data written thereto, reading data from the single instance file corresponding to the link, merging the data with the data written to the link file as merged data, converting the link file to a converted file that is no longer linked to the single instance file, including storing the merged data with the converted file, and closing the converted file.

60. A computer-readable medium having computer-executable instructions for performing the method of claim 50.

61. In a computer system having a file system of files, a method of storing the data of files having at least some duplicated data, comprising, maintaining a single instance of the data, for each file having duplicated data, providing a link file to the single instance of the data representing each file, each link file logically separate from each other link file, opening the link file, and associating a context with the link file.

62. The method of claim 61 wherein the single instance of the data is maintained in a common store file, and further comprising, receiving a request to write data to the link file, and passing the request to the file system.

63. The method of claim 62 further comprising, receiving status information from the file system indicative of a successful write to the link file, and recording in the context the location in the link file to which data was written.

64. The method of claim 62 further comprising, receiving status information from the file system indicative of a successful write to the link file, and closing the link file.

65. The method of claim 61 further comprising, receiving a request to close the link file, determining that the link file has data written thereto, reading data from the single instance corresponding to the link, merging the data with the data written to the link file as merged data, converting the link file to a converted file that is no longer linked to the single instance of data, including storing the merged data with the converted file, and closing the converted file.

66. The method of claim 61 further comprising, receiving a request to read from the link file, determining that the request is to an allocated portion of the link file, including evaluating information in the context, and passing to the file system a request to read from the link file.

67. A computer-readable medium having computer-executable instructions for performing the method of claim 61.

68. In a computer system having a file system of files, a method of storing the data of files having at least some duplicated data, comprising, maintaining a single instance of the data, for each file having duplicated data, providing a link to the single instance of the data representing each file, each link logically separate from each other link, and associating a reparse point with the file.

69. The method of claim 68 wherein the reparse point includes a reparse tag and reparse data.

70. The method of claim 69 further comprising the steps of computing a signature using the data of the source file, and storing the signature with the reparse data.

71. In a computer system, a system for storing the data of files having at least some duplicate data, comprising, a non-volatile storage for storing data including files of a file system, and a facility for maintaining a single instance of the duplicate data as a common store file of the file system, the facility providing a logically separate link file to the common store file for each file having duplicate data, each link file having a reparse point associated therewith, the reparse point including information identifying the link file as associated with the facility and identifying the common store file pointed to by the link file, and the facility handling input and output requests to each link file to manage the linking of the link file to the common store file.

72. In a computer system, a system for storing the data of files having at least some duplicate data, comprising, a non-volatile storage for storing data including files of a file system, a facility for maintaining a single instance of the duplicate data as a common store file of the file system, the facility providing a logically separate link file to the common store file for each file having duplicate data, the facility handling input and output requests to each link file to manage the linking of the link file to the common store file, and a context associated with the link file.

73. The system of claim 72 wherein the facility manages the linking of the link file to the common store file by passing each request to write to the link file to the file system, receiving status information from the file system indicative of a successful write to the link file, and recording in the context the location in the link file to which data was written.

74. In a computer system having a file system, a method of storing the data of a selected plurality of files of the file system, wherein each of the selected plurality of files have at least partially identical contents with one another, comprising the steps of, maintaining a single instance file representing at least part of the file contents that are partially identical in each of the plurality of files, providing a link to the single instance file for each file having contents represented thereby, each link logically separate from one another, and associating a context with at least one link.

75. A computer-readable medium having computer-executable instructions for performing the method of claim 74.