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

• US 7,519,623 B2
• Filed: 11/18/2004
• Issued: 04/14/2009
• Est. Priority Date: 06/06/2001
• Status: Expired due to Fees

• 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): Wong; Don
• Assistant Examiner(s): Nguyen; Kim T
• Application Number:
  US10/991,656
• Publication Number:
  US 20050071330A1
• Time in Patent Office: 1,608 Days
• Field of Search: 707/200, 707/205
• 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
• 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:

receiving file information corresponding to a file stored at a computer, wherein a choice of computer receiving the file information is based at least in part on a count of computers coupled to a requesting computer that the requesting computer is aware of;

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.

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

3. One or more computer-readable storage media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform a method, the method comprising:

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, a computer receiving the request having been chosen based in part on a count of computers coupled to the requesting computer that the requesting computer was aware of;

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.

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

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

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

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

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

9. A method comprising:

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, a computer receiving the request having been chosen based in part on a count of computers coupled to the requesting computer that the requesting computer was aware of;

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.

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

11. A method as recited in claim 9, wherein the at least one of the one or more computers includes the requesting computer.

12. A method as recited in claim 9, wherein the returning comprises returning an identification of all of the one or more computers to the requesting computer.

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

14. A method as recited in claim 9, wherein a size of the portion of the object information is based at least in part on the count of computers coupled to the requesting computer that the requesting computer is aware of.