Locating potentially identical objects across multiple computers

• US 7,310,644 B2
• Filed: 06/06/2001
• Issued: 12/18/2007
• Est. Priority Date: 06/06/2001
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Theimer, Marvin M., Bolosky, William J., Douceur, John R., Adya, Atul
• Primary Examiner(s): Leroux; Etienne
• Application Number:
  US09/876,377
• Publication Number:
  US 20030037022A1
• Time in Patent Office: 2,386 Days
• Field of Search: 707/10, 707/202, 707/200, 707/203, 707/204, 707/1, 707/2, 707/201, 707/100, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641

Abstract

Potentially identical objects (such as files) across multiple computers are located. In one embodiment, a computer generates object information for an object stored on the computer. The object information can be generated in a variety of manners (e.g., based on hashing the object, based on characteristics of the object, and so forth). The object information is then transferred to one or more database server computers, where the object information can be compared to object information from other computers to determine whether the object is potentially identical to another object on one of the other computers.

Claims

1. A method, implemented in a computer, the method comprising:

generating file information for a file at the computer, wherein the file information is different from the file and based at least in part on data in the file, and wherein the generating comprises generating file information only for files stored at the computer that satisfy certain criteria;

transferring the file information to a database server computer, wherein the file information is to be compared to file information from one or more other computers to determine whether the file is potentially identical to another file on one of the one or more other computers, wherein said transferring does not transfer the file associated with said file information;

associating, with the generated file information, a time to live component that identifies to how many additional database server computers the file information can be communicated, wherein the time to live component limits the number of additional database server computers to which the file information can be communicated; and

causing removal, from at least one computer, of one or more files determined to be identical to another file and causing a pointer to said another file to be set up in place of removed files.

2. A method as recited in claim 1, wherein the transferring comprises transferring the file information to a plurality of database server computers, wherein the file information is to be compared at each of the plurality of database server computers to file information received from one or more other computers to determine whether the file is potentially identical to another file on one of the one or more other computers.

3. A method as recited in claim 1, wherein the computer is part of one of a plurality of groups, and wherein the transferring comprises transferring the file information to a database server computer in the one group.

4. A method as recited in claim 1, further comprising:

accessing a root computer to determine the database server computer to which the file information is to be transferred.

5. A method as recited in claim 1, further comprising:

accessing one or more of a plurality of root computers to determine the database server computer to which the file information is to be transferred.

6. A method as recited in claim 1, further comprising:

identifying, by communicating with at least one of the one or more other computers, another computer; and

accessing the identified computer to determine the database server computer to which the file information is to be transferred.

7. A method as recited in claim 1, further comprising:

determining a value based on the file information; and

using the value to determine the database server computer to which the file information is to be transferred.

8. A method as recited in claim 1, wherein the computer is part of one of a plurality of groups, wherein a plurality of database server computers are in the one group, and wherein the method further comprises:

determining a value based on the file information, wherein the value is determined by performing the calculation of the file information modulo the number of database servers in the one group; and

using, as the database server computer to which the file information is to be transferred, the database server corresponding to the determined value.

9. A method as recited in claim 1, further comprising:

receiving file information corresponding to another file;

comparing the received file information to file information database;

checking whether the received file information matches any of the file information in the database; and

determining that two potentially identical files exist if the received file information matches any of the file information in the database.

10. A method as recited in claim 1, wherein the certain criteria comprise a threshold size.

11. A method as recited in claim 1, wherein the file information can further be communicated from the database server computer to one or more additional database server computers.

12. A method as recited in claim 1, wherein the transferring comprises transferring, to the database server computer, the file information for a plurality of files stored at the computer.

13. A method as recited in claim 1, wherein the transferring comprises transferring, to the database server computer, the file information after the computer becomes aware of the database server computer.

14. A method as recited in claim 1, wherein the file information is a semi-unique value based at least in part on the data in the file.

15. A method as recited in claim 1, wherein the file information is based at least in part on one or more characteristics of the file.

16. A method as recited in claim 15, wherein the one or more characteristics include a file type.

17. A method as recited in claim 15, wherein the one or more characteristics include a file size.

18. A method, implemented in a database server computer, comprising:

receiving file information from a computer only for files stored at the computer that satisfy certain criteria, wherein said file information is different from the files and based on a hash value which is based, at least in part, on convergent encryption, wherein the file information does not comprise the files themselves;

comparing the file information to other file information, received from one or more other computers, corresponding to other files;

determining that a file corresponding to the received file information is potentially identical to one of the other files if the received file information is the same as any of the other file information; and

communicating the received file information to one or more other database server computers only if a time to live component associated with the received information indicates the file information can be communicated to at least one more database server computer, wherein the time to live component identifies to how many additional database server computers the received file information can be communicated, and wherein the time to live component limits the number of additional database server computers to which the received file information can be communicated.

19. A method as recited in claim 18, wherein the computer, the database server computer, and the one or more other computers are all part of the same group of computers.

20. A method as recited in claim 18, wherein the database server computer is part of one of a plurality of groups of computers, and wherein the method further comprises:

communicating the file information to a database server computer in another group of the plurality of groups of computers.

21. A method as recited in claim 18, further comprising:

generating file information corresponding to a file stored at the database server computer; and

communicating the generated file information to another database server computer.

22. A method as recited in claim 18, wherein the file information is a semi-unique value based at least in part on the data in the file corresponding to the file information.

23. A method as recited in claim 18, wherein the file information is based at least in part on one or more characteristics of the file.

24. A system comprising:

a storage device to store a plurality of files;

a file information generation module to generate file information for one or more of the plurality of files, wherein said file information is different from the one or more of the plurality of files and based on a hash value which is based, at least in part, on convergent encryption, and wherein the file information does not comprise the files themselves; and

a forwarding location determination module, coupled to the file information generation module, to determine one or more other systems to which all of the generated file information is to be communicated, wherein the forwarding location determination module is further to associate a time to live component with each generated file information, the time to live component identifying to how many other systems the generated file information can be communicated, and wherein the time to live component limits the number of other systems to which the generated file information can be communicated.

25. A system as recited in claim 24, wherein the forwarding location module is further to associate the same time to live component with all of the generated file information.

26. A system as recited in claim 24, wherein the forwarding location determination module is to identify another system as a system to which all of the generated file information is to be communicated after the system becomes aware of the other system.

27. A system as recited in claim 24, wherein the forwarding location determination module is to identify another system as a system to which all of the generated file information is to be communicated if the other system satisfies particular criteria.

28. A system as recited in claim 27, wherein the other system satisfies the particular criteria if the other system is within a particular range of the system.

29. A system as recited in claim 24, further comprising a file information comparison module to receive file information from one of the one or more other systems and compare the received file information to the generated file information to determine whether any of the received file information matches any of the generated file information.

30. A system as recited in claim 24, wherein the file information generation module is to generate file information for only those files of the plurality of files that satisfy certain criteria.

31. A method, implemented in a computer, the method comprising:

generating, for each of a plurality of files stored at the computer, file information, wherein the file information is different than the plurality of files and is a semi-unique value based at least in part on the data in the file, wherein the file information does not comprise the files themselves;

receiving, from another computer, a plurality of file information corresponding to a plurality of files stored at the other computer;

comparing the received file information to the generated file information;

determining that a file on the computer is potentially identical to a file on the other computer if any of the received file information match any of the generated file information;

transferring the received file information to a third computer, wherein the received file information is to be compared, at the third computer, to file information corresponding to files stored at the third computer;

maintaining a time to live component corresponding to one or more of the received file information, wherein the time to live component limits the number of computers to which the received file information can be communicated;

wherein the transferring the received file information to the third computer comprises transferring the one or more of the received file information to the third computer only if the time to live component exceeds a threshold amount; and

causing removal, from at least one computer, of one or more files determined to be identical to another file and causing a pointer to said another file to be set up in place of removed files.

32. A method as recited in claim 31, further comprising:

transferring, to the third computer, both the generated file information and the received file information, wherein both the generated file information and the received file information are to be compared, at the third computer, to file information corresponding to files stored at the third computer.

33. A method as recited in claim 31, further comprising:

maintaining both the generated file information and the received file information in a database at the computer.