Locating potentially identical objects across multiple computers based on stochastic partitioning of workload

• US 20030037094A1
• 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 6,988,124 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• 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
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99946 Object-oriented database structure network
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Potentially identical objects (e.g., files) are located across multiple computers based on stochastic partitioning of workload. For each of a plurality of objects stored on a plurality of computers in a network, a portion of object information corresponding to the object is selected. 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). Any of a variety of portions of the object information can be used (e.g., the least significant bits of the object information). A stochastic partitioning process is then used to identify which of the plurality of computers to communicate the object information to for identification of potentially identical objects on the plurality of computers.

Claims

1. A method comprising:

selecting, for each of a plurality of objects stored on a plurality of computers in a network, a portion of object information corresponding to the object;

using a stochastic partitioning process to identify which of the plurality of computers to communicate the object information to for identification of potentially identical objects on the plurality of computers.

2. A method as recited in claim 1, wherein the object information comprises file information and wherein each of the plurality of objects comprises a file in a file system.

3. A method as recited in claim 1, wherein the stochastic partitioning process comprises a fully distributed stochastic partitioning process including:

comparing, for each of the plurality of computers, the selected portion to a portion of a computer identifier associated with the computer;

identifying which of the computer identifiers have portions matching the selected portion of the object information; and

communicating the object information to each of the computers associated with a computer identifier having a portion matching the selected portion of the object information.

4. A method as recited in claim 1, wherein the stochastic partitioning process comprises a group-based system using directory services process including:

accessing an object information portion to computer mapping on a remote computer; and

identifying one or more computers to receive the object information based at least in part on the accessed mapping.

5. A method as recited in claim 1, wherein the stochastic partitioning process comprises a multi-level stochastic partitioning process including:

grouping, into a plurality of groups, selected ones of the plurality of computers, wherein the grouping is based at least in part on the number of the plurality of computers in the network that the computer using the stochastic partitioning process is aware of; and

identifying which of the selected ones of the plurality of computers to communicate the object information to, wherein the identifying is based at least in part on comparing the selected portion of the object information to a portion of a computer identifier of one or more of the selected ones of the plurality of computers.

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

selecting a portion of file information corresponding to a file stored on one of the plurality of computers;

comparing, for each of the plurality of computers, the selected portion to a portion of a computer identifier associated with the computer;

identifying which of the computer identifiers have portions matching the selected portion of the file information; and

communicating, for identification of potentially identical files stored on the plurality of computers, the file information to each of the computers associated with a computer identifier having a portion matching the selected portion of the file information.

7. One or more computer-readable media as recited in claim 6, wherein the selected portion of the file information comprises a set of least significant bits of the file information.

8. One or more computer-readable media as recited in claim 6, wherein for each of the plurality of computers the portion of the computer identifier associated with the computer is a set of least significant bits of the computer identifier.

9. One or more computer-readable media as recited in claim 6, wherein the comparing includes comparing the selected portion to a portion of a computer identifier associated with the one computer.

10. One or more computer-readable media as recited in claim 6, wherein the selected portion of the file information includes a plurality of bits of the file information, wherein each portion of a computer identifier includes a plurality of bits of the computer identifier, and wherein the locations of the plurality of bits in the file information correspond to the locations of the plurality of bits of the computer identifiers.

11. One or more computer-readable media as recited in claim 6, further comprising:

receiving, from one of the plurality of computers, other file information;

comparing the received file information to a file information database stored at the computer; and

determining that a file corresponding to the received file information is potentially identical to another file on another of the plurality of computers if the received file information matches file information in the database.

12. One or more computer-readable media as recited in claim 6, wherein the file information is a semi-unique value based at least in part on the data in the file.

13. One or more computer-readable media as recited in claim 12, wherein the file information includes a hash value generated by applying a hash function to the file.

14. One or more computer-readable media as recited in claim 6, wherein the file information is based at least in part on one or more characteristics of the file.

15. One or more computer-readable media as recited in claim 14, wherein the characteristics include a file size and a file type.

16. One or more computer-readable media as recited in claim 6, wherein the communicating further comprises communicating a file identifier corresponding to the file along with the file information.

17. One or more computer-readable media as recited in claim 6, wherein the size of the portion of the file information is based at least in part on a count of computers that the one computer is aware of in the network.

18. One or more computer-readable media as recited in claim 6, wherein the size of the portion of the file information is based at least in part on an average number of computers that a particular file identifier should be communicated to.

19. One or more computer-readable media as recited in claim 6, further comprising:

determining a size of the portion of the file information;

wherein the size of the portion of the file information need not be the same as a size determined by others of the plurality of computers.

20. One or more computer-readable media as recited in claim 6, wherein a value W represents the size of the portion of the file information, wherein a value M represents a count of computers that the one computer is aware of in the network, wherein a value R is a system configuration value calculated based on an average number of computers that a particular file identifier should be communicated to, wherein 1 g is a base 2 logarithm function, wherein floor brackets indicate the largest integer that is no greater than the enclosed value, and wherein the value W is determined as follows:

21. One or more computer-readable media as recited in claim 6, further comprising repeating the selecting, comparing, identifying, and communicating for every file stored at the one computer.

22. One or more computer-readable media as recited in claim 6, further comprising repeating the selecting, comparing, identifying, and communicating for every file stored at the one computer that exceeds a threshold size.

23. A method comprising:

generating an imprint for an object stored at a computer, wherein the imprint comprises a first set of bits of object information corresponding to the object;

identifying one or more additional computers each having a computer identifier that includes a second set of bits that match the imprint; and

sending the object information to each of the identified one or more additional computers.

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

25. A method as recited in claim 23, wherein the first set of bits comprises the least significant bits of the object information, and wherein the second set of bits comprises the least significant bits of the computer identifier.

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

27. A method as recited in claim 23, wherein the communicating further comprises communicating an object identifier corresponding to the object along with the object information.

28. A method as recited in claim 23, further comprising storing the object information in an object information database stored at the computer.

29. A method as recited in claim 23, further comprising:

receiving object information corresponding to an object stored on another computer;

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.

30. A method as recited in claim 23, wherein the locations of the first set of bits correspond to the locations of the second set of bits.

31. A method as recited in claim 23, wherein the number of bits in the first set of bits is based at least in part on a count of computers that the computer is aware of in the network.

32. A method as recited in claim 23, wherein the number of bits in the first set of bits is based at least in part on an average number of computers that a particular object identifier should be communicated to.

33. A system comprising:

an interface configured to allow the system to communicate with a plurality of other computers; and

a forwarding location determination module, coupled to the interface, configured to identify one or more of the plurality of computers to communicate file information corresponding to a file to, for identification of potentially identical files in the system, by,

identifying a set of bits of file information associated with a file, and

identifying ones of the one or more computers that each have a computer identifier that has a set of bits that match the set of bits of the file information.

34. A system as recited in claim 33, wherein the number of bits in the set of bits is based at least in part on a count of computers coupled to the system that the system is aware of.

35. A system as recited in claim 33, wherein the number of bits in the set of bits is based at least in part on an average number of computers that a particular file identifier should be communicated to.

36. A system as recited in claim 33, further comprising a file information comparison module coupled to a file information database, wherein the file information comparison module is configured to,

receive, from one of the plurality of computers, other file information,

compare the received file information to file information in the database, and

determine that a file corresponding to the received file information is potentially identical to another file on another of the plurality of computers if the received file information matches file information in the database.

37. A method comprising:

identifying an imprint for an object stored at a computer, wherein the imprint is a set of bits of object information corresponding to the object;

accessing an imprint to computer mapping;

identifying one or more computers to receive the object information based at least in part on the accessed mapping; and

sending the object information to at least one of the identified one or more computers.

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

39. A method as recited in claim 37, wherein the one or more computers includes the computer at which the object is stored.

40. A method as recited in claim 37, wherein the accessing comprises accessing a locally stored imprint to computer mapping.

41. A method as recited in claim 37, wherein the accessing comprises accessing an imprint to computer mapping stored at another computer.

42. A method as recited in claim 37, wherein the identifying one or more computers comprises identifying one computer to receive the object information based at least in part on the accessed mapping, and wherein the sending comprises sending the object information to the one identified computer so that the one identified computer can forward the object information to one or more other computers responsible for maintaining the object information.

43. A method as recited in claim 37, wherein the imprint to computer mapping comprises an imprint to computer identifier mapping.

44. A method as recited in claim 37, wherein the sending comprises sending the object information to each of the identified one or more computers.

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

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

47. A method as recited in claim 37, wherein the size of the imprint is based at least in part on a count of other computers in a network coupled to the computer that the computer is aware of.

48. A method as recited in claim 37, wherein the size of the imprint is based at least in part on an average number of computers that a particular object identifier should be communicated to.

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

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

selecting a portion of file information corresponding to a file;

identifying a mapping of the portion to one or more computers; and

communicating the file information to each of the identified one or more computers for identification of potentially identical files on the one or more computers.

51. One or more computer-readable media as recited in claim 50, wherein the file information is a semi-unique value based at least in part on the data in the file.

52. One or more computer-readable media as recited in claim 50, wherein the file information is based at least in part on one or more characteristics of the file.

53. One or more computer-readable media as recited in claim 50, wherein the size of the portion of the file information is based at least in part on a count of the plurality of computers in the network that the one computer is aware of.

54. One or more computer-readable media as recited in claim 50, wherein the size of the portion of the file information is based at least in part on an average number of computers in the network that a particular file identifier should be communicated to.

55. One or more computer-readable media as recited in claim 50, wherein the identifying comprises identifying the mapping by accessing a locally stored imprint to computer mapping.

56. One or more computer-readable media as recited in claim 50, wherein the identifying comprises identifying the mapping by accessing an imprint to computer mapping stored at another computer.

57. A system comprising:

an interface configured to allow the system to communicate with a plurality of other computers; and

a forwarding location determination module, coupled to the interface, configured to identify one or more of the plurality of other computers to communicate file information corresponding to a file to for identification of potentially identical files stored on the plurality of other computers by accessing a mapping of a portion of the file information to one or more computers.

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

59. A system as recited in claim 57, wherein the size of the portion of the file information is based at least in part on a count of computers coupled to the system that the system is aware of.

60. A system as recited in claim 57, further comprising a local imprint to computer mapping, and wherein the forwarding location determination module is configured to identify the one or more computers to communicate the file information to by accessing the local imprint to computer mapping.

61. A system as recited in claim 57, wherein the forwarding location determination module is configured to identify the one or more computers to communicate the file information to by accessing an imprint to computer mapping stored at another computer.

62. A method comprising:

receiving file information corresponding to a file stored at a computer;

comparing the received file information to a file information database;

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

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

forwarding the received file information to another computer for storage in a file information database at the other computer.

63. 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.

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

receiving, from a requesting computer, a request for an imprint to computer mapping, wherein the imprint comprises a portion of object information corresponding to an object;

accessing a mapping database to identify one or more computers associated with the imprint; and

returning an identification of at least one of the one or more computers to the requesting computer.

65. One or more computer-readable media as recited in claim 64, wherein the object comprises a file and wherein the object information comprises file information.

66. One or more computer-readable media as recited in claim 64, wherein the at least one of the one or more computers includes the requesting computer.

67. One or more computer-readable media as recited in claim 64, wherein the returning comprises returning an identification of all of the one or more computers to the requesting computer.

68. One or more computer-readable media as recited in claim 64, wherein the file information is a semi-unique value based at least in part on the data in the object.

69. One or more computer-readable media as recited in claim 64, wherein the size of the portion of the object information is based at least in part on a count of computers coupled to the requesting computer that the requesting computer is aware of.

70. A method, implemented in a computer that is one of a plurality of computers in a network, the method comprising:

grouping, into a plurality of groups, selected ones of the plurality of computers, wherein the grouping is based at least in part on the number of the plurality of computers in the network that the computer is aware of;

selecting a portion of object information corresponding to an object; and

identifying which of the selected ones of the plurality of computers to communicate the object information to for identification of potentially identical objects stored on the plurality of computers, wherein the identifying is based at least in part on comparing the selected portion of the object information to a portion of a computer identifier of one or more of the selected ones of the plurality of computers.

71. A method as recited in claim 70, wherein the object is stored at the computer.

72. A method as recited in claim 70, wherein the object is stored at another of the plurality of computers.

73. A method as recited in claim 70, wherein the plurality of groups comprise two groups.

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

75. A method as recited in claim 70, wherein a size of the portion of the object information is further based at least in part on an average number of computers that a particular object identifier should be communicated to.

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

77. A method as recited in claim 70, wherein the size of the portion of the object information is the same as the size of the portions of the computer identifiers.

78. A method as recited in claim 70, wherein the portion of object information comprises a set of least significant bits of the object information.

79. A method as recited in claim 78, wherein the number of bits in the set of least significant bits is based at least in part on the number of other computers in the network that the computer is aware of.

80. A method as recited in claim 70, wherein the grouping comprises identifying as a first group one or more of the plurality of computers having computer identifiers each with a portion that is the same as a portion of a computer identifier of the computer.

81. A method as recited in claim 80, wherein the identifying comprises:

checking whether all of the bits in the portion of the computer identifier match all of the bits in the selected portion of the object information; and

identifying, as computers to communicate the object information to, the computers in the first group if all of the bits in the portion of the computer identifier match all of the bits in the selected portion of the object information.

82. A method as recited in claim 70, wherein the grouping comprises:

identifying as a first group one or more of the plurality of computers having computer identifiers each with a portion that is the same as a portion of a computer identifier of the computer; and

identifying as a second group one or more of the plurality of computers that do not have computer identifiers each with the portion that is the same as the portion of the computer identifier of the computer, but that do have computer identifiers each with a first subset of the portion that is the same as a first subset of the portion of the computer identifier of the computer.

83. A method as recited in claim 82, wherein the first subset of each portion comprises the even bits of the portion.

84. A method as recited in claim 70, wherein the grouping comprises:

identifying as a first group one or more of the plurality of computers having computer identifiers each with a portion that is the same as a portion of a computer identifier of the computer;

identifying as a second group one or more of the plurality of computers that do not have computer identifiers each with the portion that is the same as the portion of the computer identifier of the computer, but that do have computer identifiers each with a first subset of the portion that is the same as a first subset of the portion of the computer identifier of the computer; and

identifying as a third group one or more of the plurality of computers that do not have computer identifiers each with the first subset of the portion that is the same as the first subset of the portion of the computer identifier of the computer, but that do have computer identifiers each with a second subset of the portion that is the same as a second subset of the portion of the computer identifier of the computer.

85. A method as recited in claim 84, wherein the first subset of each portion comprises the even bits of the portion and the second subset of each portion comprises the odd bits of the portion.

86. A method as recited in claim 70, wherein the grouping comprises:

identifying as one group one or more of the plurality of computers that have computer identifiers each with a subset of the portion of the computer identifier that is the same as a subset of the portion of the computer identifier of the computer.

87. A method as recited in claim 86, wherein the identifying comprises:

checking whether each bit in another subset of the portion of the computer identifier matches a corresponding bit in the selected portion of the object information; and

if each bit in the other subset of the portion of the computer identifier matches the corresponding bit in the selected portion of the object information, then identifying, as computers to communicate the object information to, the computers in the one group having a portion of their computer identifiers matching the corresponding bits in the selected portion of the object information.

88. A method as recited in claim 86, wherein the identifying comprises:

checking whether each bit in another subset of the portion of the computer identifier matches a corresponding bit in the selected portion of the object information; and

if one or more bits in the other subset of the portion of the computer identifier do not match the corresponding bit in the selected portion of the object information, then identifying, as computers to communicate the object information to, the computers in another group having the bits of a subset of their computer identifiers matching the selected portion of the object information.

89. A method as recited in claim 70, wherein the grouping comprises:

identifying as a first group one or more of the plurality of computers having computer identifiers each with a portion that is the same as a portion of a computer identifier of the computer;

identifying as a second group one or more of the plurality of computers that do not have computer identifiers each with the portion that is the same as the portion of the computer identifier of the computer, but that do have computer identifiers each with a first subset of the portion that is the same as a first subset of the portion of the computer identifier of the computer;

identifying as a third group one or more of the plurality of computers that do not have computer identifiers each with the portion that is the same as the portion of the computer identifier of the computer, but that do have computer identifiers each with a second subset of the portion that is the same as a second subset of the portion of the computer identifier of the computer;

checking whether all of the bits in the portion of the computer identifier match all of the bits in the selected portion of the object information;

if all of the bits in the portion of the computer identifier match all of the bits in the selected portion of the object information, then identifying, as computers to communicate the object information to, the computers in the first group; and

if all of the bits in the portion of the computer identifier do not match all of the bits in the selected portion of the object information, then,

checking whether the bits in the second subset of the portion of the object information match the bits in the second subset of the computer identifier,

if the bits in the second subset of the portion of the object information match the bits in the second subset of the computer identifier, then identifying, as computers to communicate the object information to, the computers in the third group having their computer identifiers matching the selected portion of the object information, and

if the bits in the second subset of the portion of the object information do not match the bits in the second subset of the computer identifier, then identifying, as computers to communicate the object information to, the computers in the second group having the subset of bits in their computer identifiers matching the corresponding bits in the selected portion of the object information.

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

selecting ones of the plurality of computers to populate a plurality of groups, wherein the selecting is based at least in part on the number of computers in the network that the computer is aware of;

selecting a plurality of bits of file information corresponding to a file; and

identifying which of the selected ones of the plurality of computers to communicate the file information to for identification of potentially identical files on the plurality of computers, wherein the identifying is based at least in part on comparing the selected plurality of bits of the file information to a corresponding plurality of bits of a computer identifier of one or more of the selected ones of the plurality of computers.

91. One or more computer-readable media as recited in claim 90, wherein the file is stored at the computer.

92. One or more computer-readable media as recited in claim 90, wherein the file is stored at another of the plurality of computers.

93. One or more computer-readable media as recited in claim 90, wherein the plurality of instructions further cause the one or more processors to perform the following acts:

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 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.

94. One or more computer-readable media as recited in claim 90, wherein the selecting comprises identifying as a first group one or more of the plurality of computers having computer identifiers each with a plurality of bits that is the same as a plurality of bits of a computer identifier of the computer.

95. One or more computer-readable media as recited in claim 94, wherein the identifying comprises:

checking whether all of the plurality of bits of the computer identifier match all of the plurality of bits of the file information; and

identifying, as computers to communicate the file information to, the computers in the first group if all of the plurality of bits of the computer identifier match all of the plurality of bits of the file information.

96. A method as recited in claim 90, wherein the selecting comprises:

identifying as a first group one or more of the plurality of computers having computer identifiers each with a plurality of bits that is the same as a plurality of bits of a computer identifier of the computer; and

identifying as a second group one or more of the plurality of computers that do not have computer identifiers each with a plurality of bits that is the same as the plurality of bits of the computer identifier of the computer, but that do have computer identifiers each with a first subset of the plurality of bits that is the same as a first subset of the plurality of bits of the computer identifier of the computer.

97. A system, coupled to a plurality of computers, the system comprising:

an interface configured to allow the system to communicate with the plurality of computers; and

a forwarding location determination module, coupled to the interface, configured to identify one or more of the plurality of computers to communicate the file information for a file to, for identification of potentially identical files stored on the plurality of computers by,

grouping, into a plurality of groups, selected ones of the plurality of computers, wherein the grouping is based at least in part on the number of the plurality of computers in the network that the system is aware of,

selecting a portion of the file information, and

comparing the selected portion of the file information to a portion of a computer identifier of one or more of the selected ones of the plurality of computers.