Shulou(Shulou.com)06/01 Report--

This article to share with you is about how to use leveldb to achieve file system directory tree, Xiaobian think quite practical, so share to everyone to learn, I hope you can read this article after harvest, not much to say, follow Xiaobian to see it.

Using leveldb to realize directory tree of file system

The directory tree maintains the meta-information of the entire file system, and all operations to add, delete, check, and correct files in the file system need to be performed through the directory tree. Baidu open source distributed file system BFS(open source address: https://github.com/baidu/bfs) uses leveldb to realize the management of directory trees, making the implementation of directory trees very simple, and at the same time, the operation of directory trees is very efficient. This article will analyze its specific design and implementation ideas for you.

The directory tree is a tree structure, and leveldb is a kv storage engine, so if you want to use leveldb to implement the directory tree, you need to map the tree structure to the flattened structure of kv.

As far as each file or directory is concerned, its information only needs a kv record to be saved, and the value in this kv needs to save the attribute information of the directory or file, and there is not much room for change. Therefore, the key to mapping from tree structure to kv record lies in the selection of key.

In the directory tree of BFS, an integer number int64_t is defined as EntryID, each file or directory has an EntryID and is globally unique, and the EntryID of the root directory is specified as 1. Suppose we have the following directory structure:

/home/dirx/ /filex diry/ /filey/tmp/ filez

In order of creation, we assign/home an EntryID of 2,/tmp an EntryID of 3,/home/dirx an EntryID of 4,/home/dirty an EntryID of 5,/home/tmp/filez an EntryID of 6,/home/dirx/filex an EntryID of 7, and/home/dirty/filey an EntryID of 8.

Note that each directory has its own EntryID, and it must have a parent directory, and its parent directory must have an EntryID. You can use this to determine the key of a record by the EntryID of the parent directory and the file name in the child directory: For each file or directory, we specify that the key of each kv record is "EntryID of the parent directory + its own file name", and store its own EntryID in the value. After encoding, the directory tree can be represented as follows:

1home -> 2 + xxx1tmp -> 3 + xxx2dirx -> 4 + xxx2diry -> 5 + xxx3filez -> 6 + xxx4filex -> 7 + xxx5filey -> 8 + xxx

xxx represents other information about the directory or file, such as size, creation time, actual data storage location, etc.

At this point, the tree structure of the directory tree has been flattened into a kv record, and the operation of the directory tree has been converted into an operation on a few kv records:

For file creation operations, such as to create/home/work/directory, first search for the home directory in/directory, because the EntryID of/is 1, so the first search, the key is 1home, and then read its value, after parsing found that the EntryID of/home is 2, then write down this EntryID, continue to go down, found that work is the file to be created, then apply for an EntryID (assuming 9), at this time, write a record, according to the above rules, its key is 2work, value Information such as the time when work was created, and the EntryID of work (9)

For deletion operations, such as deleting the newly created/home/work directory, you only need to delete the record with key 2work.

For reading operation, for example, if you want to read the contents of/home/dirx/filex file, first read the value corresponding to the key of 1home, parse and find that the EntryID recorded in the value is 2, then read the value corresponding to the key of 2dirx, parse and find that the EntryID recorded in the value is 4, and then read the value corresponding to the key of 4filex, parse the actual data storage location of/home/dirx/filex from it, and read the file contents.

For List directory operations, for example, if you want to see what files and directories are under the root directory, because each file and directory contains the EntryID of the parent directory when stored, you only need to scan once. For example, ls /, you only need to scan the leveldb, with 1\0x0 as the prefix of the key can be, when it encounters 2 stop, the result is all the contents of the/directory

For the Rename operation, just change its key. For example, if you want to move the/home/dirty/file file to the home/dirx directory, according to the previous rules, the key stored in/home/dirty/file in leveldb is 5 file, and the EntryID of/home/dirx is 4. Read out the memory in the record 5 file, use 4file as the key, and store it to leveldbk again. Then delete the record 5 file, that is, complete the Rename operation.

In this way, the basic operations required for a directory tree are already supported. Since the leveldb engine itself has a fast write speed, and when reading, there is already a cache inside to cache hot kv data, and the cache size can be configured, so a very simple and efficient directory tree is realized.

The above is how to use leveldb to implement the directory tree of the file system. Xiaobian believes that some knowledge points may be seen or used in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.