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

• US 20050071315A1
• Filed: 11/18/2004
• Published: 03/31/2005
• 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,571,186 B2
• Time in Patent Office: Days
• 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:

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.

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

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

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

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

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

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

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

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

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

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

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

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