Locating potentially identical objects across multiple computers

• US 20030037022A1
• Filed: 06/06/2001
• Published: 02/20/2003
• Est. Priority Date: 06/06/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Theimer, Marvin M., Bolosky, William J., Douceur, John R., Adya, Atul
• Granted Patent: US 7,310,644 B2
• Time in Patent Office: Days
• US Class Current: 707/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 system comprising:

a plurality of client computers;

a plurality of database server computers;

wherein each of the plurality of client computers is configured to generate object information for each of a plurality of objects stored on the client; and

wherein each of the plurality of servers is configured to receive object information generated by one or more of the plurality of client computers, wherein each of the plurality of server computers is further configured to compare the object information it receives from different client computers and identify whether any of the received object information matches other of the received object information.

2. A system as recited in claim 1, wherein a computer in the system is concurrently both one of the plurality of client computers and one of the plurality of database server computers.

3. A system as recited in claim 1, wherein the system uses a serverless distributed file system.

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

5. A system as recited in claim 1, wherein the file information for a file is based at least in part on one or more characteristics of the file.

6. A system as recited in claim 1, wherein the object information comprises file information.

7. A system as recited in claim 1, wherein each of the plurality of clients is further configured to communicate the file information it generates to one or more of the plurality of server computers.

8. A system as recited in claim 1, wherein one or more of the plurality of server computers is further configured to forward the file information it receives to one or more other server computers of the plurality of server computers.

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

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

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

generating object information for an object at the computer; and

transferring the object information to a database server computer, wherein the object information is to be compared to object information from one or more other computers to determine whether the object is potentially identical to another object on one of the one or more other computers.

10. A method as recited in claim 9, wherein the object information comprises file information and wherein the object comprises a file.

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

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

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

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

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

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

15. A method as recited in claim 9, 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 object information is to be transferred.

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

determining a value based on the object information; and

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

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

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

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

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

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

20. A method as recited in claim 19, wherein the one or more characteristics include an object type.

21. A method as recited in claim 19, wherein the one or more characteristics include an object size.

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

receiving object information corresponding to another object;

comparing the received object information to an object information database;

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

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

23. A method as recited in claim 9, wherein the generating comprises generating object information for all objects stored at the computer.

24. A method as recited in claim 9, wherein the generating comprises generating object information for all objects stored at the computer that satisfy certain criteria.

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

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

27. A method as recited in claim 26, further comprising associating, with the generated object information, a time to live component that identifies a number of additional database server computers to which the object information can be communicated.

28. A method as recited in claim 9, wherein the transferring comprises transferring, to the database server computer, the object information for a plurality of objects stored at the computer.

29. A method as recited in claim 9, wherein the transferring comprises transferring, to the database server computer, the object information after the computer becomes aware of the database server computer.

30. 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; and

a forwarding location determination module, coupled to the file information generation module, to identify one or more database server computers to which the generated file information is to be communicated.

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

receiving object information from a computer;

comparing the object information to other object information, received from one or more other computers, corresponding to other objects; and

determining that an object corresponding to the received object information is potentially identical to one of the other objects if the received object information is the same as any of the other object information.

32. A method as recited in claim 31, wherein the object information comprises file information.

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

34. A method as recited in claim 31, wherein the object information is based at least in part on one or more characteristics of the object.

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

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

communicating the received object information to one or more other database server computers.

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

communicating the received object information to one or more other database server computers only if a time to live component associated with the received object information indicates the object information can be communicated to at least one more database server computer.

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

generating object information corresponding to an object stored at the database server computer; and

communicating the generated object information to another database server computer.

40. A system comprising:

a storage device to store a file information database; and

a file information comparison module coupled to access the file information database, wherein the file information comparison module is configured to receive file information corresponding to a file stored at another system, to compare the received file information to the file information in the database, and determine whether the received file information matches any of the file information in the database.

41. A method comprising:

receiving, from each of a plurality of computers, object information for a plurality of objects; and

comparing the received object information to determine whether any of the received object information corresponds to an object that is potentially identical to another object.

42. A method as recited in claim 41, wherein the receiving comprises receiving, from each of the plurality of computers, object information for a plurality of objects stored at the computer.

43. A method as recited in claim 41, wherein the object information comprises file information.

44. 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 a semi-unique value based at least in part on the data in the file;

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; and

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.

45. A method as recited in claim 44, further comprising:

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

46. A method as recited in claim 44, further comprising:

transferring, to a 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.

47. A method as recited in claim 44, further comprising:

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.

48. A method as recited in claim 47, further comprising:

maintaining a time to live component corresponding to one or more of the received file information; and

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.

49. A method as recited in claim 44, further comprising:

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

50. 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; and

a forwarding location determination module, coupled to the file information generation module, to identify one or more other systems to which all of the generated file information is to be communicated.

51. A system as recited in claim 50, 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.

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

53. A system as recited in claim 50, 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.

54. A system as recited in claim 50, 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.

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

56. A system as recited in claim 50, 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.

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

58. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, causes the one or more processors to perform the following acts:

generating, for each of a plurality of files on the computer, file information for the file; and

communicating the file information for the plurality of files to another computer after the computer becomes aware of the other computer.

59. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of one computer of a plurality of computers in a network, causes the one or more processors to perform the following acts:

receiving, from each of the other computers in the network, file information corresponding to a file stored at the computer; and

comparing the received file information to determine whether any of the file information matches any other file information and thus indicates files that are potentially identical to each other.

60. One or more computer-readable media as recited in claim 59, wherein the receiving comprises receiving, from each of the other computers in the network, only file information that satisfies certain criteria.

61. One or more computer-readable media as recited in claim 59, wherein the receiving comprises receiving, from each of the other computers in the network, only file information that, when the calculation of the file information modulo a number of computers in the network that receive file information, results in a value associated with the one computer.

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

receiving generated file information for a file; and

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.

63. A method as recited in claim 62, wherein the receiving comprises receiving file information generated for the file by a module of the computer.

64. A method as recited in claim 62, 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.

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

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

67. A method as recited in claim 62, further comprising:

receiving file information corresponding to another file;

comparing the received file information to a file information database;

checking whether the received file information matches any of the file formation 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.