Serverless distributed file system

• US 7,062,490 B2
• Filed: 12/05/2001
• Issued: 06/13/2006
• Est. Priority Date: 03/26/2001
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Theimer, Marvin M., Bolosky, William J., Douceur, John R., Adya, Atul, Cermak, Gerald, Wattenhofer, Roger P.
• Primary Examiner(s): Coby, Frantz
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US10/005,629
• Publication Number:
  US 20020188605A1
• Time in Patent Office: 1,651 Days
• Field of Search: 707/1, 707/4, 707/10, 707/102, 714/1, 714/3, 714/4, 714/11, 714/10, 713/168, 713/175, 713/157, 711/152, 711/100, 711/202
• 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 comprising:

identifying a group of computers to which a subtree of a hierarchical namespace used to store files is to be delegated;

generating a delegation certificate for the subtree, wherein the delegation certificate comprises;

a first digitally signed certificate identifying another group of computers responsible for managing a namespace root of the subtree; and

a second digitally signed certificate allowing authorization of the group of computers to manage the subtree to be traced to the other group of computers responsible for managing the namespace root;

digitally signing the delegation certificate; and

issuing the delegation certificate to the group of computers.

2. A method as recited in claim 1, wherein digitally signing the delegation certificate comprises having the delegation certificate digitally signed by a plurality of computers.

3. A method as recited in claim 1, wherein the group of computers comprise a Byzantine-fault-tolerant group.

4. A method as recited in 1, wherein the second digitally signed certificate comprises:

an identification of a path below the beginning of another subtree previously delegated to a third group of computers, wherein the third group of computers are the directory group performing generating;

an identification of a root of the other subtree delegated to the third group of computers;

an identification of the subtree; and

an identification of the members of the group of computers.

5. A method as recited in claim 4, wherein the computers in the third group of computers are the same computers as in the other group of computers.

6. A method as recited in 1, wherein the first digitally signed certificate is digitally signed by a certification authority (CA).

7. A method as recited in 1, wherein the delegation certificate further comprises one or more additional digitally signed certificates allowing a certificate chain to be established from the second digitally signed certificate to the first digitally signed certificate.

8. A serverless distributed file system comprising:

a plurality of computers;

a first set of the plurality of computers operating to store directory information for the file system, wherein each computer of the first set is part of a Byzantine-fault-tolerant group;

a second set of the plurality of computers operating to store replicas of the files in the file system, wherein for each file stored in the file system a plurality of replicas of the file are stored on the second set of computers, and wherein fewer computers are in the first set than in the second set;

wherein the first set of computers is configured to delegate management responsibility for a group of directories of the file system to a third set of the plurality of computers by,

generating a delegation certificate for the group of directories,

digitally signing the delegation certificate, and

issuing the delegation certificate to the third set of computers; and

wherein the third set of computers is configured to maintain management responsibility for the group of directories by employing a plurality of locks to control access to objects in each directory of the group, wherein the plurality of locks include,

a first set of locks to control opening of the objects, and

a second set of locks to control access to the data in the objects.

9. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform acts comprising:

identifying a group of computers to which a subtree of a hierarchical namespace used to store files is to be delegated;

generating a delegation certificate for the subtree, wherein the delegation certificate comprises;

a first digitally signed certificate identifying another group of computers responsible for managing a namespace root of the subtree; and

a second digitally signed certificate allowing authorization of the group of computers to manage the subtree to be traced to the other group of computers responsible for managing the namespace root;

digitally signing the delegation certificate; and

issuing the delegation certificate to the group of computers.

10. One or more computer readable media as recited in claim 9, wherein digitally signing the delegation certificate comprises having the delegation certificate digitally signed by a plurality of computers.

11. One or more computer readable media as recited in claim 9, wherein the group of computers comprise a Byzantine-fault-tolerant group.

12. One or more computer readable media as recited in 9, wherein the second digitally signed certificate comprises:

an identification of a path below the beginning of another subtree previously delegated to a third group of computers, wherein the third group of computers are the directory group performing generating;

an identification of a root of the other subtree delegated to the third group of computers;

an identification of the subtree; and

an identification of the members of the group of computers.

13. One or more computer readable media as recited in claim 12, wherein the computers in the third group of computers are the same computers as in the other group of computers.

14. One or more computer readable media as recited in 9, wherein the first digitally signed certificate is digitally signed by a certification authority (CA).

15. One or more computer readable media as recited in 9, wherein the delegation certificate further comprises one or more additional digitally signed certificates allowing a certificate chain to be established from the second digitally signed certificate to the first digitally signed certificate.

16. A computer comprising:

a processor;

a memory coupled to the processor; and

wherein the memory is to store a plurality of instructions to;

identify a group of computers to which a subtree of a hierarchical namespace used to store files is to be delegated;

generate a delegation certificate for the subtree, wherein the delegation certificate comprises;

a first digitally signed certificate identifying another group of computers responsible for managing a namespace root of the subtree; and

a second digitally signed certificate allowing authorization of the group of computers to manage the subtree to be traced to the other group of computers responsible for managing the namespace root;

digitally sign the delegation certificate; and

issue the delegation certificate to the group of computers.

17. A computer as recited in claim 16, wherein to digitally sign the delegation certificate is to have the delegation certificate digitally signed by a plurality of computers.

18. A computer as recited in claim 16, wherein the group of computers comprise a Byzantine-fault-tolerant group.

19. A computer as recited in 16, wherein the second digitally signed certificate comprises:

an identification of a path below the beginning of another subtree previously delegated to a third group of computers, wherein the third group of computers are the directory group performing generating;

an identification of a root of the other subtree delegated to the third group of computers;

an identification of the subtree; and

an identification of the members of the group of computers.

20. A computer as recited in claim 19, wherein the computers in the third group of computers are the same computers as in the other group of computers.

21. A computer as recited in 16, wherein the first digitally signed certificate is digitally signed by a certification authority (CA).

22. A computer as recited in 16, wherein the delegation certificate further comprises one or more additional digitally signed certificates allowing a certificate chain to be established from the second digitally signed certificate to the first digitally signed certificate.