Method and apparatus for constructing a DHT-based global namespace

A DHT-based global namespace (GNS) is constructed for a network system that includes network attached storage (NAS) devices, including at least one DHT-NAS device (a NAS device having DHT Functionalities) and at least one Existing-NAS device (a NAS device lacking DHT Functionalities). In a DHT Overlay Construction Phase, the DHT-NAS devices construct a DHT overlay. In an Initial Phase, the GNS is created above share folders in the Existing-NAS devices, with mapping of the share folders in the Existing-NAS devices to GNS paths distributed to a key lookup table in the DHT-NAS devices. Each mapping in the key lookup table includes a key, a GNS path, NAS type, IP address of the NAS, and the path within the NAS Share. There is no central GNS mapping table. In a Discovery Phase, the DHT-NAS devices discover the Existing-NAS devices to construct the GNS under the share folders. In a Working Phase, the DHT-NAS devices service GNS requests.

BACKGROUND OF THE INVENTION

The rapid growth of file-based information, and today's fast expanding and diverse business environment, have led to isolated information and storage islands within an organization. In these information and storage islands, various NAS (Network Attached Storage) devices having different performance characteristics and capacities, and even from different vendors, make it very difficult to share the information and manage the storage. End users need to know where files are located and map/mount folders shared through NFS (network file system) or CIFS (common internet file system) protocol, referred to as share folders (or simply share) hereafter, in order to access files from different NAS devices. On the other hand, system administrators must spend a great deal of time reconfiguring the system, optimizing the storage utilization, and/or migrating data, due to various needs. These requirements are complicated and may cause system downtime and corresponding interruption to the end users, which is very costly.

A Global Namespace (GNS) that can provide a single namespace, file location independent storage service to the end users, and allow system administrators to more efficiently utilize the storage, is therefore proposed and can be found in the existing art. To accommodate the amount of data growing daily, and given the fact that various NAS devices coexist, a GNS design is expected to have no limitation on scalability, and is also expected to support existing heterogeneous NAS devices. However, existing GNS solutions, such as DFS (Microsoft Distributed File System), NAS Switch ([US20030097454A1], [US2007072917B2]), and P2P (Peer-to-Peer) solutions, either have limited scalability or do not support heterogeneous NAS devices.

In the typical DFS solution, DFS links created for the GNS are shared among domain controllers and root servers. Any modification of the namespace causes the entire DFS metadata to be propagated to all domain controllers and root servers. The number of DFS links that can be created for the namespace is therefore limited in order to reduce the impact on network traffic.

In the typical NAS Switch solution, an appliance device manages the share folders of the NAS devices and constructs a pseudo file system for the clients. The appliance device appears as a single NAS server to the clients and as a single NAS client to the NAS devices. All namespace and user data access must go through the appliance device, making the appliance device a potential performance bottleneck.

Both DFS and NAS Switch solutions support heterogeneous NAS devices and maintain the local namespace within a NAS device; however, they manage the GNS information in a centralized manner with limited scalability.

On the other hand, with the concept of the DHT (Distributed Hash Table), structured P2P technologies have recently become increasingly popular for file sharing in large-scale, geographically-distributed storage systems. Chord (“Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications”, ACM SIGCOMM, 2001) and Tapestry (“Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing”, UC Berkeley, 2000) are two typical examples of DHT-based P2P technology found in the existing art. In a DHT-based P2P storage system, files and storage nodes (known as peers) are hashed into the same ID space. Each peer manages a portion of the ID space and cooperates with each other peer to share files, through a logical DHT overlay. By maintaining multiple file copies in the system, peers can join and leave the system dynamically, without affecting the file sharing service to the end users. A DHT-based P2P storage system is highly scalable without any central control point or performance bottleneck, and is highly available by self-repairing the system in the event of storage node join/leave. However, existing NAS devices do not have P2P functionality and cannot construct a P2P storage system, making the existing NAS devices unusable.

It may be possible to construct a P2P storage system, and utilize the existing heterogeneous NAS devices simply as additional storage capacity to the peers. However, this requires the system administrator to manually map/mount the share folders in the existing NAS devices to the peers, making it very difficult for the system administrator when the number of existing NAS devices is large or when peers fail. Further, the files stored in existing NAS devices are purely based on the hash value of the files (for example, the file name), making it impossible to maintain a meaningful local namespace within a NAS device, which is supported by both DFS and NAS Switch solutions.

Hence, there is an increasing need for a GNS solution that can maximize system scalability, support existing heterogeneous NAS devices, and at the same time, maintain a meaningful local namespace within a NAS device.

SUMMARY OF THE INVENTION

The present invention relates to a method and apparatus for constructing a GNS across heterogeneous NAS devices by using DHT-based P2P technology.

A GNS solution that can maximize system scalability, support existing heterogeneous NAS devices, and maintain a meaningful local namespace within a NAS device is represented by a method of constructing a distributed hash table (DHT)-based global namespace (GNS) for a network system including a plurality of network attached storage (NAS) devices connected to each other by a network, the NAS devices including at least one DHT-NAS device defined as a NAS device having DHT functionalities, and at least one Existing-NAS device defined as a NAS device that does not have DHT functionalities; the method comprising the steps of:

in a DHT overlay construction phase, constructing by each DHT-NAS device a DHT overlay of the DHT-NAS devices,

in an initial phase, the following steps performed by a processor of the DHT-NAS device executing a namespace initialization program:gathering information of the Existing-NAS devices, including IP addresses, share folders, and free storage capacity thereof, into an Existing-NAS information table;creating a GNS hierarchical namespace above the share folders based on the information gathered in the Existing-NAS information table;executing a key-value pair generation program, generating a (key, value) pair for each GNS path in the GNS hierarchical namespace, wherein the key is the hash value of the GNS path generated by invoking a hashing program, and wherein the value is generated with metadata information of the GNS path including the GNS path entry, the type of device in which the GNS path is stored, the IP address of the corresponding Existing-NAS device, and the path within the share folder; andstoring the (key, value) pairs to a key lookup table in the corresponding DHT-NAS devices through the DHT overlay;

in a discovery phase, the following steps performed by the processor of the DHT-NAS device executing a namespace discovery program:discovering the Existing-NAS devices identified in the key lookup table, andcreating the GNS hierarchical namespace under the share folders; and

in a working phase, the following steps performed by the processor of the DHT-NAS device executing a request processing program:checking whether a directory or file request to the GNS namespace has been received, andresponding to the request if a directory or file request to the GNS namespace has been received.

A GNS solution that can maximize system scalability, support existing heterogeneous NAS devices, and maintain a meaningful local namespace within a NAS device is further represented by a network system having a distributed hash table (DHT)-based global namespace (GNS), comprising:

a plurality of NAS devices connected to each other by a network, the NAS devices including at least one DHT-NAS device defined as a NAS device having DHT functionalities, and at least one Existing-NAS device defined as a NAS device that does not have DHT functionalities;

wherein each DHT-NAS device includes:a processor;a network interface via which the DHT-NAS device is coupled to the network;a NFS/CIFS protocol module;a storage management module;a storage interface arranged to receive and transmit block level data access from the storage management module to a storage and to receive and transmit a response from the storage to the storage management module, wherein the storage management module is arranged to organize the storage provided by the storage interface into shared storage for user files and free storage,a system memory; anda system bus via which the processor is coupled to each of the network interface, the NFS/CIFS protocol module, the storage management module, the storage interface, and the system memory;wherein the system memory holds a key lookup table, a DHT routing table, an Existing-NAS information table, a DHT routing program, a hashing program, a key-value pair generation program, a namespace initialization program, a namespace discovery program, and a request processing program;

wherein each Existing-NAS device includes:a network interface via which the Existing-NAS device is coupled to the network;a NFS/CIFS protocol module;a storage interface; anda storage management module arranged to organize a storage provided by the storage interface into shared storage for user files and free storage, wherein the storage interface of the Existing-NAS provides a logical storage volume to the storage management module;

wherein the processor executes the DHT routing program, stored in the system memory, to construct a DHT overlay of the DHT-NAS device in a DHT overlay construction phase;

the processor executes the namespace initialization program to perform the following in an initial phase:gathering information of the Existing-NAS devices, including IP addresses, share folders, and free storage capacity thereof, into the Existing-NAS information table;creating a GNS hierarchical namespace above the share folders based on the information gathered in the Existing-NAS information table;executing the key-value pair generation program, generating a (key, value) pair for each GNS path in the GNS hierarchical namespace,wherein the key is the hash value of the GNS path generated by invoking the hashing program, and wherein the value is generated with metadata information of the GNS path including the GNS path entry, the type of device in which the GNS path is stored, the IP address of the corresponding Existing-NAS device, and the path within the share folder; andstoring the (key, value) pairs to the key lookup table in corresponding DHT-NAS devices through the DHT overlay;

the processor executes the namespace discovery program to perform the following in a discovery phase:discovering the Existing-NAS devices identified in the key lookup table, andcreating the GNS hierarchical namespace under the share folders; and

the processor executes the request processing program to perform the following in a working phase:checking whether a directory or file request to the GNS namespace has been received, andresponding to the request if a directory or file request to the GNS namespace has been received.

There are 2 types of NAS devices in the system: DHT-NAS and Existing-NAS. DHT-NAS devices are NAS devices that have DHT functionalities. That is, DHT-NAS devices are NAS devices that are able to maintain a DHT routing table with partial information of other DHT-NAS devices, and cooperate with each other to form a DHT overlay by executing a DHT routing program. Existing-NAS devices are traditional NAS devices that do not have DHT functionalities, but already have user files stored in the share folders. The DHT-NAS devices form a logical DHT overlay with a global unique ID space, organized into a logical ring where the smallest ID succeeds the largest ID. The global namespace and the associated metadata are mapped to the same ID space and managed by the DHT-NAS devices in a distributed manner.

To construct the global namespace, a GNS hierarchy above the share folders of the Existing-NAS devices is first created and stored in the DHT overlay. The DHT-NAS devices will then construct the GNS hierarchy under the share folders by discovering the files in the share folders of the Existing-NAS devices. The discovered user files can be retained in the Existing-NAS devices to maintain the local namespace within the NAS devices.

To create a new file (or directory), the corresponding GNS metadata will be stored in the DHT overlay to the responsible DHT-NAS device whose Node ID is numerically closest clockwise in the ID space to the hash value of the file's GNS path, and the newly-created file may be stored in the DHT-NAS or Existing-NAS device which holds the parent directory. To access a file (or directory), a user can submit a request to any DHT-NAS device (or node). The request will then be routed to the responsible DHT-NAS device which manages the GNS metadata of the requested file. The responsible DHT-NAS node will then retrieve the file from the location found in the metadata and send the file to the DHT-NAS node which receives the initial user request.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1is an exemplary diagram illustrating an overall system according to a first embodiment of the present invention. The system includes, for example, multiple NAS devices (such as those identified by reference numerals0110and0120) and clients0130connected to a network0100(such as a LAN (local area network) or WAN (wide area network)). As shown, there are two types of NAS devices: a DHT-NAS0110and an Existing-NAS0120. DHT-NAS devices0110are NAS devices that are able to maintain a DHT routing table with partial information of other DHT-NAS devices0110, and cooperate with each other to form a DHT overlay by executing a DHT routing program. Existing-NAS devices0120are traditional NAS devices that do not have DHT functionalities, but already have user files stored in the share folders. A client0130is a device (such as a PC) that utilizes the global namespace (GNS) service to access any data in the system.

FIG. 2shows a high level overview of a logical system architecture that may be employed in the first embodiment, where a plurality of DHT-NAS devices0110cooperate with each other and form a logical DHT overlay0200. The DHT-NAS devices communicate with and discover the files in the Existing-NAS devices0120and construct a global namespace in the DHT Overlay.

FIG. 3is a block diagram illustrating examples of components of a DHT-NAS device0110. A DHT-NAS device may consist of, but is not limited to, a processor0310, a system memory0320, a network interface0330, a NFS/CIFS (network file system/common internet file system) protocol module0340, a storage management module0350, a storage interface0360, and a system bus0370. The system memory0320further includes a key lookup table0321, a DHT routing table0322, an Existing-NAS information table0323, a DHT routing program0324, a Hashing program0325, a Key-Value pair generation program0326, a Namespace initialization program0327, a Namespace discovery program0328, and a Request processing program0329, which are used to realize the DHT overlay0200and virtualize the global namespace. Each program will be further described hereafter.

The processor0310represents a central processing unit that executes the programs. Commands and data communicated among the processor0310and other components are transferred via the system bus0370. The network interface0330connects the DHT-NAS0110to the network0100and is used for communication with other DHT-NAS devices0110, Existing-NAS devices0120, and Clients0130. The NFS/CIFS protocol module0340implements both the client and server functions of the NFS/CIFS protocol. The NFS/CIFS protocol module0340sends NFS/CIFS requests to other DHT-NAS devices0110and Existing-NAS devices0120, and serves the NFS/CIFS requests sent from the other DHT-NAS devices0110and Clients0130. The storage interface0360manages the storage from a storage area network (SAN) or an internal HDD array, and provides a logical storage volume to the storage management module0350. The Storage interface0360receives and transmits block level data access from the Storage management module0350to the SAN or internal HDD array, and receives and transmits the response from the SAN or internal HDD array to the Storage management module0350. The storage management module0350organizes the storage provided by the storage interface0360into shared storage0351and free storage0352. The user files are stored in the shared storage0351and exported for access through the NFS/CIFS protocol module0340. The free storage0352may be utilized by the DHT-NAS device0110itself to expand the shared storage0351.

To construct the DHT overlay0200, each DHT-NAS device0110is assigned a Node ID and joins the overlay0200by following the DHT routing protocol implemented in the DHT routing program0324. The DHT routing protocol can be any DHT-based P2P routing protocol found in the existing art, such as Chord or Tapestry. A DHT-NAS device0110obtains its Node ID by executing the Hashing program0325to calculate the hash value of its IP address. With a collision-free hash function implemented in the Hashing program0325, such as 128-bit or 160-bit SHA-1, the Node ID assigned to each DHT-NAS device0110will be globally unique. It should be noted that in this description, we use decimal ID space, instead of binary bits, to represent the Node ID, for simplicity of explanation.

FIG. 4is a table that shows an example of mapping an IP address0410to a Node ID0430, by calculating the hash value0420of the IP address0410. In this example, an 8-bit ID space [0, 127] is illustrated. As an example, the hash value of a DHT-NAS device's IP address0410, 192.168.1.10, is calculated as 10, and therefore, the Node ID of the DHT-NAS device0110is assigned to #10.

Each DHT-NAS device0110in the DHT overlay0200is responsible for a range of ID space that has no overlap with the ID ranges managed by other DHT-NAS devices0110.FIG. 5shows, at0500, the ID range0520managed by each DHT-NAS device0110in a DHT overlay0200with the ID space [0, 127]0510. It should be noted that the ID space0510in the DHT overlay0200forms a circle, and therefore the ID range0520managed by the DHT-NAS device0110with Node ID #120is (90˜120], the ID range0520managed by the DHT-NAS device0110with Node ID #10is (120˜10], and the ID range0520managed by the DHT-NAS device0110with Node ID #30is (10˜30], and so on.

FIG. 6shows an example of a DHT routing table0322maintained in a DHT-NAS device0110(referred to below as the current DHT-NAS device0110) which, in this example, is DHT-NAS10. The DHT routing table0322stores information of other DHT-NAS devices0110in the DHT overlay0200known by the current DHT-NAS device0110, and will be used and updated by the DHT routing program0324. The DHT routing table has at least two columns, for the Node ID0610and IP address0620of the other DHT-NAS devices0110. The first entry and the last entry in the DHT routing table are referred to as the successor and the predecessor, respectively. In this example, for DHT-NAS10, the successor is DHT-NAS30, and the predecessor is DHT-NAS120. It should be noted that the Node IDs of the predecessor and current DHT-NASes coordinately define the ID range0520managed by the current DHT-NAS device0110.

FIG. 7is a block diagram illustrating an example of the components in an Existing-NAS device0120. An Existing-NAS device may consist of, but is not limited to, a network interface0710, a NFS/CIFS (network file system/common internet file system) protocol module0720, a storage management module0730, and a storage interface0740. The network interface0710connects the Existing-NAS device0120to the network0100and is used for communication with DHT-NAS devices0110. The NFS/CIFS protocol module0720implements the server functions of NFS/CIFS protocol, and serves the NFS/CIFS requests sent from DHT-NAS devices0110. Similar to a DHT-NAS device0110, the storage interface0740manages the storage from a storage area network (SAN) or an internal HDD array, and provides a logical storage volume to the storage management module0730. The storage management module0730organizes the storage provided by the storage interface0740into shared storage0731and free storage0732. The user files are stored in the shared storage0731and exported for access through the NFS/CIFS protocol module0720. The free storage0732may be utilized by the Existing-NAS device0120itself to expand the shared storage0731.

FIG. 8is a flow diagram illustrating exemplary steps to construct the GNS. In Step0810(the DHT Overlay Construction Phase), DHT-NAS devices0110cooperate with each other and construct a DHT overlay0200. In Step0820(the Initial Phase), the first DHT-NAS device0110that joins the DHT overlay0200creates the GNS namespace above the share folders in Existing-NAS devices0120. In Step0830(the Discovery Phase), the DHT-NAS devices0110discover the Existing-NAS devices0120to construct the GNS namespace under the share folders. After Step0830, the system remains at the Working Phase (Step0840) to serve the GNS requests. These steps will be further described hereafter.

FIG. 9is a flow diagram of an example of the DHT overlay construction phase (Step0810). DHT-NAS devices0110construct the DHT overlay0200by executing the DHT routing program0324. In Step0910, the DHT routing program0324in a DHT-NAS device0110.invokes the Hashing program0325. In Step0920, the DHT-NAS device0110obtains its Node ID0430by calculating the hash value0420of its IP address0410. In Step0930, the DHT-NAS device0110checks whether it is the first DHT-NAS device0110in the system. If YES, in Step0940, the DHT-NAS device0110constructs the DHT overlay0200with itself as the single DHT-NAS device0110. If NO in Step0930, in Step0950, the DHT-NAS device0110sends a join request to any of the existing DHT-NAS devices0110, to join the DHT overlay0200, by following the DHT routing protocol implemented in the DHT routing program0324.

FIG. 10is an example of a flow diagram of the Initial Phase (Step0820). The Initial Phase is carried out by the first DHT-NAS device0110that joins the DHT overlay0200by executing the Namespace initialization program0327. In Step1010, the DHT-NAS device0110gathers the information of Existing-NAS devices0120, such as the IP address, share folders, and free storage capacity thereof, into the Existing-NAS information table0323.FIG. 11shows an example of the Existing-NAS information table0323illustrating the gathered information of Existing-NAS devices0120. In this example, there are two Existing-NAS devices0120, Existing-NAS1and Existing-NAS2, having IP addresses 192.168.1.11 and 192.168.2.22, respectively. Existing-NAS1has a share folder S_A and Existing-NAS2has a share folder S_B. All of the above information is gathered into the Existing-NAS information table0323which consists of, but is not limited to, four columns (IP Address1110, NAS ID1120, share folder1130, and free capacity1140).

Referring back toFIG. 10, in Step1020, the DHT-NAS device0110creates the GNS hierarchical namespace above the share folders based on the information gathered in the Existing-NAS information table0323.FIG. 12shows one possible implementation1200by creating the GNS root directory “/” and one sub-directory (“/A” and “/B” in this example) for each share folder1130in Existing-NAS devices0120. Of course, a more meaningful and complicated GNS hierarchy with more than two levels can be created in Step1020. The example shown inFIG. 12is for simplicity of explanation.

Referring back toFIG. 10again, in Step1030, the DHT-NAS device0110invokes the Key-Value pair generation program0326to generate a (key, value) pair for each GNS path entry created in Step1020.FIG. 13is a flow diagram illustrating exemplary steps of the Key-Value pair generation program0326. In Step1310, the DHT-NAS device0110invokes the Hashing program0325to generate the Key for the GNS path. In Step1320, the Value is generated with the metadata information including, but not limited to, the GNS path, type, IP address of the corresponding Existing-NAS device0120, share folder, and the path within the share folder. These metadata information will be further described inFIG. 16.

FIG. 14shows an example of mapping GNS path1410to key1430, by calculating the hash value1420of the GNS path. In this example, the hash value of the root directory “/” is 3, and therefore the key generated for “I” is #003. Similarly, the keys generated for the GNS paths “/A” and “/B” are #013and #005, respectively.

Referring back toFIG. 10again, in Step1040, the DHT-NAS device0110stores the (key, value) pairs generated in Step1030to the responsible DHT-NAS devices0110through the DHT overlay0200.

It should be noted that the mapping of the share folders in Existing-NAS devices0120to the GNS path entries1410are distributed to the key lookup table0321in DHT-NAS devices0110(refer toFIG. 16). There is no central GNS mapping table required in the presented invention.

FIG. 15is a flow diagram illustrating exemplary steps constituting Step1040, to store a (key, value) pair to the responsible DHT-NAS device0110through the DHT overlay0200. In Step1510, the DHT-NAS device0110submits a Put (key, value) request to the DHT routing program0324. In Step1520, the DHT-NAS device0110checks whether the key in the request belongs to the ID range0520for which it is responsible. If NO, in Step1530, the DHT-NAS looks up the DHT routing table0322to find another DHT-NAS device0110whose Node ID0610is next numerically closer to the key, e.g., next clockwise in the ID space as inFIG. 5(to the successor to the DHT-NAS). In Step1540, the DHT-NAS device0110sends the Put (key, value) request to the DHT-NAS device0110found in Step1530. Then, the Step1520is repeated by the DHT-NAS device0110found in Step1530. If YES in the repeated Step1520, in Step1550, the DHT-NAS device0110extracts the metadata information from the (key, value) pair and inserts the information into the key lookup table0321.

FIG. 16shows an example of the structure of key lookup table0321maintained in a DHT-NAS device0110(in this example, DHT-NAS10). The key lookup table0321consists of, but is not limited to, six columns, including key1610, GNS path1620, type1630, IP address of the NAS1640, the path within NAS Share1650, and others1660. The key1610is the hash value of the GNS path1620. Type1630is either “P2P” or “NAS”. The “NAS” type means that the GNS path entry is currently hosted in an Existing-NAS0120, while the “P2P” type means that the GNS path entry is stored at a DHT-NAS device0110. The IP address of the NAS1640and the path within the NAS Share1650further describe the location of the GNS path entry within a NAS device. Others1660are used to store other meaningful information about the GNS path entry (for example, the created time, access control, or sub-folder information for a “P2P”-type directory GNS path entry.

FIG. 17is a flow diagram of the Discovery Phase (Step0830). A DHT-NAS device0110will execute the Namespace Discovery program0328when inserting a “NAS”-type GNS path entry into the key lookup table0321. In Step1710, the DHT-NAS device0110discovers the directories and files under the path within NAS Share1650in the corresponding Existing-NAS device0120with the IP Address1640. In Step1720, the DHT-NAS device0110checks whether any directory or files are found (or discovered). For each directory or file found, in Step1730, the DHT-NAS device0110constructs the GNS path by combining the GNS path information of the parent directory. For example, inFIG. 18, for the file (or directory) “S_B/B2” discovered in an Existing-NAS0120with IP address 192.168.2.22, the GNS path is set to “/B/B2” as the GNS path for the parent directory “S_B” is “/B”.

Referring back toFIG. 17, in Step1740, the DHT-NAS device0110invokes the Key-Value pair generation program0326to generate a (key, value) pair for the GNS path entry created in Step1730. Thereafter, the (key, value) pair is stored to the responsible DHT-NAS devices0110through the DHT overlay0200, which has already been described in Step1040(refer toFIG. 15). This process (Steps1720,1730,1740, and1040) repeats until no more directories/files can be found.

FIG. 19shows an example of the GNS hierarchy1200constructed after the Discovery Phase (Step0830), given the Existing-NAS1and Existing-NAS2inFIG. 11, and the GNS hierarchy1200above the share folder created inFIG. 12.

FIG. 20is an example of a flow diagram illustrating the Working Phase (Step0840). Each DHT-NAS device0110executes the Request processing program0329during the Working Phase. In Step2010, the DHT-NAS device0110checks whether any GNS request has been received. If NO, the DHT-NAS device0110remains at the Working Phase and waits for GNS requests. If YES, in Step2020, the requested GNS path is extracted from the request, and in Step2030, the key of the GNS path1130is calculated by executing the using the Hashing program0325. In Step2040, the DHT-NAS device0110checks whether the key belongs to the ID range0520for which it is responsible. If NO, in Step2050, the DHT-NAS device0110looks up the DHT routing table0322to find another DHT-NAS device0110whose Node ID0610is numerically closer clockwise in the ID space to the key. In Step2060, the DHT-NAS device0110sends the GNS request to the DHT-NAS device0110found in Step2050, and remains at the Working Phase, repeating Step2010to serve other GNS requests. If YES in Step2040, in Step2070, the DHT-NAS device0110will process the GNS request and remain at the Working Phase, repeating Step2010to serve other GNS requests.

FIG. 21is an example of a flow diagram further illustrating the Step2070to process a GNS request. In Step2110, the DHT-NAS device0110checks whether the request is to read an existing GNS namespace, to create a new GNS path entry, or to migrate a file/directory from one NAS device to another. If it is a read request, in Step2120, the read-request process is invoked. If it is a create request, in Step2130, the create-request process is invoked. If it is a migrate request, in Step2140, the migrate-request process is invoked.

FIG. 22is a flow diagram illustrating the read-request process (Step2120). In Step2210, the DHT-NAS device0110searches the key lookup table0321to look up an entry with the requested key. In Step2220, the DHT-NAS device0110checks whether the requested key is found in the key lookup table0321. If YES, in Step2230, the DHT-NAS device0110retrieves the requested GNS file or directory from the location (1640and1650) recorded in the key lookup table. Thereafter, in Step2240, the DHT-NAS device0110returns the retrieved GNS file or directory to the DHT-NAS device0110issuing the GNS request. If NO in Step2220, in Step2250, the DHT-NAS device0110returns a “File Does Not Exist” message to the DHT-NAS device0110issuing the GNS request.

FIG. 23is an example of a flow diagram illustrating the create-request process (Step2130). In Step2310, the DHT-NAS device0110further extracts the GNS path of the parent directory of the requested file/directory, and calculates the key of the parent GNS path by executing the Hashing program0325, in Step2320. In Step2330, the DHT-NAS device0110retrieves the (key, value) pair of the parent directory from the responsible DHT-NAS node0110through the DHT overlay0200. Step2330is very similar to Step1040, except that the request submitted to the DHT overlay is Get (key, value), instead of Put (key, value). In Step2340, the DHT-NAS device0110checks whether the type1630of parent directory is “P2P” or “NAS”. If the type is “NAS”, in Step2350, the new directory/file is created under the parent directory in the Existing-NAS device0120holding the parent directory. Otherwise, if the type is “P2P” in Step2340, in Step2360, the new directory/file is created to a local share folder in the DHT-NAS device0110. In Step2370, the DHT-NAS device0110updates the parent directory to include the newly-created directory/file. In Step2380, the DHT-NAS device0110inserts the GNS metadata information of the created directory/file into the key lookup table0321.

FIGS. 24,25,26,27and28together illustrate an example of a GNS namespace, GNS namespace distribution among the NAS devices, and the key lookup table maintained in DHT-NAS10and DHT-NAS30, during the create-request process (Step2130).

FIG. 24shows an example of the GNS namespace, where file “/A/A1/a1” and directory “/C” are the two new GNS path entries created during the Working Phase (compare the GNS namespace inFIG. 19).FIG. 25shows an example of the mapping1400from GNS path1410to key1430, by calculating the hash value1420of the GNS path1410.

FIG. 26shows an example of the GNS namespace distribution among the NAS devices. The ID range0520managed by DHT-NAS10is (120˜10] and the ID range managed by the DHT-NAS30is (10˜30]. Before the file “/A/A1/a1” and the directory “/C” are created, the existing share S_A in Existing-NAS1hosts the entire directory “/A”, and the existing share S_B in Existing-NAS2hosts the entire directory “/B” in the GNS namespace (refer to the example inFIG. 11). As the key of the GNS path “/A/A1/a1” is008(refer toFIG. 25), the GNS metadata information of file “/A/A1/a1” is stored in the key lookup table0321of DHT-NAS10, as shown inFIG. 27. Referring back toFIG. 26, the real file “S_A/A1/a1” is created in Existing-NAS1for “/A/A1/a1”, due to the type1630of the parent GNS path “/A/A1” being “NAS” and the physical location “S_A/A1” in Existing-NAS1. On the other hand, as the key of the GNS path “/C” is017(refer toFIG. 25), the GNS metadata information of directory “/C” is stored in the key lookup table0321of DHT-NAS30, as shown inFIG. 28. Referring back toFIG. 26again, due to the type of the parent GNS path “/” being “P2P”, the directory “/C” may be created in a local share folder managed by DHT-NAS30. In this example, the directory “/C” is stored in DHT-NAS30, by creating a new share folder “S_C”.

FIG. 29is a flow diagram illustrating the migrate-request process (Step2140). In Step2910, the DHT-NAS device0110further extracts the migration destination (such as the NAS IP address and the share folder) and the GNS path of the parent directory, and calculates the key of the parent GNS path by executing the Hashing program0325in Step2920. In Step2930, the DHT-NAS device0110retrieves the (key, value) pair of the parent directory from the responsible DHT-NAS node0110through the DHT overlay0200. In Step2940, the DHT-NAS device0110retrieves the directory/file to be migrated from the location recorded in the key lookup table0321. In Step2950, the DHT-NAS device0110checks whether the location of the parent directory is at the migration destination. If NO, in Step2960, the DHT-NAS device0110simply stores the directory/file to the destination. If YES in Step2950, in Step2970, the DHT-NAS device0110further checks whether the type1630of the parent directory is “P2P” or “NAS”. If the type is “P2P”, the DHT-NAS device0110again stores the directory/file to the destination. Otherwise, if the type is “NAS”, in Step2980, the DHT-NAS device0110stores the directory/file to the destination under the GNS parent directory. In Step2990, the DHT-NAS device0110updates the location metadata (1640and1650) of the migrated directory/file in the key lookup table to the real location in the destination NAS device.

A second embodiment of the present invention will be described next. The explanation will mainly focus on the differences from the first embodiment.

In the first embodiment, all the Existing-NAS devices0120are treated as being the same when constructing the GNS, without differentiating the performance of the NAS devices. To migrate a file from one NAS device to another, the client0130needs to provide the IP address of the destination NAS device.

FIG. 30shows an example of an overall system according to the second embodiment, in which different tiers of Existing-NAS devices0120are connected to the network0100. In this example, a Tier1 NAS device (such as an FC NAS)3010has better performance than a Tier2 NAS device (such as a SATA NAS)3020. It should be noted that the system can consist of more than two NAS tiers. The example shown inFIG. 30is for simplicity of explanation.

During the DHT overlay construction phase (Step0810), a hierarchical DHT overlay3100is constructed as shown inFIG. 31. A Tier1 DHT overlay3110and a Tier2 DHT overlay3120are constructed to virtualize the Tier1 Existing-NAS devices3010and Tier2 Existing-NAS devices3020, respectively. There is also a Global DHT overlay3130, involving all the DHT-NAS devices0110in the system. A DHT-NAS device0110belongs to only one Tier DHT overlay and the Global DHT overlay3130.

FIG. 32shows an example of the information of Existing-NAS devices3010and3020gathered in the Existing-NAS information table0323, including the tier information3210, during the Initial Phase (Step0820). The tier information3210is then included in the (key, value) pairs generated in the Initial Phase (Step1030) and the Discovery Phase (Step1740), by the Key-Value pair generation program0326. As a result, the tier information3210is stored in the key lookup table0321of a DHT-NAS device0110, as shown inFIG. 33. The tier of the NAS3310indicates the tier to which the NAS holding the GNS entry belongs.

During the Working Phase (Step0840), when receiving a GNS request to migrate a file, a DHT-NAS device0110extracts the destination tier information3210from the request and sends the request to the responsible DHT-NAS device0110in the specific tier DHT overlay3110or3120. The responsible DHT-NAS device0110then checks whether the parent GNS path entry is also stored in the same tier DHT overlay. If YES and the type of the parent GNS path entry is “NAS”, the file is stored in the Existing-NAS device0120hosting the parent GNS entry. Otherwise, the file is stored in the responsible DHT-NAS device0110in the specific tier DHT overlay.

Therefore, with the second embodiment, it is easier for a client0130to migrate a file from one NAS device to another, by providing only the destination tier number instead of the IP address of the destination NAS device.

A third embodiment of the present invention will be described in the following.

In the first and second embodiments, the geographical locations of NAS devices are omitted, making it difficult to migrate a file from one location to another, or to create a file at specific location.

FIG. 34shows an example of an overall system according to the third embodiment, in which NAS devices0110,0120and clients0130are distributed at different locations3430,3440. At each location, there is a local network3410,3420where the NAS devices0110,0120and clients0130at the location are connected. It should be noted that NAS devices can be geographically located at more than two locations. The example shown inFIG. 34is for simplicity of explanation.

Similar to the second embodiment, during the DHT overlay construction phase (Step0810), a hierarchical DHT overlay3500is constructed as shown inFIG. 35. A Local DHT overlay3510,3520is constructed for each location to virtualize the Existing-NAS devices0120at the location. There is also a global DHT overlay3530, involving all the DHT-NAS devices0110in the system. A DHT-NAS device0110belongs to only one Local DHT overlay and the global DHT overlay3530.

FIG. 36shows the information of Existing-NAS devices0120gathered in the Existing-NAS information table0323, including the location information3610, during the Initial Phase (Step0820). The location information3610is then included in the (key, value) pairs generated in the Initial Phase (Step1030) and the Discovery Phase (Step1740), by the Key-Value pair generation program0326. As a result, the location information3610is stored in the key lookup table0321of a DHT-NAS device0110, as shown inFIG. 37. The location of NAS3710indicates the location to which the NAS holding the GNS entry belongs.

During the Working Phase (Step0840), when receiving a GNS request to migrate a file, a DHT-NAS device0110extracts the destination location information3610from the request and sends the request to the responsible DHT-NAS device0110in the specific local DHT overlay3510or3520. The responsible DHT-NAS device0110then checks whether the parent GNS path entry is also stored in the same local DHT overlay. If YES and the type of the parent GNS path entry is “NAS”, the file is stored in the Existing-NAS device0120hosting the parent GNS entry. Otherwise, the file is stored in the responsible DHT-NAS device0110in the specific local DHT overlay.

Similarly, when receiving a GNS request to create a new file, a DHT-NAS device0110extracts the destination location information3610from the request, and sends the request to the responsible DHT-NAS device0110in the specific local DHT overlay. The responsible DHT-NAS device0110then checks whether the parent GNS path entry is also stored in the same local DHT overlay. If YES and the type of the parent GNS path entry is “NAS”, the file is then created in the Existing-NAS device0120hosting the parent GNS entry. Otherwise, the file is created in the responsible DHT-NAS device0110in the specific local DHT overlay.

Therefore, with the third embodiment, it is easier for a client0130to migrate a file from one location to another, or create a file at a specific location, by simply providing the destination location information3610.

It should be noted that the second and third embodiments can be combined together to provide a GNS across different tiers of geographically distributed NAS devices, by storing both the tier information3210and location information3610in the key lookup table0321.

While the invention has been described in terms of its preferred embodiments, numerous modifications may be made without departing from the spirit and scope of the present invention. It is intended that all such modifications fall within the scope of the appended claims.