Distributed file system providing a unified name space with efficient name resolution

• US 5,701,462 A
• Filed: 12/29/1993
• Issued: 12/23/1997
• Est. Priority Date: 12/29/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shah, Milan, Cook, Peter J., Koneru, Sudheer, Whitney, Alan, Neeman, Yuval, Miller, Arnold S.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/174,910
• Time in Patent Office: 1,455 Days
• Field of Search: 395/600, 395/700, 395/800, 395/425, 395/400, 395/610, 395/611, 395/616, 395/614, 395/200.16, 379/88, 379/96, 379/207, 379/269
• US Class Current: 709/229
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A distributed file system uses objects to model the behavior of components of the distributed file system. Each object has an associated logical path name and physical address. An aggregation of all the logical path names comprises a distributed name space which can be logically partitioned into domains. Each domain includes a domain folder object which maps logical path names of objects in the domain containing the domain folder object, into addresses in the distributed system where the objects are stored. The addresses of the objects are used to access the objects in order to retrieve information from the distributed system.

Claims

1. In a distributed system having a distributed name space of objects wherein each object has both a logical name uniquely identifying the object in the distributed name space and a corresponding address, the objects being grouped into logical domains which are organized into a hierarchical structure wherein each domain may have one superior domain in the hierarchical structure and one or more subordinate domains in the hierarchical structure, a computer implemented method for accessing an object comprising the steps of:

providing a domain controller component for each domain, each domain controller component holding a prefix table which stores an entry for a logical name in the distributed name space of a domain controller component for any immediately superior domain and an entry for the logical name in the distributed name space for any domain controller component in any immediately subordinate domain, each said entry specifying an address of the respective domain controller component;

providing a first computer component for processing requests for information from the distributed system, the first computer component including another prefix table which stores entries for prefixes of logical names in the distributed name space and each entry specifies an address of a selected object in the distributed system that is named by the prefix;

receiving a request to access the selected object at the first computer component, wherein the request includes a logical name for the selected object to be accessed in the distributed system;

determining if an entry for a prefix of the logical name for the selected object from the request is stored in the prefix table of the first computer component;

in response to a determination that an entry for a prefix of the logical name for the selected object is not stored in the prefix table of the first computer component,

retrieving from the prefix table of the first computer component the address of the domain controller component for the domain containing the first computer component;

sending the logical name for the selected object from the request to the domain controller component for the domain containing the first computer component;

retrieving from the prefix table of the domain controller component for the domain containing the first computer component, an address of the selected object; and

accessing the object at the address that was retrieved from prefix table of the domain controller component which contains the first computer component.

2. The method of claim 1 wherein the first computer component may directly access objects in a local address space and wherein said method further comprises the steps of:

in response to a determination that an entry for a prefix of the logical name for the selected object is stored in the prefix table of the first computer component;

identifying a longest matching prefix among the prefixes having entries in the prefix table of the first computer component;

determining whether an object associated with the longest matching prefix is stored in the local address space that is directly accessible by the first computer component;

where it is determined that the object associated with the longest matching prefix is stored in the local address space obtaining an address for a portion of the memory; and

accessing the object associated with the longest matching prefix using the obtained address for the portion of memory.

3. The method of claim 2 wherein the distributed system includes a network server and the method further comprises the steps of:

where it is determined that the object associated with the longest matching prefix is not stored in the local address space that is directly accessible by the first computer component,

forwarding the request to access the selected object to the network server; and

attempting to resolve the logical name to an address at the network server.

4. The method of claim 3, further comprising the step of where the resolution of the logical name of the selected object to an address at the network server is successful, using the address to access the object.

5. The method of claim 4, further comprising the steps of:

where the resolution of the logical name of the selected object to an address at the network server is not successful,

retrieving from the prefix table of the first computer component the address of the domain controller component for the domain containing the first computer component;

sending the logical name of the selected object from the request to the domain controller component for the domain containing the first computer component;

retrieving from the prefix table of the domain controller component for the domain containing the first computer component, an address corresponding to the logical name of the selected object from the request; and

accessing the object at the retrieved address corresponding to the logical name from the request.

6. The method of claim 1 wherein the address of the domain controller component for the domain containing the first computer component is retrieved without broadcasting a request for the physical address.

7. The method of claim 1 wherein the step of providing a domain controller component includes the step of retrieving the logical names and the corresponding addresses of the domain controller components for the immediately superior domain and the immediately subordinate domains, wherein the method further comprises the steps of storing the retrieved logical names and corresponding addresses in the prefix table of the domain controller component.

8. The method of claim 1 wherein the logical name is a logical path name.

9. In a distributed system having its components logically partitioned into self-contained domains, wherein each domain includes a domain controller holding information about what is included in the domain and included in said components is a workstation having local storage, a method comprising the steps of:

providing a distributed file system that furnishes a distributed name space for objects in the distributed system;

receiving a request at the workstation to access a selected object in the distributed name space, said request identifying the selected object by its logical name in the distributed name space;

providing a first cache of logical names of objects and associated resolved addresses of the objects at the workstation;

accessing the first cache at the workstation to locate a longest matching portion of the logical name of the selected object to which access is requested that has already been resolved to an address;

where it is determined by accessing the first cache that a portion of the logical name of the selected object has not already been resolved to an address,

forwarding the request to a domain controller for the domain that contains the workstation;

providing a second cache at the domain controller of associated resolved addresses for logical names;

accessing the second cache to determine if a portion of the logical name of the selected object to which access is requested has already been resolved to an address;

where it is determined by accessing the second cache that a portion of the logical name of the selected object to which access is requested has been resolved to an address,

forwarding the portion of the logical name of the selected object that has been resolved and the address to which the portion of the logical name of the selected object has been resolved to the workstation;

storing the portion of the logical name and the address to which the portion of the logical name of the selected object has been resolved in the first cache at the workstation; and

repeating the above steps beginning with the accessing the first cache step.

10. The method of claim 9, further comprising the steps of:

where it is determined by accessing the first cache that a portion of the logical name of the object to which access is requested has already been resolved to an address,

determining whether the address to which the portion of the logical name of the selected object has been resolved refers to a storage location in the local storage of the workstation; and

where the address portion of the of the logical name of the selected object that has been resolved refers to a storage location in the local storage of the workstation, accessing the selected object using the address to which the portion of the logical name has been resolved.

11. The method of claim 10 wherein the distributed system further comprises a network server and the method further comprises the steps of:

where it is determined that the address of the portion of the logical name of the selected object that has been resolved refers to a storage location outside local storage of the workstation,

forwarding the logical name of the selected object to the network server; and

attempting name resolution of the logical name of the selected object into an address at the network server.

12. The method of claim 11, further comprising the steps of where the name resolution at the network server is successful in resolving the logical name of the selected object to an address, using the address to access the selected object.

13. The method of claim 11, further comprising the steps of:

where the name resolution at the network server is not successful in resolving the logical name of the selected object to an address,

forwarding the logical name of the selected object to a second domain controller for a domain which includes a portion of the distributed name space identified by the portion of the logical name of the selected object that was determined to be resolved by examining the first cache at the workstation;

providing another cache of logical names and associated resolved addresses at the second domain controller;

accessing the cache at the second domain controller to find an address for a portion of the logical name of the selected object that has already been resolved;

forwarding the address that was found at the cache of the second domain controller to the workstation; and

storing the address that was forwarded and associated portion of the logical name of the selected object in the first cache at the workstation.

14. In a distributed system organized hierarchically into logical domains, including a first domain and a second domain, a method comprising the steps of:

providing a distributed name space of objects wherein each object has a logical name that identifies the object within the name space and a corresponding address;

providing a domain controller for each domain, each domain controller holding a prefix table storing entries wherein each entry holds an address for a corresponding prefix of a logical name;

receiving a request to access an object in the first domain from the second domain;

providing a first referral in the prefix table in the domain controller of the second domain that refers to the domain controller in the first domain;

accessing the prefix table in the domain controller of the second domain to obtain the first referral that refers to the domain controller in the first domain;

providing a second referral in the prefix table in the domain controller in the first domain;

using the first referral to access the prefix table in the domain controller in the first domain to obtain the second referral; and

using the second referral to access the object.

15. The method of claim 14 wherein the distributed system includes a third domain and the second referral refers to a logical name in the third domain.

16. The method of claim 15 wherein the distributed system includes a network server in the first domain wherein the second referral refers to the network server in the first domain and wherein the step of using the second referral to access the object comprises the step of using the second referral to access the network server in the first domain and accessing the object via the network server.