CN110955609B

CN110955609B - Evolved automatic flow tracking (EAST) for multi-flow, open channel storage devices

Info

Publication number: CN110955609B
Application number: CN201811154584.2A
Authority: CN
Inventors: 路向峰; 孙丛; 王金一
Original assignee: Beijing Memblaze Technology Co Ltd
Current assignee: Beijing Memblaze Technology Co Ltd
Priority date: 2018-09-26
Filing date: 2018-09-30
Publication date: 2024-07-02
Anticipated expiration: 2038-09-30
Also published as: CN110955609A

Abstract

An evolved automatic flow tracking (EAST) for multi-flow, open channel storage devices is provided. The provided method for distributing streams for IO commands comprises the following steps: acquiring an IO command; acquiring a first update parameter according to the IO command; and distributing the first stream for the IO command according to the first update parameter.

Description

Evolved automatic flow tracking (EAST) for multi-flow, open channel storage devices

Technical Field

The present application relates to storage technology, and more particularly to evolved automatic flow tracking (EAST, evolutional Automatic STREAM TRACKING) for multi-flow storage devices or open channel storage devices, identifying data accessing the storage devices as multiple flows, and adaptively tracking and evolving the identified multiple flows.

Background

Fig. 1 illustrates a block diagram of a storage device. The storage device 102 is coupled to a host for providing storage capability for the host. The host and the storage device 102 may be coupled by a variety of means including, but not limited to, connecting the host to the solid state storage device 102 via, for example, SATA (SERIAL ADVANCED Technology Attachment ), SCSI (Small Computer system interface), SAS (SERIAL ATTACHED SCSI ), IDE (INTEGRATED DRIVE Electronics), USB (Universal Serial Bus ), PCIE (PERIPHERAL COMPONENT INTERCONNECT EXPRESS, PCIE, peripheral component interconnect), NVMe (NVM Express, high speed nonvolatile storage), ethernet, fibre channel, wireless communication network, etc. The host may be an information processing device capable of communicating with the storage device in the manner described above, such as a personal computer, tablet, server, portable computer, network switch, router, cellular telephone, personal digital assistant, or the like. The memory device 102 includes an interface 103, a control unit 104, one or more NVM chips 105, and a DRAM (Dynamic Random Access Memory ) 110.

NAND flash memory, phase change memory, feRAM (Ferroelectric RAM, ferroelectric memory), MRAM (Magnetic Random Access Memory, magnetoresistive memory), RRAM (RESISTIVE RANDOM ACCESS MEMORY, resistive memory), etc. are common NVM.

The interface 103 may be adapted to exchange data with a host by means of, for example SATA, IDE, USB, PCIE, NVMe, SAS, ethernet, fibre channel, etc.

The control unit 104 is used to control data transfer among the interface 103, NVM chip 105, and DRAM 110, and also for memory management, host logical address to flash physical address mapping, erase balancing, bad block management, etc. The control component 104 can be implemented in a variety of ways, such as software, hardware, firmware, or a combination thereof, for example, the control component 104 can be in the form of an FPGA (Field-programmable gate array), an ASIC (Application SPECIFIC INTEGRATED Circuit), or a combination thereof. The control component 104 may also include a processor or controller in which software is executed to manipulate the hardware of the control component 104 to process IO (Input/Output) commands. Control unit 104 may also be coupled to DRAM 110 and may access data of DRAM 110. FTL tables and/or cached data of IO commands may be stored in the DRAM.

The control section 104 includes a flash interface controller (or referred to as a media interface controller, a flash channel controller) that is coupled to the NVM chip 105 and issues commands to the NVM chip 105 in a manner conforming to an interface protocol of the NVM chip 105 to operate the NVM chip 105 and receive a command execution result output from the NVM chip 105. Known NVM chip interface protocols include "Toggle", "ONFI", and the like.

In a storage device, FTL (Flash Translation Layer ) is utilized to maintain mapping information from logical addresses to physical addresses. The logical addresses constitute the memory space of the memory device perceived by upper software such as the operating system. The physical address is an address for accessing a physical memory location of the memory device. Address mapping may also be implemented in the related art using an intermediate address modality. For example, logical addresses are mapped to intermediate addresses, which in turn are further mapped to physical addresses.

The table structure storing mapping information from logical addresses to physical addresses is called FTL table. FTL tables are important metadata in a storage device. Typically, the entries of the FTL table record address mapping relationships in units of data pages in the storage device.

Fig. 2 shows a schematic diagram of a large block. A chunk includes a physical block from each of a plurality of logical units (referred to as a logical unit group). Optionally, each logical unit provides a physical block for a chunk. By way of example, a large block is constructed on every 16 Logical Units (LUNs). Each chunk includes 16 physical blocks, from each of 16 Logical Units (LUNs). In the example of FIG. 2, chunk 0 includes physical chunk 0 from each of the 16 Logical Units (LUNs), and chunk 1 includes physical chunk 1 from each Logical Unit (LUN). There are a variety of other ways to construct the chunk.

As an alternative, page stripes are constructed in large blocks, with physical pages of the same physical address in each Logical Unit (LUN) constituting a "page stripe". In FIG. 2, physical pages 0-0, 0-1 … …, and 0-x form page stripe 0, where physical pages 0-0, 0-1, … …, physical pages 0-14 are used to store user data, and physical pages 0-15 are used to store parity data calculated from all user data within the stripe. Similarly, in FIG. 2, physical pages 2-0, physical pages 2-1 … …, and physical pages 2-x constitute page stripe 2. Alternatively, the physical page used to store the parity data may be located anywhere in the page stripe.

When a logical page is repeatedly written with data, the correspondence of the logical page address and the latest physical page address is recorded in FTL table entry, whereas the data recorded in the physical page address that was written with data but is no longer referenced (e.g., no record in FTL table) becomes "garbage" (data). Data that has been written to the data and referenced (e.g., has records in the FTL table) is referred to as valid data, and "garbage" is referred to as dirty data. The physical block containing dirty data is referred to as a "dirty physical block", and the physical block to which data is not written is referred to as a "free physical block".

Disclosure of Invention

The multi-stream storage device utilizes statistical properties of IO commands accessing the storage device to facilitate garbage collection. In a multi-stream storage device, write data is divided into multiple groups (each group is referred to as a "stream"). Multiple memory blocks or chunks simultaneously carry write data. And writing the data of each stream into different storage blocks or large blocks respectively. In a typical application, the host appends a stream identifier on the IO command. And the storage device uses the stream identifier to place the data written by the IO command in a physical block or a large block corresponding to the stream identifier.

An Open Channel (Open-Channel) storage device model provides FTL and garbage collection at a host, and an Open Channel storage device provides a storage medium interface, such as a Parallel Unit (PU), to the host. The computer is able to write data from different applications or IO commands with different stream identifiers to different parallel units.

It is desirable to provide better splitting algorithms to identify the characteristics of an IO command, and to assign a more appropriate flow identifier to the IO command. And the inventors have also appreciated that the applications that generate IO commands are diverse and varying, requiring streams to be able to adaptively evolve to track the pattern changes of IO commands.

The data recorded in the storage device is updated from time to time. The time interval between two data updates is referred to as the lifecycle of the data. Lifecycle is one of the features of IO commands. The various data have different lifecycles. For example, video-type data has a long life cycle or near read-only, and data cached as internet web pages has a relatively short life cycle, perhaps hours, days or months. With use, data recorded in the storage device gradually becomes invalid as the logical address is updated. The space occupied by invalid data is released by garbage collection and the like.

Since valid data and invalid data are recorded in a storage medium in a mixed manner, the valid data need to be moved in a garbage collection process. The movement of the valid data causes a write amplification effect that affects the performance and lifetime of the memory device. Prior art garbage collection operations select storage media with higher invalid data duty ratios for garbage collection in an effort to reduce write amplification.

According to an embodiment of the present application, data written to a storage device is partitioned into multiple streams (assigned stream identifiers), with the data of each stream having the same or similar lifecycle. And also according to the change of the life cycle of the data of each stream, so that the data belonging to the stream is allocated with the same stream even if the life cycle fluctuates, thereby enabling the stream to track the life cycle change of the data. The streams also have the opportunity to be split or merged so that the streams better indicate the lifecycle features of the data to which they belong.

The same stream is stored as much as possible in the same or adjacent physical blocks or chunks of the storage medium, and different streams are optionally stored as much as possible in different physical blocks or chunks of the storage medium. The physical blocks or chunks are recycled as a whole in the garbage recycling process. Since the data belonging to the same stream has similar life cycle, when garbage is recovered, physical blocks or large blocks with more invalid data proportion are more easily obtained, so that write amplification caused by garbage recovery process is reduced.

In addition to being applied to garbage collection processes, data splitting also provides opportunities for storage devices to optimize the handling of IOs.

Access dependencies are also a feature of IO commands that measure the likelihood that data will be accessed again soon after it has been accessed. According to an embodiment of the application, the data is also assigned a flow identifier according to the access dependency.

According to a first aspect of the present application there is provided a method of allocating data streams according to the first aspect of the present application, comprising the steps of: acquiring an IO command; acquiring update parameters according to the IO command; and distributing streams for the IO commands according to the updated parameters.

According to the method for distributing data streams in the first aspect of the present application, there is provided the method for distributing data streams in the second aspect of the present application, wherein the IO command carries an update parameter.

According to the method for distributing data streams in the first aspect of the present application, there is provided the method for distributing data streams in the third aspect of the present application, wherein data units accessed by the IO command are acquired, and an update time interval of the data units is acquired as an update parameter.

According to a method for distributing data streams in a first aspect of the present application, a method for distributing data streams in a fourth aspect of the present application is provided, wherein data units accessed by an IO command are acquired, update time intervals of the data units are acquired, and an average value, a median value and a mode value of one or more update time intervals of the data units are taken as update parameters.

According to a method for allocating data streams in a first aspect of the present application, there is provided a method for allocating data streams in a fifth aspect of the present application, wherein data units accessed by an IO command are acquired, an update time interval of the data units is acquired, an update parameter is calculated according to g '= (1-k) ×g+k×dt, where g' is the calculated update parameter, g is an old update parameter, and dt is the update time interval, 0< k <1.

The method of allocating a data stream according to any of the first to fifth aspects of the present application provides the method of allocating a data stream according to the sixth aspect of the present application, wherein the data units represent logical address spaces or physical address spaces of a specified size.

According to a sixth data stream allocation method of the first aspect of the present application, there is provided a seventh data stream allocation method of the first aspect of the present application, wherein a data unit accessed by an IO command is acquired, and a stream is allocated to the data unit according to an update parameter of the acquired data unit.

According to a seventh method of allocating a data stream according to the first aspect of the present application, there is provided the method of allocating a data stream according to the eighth aspect of the present application, wherein data units having the same update parameter or a distance of the update parameter less than a threshold value are allocated to the same stream.

According to a seventh method for allocating a data stream according to the first aspect of the present application, there is provided a method for allocating a data stream according to the eighth aspect of the present application, further comprising allocating the first stream for an IO command accessing the first data unit if the distance between the update parameter of the first data unit and the update parameter of the first stream is smaller than a threshold value.

According to a seventh method for allocating a data stream according to the first aspect of the present application, there is provided a method for allocating a data stream according to the ninth method for allocating a data stream according to the first aspect of the present application, wherein the first stream is allocated for data units with the same update parameters; and allocating a second stream to the data units with the distance of the updated parameters of the data units within the threshold value, and allocating a third stream to other data units.

According to a third to eighth aspects of the present application, there is provided the method for allocating a data stream according to the first aspect of the present application, wherein the method for allocating a data stream according to the first aspect of the present application comprises comparing the update parameters of the acquired data units with the update parameters of one or more streams, and allocating for the IO command a stream whose update parameters are within a threshold distance from the acquired update parameters.

The method for allocating data streams according to any one of the eighth to tenth aspects of the present application provides the method for allocating data streams of the eleventh aspect of the present application, wherein, in response to allocating streams for data units accessed by IO commands, update parameters of the data streams are calculated according to update parameters of the data units.

According to an eleventh method of allocating a data stream according to the first aspect of the present application, there is provided the twelfth method of allocating a data stream according to the first aspect of the present application, wherein in response to allocating a first stream to a data unit accessed by an IO command, an update parameter of a mean, median, mode data unit of update parameters of a plurality of or all data units allocated to the first stream is taken as an update parameter of the first stream.

According to a thirteenth aspect of the present application, there is provided a method of allocating a data stream according to the thirteenth aspect of the present application, wherein in response to allocating a first stream to a data unit accessed by an IO command, the update parameters of a plurality or all of the data units allocated to the first stream are weighted averaged, or the result of the low pass filtering is used as the update parameters of the first stream.

According to a method of eleventh allocating a data stream according to the first aspect of the present application, there is provided a method of fourteenth allocating a data stream according to the first aspect of the present application, wherein in response to allocating a first stream for a data unit accessed by an IO command, new update parameters of the first stream are calculated with update parameters of the data unit and old update parameters of the first stream.

According to a fourteenth method of allocating a data stream according to the first aspect of the present application, there is provided the method of fifteenth method of allocating a data stream according to the first aspect of the present application, wherein the new update parameter is a weighted sum of an old update parameter of the stream and an update parameter of the data unit.

According to a tenth to fifteenth aspect of the present application, there is provided the sixteenth method for allocating a data stream according to the first aspect of the present application, wherein if the acquired update parameters of the data unit are all greater than a threshold value, a new stream is created, and a new stream or a specified stream is allocated for the IO command.

A method of allocating data streams according to any of the tenth to fifteenth aspects of the present application provides the method of seventeenth allocation of data streams of the first aspect of the present application, wherein the update parameters of a new stream or streams are created from the update parameters of the streams, the update parameters of each stream representing a stream.

According to a sixteenth or seventeenth method of allocating data streams according to the first aspect of the present application, there is provided the eighteenth method of allocating data streams according to the first aspect of the present application, wherein a second update parameter representing the second stream and a third update parameter representing the third stream are generated based on the update parameters of the first stream.

According to a seventeenth method for allocating a data stream according to the first aspect of the present application, there is provided the nineteenth method for allocating a data stream according to the first aspect of the present application, wherein an average or statistical value of the second update parameter and the third update parameter is a first update parameter, and the first update parameter is greater than the second update parameter.

According to a method of allocating data streams of any of the tenth to nineteenth aspects of the present application, there is provided a method of twenty-first aspect of the present application, wherein new update parameters of the first stream are calculated in response to allocating the first stream for an IO command.

The method of allocating data streams according to any one of the first to twenty-first aspects of the present application provides the method of twenty-first allocating data streams of the first aspect of the present application, wherein the IO command is allocated to the initial stream.

The method for allocating data streams according to any one of the first to twenty-first aspects of the present application provides the method for twenty-second allocating data streams of the first aspect of the present application, wherein the update parameters are compared with the update parameters of the existing stream or streams, and a stream whose update parameters are within a threshold distance from the acquired update parameters is allocated to the IO command.

The method of allocating data streams according to any of the first to twenty-second aspects of the present application provides the twenty-third method of allocating data streams of the first aspect of the present application, wherein in response to allocating streams for IO commands, new update parameters of the allocated streams are calculated.

The method of allocating data streams according to any one of the first to twenty-third aspects of the present application provides the method of twenty-fourth allocating data streams of the first aspect of the present application, wherein in response to allocating streams for IO commands, the dispersion of the streams allocated with IO commands is calculated.

According to a twenty-fourth method of allocating data streams of the first aspect of the present application, there is provided a twenty-fifth method of allocating data streams of the first aspect of the present application, wherein the dispersion of the streams is a dispersion of update parameters of a plurality of data units associated with the streams.

According to a twenty-fourth or twenty-fifth method of allocating data streams of the first aspect of the present application, there is provided a twenty-sixth method of allocating data streams of the first aspect of the present application, wherein the dispersion of the streams is a dispersion of update parameters of the streams.

According to a twenty-fourth or twenty-fifth method of allocating data streams of the first aspect of the present application, there is provided a twenty-seventh method of allocating data streams of the first aspect of the present application, wherein the dispersion of the streams is a ratio of a dispersion of update parameters of the streams to an update time interval of the streams.

The method of allocating data streams according to any of the twenty-fourth to twenty-seventh aspects of the present application provides the method of twenty-eighth allocation of data streams of the first aspect of the present application, wherein the streams are split and/or combined according to a dispersion.

According to a twenty-eighth method of allocating data streams of the first aspect of the present application, there is provided a twenty-ninth method of allocating data streams of the first aspect of the present application, wherein two new update parameters are generated according to update parameters of a stream to split the stream into two streams.

According to a twenty-ninth method of allocating data streams of the first aspect of the present application, there is provided the thirty-first method of allocating data streams of the first aspect of the present application, wherein the average or statistical value of the update parameters of the two streams is the same as the update parameters of the stream before splitting, and one of the update parameters of the two streams is larger than the other.

The method of allocating data streams according to any of the twenty-fourth to thirty-first aspects of the present application provides the method of allocating data streams of the thirty-first aspect of the present application, wherein the first stream is split into the first stream and the second stream in response to the first stream dispersion being greater than a threshold or an increase in the first stream dispersion being greater than a threshold.

According to a thirty-fourth method of allocating data streams of the first aspect of the present application, there is provided the thirty-first method of allocating data streams of the first aspect of the present application, wherein the specified portion of the dispersion of the first stream is taken as the dispersion of the split first stream and the second stream.

According to a thirty-first method of allocating data streams of the first aspect of the present application, there is provided a thirty-third method of allocating data streams of the first aspect of the present application, wherein the dispersion of the first stream after splitting is one half of the dispersion of the first stream before splitting.

The method for allocating data streams according to any one of twenty-fourth to thirty-fourth of the first aspect of the present application provides the method for allocating data streams according to the thirty-fourth of the first aspect of the present application, wherein the plurality of streams are ordered according to update time intervals or update parameters, the dispersion after the merging of two or more adjacent streams is calculated, and the two or more streams whose dispersion is smaller than a specified threshold are merged.

The method of allocating data streams according to any one of the tenth to thirty-fourth aspects of the present application provides the method of thirty-fifth allocating data streams of the first aspect of the present application, wherein in response to allocating streams for IO commands, an update time interval of the streams to which the IO commands are allocated is calculated.

According to a thirty-fourth method of allocating data streams of the first aspect of the present application, there is provided a thirty-sixth method of allocating data streams of the first aspect of the present application, wherein the plurality of update time intervals of the streams are low-pass filtered.

The method of allocating data streams according to any of the thirty-fifth to thirty-sixth aspects of the present application provides the method of thirty-seventh allocating data streams of the first aspect of the present application, wherein the streams are split and/or combined by updating the time interval.

According to a thirty-seventh method of allocating data streams of the first aspect of the present application, there is provided a thirty-eighth method of allocating data streams of the first aspect of the present application, wherein two or more streams whose update time intervals are greater than a specified threshold are combined.

The method for allocating data streams according to any one of thirty-fifth to thirty-eighth of the first aspect of the present application provides the method for thirty-ninth of the first aspect of the present application, wherein an update time interval of a stream is taken as an update time interval of each stream after splitting.

The method for allocating data streams according to any one of twenty-eighth to thirty-eighth of the first aspect of the present application provides the method for fortieth of the first aspect of the present application, wherein an average value or a statistical value of update parameters of the two or more streams that are combined is taken as the update parameter of the stream after the combination.

According to a second aspect of the present application there is provided a first storage device according to the second aspect of the present application comprising a control unit and a non-volatile storage medium, the control unit performing the method of allocating data streams of any of the first to forty aspects.

According to a third aspect of the present application, there is provided a first method of allocating streams for IO commands according to the third aspect of the present application, comprising: acquiring an IO command; acquiring a first update parameter according to the IO command; and distributing the first stream for the IO command according to the first update parameter.

According to a first method for allocating a stream to an IO command according to a third aspect of the present application, there is provided a second method for allocating a stream to an IO command according to the third aspect of the present application, wherein the first update parameter is an update parameter of a data unit accessed by the IO command, and the data unit is an address space having a specified size.

According to a first or second method for allocating streams for IO commands in the third aspect of the present application, there is provided a third method for allocating streams for IO commands in the third aspect of the present application, wherein the IO commands are write commands.

According to a second or third method of allocating streams for IO commands according to the third aspect of the present application, there is provided a fourth method of allocating streams for IO commands according to the third aspect of the present application, wherein the update parameter of the data unit is an update time interval or an average of update time intervals of the data unit.

According to the first to fourth methods for allocating streams for IO commands in the third aspect of the present application, there is provided a fifth method for allocating streams for IO commands in the third aspect of the present application, further comprising: in response to acquiring the IO command, update parameters of the data units accessed by the IO command are also calculated.

A fifth method for allocating a stream to an IO command according to a third aspect of the present application provides the method for allocating a stream to an IO command according to the sixth aspect of the present application, wherein an update parameter of a data unit is calculated according to g '= (1-k) ×g+k× (dt), where g' is a calculated update parameter, g is a pre-calculation update parameter, 0< k <1.

A fifth method for allocating streams for IO commands according to the third aspect of the present application provides a seventh method for allocating streams for IO commands according to the third aspect of the present application, wherein according to the formula

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating update parameters for data unitsWhere α is a positive number much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0 and tc is the update time interval of the data unit.

A fifth method for allocating streams for IO commands according to the third aspect of the present application provides the eighth method for allocating streams for IO commands according to the third aspect of the present application, wherein according to the formula

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating update parameters for data unitsWhere α and β are positive numbers much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0, tc is the update time interval of data units, and n is the number of data units accessed by the IO command.

According to a second or third method for allocating streams for IO commands of the third aspect of the present application, there is provided a ninth method for allocating streams for IO commands of the third aspect of the present application, wherein the parameters of the data units include a time interval parameterCorrelation parametersTime interval parameterIs the update time interval of the data unit or the average value of the update time interval; correlation parametersIndicating the likelihood that the data unit will be accessed again.

A ninth method for allocating a stream to an IO command according to the third aspect of the present application provides the tenth method for allocating a stream to an IO command according to the third aspect of the present application, wherein according to the formula

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating time interval parametersCorrelation parametersWhere α and β are positive numbers much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0, tc is the update time interval of the data unit, and Δ represents the correlation threshold.

A ninth method for allocating a stream to an IO command according to the third aspect of the present application provides the eleventh method for allocating a stream to an IO command according to the third aspect of the present application, wherein according to the formula

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating time interval parametersCorrelation parametersWhere α and β are positive numbers much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0, tc is the update time interval of the data units, Δ represents the correlation threshold, and n is the number of data units accessed by the IO command.

According to one of the first to eleventh methods of allocating streams for IO commands according to the third aspect of the present application, there is provided the twelfth method of allocating streams for IO commands according to the third aspect of the present application, wherein a difference between an update parameter of the first stream and the first update parameter is smaller than a threshold value.

According to one of the first to eleventh methods of allocating streams for IO commands according to the third aspect of the present application, there is provided the thirteenth method of allocating streams for IO commands according to the third aspect of the present application, wherein the update parameters of the first stream have a smallest difference from the update parameters of the first update parameters compared to the update parameters of the other streams.

According to one of the first to thirteenth methods of allocating streams for IO commands according to the third aspect of the present application, there is provided the method of allocating streams for IO commands according to the fourteenth aspect of the present application, wherein a difference between an update parameter of any stream and the first update parameter is greater than a threshold value.

According to one of the first to eleventh methods of allocating streams for IO commands according to the third aspect of the present application, there is provided a method of allocating streams for IO commands according to the fifteenth aspect of the present application, wherein the first update parameter is allocated to the first stream using a clustering method.

According to one of the methods of allocating streams for IO commands according to the twelfth to fifteenth aspects of the present application, there is provided the method of allocating streams for IO commands according to the sixteenth aspect of the present application, wherein the update parameter of the first stream is an average, median or mode value of the update parameters allocated to the data units of the first stream.

According to one of the first to eleventh methods of allocating streams for IO commands of the third aspect of the present application, there is provided a seventeenth method of allocating streams for IO commands of the third aspect of the present application, wherein the update parameters of the streams include time interval parametersAnd relative error parameterTime interval parameterIs the time interval or average of the stream being updated, and the relative error parameterIs the sum or sum of squares of the differences of the median values of the respective time intervals in which the stream is updated.

One of the methods of allocating streams for IO commands according to the first through eleventh aspects of the present application provides the method of allocating streams for IO commands according to the eighteenth aspect of the present application, wherein

Update parameters of a stream with respect to parameters including time intervalsRelative error parameterAnd median parameterAccording to the formula

Calculating time interval parametersRelative error parameterAnd median parameterWhere y is a positive number much smaller than 1, ts is the time interval during which the stream is updated,Is the time interval parameter of the data units allocated to the stream.

According to one of the first to eleventh methods of allocating streams for IO commands of the third aspect of the present application, there is provided a nineteenth method of allocating streams for IO commands of the third aspect of the present application, wherein the update parameters of the streams include time interval parametersRelative error parameterAnd median parameterAccording to the formula

Calculating time interval parametersRelative error parameterAnd median parameterWhere y is a positive number much smaller than 1, ts is the time interval during which the stream is updated,Is the time interval parameter assigned to the data units of the stream and n is the number of data units accessed by the IO command.

According to one of the sixteenth to nineteenth methods of allocating streams for IO commands in the third aspect of the present application, there is provided the twentieth method of allocating streams for IO commands in the third aspect of the present application, further comprising: in response to assigning the first stream to the IO command, update parameters for the first stream are also calculated.

A method for allocating streams for IO commands according to an eighteenth or nineteenth aspect of the present application provides a method for allocating streams for IO commands according to a twenty-first aspect of the present application, wherein according to the formula

A first stream is obtained, where s represents the first stream.

According to one of the first to twenty-first methods of allocating streams for IO commands according to the third aspect of the present application, there is provided a twenty-second method of allocating streams for IO commands according to the third aspect of the present application, wherein the streams to be allocated include streams from the first group and streams from the second group.

A twenty-third method of allocating streams for IO commands according to the third aspect of the present application provides a twenty-third method of allocating streams for IO commands according to the third aspect of the present application, wherein the first stream is from the first group.

A twenty-second or twenty-third method of allocating streams for IO commands according to the third aspect of the present application is provided, wherein the streams from the second group are allocated for data generated by garbage collection or wear leveling.

A twenty-third aspect of the present application provides a method for allocating streams to IO commands, wherein if the correlation parameters of the data units areAbove a specified correlation threshold, a first stream assigned to the IO command is selected from the first set.

A twenty-fifth method for distributing streams for IO commands according to the third aspect of the present application provides the twenty-sixth method for distributing streams for IO commands according to the third aspect of the present application, wherein if the correlation parameters of the data units areNo greater than a specified correlation threshold, a first stream assigned to the IO command is selected from the second set.

According to one of the first to twenty-fifth methods of allocating streams for IO commands according to the third aspect of the present application, there is provided a twenty-seventh method of allocating streams for IO commands according to the third aspect of the present application, wherein the streams are bound to NVM groups, the NVM groups being partitions of storage resources of a storage device to which the IO commands access.

According to one of the first to twenty-seventh methods of allocating streams for IO commands in the third aspect of the present application, there is provided a twenty-eighth method of allocating streams for IO commands in the third aspect of the present application, further comprising: the dispersion of the first stream is calculated and the first stream is split according to the dispersion of the first stream.

A twenty-eighth method of allocating streams for IO commands according to the third aspect of the present application provides the twenty-ninth method of allocating streams for IO commands according to the third aspect of the present application, wherein the dispersion of streams is a dispersion of update parameters of streams.

A twenty-eighth or twenty-ninth method of allocating streams for IO commands according to the third aspect of the present application provides the thirty-first method of allocating streams for IO commands according to the third aspect of the present application, wherein the dispersion of the streams is a time interval parameter of the streamsIs a dispersion of (2).

A twenty-eighth or twenty-ninth method of allocating streams for IO commands according to the third aspect of the present application provides a method of allocating streams for IO commands according to the thirty-first aspect of the present application, wherein the dispersion of the streams is a relative error parameter of the streams

A twenty-eighth or twenty-ninth method of allocating streams for IO commands according to the third aspect of the present application provides a method of allocating streams for IO commands according to the thirty-eighth aspect of the present application, wherein a dispersion of the streamsWherein the method comprises the steps ofFor time interval parameters of the streamIs the relative error parameter of the stream.

According to one of the twenty eighth to thirty second methods of allocating streams for IO commands of the third aspect of the present application, there is provided a method of allocating streams for IO commands of the thirteenth aspect of the present application, wherein two new sets of update parameters are generated from update parameters of the streams, each new set of updates representing one stream after splitting.

A thirteenth aspect of the present application provides a method for allocating streams to IO commands according to the thirteenth aspect of the present application, wherein an average value or a statistical value of update parameters of two streams is the same as that of a stream before splitting, and one of the update parameters of the two streams is larger than the other.

One of twenty-eighth to thirty-second methods of allocating streams for IO commands according to the third aspect of the present application provides a thirty-fifth method of allocating streams for IO commands according to the third aspect of the present application, wherein according to the formula

Splitting the stream Sp into a stream Sp1 and a stream Sp2, the updated parameters of the stream Sp comprising time interval parametersRelative error parameterAnd median parameterThe updated parameters of the stream Sp1 include time interval parametersRelative error parameterAnd median parameterThe updated parameters of the stream Sp2 include time interval parametersRelative error parameterAnd median parameterEpsilon is a positive number much smaller than 1.

One of the twenty eighth to thirty second methods of allocating streams for IO commands according to the third aspect of the present application provides the thirty-sixth method of allocating streams for IO commands according to the third aspect of the present application, wherein according to the formula

Combining stream Sm1 with stream Sm2 into stream Sm, wherein the updated parameters of stream Sm include time interval parametersRelative error parameterAnd median parameterThe updated parameters of the stream Sm1 include a time interval parameterRelative error parameterAnd median parameterThe updated parameters of the stream Sm2 include a time interval parameterRelative error parameterAnd median parameter

According to one of the twenty eighth to thirty sixth methods of allocating streams for IO commands according to the third aspect of the present application, there is provided a seventeenth method of allocating streams for IO commands according to the third aspect of the present application, wherein the first stream is split in response to the dispersion of the first stream being greater than a specified threshold.

A thirty-fifth or thirty-sixth method for allocating streams to IO commands according to the third aspect of the present application provides a thirty-eighth method for allocating streams to IO commands according to the third aspect of the present application, further comprising: sorting the plurality of streams by median parameter, and for streams Sp and streams Sm1 and Sm2 adjacent to the sorting, if satisfiedGreater than a first threshold orGreater than the second threshold, then splitting stream Sp and/or combining stream Sm1 with stream Sm2, whereinIs the dispersion of the stream SpIs the dispersion of the stream Sm resulting from the combination of the stream Sm1 and the stream Sm 2.

A thirty-eighth method of allocating streams to IO commands according to the third aspect of the present application provides the method of allocating streams to IO commands according to the thirty-ninth aspect of the present application, wherein the stream Sp is split and/or the stream Sm1 and the stream Sm2 are merged periodically or under specified conditions.

A method for allocating streams for IO commands according to a nineteenth aspect of the present application provides the method for allocating streams for IO commands according to the fortieth aspect of the present application, wherein an age of each of the plurality of streams is greater than an age threshold, wherein the age of a stream is a time at which the stream was created, last split of stream, or last merged of stream to the current.

A nineteenth method for allocating a stream to an IO command according to the third aspect of the present application provides the twenty-first method for allocating a stream to an IO command according to the third aspect of the present application, wherein the stream Sp is not split if the age of the stream Sp is not greater than the age threshold; and if the age of any one of the streams Sm1 and Sm2 is not greater than the age threshold, not combining the streams Sm1 and Sm2.

According to one of the thirty-eighth to fortieth methods of allocating streams for IO commands according to the third aspect of the present application, there is provided a forty-second method of allocating streams for IO commands according to the third aspect of the present application, wherein each stream of the plurality of streams is from the first group; or each stream of the plurality of streams is from the second group.

According to a fourth aspect of the present application there is provided a first storage device according to the fourth aspect of the present application comprising a control unit and a non-volatile storage medium, the control unit performing one of the methods of allocating streams for IO commands according to the third aspect of the present application.

According to a fifth aspect of the present application, there is provided the first information processing apparatus according to the fifth aspect of the present application, comprising a processor that executes one of the methods of allocating streams for IO commands according to the third aspect of the present application by running a program.

According to a sixth aspect of the present application there is provided a computer program according to the sixth aspect of the present application comprising computer program code which, when loaded into a computer system and executed thereon, causes the computer system to perform one of the methods of allocating streams for IO commands according to the third aspect of the present application.

According to a seventh aspect of the present application there is provided a program according to the seventh aspect of the present application comprising program code which, when loaded into a storage device and executed on the storage device, causes the storage IO command storage device to perform one of the methods of allocating streams for IO commands according to the third aspect of the present application.

Drawings

In order to more clearly illustrate the embodiments of the present application or the technical solutions in the prior art, the drawings used in the embodiments or the description of the prior art will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments described in the present application, and other drawings may be obtained according to these drawings for a person having ordinary skill in the art.

FIG. 1 is a block diagram of a prior art memory device;

FIG. 2 is a schematic diagram of a prior art chunk;

FIG. 3 is a schematic diagram of a large block of data state changes;

FIG. 4 is a schematic diagram of a split flow provided by an embodiment of the present application;

FIG. 5 is a flow chart of diversion and flow tracking according to an embodiment of the present application;

FIG. 6 is a schematic diagram of a memory system according to an embodiment of the application;

FIG. 7 illustrates a flow chart of diversion and flow tracking in accordance with yet another embodiment of the present application;

FIGS. 8A and 8B are schematic diagrams of flow evolution according to an embodiment of the present application;

FIG. 9 illustrates a flow chart of flow evolution according to an embodiment of the present application; and

Fig. 10 illustrates a flow chart of flow evolution according to yet another embodiment of the present application. .

Detailed Description

The following description of the embodiments of the present application will be made clearly and fully with reference to the accompanying drawings, in which it is evident that the embodiments described are some, but not all embodiments of the application. All other embodiments, which can be made by those skilled in the art based on the embodiments of the application without making any inventive effort, are intended to be within the scope of the application.

FIG. 3 is a schematic diagram of a large block of data state changes.

Fig. 3 shows data on chunk 1 and chunk 2 to which data is written, with invalid data gradually increasing over time. In fig. 3, T1 indicates the earliest time, T2 indicates the subsequent time, and T3 indicates the latest time. The large block of blank squares indicates memory cells to which data is written and which are valid, for example, physical pages or physical blocks of flash memory, and the large block of shaded squares indicates memory cells to which data is written and which become invalid because the data is updated.

As time passes from T1 to T2 and T3, the portions of valid data on chunk 1 and chunk 2 become invalid. And at each instant, chunk 1 and chunk 2 each have an invalid data duty cycle. At time T1, the invalid data duty ratio of chunk 1 is greater than chunk 2, and at time T3, the invalid data duty ratio of chunk 1 is still greater than chunk 2.

At T3, if garbage collection is performed, it is advantageous to choose to collect chunk 1 while not collect chunk 2 at all, because less valid data is stored on chunk 1. And it is desirable to recycle the bulk 2 at a later time.

In order to select smaller chunks of valid data at the time of garbage collection, the time to garbage collect the chunks may be deferred. In some cases, however, the need for storage space on the storage device makes the policy of deferring garbage collection difficult to implement. Also, the valid data on the chunk may have a very large lifecycle, which makes the benefits of deferring garbage collection policies insignificant.

Fig. 4 shows a schematic diagram of a split flow according to an embodiment of the application.

The storage device provides, for example, a contiguous logical address space. The arrow to the right indicates the direction in which the logical address space is incremented. The logical address space is divided into a plurality of data units (410, 411, 412, 413 … …, 418). Each data unit occupies a logical address space of a specified size or fixed size. For example, the size of the data unit is 512 bytes, 4KB, 16KB, 1MB, 2MB, 4MB, or other value.

The data units each have a life cycle. For example, data unit 410 is updated substantially once a day with a lifecycle of 1 day; the data unit 411 is updated substantially 1 time per month with a lifecycle of 1 month; the data unit 412 is updated substantially once an hour with a life cycle of 1 hour; the data unit 415 is updated substantially once a year with a life cycle of 1 year.

FTL tables of the storage device map addresses of the logical address space to physical addresses of the storage medium. In response to a data unit of the logical address space being updated, a new physical address is allocated for the data unit to carry updated data such that the data at the old physical address becomes dirty.

The data units of the logical address space are allocated into a plurality of streams according to their lifecycle. According to an embodiment of the application, data units having the same or similar lifecycle are allocated to the same flow. While different data units with a larger difference in lifecycle are allocated to different flows. For example, referring to FIG. 4, data unit 410, data unit 414, and data unit 418 are all 1 day in life, and these data units are assigned to flow S1; the lifecycle of data unit 411 and data unit 413 are close (1 month and 1 week, respectively) and assigned to stream S3; and assigning data unit 412 and data unit 416 to stream S2; data unit 415 is assigned to stream Sn. Optionally, other data units not suitable for allocation to stream S1, stream S2 or S3 are also allocated to stream Sn.

In an alternative embodiment, the stream has a standard lifecycle. For example, the standard lifecycle of stream S1 is, for example, 1 day, whereas data units with lifecycles of 0.5 to 5 days are allocated to stream S1.

Still alternatively or further, the standard lifecycle and/or lifecycle range of the stream is adjusted to accommodate changes in the lifecycle of the data units. For example, the standard lifecycle of a flow is updated with the mean, median, or other statistical value of the lifecycles of the data units assigned to the flow.

Alternatively, the historical two-time updated time interval of the data unit, or the average of the multiple-time updated time intervals, is used as the updated parameter of the data unit to replace the life cycle. And allocating the data units to the streams according to the update parameters of the data units. Still alternatively, the time intervals of the history of the data unit that are updated a plurality of times are weighted averaged, or the result of the low pass filtering is used as the update parameter of the data unit.

Alternatively or in addition, the update parameters of the stream are calculated from the update parameters of a plurality or all of the data units allocated to the stream, instead of the standard lifecycle of the stream. For example, the mean, median, or mode of the update parameters assigned to multiple or all data units of a stream are used as the update parameters for the stream. Still alternatively, the update parameters assigned to multiple or all data units of the stream are weighted averaged, or the result of the low pass filtering is used as the update parameters of the stream.

According to an embodiment of the application, the stream is dynamic. In some cases, data units originally allocated as one stream are changed to be allocated to another stream; in still other cases, a single stream is split into multiple streams; in other cases, two or more streams are combined into a single stream. Thus representing a change in the way the data unit is accessed. For example, a document being edited has a very short lifecycle of its data elements; and when a document is created, its data unit lifecycle will become long. As the lifecycle of a data unit changes significantly, the flow allocated to the data unit changes as well. As yet another example, the update parameters of the streams exhibit greater volatility, while the streams are split into two or more streams such that the volatility of the update parameters of the respective streams is reduced.

Still alternatively, the lifecycle of some data units is difficult to identify, and the data units for which the lifecycle is difficult to identify are all assigned to the specified data stream.

In the example of fig. 4, the logical address space provided by the storage device is allocated as a plurality of data units. In an alternative embodiment, the open channel storage device provides a physical address space, while an application at a host accessing the storage device accesses a logical address space and completes the mapping from logical addresses to physical addresses in the host. Also in the host, the logical address space is allocated as a plurality of data units, and the host counts the update parameters of each data unit, allocates the data units to the streams, and calculates the update parameters of the data units and the update parameters of the streams.

Still alternatively, the data units are allocated on other address spaces. The other address space is a physical address or an intermediate address to be mapped to a physical address. Other address space data units can be updated. An update parameter is calculated for each data unit to assign the data unit to a flow, and the update parameter of the flow is calculated.

Fig. 5 is a flow chart of splitting and flow tracking according to an embodiment of the application.

A stream is allocated for a data unit and also for an IO command to write data to a data unit.

Taking a storage device as an example, an IO command (510) is received from a host or other device, the IO command indicating, for example, a logical address to which data is to be written, the logical address corresponding to one or more data units on a logical address space. For simplicity, the IO command accesses a single data unit (denoted DU 1), by way of example.

The update parameters are acquired for the data unit DU1 accessed by the IO command (520). The update parameter indicates a statistical property of the data unit, such as a lifecycle, or a time at which the update is expected. As an example, the IO command carries an update parameter, and the update parameter carried by the IO command is used as an update parameter of a data unit accessed by the IO command. As a further example, the time it was updated before or last is recorded for each data unit, and the update parameter is taken or calculated from the difference between the current time and the time it was updated before or last. As yet another example, a time interval according to which it was updated one or more times before is recorded for each data unit, and an average, median, crowd value or other statistical value according to one or more of the updated time intervals is used as an update parameter. In yet another example, the time it was updated before or last time is recorded for each data unit, and an update parameter is recorded, and a new update parameter is calculated from the difference dt of the current time and the time it was updated before or last time, and the recorded update parameter g, e.g., g '= (1-k) g+k (dt), where g' is the calculated new update parameter, 0< k <1.

The resulting update parameters for the data units are compared to the update parameters for the same one or more streams to allocate streams for the data units (530). It will be appreciated that the allocation flow for data units is also considered as the IO command allocation flow for accessing data units. For example, a stream having stream update parameters closest to its update parameters is allocated to the data unit. As yet another example, a K-means clustering method or other clustering method is applied to assign streams to data units, where the streams represent categories of data units, with updated parameters of the data units as features for clustering.

As yet another example, if there is no flow, or no flow has update parameters close enough to those of the data units accessed by the IO command, a new flow is created and the data units are assigned to the newly created flow. As yet another example, the update parameters of no stream are close enough to the update parameters of a data unit accessed by an IO command to assign the data unit to a specified stream. The flows are represented by, for example, flow identifiers, which are assigned to data units, e.g., by attaching flow identifiers to data of updated data units, or by attaching flow identifiers to IO commands.

Optionally, as data units are allocated to a flow, the update parameters for that flow are also recalculated (540). As an example, an average, median, crowd value or other statistical value of the update parameters assigned to one, more or all data units of the stream is taken as the update parameter of the stream. As yet another example, the update parameters for each stream are recorded, and in response to assigning a stream to a new data unit, new update parameters for the stream are calculated using the new update parameters for the new data unit and the current update parameters for the stream. Still by way of example, the new update parameter of the stream is a weighted sum of the current update parameter of the stream and the update parameter of the new data unit. Alternatively or in addition, in response to receiving an IO command to access a data unit, update parameters for the data unit are also recalculated.

FIG. 6 is a schematic diagram of a memory system according to an embodiment of the application.

The host is coupled to a storage device that implements flow tracking and/or flow evolution techniques. The host provides IO commands to the storage device to access the storage device. The memory device includes a control component 620 and one or more NVM chips (610). One or more NVM chips (610) are divided into multiple NVM groups. An NVM group is a partition of storage resources provided by a storage device. By way of example, the NVM chips of each NVM group are isolated from each other. Optionally, the NVM groups are partitioned by Logical Units (LUNs), each NVM group including one or more logical units. The NVM group includes a plurality of data frames, which are, for example, 512 bytes, 2KB, 4KB, 8KB in size of memory.

According to an embodiment of the application, a stream is bound to an NVM group. So that data of an IO command accessing a data unit with the same stream identifier is written to the same NVM group. Referring to fig. 6, the IO command processing unit 630 of the control unit 620 receives an IO command from the host, obtains a flow identifier allocated to the IO command (or a data unit accessed for the IO command) from the flow tracking unit 634, and determines to write the data of the IO command to one of the NVM groups according to the flow identifier. For example, data of the IO command with stream identifier S0 is written to NVM group 0; writing data of the IO command with the stream identifier S1 to NVM group 1; while data of IO commands with other stream identifiers is written to NVM group 2.

Alternatively or in addition, valid data that is moved by garbage collection unit 636 during garbage collection is assigned a special stream tag, such as Sg, and these data are written to NVM group 3.NVM group 3 is dedicated to carrying valid data from garbage collection unit 636, but not carrying data to be written by IO commands from the host.

Still alternatively or further, the flow identifier generated by the flow tracking unit 634 is further grouped. For example, streams identified based on access correlation or sequence are divided into groups Gs, while other streams are divided into groups Gn. IO command processing unit 630 writes data belonging to different groups of streams into different NVM groups; and optionally, data of one or more streams belonging to the same group can be written to the same NVM group.

Still alternatively, the valid data generated by the garbage collection unit 636 is identified as a garbage collection stream and a wear leveling stream, respectively, depending on its source. Different NVM groups are allocated for data belonging to garbage collection flows or to wear leveling flows. The data belonging to the garbage collection flow comes from a garbage collection process with the aim of freeing up the storage resources, while the data belonging to the wear-leveling flow comes from a wear-leveling process with the aim of balancing or counter-balancing the wear level of the storage resources.

According to a further embodiment of the application, the update parameters of the data unit comprise two or more parameters. For example, the update parameters of the data units include time interval parametersCorrelation parameters

In one example, the time interval parameter is the mean of the update time intervals Tc of the data units. The access correlation parameter is the mean of the variable ind, which is 1 when the update time interval Tc is less than or equal to the correlation threshold Δ, and 0 when the update time interval Tc is greater than the correlation threshold Δ. And the correlation threshold is, for example, 64 in units of the number of IO commands, the product of the number of IO commands and the size of the IO commands in units of the number of data frames, or time in units of microseconds.

In yet another example, in response to each processing of an IO command, a time interval parameter of a data unit accessed by the IO command is calculated according to the following equation (1)Correlation parameters

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Where α and β are positive numbers much smaller than 1, respectively, ρ ₀ takes 0.00001 to 1, for example 0.001.g _c has an initial value of 0; ρ=ρ ₀·1_d>0+1_d≤0 represents ρ ₀ when d is greater than 0, and ρ1 when d is less than 0; delta represents the correlation threshold value and,Representing taking when Tc is less than or equal to the correlation thresholdAnd when Tc is greater than the correlation threshold

In another example, in response to each processing of an IO command, a time interval parameter of a data unit accessed by the IO command is calculated according to equation (2) belowCorrelation parameters

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Where α and β are positive numbers much smaller than 1, respectively, ρ ₀ takes 0.00001 to 1, for example 0.001.g _c has an initial value of 0; ρ=ρ ₀·1_d>0+1_d≤0 represents ρ ₀ when d is greater than 0, and ρ1 when d is less than 0; delta represents the correlation threshold value and,Representing taking when Tc is less than or equal to the correlation thresholdAnd when Tc is greater than the correlation thresholdEquation (2) also considers the size of the IO command (denoted as n, in terms of, for example, the number of data frames or data units accessed by the IO command). For IO commands accessing two or more data units, for each data unit it accesses, a time interval parameter is calculated according to equation (2)Correlation parameters

Further, according to an embodiment of the application, the update parameters of the stream comprise two or more parameters.

In one example, the stream update parameters include time interval parametersAnd relative error parameterTime interval parameterIs the mean value of the time interval Ts during which the stream is updated, and the relative error parameterIs the sum or sum of squares of the differences of the median values of the respective time intervals Ts of the stream being updated.

(Mode 1) in yet another example, the stream update parameter includes a time interval parameterRelative error parameterAnd median parameterIn response to each allocation of a stream for IO commands, time interval parameters for update parameters for the stream are calculated according to equation (3) belowRelative error parameterAnd median parameter

Where gamma is a positive number much smaller than 1, ts is the time interval during which the stream is updated,Is the time interval parameter of all data units allocated to the current streamOr center of mass of (c).

(Mode 2) in another example, the stream update parameters include time interval parametersRelative error parameterAnd median parameterIn response to each allocation of a stream for an IO command, a time interval parameter is calculated according to equation (4) belowRelative error parameterAnd median parameter

Where γ is a positive number much smaller than 1 and Ts is the time interval during which the stream is updated. Equation (4) also considers the size of the IO command (denoted as n, in terms of, for example, the number of data frames or data units accessed by the IO command).

Fig. 7 illustrates a flow chart of splitting and flow tracking according to yet another embodiment of the application.

The storage device receives an IO command from a host or other device (710).

Update parameters of data units accessed by the IO command are obtained (720). For example, the update parameters of each data unit are recorded in the update parameter table of the data unit. The update parameters of the data units include, for example, time interval parametersCorrelation parametersAnd acquiring the update parameters of the data unit from the update parameter table according to the data unit accessed by the IO command.

Comparing correlation parameters of data unitsAnd a threshold value Q (730), if the correlation parameterGreater than a threshold value Q, assigning IO commands or data units accessed by IO commands to streams selected from the group Gs (740); if the correlation parameterNot greater than the threshold Q, the IO command or the data unit accessed by the IO command is assigned to a stream selected from the group Gn (745). Optionally, the group Gs includes a specified one or more flow identifiers and Gn includes a specified one or more flow identifiers. Still alternatively, the streams in the group Gs are streams identified based on access correlation or sequence, and the streams in the group Gn are other streams than the streams in the group Gs.

For example, to assign an IO command to a stream selected from group G (e.g., gn or Gs), a stream is selected from group G whose stream update parameters are closest to the update parameters of the data units accessed by the IO command, and assigned to the IO command. As yet another example, in group G, the time interval parameters of data units accessed according to IO commandsMedian parameters to streams in group GAssigning IO commands to streams s using the k-means clustering (k=1) algorithm of equation (5), wherein

Referring back to FIG. 7, new update parameters are calculated for the data units accessed by the IO command (750). The method of calculating the update parameters of the data units is described above. New update parameters are also calculated 760 for the stream S assigned to the IO command in step 740 or step 745. The method of calculating the update parameters of the stream is also described above.

Fig. 8A and 8B are schematic diagrams of flow evolution according to an embodiment of the present application.

In fig. 8A and 8B, the coordinate axes represent update parameters. For descriptive purposes, the update parameters of the coordinate axes represent both the update parameters of the data units and the update parameters of the streams. The update parameters of the data units may be directly compared with the update parameters of the stream. For example, the update parameter of the data unit is a time interval parameterThe update parameter of the stream is a median parameterIn some cases, the update parameters of the stream are calculated from the update parameters of the data unit, but the update parameters of the stream may still be directly compared with the update parameters of the data unit.

Referring to fig. 8A, there are already two streams, stream S1 and stream S2. The rectangular boxes where streams S1 and S2 reside represent updated parameters for the streams. For example, the start point or the middle point of the coordinate axis covered by the rectangular frame is used as the update parameter of the stream. Data units whose update parameters fall within the range covered by the rectangular box will be assigned to the stream represented by the rectangular box. The circle on the coordinate axis represents the data unit and the position of the circle on the coordinate axis represents the update parameter of the data unit. The data units represented by circles within the rectangular box are thus allocated to the streams represented by the rectangular boxes.

With continued reference to FIG. 8A, within the rectangular box in which stream S1 is located, the plurality of data units have been formed into three groups (CG 1, CG2, and CG 3) according to their update parameters. Within the rectangular box in which stream S2 is located, a plurality of data units have been formed into 2 groups (CG 4 and CG 5) according to their update parameters. Wherein the data cell group CG3 and the data cell group CG4 are adjacent to each other. While data cell group CG4 is farther away from data cell group CG 5.

According to an embodiment of the present application, stream S1 and stream S2 are split to obtain new stream S1', stream S2' and stream S3. The new flow S1' accommodates data unit group CG1 and data unit group CG2; the new stream S2' accommodates data unit group CG3 and data unit group CG4, and stream S3 accommodates data unit group CG5, as shown in fig. 8B.

Optionally, two or more streams are also merged, the merged stream containing all data units participating in the merged stream.

By way of example, streams are split or merged by changing their updated parameters. For example, referring to FIG. 8A, the location of the midpoint of a rectangular box representing a stream on a coordinate axis indicates the update parameters of the stream. Streams are split or merged by changing or creating updated parameters for the streams.

Although fig. 8A and 8B illustrate that the rectangular box corresponding to the stream accommodates a plurality of data units. Alternatively, in response to a change in a flow (e.g., splitting or merging), data units already allocated to the flow need not be reattached to a new flow identifier, but instead for a newly received IO command, the changed flow is allocated for the IO command according to the data units it accesses.

Referring also to fig. 8A, alternatively, the update parameters of the stream may be varied. For example, in response to more data units whose update parameters are adjacent to the data unit group CG3 being assigned to the stream S1, the update parameters of the stream S1 are increased such that the rectangular frame to which the stream S1 corresponds is shifted right on the coordinate axis.

In the examples of fig. 8A and 8B, splitting or merging streams according to the dispersion of updated parameters is illustrated. The dispersion of the update parameters of the stream, representing the degree of deviation of the update parameters of the data units allocated to the stream from the update parameters of the stream, e.g. the sum of the differences of the update parameters of the data units and the update parameters of the stream, the weighted sum of the differences of the update parameters of the data units and the update parameters of the stream, the sum of the squares of the differences of the update parameters of the data units and the update parameters of the stream, the relative error parameters of the stream each time a data unit is allocated to the streamOr statistics of differences between the update parameters of the data units and the update parameters of the stream, etc. Still alternatively, the streams are also combined according to their update time intervals. The update of any data unit allocated to a stream is treated as an update to the stream. For two or more streams with larger (e.g., greater than a specified threshold) update time intervals, it is advantageous to merge them into the same stream.

Fig. 9 illustrates a flow chart of flow evolution according to an embodiment of the present application.

According to an embodiment of the application, the identification of the streams is dynamic. After initialization, an initial stream is provided and IO commands for accessing any data units are assigned to the initial stream (910). The initial stream has initial stream update parameters.

The storage device receives an IO command (920). Update parameters are calculated for data units accessed by the IO command (930).

According to the updated parameters of the data unit obtained, a stream is allocated (940) for IO commands accessing the data unit.

Optionally, if the IO command accesses a plurality of data units, the IO command is allocated to the stream according to an update parameter of one of the data units accessed by the IO command. And updating the update parameters of each data unit accessed by the IO command.

The update parameters of the data units are recalculated, and the update parameters of the streams allocated for the IO commands are recalculated (950).

In response to assigning data units to the flow, periodically, or when necessary, a dispersion of the updated flow is obtained (960). Alternatively, the dispersion of the update parameters of the stream is used as the dispersion of the stream. Still alternatively, the ratio of the dispersion of the update parameters of the stream to the update time interval of the stream is used as the dispersion of the stream.

The streams are split and/or combined according to the dispersion of the streams (970). A stream is created by creating new one or more stream update parameters from the stream update parameters. For example, a stream is split into two streams by generating two update parameters from the update parameters of the stream, where the average or statistical value of the new two update parameters is the original update parameter and one of the new update parameters is larger than the other new update parameter. Also by way of example, a specified portion (e.g., 1/2) of the dispersion according to the stream is taken as the dispersion of each stream after splitting. The update time interval of the stream is taken as the update time interval of each split stream.

Similarly, streams are combined by generating update parameters for a new single stream based on update parameters for two or more streams. For example, an average or statistical value of update parameters of two or more streams to be combined is used as the update parameter of the combined stream.

Alternatively, for a single stream, the stream is split in response to its dispersion being too large or increasing rapidly. For multiple streams, the streams are combined in response to having less dispersion if they are combined. Still alternatively, the medium parameters are set for a plurality of streamsSorting, calculating the dispersion after combining two or more adjacent streams, and combining the two or more streams corresponding to the calculation result with the dispersion of the minimum or less than the specified threshold.

Thus, during operation of the storage device, changes in the IO command to the stream are tracked by updating parameters of the stream such that the same stream identifier is appended for data units having the same or similar lifecycle.

According to yet another embodiment of the application, the dispersion of the streamsWherein the method comprises the steps ofFor time interval parameters of the streamIs the relative error parameter of the stream. To split the stream Sp into the stream Sp1 and the stream Sp2, the updated parameters of each of the split stream Sp1 and stream Sp2 are calculated using formula (6).

Where ε is a positive number much smaller than 1.

To combine stream Sm1 and stream Sm2 into stream Sm, the update parameters of the combined stream Sm are calculated using equation (7).

Responsive to allocation of data units to a stream, periodically, relative error parameters of the streamRelative error parameter of greater than threshold value, streamThe derivative with respect to time being greater than a threshold value or, if necessary, with respect to the flows within the group Gs or the flow Gc, according to a median parameterSort, and calculate the dispersion η _s of the flow.

If stream Sp is found and streams Sm1 and Sm2 are adjacent in order, it satisfiesOr alternatively Then stream Sp is split according to equation (6) and/or stream Sm1 is combined with stream Sm2 according to equation (7). Wherein θ1 is a positive number, and θ2 is greater than 1.

Further, an age parameter is recorded for each stream. The age parameter of a stream is the time to which the stream was created, split or merged. In merging streams and/or splitting streams, merging and/or splitting is performed only for streams whose age parameter is greater than an age threshold. Avoiding that the just split streams are combined again or that the just combined streams are split again.

Fig. 10 illustrates a flow chart of flow evolution according to yet another embodiment of the present application.

In response to allocation of data units to flows, periodically or if necessary, for flows within the respective flow group (flow group Gs or flow Gc), as per median parametersOrdering (1010).

The two streams Sm1 and Sm2 adjacent to each other are arbitrarily selected and sequenced, and the dispersion η _sm of the streams Sm after being combined is calculated (1020). The stream Sp is arbitrarily selected and its dispersion η _sp is calculated (1030). Alternatively, at each of steps 1020 and 1030, two streams Sm1 and Sm2, and stream Sp, adjacent to each other in the order specified, are selected.

The dispersion η _sm of the stream Sm is compared with the dispersion η _sp of the stream Sp to determine whether to split the stream Sp and/or whether to combine the streams Sm1 and Sm2 (1040). For example, if stream Sp is found and streams Sm1 and Sm2 are ranked adjacent, it satisfiesOr alternativelyThen stream Sp is split according to equation (6) and/or stream Sm1 is combined with stream Sm2 according to equation (7) (1050). Wherein θ1 is a positive number, and θ2 is greater than 1.

If, at step 1040, it is determined that neither stream Sp nor streams Sm1 and Sm2 are split, the process returns to step 1020.

Further, the storage device also places the data units belonging to the same stream on the same or adjacent physical blocks or big blocks, so that when garbage is recovered, the physical blocks or big blocks to be recovered are reasonably selected to reduce write amplification and improve the performance of the storage device.

In one set of experiments, 8 streams are provided for IO commands of a host, where group Gc includes 6 streams and group Gs includes 2 streams. The host's IO commands come from a simulated workload that divides the storage space of the storage device into 4 different sized regions, or 16 different sized regions, and cyclically writes data to each region. The results show that the flow tracking and flow evolution method of the embodiments of fig. 7 and 10 of the present application is applied with a 70% reduction in write amplification compared to existing storage devices.

In another set of experiments, the host's IO command comes from 1 instance or 4 instances of MySQL data running on the host. The results show that the write amplification is reduced by 23% and 15% respectively compared to existing memory devices, applying the flow tracking and flow evolution methods of the embodiments of fig. 7 and 10 of the present application.

While preferred embodiments of the present application have been described, additional variations and modifications in those embodiments may occur to those skilled in the art once they learn of the basic inventive concepts. It is therefore intended that the following claims be interpreted as including the preferred embodiments and all such alterations and modifications as fall within the scope of the application. It will be apparent to those skilled in the art that various modifications and variations can be made to the present application without departing from the spirit or scope of the application. Thus, it is intended that the present application also include such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof.

Claims

1. A method of assigning streams to IO commands, comprising:

acquiring an IO command;

acquiring a first update parameter according to the IO command; and

Distributing a first stream for the IO command according to the first update parameter;

wherein the first update parameter is an update parameter of a data unit accessed by the IO command, and the data unit is an address space having a specified size;

the method further comprises the following steps:

in response to acquiring the IO command, further calculating an update parameter of the data unit accessed by the IO command, wherein the update parameter of the data unit at least comprises two parameters of a time interval parameter and a correlation parameter, and the time interval parameter is an update time interval or an average value of the update time intervals of the data unit; the dependency parameter indicates the likelihood that the data unit will be accessed again.

2. The method of claim 1, wherein the IO command is a write command.

3. The method according to claim 1, wherein the update parameter of the data unit is calculated according to g '= (1-k) xg+k (dt), where g' is the calculated update parameter, g is the update parameter before calculation, 0< k <1.

4. The method of claim 1, wherein

According to the formula

ρ＝ρ₀·1_d＞0+1_d≤0

g_c＝1-ρd

Calculating update parameters for data unitsWhere α is a positive number much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0, and t _c is the update time interval of the data unit.

5. The method of claim 1, wherein the formula is based on

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

6. The method of claim 1, wherein the formula is based on

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating time interval parametersCorrelation parametersWhere α and β are positive numbers much smaller than 1, 0< ρ ₀<1,g_c has an initial value of 0, tc is the update time interval of the data unit, and Δ represents the correlation threshold; Representing taking when Tc is less than or equal to the correlation threshold And when Tc is greater than the correlation threshold

7. The method of claim 1, wherein the formula is based on

ρ＝ρ₀·1_d>0+1_d≤0

g_c＝1-ρd

Calculating time interval parametersCorrelation parametersWherein alpha and beta are positive numbers far smaller than 1, the initial value of 0< ρ ₀<1,g_c is 0, tc is the updating time interval of the data units, delta represents the correlation threshold, and n is the number of the data units accessed by IO commands; Representing taking when Tc is less than or equal to the correlation threshold And when Tc is greater than the correlation threshold

8. The method of claim 1, wherein a difference between the update parameter of the first stream and the first update parameter is less than a threshold.

9. The method of claim 1, wherein the update parameters of the first stream differ from the update parameters of the other streams by a minimum.

10. The method of claim 1, wherein a difference between the update parameter of any stream and the first update parameter is greater than a threshold.

11. The method of claim 1, wherein the first update parameter is assigned to the first stream using a clustering method.

12. The method according to one of claims 8 to 11, wherein the update parameter of the first stream is an average, a median or a mode of the update parameters assigned to the data units of the first stream.

13. The method according to any one of claims 1-7, wherein

The update parameters of the stream include time interval parametersAnd relative error parameter

Time interval parameterIs the time interval or average of the stream being updated, and the relative error parameterIs the sum or sum of squares of the differences of the median values of the respective time intervals in which the stream is updated.

14. The method of claim 1, wherein

Calculating time interval parametersRelative error parameterAnd median parameterWherein the method comprises the steps of

Gamma is a positive number much smaller than 1, T _s is the time interval during which the stream is updated,Is the time interval parameter of the data units allocated to the stream.

15. The method according to one of claims 1-7, wherein the update parameters of the stream comprise time interval parametersRelative error parameterAnd median parameterAccording to the formula

16. The method of claim 6, further comprising: in response to assigning the first stream to the IO command, update parameters for the first stream are also calculated.

17. The method of claim 14, wherein

According to the formula

A first stream is obtained, where s represents the first stream.

18. The method of claim 1, wherein the streams to be allocated include streams from a first group and streams from a second group.

19. The method of claim 18, wherein the first stream is from a first group.

20. The method of claim 18, wherein the data generated for garbage collection or wear leveling is assigned a stream from the second set.

21. The method of claim 18, wherein the first stream assigned to the IO command is selected from the first group if the correlation parameter of the data unit is greater than a specified correlation threshold.

22. The method of claim 21, wherein the first stream assigned to the IO command is selected from the second set if the correlation parameter of the data unit is not greater than the specified correlation threshold.

23. The method of claim 1, wherein the stream is bound to an NVM group, the NVM group being a partition of storage resources of a storage device accessed by the IO command.

24. The method of claim 1, further comprising:

the dispersion of the first stream is calculated and the first stream is split according to the dispersion of the first stream.

25. The method of claim 24, wherein

Dispersion of flow, whereinFor time interval parameters of the streamIs the relative error parameter of the stream.

26. The method of claim 24, wherein the dispersion of the streams is a time interval parameter of the streamsIs a dispersion of (2).

27. The method of claim 24, wherein the dispersion of the streams is a relative error parameter of the streams

28. The method of claim 24, wherein the dispersion of the streamsWherein the method comprises the steps ofFor time interval parameters of the streamIs the relative error parameter of the stream.

29. The method of claim 24, wherein two new sets of update parameters are generated based on the update parameters of the streams, each new set representing a split one of the streams.

30. The method of claim 29, wherein the average or statistical value of the update parameters of the two streams is the same as the update parameters of the stream before splitting, one of the update parameters of the two streams being greater than the other.

31. The method of claim 24, wherein the formula is followed by

32. The method of claim 24, wherein the formula is followed by

33. The method of claim 24, wherein the first stream is split in response to a dispersion of the first stream being greater than a specified threshold.

34. The method of claim 31, further comprising: sorting the plurality of streams by median parameter, and for streams Sp and streams Sm1 and Sm2 adjacent to the sorting, if satisfiedGreater than a first threshold orGreater than the second threshold, then splitting stream Sp and/or combining stream Sm1 with stream Sm2, whereinIs the dispersion of the stream SpIs the dispersion of the stream Sm resulting from the combination of the stream Sm1 and the stream Sm 2.

35. The method according to claim 34, wherein the stream Sp is split and/or the stream Sm1 and the stream Sm2 are combined periodically or under specified conditions.

36. The method of claim 35, wherein the age of each of the plurality of streams is greater than an age threshold, wherein the age of a stream is the time that the stream was created, the last time the stream was split, or the last time the stream was merged to the current time.

37. The method according to claim 35, wherein the stream Sp is not split if the age of the stream Sp is not greater than an age threshold; and if the age of any one of the streams Sm1 and Sm2 is not greater than the age threshold, not combining the streams Sm1 and Sm2.

38. The method of claim 34, wherein each of the plurality of streams is from a first group; or each stream of the plurality of streams is from the second group.

39. A storage device comprising a control unit and a non-volatile storage medium, the control unit performing the method according to one of claims 1-38.