File Availability in Distributed File Storage Systems

• US 20060106882A1
• Filed: 01/20/2006
• Published: 05/18/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,299,250 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 method for determining where 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 another object and not reduce a combined object availability of the two objects; and

swapping a replica of the object with the one of the plurality of replicas of the other object only if the swapping does not reduce the combined object availability of the two objects.

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

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

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

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

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

7. A method as recited in claim 1, wherein the evaluating comprises:

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

checking whether any of the possible swappings result in a combined object availability of the two objects that is greater than the combined object availability prior to the evaluating.

8. A method as recited in claim 1, wherein the swapping results in decreasing an availability of the object and increasing an availability of the other object.

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

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

11. One or more computer readable 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 another computing device, to determine whether a replica of a file managed by the computing device and a replica of another 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; 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.

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

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

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

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

16. One or more computer readable media as recited in claim 11, 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 the same computing device.

17. A method, implemented in a directory group, the method comprising:

selecting another directory group to participate with in a replica placement improvement process;

selecting a file maintained by the directory group;

determining whether exchanging a replica of the file with a replica of another file maintained by the other directory group will increase a combined file availability of the files; and

having the replica of the file and the replica of the other file exchanged if exchanging the replicas will increase the combined file availability of the files.

18. A method as recited in claim 17, further comprising:

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

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 file is already stored.

19. A method as recited in claim 17, wherein the file is selected as the one of a plurality of files managed by the directory group having a lowest file availability, and the other file is selected randomly from another plurality of files managed by the other directory group.

20. A method as recited in claim 17, wherein the file is selected as the one of a plurality of files managed by the directory group having a lowest file availability, and the other file is selected as the one of another plurality of files managed by the other directory group having a highest file availability.