Serverless distributed file system

• US 7,505,970 B2
• Filed: 10/06/2004
• Issued: 03/17/2009
• Est. Priority Date: 03/26/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wattenhofer, Roger P., Theimer, Marvin M., Bolosky, William J., Douceur, John R., Adya, Atul, Cermak, Gerald
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Nguyen; Merilyn P
• Application Number:
  US10/959,701
• Publication Number:
  US 20050044092A1
• Time in Patent Office: 1,623 Days
• Field of Search: 707/1, 707/2, 707/4, 707 8- 10, 707/102, 714/1, 714/3, 714/4, 714/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 2201/825 the problem or solution involving locking
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A serverless distributed file system manages the storage of files and directories using one or more directory groups. The directories may be managed using Byzantine-fault-tolerant groups, whereas files are managed without using Byzantine-fault-tolerant groups. Additionally, the file system may employ a hierarchical namespace to store files. Furthermore, the directory group may employ a plurality of locks to control access to objects (e.g., files and directories) in each directory.

Claims

1. A method implemented in a serverless distributed file system, the method comprising:

receiving a request to open an object with one or more selected locks;

checking whether the one or more selected locks conflict with a lock already granted to another application,

denying the request to open the object if the one or more selected locks conflict with a lock already granted to another application; and

granting the request to open the object only if the one or more selected locks do not conflict with a lock already granted to another application, wherein the granting comprises;

attempting to upgrade a particular selected lock of the one or more selected locks to a broader scope than the one or more selected locks indicated in the request such that upgrading the particular selected lock to the broader scope comprises upgrading the particular selected lock to a directory lock; and

activating a lease on the one or more selected locks.

2. A method as recited in claim 1, further comprising:

when it is determined that the one or more selected locks conflict with a lock already granted to another application, requesting that the application that holds the lock that conflicts with the one or more selected locks return the conflicting lock; and

granting the request to open the object if the conflicting lock is returned, otherwise denying the request to open the object.

3. A method as recited in claim 1, further comprising:

upgrading the particular selected lock to a broader scope than indicated in the request;

checking whether the particular selected lock, after being upgraded to the broader scope, conflicts with a lock already granted to another application; and

granting the request to open the object with the particular selected lock upgraded to the broader scope only if the checking of the particular selected lock of the upgraded broader scope indicates that no conflict exists.

4. A method as recited in claim 1, further comprising:

denying the request to open the object if checking whether the one or more selected locks indicates a desire to share the object for one or more operations that conflict with sharing indicated by another application that has previously been granted a lock.

5. A method as recited in claim 1, further comprising:

attempting to downgrade a lock previously granted to another application to not conflict with the one or more selected locks prior to denying the request to open the object with the one or more selected locks if the one or more selected locks conflict with a lock already granted to another application.

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

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

8. A method as recited in claim 1, wherein the one or more selected locks comprise an Open Read lock.

9. A method as recited in claim 1, wherein the one or more selected locks comprise an Open Write lock.

10. A method as recited in claim 1, wherein the one or more selected locks comprise an Open Delete lock.

11. A method as recited in claim 1, wherein the at least one selected lock comprises a Not Shared Read lock.

12. A method as recited in claim 1, wherein the at least one selected lock comprises a Not Shared Write lock.

13. A method as recited in claim 1, wherein the at least one selected lock comprises a Not Shared Delete lock.

14. A method as recited in claim 1, wherein the one or more selected locks comprise at least one of:

an Open Read lock to control opening of the objects for reading;

an Open Write lock to control opening of the objects for writing;

or

an Open Delete lock to control opening of the objects for deleting.

15. One or more computer storage media having stored thereon a plurality of instructions to implement a serverless distributed file system, wherein the plurality of instructions, when executed, direct a computing system to perform a method comprising:

assigning responsibility for managing one or more directories to a directory group, wherein each member of the directory group is a computer participating in the serverless distributed file system; and

employing a plurality of locks to control access to objects in each directory, wherein the plurality of locks comprise;

a first set of locks to control opening of the objects, wherein the first set of locks comprises more than one lock; and

a second set of locks, separate from the first set of locks, to control access to data in the objects, wherein the second set of locks comprises more than one lock.

16. One or more computer storage media as recited in claim 15, wherein the second set of locks comprises at least one of:

a Read lock to control read access to the data in the objects;

or

a Write lock to control write access to the data in the objects.

17. One or more computer storage media as recited in claim 15, wherein the first set of locks comprises at least one of:

an Open Read lock to control opening of the objects for reading;

an Open Write lock to control opening of the objects for writing;

or

an Open Delete lock to control opening of the objects for deleting.

18. One or more computer storage media as recited in claim 15, wherein the first set of locks comprises:

a Not Shared Read Lock to indicate an unwillingness to share the ability to read the objects.

19. One or more computer storage media as recited in claim 15, wherein the first set of locks comprises:

a Not Shared Write Lock to indicate an unwillingness to share the ability to write to objects.

20. One or more computer storage media as recited in claim 15, wherein the first set of locks comprises:

a Not Shared Delete Lock to indicate an unwillingness to share the ability to delete the objects.

21. One or more computer storage media as recited in claim 15, wherein the plurality of locks further comprises an Insert lock to control creation of a new object with a particular name.

22. One or more computer storage media as recited in claim 15, wherein the plurality of locks further comprises an Exclusive lock to obtain all of the other ones of the plurality of locks for an object.

23. One or more computer storage media as recited in claim 15, wherein the objects comprise one or more files and one or more directories.