CN105787093B - A Construction Method of Log File System Based on LSM-Tree Structure - Google Patents

Abstract

The invention proposes a kind of construction methods of log file system based on LSM-Tree structure, include the following steps to construct the log file system fuse framework interface based on LSM-Tree structure, includes the following steps: the multiple directory operation functions for constructing the log file system based on LSM-Tree structure and file manipulation function；Record data are added and inquired into the log file system based on LSM-Tree structure of building using Hash mapping function.The present invention can effectively improve the readwrite performance of catalogue, small documents under the premise of keeping big file read-write performance constant.

Description

A Construction Method of Log File System Based on LSM-Tree Structure

technical field

The invention relates to the technical field of file systems, in particular to a construction method of a log file system based on an LSM-Tree structure.

Background technique

A file system is the mechanism by which the operating system stores and manages data on a computer's disk. In 1964, the Multics time-sharing operating system jointly developed by Bell Labs, MIT and North American General Electric Company first proposed the idea of directory tree structure, marking the origin of the modern file system.

The UNIX operating system uses this tree idea in its own file system design, forming a file system architecture including four modules: boot block, super block, inode and data block. Since then, many file systems have followed this organizational structure.

In order to continuously improve the I/O performance, the Fast File System (FFS) appeared in 1984. It introduces the concept of Cylinder Group, saves several files in the same directory in the same group as much as possible, and saves several data blocks of the same file in the same group, which can significantly reduce the total seek time to improve read and write performance. After FFS, the Log-structured File System appeared in 1989. It adopts the idea of log appending, writes files in the form of log records, and indexes the log structure for file reading. , greatly improving the write performance, and using this structure can achieve fast recovery after a file system crash.

In 1994, with the birth of the Linux 1.0 kernel, the Extended File System (ext) series began to enter people's attention. ext1 is the first Linux Virtual File System (Linux Virtual File System, referred to as Linux VFS). The maximum disk space managed is 2GB, at this time ext1 is still a little rudimentary in all aspects. The emergence of ext2 has gradually become popular. It has many advantages such as the maximum disk space of 16TB, the maximum file size of 2TB, and the longest file name of 255 bytes. However, it has obvious defects in log management and is not suitable for security. demanding system. In 2001, ext3 came into being. It added a sound log function on the basis of ext2, which solved the fatal weakness of ext2. Using ext3 can greatly improve the reliability of file system data. It only takes 10 seconds to restore data. In order to support larger files, manage larger disk space, and make several optimizations, the ext4 file system was created, which uses delayed allocation, multi-block allocation, no-journal mode, etc. to improve performance, and supports an unlimited number of subdirectories, Online defragmentation, persistent pre-allocation and other functions are further optimizations to ext3.

Ext3 is the most popular Linux file system at present. This paper selects ext3 as the representative of traditional file system, takes ext3 as the research object, and analyzes the common characteristics of this type of file system architecture.

While traditional file systems such as ext3 provide users with many advantages such as high availability, high access speed, and multi-log mode support, such traditional file system architectures also have their shortcomings, especially for small file storage. It is said that the defects are reflected in the following three aspects: randomization of data distribution, waste of space and limited resources of index nodes.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve at least one of the technical defects.

Therefore, the purpose of the present invention is to propose a method for constructing a log file system based on the LSM-Tree structure.

In order to achieve the above object, an embodiment of the present invention provides a method for constructing a log file system based on an LSM-Tree structure, comprising the following steps:

Step S1, building a log file system fuse frame interface based on the LSM-Tree structure, including the following steps:

Step S11, call the fuse_main() function to mount the fuse file system to the mount point, create a UNIX local socket, create and run the sub-process fusermount, and then call the fuse_new() function to allocate data storage space for the fuse file system, complete mount;

Step S12, after the mounting is completed, the fuse_main() function calls fuse_loop() to start the session mode, and provides session services to the user;

Step S13, using the fusermount-uPATH command to unload the fuse file system, then interrupt the session service and reclaim the corresponding storage space;

Step S2, construct multiple directory operation functions and file operation functions of the log file system based on the LSM-Tree structure;

Step S3, using a hash mapping function to add and query record data into the constructed log file system based on the LSM-Tree structure.

According to the construction method of the log file system based on the LSM-Tree structure according to the embodiment of the present invention, the constructed LevelFS file system can effectively improve the read and write performance of directories and small files on the premise of keeping the read and write performance of large files unchanged. .

Further, the multiple directory operation functions include: a directory creation function fs_mkdir, a directory storage listing function fs_readdi, and a directory deletion function fs_rmdir;

The multiple file operation functions include: file renaming function fs_rename, file opening function fs_open, file reading function fs_read, file writing function fs_write, file size setting function fs_truncate, file permission modification function fs_chmod, file account information modification function fs_chown , the file system information read function fs_statvfs, the file timestamp update function fs_utimens, the file creation function fs_symlink pointing to the target symbolic link, the inumber path acquisition function get_disk_path and the disk file open function open_disk_file.

Further, in described step S3, described adopting the hash mapping function to build the log file system based on LSM-Tree structure to add record data, including the following steps:

Suppose k hash mapping functions are used to map the keys to k numbers between [0, m-1] respectively. When a record needs to be written, the corresponding k numbers are found through the mapping, and then the bytes are The numbers in the k corresponding positions in the array are all incremented by 1, indicating that there is such a record in the system.

Further, in the step S3, the use of the hash mapping function to query record data in the log file system based on the LSM-Tree structure that is constructed, includes the following steps:

Find the corresponding position of the record data through the hash mapping function, and judge whether the value at each position is greater than 0. If so, read the record data.

Further, after the step S3, the following steps are further included: delete the record data, then decrement the number at the corresponding position of the record in the array by 1.

Additional aspects and advantages of the present invention will be set forth, in part, from the following description, and in part will be apparent from the following description, or may be learned by practice of the invention.

Description of drawings

The above and/or additional aspects and advantages of the present invention will become apparent and readily understood from the following description of embodiments taken in conjunction with the accompanying drawings, wherein:

1 is a flowchart of a method for constructing a log file system based on an LSM-Tree structure according to an embodiment of the present invention;

Fig. 2 is the flow chart of constructing the log file system fuse frame interface based on LSM-Tree structure according to an embodiment of the present invention;

3 is a schematic diagram of a fuse frame interface of a log file system based on an LSM-Tree structure according to an embodiment of the present invention;

4 is a data flow diagram of the mkdir command of the log file system based on the LSM-Tree structure according to an embodiment of the present invention;

5 is a data structure diagram of adding records x and y according to an embodiment of the present invention;

6 is a flowchart of an operation of querying p and q according to an embodiment of the present invention;

FIG. 7 is a data structure diagram of a deletion record according to an embodiment of the present invention.

Detailed ways

The following describes in detail the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein the same or similar reference numerals refer to the same or similar elements or elements having the same or similar functions throughout. The embodiments described below with reference to the accompanying drawings are exemplary, and are intended to explain the present invention and should not be construed as limiting the present invention.

Aiming at the problem that the traditional file system has low access efficiency for small files, the invention proposes a construction method of a log file system based on an LSM-Tree (Log-Structured-Merge Tree) structure, and constructs a log based on the LSM-Tree structure. The file system implements LevelFS, a file system constructed using logs based on the above-mentioned basic architecture, so that an access optimization technical scheme can be designed for small files, and the efficiency of access operations to a large number of small files can be improved.

The construction method of the log file system based on the LSM-Tree structure proposed by the present invention includes the following steps: by setting a write cache in the memory, the disk random writes of several small files are changed into disk sequential writes to improve the writing efficiency, and at the same time, the disk On the other hand, the storage distance of the associated data is reduced to improve the read efficiency, thereby improving the read and write performance of the file system.

As shown in Figure 1, the construction method of the log file system based on the LSM-Tree structure of the embodiment of the present invention comprises the following steps:

Step S1, building a log file system fuse frame interface based on the LSM-Tree structure, including the following steps:

Referring to Figure 2 and Figure 3, the fuse framework interface is divided into three parts: mount, call and unload.

Step S11, call the fuse_main() function to mount the fuse file system to the mount point, create a UNIX local socket, create and run the sub-process fusermount, and then call the fuse_new() function to allocate data storage space for the fuse file system, complete mount.

Mounting part: When the user runs the compiled and linked executable file, the fuse_main() function will be called to parse the mount point, multi-threading support and other parameters, marking the beginning of the FUSE file system life cycle. The fuse_main() function will call the fuse_mount() function to mount the fuse file system on the mount point, create a UNIX local socket, create and run the subprocess fusermount, and then call the fuse_new() function to allocate data storage space for the fuse file system fuse_datastructure, the mount is complete.

Step S12, after the mounting is completed, the fuse_main() function calls fuse_loop() to start the session mode, and provides session services to the user.

Session part: The fuse_main() function calls fuse_loop() to open the session mode after the mount is completed, providing users with the services of continuously receiving the session, processing the session, and returning the session.

In step S13, the fuse file system is unmounted by using the fusermount-uPATH command, then the call-back service is interrupted, and the corresponding storage space is reclaimed.

Unmounting part: The user unmounts the fuse file system using the fusermount-u PATH command, the session is interrupted and the storage space is reclaimed, marking the end of the FUSE file system life cycle.

In step S2, multiple directory operation functions and file operation functions of the log file system based on the LSM-Tree structure are constructed.

Fig. 4 is the data flow chart of the mkdir command of the log file system based on the LSM-Tree structure according to the embodiment of the present invention. As shown in Fig. 4, taking the mkdir command under linux as an example, a directory "hi" is created under "/" ”, which is passed to the int fs_mkdir(const char*path, mode_t mode) function of LevelFS after being parsed layer by layer. The following is a detailed introduction to the functions and key points of the functions related to directory and file operations.

In an embodiment of the present invention, the plurality of directory operation functions include: a directory creation function fs_mkdir, a directory storage listing function fs_readdi, and a directory deletion function fs_rmdir.

(1) fs_mkdir

Function: Create a directory on the specified path.

Key points: First, parse the path into the parent directory par_path and the subdirectory file dir_name, find the number par_inumber of the parent node according to the par_path, and extract the meta information of the parent node at the same time, combine the account information to determine whether the user has the permission to create files in the par_path directory , if not return an error. If you have permission, assign i_number=cur_inumber+1 to the directory file, create an fs_inode data structure as the metadata information of new_dir, fill in account information, timestamp information, set the number of hard links to 1, set i_number to ++cur_inumber, set The file type is directory. Finally, write {par_inumber}/{dir_name}->{i_number}:{fs_inode} into LevelDB.

(2) fs_readdir

Function: List the directory items stored in the specified path. This command corresponds to the ls command in the Linux terminal.

Key points: First, open the directory file according to the path (refer to fs_open for the specific process), and if the opening is successful, take out the i_number of the directory node; then, use the Iterator in LevelDB to traverse the key in range[i_number+"/", i_number+1) key-value record; finally fill the filename of each record into the filler list and return.

(3) fs_rmdir

Function: Delete the directory on the specified path.

Key points: First, the parent directory par_path and the subdirectory file dir_name are also parsed from the path, and the number par_inumber and meta of the parent node are found according to the par_path, and the deletion permission is judged; if there is permission, just write the record {par_inumber}/ {dir_name}->Delete is enough.

Multiple file operation functions include: file rename function fs_rename, file open function fs_open, file read function fs_read, file write function fs_write, file size setting function fs_truncate, file permission modification function fs_chmod, file account information modification function fs_chown, file The system information reading function fs_statvfs, the file timestamp update function fs_utimens, the file creation function fs_symlink pointing to the target symbolic link, the inumber path obtaining function get_disk_path and the disk file opening function open_disk_file.

(4)fs_rename

Function: Rename the file under the specified path.

Key points: First, read the parent directory as well, determine whether it has write permission to the parent directory (not repeated here), and take out the par_inumber; then, read the Value information of {par_path}/{old_name}, and record it as r_value ; Finally, write records {par_inumber}/{old_name}->Delete and {par_inumber}/{old_name}->{r_value} to LevelDB.

(5) fs_open

Function: Open the file on the specified path.

Key points: First, read the parent directory, get par_inumber and par_meta, check permissions according to par_meta; then store the record item fs_record with key {par_inumber}/{filename} in the cache, create a fs_openfile data structure, and fill the address pointer of fs_record , user account information, etc., set the current position of the file to 0, set the start position of the file in r_value, and set the r_count in fs_record to 1, the file is successfully opened.

(6) fs_read

Function: Read the content in the specified location of the file on the specified path.

Point: Before reading the content of a file, you need to use fs_open to open the file. At this time, the content of the file is already in the memory. Since the amount of data in each record of LevelDB is small, the data of the file is also changed when the file meta is retrieved. and take out. If the file is a large file, open the large file located in the local file system through get_disk_path and open_disk_file. Whether it is a large file or a small file, the data can be read through f_start and f_pos in the fs_openfile data structure.

(7) fs_write

Function: Write data to the specified location of the file on the specified path.

Important: Like fs_read, before writing the file content, first use fs_open to open the file; then adjust f_pos in fs_openfile to the specified position to start data writing; as data is written, f_pos also keeps moving backwards. It should be noted that the total file size after writing needs to be checked before each write operation. If the total file size exceeds the threshold, the file content originally stored in LevelDB will be migrated to the local file system.

(8) fs_truncate

Function: Set the new size of the file on the specified path.

Important: After obtaining the metadata information of the file, modify the corresponding size information and the timestamp of the file. It should be noted that if the size of the file before truncate is smaller than the threshold, and the size of the file after truncate is larger than the threshold, you need to migrate the small files in LevelDB to the local file system and store them in the form of large files, and vice versa.

(9) fs_chmod

Function: Modify the new permission flag of the file on the specified path.

Point: Obtain the metadata information of the file through the parent directory, read the stat in it, then change the stat.st_mode to the new mode, and finally write the modified record item back.

(10) fs_chown

Function: Modify the account information of the file on the specified path.

Important: Similar to fs_chmod, first obtain the metadata information of the file through the parent directory, read the stat in it, then set stat.st_uid=uid and stat.st_gid=gid, and finally write the modified record item back.

(11) fs_statvfs

Function: Read file system information, such as used space, free space, and free block tree, and store it in statvfs. This is the statistical information of the local file system. You can directly call the statvfs(path, stbuf) interface of the local file system.

(12) fs_utimens

Function: Update the timestamp information of the file on the specified path.

Point: Similar to fs_chmode, first obtain the metadata information of the file through the parent directory, read the stat in it, and then set new st_atim and st_mtim, and for st_ctim, since the creation time is managed by the operating system, users are not allowed to modify it .

(13) fs_symlink

Function: Create a file pointing to the target symbolic link on the specified path

Point: First, obtain the fs_inode of the file through the parent directory, store the linked target string in the value, set is_large=false, and write the generated path record back.

(14) get_disk_path

Function: Get the path corresponding to inumber

Main point: The non-external interface mainly calculates the corresponding index path according to the inumber, which plays an important role in the mapping of large files. Specifically, the mapping rules for large files include, for example:

First, to obtain the 64-bit positive integer i_number assigned to the file by LevelFS, you need to observe its characteristics. Although the range of i_number is 64 bits, it starts from 0 and increases continuously, and is not randomly assigned like a memory address. This also determines that when the size of the file system is relatively small, only the lower bits of i_number may have data, while most of the high bits are 0; The number of digits is also increasing.

Then, the 64-bit positive integers are grouped in groups of 13 bits from the low order, there are 5 groups of numbers, named p0, p1, p2, p3, p4, except that p4 is less than 13 bits, the range of the other groups of numbers All are 0 to 2^13–1.

Finally, LevelDB uses the following rules for mapping:

(1) If i_number<2 ²⁶ (that is, 8192 ² ), then the mapping path is /{p1}/{p0}, for example, i_number=9000, then its corresponding storage path is /1/808;

(2) If i_number>=2 ²⁶ and i_number<2 ³⁹ , then the mapping path is /a/{p2}/{p1}/{p0};

(3) If i_number>=2 ³⁹ and i_number<2 ⁵² , the mapping path is /b/{p3}/{p2}/{p1}/{p0};

(4) If i_number>=2 ⁵² and i_number<2 ⁶⁴ , the mapping path is /c/{p4}/{p3}/{p2}/{p1}/{p0}.

It should be noted that the reason why LevelFS adopts the above mapping rules is mainly due to the following reasons:

First, when the number of directory entries in a directory is too large, the speed of searching it by file name will become very slow. Therefore, LevelFS adopts the idea of grading, takes ¹³ bits as a group, and controls the number of directory entries in each directory node within the order of magnitude of 213.

Then, if the multi-level index method is directly adopted, and a level-1 index is established for every 13 bits, then it takes 5 levels to retrieve a file. Even if the amount of data in the file system is small, 5 levels of indexes are also required to retrieve the 123rd file, which is an overhead. It's bigger, and it's not necessary. Therefore, LevelFS adopts an unbalanced method. When the size of the file system is relatively small, the two-level indexing method of /{p1}/{p0} is used, which can reduce the total number of indexes compared with the direct multi-level indexing.

Finally, when i_number is very large, it exceeds 10 ⁸ , indicating that the scale of the file system is very large. At this time, according to the scale of i_number, it is decided whether to search the /a/ path, the /b/ path or the /c/ path.

The use of this unbalanced multi-level index method can well meet the characteristics of the sequential growth of inode numbers, so that the file system can have a suitable index level no matter in a small scale or a large scale, and reduce the average number of indexes as much as possible. ; At the same time, it fully limits the number of directory entries in each directory and reduces the indexing time in each directory.

(15) open_disk_file

Function: Open the disk file of the fs_inode_header*iheader object.

Point: For non-external interfaces, call get_disk_path to obtain the file path according to iheader.st_ino, and then call the open function of the local file system with flags to record the open file information.

Step S3, using a hash mapping function to add and query record data into the constructed log file system based on the LSM-Tree structure.

Adding record data to the constructed log file system based on the LSM-Tree structure using the hash mapping function includes the following steps:

Suppose k hash mapping functions are used to map the keys to k numbers between [0, m-1] respectively. When a record needs to be written, the corresponding k numbers are found through the mapping, and then the bytes are The numbers in the k corresponding positions in the array are all incremented by 1, indicating that there is such a record in the system.

Fig. 5 is the data structure diagram of adding record x, y described in the embodiment of the present invention, as shown in Fig. 5:

Assuming that k hash mapping functions are used, keys can be mapped to k numbers between [0, m-1] respectively. When a record needs to be written, the corresponding k numbers are found through mapping, and then the numbers in the k corresponding positions in the byte array are incremented by 1, indicating that such a record exists in the system. For example, suppose k=3, write records x and y, hashs(x)=[2,4,7], hashs(y)=[4,8,11], the array at this time becomes Figure 5 shown.

Using the hash mapping function to query the record data in the log file system based on the LSM-Tree structure, the following steps are included:

Find the corresponding position of the record data through the hash mapping function, and judge whether the value at each position is greater than 0. If so, read the record data.

FIG. 6 is a flow chart of the query p, q operation according to the embodiment of the present invention. As shown in FIG. 6, when a record needs to be read, the corresponding position is first found through hashs, and it is judged whether the value of each position is greater than 0. If hashs(p)=[1,4,11], check the array and find that the corresponding number at the 1 position is 0, then the record p must not be in LevelDB, no need to continue to search down, and return to read failure; if hashs(q) = [4, 8, 11], the numbers at each position are greater than 0, then the record q may be in LevelDB, and the reading of q cannot be filtered out.

After step S3, it also includes the following steps: delete the record data, then decrement the number at the corresponding position of the record in the array by 1.

Fig. 7 is the data structure diagram of the deleted record according to the embodiment of the present invention. As shown in Fig. 7, when a record needs to be deleted, the number at the corresponding position of the record in the array is decremented by 1, and the array after the record x is deleted The content is shown in Figure 7.

According to the construction method of the log file system based on the LSM-Tree structure according to the embodiment of the present invention, the constructed LevelFS file system can effectively improve the read and write performance of directories and small files on the premise of keeping the read and write performance of large files unchanged. .

In the description of this specification, description with reference to the terms "one embodiment," "some embodiments," "example," "specific example," or "some examples", etc., mean specific features described in connection with the embodiment or example , structure, material or feature is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms do not necessarily refer to the same embodiment or example. Furthermore, the particular features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.

Although the embodiments of the present invention have been shown and described above, it should be understood that the above embodiments are exemplary and should not be construed as limiting the present invention, and those of ordinary skill in the art will not depart from the principles and spirit of the present invention Variations, modifications, substitutions, and alterations to the above-described embodiments are possible within the scope of the present invention without departing from the scope of the present invention. The scope of the invention is defined by the appended claims, with their full equivalents.

Claims (4)

1. a kind of construction method of the log file system based on LSM-Tree structure, which comprises the steps of:

Step S1 constructs the log file system fuse framework interface based on LSM-Tree structure, includes the following steps:

Step S11 calls fuse_main () function that fuse is file system mounted on mount point, and creation UNIX is locally socketed Word creates and runs subprocess fusermount, and then calling fuse_new () function is that fuse file system distribution data are deposited Space is stored up, carry is completed；

Step S12, after completing carry, fuse_main () function call fuse_loop () opens conversation modes, provides a user Conversational services；

Fuse file system is unloaded using fusermount-uPATH order, then interrupts the conversational services by step S13, is returned Receive corresponding memory space；

Step S2 constructs the multiple directory operation functions and file operation letter of the log file system based on LSM-Tree structure Number；

Step S3 is added and is inquired into the log file system based on LSM-Tree structure of building using Hash mapping function Record data, comprising: set using k Hash mapping function, key is mapped to the k number between [0, m-1] respectively, when needs are write When entering a record, corresponding k number is found by mapping, then by the number in byte arrays in this k corresponding position All plus 1, show that there are such one records in system.

2. the construction method of the log file system as described in claim 1 based on LSM-Tree structure, which is characterized in that institute State multiple directory operation functions include: directory creating function fs_mkdir, catalogue storage list function fs_readdi, catalogue is deleted Except function fs_rmdir；

Multiple file manipulation functions include: file renaming function fs_rename, File Open function fs_open, file reading Function fs_truncate, file permission Modification growth function is arranged in function fs_read, file write-in function fs_write, file size Fs_chmod, file account information Modification growth function fs_chown, filesystem information function reading fs_statvfs, document time Stamp renewal function fs_utimens, the path document creation function fs_symlink, inumber for being directed toward target Symbolic Links are obtained Function get_disk_path and disk file is taken to open function open_disk_file.

3. the construction method of the log file system as described in claim 1 based on LSM-Tree structure, which is characterized in that It is described to be inquired using Hash mapping function into the log file system based on LSM-Tree structure of building in the step S3 Data are recorded, are included the following steps:

The corresponding position that record data are found by k Hash mapping function, judges whether the value on k position is both greater than 0, such as Fruit is then to read the record data.

4. the construction method of the log file system as described in claim 1 based on LSM-Tree structure, which is characterized in that Further include following steps after the step S3: deletion record data, and this in byte arrays is recorded on corresponding position Number all subtracts 1.