File availability in distributed file storage systems

• US 7,299,250 B2
• Filed: 01/20/2006
• Issued: 11/20/2007
• Est. Priority Date: 03/07/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Wattenhofer, Roger P.
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US11/275,655
• Publication Number:
  US 20060106882A1
• Time in Patent Office: 669 Days
• Field of Search: 707200-205, 709/206, 714/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

File availability in distributed file storage systems is improved by initially placing replicas of a file or other object on different ones of multiple devices using a first process. Subsequently, the placement of the replicas is improved by evaluating whether any replicas of a first file can be swapped with any replicas of a second file without a reduction in the combined file availability of the first and second files, and swapping a replica of the first file with a replica of the second file if the swapping results in no reduction in the combined file availability of the first and second files.

Claims

1. A method for determining location to store object replicas, the method comprising:

receiving an indication of a homeless replica of an object, wherein the object has a plurality of replicas including the homeless replica;

determining an initial placement for the homeless replica, wherein the initial placement is one of a plurality of devices in a system;

evaluating, on an object by object basis, whether any replicas of the object can be swapped with one of a plurality of replicas of an other object and not reduce a combined object availability of the two objects, wherein the evaluating comprises determining, for each possible swapping of replicas of objects, an object availability for each object, and checking whether any of the possible swappings result in a combined object availability of two objects that is greater than other combined object availability prior to the evaluating; and

swapping a replica of the object with the one of the plurality of replicas of the other object, wherein the swapping is based on the evaluating and performed only if the swapping does not reduce the combined object availability of the two objects, wherein the replica of the object is stored on a first computing device and wherein the swapping the replicas comprises moving the replica of the object to a second computing device, storing the moved replica of the object in the second computing device and moving the one of the plurality of replicas of the other object to the first computing device, wherein the swapping results in decreasing an availability of the object and increasing an availability of the other object.

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

3. A method as recited in claim 1, wherein the object comprises a plurality of files.

4. A method as recited in claim 1, wherein the object comprises a portion of a file.

5. A method as recited in claim 1, wherein the object comprises a directory.

6. A method as recited in claim 1, implemented by a computing device and further comprising selecting, prior to the evaluating, as the object one of a plurality of objects that the computing device is responsible for maintaining.

7. A method as recited in claim 6, wherein the selecting comprises selecting the one of the plurality of objects that has lowest object availability.

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

working, in conjunction with one or more other processors of by other computing device, to determine whether a replica of a file managed by the computing device and a replica of an other file managed by the other computing device can be swapped with one another to bring an availability of the file and an availability of the other file closer, wherein said working comprises determining, for the replicas, an availability for each replica and checking whether the swapping results in a combined availability of two replicas that is greater than other combined availability if the files were not to be swapped; and

swapping the replica of the file and the replica of the other file only if the swapping brings the availability of the file and the availability of the other file closer, wherein said swapping comprises communicating with a first device on which the replica of the file is stored and a second device on which the replica of the other file is stored to have the first device transfer the replica of the file to the second device and delete the replica of the file on the first device, and to have the second device transfer the replica of the other file to the first device and delete the replica of the other file on the second device, wherein the swapping results in decreasing an availability of the replica of the file and increasing the availability of the replica of the other file.

9. One or more computer readable storage media as recited in claim 8, wherein the plurality of instructions further cause the one or more processors to perform acts comprising:

receiving an indication of a homeless replica of the file; and

determining an initial placement, on one of a plurality of additional computing devices, for the homeless replica.

10. One or more computer readable storage media as recited in claim 9, wherein the plurality of additional computing devices exclude any computing device on which a replica of the file is already stored.

11. One or more computer readable storage media as recited in claim 8, wherein the file is selected randomly from a plurality of files managed by the computing device, and wherein the other file is selected randomly from another plurality of files managed by the other computing device.

12. One or more computer readable storage media as recited in claim 8, wherein the one or more processors of a computing device and the one or more other processors of another computing device are the same processors of a same computing device.