US20030172089A1
Expired / Lapsed
US
⏱️ 0.0 years remaining
File availability in distributed file storage systems
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2002-03-07
•
Granted: —
•
Expires: 2022-03-07
Abstract
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.
Inventors
- 👤 John Douceur
- 👤 Roger Wattenhofer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 19:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/955; Y10S707/964; Y10S707/966; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10S707/99955
Claims Analysis
Total Claims: 53
Claim 1
Independent Claim
123 words
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 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.
Claim 2
Dependent Claim
123 words
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 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.
Claim 3
Dependent Claim
77 words
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.
Claim 4
Dependent Claim
25 words
3 . A method as recited in claim 1 , wherein the method is implemented by multiple computing devices in a serverless distributed file system.
Claim 5
Dependent Claim
24 words
4 . A method as recited in claim 1 , wherein both the object and the other object have a same amount of replicas.
Claim 6
Dependent Claim
16 words
5 . A method as recited in claim 1 , wherein the object comprises a file.
Claim 7
Dependent Claim
18 words
6 . A method as recited in claim 1 , wherein the object comprises a plurality of files.
Claim 8
Dependent Claim
19 words
7 . A method as recited in claim 1 , wherein the object comprises a portion of a file.
Claim 9
Dependent Claim
16 words
8 . A method as recited in claim 1 , wherein the object comprises a directory.
Claim 10
Dependent Claim
23 words
9 . A method as recited in claim 1 , wherein the determining comprises randomly selecting the initial placement for the homeless replica.
Claim 11
Dependent Claim
60 words
10 . 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.
Claim 12
Dependent Claim
43 words
11 . A method as recited in claim 1 , wherein combined object availability is not reduced if the availability of the object and the availability of the other object are no further from one another than they were prior to the evaluating.
Claim 13
Dependent Claim
29 words
12 . A method as recited in claim 1 , wherein the swapping results in increasing an availability of the object and decreasing an availability of the other object.
Claim 14
Dependent Claim
29 words
13 . 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.
Claim 15
Dependent Claim
40 words
14 . 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.
Claim 16
Dependent Claim
22 words
15 . A method as recited in claim 14 , wherein the selecting comprises randomly selecting one of the plurality of objects.
Claim 17
Dependent Claim
28 words
16 . A method as recited in claim 14 , wherein the selecting comprises selecting the one of the plurality of objects that has the lowest object availability.
Claim 18
Dependent Claim
42 words
17 . A method as recited in claim 1 , wherein the other object is one of a plurality of objects that a computing device is responsible for maintaining, and wherein the other object is randomly selected from the plurality of objects.
Claim 19
Dependent Claim
48 words
18 . A method as recited in claim 1 , wherein the other object is one of a plurality of objects that a computing device is responsible for maintaining, and wherein the other object is the one of the plurality of objects that has the highest object availability.
Claim 20
Dependent Claim
128 words
19 . 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.
Claim 21
Dependent Claim
128 words
19 . 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.
Claim 22
Dependent Claim
101 words
20 . One or more computer readable media as recited in claim 19 , 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.
Claim 23
Dependent Claim
31 words
21 . One or more computer readable media as recited in claim 19 , wherein the one or more processors are part of a device in a serverless distributed file system.
Claim 24
Dependent Claim
22 words
22 . One or more computer readable media as recited in claim 19 , wherein the file represents a plurality of files.
Claim 25
Dependent Claim
23 words
23 . One or more computer readable media as recited in claim 19 , wherein the file represents a portion of another file.
Claim 26
Dependent Claim
20 words
24 . One or more computer readable media as recited in claim 19 , wherein the file represents a folder.
Claim 27
Dependent Claim
58 words
25 . One or more computer readable media as recited in claim 19 , 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.
Claim 28
Dependent Claim
29 words
26 . One or more computer readable media as recited in claim 25 , wherein determining the initial placement comprises randomly selecting the initial placement for the homeless replica.
Claim 29
Dependent Claim
35 words
27 . One or more computer readable media as recited in claim 25 , wherein the plurality of additional computing devices exclude any computing device on which a replica of the file is already stored.
Claim 30
Dependent Claim
49 words
28 . One or more computer readable media as recited in claim 19 , 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.
Claim 31
Dependent Claim
55 words
29 . One or more computer readable media as recited in claim 19 , wherein the file is selected as the one of a plurality of files managed by the computing device having a lowest file availability, and the other file is selected randomly from another plurality of files managed by the other computing device.
Claim 32
Dependent Claim
62 words
30 . One or more computer readable media as recited in claim 19 , wherein the file is selected as the one of a plurality of files managed by the computing device having a lowest file availability, and the other file is selected as the one of another plurality of files managed by the other computing device having a highest file availability.
Claim 33
Dependent Claim
63 words
31 . One or more computer readable media as recited in claim 19 , wherein the computing devices is part of a directory group that is collectively responsible for managing a plurality of files including the file, and wherein the other computing device is part of another directory group that is collectively responsible for managing another plurality of files including the other file.
Claim 34
Dependent Claim
44 words
32 . One or more computer readable media as recited in claim 19 , 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.
Claim 35
Dependent Claim
202 words
33 . A serverless distributed file system 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 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 file and a replica of another file for which the second computing device manages storage can be swapped in order to improve a combined file availability; and if the replicas can be swapped to improve the combined file availability, then instructing the one of the first plurality of computing devices on which the replica of the file is stored to transfer the replica of the file to the one of the first plurality of computing devices on which the replica of the other file is stored, and instructing the one of the first plurality of computing devices on which the replica of the other file is stored to transfer the replica of the other file to the one of the first plurality of computing devices on which the replica of the file is stored.
Claim 36
Dependent Claim
202 words
33 . A serverless distributed file system 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 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 file and a replica of another file for which the second computing device manages storage can be swapped in order to improve a combined file availability; and if the replicas can be swapped to improve the combined file availability, then instructing the one of the first plurality of computing devices on which the replica of the file is stored to transfer the replica of the file to the one of the first plurality of computing devices on which the replica of the other file is stored, and instructing the one of the first plurality of computing devices on which the replica of the other file is stored to transfer the replica of the other file to the one of the first plurality of computing devices on which the replica of the file is stored.
Claim 37
Dependent Claim
26 words
34 . A serverless distributed file system as recited in claim 33 , wherein the second plurality of computing devices comprise one or more directory groups.
Claim 38
Dependent Claim
64 words
35 . A serverless distributed file system as recited in claim 33 , 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.
Claim 39
Dependent Claim
130 words
36 . 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: initially place replicas of a 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 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.
Claim 40
Dependent Claim
130 words
36 . 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: initially place replicas of a 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 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.
Claim 41
Dependent Claim
21 words
37 . One or more computer readable media as recited in claim 36 , wherein the first process comprises random selection.
Claim 42
Dependent Claim
116 words
38 . One or more computer readable media as recited in claim 36 , 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.
Claim 43
Dependent Claim
41 words
39 . One or more computer readable media as recited in claim 36 , wherein the first file is selected randomly from a first plurality of files, and wherein the second file is selected randomly from a second plurality of files.
Claim 44
Dependent Claim
47 words
40 . One or more computer readable media as recited in claim 36 , wherein the first file is selected as the one of a first plurality of files having a lowest file availability, and the second file is selected randomly from a second plurality of files.
Claim 45
Dependent Claim
55 words
41 . One or more computer readable media as recited in claim 36 , wherein the first file is selected as the one of a first plurality of files managed having a lowest file availability, and the second file is selected as the one of a second plurality of files having a highest file availability.
Claim 46
Dependent Claim
90 words
42 . 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.
Claim 47
Dependent Claim
90 words
42 . 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.
Claim 48
Dependent Claim
57 words
43 . A method as recited in claim 42 , 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.
Claim 49
Dependent Claim
16 words
44 . A method as recited in claim 42 , wherein the selecting comprises randomly selecting.
Claim 50
Dependent Claim
109 words
45 . A method as recited in claim 42 , wherein having the replica of the file and the replica of the other file exchanged 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.
Claim 51
Dependent Claim
45 words
46 . A method as recited in claim 42 , wherein the file is selected randomly from a plurality of files managed by the directory group, and wherein the other file is selected randomly from another plurality of files managed by the other directory group.
Claim 52
Dependent Claim
51 words
47 . A method as recited in claim 42 , 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.
Claim 53
Dependent Claim
58 words
48 . A method as recited in claim 42 , 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.
References Cited (Backward Citations)
US6345288B1
Cited
US5317728A
Cited
US5721880A
Cited
US5452447A
Cited
US5588147A
Cited
US5991771A
Cited
US5778395A
Cited
US5873085A
Cited
US5907673A
Cited
US6026474A
Cited
US6185574B1
Cited
US6160552A
Cited
US6718360B1
Cited
US5950198A
Cited
US6738797B1
Cited
US6484204B1
Cited
US6067545A
Cited
US6493804B1
Cited
US20040068652A1
Cited
US6560706B1
Cited
US6725373B2
Cited
US6510426B1
Cited
US6522423B2
Cited
US6463535B1
Cited
US6324544B1
Cited
US6295538B1
Cited
US6389433B1
Cited
US6477544B1
Cited
US6466978B1
Cited
US6766367B1
Cited
US6415372B1
Cited
US6748538B1
Cited
US6671821B1
Cited
US20030135586A1
Cited
US6704730B2
Cited
US6556998B1
Cited
US20020103818A1
Cited
US6535894B1
Cited
US20020073082A1
Cited
US20020111996A1
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.