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

• US 6,988,124 B2
• Filed: 06/06/2001
• Issued: 01/17/2006
• 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): Vu, Viet D.
• Assistant Examiner(s): Hu, Jinsong
• Application Number:
  US09/876,376
• Publication Number:
  US 20030037094A1
• Time in Patent Office: 1,686 Days
• Field of Search: 709/203, 709/212, 709/227, 707/201
• US Class Current: 709/203
• 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. 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;

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

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 1g 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;

$W=\lfloor <br><br>\lg <br><br>\frac{M}{R}\rfloor <br><br>.$

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

3. One or more computer-readable media as recited in claim 1, 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.

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

5. One or more computer-readable media as recited in claim 1, 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.

6. One or more computer-readable media as recited in claim 1, 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.

7. One or more computer-readable media 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.

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

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

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

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

12. One or more computer-readable media as recited in claim 1, 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.

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

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