CN101692239A - Method for distributing metadata of distributed type file system - Google Patents

Abstract

The invention discloses a method for distributing metadata of a distributed type file system. The method uses a catalogue of the file system as a basic unit of Hash, adopts an extensible Hash method to distribute the metadata to each metadata server to ensure that clients can position the position of the metadata; the metadata has high accessing efficiency, even distribution and balanced load; meanwhile, the method maintains storage locality of the catalogue, realizes conveniently prefetching, and improves the accessing efficiency. A unique and unchanged identifier is given to the catalogue to avoid metadata migration caused by the path name of Hash and improve the system performance; participation or exit of the metadata server cannot cause redistribution of mass metadata so as to furthest reduce the metadata migration and ensure high expandability.

Description

A Distributed File System Metadata Allocation Method

technical field

The present invention relates to the field of distributed file systems, and more specifically, to a distributed file system metadata distribution method for clustered metadata servers (Metadata Server: MDS).

Background technique

With the emergence of object storage devices (Object Storage Device: OSD), it provides a basis for building a large-scale distributed file system of PB (10 to the 15th power byte) level. In order to manage a large-scale distributed file system based on OSD more effectively, file metadata and data access are often separated, and all metadata of the file system is managed by an independent metadata server cluster, while the cluster composed of OSD is dedicated to Manage and store files. Figure 1 shows the structure of the distributed file system in this case.

Metadata is data describing data, and the metadata of a file system includes basic attribute information and directory structure information of files. Although its size only accounts for a small part of the entire system size, metadata operations are very frequent, accounting for more than 50% of the entire file system operation, making metadata management very important. A good metadata distribution method can make the system achieve high performance and high scalability. Existing methods mainly include Static Subtree Partition, Dynamic Subtree Partition, Hash and so on.

The static subtree partitioning method divides the entire file system into several directory subtrees, and assigns the subtrees to different MDSs. The advantage of this method is that the distribution of metadata is simple, and it is convenient to develop the storage locality of the directory. The disadvantage is that the scalability is poor, and the load cannot be effectively balanced, and it is easy to cause hot-pot problems.

The dynamic subtree partitioning method is based on the static subtree partitioning method, and uses the method of dynamically decomposing subtrees to balance the load, that is, when a certain subtree structure is too large or the access is frequent, the subtree is dynamically decomposed into two parts. One or more subtrees, and migrate the decomposed subtrees to other MDSs to balance the load. However, this approach does not solve the scalability problem, and there is also a large amount of metadata migration

Hashing methods distribute metadata based on the hash of some unique file identifier (eg, inode number, pathname). The advantage of this method is that the location of the metadata can be directly calculated, and the metadata is evenly distributed to each MDS to obtain a better load balance, but it loses the storage locality of the file system directory, making path traversal consume a lot . Moreover, when a file (or directory) is renamed or the number of metadata servers increases or decreases, its hash value changes accordingly, which will lead to a large amount of metadata migration, causing a sharp drop in system performance.

Given that existing metadata allocation methods cannot meet the high-performance and high-scalability requirements of distributed file systems for metadata server clusters, we propose a directory-based scalable hashing method to allocate metadata. This method inherits the original advantages of the hash method - load balancing, fast query speed, and can maintain directory locality, allowing directory name modification without causing data migration, adding or adding metadata servers will only cause a small amount of metadata migration, greatly improving scalability.

Contents of the invention

The purpose of the present invention is to provide a new, efficient, and scalable metadata allocation method, which uses the directory of the file system as the basic unit of hash, and uses the scalable hash method to allocate metadata to each element. data server.

Using the directory as the basic unit of the hash can maintain the storage locality of the directory, facilitate prefetching, and improve the efficiency of the system. When creating a directory, assign each directory a unique identifier that does not change, and distribute metadata to different metadata servers based on the hash value of the identifier. This avoids the problem encountered with hashed pathnames - when the pathname is modified, the hash value is changed, resulting in metadata migration.

The common hash algorithm that takes the modulo operation on the number of nodes in the metadata server cluster cannot meet the scalability requirements of the distributed file system. When the metadata server joins, exits (or fails), the hash value changes, resulting in a large amount of metadata migration, causing great network consumption. In order to solve this problem, we adopt a scalable hash method. First, we use the same hash function [Addr=hash(key) for the directory identifier and metadata server identifier, where the key value is a relatively large constant ]; Then, allocate according to the size of the hash value. Since the key value used has nothing to do with the number of servers in the metadata server cluster, the addition or withdrawal of metadata servers will not cause the redistribution of a large amount of metadata, but will only affect the distribution of a small amount of metadata. Its specific implementation is shown in Figure 2.

To sum up, using the directory-based scalable hash method to allocate metadata can have the following advantages:

(1) The client can locate the location of the metadata, and the metadata access efficiency is high.

(2) The metadata is evenly distributed and the load is balanced.

(3) The directory is used as the basic unit of the hash, the storage locality of the directory is maintained, the realization of prefetching is convenient, and the access efficiency is improved.

(4) Give the directory a unique identifier that does not change, avoiding metadata migration caused by the hash path name, and improving system performance.

(5) Joining or exiting metadata server will not cause massive metadata redistribution, minimize metadata migration, and have high scalability.

Description of drawings

Figure 1 shows the structure of the distributed file system

Figure 2 is a directory-based decomposition demonstration of the file system

Figure 3. Metadata allocation for scalable hashing methods

Figure 4 shows the redistribution of metadata when the metadata server exits

Figure 5 shows the redistribution of metadata when the metadata server joins

Detailed ways

In order to make the purpose, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments:

Figure 1 shows the distributed file system structure. The whole system consists of three parts: client, metadata server cluster and OSD cluster. The metadata server cluster is mainly responsible for managing metadata and providing customers with a unified namespace, and the OSD cluster is mainly responsible for storing file data and metadata. When a client operates a file, first of all, it locates the metadata server responsible for the file according to the metadata allocation principle, and sends a request to the metadata server; after receiving the request, the metadata server performs corresponding processing on the metadata of the file. Operations (such as: create, query, modify, delete, etc.), return the identifier of the file to the client; then, the client communicates with the OSD cluster using the identifier of the file as an input parameter to perform specific file IO operations.

The key processes involved in the present invention are described in detail below:

(1) Decomposition of the file system

The namespace of the file system is organized in the structure of a directory tree. We use the directory as the standard, and use the first-level files or subdirectories contained in the directory as the basic unit of the hash (DHU: Directory-basedHash Unit). Each DHU corresponds to a directory. The metadata of files or subdirectories in the same DHU will be distributed to the same metadata server, and the metadata of the second layer and below in the directory tree will be distributed to other metadata servers, that is, each DHU only contains its The metadata information of the subdirectory, but not the content under the subdirectory. as shown in picture 2. There are 3 layers under the directory d1. The files and directories on the first layer belong to DHU1. The directory tree has three directories d1, d2, and d3, corresponding to three DHUs: DHU1, DHU2, and DHU3.

(2) Distribution of metadata

Each node in the metadata server cluster has its unique ID (for example: IP address), and each DHU has a unique identifier DHU-ID assigned by us that does not change.

First, we use the same hash function to hash the node ID and DHU-ID to a circle of 0 to 2 ³² (the size of the range depends on the size of the file system, and different metadata server nodes should be avoided to hash to the same virtual location above); then search clockwise from the hash value of the DHU-ID to the position on the circle, and distribute the metadata contained in the DHU to the first server found; if the server is still not found after exceeding 2 ³² , Then it is assigned to the first metadata server. As shown in Figure 3, DHU 1 finds MDS1 clockwise, and its metadata is assigned to MDS 1; DHU 2 finds MDS 4 clockwise, so its metadata is assigned to MDS 4; and so on

In addition, using a general hash algorithm to hash metadata servers, the mapping locations of metadata servers on the circle are not evenly distributed. Therefore, we adopt the idea of virtual metadata server and allocate multiple virtual metadata servers on the circle for each physical metadata server, so that uneven distribution can be simulated, better load balancing can be achieved, and Metadata redistribution when small metadata servers increase or decrease.

(3) Metadata access

Access to metadata mainly includes operations such as creating, deleting, moving, renaming, querying files or directories, and listing directories (reading directories). Refer to Figures 2 and 3.

Create a file or directory

Scenario: The user creates a file text under a certain directory (for example: /d1/d2/).

In the first step, the server receiving the request parses the directory /d1/d2/, obtains the ID of DHU2 corresponding to d2, and calculates the hash value of the DHU-ID;

The second step is to find the MDS4 that manages the metadata under the DHU2 according to the hash value of the DHU-ID, and send a request to create a file text to MDS4;

In the third step, after receiving the request, MDS4 adds a piece of metadata of the file text under the directory d2, and returns the identifier of the file text to the user.

Step 4: MDS4 sends a request to update metadata of directory d2 to metadata server MDS1 corresponding to parent directory d1 of d2.

Creating a directory is similar to creating a file.

delete file or directory

File deletion is relatively simple. We find the corresponding MDS according to the DHU-ID of its parent directory, and then the MDS deletes the metadata of the file, returns the identifier of the file to the user, and sends a message to the MDS where the metadata of the parent directory is located. update request.

Then the deletion of the directory is a little more complicated, because there may be multiple levels of subdirectories nested under the directory. When deleting the directory, we must ensure that all its subdirectories are deleted. For example, if we want to delete the directory /d1:

The first step is to find MDS1 according to the DHU-ID of DHU1 corresponding to directory d1, and send a deletion request to MDS1;

In the second step, MDS1 finds all the subdirectories in d1, and there is only directory d2 in Figure 1, finds MDS4 according to the DHU-ID of DHU2 corresponding to directory d2, and sends a request to delete directory d2 to MDS4;

The third step is the same as the first and second steps. MDS4 sends a request to delete the directory d3 to the MDS in charge of d3 until there are no subdirectories in the directory, delete all files in the directory, and send feedback information to MDS4 after the deletion is completed. ;

Step 4: After receiving the feedback information, MDS4 completes the operation of deleting the content of d2, and sends the same feedback information to MDS1 after completion;

Finally, MDS1 can finish deleting the directory d1.

move a file or directory

The movement of files is equivalent to performing a delete operation on the MDS where the source parent directory is located, and then performing a create operation on the MDS where the target parent directory is located.

The movement of the directory does not need to change the MDS where the entire directory is located (that is, no data migration will occur), but only needs to send update directory item requests to the MDS where the source parent directory and the target parent directory are located.

Query files or directories, list directory contents (read directory)

To query a file or directory, first obtain the DHU-ID of the parent directory, determine the MDS according to the DHU-ID, and the MDS responds to the request and returns the required information.

There are two ways to list the content of the directory: 1) by querying the metadata information of the parent directory of the directory; 2) reading the content of the directory in the MDS where the directory is located.

(4) Expansion of metadata server

As the size of the file system increases, the metadata server cluster also needs to expand accordingly. At the same time, nodes in the cluster may fail and exit the cluster. The addition or withdrawal of the metadata server will inevitably lead to the migration of metadata, and the method proposed by the present invention can minimize the redistribution of metadata when the metadata server increases or decreases.

Compared with Figure 3, when the metadata service MDS 1 exits (or fails), unlike the past, all metadata needs to be redistributed. The exit of MDS 1 only affects its two DHUs in the counterclockwise direction (between MDS1 and Between MDS 3), as shown in Figure 4, only the metadata of the two DHUs originally allocated in MDS 1 are redistributed to MDS 2, while the metadata allocation of other DHUs does not change.

Compared with Figure 4, when the metadata server MDS x joins, as shown in Figure 5, it is not necessary to redistribute all the metadata. The addition of MDS x only affects the redistribution of DHU metadata in the counterclockwise direction , that is, the metadata of the DHU between MDS 3 and MDS x is transferred from the original MDS 2 to MDS x, while the metadata allocation of other DHUs does not change.

Claims (10)

1. A distributed file system metadata distribution method, the distributed file system includes a client, a metadata server cluster and an OSD cluster, characterized in that: Create a directory, using the directory of the file system as the basic unit of the hash; Metadata distribution is carried out by adopting an extensible hash method. In the extensible hash method, at first, the directory identifier and the identifier of the metadata server are used with the same hash function Addr=hash(key), where key The value is a constant with a relatively large value, and then, it is allocated according to the size of the hash value. 2. the distributed file system metadata distribution method as claimed in claim 1, is characterized in that: In the directory creation stage, each directory is assigned a unique identifier that does not change, and the metadata is distributed to different metadata servers based on the hash value of the identifier. 3. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system is decomposed, the directory is used as the standard, and the first-level files or subdirectories contained in the directory are used as the basic unit of the hash. Each basic unit of the hash corresponds to a directory. The metadata of the file or subdirectory in the basic unit of the above hash will be distributed to the same metadata server, and the metadata of the second layer and below in the directory tree will be distributed to other metadata servers. 4. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system distributes metadata, each node in the metadata server cluster has its uniquely identified ID, and each basic unit of the hash has a unique identifier DHU- ID, First, use the same hash function to hash the node ID and DHU-ID to the circle of 0-2 ³² ; then search clockwise from the position on the circle where the hash value of the DHU-ID is mapped, and convert the hashed The metadata contained in the basic unit is allocated to the first server found; if the server cannot be found after more than ²³² , it is allocated to the first metadata server. 5. The distributed file system metadata distribution method as claimed in claim 4, characterized in that: The size of the range of the circle depends on the scale of the file system, and it should be avoided that different metadata server nodes hash to the same virtual location. 6. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system creates a file or directory, the following steps are performed, In the first step, the server receiving the request parses the directory /d1/d2/, obtains the identifier DHU-ID of the hash basic unit corresponding to d2, and calculates the hash value of the DHU-ID; In the second step, according to the hash value of the DHU-ID, search for a second metadata server that manages metadata under the hash basic unit, and send a request to create a file or directory to the second metadata server; Step 3: After receiving the request, the second metadata server adds the metadata of the corresponding file or directory under the directory d2, and returns the identifier of the file or directory to the user; Step 4: The second metadata server sends a request to update the metadata of the directory d2 to the first metadata server corresponding to the parent directory d1 of d2. 7. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system deletes a file, it searches for the corresponding metadata server according to the hash basic unit identifier of the parent directory of the file to be deleted, and then the metadata server obtained by the search deletes the metadata of the file, and Return the identifier of the file to the user, and at the same time send an update request to the metadata server where the metadata of the parent directory is located; The distributed file system takes the following steps when deleting a directory, In the first step, a third metadata server is found according to the hash basic unit identifier corresponding to the directory, and a deletion request is sent to the third metadata server; In the second step, the third metadata server finds all subdirectories in the directory, finds the fourth metadata server according to the hash basic unit identifier corresponding to the subdirectory, and sends a request to delete the subdirectory to the first Quaternary data server; The third step is the same as the first and second steps. The fourth metadata server sends a request to delete the next subdirectory to the metadata server responsible for the next subdirectory until there is no subdirectory under the directory to be deleted. Delete Delete all files in this directory, and send feedback information to the fourth metadata server after deletion is completed; In the fourth step, after receiving the feedback information, the fourth metadata server completes the operation of deleting the content of the subdirectory, and sends the feedback information to the third metadata server in the same way after completion; Finally, the third metadata server completes the operation of deleting the directory to be deleted. 8. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system moves files or directories, First perform the delete operation on the metadata server where the source parent directory is located, and then perform the create operation on the metadata server where the target parent directory is located, so as to complete the file movement; The movement of the directory does not need to change the metadata server where the entire directory is located, but only needs to send the update directory item request to the MDS where the source parent directory and the target parent directory are located. 9. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the distributed file system queries a file or directory, it first obtains the hash basic unit identifier of the parent directory, determines the corresponding metadata server according to the hash basic unit identifier, and the corresponding metadata server responds to the request and returns required information; There are two ways for the distributed file system to enumerate directory contents: 1) by querying the metadata information of the parent directory of the directory; 2) reading the directory contents in the metadata server where the directory is located. 10. The distributed file system metadata distribution method as claimed in claim 1 or 2, characterized in that: When the first metadata server exits or fails, the exit or failure of the first metadata server only affects its counterclockwise DHUs, and only redistributes the metadata of the DHUs originally assigned to the first metadata server to the corresponding first metadata server. In the binary data server, the metadata allocation of other DHUs does not change; When the metadata server MDSx joins, the addition of MDSx only affects the redistribution of DHU metadata in the counterclockwise direction, that is, the metadata of the DHU between the corresponding third metadata server and MDSx is changed from the original corresponding metadata server The data server is transferred to MDSx, while the metadata allocation of other DHUs is not changed.

Images