US6477544B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Single instance store for file systems
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1999-07-16
•
Granted: 2002-11-05
•
Expires: 2019-07-16
Abstract
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.
Inventors
- 👤 William J. Bolosky
- 👤 John R. Douceur
- 👤 Scott M. Cutshall
- 👤 Richard F. Rashid
- 👤 Nathan P. Myhrvold
- 👤 David A. Goebel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 20:35
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; G06F16/17; G06F16/174; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 81
Claim 1
Independent Claim
114 words
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.
Claim 2
Dependent Claim
34 words
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.
Claim 3
Dependent Claim
25 words
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.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
31 words
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.
Claim 6
Dependent Claim
28 words
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.
Claim 7
Dependent Claim
24 words
The method of claim 5 wherein the information further includes data for identifying the single instance of data pointed to by the link file.
Claim 8
Dependent Claim
16 words
The method of claim 6 wherein the reparse point includes a reparse tag and reparse data.
Claim 9
Dependent Claim
28 words
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.
Claim 10
Dependent Claim
18 words
The method of claim 1 further comprising the step of receiving a request to open the link file.
Claim 11
Dependent Claim
47 words
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.
Claim 12
Dependent Claim
22 words
The method of claim 11 further comprising the step of passing to the file system a request to open the link file.
Claim 13
Dependent Claim
85 words
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.
Claim 14
Dependent Claim
22 words
The method of claim 1 further comprising the steps of, opening the link file, and associating a context with the link file.
Claim 15
Dependent Claim
38 words
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.
Claim 16
Dependent Claim
49 words
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.
Claim 17
Dependent Claim
39 words
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.
Claim 18
Dependent Claim
46 words
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.
Claim 19
Dependent Claim
44 words
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.
Claim 20
Dependent Claim
129 words
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.
Claim 21
Dependent Claim
43 words
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.
Claim 22
Dependent Claim
49 words
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.
Claim 23
Dependent Claim
31 words
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.
Claim 24
Dependent Claim
84 words
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.
Claim 25
Dependent Claim
28 words
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.
Claim 26
Dependent Claim
54 words
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.
Claim 27
Dependent Claim
73 words
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.
Claim 28
Dependent Claim
42 words
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.
Claim 29
Dependent Claim
63 words
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.
Claim 30
Dependent Claim
78 words
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.
Claim 31
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the method of claim 1 .
Claim 32
Dependent Claim
135 words
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.
Claim 33
Dependent Claim
135 words
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.
Claim 34
Dependent Claim
23 words
The system of claim 32 wherein the facility comprises a filter driver which receives input and output requests directed to the file system.
Claim 35
Dependent Claim
37 words
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.
Claim 36
Dependent Claim
41 words
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.
Claim 37
Dependent Claim
51 words
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.
Claim 38
Dependent Claim
50 words
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.
Claim 39
Dependent Claim
14 words
The system of claim 32 further comprising a context associated with the link file.
Claim 40
Dependent Claim
27 words
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.
Claim 41
Dependent Claim
59 words
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.
Claim 42
Dependent Claim
57 words
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.
Claim 43
Dependent Claim
138 words
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.
Claim 44
Dependent Claim
76 words
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.
Claim 45
Dependent Claim
55 words
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.
Claim 46
Dependent Claim
95 words
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.
Claim 47
Dependent Claim
65 words
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.
Claim 48
Dependent Claim
98 words
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.
Claim 49
Dependent Claim
66 words
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.
Claim 50
Dependent Claim
81 words
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.
Claim 51
Dependent Claim
111 words
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.
Claim 52
Dependent Claim
21 words
The method of claim 50 wherein the selected plurality of files of the file system comprise two files having identical contents.
Claim 53
Dependent Claim
15 words
The method of claim 50 wherein the single instance file maintains the entire identical contents.
Claim 54
Dependent Claim
24 words
The method of claim 50 wherein the single instance file is maintained in a common store with at least one other single instance file.
Claim 55
Dependent Claim
44 words
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.
Claim 56
Dependent Claim
25 words
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.
Claim 57
Dependent Claim
62 words
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.
Claim 58
Dependent Claim
127 words
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.
Claim 59
Dependent Claim
66 words
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.
Claim 60
Dependent Claim
84 words
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.
Claim 61
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the method of claim 50 .
Claim 62
Dependent Claim
74 words
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.
Claim 63
Dependent Claim
74 words
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.
Claim 64
Dependent Claim
40 words
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.
Claim 65
Dependent Claim
39 words
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.
Claim 66
Dependent Claim
28 words
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.
Claim 67
Dependent Claim
81 words
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.
Claim 68
Dependent Claim
49 words
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.
Claim 69
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the method of claim 61 .
Claim 70
Dependent Claim
67 words
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.
Claim 71
Dependent Claim
67 words
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.
Claim 72
Dependent Claim
16 words
The method of claim 68 wherein the reparse point includes a reparse tag and reparse data.
Claim 73
Dependent Claim
28 words
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.
Claim 74
Dependent Claim
131 words
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.
Claim 75
Dependent Claim
131 words
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.
Claim 76
Dependent Claim
102 words
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.
Claim 77
Dependent Claim
102 words
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.
Claim 78
Dependent Claim
66 words
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.
Claim 79
Dependent Claim
100 words
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.
Claim 80
Dependent Claim
100 words
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.
Claim 81
Dependent Claim
14 words
A computer-readable medium having computer-executable instructions for performing the method of claim 74 .
References Cited (Backward Citations)
US5410667A
Cited
EP0774715A1
Cited
US5778395A
Cited
US5778384A
Cited
US5706510A
Cited
US5907673A
Cited
US5918229A
Cited
US6185574B1
Cited
WO1999009480A1
Cited
WO1999012098A1
Cited
WO1999021082A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-11-04 | 2006-05-06 | 2006-11-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-11-04 | 2010-05-06 | 2010-11-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-11-04 | 2014-05-06 | 2014-11-05 | $7700.00 | Window Closed / Lapsed |