CN105786916B - Storage method and system for a hierarchical directory based on a large-capacity table - Google Patents

Abstract

The invention discloses a storage method and system of a hierarchical directory based on a large-capacity table. The method includes: adding an identifier before the first letter of the lowest layer object or directory of a given path, identifying the object or directory as the lowest layer, and storing the object or directory; obtaining the parent directory path of the object or directory, And judge whether described parent directory path is the first layer, if not, then add identifier before the first letter of the catalog of described parent directory path, mark described parent directory path as the lowest layer, and store described parent directory path Directory. Therefore, centralized storage of objects and directories at the same layer is realized, thereby improving efficiency during retrieval.

Description

Storage method and system for a hierarchical directory based on a large-capacity table

technical field

The invention relates to the field of cloud computing, in particular to a storage method and system for a hierarchical directory based on a large-capacity table.

Background technique

Traditional relational databases have poor performance and scalability for trillion-level data. Large-capacity tables can accommodate PB-level data, and with the development of business, the number can increase by dozens of times. Although the large-capacity table solves the limitation of capacity, when its directory or file is stored, the directory or file of a specific level to be queried is randomly distributed, which will cause a large number of continuous scans and subsequent path resolution, thus consuming Lots of IO and CPU resources. For example, take the captured paths of /bn1/a_dp1/a_dp2/b, /bn1/a_dp1/mfile_dp2, and /bn1/a_dp1/z_dp2/z in the front, middle, and back of alphabetical sorting as an example:

/bn1/a_dp1/a_dp2/b

....

/bn1/a_dp1/a_dp2/c/23/s

/bn1/a_dp1/ab_dp2/c/23/s

(a total of 60 billion object records in the middle)

....

/bn1/a_dp1/mfile_dp2

....

/bn1/a_dp1/a_dp2/c/23/s

/bn1/a_dp1/ab_dp2/c/23/s

(a total of 40 billion object records in the middle)

....

/bn1/a_dp1/z_dp2/z

If 10 billion object records can be stored on one server, and there are 10 servers, in order to retrieve the lower-level directory or file of /bn1/a_dp1, it is necessary to search from /bn1/a_dp1/a_dp2/b to /bn1/a_dp1/ The 10 servers limited to z_dp2/z are fully scanned, and at the same time, the object name of each record needs to be analyzed hierarchically to intercept the third-level directory. In this case, 10 servers need to be searched for a directory Perform a full scan of the storage, and perform string interception, matching, and deduplication operations on 100 billion object records. Therefore, the directory storage method of the large-capacity table prevents the directories and objects of the same layer from being stored centrally, resulting in extremely low retrieval efficiency.

Contents of the invention

The technical problem to be solved by the present invention is that the directory and object storage method of the large-capacity table prevents centralized storage of the directories and objects of the same layer, resulting in extremely low retrieval efficiency.

According to one aspect of the present invention, a storage method for a hierarchical directory based on a large-capacity table is proposed, including:

add an identifier before the first letter of the lowest-level object or directory of the given path, identify the object or directory as the lowest level, and store the object or directory;

Obtain the parent directory path of the object or directory, and judge whether the parent directory path is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path to identify the parent directory path is the lowest level and stores the directory of the parent directory path.

Further, the object or directory is used as the key (key) of the large-capacity table, and the number of objects corresponding to the lower layer of the directory is used as the corresponding value (value) of the directory;

When adding an object, the value corresponding to the upper directory of the object is incremented;

When deleting an object, first delete the key-value pair record of the object, and decrement the value of the upper directory of the object.

Further, when adding an object, if the upper-level directory of the object does not exist, create the directory first, and set the value corresponding to the directory to 1;

When deleting an object, if the value of the upper directory of the object is decremented to 0, the directory is deleted.

Further, save the start record and end record of the data block, and the server where the data block is stored, wherein the data block includes a record of an object or a directory in a large-capacity table;

When retrieving a directory or object, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, then find the server where the data block is stored, and retrieve the server .

Further, the identifier is a leading character, which identifies objects or directories at the same layer as being in front of the sequence.

According to another aspect of the present invention, a storage system based on a hierarchical directory of a large-capacity table is also proposed, including:

The processing module is used to add an identifier before the first letter of the lowest-level object or directory of a given path to identify the object or directory as the lowest level; obtain the parent directory path of the object or directory, and determine the parent directory path Whether it is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path, and identify the parent directory path as the lowest layer;

Storage module, used to store objects or directories.

Further, the maintenance module is used to use the object or directory as the key of the large-capacity table, and the number of objects corresponding to the lower layer of the directory as the value corresponding to the directory; when adding an object, the upper directory of the object corresponds to The value of the object is incremented; when deleting an object, the key-value pair record of the object is deleted first, and the value of the upper directory of the object is decremented.

Further, the maintenance module is used to create a directory first if the upper-level directory of the object does not exist when adding an object, and set the value corresponding to the directory to 1; when deleting an object, if the value of the upper-level directory of the object If it is 0 after decrementing, the directory will be deleted.

Further, the record module is used to save the start record and end record of the data block and the server where the data block is stored, wherein the data block includes the records of objects or directories in the large-capacity table;

Wherein, when retrieving a directory or object, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, then find the server where the data block is stored, and retrieve the data block. said server.

Further, the identifier is a leading character, which identifies objects or directories at the same layer as being in front of the sequence.

Compared with the prior art, the present invention identifies the object or directory as the lowest layer by adding an identifier before the first letter of the lowest layer object or directory of a given path, and stores the object or directory; obtains the object or directory The parent directory path of the directory, and judge whether the parent directory path is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path, identify the parent directory path as the lowest level, and The directory where the path to the parent directory is stored. Therefore, centralized storage of objects and directories at the same layer is realized, thereby improving efficiency during retrieval.

Other features of the present invention and advantages thereof will become apparent from the following detailed description of exemplary embodiments of the present invention with reference to the accompanying drawings.

Description of drawings

The accompanying drawings, which constitute a part of this specification, illustrate the embodiments of the invention and together with the description serve to explain the principles of the invention.

The present invention can be more clearly understood from the following detailed description with reference to the accompanying drawings, in which:

FIG. 1 is a schematic flow chart of an embodiment of the method for storing a hierarchical directory based on a large-capacity table in the present invention.

FIG. 2 is a schematic structural diagram of an embodiment of a storage system based on a hierarchical directory of a large-capacity table according to the present invention.

Fig. 3 is a comparison diagram between the hierarchical directory storage of the present invention and the storage method of the prior art.

Detailed ways

Various exemplary embodiments of the present invention will now be described in detail with reference to the accompanying drawings. It should be noted that the relative arrangements of components and steps, numerical expressions and numerical values set forth in these embodiments do not limit the scope of the present invention unless specifically stated otherwise.

At the same time, it should be understood that, for the convenience of description, the sizes of the various parts shown in the drawings are not drawn according to the actual proportional relationship.

The following description of at least one exemplary embodiment is merely illustrative in nature and in no way taken as limiting the invention, its application or uses.

Techniques, methods and devices known to those of ordinary skill in the relevant art may not be discussed in detail, but where appropriate, such techniques, methods and devices should be considered part of the Authorized Specification.

In all examples shown and discussed herein, any specific values should be construed as illustrative only, and not as limiting. Therefore, other examples of the exemplary embodiment may have different values.

It should be noted that like numerals and letters denote like items in the following figures, therefore, once an item is defined in one figure, it does not require further discussion in subsequent figures.

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be described in further detail below in conjunction with specific embodiments and with reference to the accompanying drawings.

FIG. 1 is a schematic flow chart of an embodiment of the method for storing a hierarchical directory based on a large-capacity table in the present invention. The method includes the following steps:

In step 110, an identifier is added before the first letter of the lowest-level object or directory of the given path to identify the object or directory as the lowest level, and store the object or directory.

In step 120, obtain the parent directory path of the object or directory, and judge whether the parent directory path is the first level, if not, execute step 130, and if yes, execute step 140.

In step 130, an identifier is added before the first letter of the directory of the parent directory path to identify the parent directory path as the lowest level, and the directory of the parent directory path is stored.

At step 140, no further identifier and store operations are performed.

Wherein, the identifier can be a leading character, for example, the character minimum value (Character.MIN-VALUE), Character.MIN-VALUE is a character that cannot be printed and displayed in the computer, and it is represented by Δ for the sake of easy identification, because The system arranges in alphabetical order by default. By adding a leading character before the first letter of the object or directory, the objects or directories at the same level can be sorted and stored together consecutively. Those skilled in the art should understand that Δ is just for example, and can be identified by any other shape in the computer, which should not be construed as a limitation of the present invention.

Take the object /bucketname1/a_depth1/z_depth2/z as an example, bucketname1 is the first layer, a_depth1 is the second layer, z_depth2 is the third layer, and z is the lowest layer, that is, the path of the object or directory is the first layer from left to right. One layer/second layer/third layer/fourth layer/.../nth layer/lowest layer, then the calculated output of the object /bucketname1/a_depth1/z_depth2/z is:

/bucketname1/a_depth1/z_depth2/Δz

/bucketname1/a_depth1/Δz_depth2

/bucketname1/Δa_depth1

Since the first layer is the storage segment (bucketname) layer, not an object, no identifier is added to the first layer.

The present invention stores objects or directories of the same layer together, for example:

/bn1/Δa_dp1/

...

/bn1/a_dp1/Δa_dp2/

/bn1/a_dp1/Δab_dp2/

/bn1/a_dp1/Δmfile_dp2

/bn1/a_dp1/Δz_dp2/

...

/bn1/a_dp1/a_dp2/Δb

/bn1/a_dp1/a_dp2/Δc/

/bn1/a_dp1/ab_dp2/Δc/

...

/bn1/a_dp1/z_dp2/Δz

Among them, the ones ending with "/" represent directories, and the ones without "/" denote objects.

Use the metadata table to record the situation of the large-capacity table, for example, record the storage status of the objects or directories in the large-capacity table on the server and on the data block of the server. For example, if the size of a data block is 128M, the metadata table will record The server where the data block is located and the start record and end record of the data block can quickly locate the object or directory that needs to be queried through the retrieval of the metadata table. Wherein, the metadata table can be placed on one server alone, or on multiple servers.

For example, when retrieving the lower-level object or directory of /bn1/a_dp1/, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, and then find the data The server where the block is stored, retrieves the server.

If there are 100 billion records in the server, and there are 1 million records in the three-layer directory, 100 billion IO operations are required in the prior art, but 1 million IO operations are required in the present invention.

In addition, in the prior art, multiple operations such as string interception, matching, and deduplication are performed on 100 billion object records, but the object records of the present invention only need to remove the leading characters.

In an embodiment of the present invention, an identifier is added before the first letter of the lowest-level object or directory of a given path, and the object or directory is identified as the lowest layer, and the object or directory is stored; the object or directory is obtained parent directory path, and judge whether the parent directory path is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path, identify the parent directory path as the lowest level, and store all A directory that describes the path of the parent directory. Therefore, centralized storage of objects and directories at the same layer is realized, thereby improving efficiency during retrieval.

In another embodiment of the present invention, the object or directory is used as a key (key) of a large-capacity table, and the large-capacity table is an object directory hierarchical storage table, and the number of objects corresponding to the next layer of the directory is used as the number of objects in the directory. The corresponding value (value).

When an object is added, the value corresponding to the upper-level directory of the object is incremented. If the upper-level directory of the object does not exist, the directory is created first, and the value corresponding to the directory is set to 1.

When deleting an object, first delete the key-value pair record of the object, and decrement the value of the upper directory of the object, if the value of the upper directory of the object is decremented to 0, then delete the directory.

In the embodiment of the present invention, when deleting an object under a directory in the directory hierarchy index, if the directory is empty, the directory will be deleted together; when adding or deleting objects, after decomposing each layer Accumulate or decrement the number of objects in the directory, and delete the directory when the number of objects in the directory is 0, while improving retrieval performance and storage capacity, it realizes the function of adding, deleting, maintaining and managing directory files.

FIG. 2 is a schematic structural diagram of an embodiment of a storage system based on a hierarchical directory of a large-capacity table according to the present invention. The system includes: a processing module 210 and a storage module 220 . in:

The processing module 210 is used to add an identifier before the first letter of the lowest-level object or directory of a given path to identify the object or directory as the lowest level; obtain the parent directory path of the object or directory, and determine the parent directory Whether the path is the first level, if not, add an identifier before the first letter of the directory of the parent directory path, and identify the parent directory path as the lowest level.

The storage module 220 is used for storing objects or directories.

Wherein, the identifier can be a leading character, for example, the character minimum value (Character.MIN-VALUE), Character.MIN-VALUE is a character that cannot be printed and displayed in the computer, and it is represented by Δ for the sake of easy identification, because The system arranges in alphabetical order by default. By adding a leading character before the first letter of the object or directory, the objects or directories at the same level can be sorted and stored together consecutively. Those skilled in the art should understand that Δ is just for example, and can be identified by any other shape in the computer, which should not be construed as a limitation of the present invention.

Take the object /bucketname1/a_depth1/z_depth2/z as an example, bucketname1 is the first layer, a_depth1 is the second layer, z_depth2 is the third layer, and z is the lowest layer, that is, the path of the object or directory is the first layer from left to right. One layer/second layer/third layer/fourth layer/.../nth layer/lowest layer, then the calculated output of the object /bucketname1/a_depth1/z_depth2/z is:

/bucketname1/a_depth1/z_depth2/Δz

/bucketname1/a_depth1/Δz_depth2

/bucketname1/Δa_depth1

Since the first layer is the storage segment (bucketname) layer, not an object, no identifier is added to the first layer.

The present invention stores objects or directories of the same layer together, for example:

/bn1/Δa_dp1/

...

/bn1/a_dp1/Δa_dp2/

/bn1/a_dp1/Δab_dp2/

/bn1/a_dp1/Δmfile_dp2

/bn1/a_dp1/Δz_dp2/

...

/bn1/a_dp1/a_dp2/Δb

/bn1/a_dp1/a_dp2/Δc/

/bn1/a_dp1/ab_dp2/Δc/

...

/bn1/a_dp1/z_dp2/Δz

Among them, the ones ending with "/" represent directories, and the ones without "/" denote objects.

The system also includes a record module 230, which is used to save the start record and end record of the data block, and the server where the data block is stored, wherein the data block includes records of objects or directories in a large-capacity table. The recording module 230 may be a metadata table. For example, if the size of a data block is 128M, the metadata table will record the server where the data block is located and the start record and end record of the data block. Through the retrieval of the metadata table, the object or directory to be queried can be quickly located. Wherein, the metadata table can be placed on one server alone, or on multiple servers.

For example, when retrieving the lower-level object or directory of /bn1/a_dp1/, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, and then find the data The server where the block is stored, retrieves the server.

If there are 100 billion records in the server, and there are 1 million records in the three-level directory, 100 billion IO operations are required in the prior art, but the present invention requires 1 million IO operations.

In addition, in the prior art, multiple operations such as string interception, matching, and deduplication are performed on 100 billion object records, but the object records of the present invention only need to remove the leading characters.

In an embodiment of the present invention, by adding an identifier before the initial letter of the lowest-level object or directory of a given path, the object or directory is identified as the lowest layer; the parent directory path of the object or directory is obtained, and the Whether the parent directory path is the first level, if not, an identifier is added before the first letter of the directory of the parent directory path to identify the parent directory path as the lowest level. Therefore, centralized storage of objects and directories at the same layer is realized, thereby improving efficiency during retrieval.

In another embodiment of the present invention, the system also includes a maintenance module 240, which is used to use the object or directory as the key of the large-capacity table. The large-capacity table is a hierarchical storage table for the object directory, and the corresponding The number of objects in is used as the value corresponding to the directory. When an object is added, the value corresponding to the upper-level directory of the object is incremented. If the upper-level directory of the object does not exist, the directory is created first, and the corresponding directory The value of the object is set to 1. When deleting an object, the key-value pair record of the object is deleted first, and the value of the upper directory of the object is decremented. If the value of the upper directory of the object is decremented to 0, the Directory deletion.

In the embodiment of the present invention, when deleting an object under a directory in the directory hierarchy index, if the directory is empty, the directory will be deleted together; when adding or deleting objects, after decomposing each layer Accumulate or decrement the number of objects in the directory, and delete the directory when the number of objects in the directory is 0, while improving retrieval performance and storage capacity, it realizes the function of adding, deleting, maintaining and managing directory files.

The present invention will be further described below with a specific embodiment.

As shown in Figure 3, first deploy a distributed database on 10 servers configured as 2-way intel E5-2640v2, 128GB memory, and 4T hard disk space, and then create an object directory hierarchical storage table on it.

When a cloud storage user uploads an object, first escape the leading character before the first letter of the object or directory at the lowest level of the path, then obtain the path of the parent directory of the object or directory, and determine whether the path of the parent directory is the first layer, if not, add a leading character before the first letter of the directory of the parent directory path to escape, and store the directory of the parent directory path, and centrally store the objects and directories of the same layer.

When adding an object, the value corresponding to the upper-level directory of the object is incremented. If the upper-level directory of the object does not exist, create the directory first, and set the value corresponding to the directory to 1. When deleting the object, delete the object first The key-value pair record of the object, and decrement the value of the upper directory of the object, if the value of the upper directory of the object is decremented to 0, then delete the directory.

Wherein, the metadata table is used to record the situation of the hierarchical storage table of the object directory, for example, the storage situation of the object or the directory in the hierarchical storage table of the object directory on the server and on the data block of the server. When retrieving a directory or object, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, then find the server where the data block is stored, and retrieve the server .

In the prior art, when retrieving a directory or object, it is necessary to perform a full scan on the storage of the server, and to perform various operations such as string interception, matching, and deduplication on the retrieved directory or object.

In the embodiment of the present invention, compared with the traditional database, the present invention only needs to traverse the data of a certain directory or object layer to be queried, and the directory or object record only needs to remove the leader. Therefore, the computing and storage capabilities of the present invention have been expanded horizontally by 10 times, and horizontal expansion can be conveniently performed. Compared with the default storage method for large-capacity tables, the retrieval efficiency has been improved by 5 orders of magnitude.

So far, the present invention has been described in detail. Certain details well known in the art have not been described in order to avoid obscuring the inventive concept. Based on the above description, those skilled in the art can fully understand how to implement the technical solutions disclosed herein.

The method and apparatus of the invention may be implemented in many ways. For example, the method and device of the present invention can be realized by software, hardware, firmware or any combination of software, hardware, and firmware. The above sequence of steps used in the method is for illustration only, and the steps of the method of the present invention are not limited to the sequence specifically described above unless specifically stated otherwise. Furthermore, in some embodiments, the present invention can also be implemented as programs recorded in recording media including machine-readable instructions for realizing the method according to the present invention. Thus, the present invention also covers a recording medium storing a program for executing the method according to the present invention.

Although some specific embodiments of the present invention have been described in detail through examples, those skilled in the art should understand that the above examples are for illustration only, rather than limiting the scope of the present invention. Those skilled in the art will appreciate that modifications can be made to the above embodiments without departing from the scope and spirit of the invention. The scope of the invention is defined by the appended claims.

Claims (8)

1. A storage method based on a hierarchical directory of a large-capacity table, comprising: add an identifier before the first letter of the lowest-level object or directory of the given path, identify the object or directory as the lowest level, and store the object or directory; Obtain the parent directory path of the object or directory, and judge whether the parent directory path is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path to identify the parent directory path is the lowest level and stores the directory of the parent directory path; Save the start record and end record of the data block, and the server where the data block is stored, wherein the data block includes the records of objects or directories in the large-capacity table; When retrieving a directory or object, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, then find the server where the data block is stored, and retrieve the server . 2. the storage method of the hierarchical directory based on the mass table according to claim 1, further comprising: The object or directory is used as the key of the large-capacity table, and the number of objects corresponding to the layer below the directory is used as the value corresponding to the directory; When adding an object, the value corresponding to the upper directory of the object is incremented; When deleting an object, first delete the key-value pair record of the object, and decrement the value of the upper directory of the object. 3. the storage method of the hierarchical directory based on the large-capacity table according to claim 2, comprising: When adding an object, if the upper directory of the object does not exist, create the directory first, and set the value corresponding to the directory to 1; When deleting an object, if the value of the upper directory of the object is decremented to 0, the directory is deleted. 4. The storage method of a hierarchical directory based on a large-capacity table according to any one of claims 1 to 3, comprising: The identifier is a leading character, which identifies objects at the same layer or precedes the sorting of directories. 5. A storage system based on a hierarchical directory of large-capacity tables, comprising: The processing module is used to add an identifier before the initial letter of the lowest-level object or directory of a given path to identify the object or directory as the lowest level; obtain the parent directory path of the object or directory, and determine the parent directory path Whether it is the first layer, if not, add an identifier before the first letter of the directory of the parent directory path, and identify the parent directory path as the lowest layer; storage module, used to store objects or directories; A record module, configured to save the start record and end record of the data block, and the server where the data block is stored, wherein the data block includes records of objects or directories in the large-capacity table; Wherein, when retrieving a directory or object, first find the data block corresponding to the directory or object to be retrieved through the start record and end record of the data block in the metadata table, then find the server where the data block is stored, and retrieve the data block. said server. 6. The storage system based on the hierarchical directory of the large-capacity table according to claim 5, further comprising: The maintenance module is used to use the object or directory as the key key of the large-capacity table, and the number of objects corresponding to the lower layer of the directory as the value value corresponding to the directory; when adding an object, the upper directory of the object corresponds to The value of the object is incremented; when deleting an object, the key-value pair record of the object is deleted first, and the value of the upper directory of the object is decremented. 7. The storage system based on the hierarchical directory of the large-capacity table according to claim 6, comprising: The maintenance module is used to create a directory first if the upper-level directory of the object does not exist when adding an object, and set the value corresponding to the directory to 1; when deleting an object, if the value of the upper-level directory of the object is decremented If it is 0, the directory will be deleted. 8. The storage system based on the hierarchical directory of the large-capacity table according to any one of claims 5 to 7, comprising: The identifier is a leading character, which identifies objects at the same layer or precedes the sorting of directories.