File Availability in Distributed File Storage Systems

• US 20060112154A1
• Filed: 01/20/2006
• Published: 05/25/2006
• Est. Priority Date: 03/07/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Wattenhofer, Roger P.
• Granted Patent: US 7,200,618 B2
• Time in Patent Office: Days
• 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 computing device for determining location to store object replicas, the computing device comprising:

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

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

means for evaluating, on an object by object basis, whether any replicas of a first object can be swapped with one of a plurality of replicas of a second object and not reduce a combined object availability of the first and second objects, wherein the first object is selected as the one of a plurality of objects managed by a first computing device having a lowest object availability, and the second object is selected as the one of another plurality of objects managed by a second computing device having a highest file availability, wherein the means for evaluating comprises;

means for determining, for each possible swapping of replicas of the objects, an object availability for each object; and

means for checking whether any of the possible swappings result in the combined object availability of the first and second objects that is greater than the combined object availability; and

means for swapping a replica of the first object with the one of the plurality of replicas of the second object only if the swapping does not reduce the combined object availability of the first and second objects, wherein the swapping results in increasing an availability of the first object and decreasing an availability of the second object.

2. A computing device as recited in claim 1, wherein the replica of the first object is stored on the first computing device, wherein the one of the plurality of replicas of the second object is stored on the second computing device, and wherein swapping the replicas comprises moving the replica of the first object to the second computing device and moving the one of the plurality of replicas of the second object to the first computing device.

3. A computing device as recited in claim 1, wherein both the first object and the second object have a same amount of replicas.

4. A computing device as recited in claim 1, wherein the object represents a plurality of files.

5. A computing device as recited in claim 1, wherein the object is represents a portion of a file.

6. A computing device as recited in claim 1, wherein the object represents a directory.

7. A computing device as recited in claim 1, wherein the means for determining an initial placement comprises means for randomly selecting the initial placement for the homeless replica.

8. A computing device as recited in claim 1, wherein combined object availability is not reduced if the availability of the first object and the availability of the second object are no further from one another than they were prior to the evaluating.

9. A computing device comprising:

a processor;

a memory, coupled to the processor, to store a program for determining location to store object replicas, wherein the program, when executed by the processor, causes the processor to;

receive an indication of a homeless replicas of a file;

initially place the homeless replicas of the file on different ones of a plurality of devices using a first process; and

subsequently improve the placement of replicas of a plurality of files by;

evaluating, on a file by file basis, 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, wherein the first file is selected as the one of a plurality of files managed by a first computing device having a lowest file availability, and the second file is selected as the one of another plurality of files managed by a second computing device having a

determining, for each possible swapping of replicas of the files, a file availability for each file; and

checking whether any of the possible swappings result in the combined file availability of the first and second files that is greater than a combined file availability; 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, wherein the swapping results in increasing an availability of the first file and decreasing an availability of the second file.

10. A computing device as recited in claim 9, wherein the first process comprises random selection.

11. A computing device as recited in claim 9, wherein swapping the replica of the first file with the replica of the second file comprises communicating with a first device on which the replica of the first file is stored and a second device on which the replica of the second file is stored to have the first device transfer the replica of the first file to the second device and delete the replica of the first file on the first device, and to have the second device transfer the replica of the second file to the first device and delete the replica of the second file on the second device.

12. A computing device in a directory group for determining location to store file replicas, the computing device comprising:

means for selecting other directory group to participate with in a replica placement process;

means for selecting a first file maintained by the directory group;

means for determining whether exchanging a replica of the first file with a replica of a second file maintained by the other directory group will increase a combined file availability of the first and second files, wherein the first file is selected as one of a plurality of files managed by the directory group having a lowest file availability, and the second file is selected as one of another plurality of files managed by the other directory group having a highest file availability;

means for evaluating, on a file by file basis, whether any replicas of the first file can be swapped with one of a plurality of replicas of the second file and not reduce a combined file availability of the first and second files, wherein the means for evaluating comprises;

means for determining, for each possible swapping of replicas of the files, a file availability for each file; and

means for checking whether any of the possible swappings result in the combined file availability of the first and second files that is greater than a combined file availability; and

means for having the replica of the first file and the replica of the second file exchanged if exchanging the replicas increases the combined file availability of the first and second files, wherein the exchange results in increasing an availability of the first file and decreasing an availability of the second file.

13. A computing device as recited in claim 12, further comprising:

means for receiving, at the directory group, an indication of a homeless replica of the first file; and

means for selecting, as a computing device on which to store the homeless replica, one of a plurality of computing devices on which no other replica of the first file is already stored.

14. A computing device as recited in claim 12, wherein the means for having the replica of the first file and the replica of the second file exchanged comprises means for communicating with a first device on which the replica of the first file is stored and a second device on which the replica of the second file is stored to have the first device transfer the replica of the first file to the second device and delete the replica of the first file on the first device, and to have the second device transfer the replica of the second file to the first device and delete the replica of the second file on the second device.