Serverless distributed file system

• US 20050102268A1
• Filed: 12/17/2004
• Published: 05/12/2005
• Est. Priority Date: 03/26/2001
• Status: Active Grant

• 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.
• Granted Patent: US 7,240,060 B2
• Time in Patent Office: Days
• 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 device comprising:

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

means for 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;

means for digitally signing the delegation certificate; and

means for issuing the delegation certificate to the group of computers.

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

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

4. A device as recited in claim 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 device 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 device as recited in claim 1, wherein the first digitally signed certificate is digitally signed by a certification authority (CA).

7. A device as recited in claim 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 including means for storing 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 including means for storing 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 includes, to delegate management responsibility for a group of directories of the file system to a third set of the plurality of computers,

means for generating a delegation certificate for the group of directories,

means for digitally signing the delegation certificate, and

means for 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.