File availability in distributed file storage systems

• US 7,020,665 B2
• Filed: 03/07/2002
• Issued: 03/28/2006
• 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:
  US10/092,994
• Publication Number:
  US 20030172089A1
• Time in Patent Office: 1,482 Days
• Field of Search: 707200-205, 711/165, 711/159, 711/203, 711/206, 709/201, 709/203, 709/227
• US Class Current: 707/626
• 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 computer implemented 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, wherein the object is a file;

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 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 one of a plurality of objects managed by a first computing device having a lowest object availability, and the second object is selected as one of another plurality of objects managed by a second computing device having a highest file availability, 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 the combined object availability of the first and second objects that is greater than a combined object availability; and

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 method 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 method as recited in claim 1, wherein the method is implemented by multiple computing devices in a serverless distributed file system.

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

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

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

7. A method as recited in claim 1, wherein the object represents a directory.

8. A method as recited in claim 1, wherein the determining comprises randomly selecting the initial placement of the homeless replica.

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

10. 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 for determining location to store file replicas, causes the one or more processors to perform acts comprising:

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

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

working, in conjunction with one or more other processors of another computing device, to determine whether a replica of a first file managed by a first computing device and a replica of a second file managed by a second computing device can be swapped with one another to bring an availability of the first file and an availability of the second file closer, wherein the first file is selected as one of a plurality of files managed by the first computing device having a lowest file availability, and the second file is selected as one of another plurality of files managed by the second computing device having a highest file availability;

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 evaluating comprises;

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

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 the replica of the first file and the replica of the second file only if the swapping brings the availability of the first file and the availability of the second file closer, wherein the swapping results in increasing the availability of the first file and decreasing the availability of the second file.

11. One or more computer readable media as recited in claim 10, wherein the swapping 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. One or more computer readable media as recited in claim 10, wherein the one or more processors are part of a device in a serverless distributed file system.

13. One or more computer readable media as recited in claim 10, wherein the file represents a plurality of files.

14. One or more computer readable media as recited in claim 10, wherein the file represents a portion of another file.

15. One or more computer readable media as recited in claim 10, wherein the file represents a folder.

16. One or more computer readable media as recited in claim 10, wherein determining the initial placement comprises randomly selecting the initial placement for the homeless replica.

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

18. One or more computer readable media as recited in claim 10, wherein the first computing device is part of a directory group that is collectively responsible for managing a plurality of files including the first file, and wherein the second computing device is part of another directory group that is collectively responsible for managing another plurality of files including the second file.

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

20. A computer implemented serverless distributed file system for determining location to store file replicas comprising:

a first plurality of computing devices storing files;

a second plurality of computing devices managing storage of the files;

wherein a first computing device of the second plurality of computing devices selects a first file for which it manages storage and communicates with a second computing device of the second plurality of computing devices to determine whether a replica of the first file and a replica of a second file for which the second computing device manages storage can be swapped in order to not reduce 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 first computing device having a lowest file availability, and second file is selected as one of another plurality of files managed by the second computing device having a highest file availability;

wherein at least one of the second plurality of computing devices determines, for each possible swapping of replicas of the files, a file availability for each file, and checks 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

if the replicas can be swapped to not reduce the combined file availability of the first and second files, then instructing one of the first plurality of computing devices on which the replica of the first file is stored to transfer the replica of the first file to one of the first plurality of computing devices on which the replica of the second file is stored, instructing the one of the first plurality of computing devices on which the replica of the second file is stored to transfer the replica of the second file to the one of the first plurality of computing devices on which the replica of the first file is stored, and

wherein the transfer of the replica of the first file to the one of the first plurality of computing devices on which the replica of the second file is stored and the transfer of the replica of the second file to the one of the first plurality of computing devices on which the replica of the first file is stored results in increasing an availability of the first file and decreasing an availability of the second file.

21. A serverless distributed file system as recited in claim 20, wherein the second plurality of computing devices comprise one or more directory groups.

22. A serverless distributed file system as recited in claim 20, wherein the second plurality of computing devices further receives an indication of a homeless replica of the file, and randomly selects, as a computing device on which to store the homeless replica, one of the first plurality of computing devices on which no other replica of the file is already stored.

23. One or more computer readable media having stored thereon a plurality of instructions that is executed by one or more processors of a computing device for determining location to store file replicas, causing the one or more processors 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 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 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 a first computing device having a lowest file availability, and the second file is selected as one of another plurality of files managed by a second computing device having a highest file availability, wherein the evaluating comprises;

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.

24. One or more computer readable media as recited in claim 23, wherein the first process comprises random selection.

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

26. A computer implemented method in a directory group for determining location to store file replicas, the method comprising:

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

selecting a first file maintained by the directory group;

determining whether exchanging a replica of the first file with a replica of a second file maintained by the other directory group increases 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;

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 the combined file availability of the first and second files, wherein the evaluating comprises;

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

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.

27. A method as recited in claim 26, further comprising:

receiving, at the directory group, an indication of a homeless replica of the first 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 first file is already stored.

28. A method as recited in claim 26, wherein having the replica of the first file and the replica of the second file exchanged 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.