Serverless distributed file system

• US 8,112,452 B2
• Filed: 01/29/2009
• Issued: 02/07/2012
• Est. Priority Date: 03/26/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Adya, Atul, Cermak, Gerald, Douceur, John R., Theimer, Marvin M., Wattenhofer, Roger P., Bolosky, William J.
• Primary Examiner(s): Wong, Dong
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US12/361,678
• Publication Number:
  US 20090132552A1
• Time in Patent Office: 1,104 Days
• Field of Search: 707/747, 707/797, 707/821, 707/829, 707/791, 707/796, 707/802, 707/828, 707/953, 707/956, 707/966
• US Class Current: 707/802
• 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 used in managing a serverless distributed file system, the method comprising:

managing directories of the file system using Byzantine groups and a hierarchical namespace; and

managing files within the directories without using Byzantine groups by saving replicas of the files to fewer computers than exist in the Byzantine groups.

2. A method as recited in claim 1, wherein each directory includes one or more directory entries corresponding to one or more of the files, and wherein each directory entry includes:

an identification of the file;

an identification of a plurality of computers where replicas of the file are stored; and

file verification data comprising;

at least one of a file identification number, a file version number, and a name of a user whose signature is on the file; and

a hash value generated from applying a cryptographically secure hash function to the file.

3. A method as recited in claim 1, wherein each of a plurality of computers in the serverless distributed file system need not trust the other ones of the plurality of computers.

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

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

generating a delegation certificate for the subtree;

digitally signing the delegation certificate; and

issuing the delegation certificate to the group of computers.

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

6. A method implemented in a computing device of a serverless distributed file system, the method comprising:

checking a local cache of pathnames to Byzantine-fault-tolerant directory group mappings to determine a mapping for a longest prefix of a desired pathname; and

if the entire pathname is mapped to a Byzantine-fault-tolerant directory group using the local cache, then accessing a member of the Byzantine-fault-tolerant directory group to determine where to locate a file corresponding to the pathname, and otherwise repeating the following until the entire pathname is mapped to a Byzantine-fault-tolerant directory group, obtaining, from a member of the Byzantine-fault-tolerant directory group corresponding to the longest prefix of the desired pathname, mappings for a relevant subtree from the longest prefix, and

if the entire pathname is not mapped to a Byzantine-fault-tolerant directory group using the relevant subtree from the longest prefix, then repeating the obtaining with the longest prefix being the previously used longest prefix concatenated with the relevant subtree.

7. A method as recited in claim 6, wherein the mappings are obtained from the member of the directory group via a delegation certificate digitally signed by one or more members of the directory group.

8. A method as recited in claim 6, further comprising adding the mappings for the relevant subtree to the local cache.

9. A method as recited in claim 6, wherein the longest prefix includes one or more directories in addition to a namespace root.

10. A method as recited in claim 6 further comprising:

generating a directory entry corresponding to a file to be stored in the serverless distributed file system;

saving the directory entry to each of a first plurality of computers that are part of a Byzantine-fault-tolerant group; and

saving the file to each of a second plurality of computers, wherein fewer computers are in the second plurality of computers than are in the first plurality of computers, and wherein at least one of the second plurality of computers is not part of the Byzantine-fault-tolerant group.

11. A method as recited in claim 10, further comprising:

receiving, prior to generating the directory entry, an encrypted file name of the file; and

receiving, prior to saving the file to each of the second plurality of computers, the file in encrypted form.

12. A method as recited in claim 10, wherein at least one of the second plurality of computers is part of the Byzantine-fault-tolerant group.

13. A computer comprising:

a processor; and

a memory coupled to the processor, wherein;

the memory is to store a plurality of instructions to implement a file system using a hierarchical namespace to store files,

the file system is distributed across a plurality of computers including the computer,

each of the plurality of computers can operate as both a client computer and a server computer,

each of the plurality of computers need not trust the other ones of the plurality of computers,

files and corresponding directory entries are stored in the file system, and

for any given file that is stored in the file system, a number of copies of the file and a number of copies of the corresponding directory entry are stored, and a lesser number of copies of the file are stored than the number of copies of the corresponding directory entry that are stored.

14. A computer as recited in claim 13, wherein the file system stores directory entries using Byzantine groups and objects corresponding to the directory entries without using Byzantine groups.

15. A computer as recited in claim 13, wherein the computer is part of a directory group responsible for managing a set of directories in the hierarchical namespace, and wherein the plurality of instructions are further to cause the computer to identify a new directory group and delegate responsibility for managing a subset of the set of directories to the new directory group.

16. A computer as recited in claim 15, wherein the plurality of instructions are further to cause the computer to:

identify a group of computers to be part of the new directory group;

generate a delegation certificate for the subset;

digitally sign the delegation certificate; and

issue the delegation certificate to the group of computers.

17. A computer as recited in claim 13, wherein the computer includes a cache of pathname to directory group mappings, and wherein the plurality of instructions are further to cause the computer to determine where to locate a file corresponding to a pathname in the file system by performing the following acts:

checking the cache to determine a mapping for a longest prefix of a desired pathname; and

if the entire pathname is mapped to a directory group using the cache, then accessing a member of the directory group to determine where to locate the file, and otherwise repeating the following until the entire pathname is mapped to a directory group, obtaining, from a member of the directory group corresponding to the longest prefix of the desired pathname, mappings for a relevant subtree from the longest prefix, and

if the entire pathname is not mapped to a directory group using the relevant subtree from the longest prefix, then repeating the obtaining with the longest prefix being the previously used longest prefix concatenated with the relevant subtree.

18. A computer as recited in claim 13 being one of the plurality of computers wherein:

the plurality of computers including the computer comprise at least two sets;

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 directory Byzantine group; and

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 the quantity of replicas is less than the quantity of computers in the Byzantine group; and

one or more of the plurality of computers are in both the first set and the second set.

19. A computer as recited in claim 18, wherein the directory information includes a plurality of directory entries, and wherein each directory entry on a computer in the first set includes an indication of each computer in the second set where a copy of a file corresponding to the directory entry is located.

20. A computer as recited in claim 18, wherein the replicas comprise encrypted versions of the file being stored.