Patent Description:
In a log-structured file system (log structured file system, LFS), storage space of an entire storage device is considered as a log. When a data write request is received, data is continuously written, starting from a current write location. According to a log recording principle, written data that may be originally discrete is aggregated into contiguous written data, and then the written data is submitted to the storage device, to achieve relatively high random write performance. However, as an application continuously creates, modifies, or deletes a file in the LFS, idle space in the LFS is fragmented. However, data writing requires contiguous idle space. Therefore, idle space reclaiming is performed on a storage fragment in the LFS. To be specific, the fragmented idle space is arranged into contiguous idle space to meet a continuous write mode in a log structure.

Currently, the log is divided into a plurality of segments (segment) in the LFS. The segment is a storage area with a fixed size. In the LFS, the segment is used as a unit for storage, and the segment is divided into blocks. A storage fragment management method provided in the prior art includes: identifying a segment in which a storage fragment appears; replicating data of a valid block in the segment; and writing the data of the valid block into contiguous idle segments. After the operations are completed, storage space occupied by the segment in which the storage fragment appears is released, and the segment is re-marked as an idle segment. However, in this case, there is the following disadvantage: If the data of the valid block in the segment in which the storage fragment appears is hot data, in other words, a probability that the data is updated is relatively high, after the data of the valid block is written into the idle segment, the data in the segment may be updated or deleted soon. Consequently, a storage fragment reappears in the segment. Therefore, the data of the valid block in the segment needs to be migrated again, resulting in extra power consumption. <CIT> discloses a nonvolatile memory device including a memory area having free segments and first to fourth regions having used segments. A garbage collection method includes selecting a target segment from the used segments, moving a valid data block from the selected target segment to the used segments, and erasing data of all data blocks in the selected target segment and making the selected target segment into a free segment. When the number of free segments is greater than a predefined value, the target segment is selected by a first method and valid data blocks in the target segment are moved by a second method. When the number of free segments is less than the predefined value, the target segment is selected by a third method and valid data blocks in the target segment are moved by a fourth method.

This application provides a storage fragment management method and a terminal, to resolve a problem that power consumption is high when data migration is performed on a storage fragment in an existing log-structured file system.

According to a first aspect, an embodiment of this application provides a storage fragment management method, where the method may be applied to a file system of a terminal, and the file system includes at least one segment. The method includes: first determining, by the terminal, a source segment from the file system based on an aging degree of the segment and a valid block ratio of the segment; then determining, by the terminal from the file system based on an aging degree of the source segment, a target segment whose aging degree is consistent with the aging degree of the source segment; and finally migrating, by the terminal, data of a valid block in the source segment to an idle block in the target segment.

In this embodiment of this application, because the aging degree of the source segment is consistent with that of the target segment, data in the target segment has an equivalent hotness degree after migration. Therefore, time for re-updating or re-deleting data of each block in the target segment is basically the same, and it is not easy to cause re-fragmentation of the target segment, so that migration times can be reduced, and power consumption can be reduced to some extent.

According to the first aspect, the source segment is a segment whose aging degree is greater than or equal to a first threshold and whose valid block ratio is the lowest in the file system. Specifically, the terminal may first traverse the segment in the file system to determine a first candidate set, where an aging degree of a segment in the first candidate set is greater than or equal to the first threshold, and then the terminal determines, from the first candidate set, a segment with a lowest valid block ratio as the source segment. In this way, a data amount of a valid block in the source segment selected by the terminal each time is the smallest. Therefore, a data write amount during migration can be reduced, and power consumption is reduced to some extent.

In a possible design, when a quantity of segments in the first candidate set is less than or equal to a second threshold, the terminal determines, from the first candidate set, the segment with the lowest valid block ratio as the source segment; or when the quantity of segments in the first candidate set is greater than the second threshold, the terminal removes at least one segment with a lowest aging degree from the first candidate set until the quantity of segments in the first candidate set is less than or equal to the second threshold, and then determines, from the first candidate set, the segment with the lowest valid block ratio as the source segment. In this way, because all segments in the first candidate set are segments with relatively high aging degrees, an aging degree of the selected source segment is high enough. In addition, a data amount of a valid block in the source segment selected by the terminal is the smallest. Therefore, a data write amount during writeback can be reduced, and power consumption is reduced to some extent.

In a possible design, that the aging degree of the target segment is consistent with that of the source segment in the storage fragment management method may be understood as that the aging degree of the target segment is greater than or equal to the first threshold, and the aging degree of the target segment falls within a specified value range. It should be noted that the specified value range is generated based on the aging degree of the source segment. For example, a central value of the specified value range is the aging degree of the source segment. In this way, the aging degree of the target segment is the same as or close to that of the source segment. Therefore, data in the target segment has an equivalent hotness degree after migration.

According to the first aspect that the aging degree of the target segment is consistent with that of the source segment in the storage fragment management method may be understood as that the aging degree of the target segment is greater than or equal to the first threshold, the aging degree of the target segment falls within the specified value range, and the target segment is a segment whose aging degree is greater than or equal to the first threshold and that has a highest valid block ratio in segments whose aging degrees fall within the specified value range. In this way, the aging degree of the target segment is the same as or close to that of the source segment, and there is a relatively high probability that the target segment is filled with the data of the valid block in the source segment. Therefore, after migration, the idle block in the target segment is fully used, and data in the target segment has an equivalent hotness degree.

In a possible design, the target segment may be determined by using the following steps. Specifically, the terminal traverses the segment in the file system to determine a second candidate set, where an aging degree of a segment in the second candidate set is greater than or equal to the first threshold; then, the terminal determines a third candidate set from the second candidate set, where an aging degree of a segment in the third candidate set falls within the specified value range; and finally the terminal selects, from the third candidate set, a segment with a highest valid block ratio as the target segment. In this way, the terminal can implement that the aging degree of the determined target segment is consistent with that of the source segment, and the idle block in the target segment can be also fully filled, so that the target segment is fully used.

In a possible design, a condition for triggering the terminal to determine the source segment from the file system may be as follows: When a quantity of idle segments in the file system is less than a third threshold, the terminal determines the source segment from the file system based on the aging degree of the segment and the valid block ratio of the segment. Alternatively, the terminal periodically determines the source segment from the file system based on the aging degree of the segment and the valid block ratio of the segment. In other words, the terminal may be triggered to perform storage fragment management because idle segments of an LFS are insufficient, or the terminal may have a cleanup thread to periodically determine the source segment and migrate data in the source segment. Any trigger condition facilitates the terminal to reclaim storage space of the terminal in time.

It should be noted that in a possible design, the file system mentioned in this embodiment of this application may be the LFS.

According to a second aspect, an embodiment of this application provides a terminal according to claim <NUM> or a computer storage medium of claim <NUM>.

The following further describes in detail the embodiments of this application with reference to accompanying drawings.

Embodiments of this application provide a storage fragment management method and a terminal, to resolve a problem that power consumption is high when data migration is performed on a storage fragment in an existing log-structured file system. The method and the terminal in this application are based on a same inventive concept. The method and the terminal have similar problem resolving principles. Therefore, for implementation of the device and the method, mutual reference may be made. Details of repeated parts are not described again.

The following explains and describes some terms in this application.

The following uses a disk as an example of the storage device, and first describes related information about a log-structured file system in detail.

Table <NUM> describes main data structures of the LFS on the storage device and functions and locations of the main data structures. A checkpoint region is a fixed location on the storage device, and is used to position a disk block or a flash block on which an inode map is located and determine a last checkpoint in a log. A current location of each index node is maintained by using the inode map, and information about the inode map is cached on the disk. Therefore, the storage device does not need to be accessed during searching.

In the LFS, a log is a disk structure. To facilitate management of idle space, the LFS divides a log into segments. Metadata (meta data) in the LFS is mainly distributed in checkpoints and segments, and the disk layout of the log-structured file system is shown <FIG>. A pointer of the index node and a current location of the index node given by the inode map often change. A timestamp in a checkpoint can be used to determine a last successful checkpoint.

A log in the LFS uses a sequential and incremental data structure. Description of the LFS still uses a conventional index organization model. The LFS accesses an index node in the log. The index node enables the LFS to retrieve relative information of a file from the log in a random access mode. Steps for searching for an index node in the LFS is as follows: Find a nearest inode map in checkpoints located at a fixed region on the disk. Find a latest version of the index node from the inode map. A corresponding data block can be found based on the index node. As shown in <FIG>, an inode map is found in a checkpoint region, then three index nodes are found in the inode map, and a corresponding data block is found based on each index node.

In the log-structured file system, each segment is a sequence including a plurality of blocks. The status of the block may be: (<NUM>) idle or (<NUM>) valid. Statuses of these blocks are defined in Table <NUM>.

That the status of the block is valid means that there is valid data in the block. The status of the block may be determined based on information about the segment summary or the segment use table. The following two determining manners are listed in this embodiment of this application for description.

Manner <NUM>: In the LFS, summary information is recorded for each block. The summary information includes an inode number (the index node sequence number is used to indicate that this disk block belongs to which file) and an offset (the offset is used to indicate a sequence number of the disk block in the file). This information is stored in a segment summary block (segment summary block) in a header of the segment. Based on the information about the segment summary block, it can be directly determined whether there is valid data in the block. If there is the valid data, the block is a valid block, otherwise, the block is an idle block.

Manner <NUM>: Validity of blocks (block) may be determined by checking whether a block pointer of an index node (Inode) or an indirect block (Indirect block) of the file still points to these blocks. If the pointer still points to these blocks, these blocks are valid blocks, otherwise, these blocks are idle blocks.

Because a segment includes blocks, different combinations of statuses of the blocks in the segment determine a status of the segment. The status of the segment may be: (<NUM>) idle, (<NUM>) dirty, or (<NUM>) valid. Statuses of these segments are defined in Table <NUM>.

As shown in <FIG>, a log-structured file system <NUM> includes <NUM>, <NUM>, and <NUM>. Each segment is a set of a physical disk block or a flash memory block. For example, a capacity of the segment is <NUM> MB. All blocks in the segment <NUM> are idle, and therefore a status of the segment <NUM> is idle. There are two valid blocks and four idle blocks in the segment <NUM>, and therefore a status of the segment <NUM> is dirty. All blocks in the segment <NUM> are valid, and therefore a status of the segment <NUM> is valid.

Usually, data of a valid block in the segment may include hot data and cold data. The hot data means that data of the valid block may be updated or deleted soon, and the cold data means that data of the valid block may be updated or deleted after a long time. Because the segment includes the blocks, if data of a valid block in the segment is basically the cold data, the segment also is a cold segment. If data of a valid block in the segment is basically the hot data, the segment also is a hot segment. In other words, if the data of the valid block is cold data, time of last updated data stored in the segment use table (Segment use table) is usually relatively long from a current time, namely, the valid block is relatively old. Usually, an aging degree may also be used to measure a hotness degree of each segment. The aging degree is defined in the following manner: <MAT> <MAT>.

The last update time of the system is time at which the log-structured file system is last updated. The earliest update time of the system is time at which the log-structured file system is updated for the first time. The update time of the segment is an average update time of all valid blocks in the segment. Herein, n is a quantity of valid blocks in the segment, T <NUM> is an update time of a first valid block in the segment, T2 is an update time of a second valid block in the segment, and Tn is an update time of an nth valid block in the segment.

An embodiment of this application provides a storage fragment management method. The method may be used to perform garbage collection on a storage fragment on a storage device. According to a design principle of an LFS, as an application continuously creates, modifies, and deletes files in the LFS, idle space of the LFS is fragmented. Consequently, a large quantity of continuous write operations cannot be performed. Therefore, available space on the storage device needs to be collated. Currently, in the prior art, a garbage collection manner usually used by the log-structured file system is as follows: In a garbage clearing process, a segment with a lowest valid block ratio in segments in a dirty state is selected as a source segment each time, data in all valid blocks in the source segment is migrated to continuous idle space, and then storage space occupied by the source segment is collected. As shown in <FIG>, before garbage collection, there are three valid blocks and three idle blocks in a source segment, and all blocks in a target segment are idle. After garbage collection, data of the valid blocks in the source segment is migrated, the source segment is filled with idle blocks, first three blocks in the target segment are valid, and last three blocks in the target segment are idle. However, a disadvantage of this operation is that if data stored in the source segment is hot data, data of the valid blocks in the source segment may be updated or deleted soon. This causes repeated migration and additional power consumption.

According to the storage fragment management method provided in this embodiment of this application, an aging degree of a segment is considered in a process of selecting the target segment and the source segment. According to the method in this embodiment of this application, a source segment with a relatively high aging degree is selected, and data of a valid block in the source segment is migrated to an idle block in a target segment whose aging degree is consistent with that of the source segment. In this way, data in the target segment has an equivalent hotness degree after migration. Therefore, time for re-updating or re-deleting data of each block in the segment is basically the same, and it is not easy to cause re-fragmentation of the target segment, so that migration times can be reduced, and power consumption can be reduced to some extent.

To describe the technical solutions in the embodiments of this application more clearly, the following describes in detail a storage fragment management method and a terminal in the embodiments of this application with reference to the accompanying drawings. Referring to <FIG>, an embodiment of this application provides a storage fragment management method. The method may be performed by a terminal. A specific procedure includes the following steps.

Step <NUM>: The terminal determines a source segment from a file system based on an aging degree of a segment and a valid block ratio of the segment.

Specifically, for example, the file system is an LFS, and a processor of the terminal initiates a cleanup thread. The cleanup thread may first traverse all segments in the log-structured file system, determine the source segment whose aging degree and valid block ratio meet a specified condition, and then write data of a valid block in the source segment into a cache. The specified condition may be: The source segment is a segment whose aging degree is greater than a first threshold and whose valid block ratio is the lowest in the LFS. Certainly, the specified condition may alternatively be: The source segment is a segment whose aging degree is greater than a first threshold and whose valid block ratio is the second lowest in the LFS. Alternatively, the specified condition may be: The source segment is a segment whose aging degree is greater than a first threshold and whose valid block ratio is less than a threshold in the LFS. In other words, the source segment may have a relatively high aging degree and a relatively low valid block ratio.

Usually, the cleanup thread cyclically traverses the LFS a plurality of times, and selects a segment whose aging degree is greater than the first threshold and whose valid block ratio is the lowest in the LFS as a source segment in each traversal. In this way, because the valid block ratio of the source segment determined by the cleanup thread each time is the lowest, a data amount of a valid block is also the smallest, and an amount of data that needs to be migrated is also the smallest. In comparison, this condition can be used to reduce a write amount during migration, and reduce power consumption to some extent. Similarly, when a segment whose aging degree is greater than the first threshold and whose valid block ratio is relatively low (less than a threshold) is selected as a source segment in each traversal, an amount of data that needs to be migrated is also relatively small. This can also reduce a write amount during migration, and reduce power consumption.

Specifically, in a possible design, the terminal may first traverse the segments in the log-structured file system, and add each segment that is in a dirty state and whose aging degree is greater than the first threshold to a first candidate set. Then, the terminal traverses the first candidate set, to determine a segment with a lowest valid block ratio as the source segment. Subsequently, the terminal loads data of a valid block in the source segment into the cache, and adds an identifier to the segment.

In addition, when a quantity of segments in the first candidate set is less than or equal to a second threshold, the terminal determines, from the first candidate set, the segment with the lowest valid block ratio as the source segment.

Alternatively, when the quantity of segments in the first candidate set is greater than the second threshold, the terminal may remove some segments with relatively low aging degrees from the first candidate set until the quantity of segments in the first candidate set is less than or equal to the second threshold. Then, the terminal determines the segment with the lowest valid block ratio from the first candidate set as the source segment. In this way, because all segments in the first candidate set are segments with relatively high aging degrees, an aging degree of the selected source segment is high enough. In addition, a data amount of a valid block in the source segment selected by the terminal is the smallest. Therefore, a data write amount during writeback can be reduced, and power consumption is reduced to some extent.

Step <NUM>: The terminal determines, from the file system based on the aging degree of the source segment, a target segment whose aging degree is consistent with that of the source segment.

Specifically, in a possible design, that the aging degree of the target segment is consistent with that of the source segment in the storage fragment management method may be understood as that the aging degree of the target segment is the same as or close to that of the source segment. Specifically, when the target segment is selected, a segment whose aging degree is greater than or equal to a first threshold and whose aging degree falls within a specified value range may be selected from the file system as the target segment. The first threshold may be the same as the first threshold used to determine the source segment. The specified value range is generated based on the aging degree of the source segment. For example, a central value of the specified value range is the aging degree of the source segment. In this way, the aging degree of the target segment is the same as or close to that of the source segment. Therefore, data in the target segment has an equivalent hotness degree after migration.

Specifically, in a possible design, the cleanup thread may first traverse the segments in the log-structured file system, select, from segments in a dirty state, segments whose aging degrees are greater than the first threshold, and add all the selected segments to a second candidate set. Then, the cleanup thread traverses the second candidate set, to determine segments whose aging degrees are within the specified value range, and adds the segments to a third candidate set. Finally, the terminal selects, from the third candidate set, a segment whose aging degree is the closest to that of the source segment as the target segment, or randomly selects a segment as the target segment, or selects a segment whose aging degree is the highest as the target segment.

For example, it is assumed that the aging degree of the source segment is a (for example, <NUM>), and the pre-specified value range may be [a - <NUM>, a + <NUM>]. Therefore, the aging degrees of all the segments in the third candidate set are within [a - <NUM>, a + <NUM>]. Then, the terminal selects a segment from the third candidate set as the target segment.

For another example, in a possible design, the terminal may sort the segments in the second candidate set in descending order of aging degrees. Then, the terminal selects, by using the aging degree of the source segment as a center and using K as a radius, K segments whose aging degrees are higher than the aging degree of the source segment and K segments whose aging degrees are lower than the aging degree of the source segment, and adds the selected segments to the third candidate set. For example, it is assumed that the aging degree of the source segment is a (for example, <NUM>), and the terminal may select k (for example, k is <NUM>) segments whose aging degrees are lower than a and k segments whose aging degrees are higher than a from the sorted second candidate set, and use the selected <NUM> segments or (<NUM> + <NUM>) segments as the third candidate set. Then, the terminal selects a segment from the third candidate set as the target segment. If the second candidate set includes a segment whose aging degree is a, (<NUM> + <NUM>) segments are selected as the third candidate set. If the second candidate set does not include a segment whose aging degree is a, <NUM> segments are selected as the third candidate set.

In another possible design, that the aging degree of the target segment is consistent with that of the source segment in the storage fragment management method may be further understood as that the target segment is a segment whose aging degree is greater than or equal to the first threshold and that has a highest valid block ratio in segments whose aging degrees fall within the specified value range. In this way, the aging degree of the target segment is the same as or close to that of the source segment, and there is a relatively high probability that the target segment is filled with the data of the valid block in the source segment. Therefore, after migration, an idle block in the target segment is fully used, and data in the target segment has an equivalent hotness degree.

Specifically, in a possible design, the cleanup thread may first traverse the segments in the log-structured file system, select, from segments in a dirty state, segments whose aging degrees are greater than the first threshold, and add all the selected segments to a second candidate set. Then, the cleanup thread traverses the second candidate set, to determine segments whose aging degrees are within the specified value range, and adds the segments to a third candidate set. The terminal selects, from the third candidate set, a segment with a highest valid block ratio as the target segment.

For example, it is assumed that the aging degree of the source segment is a (for example, <NUM>), and the pre-specified value range may be [a - <NUM>, a + <NUM>]. Therefore, the aging degrees of all the segments in the third candidate set are within [a - <NUM>, a + <NUM>]. Then, the terminal selects the segment with the highest valid block ratio from the third candidate set as the target segment.

Step <NUM>: The terminal migrates the data of the valid block in the source segment to the idle block in the target segment.

In step <NUM>, after finding the source segment, the terminal may first load the data of the valid block in the source segment into the cache. Then, for each valid block in the cache, the terminal finds, based on a data index of the valid block in the cache, an identifier of the source segment in which the valid block is located, so as to determine the target segment based on the aging degree of the source segment. Then, the terminal writes the data of the valid block into the idle block in the target segment. In addition, the terminal releases storage space occupied by the source segment corresponding to the identifier of the source segment.

Usually, there are a plurality of trigger conditions for storage fragment management. Several conditions are listed below.

One trigger condition may be that only when a quantity of idle segments in the file system is less than a third threshold (for example, <NUM>), the processor generates, in a kernel, a cleanup thread used for garbage collection. The cleanup thread cyclically performs step <NUM> to step <NUM>, and stops when the quantity of idle segments in the file system increases to a specific threshold (for example, <NUM>). This storage fragment management manner may also be referred to as foreground garbage collection.

Another trigger condition may be that the processor configures, in a kernel, a cleanup thread used for garbage collection. The cleanup thread performs step <NUM> in real time or periodically. When the data of the valid block in the source segment determined by the terminal is loaded into the cache, the source segment is marked as a segment to be garbage-collected. In one case, when a percentage of the data of the valid block in the cache in all data in the cache is greater than or equal to a specific percentage, for example, <NUM>%, step <NUM> and step <NUM> are triggered to be performed. In another case, a loading time point is recorded and the data of the valid block is marked as dirty when the data of the valid block is loaded into the cache. Once a cache manager monitors that duration in which the data of the valid block is marked as dirty exceeds specific duration, step <NUM> and step <NUM> are triggered to be performed, and the data of the valid block in the cache is cleared. This storage fragment management manner may also be referred to as background garbage collection.

The following specifically describes an execution process of the storage fragment separately in two scenarios: a background garbage collection scenario and a foreground garbage collection scenario by using an LFS as an example.

A processor of a terminal generates, in a kernel, a cleanup thread used for garbage collection. The cleanup thread is used to perform processing in the following three phases. The three phases include: Phase <NUM>: selecting a source segment in real time or periodically, Phase <NUM>: selecting a target segment, and Phase <NUM>: garbage collection.

In Phase <NUM>: The source segment is selected in real time or periodically. The following provides a systematic description with reference to <FIG>.

Step <NUM>: The cleanup thread scans all segments in the LFS to obtain aging degrees of the segments.

Step <NUM>: The cleanup thread determines whether there is a segment, in the scanned segments, whose aging degree is greater than or equal to a first threshold; and if yes, skip to step <NUM>, or if no, skip to step <NUM>.

Step <NUM>: The cleanup thread adds a segment whose aging degree is greater than the first threshold to a first candidate set.

Step <NUM>: The cleanup thread determines whether a quantity of segments in the first candidate set does not exceed a second threshold, and if yes, skip to step <NUM>, or if no, skip to step <NUM>.

Step <NUM>: The cleanup thread removes a segment with a lowest aging degree from the first candidate set, and then performs step <NUM>.

Step <NUM>: The cleanup thread selects, from a current first candidate set, a segment with a lowest valid block ratio as the source segment.

Finally, in a possible design, the cleanup thread loads data of a valid block in the source segment selected each time to a cache, and then adds a to-be-garbage collection identifier to the source segment.

Phase <NUM> is executed to select the target segment.

When a percentage of data of a valid block in the cache in that of the cache reaches a specific percentage, for example, <NUM>%, the cleanup thread is triggered to select the target segment. Alternatively, when duration in which data of a valid block in the cache is marked as dirty exceeds specified duration, the cleanup thread is triggered to select the target segment.

In phase <NUM>, the target segment is mainly selected from segments in a dirty state in the LFS. The target segment can be selected based on an aging degree or based on an aging degree and a valid block ratio. An aging degree of a finally selected target segment is the same as that of the source segment. Specifically, for each valid block in the cache, the cleanup thread indexes, based on an index node corresponding to the data of the valid block in the cache, an identifier of a source segment in which the valid block is located, so as to determine the target segment based on an aging degree of the source segment corresponding to the source segment identifier. This is systematically described in the following with reference to <FIG>.

Step <NUM>: The cleanup thread determines whether there is a segment, in the scanned segments, whose aging degree exceeds a first threshold; and if yes, skip to step <NUM>, or if no, skip to step <NUM>.

Step <NUM>: The cleanup thread adds a segment whose aging degree is greater than the first threshold to a second candidate set.

It should be noted that, target segment selection may be triggered only when a percentage of data of a valid block in the cache reaches a specific percentage, target segment selection occurs after the source segment is selected, therefore, statuses of the segments in the LFS scanned by the cleanup thread in step <NUM> may be probably different from those of the segments in the LFS scanned by the cleanup thread in step <NUM>. Consequently, the obtained second candidate set may also be different from the first candidate set.

Step <NUM>: The cleanup thread traverses the second candidate set based on the aging degree of the source segment, to determine whether there is a segment whose aging degree is not within a specified value range, and if yes, skip to step 805a, otherwise, skip to step 806a.

Specifically, it is assumed that the aging degree of the source segment is a (for example, <NUM>), the specified value range may be [a - <NUM>, a + <NUM>], and the cleanup thread determines whether there is a segment, in the second candidate set, whose aging degree is not within [a - <NUM>, a + <NUM>].

Step <NUM>: The cleanup thread removes, from the second candidate set, the segment whose aging degree is not within the specified value range, and then performs step <NUM>.

Step <NUM>: The cleanup thread selects, from a current third candidate set, a segment with a highest valid block ratio as the target segment.

It should be noted that step <NUM> may alternatively be as follows: From a current third candidate set, the cleanup thread selects a segment whose aging degree is closest to that of the source segment as the target segment, or may randomly select a segment as the target segment, or selects a segment whose aging degree is the earliest as the target segment.

It should be noted that after determining the second candidate set, the cleanup thread may also determine the target segment in another manner. This is described in this specification with reference to <FIG>.

Step <NUM> to step <NUM> are the same as step <NUM> to step <NUM>, and details are not described.

Step <NUM>: The cleanup thread sorts segments in a second candidate set based on aging degrees, where the segments may be sorted in descending order, or may be sorted in ascending order.

Step <NUM>: The cleanup thread traverses the second candidate set based on the aging degree of the source segment, to determine whether there is a segment exceeds a quantity radius, and if yes, skip to step <NUM>, otherwise, skip to step <NUM>.

For example, the aging degree of the source segment is a (for example, <NUM>), and it is determined, from a sorted second candidate set, whether there is another segment in addition to three consecutive segments less than a and three consecutive segments greater than a.

Step <NUM>: Remove the segment beyond the quantity radius from the second candidate set, and then perform step 805b.

Step <NUM>: The cleanup thread selects, from a third candidate set, a segment with a highest valid block ratio as the target segment.

It should be noted that a quantity of target segments finally determined by the cleanup thread may be greater than <NUM>. For example, the cleanup thread selects the segment with a highest valid block ratio and a segment with a second highest valid block ratio from the third candidate set as the target segments. In this way, a problem that the target segment has too few idle blocks and cannot completely write valid data in the source segment canbe avoided.

For each valid block in the cache, the cleanup thread writes the data of the valid block in the cache into a corresponding target segment. After all data of the valid block in the cache is completely written, storage space occupied by the source segment corresponding to the to-be-garbage collection identifier is released.

It should be noted that Phase <NUM> and Phase <NUM> may be performed cyclically until a percentage of data of the valid block in the cache in that of the cache is less than a specific percentage (for example, <NUM>%). In addition, Phase <NUM> and Phase <NUM> may also be performed periodically. For example, the cleanup thread determines a source segment every five minutes, and loads data of a valid block in the source segment to the cache. After loading the data of the valid block in the source segment to the cache, the cleanup thread indexes to a corresponding source segment based on each valid block in the cache every <NUM> seconds, then, determines a target segment based on an aging degree of the source segment, and finally writes the data of the valid block into an idle block in the target segment.

In addition to that the cleanup thread may directly write the data of the valid block in the source segment into the idle block in the target segment, the cleanup thread may alternatively load the data of the valid block in the source segment into the cache, and then write the data in the cache into the idle block in the target segment. This is not specifically limited in this application.

If a cleanup thread of an LFS receives a resource recycling instruction, or when a quantity of idle segments in the LFS system decreases to a specified threshold (for example, <NUM>), a processor generates a cleanup thread. The cleanup thread is used to perform processing in the following three phases. The three phases include: Phase <NUM>: selecting a source segment and a target segment, and Phase <NUM>: garbage collection. This is systematically described in the following with reference to <FIG>.

Step <NUM>: The cleanup thread adds the segment whose aging degree is greater than the first threshold to a first candidate set.

Step <NUM>: The cleanup thread removes a segment with a lowest aging degree from the first candidate set, and then skips to step <NUM>.

Step <NUM>: The cleanup thread traverses the first candidate set based on an aging degree of the source segment, to determine whether there is a segment whose aging degree is not within a specified value range, and if yes, skip to step <NUM>, otherwise, skip to step <NUM>.

Specifically, it is assumed that the aging degree of the source segment is a (for example, <NUM>), the specified value range may be [a - <NUM>, a + <NUM>], and the cleanup thread determines whether there is a segment, in the first candidate set, whose aging degree is not within [a - <NUM>, a + <NUM>].

Step <NUM>: The cleanup thread removes, from the first candidate set, the segment whose aging degree is not within the specified value range, and then skips to step <NUM>, until aging degrees of all segments in the first candidate set are within the pre-specified value range.

Step <NUM>: The cleanup thread selects, from a current first candidate set, a segment with a highest valid block ratio as the target segment.

It should be noted that step <NUM> may alternatively be as follows: From a current first candidate set, the cleanup thread selects a segment whose aging degree is closest to that of the source segment as the target segment, or may randomly select a segment as the target segment, or selects a segment whose aging degree is the earliest as the target segment.

The cleanup thread writes data of a valid block in the source segment to the target segment, and then repeatedly performs step <NUM> to step <NUM> until a quantity of idle segments in the LFS system increases to a specified threshold (for example, <NUM>). Specifically, the cleanup thread may directly write the data of the valid block in the source segment into an idle block in the target segment, or the cleanup thread may load the data of the valid block in the source segment into the cache, and then write the data in the cache into the idle block in the target segment. This is not specifically limited in this application.

A quantity of target segments finally determined by the cleanup thread may be greater than <NUM>. For example, the cleanup thread selects the segment with a highest valid block ratio and a segment with a second highest valid block ratio from the first candidate set as the target segments. In this way, a problem that the target segment has too few idle blocks and cannot completely write valid data in the source segment can be avoided.

In addition, it should be noted that the manner shown in FIG. 7b may also be used as the manner of selecting the target segment in <FIG>. In addition, it should be noted that each of the source segment and the target segment shown in <FIG> may be determined from the first candidate set, or may be determined from different candidate sets. For example, the source segment is selected from segments, in the LFS, corresponding to a first moment, and the target segment is selected from segments, in the LFS, corresponding to a second moment. The second moment is later than the first moment, and segments, in the LFS, corresponding to the two moments may be different. Therefore, first candidate sets corresponding to the two moments may also be different.

Corresponding to the garbage collection phase, for example, as shown in <FIG>, before garbage collection, there are three valid blocks and three idle blocks in a source segment, and there are three idle blocks and three valid blocks in a target segment. When foreground garbage collection or background garbage collection is performed, all the six segments in the source segment are idle segments, and the target segment is full filled with valid blocks. After garbage collection is complete, storage space corresponding to the source segment is reclaimed, the source segment is reset to an idle segment, and new data may be written into the source segment again.

It should be noted that, in a possible design, during garbage collection, if there are a plurality of files whose data of a valid block in a source segment belongs to a same directory, the files in the same directory may be preferentially migrated to one target segment. In another possible design, during garbage collection, valid blocks in a source segment are grouped based on last modification time of each of the valid blocks, valid blocks at a same time or similar time are placed in a same group, and data of valid blocks in these groups is migrated to a same target segment.

An embodiment of this application further provides a computer-readable storage medium. The computer-readable storage medium includes a computer program. When the computer program is run on a terminal, the terminal is enabled to perform any possible implementation of the storage fragment management method.

An embodiment of this application further provides a computer program product. When the computer program product runs on a terminal, the terminal is enabled to perform any possible implementation of the storage fragment management method.

In some embodiments of this application, an embodiment of this application discloses a terminal. As shown in <FIG>, the terminal is configured to implement the method recorded in the foregoing method embodiments. The terminal includes a status cache module <NUM>, a source segment selection module <NUM>, a target segment selection module <NUM>, and a garbage collection module <NUM>. Modules included in the terminal may be implemented at a kernel layer in an Android operating system. The status cache module <NUM> obtains a status of a segment in an LFS, and calculates an aging degree and a valid block ratio of each segment. The source segment selection module <NUM> is configured to support the terminal in performing step <NUM> in <FIG>. The target segment selection module <NUM> is configured to support the terminal in performing step <NUM> in <FIG>. The garbage collection module <NUM> is configured to support the terminal in performing step <NUM> in <FIG>. All related content of the steps in the foregoing method embodiments may be cited in function descriptions of the corresponding functional modules.

In some other embodiments of this application, an embodiment of this application discloses a terminal. As shown in <FIG>, the terminal may include one or more processors <NUM>, a memory <NUM>, a display <NUM>, one or more applications (not shown), and one or more computer programs <NUM>. The foregoing components may be connected with each other by using one or more communications buses <NUM>. The one or more computer programs <NUM> are stored in the memory <NUM> and are configured to be executed by the one or more processors <NUM>. The one or more computer programs <NUM> include an instruction, and the instruction may be used to perform the steps in <FIG> and the corresponding embodiments.

The terminal may be a terminal device such as a mobile phone, a tablet computer, a notebook computer, an ultra-mobile personal computer (ultra-mobile personal computer, UMPC), a netbook, or a personal digital assistant (personal digital assistant, PDA). For example, the following describes a case that the terminal is a mobile phone. <FIG> is a block diagram of some structures of a mobile phone <NUM> related to the embodiments of the present invention.

As shown in <FIG>, the mobile phone <NUM> includes a display device <NUM>, a processor <NUM>, and a memory <NUM>. The memory <NUM> may be configured to store a software program and data. The memory <NUM> may mainly include a program storage area and a data storage area. The program storage area may store an operating system, an application program required by at least one function (for example, an image capture function), and the like. The data storage area may store data (for example, audio data, a phone book, and an image) created based on use of the mobile phone <NUM>, and the like. In addition, the memory <NUM> may include a high-speed random access memory, or may include a nonvolatile memory, such as at least one magnetic disk storage device, a flash storage device, or another volatile solid-state storage device. The storage fragment management method provided in the embodiments of the present invention is applicable to managing a storage fragment in the memory <NUM>.

The processor <NUM> runs the software program and the data stored in the memory <NUM>, to execute various function applications of the mobile phone <NUM> and perform data processing. The processor <NUM> is a control center of the mobile phone <NUM>, and is connected to all parts of the entire mobile phone by using various interfaces and lines. The processor <NUM> runs or executes the software program and/or the data that are/is stored in the memory <NUM>, to perform the various functions of the mobile phone <NUM> and perform data processing, thereby performing overall monitoring on the mobile phone. The processor <NUM> may include one or more general purpose processors, or may include one or more DSPs (digital signal processor, digital signal processor), or may include one or more ISPs (image signal processor, image signal processor), configured to perform a related operation, to implement the technical solutions provided in the embodiments of this application.

The mobile phone <NUM> further includes a camera <NUM> for capturing an image or shooting a video. The camera <NUM> may be an ordinary camera, or may be a focusing camera.

The mobile phone <NUM> may further include an input device <NUM>, configured to receive digital information, character information, or a contact touch operation/non-contact gesture that is input, and generate signal input that is related to user settings and function control of the mobile phone <NUM>, and the like.

The display device <NUM> includes a display panel <NUM>, configured to display information entered by a user or information provided for the user, various menu screens of the mobile phone <NUM>, and the like. In this embodiment of this application, the display panel <NUM> is mainly configured to display a to-be-detected image obtained by the camera or a sensor of the mobile phone <NUM>. Optionally, the display panel <NUM> may be configured by using a liquid crystal display (liquid crystal display, LCD), an OLED (organic light-emitting diode, organic light-emitting diode), or a like form.

In addition to the foregoing parts, the mobile phone <NUM> may further include a power supply <NUM>, configured to supply power to other modules. The mobile phone <NUM> may further include one or more sensors <NUM>, such as an image sensor, an infrared sensor, and a laser sensor. The mobile phone <NUM> may further include a radio frequency (radio frequency, RF) circuit <NUM>, configured to perform network communication with a wireless network device, and may further include a Wi-Fi module <NUM>, configured to perform Wi-Fi communication with another device to obtain images or data or the like transmitted by the another device.

The foregoing descriptions about implementations allow a person skilled in the art to understand that, for the purpose of convenient and brief description, division of the foregoing function modules is taken as an example for illustration. In actual application, the foregoing functions can be allocated to different modules and implemented according to a requirement, that is, an inner structure of an apparatus is divided into different function modules to implement all or some of the functions described above. For a detailed working process of the foregoing system, apparatus, and unit, refer to a corresponding process in the foregoing method embodiments, and details are not described herein again.

Functional units in the embodiments of this application may be integrated into one processing unit, or each of the units may exist alone physically, or two or more units are integrated into one unit.

Claim 1:
A storage fragment management method, applied to a file system of a terminal, wherein the file system comprises at least one segment, and the method comprises:
Determining (<NUM>), by the terminal, a source segment from the file system based on an aging degree of the segment and a valid block ratio of the segment, wherein the source segment is a segment whose aging degree is greater than or equal to a first threshold and whose valid block ratio is the lowest in the file system;
Determining (<NUM>), by the terminal, a target segment having an idle block available from the file system based on an aging degree of the source segment, wherein an aging degree of the target segment is consistent with that of the source segment, wherein that an aging degree of the target segment is consistent with that of the source segment comprises: the aging degree of the target segment is greater than or equal to a first threshold, and the aging degree of the target segment falls within a specified value range, wherein the specified value range is generated based on the aging degree of the source segment; and
Migrating (<NUM>), by the terminal, data of a valid block in the source segment to the idle block in the target segment.