CN109977031B

CN109977031B - Solid state disk garbage recycling method and solid state disk

Info

Publication number: CN109977031B
Application number: CN201711442349.0A
Authority: CN
Inventors: 熊伟; 张瑛
Original assignee: Chengdu Huawei Technology Co Ltd
Current assignee: Chengdu Huawei Technology Co Ltd
Priority date: 2017-12-27
Filing date: 2017-12-27
Publication date: 2021-06-01
Anticipated expiration: 2037-12-27
Also published as: CN109977031A

Abstract

The application provides a solid state disk garbage recycling method and a solid state disk, wherein the method comprises the following steps: determining the change trend of the residual space of the solid state disk SSD of at least two sampling points in a sampling interval corresponding to the current sampling point, wherein the sampling interval comprises a plurality of sampling points. And determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the change trend of the residual space in the sampling interval. And in a time period between the current sampling point and the next sampling point, performing garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point. The purpose of dynamically adjusting the recovery step length can be achieved, and therefore the garbage recovery rate of the SSD can be dynamically adjusted. Finally, the recovery concurrency number is always close to the stable concurrency number. In the process of SSD garbage collection, impact on the I/O of the SSD is reduced.

Description

Solid state disk garbage recycling method and solid state disk

Technical Field

The application relates to the field of storage, in particular to a solid state disk garbage recycling method and a solid state disk.

Background

Solid State Drives (SSD), which are currently popular high performance memories, are made of an array of Solid State electronic Memory chips, and are composed of a control unit and a storage unit, where the storage unit may be a FLASH Memory (FLASH) chip, a Dynamic Random Access Memory (DRAM) chip, or the like. Unlike the conventional mechanical hard disk, due to the granular nature of the solid state disk, new data cannot directly overwrite original data when new data is written. The solid state disk must erase old data before new data can be written. For solid state disk, Garbage Collection (GC) refers to a process of transferring existing data to other flash memory locations and completely deleting some useless data.

In the garbage recovery process of the solid state disk, the balance between the recovery bandwidth of the solid state disk and the host bandwidth of the solid state disk is the basis of stable operation of the system. If the recovery bandwidth is smaller than the host bandwidth, the remaining space is gradually reduced and exhausted, so that no remaining space is available for accommodating newly written data, and the performance and user experience of the solid state disk are seriously affected. If the recovery bandwidth is larger than the host bandwidth, the host bandwidth is degraded due to preemption of Input/Output (IO) resources, so that IO fluctuation of the solid state disk is large, and operations such as writing of a user are affected. Therefore, the best state is that the reclamation bandwidth and the host bandwidth are completely equal, and the space is not exhausted, and the occupied host bandwidth is squeezed back. However, the existing garbage collection method is difficult to balance the host bandwidth and the collection bandwidth, and the user experience is poor.

Disclosure of Invention

The application provides a solid state disk garbage recycling method and a solid state disk, which can achieve the purpose of dynamically adjusting the recycling step length, and therefore dynamically adjusting the garbage recycling rate of an SSD. Finally, the recovery concurrency number is always close to the stable concurrency number. In the process of recovering the SSD garbage, the impact on the I/O of the SSD is reduced,

in a first aspect, a method for recovering garbage of a solid state disk is provided, including: determining the change trend of the residual space of the solid state disk SSD of at least two sampling points in a sampling interval corresponding to the current sampling point, wherein the sampling interval comprises a plurality of sampling points. And determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the change trend of the residual space in the sampling interval. And in a time period between the current sampling point and the next sampling point, performing garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point.

According to the method for recovering the garbage of the solid state disk, a step length for calculating the utilization of the recovery concurrency number (which can also be called as a recovery rate) of a current sampling point is determined according to the residual space variation trend of a plurality of sampling points included in a sampling interval corresponding to the current sampling point. And calculating the recovery rate of the current sampling point according to the determined step length, and performing garbage recovery of the SSD according to the calculated recovery rate. The residual space variation trend of the current sampling point corresponding to the sampling interval is different, and the step length is also different. The purpose of dynamically adjusting the step length can be achieved, and therefore the garbage recycling rate of the SSD can be dynamically adjusted. In the SSD garbage recycling process, the impact of garbage recycling on the I/O of the SSD is reduced, and the performance and the user experience of the SSD are improved.

In a possible implementation manner of the first aspect, when the remaining spatial variation trends all increase or all decrease, a step length corresponding to the remaining spatial variation trend is a first step length; under the condition that the residual space variation trend comprises an increase and a decrease, the step length corresponding to the residual space variation trend is a second step length; wherein the value of the first step is greater than the value of the second step. In the implementation mode, the size relationship between the recovery concurrency number and the stable concurrency number is determined according to the variation trend of the residual space, and the recovery concurrency number is dynamically adjusted according to different step lengths according to the size relationship between the recovery concurrency number and the stable concurrency number. The method can more accurately reflect the size relationship between the recovery concurrency number and the stable concurrency number, and finally enables the recovery concurrency number to be always close to the stable concurrency number. In the process of SSD garbage recovery, the impact on the I/O of the SSD is reduced, and the performance and the user experience of the SSD are improved.

In a possible implementation manner of the first aspect, the determining the remaining space variation trend of the solid state disk SSD of at least two sampling points in the sampling interval corresponding to the current sampling point includes: determining the remaining space change trend bitmap of a sampling interval corresponding to the current sampling point; the determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the remaining space variation trend includes: and determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the residual space change trend bitmap. In the implementation mode, the remaining space variation trend can be more conveniently and simply represented by using the remaining space variation trend bitmap, so that the actual implementation is facilitated, and the resources and the cost are saved. The efficiency of determining different step lengths corresponding to different residual space variation trends is improved, and therefore the efficiency of SSD garbage recycling is improved.

In a possible implementation manner of the first aspect, the determining the remaining space variation trend bitmap of the sampling interval corresponding to the current sampling point includes: determining the residual spatial value N of the SSD for the previous sample point_i-1(ii) a Determining the residual space value N of the SSD corresponding to the current sampling point_i(ii) a In N_i-1Greater than N_iAnd N is_i-1And N_iDeleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is larger than or equal to the value of the residual space reference interval of the SSD, and adding one bit 1 after the last bit to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_i-1And N_iThe value of (b) is positive. In the implementation mode, the remaining space change trend bitmap is updated in real time according to the remaining space value obtained by twice sampling, so that the size relationship between the recovered concurrent number and the stable concurrent number can be reflected more accurately in real time by the remaining space change trend bitmap, and the accuracy and flexibility of dynamically adjusting the step length are improved.

In a possible implementation manner of the first aspect, the determining the remaining space variation trend bitmap of the sampling interval corresponding to the current sampling point includes: determining the residual space value N of the SSD corresponding to the previous sampling point_i-1(ii) a Determining the residual space value N of the SSD corresponding to the current sampling point_i(ii) a In N_i-1Less than N_iAnd N is_iAnd N_i-1Deleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is larger than or equal to the value of the residual space reference interval of the SSD, and adding a bit 0 after the last bit to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_iAnd N_i-1The value of (b) is positive. In the implementation mode, the remaining space change trend bitmap is updated in real time according to the remaining space value obtained by twice sampling, so that the size relationship between the recovered concurrent number and the stable concurrent number can be reflected more accurately in real time by the remaining space change trend bitmap, and the accuracy and flexibility of dynamically adjusting the step length are improved.

In a possible implementation manner of the first aspect, before performing garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point, the method further includes: and determining that the residual space value of the SSD corresponding to the current sampling point is smaller than the residual space reference value of the SSD. In this implementation manner, garbage collection is performed when the remaining space value of the SSD corresponding to the current sampling point is smaller than the remaining space reference value of the SSD. Unnecessary garbage recycling can be avoided. Therefore, the impact of garbage collection on the I/O of the SSD is reduced, and the receiving performance and the user experience of the SSD can be further improved under the condition that the SSD has enough storage resources. And the method is convenient for practical realization, and saves resources and cost.

In a possible implementation manner of the first aspect, determining, according to a step size corresponding to the remaining space variation trend, a garbage collection rate of the SSD corresponding to the current sampling point includes: determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the following formula:

wherein, V_iGarbage recovery rate, V, of the SSD for the current sample point_i-1Garbage recovery rate, N, of the SSD for the previous sampling point_iFor the remaining spatial value of the SSD corresponding to the current sample point, N_i-1And B is the residual space value of the SSD corresponding to the previous sampling point, B is the residual space reference interval of the SSD, and S is the step length corresponding to the residual space variation trend. In this implementation, the current recycle concurrency number is calculated according to the formula described above. The data of the recovery concurrency number can be rapidly obtained, and the recovery concurrency number is enabled to be close to the stable concurrency number rapidly. The garbage recovery efficiency of the SSD is improved. And the recovery concurrency number can be accurately obtained by using formula calculation. The garbage recovery rate of the SSD is dynamically adjusted. And the actual implementation and the subsequent updating and maintenance are facilitated.

In a possible implementation manner of the first aspect, all bits in the remaining spatial variation trend bitmap corresponding to the first sampling point are 1. In the implementation mode, the remaining space variation trend bitmap can reflect the relationship between the recovery concurrency number and the stable concurrency number more accurately. The residual space variation trend bitmap is more accurate, and the adjustment of the recovered concurrent number is closer to the stable concurrent number.

In one possible implementation of the first aspect, the remaining space variation trend bitmap comprises 16 bits. The recovery concurrency number can be calculated more conveniently and rapidly, and the garbage recovery efficiency of the SSD is improved.

In a second aspect, a solid state disk is provided, which includes a storage unit and a processing unit, and is configured to support the solid state disk to perform the functions of the method in the first aspect or any possible implementation manner of the first aspect. The functions may be implemented by hardware, or by hardware executing corresponding software, where the hardware or software includes one or more modules corresponding to the above functions.

In a third aspect, a solid state disk is provided, which includes a memory, a processor, an input/output interface, and a transceiver. The method is used for supporting the solid state disk to execute corresponding functions in the method. The memory, the processor, the input/output interface and the transceiver are connected through communication, the memory stores instructions and data, the transceiver is used for executing specific signal transceiving under the driving of the processor, and the input/output interface is used for receiving input data and information, outputting operation results and the like under the driving of the processor. The processor is configured to invoke the instruction to implement the method for garbage collection of the solid state disk in the first aspect and various implementation manners thereof.

In a fourth aspect, there is provided a computer program product comprising: computer program code which, when run on a computer, causes the computer to perform the method of the above-mentioned aspects.

In a fifth aspect, a computer-readable medium is provided, which stores program code, which, when run on a computer, causes the computer to perform the method of the above-mentioned aspects.

A sixth aspect provides a system on a chip comprising a processor for a terminal to perform the functions referred to in the above aspects, e.g. to generate, receive, transmit, or process data and/or information referred to in the above methods. In one possible design, the system-on-chip further includes a memory for storing program instructions and data necessary for the terminal. The chip system may be formed by a chip, or may include a chip and other discrete devices.

Drawings

FIG. 1 is a graph showing the relationship between the recovery concurrency number of a current sampling point and the difference between a reference value and a residual space

Fig. 2 is a schematic flow chart of a method for garbage collection of a solid state disk according to an embodiment of the present application.

Fig. 3 is a schematic flow chart of a method for garbage collection of a solid state disk according to another embodiment of the present application.

FIG. 4 is a graph of the recovered concurrency number of the current sample point versus the difference between the baseline value and the residual space, according to one embodiment of the present application.

FIG. 5 is a graph of the relationship between current reclaim concurrency number and time for one embodiment of the present application.

Fig. 6 is a schematic block diagram of a solid state disk according to an embodiment of the present application.

Fig. 7 is a schematic block diagram of a solid state disk according to another embodiment of the present application.

Detailed Description

The technical solution in the present application will be described below with reference to the accompanying drawings.

The following key terms are referred to in the embodiments of the present application.

Host bandwidth: the amount of data actually written to the SSD at each instant in time. For example, it may be the amount of data written to the SSD per second.

And (3) recovering the bandwidth: the actual amount of data or space value reclaimed by an SSD at an instant in time may be, for example, the amount of garbage reclaimed per second.

Reference value: the reference value of the SSD residual space is expressed in percentage of the total storage space of the SSD. When the remaining space of the SSD is smaller than the reference value, garbage collection is started.

Reference interval: a minimum unit of a difference value of the remaining space of the SSD and the reference value of the SSD. The size of the reference interval is expressed in% of the total storage space of the SSD.

And (3) concurrent counting: the unit of the recovery amount of the SSD in each garbage recovery is the number of the block groups to be recovered, i.e. the number of the block groups to be recovered in each garbage recovery, which is also referred to as the recovery concurrency number.

Step length: the number of recovery concurrencies for each reference interval.

Stable concurrency number: the number of reclamation concurrency required when balancing with host bandwidth.

For the SSD, due to the granular nature of the SSD, when new data is written, the new data cannot directly overwrite the original data, and the SSD must first erase the old data before the new data can be written. For SSDs, garbage collection refers to the process of transferring existing data back to other flash locations and completely deleting some unused data.

The flash memory in an SSD may be divided into a number of blocks (blocks), each of which may in turn be divided into a number of pages (pages). Data can be written directly in units of pages, but block units are required to delete data. Therefore, to delete useless data, the SSD first needs to copy and paste useful data included in one block into a page in a completely new block, so that the useless data included in the original block can be deleted in units of blocks. After deletion, new data can be written. Therefore, when deleting data on a page, data on other pages in a block where the page is located needs to be copied to pages in another block, and then the data in the block needs to be erased.

In the process of garbage recovery of the SSD, the balance between the recovery bandwidth and the host bandwidth is the basis for stable operation of the SSD system. If the recovery bandwidth of the SSD is smaller than the host bandwidth of the SSD, the remaining space of the SSD will gradually decrease and be exhausted, resulting in no remaining space to accommodate the newly written data, which seriously affects the performance and user experience of the SSD. If the recovery bandwidth is larger than the host bandwidth, the host bandwidth is degraded due to preemption of the I/O resources of the SSD, so that the I/O fluctuation of the SSD is large, and the writing operation of a user is influenced. Therefore, the best state is that the reclamation bandwidth and the host bandwidth are completely equal, and the space is not exhausted, and the host bandwidth occupying the SSD is squeezed back.

The existing algorithm for recovering the garbage concurrency number (recovery bandwidth) generally designates a value of a residual space of an SSD as a reference value (unit is percentage) of the SSD, specifies a step size (stepcount) and a reference interval (basegap), and then calculates how many reference intervals the residual space of the current sampling time point is different from the reference value, and the step size is multiplied to obtain the current concurrency number. The formula is shown in formula (1):

in the formula (1), V represents the recovery concurrency number corresponding to the current sampling point, that is, in the time period from the current sampling point to the next sampling point, the calculated recovery concurrency number of the current sampling point is used for performing the garbage recovery of the SSD. D represents a reference value of the remaining space of the SSD, that is, the garbage collection of the SSD is started only when the remaining space of the SDD is smaller than the reference value. N represents a remaining space corresponding to the current sampling point, that is, a value of the remaining space acquired at the time of the current sampling. B represents a reference interval. The recovery concurrency number corresponding to the current sampling point is updated only if the difference between the reference value D and the remaining space N at the current sampling time point is greater than or equal to one reference interval B. S denotes a step size.

For example, assume that the value of B is 0.2%, i.e., the reference interval is 0.2% of the entire storage space of the SSD. The value of S is 16 and the value of D is 4%, i.e. the reference value is 0.2% of the total storage space of the SSD. Samples were taken every 5 seconds.

After the first sampling, it is assumed that the value of the remaining space is 4.2%, that is, 4.2% of the entire storage space of the remaining space value SSD is greater than the reference value 4%, and therefore, garbage collection is not performed.

After the second sampling, assuming that the value of the residual space is 3.8% and is less than the reference value 4%, the recovery concurrency number of the second recovery sampling is 16 calculated according to the above formula (1). Namely, in the period after the second sampling is completed and before the third sampling is started, the garbage is recycled by using the recycling rate with the recycling concurrence number of 16.

After the third sampling, assuming that the value of the remaining space is 3.2% and less than the reference value of 4%, it proves that the speed of writing new data is greater than the speed of recovering garbage in the period between the second sampling and the third sampling, and therefore, the value of the remaining space is reduced. According to the above formula (1), the recovery concurrency number of the third recovery sample is calculated to be 64. Namely, in the period after the third sampling is completed and before the fourth sampling is started, the garbage collection is carried out by using the recovery rate of the recovery concurrency number of 64.

After the fourth sampling, assuming that the value of the remaining space is 3.9% and less than the reference value of 4%, it is proved that the speed of writing new data is less than the speed of recovering garbage in the period between the third sampling and the fourth sampling, and thus, the value of the remaining space is increased. Since the difference between the reference value and the remaining space is smaller than the value of one reference interval, i.e., smaller than the minimum unit of the difference between the reference value and the remaining space. In this case, since the difference between the reference value and the remaining space is smaller than the value of one reference interval, the recovery concurrency number corresponding to the fourth sampling maintains the recovery concurrency number calculated at the time of the third sampling, that is, is 64. I.e. no update of the recycle concurrency is performed. In other words, in the period from the third sampling to the fifth sampling, the recovery rate of the recovery concurrency number 64 is used for recovering the garbage of the SSD. I.e. the recovery concurrency, i.e. the rate of garbage recovery, is updated only if the difference between D and N is greater than or equal to a value of B.

As can be seen from equation (1), since the values of the step size S and the reference interval B are fixed, the difference between the reference value D and the remaining space N at the current sampling time point is an integer number of reference intervals. That is, the relationship between the recovery concurrency number corresponding to the current sampling point and the step length S can be represented by formula (2):

V＝K·S (2)

k in equation (2) represents the number of reference intervals included in the difference between the reference value D and the remaining space N at the current sampling time point. The value of K is a positive integer. That is, as shown in fig. 1, the relationship between the recovery concurrency number of the current sampling point (current recovery concurrency number) and the difference between the reference value and the remaining space of the current sampling time point is a linear function.

As can be seen from formula (1), formula (2) and fig. 1. The current recovery concurrency number is integral multiple of the step length. That is, the current number of recovered concurrency is adjusted by at least one step size based on the last number of recovered concurrency. If the step length is set to be too large, the change between the current recovery concurrent number and the last recovery concurrent number is too large, and the influence on the I/O of the SSD is large, namely the fluctuation of the host I/O curve of the SSD is large, so that the performance of the SSD is influenced. The situation that the recovery bandwidth is larger than the host bandwidth is caused, the I/O resources of the SSD are preempted, the host bandwidth of the SSD is degraded, and the I/O fluctuation of the SSD is large. For example, if the step size is set to 100, the current recovery concurrency number will be changed by 100 at least based on the last recovery concurrency number. Causing the host I/O curve of the SSD to fluctuate widely. Affecting the performance and user experience of the SSD. If the step length is set to be too small, the difference between the current residual space and the reference value is a plurality of reference intervals to reach a stable concurrency value, the recovery concurrency number cannot reach the stable concurrency number in some scenes even if the residual space is 0, the recovery concurrency number is increased all the time in the time period, the I/O curve of the SSD gradually goes low, no residual space contains newly written data, and the performance and the user experience of the SSD are seriously influenced.

For example, assuming that the stable concurrency number (the write rate of SSD data) is 800, i.e., the recovery concurrency number (the rate of garbage recovery) is 800, which is just equal to the stable concurrency number, the performance of the SSD is optimal. Assuming that the step size is set to 10, according to the above formula (1), assuming that the remaining space at the time of current sampling is 0, the value of B is 0.2%, and the value of D is 4%, the current recovery concurrency number is calculated to be 200. That is, when garbage collection is performed at a rate of 200 recovery concurrency numbers, since the stable concurrency number is 800, that is, the rate of writing data is 800, and the recovery concurrency number has a value of 200, it means that the speed of writing data is much higher than the recovery garbage stable rate. Resulting in a gradual reduction in the remaining space, and eventually the remaining space of the SSD will be exhausted, resulting in no remaining space to accommodate the newly written data. Severely impacting the performance and user experience of the SSD.

Based on the above problem, the application provides a method for recovering garbage of a solid state disk, which can increase the step length when the difference between the current concurrency number and the stable concurrency number is large, that is, the recovered concurrency number is close to the stable concurrency value at a fast speed. When the current concurrency number is close to the stable concurrency number, the step length can be made smaller, the step length is closed to the stable concurrency value at a slower speed, and the impact on the I/O of the SSD can be reduced.

The method for garbage collection of a solid state disk provided by the present application, which can be executed by an SSD, is described in detail below with reference to fig. 2. The method for recovering garbage of a solid state disk provided in the embodiment of the present application may be applied to various scenarios requiring dynamic adjustment of concurrency number, for example, cache (cache) disk-flushing concurrency number control adjustment, Quality of Service (QOS) flow control adjustment, and the like, and the embodiment of the present application is not limited herein.

Fig. 2 is a schematic flow chart of a method 200 for garbage collection of a solid state disk according to an embodiment of the present application, where as shown in fig. 2, the method 100 includes:

s110, determining the change trend of the residual space of the solid state disk SSD of at least two sampling points in a sampling interval corresponding to the current sampling point, wherein the sampling interval comprises a plurality of sampling points.

And S120, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the change trend of the residual space in the sampling interval.

S130, in the time period between the current sampling point and the next sampling point, the garbage of the SSD is recycled according to the garbage recycling rate of the SSD corresponding to the current sampling point.

According to the method for recovering the garbage of the solid state disk, provided by the embodiment of the application, the step length for calculating the utilization of the recovery concurrency number (which can also be called as the recovery rate) of the current sampling point is determined according to the residual space variation trend of a plurality of sampling points included in the sampling interval corresponding to the current sampling point. And calculating the recovery rate of the current sampling point according to the determined step length, and performing garbage recovery of the SSD according to the calculated recovery rate. The residual space variation trend of the current sampling point corresponding to the sampling interval is different, and the step length is also different. The purpose of dynamically adjusting the step length can be achieved, and therefore the garbage recycling rate of the SSD can be dynamically adjusted. Finally, the recovery concurrency number is always close to the stable concurrency number. In the process of SSD garbage recovery, the impact on the I/O of the SSD is reduced, and the performance and the user experience of the SSD are improved.

Specifically, in S110, when garbage collection of the SSD is required, that is, when the remaining space condition of the SSD is sampled once, if the remaining space of the SSD is smaller than the remaining space reference value of the SSD, it is necessary to determine a remaining space variation trend of the sampling interval corresponding to the sampling point. The remaining space value is used to characterize how much space the SSD remains. And during each sampling, a residual space value can be obtained, and the residual space values of two adjacent or nonadjacent sampling points are compared to obtain the residual space variation trend of the two samplings. For example, as shown in table 1, table 1 is a remaining spatial variation trend table of SSD in sampling intervals corresponding to different sampling points.

TABLE 1 residual spatial variation trends of SSD for sampling intervals corresponding to different sampling points

In table 1, it is assumed that each sampling interval includes 4 sampling points, and the sampling is performed every 1 second (second, S), that is, the time length of each sampling interval is 4S. Assume that the current sampling point is the 4 th sampling point, i.e. the current sampling point corresponds to the time period between the time T +1 and the time T +4 of the sampling interval. And, the current sampling point corresponds to the last sampling point in the sampling interval. Of the 4 sampling points, the 2 nd sampling point is in a decreasing trend compared to the remaining space of the 1 st sampling point. The 3 rd sample point is decreasing compared to the remaining space of the 2 nd sample point. The 4 th sample point is also trending less than the remaining space of the 3 rd sample point. The fact that the trend of the change of the residual space in the whole sampling interval is reduced means that the recovery concurrency number is smaller than the stable concurrency number in the period from the 1 st sampling point to the 4 th sampling point, namely garbage recovery of the SSD is slow, and writing of the SSD is fast. I.e. the waste recovery with the larger first step length is needed to speed up the recovery rate. If the trend of the residual space is increased in the whole sampling interval, the recovery concurrency number is larger than the stable concurrency number in the period from the 1 st sampling point to the 4 th sampling point, namely the garbage recovery of the SSD is relatively large, and the writing of the SSD is relatively slow. I.e. the garbage recovery rate needs to be rapidly reduced to be near the stable concurrency number by using a larger first step length. And similarly. Assume that the current sampling point is the 5 th sampling point, i.e. the current sampling point corresponds to the sampling point in the period from the time T +2 to the time T + 5. That is, the sampling points included in the sampling interval corresponding to the 5 th sampling point are: sample 2 to sample 5.

For another example, assume that the current sampling point is the 8 th sampling point, i.e., the current sampling point corresponds to the sampling interval from time T +5 to time T + 8. The sampling interval includes 5 th to 8 th sampling points. The 6 th sample point is a decreasing trend compared to the remaining space of the 5 th sample point. The 7 th sample point is on an increasing trend compared to the remaining space of the 6 th sample point. The 8 th sample point is also trending less than the remaining space of the 7 th sample point. The residual space has more and less trend in change in the whole sampling interval. Meaning that the recovery concurrency number is around the stable concurrency number in the period from the 5 th sampling point to the 8 th sampling point. For example, the garbage collection rate in the time period between the 7 th sampling point and the 6 th sampling point is greater than the stable concurrency number. The garbage recovery rate in the time period between the 6 th sampling point and the 5 th sampling point is less than the stable concurrency number. In this case, since the recovery concurrency number (garbage recovery rate) is around the stable concurrency number. Therefore, waste recycling is required with a smaller second step size. So that the slow recovery concurrence number and the slow recovery ultra-stable concurrence number are close.

It should be understood. Table 1 shows the residual spatial variation trend of two adjacent sampling points in the sampling interval. In this embodiment of the present application, the remaining spatial variation trend in the sampling interval may also be two sampling points that are not adjacent to each other, for example, the remaining spatial variation trend of the 4 th sampling point corresponding to the sampling interval may also be: the trend of the 1 st sampling point compared with the remaining space of the 3 rd sampling point, and the trend of the 3 rd sampling point compared with the remaining space of the 4 th sampling point. The embodiments of the present application are not limited thereto.

It should also be understood that table 1 is merely exemplary. In the embodiment of the present application, more sampling points may be included in the sampling interval. The sampling period may also be other periods. The embodiments of the present application are not limited thereto.

In S120, the step size corresponding to the remaining spatial variation trend of the sampling interval is, for example, as shown in table 1. And calculating the garbage recovery rate of the SSD corresponding to the current sampling point by the first step length corresponding to the residual space variation trend of the sampling interval corresponding to the 4 th sampling point or the second step length corresponding to the residual space variation trend of the sampling interval corresponding to the 8 th sampling point. Wherein the first step size is greater than the value of the second step size.

In S130, in a time period between the current sampling point and the next sampling point, garbage collection of the SSD is performed according to the garbage collection rate of the SSD corresponding to the current sampling point. For example, as shown in table 1. And if the current sampling point is the 4 th sampling point, garbage recovery is carried out in the period from T +4 to T +5 according to the garbage recovery rate (recovery concurrency number) calculated at the fourth sampling point.

Optionally, as an embodiment, when the remaining space variation trends are both increased or both decreased, the step length corresponding to the remaining space variation trend is a first step length;

under the condition that the residual space variation trend comprises an increase and a decrease, the step length corresponding to the residual space variation trend is a second step length; wherein the value of the first step is greater than the value of the second step.

Specifically, in step S120, when the remaining spatial variation trends of the sampling interval are all increasing or all decreasing, the garbage collection rate of the SSD corresponding to the current sampling point is determined according to the first step size, or

Under the condition that the change trend of the residual space in the sampling interval comprises increase and decrease, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the second step length;

wherein the value of the first step is greater than the value of the second step.

In the garbage collection of the SSD, the balance between the recovery concurrency number and the stable concurrency number is a final target, and since the stable concurrency number is related to the host bandwidth, that is, the stable concurrency number is the recovery concurrency number corresponding to the host bandwidth, the stable concurrency number is difficult to obtain. Therefore, the embodiment of the present application indirectly reflects the magnitude relationship between the recovery concurrency number and the stable concurrency number by using the variation trend of the remaining space in a period of time (sampling interval). For example, the values of the residual space of the last sampling point and the residual space of the current (current) sampling point are reduced compared, and it is proved that the recovery concurrency number is smaller than the stable concurrency number in the period between the last sampling point and the current sampling point, that is, the garbage recovery of the SSD is slow, and the write-in rate of the SSD is fast. The value of the residual space of the last sampling point is increased compared with that of the residual space of the current sampling point, and the fact that the recovery concurrency number is larger than the stable concurrency number in the period between the last sampling point and the current sampling point is proved, namely the garbage recovery of the SSD is relatively block, and the writing of the SSD is relatively slow. The size relation between the recovery concurrency number and the stable concurrency number in a sampling interval is determined by analyzing the residual spatial variation trend of a plurality of sampling points in the sampling interval. The size relationship between the recovery concurrency number and the stable concurrency number can be more accurately reflected. For example, if the trend of the change of the remaining space in the sampling interval corresponding to the current sampling point is all increased or all decreased, it is proved that the difference between the recovery concurrency number (i.e., the garbage recovery speed corresponding to the previous sampling point) corresponding to the previous sampling point and the stable concurrency number (the rate of writing data into the SSD) is large, and the recovery concurrency number corresponding to the previous sampling point needs to be adjusted to a large extent to obtain the current recovery concurrency number, so that the current recovery concurrency number is fast close to the stable concurrency number. Namely, the garbage recovery rate of the SSD corresponding to the current sampling point is determined according to the larger first step length. And performing subsequent garbage recovery according to the calculated garbage recovery rate.

If the residual space variation trend of the current sampling point corresponding to the sampling interval includes increase or decrease, the difference between the current recovery concurrency number and the stable concurrency number is proved to be smaller, and the current recovery concurrency number is close to the stable concurrency number and needs to be adjusted in a smaller range. Namely, the garbage recovery rate of the SSD corresponding to the current sampling point is determined according to the smaller second step size. And performing subsequent garbage recovery according to the calculated garbage recovery rate. And according to the size relation between the recovery concurrency number and the stable concurrency number, dynamically adjusting the recovery concurrency number according to different step lengths. The method can more accurately reflect the size relationship between the recovery concurrency number and the stable concurrency number, and finally enables the recovery concurrency number to be always close to the stable concurrency number. In the process of SSD garbage recovery, the impact on the I/O of the SSD is reduced, and the performance and the user experience of the SSD are improved.

It should be understood that, in the embodiment of the present application, the step size corresponding to the remaining spatial variation trend may also be determined according to the number of increasing trends or decreasing trends included in the remaining spatial variation trend of the sampling interval. For example, as shown in table 1, assuming that the remaining spatial variation trend of the sampling interval corresponding to the 8 th sampling point includes 1 growth trend, determining the garbage collection rate of the SSD corresponding to the current sampling point according to the first step length; if the change trend of the residual space comprises 2 growth trends, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the second step length; and if the change trend of the residual space comprises 3 growth trends, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the third step length. The first step size is greater than the second step size, and the second step size is greater than the third step size. The embodiments of the present application are not limited thereto.

It should also be understood that in the case where the remaining space is the same at the time of two samplings, for example, in the case where the remaining space value of the 4 th sampling point is the same as the remaining space value of the 3 rd sampling point, it is proved that the garbage collection rate corresponding to the 3 rd sampling point is the same as the writing speed between the 3 rd sampling point and the 4 th sampling point. In this case, the garbage collection rate corresponding to the 3 rd sampling point can be directly set as the garbage collection rate corresponding to the 4 th sampling point. Namely, the garbage recycling rate corresponding to the 4 th sampling point is determined without calculating or according to the change trend of the residual space. The embodiments of the present application are not limited thereto.

Optionally, as an embodiment. The residual space variation trend is represented by a residual space variation trend bitmap, each bit in the residual space variation trend bitmap is used for indicating the variation trend of the residual space of two sampling points in the sampling interval,

as shown in fig. 3, in S110, determining a remaining spatial variation trend of the solid state disk SSD at least two sampling points in a sampling interval corresponding to the current sampling point includes:

determining the remaining space change trend bitmap of a sampling interval corresponding to the current sampling point;

in S120, determining a garbage collection rate of the SSD corresponding to the current sampling point according to the step size corresponding to the remaining space variation trend, includes:

and determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the residual space change trend bitmap.

Specifically, the remaining space variation tendency is represented by a remaining space variation tendency bitmap. Each bit in the remaining space variation trend bitmap is used to indicate a variation trend of the remaining space of the SSD when two sampling points (which may be two adjacent sampling points in the sampling interval, or two non-adjacent sampling points in the sampling interval) are sampled in the sampling interval. The change trend of the residual space can be more conveniently and simply expressed, the actual realization is convenient, and the resources are saved. For example, the remaining space trend bitmap may be 11101, and the value of the remaining space of the last sampling point and the value of the remaining space of the present (current) sampling point are reduced by 1 in the bitmap. A 0 in the bitmap indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point. Alternatively, a 1 indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point. A 0 in the bitmap indicates that the value of the residual space of the last sample point and the residual space of the present (current) sample point is reduced compared to the value of the residual space of the last sample point.

For example, when garbage collection of the SSD is required, that is, when the remaining space condition of the SSD is sampled at a certain time, and the remaining space of the SSD is smaller than the remaining space reference value of the SSD, it is necessary to determine the remaining space variation trend bitmap corresponding to the sampling interval at the time of sampling. Each bit in the remaining space variation trend bitmap is used for indicating the variation trend of the remaining space of the SSD when the sampling points are sampled twice. For example, the remaining spatial variation trend bitmap corresponding to the sampling interval may be 11101, that is, the sampling interval includes at least 5 sampling points. The value of 1 in the bitmap indicates that the residual space of the last sample point is reduced compared to the value of the residual space of the present (current) sample point. A 0 in the bitmap indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point. Alternatively, a 1 indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point. A 0 in the bitmap indicates that the value of the residual space of the last sample point and the residual space of the present (current) sample point is reduced compared to the value of the residual space of the last sample point.

The application provides a remaining space variation trend bitmap. The remaining space variation trend bitmap can effectively represent the size relationship between the current recycling concurrency number and the stable concurrency number. For example, a 1 in the residual space variation tendency bitmap indicates that the value of the residual space of the last sampling point and the value of the residual space of the present (current) sampling point within the sampling interval are reduced. 0 in the residual space variation trend bitmap indicates that the value of the residual space of the last sampling point and the value of the residual space of the current sampling point in the sampling interval are increased compared with each other. If all the bit positions in the remaining spatial variation trend bitmap of the sampling interval corresponding to the current sampling point are 1 or 0, it is proved that the difference between the current recovery concurrency number and the stable concurrency number is large, and the current recovery concurrency number needs to be adjusted to a large extent. If the bit position in the residual space variation trend bitmap of the sampling interval corresponding to the current sampling point is a mixture of 1 and 0, the difference between the current recovery concurrency number and the stable concurrency number is proved to be smaller, and the current recovery concurrency number is close to the stable concurrency number, so that the current recovery concurrency number needs to be adjusted in a smaller range. The change trend of the residual space can be more conveniently and simply represented by using the bitmap of the change trend of the residual space, so that the actual realization is facilitated, the efficiency of determining different step lengths corresponding to different change trends of the residual space is improved, and the recovery efficiency of the SSD garbage is improved.

The following description will be given by taking the remaining space variation trend bitmap as 4 bits by way of example.

As shown in table 2, assuming that the initial remaining spatial variation trend bitmap is 1111, sampling is performed every 1 second, i.e. each sampling interval includes 4 sampling points. The remaining space trend bitmap of all sampling points corresponding to the remaining space greater than or equal to the remaining space reference value is 1111, that is, under the condition that the remaining space of the sampling points is greater than or equal to the remaining space reference value, because the sampling process exists periodically, that is, no matter how many times of sampling is performed, the remaining space trend bitmap does not need to be updated, and the remaining space trend bitmap corresponding to the sampling process is 1111. Assuming that the reference value is 4%, 1 in the bitmap indicates that the value of the residual space of the last sample point is reduced compared to the value of the residual space of the present (current) sample point. A 0 in the bitmap indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point. The value of the first step size in table 1 is greater than the value of the second step size, for example, the value of the first step size is 100 concurrency numbers, and the second step size is 20 concurrency numbers. It should be understood that the initial remaining space variation trend bitmap may also be 0000.

TABLE 2 residual spatial variation trend bitmap corresponding to different sampling points

It should be understood that table 2 is only one example of a residual spatial variation trend bitmap for different sample points. No restrictions should be imposed on the remaining space variation tendency bitmap or the like. For example, the remaining spatial variation trend bitmap may also be 8 bits or 10 bits, that is, one sampling interval includes 8 or 10 sampling points. The corresponding relationship between the remaining space variation trend bitmap and the step size may also be other corresponding relationships, for example, the corresponding step size is determined according to the number of 0 or 1 included in the remaining space variation trend bitmap. When all the bits of the remaining spatial variation trend bitmap are 0, the corresponding step size may be the first step size, or the like. It should be understood. The remaining space variation trend bitmap may also be updated in the case where the remaining space of the sampling point is greater than or equal to the remaining space reference value. The embodiments of the present application are not limited thereto.

And under the condition that the residual space value of the SSD corresponding to the current sampling point is smaller than the residual space reference value of the SSD, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the residual space change trend bitmap. For example, the current sampling point is the 4 th sampling point shown in table 2, and the remaining space value of the SSD corresponding to the 4 th sampling point is 3.7% and is less than the reference value 4.0%. Therefore, garbage collection of the SSD is required. And determining a corresponding step length of the 4 th sampling point, namely a first step length, according to the residual space change trend bitmap corresponding to the 4 th sampling point, namely 1111, and calculating the garbage recovery rate corresponding to the 4 th sampling point according to the first step length. I.e. recovering the concurrency number. It should be understood that, when the remaining space value of the SSD corresponding to the current sampling point is greater than or equal to the remaining space reference value of the SSD, it proves that the remaining space is relatively abundant, and garbage collection is not required.

It should be understood that, when the remaining space value of the SSD corresponding to the current sampling point is greater than or equal to the remaining space reference value of the SSD, the garbage collection rate of the SSD corresponding to the current sampling point may also be determined according to the step size corresponding to the remaining space change trend bitmap, and the garbage collection is performed, that is, the garbage collection is not limited to the case that the remaining space value is less than the remaining space reference value.

And in a time period between the current sampling point and the next sampling point, performing garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point. For example, the current sampling point is the 4 th sampling point shown in table 2, and according to the calculated garbage collection rate corresponding to the 4 th sampling point, the garbage collection rate is used for performing garbage collection of the SSD in the period from T +4 to T + 5.

According to the method for recovering the garbage of the solid state disk, the size relation between the recovered concurrent number and the stable concurrent number is indirectly reflected through the change trend bitmap of the remaining space, and the recovered concurrent number can be dynamically adjusted according to the change trend bitmap of different remaining spaces. The method comprises the steps of determining and calculating the recycling concurrent number utilization step length of a current sampling point by using a residual space variation trend bitmap of the current sampling point corresponding to a sampling interval, calculating the recycling rate of the current sampling point according to the step length, and recycling the garbage of the SSD according to the calculated recycling rate. The residual space variation trend bitmaps of the current sampling point corresponding to the sampling interval are different, and the step length is also different. The method can realize the purpose of dynamically adjusting the step length, so that the recovery concurrent number is rapidly close to the stable concurrent number, and the problem that the recovery concurrent number is increased due to overlarge step length setting and the I/O fluctuation of the SSD is large under the condition that the difference between the recovery concurrent number and the stable concurrent number is not large can be avoided. Under the condition that the difference between the recovery concurrency number and the stable concurrency number is large, the SSD has no residual space for accommodating newly written data due to the over-small step length setting, the impact on the I/O of the SSD is reduced in the process of SSD garbage recovery, and the performance and the user experience of the SSD are improved. And the change trend bitmap of the residual space can more conveniently and simply show the change trend of the residual space, thereby facilitating the actual realization and saving resources.

It should be understood that, instead of using the remaining space trend bitmap of the remaining space to represent the remaining space trend of the sampling interval corresponding to the current sampling point, other ways can be used, for example, as shown in table 2, the remaining space trend of the 8 th sampling point can be represented by 81 to represent an increasing trend compared with the remaining space of the 7 th sampling point, and the decreasing trend can be represented by 80. Similarly, the residual spatial trend of the 4 th sampling point can be represented by 41 as an increasing trend and 40 as a decreasing trend compared with the residual spatial trend of the 3 rd sampling point. The embodiments of the present application are not limited thereto.

Optionally, as an embodiment, in S110, determining a remaining spatial variation trend bitmap of a sampling interval corresponding to the current sampling point includes:

determining the residual space value N of the SSD corresponding to the previous sampling point_i-1。

Determining the residual space value N of the SSD corresponding to the current sampling point_i。

In N_i-1Greater than N_i、N_iLess than the SSD's remaining space reference value, and N_i-1And N_iDeleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is larger than or equal to the value of the residual space reference interval of the SSD, and adding one bit 1 after the last bit to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_i-1And N_iThe value of (b) is positive.

Specifically, for example, as shown in table 2, it is assumed that the initial residual spatial variation trend bitmap is 1111, the previous sample point is the 3 rd sample point, and the current sample point is the 4 th sample point. The residual space of the 3 rd sampling point is 3.8%, and the residual space of the 4 th sampling point is 3.7%, i.e., i is 4, N_i-1＝3.8％，N_i＝3.7％，N_i-1Is greater than N_iA remaining space reference value of 4%,the reference interval was 0.1%, N_iIs less than the reference value, and N_i-1And N_iIs greater than the reference interval. Therefore, the first bit in the remaining space variation trend bitmap of the sampling interval corresponding to the 3 rd sampling point is deleted, which becomes 111 after deletion, and a bit 1 is added after the last bit, which becomes 1111, that is, the remaining space variation trend bitmap corresponding to the 4 th sampling point becomes 1111.

It is to be understood that in N_iGreater than or equal to the SSD's remaining space reference value, and/or, N_iAnd N_i-1If the difference value of (a) is smaller than the value of the remaining space reference interval of the SSD, the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point may be determined or updated according to the above method. The embodiments of the present application are not limited thereto.

It should also be understood that assume N_i-1And N_iIs less than the value of the remaining spatial reference interval of the SSD, e.g., N_i-1Equal to the value of Ni, the difference between the remaining space at the previous sampling and the remaining space at the current sampling is less than the minimum unit of the difference. In this case, it means that the garbage collection rate from the previous sampling point to the current sampling point is not much different from the rate of writing data into the SSD in this period, i.e. the recovery concurrency number and the stable concurrency number are substantially balanced. The remaining space change trend bitmap corresponding to the current sampling point is also the remaining space change trend bitmap corresponding to the previous sampling point, that is, the remaining space change trend bitmap may not be updated during the current sampling. Meaning that the step size used to calculate the recovered concurrency number is the same for the previous and current samples. The garbage collection rate (the number of concurrent collections recovered) corresponding to the previous sampling point can be set as the garbage collection rate corresponding to the current sampling point. The embodiments of the present application are not limited thereto.

It should also be understood that assuming the initial remaining space variation trend bitmap is 0000, then the scheme may also be transformed to:

Determine the current sampling point corresponding toResidual space value N of SSD_i。

In N_i-1Greater than N_i、N_iLess than the SSD's remaining space reference value, and N_i-1And N_iDeleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is larger than or equal to the value of the residual space reference interval of the SSD, and adding a bit 0 after the last bit to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_i-1And N_iThe value of (b) is positive. The embodiments of the present application are not limited thereto.

According to the method for recycling the garbage of the solid state disk, the residual space change trend bitmap is updated in real time according to the residual space value obtained in twice sampling, the size relation between the recycled concurrent number and the stable concurrent number can be reflected more accurately in real time by the residual space change trend bitmap, and the accuracy and the flexibility of dynamically adjusting the step length are improved. The difference between the recovery concurrency number and the stable concurrency number is reduced, and the garbage recovery performance and the user experience of the SSD are improved.

Optionally, as an embodiment, in S110, the determining a remaining spatial variation trend bitmap of the sampling interval corresponding to the current sampling point includes:

In N_i-1Less than N_i、N_iLess than the SSD's remaining space reference value, and N_iAnd N_i-1And deleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point and adding a bit 0 after the last bit under the condition that the difference value of the sampling interval is greater than or equal to the value of the residual space reference interval of the SSD, so as to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point. Wherein the value of i is a positive integer greater than or equal to 2Number, N_iAnd N_i-1The value of (b) is positive.

Specifically, for example, as shown in table 2, it is assumed that the initial residual spatial variation trend bitmap is 1111, the previous sample point is the 4 th sample point, and the current sample point is the 5 th sample point. The residual space at the 4 th sample point is 3.7%, and the residual space at the 5 th sample point is 3.8%, i.e., i is 5, N_i-1＝3.8％，N_i＝3.7％，N_i-1Is less than N_iA residual space reference value of 4%, a reference interval of 0.1%, N_iIs less than the reference value, and N_iAnd N_i-1Is equal to the reference interval. Therefore, the first bit in the remaining space variation trend bitmap corresponding to the 4 th sampling point is deleted, which becomes 111 after deletion, and a bit of 0 is added after the last bit, which becomes 1110, that is, the remaining space variation trend bitmap corresponding to the 5 th sampling point is 1110.

According to the method for recycling the garbage of the solid state disk, the residual space change trend bitmap is updated in real time according to the residual space value obtained in twice sampling, the size relation between the recycled concurrent number and the stable concurrent number can be reflected more accurately in real time by the residual space change trend bitmap, and the accuracy and flexibility of dynamically adjusting the step length are improved. The difference between the recovery concurrency number and the stable concurrency number is reduced, and the garbage recovery performance and the user experience of the SSD are improved.

It is to be understood that in N_iGreater than or equal to the SSD's remaining space reference value, and/or, N_iAnd N_i-1The remaining space variation trend bitmap of the sampling interval corresponding to the current sampling point may also be determined according to the above method under the condition that the difference value of (a) is smaller than the value of the remaining space reference interval of the SSD. The embodiments of the present application are not limited thereto.

Determining current sample point correspondencesOf the SSD_i。

In N_i-1Less than N_i、N_iLess than the SSD's remaining space reference value, and N_iAnd N_i-1And under the condition that the difference value of the sampling interval is greater than or equal to the value of the residual space reference interval of the SSD, deleting the first bit in the residual space change trend bitmap of the sampling interval corresponding to the previous sampling point, and adding one bit 1 after the last bit to obtain the residual space change trend bitmap of the sampling interval corresponding to the current sampling point. Wherein, the value of i is a positive integer greater than or equal to 2, and N_iAnd N_i-1The value of (b) is positive. The embodiments of the present application are not limited thereto.

Optionally, as an embodiment, before step S130, the method 100 may further include:

and determining that the residual space value of the SSD corresponding to the current sampling point is smaller than the residual space reference value of the SSD.

Accordingly, when the remaining space variation tendency is represented by the remaining space variation tendency bitmap, step S120 may include:

under the condition that all bits in the remaining space variation trend bitmap are 1 or 0, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the first step length, or

And under the condition that the residual space value of the SSD corresponding to the current sampling point is smaller than the residual space reference value of the SSD and the bit in the residual space change trend bitmap is a mixture of 1 and 0, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the second step length. The value of the first step length is greater than that of the second step length, and the first step length and the second step length are concurrency numbers corresponding to the residual space reference interval.

Specifically, in general, garbage collection of an SSD is performed only when the remaining space of the SSD is smaller than the remaining space reference value of the SSD. It should be understood that the method for SSD garbage collection provided in the embodiment of the present application may be used for garbage collection performed when the remaining space of the SSD is smaller than the remaining space reference value of the SSD, or may be used for garbage collection performed when the remaining space of the SSD is greater than or equal to the remaining space reference value of the SSD. The embodiments of the present application are not limited thereto.

When the remaining space variation trend is represented by the remaining space variation trend bitmap, for example, in combination with the example shown in table 2, the current sampling point is the third sampling point, the corresponding remaining space value is 3.8% and is less than the reference value 4%, the remaining space variation trend bitmap of the sampling interval corresponding to the third sampling point is 1111, that is, all bits in the bitmap are 1, and therefore, the garbage collection rate corresponding to the third sampling point is calculated according to the first step size corresponding to the remaining space variation trend bitmap.

Or, in combination with the example shown in table 1, the current sampling point is the 5 th sampling point, the corresponding remaining space value is 3.8%, and is less than the reference value 4%, and the remaining space change trend bitmap corresponding to the 5 th sampling point is 1110, that is, the bit in the bitmap is a mixture of 1 and 0, so that the garbage collection rate corresponding to the fourth sampling point is calculated according to the second step size corresponding to the remaining space change trend bitmap.

It should be understood that, in the embodiment of the present application, the remaining spatial variation trend bitmap of the sampling interval corresponding to different sampling points may also be as shown in table 3.

TABLE 3 residual spatial variation trend bitmap corresponding to different sampling points

As shown in table 3, the corresponding step size is determined according to the number of 0 or 1 included in the remaining spatial variation trend bitmap corresponding to different sampling points, for example, the remaining spatial variation trend bitmap does not include 0, and corresponds to the first step size. The remaining space variation trend bitmap includes 10, and the corresponding is a second step size. The remaining space variation trend bitmap comprises two 0 s, and the corresponding is a third step length, wherein the first step length is larger than the third step length, and the third step length is larger than the second step length. The embodiments of the present application are not limited thereto.

According to the method for recovering the garbage of the solid state disk, different step lengths are determined according to the number of 0 or 1 in the remaining space change trend bitmap, under the condition that the value of 1 in the remaining space change trend bitmap, which represents the remaining space of the last sampling point, is reduced compared with the value of the remaining space of the current sampling point, and the value of 0 in the remaining space change trend bitmap, which represents the remaining space of the last sampling point, is increased compared with the value of the remaining space of the current sampling point, under the condition that all bits in the remaining space change trend bitmap are 1 or 0, the garbage recovery rate of the SSD corresponding to the current sampling point is determined according to the larger first step length. Or, under the condition that the bit in the remaining space variation trend bitmap is a mixture of 1 and 0, determining the garbage collection rate of the SSD corresponding to the current sampling point according to the smaller first step size. The number of recovery concurrencies (recovery rate) can be dynamically adjusted such that the gap between the number of recovery concurrencies and the number of stable concurrencies is reduced. So that the number of recovery concurrencies varies with the number of stable concurrencies. The impact of the garbage collection process on the I/O of the SSD is reduced, and the garbage collection performance and the user experience of the SSD are improved. And the method is convenient for practical realization, and saves resources and cost.

Optionally, as an embodiment, in S120, determining a garbage collection rate of the SSD corresponding to the current sampling point according to a step size corresponding to the remaining space variation trend includes: determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the following formula (3):

wherein, V_iGarbage recovery rate, V, of the SSD for the current sample point_i-1Garbage recovery rate, N, of the SSD for the previous sampling point_iFor the remaining spatial value of the SSD corresponding to the current sample point, N_i-1And B is the residual space value of the SSD corresponding to the previous sampling point, B is the residual space reference interval of the SSD, and S is the step length corresponding to the residual space variation trend.

Specifically, different remaining space variation trends correspond to different step lengths, so the garbage collection rate of the SSD corresponding to each sampling point can be calculated by the above formula (3). Specifically, when the remaining space variation trends are both increased or both decreased, the garbage collection rate of the SSD corresponding to the current sampling point may be determined according to the first step size. In the case that the remaining space variation trend includes an increase and a decrease, the garbage collection rate of the SSD corresponding to the current sampling point may be determined according to the second step size. The value of the first step is greater than the value of the second step.

Specifically, determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the first step size includes:

determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the following formula (4):

in the formula (4), V_iGarbage recovery rate, V, of the SSD for the current sample point_i-1Garbage recovery rate, N, of the SSD for the previous sampling point_iFor the remaining spatial value of the SSD corresponding to the current sample point, N_i-1The residual space value of the SSD corresponding to the previous sampling point, B is the residual space reference interval of the SSD, S₁Is the first step size.

Specifically, in combination with the examples shown in table 1 or table 2, it is assumed that the current sampling point is the 2 nd sampling point, and since the 2 nd sampling point is the sampling point when garbage collection is performed first, it can be defined that the garbage collection rate of the SSD corresponding to the first sampling point for performing SSD garbage collection is 1 concurrent number, that is, the garbage collection rate of the SSD corresponding to the 2 nd sampling point is 1 concurrent number.

For another example, assume that the current sample point is the 3 rd sample point, i.e., i is 3, V_i-1The garbage collection rate of SSD corresponding to the 2 nd sampling point is shown as V_i-1＝1，N_iFor the remaining space value, N, of the SSD corresponding to the 3 rd sampling point_i＝3.8％。N_i-1For the remaining space value of the SSD, N, corresponding to the 2 nd sampling point_i-13.9%, B is the remaining spatial reference interval of the SSD, and B is 0.1%. S₁The first step size. Assume that the first step size has a value of 200. And (4) substituting the formula (4) to obtain that the garbage recovery rate (recovery concurrency number) corresponding to the 3 rd sampling point is 201. That is, in the period from time T +3 to time T +4, the garbage collection rate of the SSD is 201 concurrent numbers of collection.

It is understood that if the difference between the residual space of the 4 th sample point and the residual space of the 3 rd sample point is less than 0.1%. The garbage recovery rate in the period from the 3 rd sampling point to the 4 th sampling point is not greatly different from the rate of writing data into the SSD in the period, that is, the recovery concurrency number is substantially balanced with the stable concurrency number, so that the garbage recovery rate (recovery concurrency number) corresponding to the 3 rd sampling point can be set to be the garbage recovery rate corresponding to the 4 th sampling point. I.e. not in calculating the garbage collection rate corresponding to the 4 th sampling point.

Optionally, determining the garbage collection rate of the SSD corresponding to the current sampling point according to the second step size includes:

determining the recovery rate of the current sampling point corresponding to the SSD garbage recovery according to the following formula (5):

in the formula (5), V_iGarbage recovery rate, V, of the SSD for the current sample point_i-1Garbage recovery rate, N, of the SSD for the previous sampling point_iFor the remaining spatial value of the SSD corresponding to the current sample point, N_i-1The residual space value of the SSD corresponding to the previous sampling point, B is the residual space reference interval of the SSD, S₂Is the second step size.

Specifically, assume that the current sample point is the 5 th sample point, i.e., i is 5, V_i-1Corresponds to the 4 th sampling pointOf the SSD, e.g., V_i-1＝601。N_iThe residual space value of SSD, N, corresponding to the 5 th sampling point_i＝3.8％。N_i-1For the remaining space value of the SSD, N, corresponding to the 4 th sampling point_i-13.7%. B is the remaining spatial reference interval of the SSD, B being 0.1%. S₂The second step size. Assume that the second step size has a value of 20. Substituting the formula (5) to obtain that the garbage recovery rate (recovery concurrency number) corresponding to the 5 th sampling point is 561. That is, during the period from time T +5 to time T +6, the garbage collection rate of the SSD is 561 collected concurrency numbers. The recovery rate of the 5 th sample is reduced compared to the recovery rate 601 of the 4 th sample. Since 0 appears for the first time in the remaining space variation trend bitmap of the sampling interval of the 5 th sample, it means that the remaining space increases. That is, in the period from the 4 th sampling point to the 5 th sampling point, the rate of writing data into the SSD is smaller than the rate of garbage collection, that is, the collection concurrency number is larger than the stable concurrency number, and the stable concurrency number is smaller than 601, since 0 appears in the remaining space variation trend bitmap corresponding to the 5 th sampling point for the first time, it is proved that the stable concurrency number is in the 601 attachment. Therefore, after the 5 th sampling point, the recovery concurrency number needs to be adjusted by fine adjustment with a smaller step size.

According to the method for recovering the garbage of the solid state disk, the current recovery concurrency number is calculated according to the formula (3), the formula (4) or the formula (5). The data of the recovery concurrency number can be rapidly obtained, so that the garbage recovery efficiency of the SSD is improved. And the recovery concurrency number can be accurately obtained by using formula calculation. The effect of dynamically adjusting the garbage recovery rate of the SSD and the user experience are improved. And the actual implementation and the subsequent updating and maintenance are facilitated.

It should also be understood that, in addition to calculating the current recycling concurrence number by using the above formula (3), or formula (4), or formula (5), other formulas, or any modified formulas of the above formulas may also be used to calculate the current recycling concurrence number, and the embodiments of the present application are not limited herein.

It should also be understood that, in the embodiment of the present application, it may also be determined to calculate the recovery concurrency number by using the corresponding step size according to the number of 0 or 1 in the remaining space variation trend bitmap, for example, different step sizes are determined according to the remaining space variation trend bitmap corresponding to different sampling points shown in table 2. The embodiments of the present application are not limited thereto.

It should also be understood that in the embodiments of the present application, the first step size and the second step size only indicate two step sizes with different lengths, i.e., two step sizes with different numbers of concurrences. The terms "first" and "second" are merely used to distinguish different step sizes, i.e., do not limit the scope of the embodiments of the present application.

Fig. 4 is a graph illustrating a relationship between a recovery concurrency number (current recovery concurrency number) of a current sampling point and a difference between a reference value and a residual space according to an embodiment of the present application. As shown in fig. 4, when the residual spatial variation trend (i.e., the residual spatial variation trend of the sampling interval corresponding to the current sampling point) corresponding to the current recovery concurrency number is increased or decreased, the difference between the current recovery concurrency number and the stable concurrency number is proved to be large by using the current recovery concurrency number calculated by the above formula (3) or formula (4). Along with the increase of the difference value between the reference value and the residual space, the current recovery concurrency number correspondingly increases, namely the garbage recovery rate increases. The relationship of the linear function is presented. And under the condition that the residual space variation trend corresponding to the current recovery concurrency number (namely the residual space variation trend of the sampling interval corresponding to the current sampling point) comprises an increasing trend and a decreasing trend, the difference between the current recovery concurrency number and the stable concurrency number is proved to be smaller. The relation between the current recovery concurrency number and the difference between the reference value and the remaining space is not a linear function. The difference between the reference value and the remaining space varies less, while the corresponding current recycling concurrency number varies more.

FIG. 5 is a graph illustrating a relationship between a current number of concurrent recoveries and time, according to an embodiment of the present application. As shown in fig. 5, when the residual spatial variation trend bits (i.e., the residual spatial variation trend of the sampling interval corresponding to the current sampling point) corresponding to the current recovery concurrency number are both increased or both decreased by using the current recovery concurrency number calculated by using the above formula (3) or formula (4), it is proved that the difference between the current recovery concurrency number and the stable concurrency number is large, and the recovery concurrency number continuously increases with the increase of time, i.e., the current recovery concurrency number and time exhibit a linear function relationship. And under the condition that the residual space variation trend corresponding to the current recovery concurrency number (namely the residual space variation trend of the sampling interval corresponding to the current sampling point) comprises an increasing trend and a decreasing trend, the difference between the current recovery concurrency number and the stable concurrency number is proved to be smaller. As time goes by, the recovery concurrency number does not change much, that is, the recovery concurrency number changes around a stable concurrency number.

The method for recycling the garbage of the solid state disk, provided by the embodiment of the application, provides a two-stage step size adjusting mode, namely a coarse adjusting (first step size) mode and a fine adjusting (second step size) mode, and determines which adjusting mode to use according to the number of 0 or 1 in a remaining space change trend bitmap. And (3) coarse adjustment is carried out for all 1 or all 0 in the default residual space change trend bitmap, and the recovery concurrency number is calculated by using a larger first step size, namely the same change trend needs to be kept for a period of time for coarse adjustment, so that the difference between the current concurrency value and the stable concurrency value is larger. If 0 and 1 in the remaining space variation trend bitmap are mixed, which indicates that the current concurrency number is jittered around a stable concurrency value, the conversion to fine adjustment is needed, namely, a smaller first step size is used for calculating the recycled concurrency number, and the recycled concurrency number is slowly closed towards the stable concurrency value. So that the number of recovery concurrencies varies with the number of stable concurrencies. The impact of the garbage collection process on the I/O of the SSD is reduced, and the garbage collection efficiency and the user experience of the SSD are improved.

Optionally, all bits in the remaining spatial variation trend bitmap corresponding to the first sampling point are 1.

Specifically, since the sampling process is always performed, garbage collection is performed only when the remaining space value of the SSD is smaller than the remaining space reference value of the SSD. Therefore, at the time of the first sampling, all the bits in the corresponding remaining space variation trend bitmap are 1. I.e. the bits in the initial remaining spatial variation trend bitmap are all 1. In this case, 1 in the remaining space variation tendency bitmap indicates that the value of the remaining space of the last sample point and the value of the remaining space of the present (current) sample point are reduced as compared with each other. 0 in the residual space variation tendency bitmap indicates that the value of the residual space of the last sample point and the value of the residual space of the present (current) sample point increase.

It should be understood that, at the time of the first sampling, the bits in the corresponding remaining space variation trend bitmap may also be all 0, that is, the bits in the initial remaining space variation trend bitmap are all 0. In this case, 0 in the remaining space variation tendency bitmap indicates that the value of the remaining space of the last sample point and the value of the remaining space of the present (current) sample point are reduced as compared with each other. A 1 in the residual space variation tendency bitmap indicates that the value of the residual space of the last sample point increases compared to the value of the residual space of the present (current) sample point.

The SSD garbage recycling method provided by the embodiment of the application. Whether all bits in the initial remaining spatial variation trend bitmap are 1 or all 0. The calculation difficulty of calculating the SSD garbage recycling concurrent number can be reduced, and the step length corresponding to different residual space change trend bitmaps can be determined more conveniently and rapidly. The garbage recycling performance of the SSD is improved.

Optionally, the garbage collection rate of the SSD corresponding to the first sampling point for performing garbage collection of the SSD is 1 concurrent number.

Specifically, in combination with the example shown in table 1, it is assumed that the current sampling point is the 2 nd sampling point, and since the 2 nd sampling point is the sampling point when garbage collection is performed first, it can be defined that the garbage collection rate of the SSD corresponding to the first sampling point for performing SSD garbage collection is 1 concurrent number, that is, the garbage collection rate of the SSD corresponding to the 2 nd sampling point is 1 concurrent number. Therefore, the recovery concurrency number can be calculated more conveniently and rapidly, and the garbage recovery efficiency of the SSD is improved.

It should be understood that the garbage collection rate of the SSD corresponding to the first sampling point for performing garbage collection of the SSD may also be other values, for example, 10 or 20 concurrent numbers, and the embodiment of the present application is not limited herein.

Optionally, the remaining space variation trend bitmap includes 16 bits. For example, the remaining space variation trend bitmap is 16 1 s, or 16 0 s, or 16 total numbers of 0 s and 1 s. Therefore, the residual space variation trend bitmap can reflect the relationship between the recovery concurrency number and the stable concurrency number more accurately. The residual space variation trend bitmap is more accurate, and the adjustment of the recovered concurrent number is closer to the stable concurrent number.

It should be understood that, in the embodiment of the present application, the remaining space variation trend bitmap includes other numbers of bits, for example, 5 bits or 10 bits, etc. The embodiments of the present application are not limited thereto.

It should be understood that the above description is only for the purpose of helping those skilled in the art better understand the embodiments of the present application, and is not intended to limit the scope of the embodiments of the present application. Various equivalent modifications or changes, or combinations of any two or more of the above, may be apparent to those skilled in the art in light of the above examples given. Such modifications, variations, or combinations are also within the scope of the embodiments of the present application.

It should also be understood that the sequence numbers of the above-mentioned processes do not mean the execution sequence, and the execution sequence of each process should be determined by the function and the inherent logic thereof, and should not constitute any limitation to the implementation process of the embodiments of the present application.

An embodiment of the present application further provides a solid state disk, as shown in fig. 6, the solid state disk 200 includes:

the storage unit 210: for storing data.

The processing unit 220: and the residual space variation trend of the storage unit of at least two sampling points in a sampling interval corresponding to the current sampling point is determined, and the sampling interval comprises a plurality of sampling points.

The processing unit 220 is further configured to: and determining the garbage recovery rate of the storage unit corresponding to the current sampling point according to the step length corresponding to the change trend of the residual space.

The processing unit 220 is further configured to: and the garbage collection device is used for carrying out garbage collection on the storage unit according to the garbage collection rate of the storage unit corresponding to the current sampling point in a time period between the current sampling point and the next sampling point.

The Solid State Disk (SSD) provided in the embodiment of the application determines a step length for calculating a recovery concurrency number (which may also be referred to as a recovery rate) utilization of a current sampling point according to a residual space variation trend of an SSD (storage unit) of a plurality of sampling points included in a sampling interval corresponding to the current sampling point. And calculating the recovery rate of the current sampling point according to the determined step length, and performing garbage recovery of the SSD according to the calculated recovery rate. The residual space variation trend of the current sampling point corresponding to the sampling interval is different, and the step length is also different. The purpose of dynamically adjusting the step length can be achieved, and therefore the garbage recycling rate of the SSD can be dynamically adjusted. Finally, the recovery concurrency number is always close to the stable concurrency number. In the process of SSD garbage recovery, the impact on the I/O of the SSD is reduced, and the performance and the user experience of the SSD are improved.

Optionally, as an embodiment, when the remaining space variation trends all increase or all decrease, the step size corresponding to the remaining space variation trend is a first step size. In the case that the remaining space variation trend includes an increase and a decrease, the step size corresponding to the remaining space variation trend is a second step size. Wherein the value of the first step is greater than the value of the second step. Wherein the value of the first step is greater than the value of the second step.

Optionally, as an embodiment, the remaining space variation trend is represented by a remaining space variation trend bitmap, each bit in the remaining space variation trend bitmap is used to indicate a variation trend of the remaining space of two sampling points in the sampling interval, and the processing unit 220 is specifically configured to: determining the remaining space change trend bitmap of a sampling interval corresponding to the current sampling point; and determining the garbage recovery rate of the storage unit corresponding to the current sampling point according to the step length corresponding to the residual space change trend bitmap.

Optionally, as an embodiment, the processing unit 220 is specifically configured to: determining the residual spatial value N of the memory cell 210 of the previous sample point_i-1(ii) a Determining the residual space value N of the memory cell 210 corresponding to the current sampling point_i(ii) a In N_i-1Greater than N_iAnd N is_i-1And N_iWhen the difference is greater than or equal to the value of the remaining space reference interval of the storage unit 210, deleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point, and adding one bit 1 after the last bit to obtain the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_i-1And N_iThe value of (b) is positive.

Optionally, as an embodiment, the processing unit 220 is specifically configured to: determining the remaining space value N of the memory cell 210 corresponding to the previous sampling point_i-1(ii) a Determining the residual space value N of the memory cell 210 corresponding to the current sampling point_i(ii) a In N_i-1Less than N_iAnd N is_iAnd N_i-1When the difference is greater than or equal to the value of the remaining space reference interval of the storage unit 210, deleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point, and adding a bit 0 after the last bit to obtain the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point; wherein, the value of i is a positive integer greater than or equal to 2, and N_iAnd N_i-1The value of (b) is positive.

Optionally, as an embodiment, before performing garbage collection on the storage unit according to the garbage collection rate of the storage unit corresponding to the current sampling point, the processing unit 220 is further configured to: determining that the remaining space value of the memory cell 210 corresponding to the current sampling point is smaller than the remaining space reference value of the memory cell 210.

Optionally, as an embodiment, the processing unit 220 is specifically configured to: determining the garbage collection rate of the storage unit 210 corresponding to the current sampling point according to the following formula:

wherein, V_iFor the memory cell corresponding to the current sample pointRate of garbage recovery, V_i-1The garbage recovery rate, N, of the storage unit corresponding to the previous sampling point_iThe remaining space value of the memory cell corresponding to the current sampling point, N_i-1And B is the residual space value of the storage unit corresponding to the previous sampling point, B is the residual space reference interval of the storage unit, and S is the step length corresponding to the residual space change trend.

Optionally, as an embodiment, all bits in the remaining spatial variation trend bitmap corresponding to the first sampling point are 1.

Optionally, as an embodiment, the remaining space variation trend bitmap includes 16 bits.

It should be understood that the embodiment of the solid state disk corresponds to the above-mentioned embodiment of the method for garbage collection of the solid state disk, and similar descriptions may refer to the embodiment of the method, and in order to avoid repetition, the detailed description is not repeated here

It is also understood that the processing unit 220 may be implemented by a processor and the storage unit 210 may be implemented by a memory. An embodiment of the present application further provides a solid state disk, as shown in fig. 7, the solid state disk 300 includes: memory 310, processor 320, input/output interface 330, transceiver 340. The memory 310, the processor 320, the input/output interface 330 and the transceiver 340 are connected via an internal connection path, the memory 310 is used for storing program instructions and data, and the processor 320 is used for executing the program instructions stored in the memory 320 to control the input/output interface 330 to receive input data and information, output data such as operation results, and control the transceiver 340 to transmit signals. And enabling the solid state disk to execute any solid state disk garbage recycling method.

It should be understood that, in the embodiment of the present Application, the processor 320 may adopt a general-purpose Central Processing Unit (CPU), a microprocessor, an Application Specific Integrated Circuit (ASIC), or one or more Integrated circuits, for executing related programs to implement the technical solutions provided in the embodiments of the present Application.

It should also be understood that the transceiver 340 is also referred to as a communication interface, and uses a transceiver device such as, but not limited to, a transceiver to enable communication between the data verification apparatus 300 and other devices or communication networks.

The memory 310 may include a read-only memory and a random access memory, and provides instructions and data to the processor 320. A portion of processor 320 may also include non-volatile random access memory. For example, processor 320 may also store information of the device type.

In implementation, the steps of the above method may be performed by integrated logic circuits of hardware or instructions in the form of software in the processor 320. The method for transmitting data disclosed in the embodiments of the present application may be directly implemented by a hardware processor, or implemented by a combination of hardware and software modules in the processor. The software module may be located in ram, flash memory, rom, prom, or eprom, registers, etc. storage media as is well known in the art. The storage medium is located in the memory 310, and the processor 320 reads the information in the memory 310 and completes the steps of the method in combination with the hardware. To avoid repetition, it is not described in detail here.

It should be understood that in the embodiments of the present application, the processor may be a Central Processing Unit (CPU), and the processor may also be other general-purpose processors, Digital Signal Processors (DSPs), Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) or other programmable logic devices, discrete gate or transistor logic devices, discrete hardware components, and the like. A general purpose processor may be a microprocessor or the processor may be any conventional processor or the like.

The present application also provides a computer readable medium for storing a computer program code, the computer program including instructions for executing at least one of the methods of the present application. The readable medium may be a read-only memory (ROM) or a Random Access Memory (RAM), which is not limited in this embodiment of the present application.

An embodiment of the present application further provides a computer program product, where the computer program product includes: computer program code which, when run on a computer, causes the computer to perform the various solid state disk garbage collection methods described above.

An embodiment of the present application further provides a system chip, where the system chip includes: a processing unit, which may be, for example, a processor, and a communication unit, which may be, for example, an input/output interface, a pin or a circuit, etc. The processing unit can execute computer instructions to enable a chip in the terminal to execute any one of the above solid state disk garbage collection methods.

Optionally, the computer instructions are stored in a storage unit.

Alternatively, the storage unit is a storage unit in the chip, such as a register, a cache, and the like, and the storage unit may also be a storage unit located outside the chip in the terminal, such as a ROM or other types of static storage devices that can store static information and instructions, a RAM, and the like. The processor mentioned in any of the above may be a general purpose CPU, microprocessor, ASIC, or one or more integrated circuits for controlling the execution of the programs of the above method for controlling the memory array.

It should be understood that the term "and/or" and "at least one of a or B" herein is merely one type of association that describes an associated object, meaning that three types of relationships may exist, e.g., a and/or B, may mean: a exists alone, A and B exist simultaneously, and B exists alone. In addition, the character "/" herein generally indicates that the former and latter related objects are in an "or" relationship.

Those of ordinary skill in the art will appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware or combinations of computer software and electronic hardware. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the implementation. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present application.

It is clear to those skilled in the art that, for convenience and brevity of description, the specific working processes of the above-described systems, apparatuses and units may refer to the corresponding processes in the foregoing method embodiments, and are not described herein again.

In the several embodiments provided in the present application, it should be understood that the disclosed system, apparatus and method may be implemented in other ways. For example, the above-described apparatus embodiments are merely illustrative, and for example, the division of the unit is only one logical functional division, and other divisions may be realized in practice, for example, a plurality of units or components may be combined or integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or units, and may be in an electrical, mechanical or other form.

The units described as separate parts may or may not be physically separate, and parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units can be selected according to actual needs to achieve the purpose of the solution of the embodiment.

In addition, functional units in the embodiments of the present application may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit.

This functionality, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a computer readable storage medium. Based on such understanding, the technical solution of the present application or portions thereof that substantially contribute to the prior art may be embodied in the form of a software product stored in a storage medium and including instructions for causing a computer device (which may be a personal computer, a server, or a network device) to execute all or part of the steps of the method according to the embodiments of the present application. And the aforementioned storage medium includes: various media capable of storing program codes, such as a U disk, a removable hard disk, a ROM, a RAM, a magnetic disk, or an optical disk.

The above description is only for the specific embodiments of the present application, but the scope of the present application is not limited thereto, and any person skilled in the art can easily conceive of the changes or substitutions within the technical scope of the present application, and all the changes or substitutions should be covered by the scope of the present application. Therefore, the protection scope of the present application shall be subject to the protection scope of the claims.

Claims

1. A method for recovering garbage of a solid state disk is characterized by comprising the following steps:

determining the change trend of the residual space of the solid state disk SSD of at least two sampling points in a sampling interval corresponding to the current sampling point, wherein the sampling interval comprises a plurality of sampling points;

determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the residual space variation trend;

in a time period between the current sampling point and the next sampling point, performing garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point;

the step length is a recovery concurrency number corresponding to the reference interval; the reference interval is a minimum unit of a difference value between a remaining space of the SSD and a reference value of the SSD; the concurrency number is a unit of recovery amount in the SSD garbage recovery.

2. The method according to claim 1, wherein, when the remaining spatial variation trends all increase or all decrease, the step size corresponding to the remaining spatial variation trend is a first step size;

under the condition that the residual space variation trend comprises increase and decrease, the step length corresponding to the residual space variation trend is a second step length;

3. The method of claim 2, wherein the residual spatial trend is represented by a residual spatial trend bitmap, each bit of the residual spatial trend bitmap being used to indicate the trend of the residual space for two sampling points within the sampling interval,

the determining of the residual space variation trend of the solid state disk SSD of at least two sampling points in the sampling interval corresponding to the current sampling point includes:

determining the residual space change trend bitmap of a sampling interval corresponding to the current sampling point;

the determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the step length corresponding to the residual space variation trend comprises:

4. The method of claim 3, wherein the determining the remaining spatial trend bitmap for the sampling interval corresponding to the current sampling point comprises:

determining a residual spatial value N of the SSD for a previous sample point_i-1；

Determining the residual space value N of the SSD corresponding to the current sampling point_i；

In N_i-1Greater than N_iAnd N is_i-1And N_iDeleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point and adding one bit 1 after the last bit to obtain the current sampling point under the condition that the difference value of (2) is greater than or equal to the value of the remaining space reference interval of the SSDThe residual space variation trend bitmap of a sampling interval corresponding to the sampling points;

wherein, the value of i is a positive integer greater than or equal to 2, and N_i-1And N_iThe value of (b) is positive.

5. The method of claim 3, wherein the determining the remaining spatial trend bitmap for the sampling interval corresponding to the current sampling point comprises:

determining a remaining space value N of the SSD corresponding to a previous sampling point_i-1；

In N_i-1Less than N_iAnd N is_iAnd N_i-1Deleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is greater than or equal to the value of the remaining space reference interval of the SSD, and adding one bit of 0 after the last bit to obtain the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point;

wherein, the value of i is a positive integer greater than or equal to 2, and N_iAnd N_i-1The value of (b) is positive.

6. The method according to any one of claims 1 to 5, wherein before the garbage collection of the SSD according to the garbage collection rate of the SSD corresponding to the current sampling point, the method further comprises:

determining that the residual space value of the SSD corresponding to the current sampling point is smaller than the residual space reference value of the SSD.

7. The method according to any one of claims 4 or 5, wherein the determining the garbage collection rate of the SSD corresponding to the current sampling point according to the step size corresponding to the remaining space variation trend comprises:

determining the garbage recovery rate of the SSD corresponding to the current sampling point according to the following formula:

wherein, V_iA garbage recovery rate, V, of the SSD corresponding to the current sampling point_i-1A garbage recovery rate, N, of the SSD for the previous sampling point_iA remaining space value, N, of the SSD corresponding to the current sample point_i-1And B is the residual space value of the SSD corresponding to the previous sampling point, B is the residual space reference interval of the SSD, and S is the step length corresponding to the residual space variation trend.

8. The method according to any one of claims 3 to 5, wherein all bits in the remaining spatial variation trend bitmap corresponding to the first sampling point are 1.

9. The method of any of claims 3 to 5, wherein the remaining space trend bitmap comprises 16 bits.

10. A solid state disk, comprising:

a storage unit: for storing data;

a processing unit: the residual space variation trend of the storage unit of at least two sampling points in a sampling interval corresponding to the current sampling point is determined, and the sampling interval comprises a plurality of sampling points;

the processing unit is further to: determining the garbage recycling rate of the storage unit corresponding to the current sampling point according to the step length corresponding to the residual space variation trend;

the processing unit is further to: the garbage collection device is used for carrying out garbage collection on the storage unit according to the garbage collection rate of the storage unit corresponding to the current sampling point in a time period between the current sampling point and the next sampling point;

11. Solid state disk according to claim 10,

under the condition that the residual space variation trends are increased or decreased, the step length corresponding to the residual space variation trend is a first step length;

12. The solid state disk of claim 11, wherein the residual space trend is represented by a residual space trend bitmap, each bit of the residual space trend bitmap being used for indicating the trend of the residual space of two sampling points in the sampling interval,

the processing unit is specifically configured to:

and determining the garbage recovery rate of the storage unit corresponding to the current sampling point according to the step length corresponding to the residual space change trend bitmap.

13. The solid state disk of claim 12, wherein the processing unit is specifically configured to:

determining the residual spatial value N of the memory cell of the previous sample point_i-1；

Determining the residual space value N of the storage unit corresponding to the current sampling point_i；

In N_i-1Greater than N_iAnd N is_i-1And N_iDeleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is greater than or equal to the value of the remaining space reference interval of the storage unit, and adding one bit 1 after the last bit to obtain the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point;

14. The solid state disk of claim 12, wherein the processing unit is specifically configured to:

determining the residual space value N of the memory cell corresponding to the previous sampling point_i-1；

In N_i-1Less than N_iAnd N is_iAnd N_i-1Deleting the first bit in the remaining space change trend bitmap of the sampling interval corresponding to the previous sampling point under the condition that the difference value of the sampling interval is greater than or equal to the value of the remaining space reference interval of the storage unit, and adding a bit 0 after the last bit to obtain the remaining space change trend bitmap of the sampling interval corresponding to the current sampling point;

15. The solid state disk according to any one of claims 10 to 14, wherein before the garbage collection of the storage unit according to the garbage collection rate of the storage unit corresponding to the current sampling point, the processing unit is further configured to:

and determining that the residual space value of the storage unit corresponding to the current sampling point is smaller than the residual space reference value of the storage unit.

16. The solid state disk of any one of claims 13 or 14, wherein the processing unit is specifically configured to:

determining the garbage recovery rate of the storage unit corresponding to the current sampling point according to the following formula:

wherein, V_iA garbage recovery rate, V, for the memory cell corresponding to the current sampling point_i-1A garbage collection rate, N, for the memory cell corresponding to the previous sampling point_iA remaining space value, N, of the memory cell corresponding to the current sampling point_i-1And the residual space value of the storage unit corresponding to the previous sampling point is obtained, B is the residual space reference interval of the storage unit, and S is the step length corresponding to the residual space variation trend.

17. The solid state disk according to any one of claims 12 to 14, wherein all bits in the remaining spatial variation trend bitmap corresponding to the first sampling point are 1.

18. The solid state disk of any of claims 12 to 14, wherein the remaining space trend bitmap comprises 16 bits.

19. A computer-readable storage medium for storing a computer program, characterized in that the computer program is adapted to execute the instructions of the method according to any of claims 1 to 9.