Native data signatures in a file system

• US 5,978,814 A
• Filed: 01/21/1998
• Issued: 11/02/1999
• Est. Priority Date: 01/21/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, Thomas J., Cabrera, Luis Felipe
• Primary Examiner(s): Choules, Jack M.
• Application Number:
  US09/010,097
• Time in Patent Office: 650 Days
• Field of Search: 707/203
• US Class Current: 707/758
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

The present invention provides reliable systems and methods for rapidly determining whether file data streams are the same, or different, without having to make a comparison between the actual data streams. If the determination is made that the data streams are different, the present invention can rapidly determine where the changes between the data streams occur, again, without having to actually compare the entire size of the data streams. Such methods and systems are accomplished by generating a native data signature (NDS) for each data stream stored by the file system, wherein each NDS is substantially smaller in size as compared to the data stream corresponding thereto. The NDS is generated by separating the data stream into a plurality of allocation units, ranging in size from 4K bytes to 256K bytes; by generating a unique change identifier (UCI), one per each allocation unit; and by assembling the UCIs into a series of bits, typically ranging up to, and including, 64 in number. Thus, even with a UCI having 64 bits, time efficiency for comparing data streams by comparing between NDSs is improved on the order of 500:1 or 32,000:1, depending upon the size of the allocation unit.

Claims

1. In a file system of a computer operating system, a method for comparing data streams, comprising the steps of:

generating, for a first data stream, a first data signature including a plurality of first unique change identifiers, said first data stream being separated into a plurality of first allocation units, with each of said first unique change identifiers being associated with a different one of said first allocation units;

generating, for a second data stream, a second data signature including a plurality of second unique change identifiers, said second data stream being separated into a plurality of second allocation units, with each of said second unique change identifiers being associated with a different one of said second allocation units; and

comparing said first data signature and said second data signature to determine whether said first data stream and said second data stream are the same.

2. A method for comparing data streams as recited in claim 1, wherein the step of generating the first data signature comprises the steps of:

separating each first data stream into said plurality of first allocation units;

generating said plurality of first unique change identifiers, one first unique change identifier per first allocation unit; and

assembling the first unique change identifiers into the first data signature.

3. A method for comparing data streams as recited in claim 2, wherein the step of generating said plurality of first unique change identifiers is conducted using a monotonically increasing means for assigning one of said first unique change identifiers to each of the first allocation units.

4. A method for comparing data streams as recited in claim 2, further comprising the step of creating said second data stream by changing said first data stream, wherein the step of generating the second data signature comprises the steps of:

generating said plurality of second unique change identifiers, said plurality of second unique change identifiers including;

at least one second unique change identifier that is the same as a corresponding one of the plurality of first unique change identifiers, each of said at least one second unique change identifier being associated with one of the second allocation units that has not changed with respect to a corresponding one of the first allocation units; and

at least one new unique change identifier, each of said at least one new unique change identifier being associated with a second allocation unit that includes changed data with respect to the first data stream; and

assembling said plurality of second change identifiers into said second data signature.

5. A method for comparing data streams as recited in claim 2, wherein the step of generating said plurality of first unique change identifiers comprises the step of stamping the first data stream with a monotonically increasing means when the first data stream is stored to a disk.

6. A method for comparing data streams as recited in claim 2, wherein each of the first unique change identifiers and each of the second unique change identifiers have a size no greater than 64 bits.

7. A method for comparing data streams as recited in claim 2, wherein each of the first allocation units and each of the second allocation units have a size in a range from 4K bytes to 256K bytes.

8. A method for comparing data streams recited in claim 1, wherein the step of generating the first data signature comprises the step of generating said plurality of first unique change identifiers by combining an identifier which uniquely identifies a computer with a locally generated counter.

9. A method for comparing data streams in a file system of a computer operating system, comprising:

generating a first signature for a first data stream by;

(i) separating the first data stream into a plurality of first allocation units;

(ii) tagging each of the first allocation units with a first unique change identifier; and

(iii) assembling each of the first unique change identifiers into the first signature;

generating a second signature for a second data stream, the second data signature including a plurality of second unique change identifiers, the second data stream being separated into a plurality of second allocation units, with each of the second unique change identifiers being associated with a different one of the second allocation units; and

comparing the first and second signatures to determine whether the first and second data streams are identical, including the step of comparing the first unique change identifiers and the second unique change identifiers.

10. A method for comparing data streams as recited in claim 9, wherein the second data stream is the first data stream having changed data, the step of generating the second signature for the second data stream comprising the steps of:

determining which of the second allocation units corresponds to the changed data;

assigning an updated unique change identifier to each of the second allocation units corresponding to the changed data; and

altering the first signature by replacing each of the first unique change identifiers that correspond to the second allocation units corresponding to the changed data with the corresponding updated unique change identifier to form the second signature.

11. A method for comparing data streams as recited in claim 10, further comprising the step of storing a first signature attribute that represents the first signature and a second signature attribute that represents the second signature in a first file and a second file, respectively, through operation of the file system.

12. A method for comparing data streams as recited in claim 11, wherein the step of comparing the first and second signatures comprises the step of comparing the first and second signature attributes.

13. A method for comparing data streams as recited in claim 12, wherein the step of comparing the first and second signature attributes comprises the step of comparing the first and second files.

14. A method for comparing data streams as recited in claim 9 wherein each of said first unique change identifiers comprises an identifier of an entity that created said first change identifiers.

15. A computer readable medium having computer executable instructions, said computer-executable instructions comprising:

means for separating said first data stream into a plurality of first allocation units;

means for generating a plurality of first unique change identifiers, one first unique change identifier per first allocation unit;

means for assembling said plurality of first unique change identifiers into a first signature corresponding to said first data stream, said first signature including said plurality of first unique change identifiers;

means for generating a second signature corresponding to a second data stream, said second signature including a plurality of second change identifiers, each of said second change identifiers being associated with a different one of a plurality of second allocation units into which said second data stream is separated; and

means for comparing said first signature and said second signature in order to determine whether said first and second data streams are the same.

16. A computer readable medium as recited in claim 15, wherein said computer-executable instructions further comprise means for determining an appropriate size for said first allocation units.

17. A computer readable medium as recited in claim 15, wherein said computer-executable instructions further comprise means for assembling said first and second signatures into first and second signature attributes, respectively, in order to store said first and second signature attributes in a first and second file, respectively, said first and second files having said first and second data streams stored therein, respectively.

18. A computer readable medium as recited in claim 15, wherein said second data stream is said first data stream having changed data therein, said means for generating said second signature corresponding to said second data stream further comprising means for replacing at least some of said fist unique change identifiers in said first signature with updated unique change identifiers in order to form said second signature.

19. A computer program product comprising computer-readable medium having stored thereon computer-executable instructions, said computer-executable instructions including:

means for generating;

for a first data stream, a first data signature including a plurality of first unique change identifiers, said first data stream being separated into a plurality of first allocation units, with each of said first unique change identifiers being associated with a different one of said first allocation units; and

for a second data stream, a second data signature including a plurality of second unique change identifiers, said second data stream being separated into a plurality of second allocation units, with each of said second unique change identifiers being associated with a different one of said second allocation units; and

means for comparing said first data signature and said second data signature to determine whether said first data stream and said second data stream are the same.

20. A computer program product as recited in claim 19, wherein the means for generating the first signature comprises:

means for separating said first data stream into said plurality of first allocation units;

means for generating said plurality of first unique change identifiers, one first unique change identifier per first allocation unit; and

means for assembling the first unique change identifiers into the first data signature.

21. A computer program product as recited in claim 20, wherein the means for generating said plurality of first unique change identifiers comprises monotonically increasing means of assigning one of said first unique change identifiers to each of the first allocation units.

22. A computer program product as recited in claim 20, wherein said second data stream is said first data stream having changed data therein, wherein the means for generating the second data stream comprises:

means for generating said plurality of second unique change identifiers, said plurality of second unique change identifiers including;

at least one second unique change identifier that is the same as a corresponding one of the plurality of first unique change identifiers, each of said at least one second unique change identifier being associated with one of the second allocation units that has not changed with respect to a corresponding one of the first allocation units; and

at least one new unique change identifier, each of said at least one new unique change identifier being associated with a second allocation unit that includes changed data with respect to the first data stream; and

means for assembling said plurality of second change identifiers into said second data signature.

23. A computer program product as recited in claim 20, wherein the means for generating said plurality of first unique change identifiers comprises means for stamping the first data stream with a monotonically increasing means when the first data stream is stored to a disk.