CN104281517B - Log mode based memory space management method and device - Google Patents

Abstract

The present invention provides a log-based storage space management method, which is applied to storage devices, and the method includes: when applying for storage space or releasing storage space, recording the corresponding Application or release log, the application or release log records the initial location and size information of the application or release storage space; according to a certain strategy, perform the operation of merging storage space on the application or release log and the last merged log in sequence , and record the merged log generated this time in the SMR, where the merged log records the starting position and size of the free storage space. The technical scheme of the invention solves the problem of device performance degradation caused by the release of a large amount of random storage space in the existing storage space management, and does not require high memory capacity of the storage device.

Description

A log-based storage space management method and device

technical field

The present invention relates to the technical field of storage, and in particular to a storage space management method and device based on a log mode.

Background technique

Whether it is an application based on a file system or other block devices, there are two basic requirements: 1. On which blocks of the block device the record data is stored; 2. Which blocks of the block device are idle.

In principle, it is not necessary to record which blocks of the block device are free, but only record which blocks the data is stored on. Because there are only two states of a block: the use state or the idle state. Therefore, which blocks are free can be deduced from the used blocks. However, this again means that all used blocks need to be traversed. In order to make the application for free blocks more efficient, most block devices will record which blocks are free.

At present, there are two main ways to record whether the block is in the idle state or in the used state, one is the bitmap method, and the other is the b-tree method. Of course, the most commonly used method is bitmap. The bitmap uses the Nth bit of a continuous space to indicate whether the Nth block of the block device is free or occupied. Relatively speaking, the resource consumption of the bitmap is relatively small. For a block size of 4KB, its resource consumption is only 1/(4096*8)=0.003% (8 represents 8 bits in a byte). For a file system with a size of 1GB, the required space for the bitmap is 32KB; for a file system with a size of 1TB, the required space is 2MB. This size is acceptable for the system memory, but from the perspective of search efficiency, it is relatively low. And if for a 1PB file system, the required size of the bitmap becomes 32GB, which is unacceptable for the memory of most devices. This means that every time a block state needs to be obtained, it needs to be read from disk, which will seriously affect the performance of the file system.

To solve the above problems, an easy-to-think method is to divide the bitmap into multiple small bitmaps, and then use the bitmap to map the divided small bitmaps, as shown in Figure 1. In this way, it is possible to find out which small bitmaps have free blocks through the topmost bitmap; if the small bitmap is not in the memory, read the small bitmap from the disk.

However, the following problem still exists in this way: whether it is to apply for or release block resources, the bitmap needs to be updated. For the operation of applying for block resources, the update of the bitmap can be controlled, but it is difficult to control the operation of releasing block resources, because the release operation is triggered by the upper layer application. Frequent release of block resources means frequent update of the bitmap, which means a lot of read and write IO. What's more, if the update of the bitmap involves many small bitmaps, that is, the update of the bitmap has great randomness, the system will be overwhelmed.

B-tree uses extent (a continuous storage space) to manage continuous blocks. The Extent method uses the method of offset plus length to manage free block space. But b-tree and bitmap have the same problems mentioned above.

Contents of the invention

In view of this, the present invention provides a log-based storage space management method.

The method is applied to a storage device, and includes: when applying for storage space or releasing storage space, recording a corresponding application or release log in the second mapping area SMR of a preset size, the application or release log records the application or release of storage space The starting position and size information of the storage space; according to a certain strategy, execute the storage space consolidation operation on the application or release log and the last merged log in sequence, and record the merged log generated this time in the SMR, so The merged log above records the starting position and size of the free storage space.

Preferably, the recording of the log in the SMR is carried out in a circular covering manner; the operation of performing storage space merging on the application or release log and the last merging log in sequence according to a certain strategy includes: when the last merging When the ratio of the generated merged logs and the total number of currently unmerged application or release logs to the total log capacity of the SMR content area reaches the preset threshold, the storage space is sequentially executed for the application or release logs and the last merged log An operation of merging; or, when the storage space is applied for and there is no storage space meeting the required size of the application, the operation of merging the storage space is sequentially performed on the application or release log and the last merged log.

Preferably, performing the operation of merging the storage space on the application or release log and the last merged log sequentially includes: for each currently unmerged application or release log in sequence, according to the starting position and size recorded in the log , to judge whether it can be merged with the current node in the red-black tree, and if so, merge it; insert the newly generated node into the red-black tree after the merge, and delete the merged node; the content of the newly generated node is : The starting position and size of the free storage space after this merge.

Preferably, the log recorded in the SMR includes: information indicating whether it is a space release operation or an application space operation; information indicating whether it is a log of a real application for a release operation or a log of a merge operation; the number Cur_journal_id of the log, the number follows the log increases sequentially; the sequence of performing storage space consolidation operations on the application or release log, and the last merge log is to execute the merge operations sequentially in the order of increasing log numbers.

Preferably, the disk storage space is divided into several regions, and each region includes a data region DR and a mapping region MR; wherein MR includes a main mapping region PMR and a second mapping region SMR; PMR includes a header region and records belonging to the The location of each SMR managed by the PMR and the content area of the next PMR location; the SMR includes a header area and a content area for recording the log.

Preferably, after the storage device starts working, it will read PMR information and SMR information from the disk into the memory, and manage the storage space based on the PMR information and SMR information in the memory.

Preferably, if the log with the largest number in the SMR content area in the memory read from the disk is a merged log, when a further merge operation is required, the last merged log before the merged log, the last After the log is merged, the application log and release log are merged again.

Preferably, when applying for a storage space, if there are several continuously available spaces meeting the application conditions in the DR managed by the SMR, then select the available space with a smaller logical block address lba.

Compared with the prior art, the technical solution of the present invention solves the problem of device performance degradation caused by the release of a large amount of random storage space in the existing storage space management, and does not require high memory capacity of the storage device.

Description of drawings

Fig. 1 is a schematic diagram of multi-layer bitmap mapping.

Fig. 2 is a flowchart of an embodiment of the present invention.

FIG. 3 is a structural diagram of division of a storage space according to an embodiment of the present invention.

Fig. 4 is a log content diagram of the embodiment of the present invention.

Fig. 5 is an example diagram of log merging according to the embodiment of the present invention.

FIG. 6( a ) to FIG. 6( b ) are diagrams illustrating another example of log merging according to the embodiment of the present invention.

detailed description

In view of the technical problems mentioned in the background art, the present invention mainly provides a technical solution for storage space management based on a log method. The technical solution solves the problem of device performance degradation caused by the release of a large amount of random storage space in the existing storage space management. It will be described in detail below through specific examples.

Please refer to the flowchart of the embodiment of the present invention shown in FIG. 2 .

S21. When applying for storage space or releasing storage space, record the corresponding application or release log in the second mapping area SMR with a preset size, and the application or release log records the initial position and size information of the application or release storage space .

S22. According to a certain strategy, sequentially perform storage space consolidation operations on the application or release log and the last merged log, and record the merged log generated this time in the SMR, and the merged log records the free The starting location and size of the storage space.

The above method only records the corresponding application or release operation log when applying for or releasing the storage space; when certain conditions are met, the merge operation is performed on the above application or release log (the essence of the merge operation is: count the storage Which space in the space has been released, the space that has been continuously released, that is, the extent, is merged, and the result of the merge operation is appended to the SMR area as a merge log and recorded as a new log). In this way, frequent storage space management is avoided, and the performance of the storage device is improved. In addition, the merging log records the initial location and size of the free storage space, and the application operation for a new storage space can judge whether the application requirement is met according to the initial location and size, and if so, directly apply for the storage space.

Please refer to FIG. 3 further. As an example, the storage space of the storage device may be divided in the manner shown in FIG. 3 . The storage space is divided into several regions, and each region includes a data region DR (data region) and a mapping region MR (map region); wherein MR includes a main mapping region PMR and a second mapping region SMR; PMR includes a header region ( map region head) and the content area that records the position (SMR Entry) of each SMR managed by the PMR and the next PMR position (Next PMR Entry); SMR includes the head area (Map Region Head) and records the log ( Map Region Journal) content area.

The storage space adopts a two-level mapping method, and each region region can be divided according to a certain size, for example, 128GB. In this way, the entire storage space will be divided into several regions, and each region includes the above-mentioned two-level mapping structure and is managed separately.

As an example, please refer to Figure 4 for the log Map Region Journal (MRJ) recorded in the content area of SMR. Each MRJ includes: 2-bit Reserved (reserved) bits. Ops_flag occupies 2 bits, where the low bit indicates the operation of releasing space or applying for space. For example, the release operation is 0, and the application operation is 1; the high bit indicates whether the log is a real application/release log or a log generated by merging. For example, the real application/release log is 0, and the merged log is 1. Occupying 28 bits respectively (also means that the maximum capacity of DR is (2^28-1)*4KB≈1TB) Offset and Size, the Offset indicates the offset of the space involved in the operation in DR (relative position, in units of 4KB), Size indicates the size involved in the operation. Cur_journal_id indicates the id of the current journal, and the id will be added once for each journal. The starting position of the storage space for log records above is represented by Offset in this example.

The above PMR information and SMR information are stored in the internal memory of the storage device; other information is recorded in the disk space. Since the PMR information and the SMR information require less space, the memory size requirement is relatively low. Of course, the memory can further store the information of the last accessed storage space of the DR corresponding to the SMR, so that when applying for storage space later, if the storage space meets the requirements of the application, the space can be directly drawn from it.

Since the size of the SMR content area used to record logs is preset, and the logs corresponding to application operations, release operations, and merge operations are constantly increasing, so here the log is recorded in the SMR in a circular coverage manner.

In order to manage the storage space accurately, it is necessary to adopt a certain strategy for the merging of logs. Strategy 1: When the ratio of the total number of merged logs generated by the last merge and the total number of application or release logs that have not been merged to the total capacity of the logs in the SMR content area reaches the preset threshold, the application or release logs, and the above Merge logs once to perform storage space merging operations; Strategy 2: When applying for storage space and there is no storage space that meets the required size of the application, sequentially perform storage space merging on the application or release log and the last merged log operation. Here are just two examples, and this embodiment does not exclude other storage space management strategies.

Please refer to an example given in Figure 5, "MRJ 45" in the first line indicates the 45th log, and "1" in the first line indicates that the 45th log is a merged log; other lines have the same interpretation. It can be seen from this example that the logs before the 45th log have been merged, and two merged logs 45 and 46 have been formed. The 45 and 46 merged logs are the merged logs generated by the previous merge; after that, Several real (non-merged) operation logs are newly generated: 47, 48, 49, 50, 51, 52. In this way, the merged logs generated by the last merge and the currently unmerged logs are the following logs: 45 to 52, a total of 8 entries. The total capacity of the logs in the SMR content area here is 10, so its proportion is 80%. When the preset threshold in the above strategy 1 is 78%, it is currently necessary to perform a merge operation on the logs 45-52. This merging strategy can prevent valid logs from being overwritten without processing in time.

Strategy 2 When applying for storage space, if the space to be applied is larger than the current free space, you can use log merging to check whether the free space corresponding to the merged new log meets the application requirements. If so, Then the application operation will be successful, and the offset value of the merged space will be directly fed back to the upper layer.

When this embodiment performs a storage space merging operation for logs, the merging operation may be performed by relying on a red-black tree. For example, for each application or release log that has not been merged, judge whether it can be merged with the current node in the red-black tree according to the starting position and size of the application or release log recording space, and if possible, merge; merge Then insert the newly generated nodes into the red-black tree, and delete the merged nodes. The content of the newly generated node is: the starting position and size of the free storage space after merging. Each node of the red-black tree records the starting position and size information of the free space, and the index value is the starting position. The principle that the above can be merged is that the free space information recorded by the nodes in the red-black tree and the application/release space recorded in the log overlap, partially overlap, and continue.

Here are a few examples to illustrate the above merge operation:

Example 1: There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, it is necessary to merge release logs with an offset value of 36 and a size of 4K. According to the above offset and size values, it is judged that the current log can be merged with this node, and the offset value corresponding to the merged new node is 32, and the size value is 20. Therefore, insert the new node into the red-black tree according to its index value of 32, and delete the node with the original offset value of 32 and the size value of 16K from the red-black tree. And generate a merge log in SMR, the content of the merge log is: release operation, offset value is 32, size value is 20.

Example 2. There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, it is necessary to merge release logs with an offset value of 31 and a size value of 4KB. According to the above offset and size values, it is judged that the current log can be merged with this node, and the offset value corresponding to the merged new node is 31, and the size value is 20. Therefore, insert the new node into the red-black tree according to its index value 31, and delete the node with the original offset value of 32 and the size value of 16K from the red-black tree. And generate a merge log in SMR, the content of the merge log is: release operation, offset value is 31, size value is 20.

Example 3. There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, it is necessary to merge release logs with an offset value of 32 and a size value of 16KB. Ignore this release log directly without any processing.

Example 4. There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, the application logs whose offset value is 34 and size value is 4KB need to be merged. At this point, the original node needs to be split into two, and the original node should be deleted. The offsets of the newly generated nodes are 32 and 35 respectively, and the size values are 8K and 4K respectively. At this point, you need to further generate two merged logs in SMR.

Example 5. There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, the application logs whose offset value is 35 and size value is 4KB need to be merged. At this time, delete the original node, and the offset value of the newly generated node is 32, and the size value is 12K; in fact, it is only necessary to directly change the size value of the original node to 12K. Further generate a merged log corresponding to the new node in the SMR.

Example 6. There is already a node representing free space in the red-black tree: the offset value is 32, and the size value is 16K; assuming that every 4K, the offset value increases by 1. Currently, the application logs whose offset value is 32 and size value is 4KB need to be merged. At this point, the original node is deleted, and the newly generated node has an offset value of 33 and a size value of 12K. Further generate a merged log corresponding to the new node in the SMR.

Here is a situation that needs to be explained. When the storage device is started, it is first necessary to read the PMR information and SMR information in the disk into the memory. At this time, the situation shown in Fig. 6(a) or Fig. 6(b) may appear. In Figure 6(a), since the MRJ with the largest journal_id number is the real application or release log, so if you want to merge at this time, you only need to merge the three MRJs with journal_ids of 09, 10, and 11 to participate in the log merge; and Figure 6 ( In b), since the MRJ with the largest journal_id number is a merged log, if you want to perform a merge operation at this time, you need to merge the four logs with journal_ids of 06, 07, 08, and 09. Among them, the logs with journal_id 06 and 07 are the merged logs generated last time; the logs with journal_id 08 and 09 are the real application/release logs newly generated after the last merged log. If the merged result is consistent with the results of the current journal_id 10 and 11, no operation is required. If the merged result includes other merged results besides the results of the current journal_id 10 and 11 logs, further add the logs of the other merged results. In this case, the last merge may not be complete due to system shutdown or other circumstances Finish.

In addition, there is another point that needs to be explained. When applying for storage space, in addition to considering the size of the continuous available space in the DR managed by the SMR, it is also necessary to consider that the available space is located where the logical block address lba is as small as possible. This is mainly because for the existing hard disk, the track corresponding to the small lba is on the outer side of the hard disk. When the rotation speed of the hard disk platter is a constant value, the outer side has a higher linear speed, which means a faster read and write rate ( The average speed ratio of the outer track to the inner track is 2:1).

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the present invention. within the scope of protection.

Claims (8)

1. A storage space management method based on a log mode, the method is applied to a storage device, and it is characterized in that the method comprises: When applying for storage space or releasing storage space, record the corresponding application or release log in the second mapping area SMR of the preset size. The application or release log records the initial position and size information of the application or release storage space, and stores The storage space of the device is divided into several regions, and each region includes a data region DR and a mapping region MR; wherein MR includes a main mapping region PMR and the second mapping region SMR; When the ratio of the combined log generated by the last merge and the total number of application or release logs that have not been merged to the total log capacity of the SMR content area reaches the preset threshold, or when the storage space is applied for and does not meet the required size of the application When storing space, sequentially execute the storage space merging operation on the application or release log and the last merging log, and record the merging log generated this time in the SMR, and the merging log records the free storage space The starting position and size of . 2. The method according to claim 1, characterized in that the recording of the log in the SMR is carried out in a circular coverage manner. 3. The method according to claim 1, wherein the sequentially performing the operation of merging storage space on the application or release log and the last merged log comprises: sequentially targeting each currently unmerged application or release log Log, according to the starting position and size recorded in the log, judge whether it can be merged with the current node in the red-black tree, and if so, merge it; after the merge, insert the newly generated node into the red-black tree, and delete the The merged node; the content of the newly generated node is: the starting position and size of the free storage space after this merge. 4. The method according to claim 1, wherein the log recorded in the SMR includes: information indicating whether it is a space release operation or an application space operation; whether it is a log of a real application for a release operation or a log of a merge operation Information; the number Cur_journal_id of the journal, which increases sequentially with the number of logs; The sequence of performing storage space merging operations on the application or release log and the last merging log is to perform the merging operation in sequence in the order of increasing log numbers. 5. The method according to claim 1, wherein the PMR includes a header area and a content area that records the positions of each SMRs managed by the PMR and the next PMR position; the SMR includes a header area and records The content area of the log. 6. the method for claim 5, is characterized in that, after described storage device starts work, will read PMR information, SMR information in internal memory from disk, and store based on the PMR information in internal memory and SMR information management of space. 7. The method according to claim 6, wherein if the log with the largest number in the SMR content area in the internal memory read from the disk is a merged log, when further merge operations are needed, it is necessary to redo the log Perform a merge operation on the last merged log before the above merged log, the application log after the last merged log, and the released log. 8. The method according to claim 1, wherein when applying for storage space, if there are several continuously available spaces that meet the application conditions in the DR managed by SMR, then select the available space with the smallest logical block address lba space.