Efficient file hash identifier computation

• US 20090089337A1
• Filed: 10/01/2007
• Published: 04/02/2009
• Est. Priority Date: 10/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Pudipeddi, Ravisankar V., Perlin, Eric C.
• Granted Patent: US 9,424,266 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 21/565 by checking file integrity
• CPC Class Codes: G06F 2221/2101 Auditing as a secondary aspect

Abstract

Described is maintaining cached hash values for files in association with state data for each file that represents the state of that file'"'"'s contents at the time of hashing. For example, in a journaling file system, the state data may comprise the update sequence number of the file in the journal and a journal identifier for that journal instance. A request for a hash value for a file is processed by determining whether a cached hash value is maintained for that file. If so, and the associated maintained state data matches current state data for the file, the file contents are unchanged since the last hash computation, whereby the cached hash value is returned in response to the request. Otherwise, a new hash value is computed for the file and returned, and cached for future use. Multiple types of hashes may be cached for a given file.

Claims

1. In a computing environment, a system comprising:

a hash data store, in which each file of a plurality of files has an entry in the hash data store including at least one hash value and state data representative of a state of the file'"'"'s contents at a hashing time corresponding to computing the at least one hash value for that file; and

a hash return mechanism coupled to the hash data store to process requests for hash values for files, including by accessing the hash data store upon receiving a request for a hash value for a file to locate an entry for that file in the hash data store, by evaluating the state data associated with that file against current state data of the file to determine from the evaluation whether the file contents are unchanged since the hashing time, and if unchanged, by returning a hash value from the hash data store for that file in response to the request.

2. The system of claim 1 wherein the hash data store comprises a set of records, one record for each file, wherein the state data representative of the state of the file'"'"'s contents at the hashing time is maintained in one or more fields of a record for the file, including an update number corresponding to a logged update in a file system journal, and wherein the current state data of the file includes another update number corresponding to a last file update.

3. The system of claim 2 wherein the update number in the field does not equal the other update number corresponding to the last file update, wherein the state data includes a set of one or more updates in the journal corresponding to the file, and wherein the hash return mechanism includes means for scanning the set to determine whether any update is of a type that modified the file contents, and if not, the hash return mechanism returning a hash value from the hash data store for that file in response to the request.

4. The system of claim 2 wherein the state data further comprises a journal identification number corresponding to an instance of the journal, and wherein the current state data of the file includes another journal identification number corresponding to a current file system instance of the journal.

5. The system of claim 1 wherein the hash return mechanism accesses the hash data store to locate the entry via a file identifier used as a key.

6. The system of claim 1 wherein the hash return mechanism accesses the hash data store to locate the entry via a volume identifier and a file identifier used as keys.

7. The system of claim 1 further comprising a mechanism that builds or updates, or both builds and updates, the hash data store.

8. A computer-readable medium having computer-executable instructions, which when executed perform steps, comprising:

a) maintaining cached hash values for files in association with maintained state data for each file representative of a state of that file'"'"'s contents at a time of computing the hash value;

b) processing a request for a hash value for a file by determining whether a cached hash value is maintained for that file, and if not maintained for that file, advancing to step d);

c) determining from the maintained state data for that file and information associated with a current state of the file whether the file contents are unchanged since the time of the hash computation, and if the information associated with the current state of the file and the maintained state data indicate the file contents are unchanged since the time of the hash computation, selecting as a selected hash value the cached hash value for that file and advancing to step e);

d) computing a hash value for the file and selecting as a selected hash value the computed hash value; and

e) returning the selected hash value in response to the request.

9. The computer-readable medium of claim 8 wherein processing the request determines that no cached hash value is maintained for that file, and having further computer-executable instructions comprising, creating a set of information that maintains a cached hash value for that file in association with state data representative of the state of that file'"'"'s contents at the time of computing the hash value in step d).

10. The computer-readable medium of claim 8 wherein the maintained state data for the file and the information associated with the current state of the file determines that the file contents are possibly changed, and having further computer-executable instructions comprising, updating the cached hash value for that file and the associated state data representative of the state of that file'"'"'s contents for that file at the time of computing the hash value in step d).

11. The computer-readable medium of claim 8 wherein multiple hash values are maintained for the file, and wherein processing the request for the hash value includes determining whether a cached hash value of a particular type associated with the request is maintained for that file.

12. The computer-readable medium of claim 8 wherein the maintained state data includes an update number corresponding to a logged update in a file system journal for that file and a journal identification number corresponding to an instance of the journal when the update was logged, and wherein determining from the maintained state data and the information associated with the current state of the file comprises evaluating the update number and journal identifier maintained in association with the hash value against an update number maintained with the file and a current journal identifier.

13. The computer-readable medium of claim 8 wherein the file contents are unchanged if the maintained update number and journal identifier are equivalent to the update number maintained with the file and the current journal identifier, and wherein if the update numbers are different and the journal identifiers are equivalent or the update numbers indicate the journal has not wrapped, the step of determining from the maintained state data includes further computer-executable instructions, comprising, scanning one or more updates corresponding to logged updates between the update numbers to determine whether any update is of a type that modified the file contents, and if not, considering the file contents as unchanged.

14. The computer-readable medium of claim 13 wherein if the scanning step results in the file contents being considered unchanged, having further computer-executable instructions, comprising, updating the maintained update number associated with the cached hash value.

15. The computer-readable medium of claim 8 wherein the file contents are unchanged if the maintained update number and journal identifier are equivalent to the update number maintained with the file and the current journal identifier, and wherein if the update numbers are different and the journal identifiers are equivalent or the update numbers indicate the journal has not wrapped, the step of determining from the maintained state data includes further computer-executable instructions, comprising, evaluating whether a file size maintained with the hash value is equivalent to a current file size, and if not, considering the file as not unchanged and advancing to step d), and if the file sizes are equivalent, scanning one or more updates corresponding to logged updates between the update numbers to determine whether any update is of a type that modified the file contents, and if not, considering the file contents as unchanged.

16. The computer-readable medium of claim 8 wherein the file contents are unchanged if the maintained update number and journal identifier are equivalent to the update number maintained with the file and the current journal identifier, and wherein if the update numbers are different and the journal identifiers are equivalent, the step of determining from the maintained state data includes further computer-executable instructions, comprising, determining from the update numbers whether the difference between the update numbers exceeds a threshold and indicate the journal has not wrapped, and if so, considering the file contents as not unchanged and advancing to step d) regardless of whether the file contents are actually changed, and if the threshold is not exceeded, scanning one or more updates corresponding to logged updates between the update numbers to determine whether any update is of a type that modified the file contents, and if not, considering the file contents as unchanged.

17. In a computing environment in which a file system maintains a journal of changes to files, each change associated with an update sequence number, a method comprising:

a) maintaining a record for a file, the record including a hash set of at least one computed hash value for the file'"'"'s contents and a set of file-related data at a time that the hash set was computed for the file, the file related-data including the update sequence number of the file and a journal identifier that identifies an instance of the journal;

b) processing a request for a hash value for that file by comparing the update sequence number and the journal identifier maintained with the hash set against an actual update sequence number associated with the file and a current journal identifier, respectively, and if the comparison indicates the update sequence numbers and journal identifiers are equivalent, returning a hash value from the hash set in response to the request.

18. The method of claim 17 wherein the update sequence numbers or journal identifiers, or both, are not respectively equivalent to one another, and further comprising, re-computing at least part of the hash set for the file including a hash value to return in response to the request, updating the record with the hash set, with a value corresponding to the actual update sequence number associated with the file, and with a value corresponding to the current journal identifier, and returning at least one hash value in response to the request.

19. The method of claim 17 wherein the update sequence numbers are not equivalent to one another and the journal has not wrapped, and further comprising, comparing whether a file size maintained with the hash value is equivalent to a current file size, and if so, scanning one or more updates corresponding to logged updates between the update sequence numbers to determine whether any update is of a modifying type that modified the file contents, and if no such type of modifying update exists, returning a hash value from the hash set in response to the request.

20. The method of claim 17 further comprising, building the record for the file prior to processing any request for a hash value for that file.