CN105917303A - Controller, method for identifying data block stability and storage system - Google Patents

Abstract

An embodiment of the present invention provides a controller, including a processor and a cache, and the processor is configured to calculate a target logical address among the plurality of logical addresses according to a preset hash function to obtain a target hash value; determine the target entry corresponding to the target logical address in the hash table according to the target hash value, and record the target count value in the target entry; according to the target count value, and the count value The corresponding relationship with the stability level determines the stability level of the data block corresponding to the target logical address, and the stability level is used to represent the stability of the data block corresponding to the target logical address; the target logical address and the target The stability level of the data block corresponding to the logical address is sent to the flash memory device. The flash memory device can centrally store data blocks of the same stability level.

Description

A controller, a method for identifying the stability of a data block, and a storage system technical field

Embodiments of the present invention relate to the field of storage technology, in particular to a controller, a method for identifying the stability of a data block, and a storage system.

Background technique

Flash Memory (flash memory) device is a kind of non-volatile memory, and its storage medium is NAND Flash, which has the characteristic that the data will not disappear after power failure, so it is widely used as external and internal memory. The flash memory device using NAND Flash as the storage medium may be a solid-state hard drive (full name: Solid State Device, abbreviated: SSD), also known as a solid-state drive (full name: Solid State Drive, abbreviated: SSD), or other memories.

An SSD usually consists of multiple flash memory chips, and each flash memory chip contains several blocks. Due to the erasing feature of NAND Flash, the data stored in the block will not be directly modified like ordinary mechanical hard disks. When it is necessary to modify the data pointed to by a logical address, it is necessary to find an idle block, write the modified data into the idle block, and then point the logical address to the newly written data, then the original block The data in becomes invalid data. For SSD, valid data refers to the data stored in the block that is pointed to by a logical address, and this part of data may be read; invalid data refers to the data stored in the block that does not point to a logical address, and this part of data cannot be read. is read.

As more and more data are stored in the SSD, there are fewer and fewer available free blocks, so it is necessary to perform garbage collection on the SSD in order to generate available free blocks. Garbage collection refers to moving valid data in a block to an idle block, and then erasing the old block, and the erased block can be used as an idle block to write data again. Normally, when an SSD performs garbage collection, it will look for blocks containing more invalid data, because blocks containing more invalid data contain less valid data, so less valid data needs to be moved to free blocks. In the case that the life of the SSD is related to the erasure times of the NAND Flash, The less data moved during garbage collection, the smaller the write amplification of the SSD. However, in the existing storage system, the controller cannot know the possibility of the data being modified, so when sending the data to the SSD, the SSD can only store the data according to the existing storage method, and the data stored in each block The probability of being modified is roughly the same, so there is no obvious difference in the amount of invalid data contained in each block.

Contents of the invention

The first aspect of the embodiments of the present invention provides a controller, the controller includes a processor and a cache, the cache stores a plurality of logical addresses, and the cache also stores a hash table, the hash The table includes a plurality of entries, each entry corresponds to a logical address, and each entry records a count value, and the count value is used to indicate the number of times of modification of the data block corresponding to the logical address. Wherein, the processor is configured to calculate a target logical address among the plurality of logical addresses according to a preset hash function to obtain a target hash value. Then, a target entry corresponding to the target logical address in the hash table is determined according to the target hash value, and a target count value is recorded in the target entry. Determine the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level, and the stability level is used to represent the stability of the data block corresponding to the target logic address . Finally, the target logical address and the stability level of the data block corresponding to the target logical address are sent to the flash memory device.

In the first implementation manner of the first aspect, the correspondence between the count value and the stability level includes the correspondence between the count value interval and the stability level. The processor is specifically configured to determine a target count value interval according to the target count value, and the target count value is located in the target count value interval. Then, the stability level of the data block corresponding to the target logical address is determined according to the target count value interval and the corresponding relationship between the count value interval and the stability level.

In the second implementation manner of the first aspect, the processor is further configured to obtain the target logical address before calculating the target logical address among the plurality of logical addresses according to the preset hash function logical address. Then, calculation is performed according to the target logical address and the hash function to obtain the target hash value. Then determine the target entry according to the target hash value, the target A count value is recorded in the entry, and the count value recorded in the target entry is increased, and the target count value is equal to the increased count value recorded in the target entry.

The second aspect of the embodiment of the present invention provides a method for identifying the stability of a data block, the method is applied to a controller, the controller includes a processor and a cache, and multiple logical addresses are stored in the cache, and A hash table is also saved in the cache, the hash table includes a plurality of entries, each entry corresponds to a logical address, and a count value is recorded in each entry, and the count value is used to represent The modification times of the data block corresponding to the logical address. The method is executed by the processor, and includes the following steps: calculating a target logical address among the plurality of logical addresses according to a preset hash function to obtain a target hash value. Then, a target entry corresponding to the target logical address in the hash table is determined according to the target hash value, and a target count value is recorded in the target entry. Then send the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device.

In the first implementation manner of the second aspect, the correspondence between the count value and the stability level includes the correspondence between the count value interval and the stability level. The determining the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level includes: determining a target count value interval according to the target count value, and the target count value in the range of the target count value. The stability level of the data block corresponding to the target logical address is then determined according to the target count value interval and the corresponding relationship between the count value interval and the stability level.

In the second implementation manner of the second aspect, before the calculation of the target logical address among the plurality of logical addresses according to the preset hash function, the method further includes: acquiring the target logical address . Then, calculation is performed according to the target logical address and the hash function to obtain the target hash value. Then determine the target entry according to the target hash value, the count value is recorded in the target entry, and the count value recorded in the target entry is increased, and the target count value is equal to the increased value The count value recorded in the target entry.

The third aspect of the embodiments of the present invention provides a storage system, the storage system includes a controller in any one of the first to second implementations of the first aspect, and a flash memory device place. The flash memory device includes a main controller and a flash memory chip, the flash memory chip includes a plurality of blocks, and the main controller includes a processor. The processor is configured to acquire a stability level corresponding to the target logical address, and the stability level is used to represent the stability of the data block. Then, according to the stability level corresponding to the target logic address, write the data block corresponding to the target logic address into the block corresponding to the stability level.

In the first implementation manner of the third aspect, the method further includes: searching for a block containing the most invalid data in the flash chip, and the block containing the most invalid data includes the data block corresponding to the target logical address .

In the second implementation manner of the third aspect, the method further includes: searching for a block that has not been erased for the longest time in the flash memory chip, and the block that has not been erased for the longest time includes the The data block corresponding to the target logical address.

In a third implementation manner of the third aspect, the main controller further includes a cache. The obtaining the stability level corresponding to the target logical address includes: when determining that the number of logical addresses stored in the cache reaches a preset threshold, obtaining the stability level corresponding to the target logical address, wherein the stable level corresponding to the logical address The level is the same as the stability level corresponding to the target logical address.

A fourth aspect of the embodiments of the present invention provides an apparatus for identifying the stability of a data block, where the apparatus is located in a controller. The device includes: a storage module for saving a plurality of logical addresses and a hash table, the hash table includes a plurality of entries, each entry corresponds to a logical address, and a count is recorded in each entry value, and the count value is used to indicate the modification times of the data block corresponding to the logical address. A calculation module, configured to calculate a target logical address among the plurality of logical addresses according to a preset hash function to obtain a target hash value; A target entry corresponding to the target logical address, where the target count value is recorded. A determining module, configured to determine the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level, and the stability level is used to represent the data corresponding to the target logic address block stability. A sending module, configured to send the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device.

In the first implementation manner of the fourth aspect, the correspondence between the count value and the stability level includes the correspondence between the count value interval and the stability level. The determining module is specifically configured to determine a target count value interval according to the target count value, and the target count value is located in the target count value interval. Then, the stability level of the data block corresponding to the target logical address is determined according to the target count value interval and the corresponding relationship between the count value interval and the stability level.

The fifth aspect of the embodiments of the present invention provides a computer program product, including a computer-readable storage medium storing program code, the program code includes instructions for executing the second implementation mode of the second aspect to the second aspect The method described in any one of the embodiments.

In this embodiment, the controller can calculate and obtain a hash value according to the logical address, and the hash value corresponds to an entry in the hash table, and a count value is recorded in the entry, and the count value is used for Indicates the number of modifications of the data block corresponding to the logical address, so the stability level of the data block corresponding to the logical address can be obtained according to the count value, and the stability level can reflect the stability of the data block corresponding to the logical address, and Send the stability level and logical address of the data block to the flash memory device, so that the flash memory device will centrally store the data blocks of the same stability level, thereby moving less valid data when performing subsequent garbage collection operations, reducing write amplification .

Description of drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following will briefly introduce the prior art or the accompanying drawings required in the embodiments. Obviously, the accompanying drawings in the following description are only some implementations of the present invention For example, those of ordinary skill in the art can also obtain other drawings based on these drawings on the premise of not paying creative efforts.

FIG. 1 is a composition diagram of a storage system provided by an embodiment of the present invention;

Fig. 2 is a schematic structural diagram of a controller provided by an embodiment of the present invention;

FIG. 3A is a schematic structural diagram of a storage medium of a flash memory device provided by an embodiment of the present invention;

3B is a schematic structural diagram of a main controller of a flash memory device provided by an embodiment of the present invention;

FIG. 4 is a schematic flowchart of a method for identifying data block stability provided by an embodiment of the present invention;

FIG. 5 is a flowchart of a method for storing data in a flash memory device according to an embodiment of the present invention. intention;

Fig. 6 is a schematic diagram of a hash table provided by an embodiment of the present invention;

Fig. 7 is a schematic structural diagram of an apparatus for identifying data block stability provided by an embodiment of the present invention.

detailed description

Embodiments of the present invention provide a controller, a method for identifying the stability of a data block, and a storage system, for the controller to identify the stability level of the data block corresponding to the logical address, and send the logical address and the stability level to the flash memory device, so that the flash memory device can centrally store data blocks with the same stability level, then the selected block contains as little valid data as possible during subsequent garbage collection, thereby reducing the write amplification of the flash memory device.

Before describing the embodiments of the present invention, firstly, the following terms will be explained:

Data objects refer to objects containing actual data, which can be block data, files or other forms of data.

A data block refers to a data unit divided by a data object. For the convenience of management, a data object can be divided into several data blocks, and each data block has the same size.

The metadata of the data block refers to information used to describe the data block, such as the logical address of the data block, the physical address of the data block, the correspondence between the logical address and the physical address, the writing time of the data block, and the like.

Stable data refers to data that has a relatively low probability of being modified.

Logical block address, also known as logical address (full name in English: Logical Block Address, English abbreviation: LBA), refers to the storage address of the data block. This address is not the actual address of the data block stored in the SSD, but the externally accessible the address of.

The physical block address, also known as the physical address (English full name: Physical Block Address, English abbreviation: PBA) refers to the actual address of the data block stored in the SSD.

Valid data in SSD refers to the data block pointed to by logical address in the block of SSD, that is to say, its physical address has corresponding logical address.

Invalid data in SSD usually refers to the data block stored in the block of SSD without logical address pointing, that is to say, its physical address has no corresponding logical address.

FIG. 1 depicts a composition diagram of a storage system provided by an embodiment of the present invention. The storage system shown in FIG. 1 includes a controller 11 and multiple flash memory devices 22 . Wherein, the flash memory device 22 is a storage device with Flash particles as a storage medium, which may include a solid state drive (full name: Solid State Device, abbreviated: SSD), also known as a solid state drive (full name: Solid State Drive, abbreviated: SSD). including other memory. In this embodiment, the flash memory device 22 is described by taking an SSD as an example.

FIG. 1 is only an illustration, and does not limit a specific networking mode, for example, cascading tree networking and ring networking are all possible. As long as the controller 11 and the flash memory device 22 can communicate with each other.

Controller 11 may include any computing device known in the art, such as a server, desktop computer, and the like. The controller 11 can receive the data object sent by the host (not shown in FIG. 1 ), and send a write data request to the flash memory device 22, so that the flash memory device 22 writes the data object carried in the write data request into its flash chip.

Please refer to FIG. 2 , which is a schematic structural diagram of a controller 11 according to an embodiment of the present invention. As shown in FIG. 2 , the controller 11 mainly includes a processor (processor) 118, a cache (cache) 120, a memory (memory) 122, a communication bus (bus for short) 126 and a communication interface (Communication Interface) 128. The processor 118 , the cache 120 , the memory 122 and the communication interface 128 communicate with each other through the communication bus 126 .

The processor 118 may be a central processing unit CPU, or an ASIC (Application Specific Integrated Circuit), or one or more integrated circuits configured to implement the embodiments of the present invention. In the embodiment of the present invention, the processor 118 is configured to receive a data object from the host, and send the data object to the flash memory device 22 after certain processing.

The communication interface 128 is used for communicating with the host or the flash memory device 22 .

The memory 122 is used to store the program 124. The memory 122 may include a high-speed RAM memory, and may also include a non-volatile memory (non-volatile memory), such as at least one disk memory. It can be understood that the memory 122 can be a random access memory (full name: Random-Access Memory, referred to as: RAM), magnetic disk, hard disk, optical disk, solid state disk (full name: Solid State Disk, referred to as: SSD) or non-volatile memory and other non-transitory (non-transitory) that can store program code machine-readable medium.

The cache 120 (Cache) is used to temporarily store data objects received from the host or read from the flash memory device 22 . In addition, because the Cache reads and writes data faster, some frequently used information can also be stored in the Cache for the convenience of reading, such as the logical address of the data block. The cache 120 can be RAM, storage-class memory (full name: Storage-Class Memory, abbreviated: SCM), non-volatile storage (full name: Non-Volatile Memory, abbreviated: NVM), flash memory (Flash memory) or solid-state hard disk (full name: Solid State Disk (SSD for short) and other non-transitory (non-transitory) machine-readable media that can store data are not limited here.

The cache 120 and the memory 122 may be set together or separately, which is not limited in this embodiment of the present invention.

Program 124 may include program code including computer operating instructions. For example, the program code may include a stability judgment module, through which the number of times the data block stored in each LBA is modified can be judged, that is, the stability of the data block corresponding to the LBA can be judged.

The following briefly introduces the functions of the stability judgment module:

First, in order to complete this function, a hash table needs to be saved in the cache 120 (in order to prevent loss, another copy can be stored in the flash memory device 22 as a backup), and the hash table includes a plurality of entries, each table There is a count value recorded in the item. The number of entries in the hash table is related to the available capacity of the storage system shown in Figure 1, assuming that the storage system stores N data blocks (N is a positive integer), and the size of each data block is 4KB, then There can be 2-8 times the number of entries in the hash table.

Secondly, after receiving the data object sent by the host, the controller 11 may divide the data object into several data blocks with the same size. In addition, when the controller 11 receives the data object, it will also receive the address information of the data object, and the address information may include the ID of the logical unit number (English full name: Logical Unit Number, English abbreviation: LUN) and the LUN The start address offset of the file; or the ID of the file and the start address offset of the file, etc.; or when the When the storage system has multiple file systems, the address information may include the ID of the file system, the ID of the file, the offset of the starting address of the file, and the like. After the data object is divided into several data blocks with the same size, the logical address of each data block can be obtained according to the address information of the data object and the multi-level mapping table.

The stability judging module includes a hash function, and for an LBA, a hash operation can be performed according to the hash function to obtain a hash value. The hash value is used to indicate the position of an entry in the above hash table, so the count value recorded in the entry can be found according to the hash value, and after the count value corresponding to the LBA is found, the count Add 1 to the value (or other operations to increase it, not limited here). By analogy, when the subsequent controller 11 receives other data blocks to be written into the LBA, the count value corresponding to the LBA will be incremented by 1. Therefore, the count value can be used to represent the modification times of the data block stored in the corresponding LBA. The larger the count value is, the more times the data blocks stored in the LBA are modified, the more unstable they are; otherwise, the more stable they are.

When the task (the task here refers to the task that the controller 11 identifies the stability of the data block corresponding to each LBA) is triggered, the processor 118 can scan each LBA in turn, and hash the LBA according to the hash function described above Calculate to obtain the hash value, and then find the entry corresponding to the LBA according to the hash value, the entry records a count value, and obtain the stability level of the LBA according to the count value. The stability level is a value that reflects the stability of the data block corresponding to the LBA. The larger the value, the lower the stability, and vice versa. Alternatively, the stability level can also be defined as the smaller the value, the higher the stability, and vice versa.

After the controller 11 obtains the stability level of the data block corresponding to the LBA, it can send the LBA and the stability level to the flash memory device 22, so that the flash memory device 22 stores the data blocks of the same level in one or more blocks.

The structure and function of the flash memory device 22 will be described below.

Please refer to FIG. 3A , which is a schematic structural diagram of a flash memory device 22 according to an embodiment of the present invention. In this embodiment, the flash memory device 22 is described by taking an SSD as an example.

As shown in FIG. 3A , the flash memory device 22 includes a main controller 220 and a storage medium 221 . Wherein, the main controller 220 is used to receive the I/O request sent by the controller 11 to the flash memory device 22, or other information, such as the logical address and stability level of the data block, and the main controller 220 is also used to execute the received I/O request. The /O request, for example, writes the data block carried in the I/O request into the storage medium 221 , or reads the data block from the storage medium 221 and returns it to the controller 11 . The main controller 220 here is the main controller of the SSD.

The storage medium 221 is generally composed of several flash memory (Flash) chips. Each flash memory chip includes several blocks. Each block includes several pages (pages), and the main controller 220 writes a data block into a block in units of pages.

Due to the erasing feature of NAND Flash, the data stored in the block will not be directly modified like ordinary mechanical hard disks. When it is necessary to modify the data in a certain block, it is necessary to find an idle block and write the modified data into the idle block, then the data in the original block becomes invalid data. As more and more data are stored in the SSD, there are fewer and fewer available free blocks, so it is necessary to perform garbage collection on the SSD in order to generate available free blocks. In this embodiment, when performing garbage collection, the blocks containing the most invalid data are usually selected in sequence for recycling. The trigger condition for garbage collection is that the number of free blocks included in the flash memory chip is lower than a first threshold, and the first threshold may be an integer greater than 10 and less than 100.

In addition, regular inspections are required inside the flash memory device 22. Inspection refers to the operation of periodically moving the data stored in the flash memory chip in order to prevent data loss due to the long erasing time of certain blocks in the flash memory chip. For NAND Flash, its ability to retain data can only be maintained for a certain period of time, so the data stored in it needs to be relocated periodically. In this embodiment, during the inspection, the block that has not been erased for the longest time is usually selected sequentially, the valid data in the block is moved to a free block, and then the original block is erased. The trigger condition of the inspection may be when a preset inspection period is reached.

Since the lifespan of SSD is related to the erasing times of NAND Flash, minimizing data transfer inside SSD will help reduce write amplification and prolong the lifespan of SSD. In this example, The data movement inside the SSD mainly refers to the movement of valid data in the block during garbage collection or inspection. It is understandable that, for a block to be recycled, if it contains less valid data, the less data needs to be moved. Therefore, the purpose of the present invention is mainly to identify the stability of the data block corresponding to the logical address by the controller, and send the stability level reflecting the stability of the data block to the SSD, so that the data blocks in the SSD are stored centrally according to the stability level, then The amount of valid data moved during subsequent garbage collection operations will be as little as possible.

FIG. 3B is a schematic structural diagram of the main controller 220 in the flash memory device 22 described in the embodiment of the present invention.

The main controller 220 mainly includes a processor (processor) 218 , a memory (cache) 230 , a communication bus (bus for short) 226 and a communication interface (Communication Interface) 228 . The processor 218 , the cache 230 and the communication interface 228 communicate with each other through the communication bus 226 .

The processor 218 may be a central processing unit CPU, or an ASIC (Application Specific Integrated Circuit), or one or more integrated circuits configured to implement the embodiments of the present invention. In the embodiment of the present invention, the processor 218 can be used to receive information such as the I/O request from the controller 11, the logical address of the data block, and the stability level of the data block. In addition, the processor 218 is also used to perform I/O ask.

The communication interface 228 is used for communicating with the controller 11 and the storage medium 221 .

The cache 230 (Cache) is used to cache the information received from the controller 11, such as the logical address of the data block and the stability level of the data block. The cache 230 may be various non-transitory (non-transitory) or transitory (transitory) machine-readable media capable of storing data such as RAM, SCM, NVM, etc., which is not limited herein. In addition, in some application scenarios, the cache 230 may also be placed outside the main controller 220 .

In this embodiment, a mapping table may be stored in the cache 230 for storing the correspondence between the LBA of the data block received from the controller 11 and the stability level of the data block. Usually, there is also a mapping table that records the mapping relationship between LBA and PBA in the cache 230. In the embodiment of the present invention, on the basis of this mapping table, the correspondence between the LBA and the stability level can be increased. should be related.

Alternatively, multiple arrays are stored in the cache 230, each array corresponds to a stability level, and logical addresses of multiple data blocks corresponding to the stability level may be stored in the array.

Alternatively, the cache 230 may not save the mapping table, but store logical addresses of data blocks with the same stability level in a cache space of the cache 230 . For example, the controller 11 may send the cache area division information to the flash memory device 22 in advance, the cache area division information includes different stability levels (for example, 10 stability levels of 1-10), and the flash memory device 22 receives the After the cache area is divided into information, the cache 230 is divided into 10 cache areas according to 10 stability levels, each cache area corresponds to a stability level, and is specially used to store the logical address of the data block corresponding to the stability level. Alternatively, the controller 11 may also directly send the logical address of the data block and the stability level of the data block to the flash memory device 22 without sending the cache area division information to the flash memory device 22 in advance. The flash memory device 22 divides a cache area in the cache 230 according to the stability level of the data block, and corresponds the cache area to the stability level (saves the correspondence between the cache area and the stability level), Afterwards, the divided cache area may be specially used to store the logical address of the data block corresponding to the stability level. Both of the above two methods can realize the centralized storage of logical addresses of data blocks with the same stability level in a cache space of the cache 230 .

The following describes a method for identifying the stability of a data block according to an embodiment of the present invention. The method describes the process of obtaining the stability level of the data block according to the logical address of the data block and sending it to the flash memory device 22 from the perspective of the controller 11 . Please refer to FIG. 4. FIG. 4 is a schematic flowchart of the method for identifying the stability of the data block corresponding to the logical address. The method can be applied in the storage system shown in FIG. 1 and the controller 11 shown in FIG. 2 , a plurality of logical addresses are stored in the cache 120 of the controller 11, and in addition, a hash table is also stored in the cache 120, and the hash table includes a plurality of entries, each entry corresponds to a logical address, and, A count value is recorded in each entry, and the count value is used to represent the modification times of the data block corresponding to the logical address; the execution body of the count value is the processor 118 in the controller 11 . The methods include:

Step S102: According to the preset hash function, the objects in the plurality of logical addresses are logically The address is calculated to obtain the target hash value.

Specifically, the controller 11 may sequentially obtain the logical address of each data block from the multiple logical addresses, so as to perform calculation and obtain a hash value. Here, the target logical address is taken as an example for description.

In addition, the trigger condition of step S102 may be that the size of all data blocks received by the controller 11 exceeds a preset capacity threshold or is triggered by a timer. The preset capacity threshold may be equal to the storage system shown in FIG. 1 presented to the user. available capacity, or an integer multiple of the available capacity.

Step S103: Determine a target entry corresponding to the target logical address in the hash table according to the target hash value, and a target count value is recorded in the target entry.

Specifically, the hash table may contain a plurality of entries, and each entry has a position in the hash table (for example, a number may be used to indicate the position of each entry), and in step 102 The calculated target hash value may be equal to the number of the target entry, or other values directly pointing to the number of the target entry. Moreover, since each entry of the hash table records a count value, the target count value can be obtained according to the target hash value.

Step S104: Determine the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level, and the stability level is used to indicate the stability level of the data block corresponding to the target logical address stability.

Wherein, the controller 11 may preset the number of stable levels.

Optionally, an implementation manner is: dividing the count value recorded in the entry into multiple count value intervals, where each count value interval corresponds to a stability level. For example, assuming that 10 stability levels are preset, the corresponding relationship between the count value interval and the stability level can be shown in Table 1:

Count value range stable level +∞>Count value≥35 10 35>Count value≥30 9 30>Count value≥25 8 25>Count value≥20 7

20>Count value≥15 6 20>Count value≥15 5 15>Count value≥10 4 10>Count value≥5 3 5>Count value ≥ 2 2 count value = 1 1

Table 1

Then, correspondingly, determining the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level may specifically be: determining the target count value interval according to the target count value, The target count value is located in the target count value interval; the stability level of the data block corresponding to the target logical address is determined according to the target count value interval and the corresponding relationship shown in Table 1. For example, a target count value of 3 corresponds to a stability level of 2.

Step S105: Send the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device.

Specifically, the controller 11 may send one logical address and stability level to the flash memory device 22 each time, or may send multiple logical addresses and stability levels to the flash memory device 22 each time.

In this embodiment, the controller 11 can calculate and obtain a hash value according to the logical address, the hash value corresponds to an entry in the hash table, and the count value is recorded in the entry, and the count value is used as In order to represent the modification times of the data block corresponding to the logical address, the stability level of the data block corresponding to the logical address can be obtained according to the count value, and the stability level can reflect the stability of the data block corresponding to the logical address, And the stability level and logical address of the data block are sent to the flash memory device 22, so that the flash memory device 22 centrally stores the data blocks of the same stability level.

Another method for storing data in a flash memory device according to an embodiment of the present invention is introduced below. Please refer to FIG. 5, which is a schematic flowchart of identifying data block stability. The method can be applied to the data block shown in FIG. 1 in the storage system.

In this embodiment, steps S201 to S204 describe the process of how the write data request triggers the update of the counter value in the hash table. Step S201 - step S204 can be applied in the controller 11 shown in FIG. 2 , and the execution subject is the processor 118 in the controller 11 .

In step S201, the controller 11 receives a write data request sent by the host, and the write data request includes a data object and address information of the data object.

In step S202, the controller 11 divides the data object into multiple data blocks of the same size.

In this embodiment, taking the size of the data block as 4KB as an example, when the data object is larger than 4KB, it needs to be split into multiple data blocks; when the data object is smaller than 4KB, it does not need to be split.

Correspondingly, the controller 11 can obtain the logical address of each data block according to the address information and the multi-level mapping table, and store these logical addresses in the cache 120 .

In step S203, the controller 11 determines a target logical address from the plurality of logical addresses.

Specifically, the controller 11 may scan the multiple logical addresses, and read each logical address in sequence. For the convenience of description, in the following steps, the processing manner of the target logical address is taken as an example for illustration. It can be understood that the processing manner of other logical addresses is the same as that of the target logical address.

In step S204, the target logical address is calculated according to a preset hash function to obtain a target hash value, the target hash value points to an entry in the hash table, and the entry is added The count value recorded in .

In some cases, due to the limited number of entries in the hash table, the hash values generated by multiple logical addresses using the same hash function may point to the same entry, so there is no difference between the logical address and the entry. one-to-one relationship. In this case, in order to obtain the modification times of the data block corresponding to the logical address, multiple hash (Hash) functions can be preset, and the multiple hash functions are used to calculate the logical address, thereby obtaining Multiple hash values, and then update the count value in the entry pointed to by each hash value. As shown in Figure 6, four hash functions (respectively H1, H2, H3, and H4) calculate the logical address (LBA), and obtain four hash values, each of which points to an entry in the hash table, so as to count the records recorded in each entry value plus 1. For how to use the four hash values to obtain the most accurate modification times of the data block corresponding to the logical address, please refer to the description of step S208 below.

A specific example is used below to illustrate how to calculate and obtain the count value in its corresponding entry according to the LBA.

Suppose the hash table contains 10,000 entries, which is equivalent to a one-dimensional array with 10,000 elements. hash[x] indicates the value stored in the xth entry of the hash table, where x is an integer greater than or equal to 1.

Assuming that the LBA is 100, when a data block is written in the logical address with the LBA of 100, the operation of updating the count value of the hash table is as follows:

First, 4 hash values are calculated by 4 hash functions, and the 4 hash functions are:

Hash value 1=(LBA*11)% (the number of entries in the hash table);

Hash value 2=(LBA*13)% (number of entries in the hash table);

Hash value 3=(LBA*15)% (number of entries in the hash table);

Hash value 4=(LBA*17)% (number of entries in the hash table);

Among them, "%" represents the remainder operation. Thus, it can be known that hash value 1=1100; hash value 1=1300; hash value 3=1500; hash value 4=1700.

The entries corresponding to the four hash values are hash[1100], hash[1300], hash[1500], and hash[1700], and then add 1 to the count values in these entries.

According to the method described in step S201-step S204, the controller 11 may update the count value in the hash table according to the received data object. For a logical address, the more data blocks are received, the count value in the corresponding entry will be incremented sequentially. Therefore, the count value recorded in an entry reflects the stability of the data block stored in its corresponding logical address.

Steps S205 to S209 describe the process that the controller 11 identifies the stability level of the data block corresponding to each logical address stored in the cache 120 and sends it to the flash memory device 22 . Step S205- Step S209 may be applied in the controller 11 shown in FIG. 2 , and its execution subject is the processor 118 in the controller 11 . It should be noted that there is no sequence between the process of identifying the stability level and the process of updating the count value described in steps S201-S204.

In step S205 , when the task is triggered, the controller 11 reads the plurality of logical addresses from the cache 120 .

The task here refers to the task of the controller 11 identifying the stable level of the data block stored in each logical address stored in the cache 120, and its trigger condition can be the arrival of a preset time interval, or the data object received by the controller 11 from the host. The total size exceeds a preset threshold, etc. These two conditions can also be set at the same time, and when one of the conditions is satisfied, the controller 11 starts to read the plurality of logical addresses from the cache 120 .

In step S206, the controller 11 determines a target logical address from the plurality of logical addresses.

Specifically, the controller 11 may scan the multiple logical addresses, and read each logical address in sequence. For the convenience of description, in the following steps, the processing manner of the target logical address is taken as an example for illustration. It can be understood that the processing manner of other logical addresses is similar to that of the target logical address. It should be noted that the target logical address in step S206 may be the same as or different from the target logical address in step S203-step S204.

In step S207, the controller 11 calculates the target logical address according to a preset hash function to obtain a target hash value.

Specifically, the preset hash function refers to the hash function in step S204. When there are multiple hash functions, there are also multiple calculated hash values.

In step S208, the controller 11 determines a target entry corresponding to the target logical address in the hash table according to the target hash value, and the target count value is recorded in the target entry.

Still taking the LBA as 100 as an example, the hash values obtained by using the above four hash functions include: hash value 1=1100; hash value 1=1300; hash value 3=1500; hash value 4=1700. Four count values can be obtained from the four table entries through the four hash values, and the smallest count value is selected from the four count values as the target count value.

It can be understood that since the same count value may be referenced by multiple LBAs (the reference here means that the hash value calculated by the LBA through the hash function points to the count value), the smaller the count value, the corresponding The fewer entries are referenced by other LBAs, the smallest count value is the most accurate and can best represent the modification times of its corresponding data block. In this embodiment, the target count value is equal to the smallest count value.

In step S209, the controller 11 obtains the stability level of the data block corresponding to the target logical address according to the target count value.

For a specific implementation manner, reference may be made to step S104 in the embodiment shown in FIG. 4 , which will not be repeated here.

In step S210 , the controller 11 sends the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device 22 .

For a specific implementation manner, reference may be made to step S105 in the embodiment shown in FIG. 4 , which will not be repeated here.

It can be understood that, according to the manner described in step S206-step S210, the controller 11 may send multiple logical addresses and stability levels corresponding to the logical addresses to the flash memory device 22.

After the controller 11 has processed each logical address stored in the buffer memory 120, this task is completed, and a fixed value can be subtracted from the count value recorded in the hash table, so that when the next task starts, the count value can be A smaller base to start incrementing.

Steps S211 to S213 describe the process of collectively storing data blocks with the same stability level after the flash memory device 22 receives multiple logical addresses and stability levels sent by the controller 11 . Steps S211 to S213 may be applied in the flash memory device (eg, SSD) shown in FIG. 3A and FIG. 3B , and the execution body thereof is the processor 218 in the flash memory device 22 .

In step S211, the flash memory device 22 stores the logical addresses of the multiple data blocks and the stability level corresponding to the logical addresses.

Optionally, a storage method is to establish a mapping table in the cache 230 of the flash memory device 22 for storing the correspondence between the logical address of the data block received from the controller 11 and the stability level of the data block.

Optionally, another storage method is to store multiple arrays in the cache 230, each array corresponding to a level of stability. The logical addresses of the multiple data blocks are respectively stored in their corresponding arrays.

Optionally, another storage method is to divide the cache 230 into several cache areas in advance, and each cache area corresponds to a stability level. The logical addresses of the multiple data blocks are respectively recorded in their corresponding cache areas.

In step S212, the flash memory device 22 obtains a stability level corresponding to the target logical address, and the stability level is used to represent the stability of the data block.

The target logical address is one of the logical addresses stored in the flash memory device 22 , and the target logical address is taken as an example for illustration here.

In step S213, the flash memory device 22 writes the data block corresponding to the target logical address into the block corresponding to the stable level according to the stable level corresponding to the target logical address.

In this embodiment, in order to move data blocks of the same stability level into the same block, a corresponding relationship between blocks and stability levels in the flash memory chip may be established. According to this correspondence, the data block corresponding to the target logical address can be read from the original block and written into the block corresponding to its stability level. The corresponding relationship between the block and the stability level in the flash memory chip can be pre-established, and it can also be the first time that a data block or multiple data blocks with the same stability level are written into a block and then the stability level and stability level are recorded. Correspondence between blocks.

For reading the data block corresponding to the target logical address from the original block, it can be specifically: usually, a mapping table is stored in the cache memory 230 of the flash memory device 22 or the flash memory chip, and the mapping table is used to save each data Therefore, according to the logical address and the mapping table, the data block can be read from the storage space where the corresponding physical address is located.

Using the method provided by this embodiment, data blocks of the same stability level can be stored in one block. Then, for a block that stores a data block with a high level of stability, the possibility of the stored data block becoming invalid data is small. On the whole, the block does not contain invalid data or only contains a small amount of invalid data. Such a block Belong to the block with relatively high utilization rate, can not recycle such block when carrying out garbage collection to flash memory device 22; block, the data blocks stored in it are more likely to become invalid data, assuming that most or most of the data in a block has become invalid data, then correspondingly, the valid data contained in this block is less, Less data needs to be migrated during garbage collection, reducing write amplification. It should be noted that the effect of this embodiment is mainly reflected in the reduction of valid data moved during subsequent garbage collection. It can be seen that whether it is a block storing a data block with a higher stability level or a block storing a data block with a lower stability level, the write amplification of the flash memory device 22 can be reduced, so the flash memory device 22 can be extended to a certain extent. lifespan.

In addition, a preferred implementation manner is to combine the above-described step S212-step S213 with the garbage collection operation. Specifically, when it is determined that the number of free blocks contained in the flash memory chip is lower than the first threshold, the blocks containing the most invalid data are sequentially found from the flash memory chip, and the blocks to be moved are obtained from these blocks. The logical address of the data block, and then according to the logical address, search in the corresponding relationship between the logical address and the stability level, obtain the stability level corresponding to the logical address, and then write the data block corresponding to the logical address into the corresponding in the block.

Another preferred embodiment is to combine the steps S212-S213 described above with the inspection operation, that is to say, when the flash memory device 22 needs to perform an inspection, follow the method described in steps S212-S213 Carry out inspection, specifically, when the preset inspection cycle arrives, find the blocks that have not been erased for the longest time from the flash memory chip in turn, obtain the logical address of the data block to be moved from these blocks, and then According to the logical address, search in the corresponding relationship between the logical address and the stability level, obtain the stability level corresponding to the logical address, and then write the data block corresponding to the logical address into the corresponding block.

According to the two preferred implementation modes provided above, it is possible to centrally store data blocks with the same stability level when the flash memory device 22 performs garbage collection or inspection, because the flash memory device 22 originally performs garbage collection or inspection. Data movement, so this embodiment does not require additional data movement operations, which can further reduce write amplification.

Another preferred implementation mode is that step S212-step S213 may not be combined with garbage collection or inspection operations, that is to say, in this implementation mode, the trigger conditions for moving data blocks are different from those of the previous two implementation modes. The trigger condition is that the number of logical addresses corresponding to the same stability level stored in the cache reaches a preset threshold.

Then, for how to judge whether the number of logical addresses corresponding to the same stability level reaches the preset threshold, there are three implementation methods as follows:

The first implementation manner is to determine whether the number of logical addresses with the same stability level reaches a preset threshold according to the mapping table stored in the cache 230 .

The second implementation manner is to judge whether the number of logical addresses stored in an array in the cache 230 reaches a preset threshold.

A third implementation manner is to determine whether the number of logical addresses stored in a cache area in the cache 230 reaches a preset threshold.

Wherein, the preset threshold can be set as the ratio between the capacity of the block and the size of the data block. According to this embodiment, when the number of logical addresses reaches the threshold, the corresponding The data block exactly fills a free block. At this time, the block corresponding to the stability level in step S213 may be a free block.

Please refer to FIG. 7. FIG. 7 is a device 70 for identifying data block stability provided by an embodiment of the present invention. The device 70 is located in the controller 11 and includes:

The storage module 701 is configured to save a plurality of logical addresses and a hash table, the hash table includes a plurality of entries, each entry corresponds to a logical address, and a count value is recorded in each entry, the The count value is used to represent the modification times of the data block corresponding to the logical address.

The calculation module 702 is configured to calculate a target logical address among the plurality of logical addresses according to a preset hash function to obtain a target hash value; a target entry corresponding to the target logical address, and the target count value is recorded in the target entry.

A determining module 703, configured to determine the stability level of the data block corresponding to the target logical address according to the target count value and the corresponding relationship between the count value and the stability level, and the stability level is used to indicate the stability level of the data block corresponding to the target logic address. Data block stability;

The sending module 704 is configured to send the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device.

In this embodiment, the hash value can be obtained by calculating according to the logical address, the hash value corresponds to an entry in the hash table, and a count value is recorded in the entry, and the count value is used to represent the The modification times of the data block corresponding to the logical address, so the stability level of the data block corresponding to the logical address can be obtained according to the count value, and the stability level can reflect the stability of the data block corresponding to the logical address, and the obtained The stability level and logical address of the above data blocks are sent to the flash memory device 22, so that the flash memory device 22 centrally stores the data blocks of the same stability level.

Optionally, in the above embodiment, the correspondence between the count value and the stability level includes the correspondence between the count value interval and the stability level; the determining module 703 is specifically configured to determine the target count value interval according to the target count value, The target count value is located in the target count value interval; and the stability level of the data block corresponding to the target logical address is determined according to the target count value interval and the corresponding relationship between the count value interval and the stability level.

In addition, in the above embodiment, the calculation module 702 is further configured to obtain the target logical address before calculating the target logical address among the plurality of logical addresses according to a preset hash function; according to The target logical address and the hash function are calculated to obtain the target hash value; the target entry is determined according to the target hash value, and a count value is recorded in the target entry; A count value recorded in the target entry, where the target count value is equal to the added count value recorded in the target entry.

Optionally, the calculation module 702 is further configured to, after sending the target logical address and the stability level of the data block corresponding to the target logical address to the flash memory device, record the Target count value minus fixed value.

An embodiment of the present invention also provides a computer program product for data processing, including a computer-readable storage medium storing program code, and the program code includes instructions for executing the method process described in any one of the foregoing method embodiments.

Those of ordinary skill in the art can understand that the aforesaid storage medium includes: U disk, mobile hard disk, magnetic disk, optical disk, random-access memory (Random-Access Memory, RAM), solid-state hard disk (Solid State Disk, SSD) or nonvolatile Various non-transitory (non-transitory) machine-readable media that can store program codes such as non-volatile memory.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solution of the present invention, rather than to limit it.

Claims (18)

1. A kind of controller, it is characterized in that, the controller includes processor and caching, preserved in the caching and Hash table is also preserved in multiple logical addresses, and the caching, the Hash table includes multiple list items, one logical address of each list item correspondence, also, record has count value in each list item, the count value is used for the modification number of times for representing the corresponding data block of the logical address；

   The processor, for being calculated according to default hash function the destination logical address in the multiple logical address, obtains target cryptographic Hash；

   Determine that record has objective count value in target list item corresponding with the destination logical address in the Hash table, the target list item according to the target cryptographic Hash；

   According to the objective count value, and count value and the other corresponding relation of stationary level determine the stable rank of the corresponding data block of the destination logical address, and the stable rank is used for the stability for representing the corresponding data block of the destination logical address；

   The stable rank of the destination logical address and the corresponding data block of the destination logical address is sent to flash memory device.
2. Controller according to claim 1, it is characterised in that the count value includes count value interval and the other corresponding relation of stationary level with the other corresponding relation of stationary level；

   The processor, specifically for determining that objective count value is interval according to the objective count value, the objective count value is located in objective count value interval；

   It is interval according to the objective count value, and the interval stable rank that the corresponding data block of the destination logical address is determined with the other corresponding relation of stationary level of the count value.
3. Controller according to claim 1, it is characterised in that

   The processor, be additionally operable to it is described the destination logical address in the multiple logical address is calculated according to default hash function before, obtain the destination logical address；

   Calculated according to the destination logical address and the hash function, obtain the target Hash Value；

   Determine that record has count value in the target list item, the target list item according to the target cryptographic Hash；

   Increase the count value recorded in the target list item, the objective count value is equal to the count value recorded in the target list item after the increase.
4. Controller according to claim 1, it is characterised in that

   The processor, is additionally operable to be sent to after flash memory device in the stable rank by the destination logical address and the corresponding data block of the destination logical address, the objective count value recorded in the target list item is subtracted into fixed value.
5. A kind of method of identification data block stability, it is characterized in that, methods described is applied in controller, and the controller includes preserving multiple logical addresses in processor and caching, the caching, and also preserve Hash table in the caching, the Hash table includes multiple list items, and each list item corresponds to a logical address, and, record has count value in each list item, and the count value is used for the modification number of times for representing the corresponding data block of the logical address；Methods described by the computing device, including：

   The destination logical address in the multiple logical address is calculated according to default hash function, target cryptographic Hash is obtained；

   Determine that record has objective count value in target list item corresponding with the destination logical address in the Hash table, the target list item according to the target cryptographic Hash；

   According to the objective count value, and count value and the other corresponding relation of stationary level determine the stable rank of the corresponding data block of the destination logical address, and the stable rank is used for the stability for representing the corresponding data block of the destination logical address；

   The stable rank of the destination logical address and the corresponding data block of the destination logical address is sent to flash memory device.
6. Method according to claim 5, it is characterised in that the count value is with stablizing rank Corresponding relation to include count value interval with the other corresponding relation of stationary level；

   It is described according to the objective count value, and count value and the other corresponding relation of stationary level determine that the stable rank of the corresponding data block of the destination logical address includes：

   Determine that objective count value is interval according to the objective count value, the objective count value is located in objective count value interval；

   It is interval according to the objective count value, and the interval stable rank that the corresponding data block of the destination logical address is determined with the other corresponding relation of stationary level of the count value.
7. Method according to claim 5, it is characterised in that it is described the destination logical address in the multiple logical address is calculated according to default hash function before, methods described also includes：

   Obtain the destination logical address；

   Calculated according to the destination logical address and the hash function, obtain the target cryptographic Hash；

   Determine that record has count value in the target list item, the target list item according to the target cryptographic Hash；

   Increase the count value recorded in the target list item, the objective count value is equal to the count value recorded in the target list item after the increase.
8. Method according to claim 5, it is characterised in that be sent in the stable rank by the destination logical address and the corresponding data block of the destination logical address after flash memory device, methods described also includes：The objective count value recorded in the target list item is subtracted into fixed value.
9. A kind of storage system, it is characterised in that including the controller and flash memory device as described in claim 1-4 is any；The flash memory device includes master controller and flash chip, and the flash chip includes multiple pieces, and the master controller includes processor；

   The processor, for obtaining the corresponding stable rank of destination logical address, the stable rank Stability for representing data block；

   According to the corresponding stable rank of the destination logical address, by the corresponding data block write-in of the destination logical address stable corresponding piece of the rank.
10. Method according to claim 9, it is characterised in that methods described also includes：

    Searched in the flash chip comprising the most block of invalid data, the block most comprising invalid data includes the corresponding data block of the destination logical address.
11. Method according to claim 9, it is characterised in that methods described also includes：

    The block not being wiped free of in the block not being wiped free of in maximum duration, the maximum duration is searched in the flash chip includes the corresponding data block of the destination logical address.
12. Method according to claim 9, it is characterised in that the master controller also includes caching；

    The corresponding stable rank of destination logical address that obtains includes：When determining that the number of the logical address preserved in the caching reaches predetermined threshold value, the acquisition destination logical address is corresponding to stablize rank, wherein, the corresponding stable rank of the logical address stably rank corresponding with the destination logical address is identical.
13. Method according to claim 12, it is characterised in that the predetermined threshold value is equal to the business obtained by the capacity of block divided by the size of data block.
14. A kind of device of identification data block stability, it is characterised in that described device is located in controller, including：

    Memory module, for preserving multiple logical addresses and Hash table, the Hash table includes multiple list items, one logical address of each list item correspondence, also, record has count value in each list item, the count value is used for the modification number of times for representing the corresponding data block of the logical address；

    Computing module, for being calculated according to default hash function the destination logical address in the multiple logical address, obtains target cryptographic Hash；Determine that record has objective count value in target list item corresponding with the destination logical address in the Hash table, the target list item according to the target cryptographic Hash；

    Determining module, for according to the objective count value, and count value and the other corresponding relation of stationary level determine the stable rank of the corresponding data block of the destination logical address, and the stable rank is used for the stability for representing the corresponding data block of the destination logical address；

    Sending module, for the stable rank of the destination logical address and the corresponding data block of the destination logical address to be sent into flash memory device.
15. Device according to claim 14, it is characterised in that the count value includes count value interval and the other corresponding relation of stationary level with the other corresponding relation of stationary level；

    The determining module, specifically for determining that objective count value is interval according to the objective count value, the objective count value is located in objective count value interval；It is interval according to the objective count value, and the interval stable rank that the corresponding data block of the destination logical address is determined with the other corresponding relation of stationary level of the count value.
16. Device according to claim 14, it is characterised in that

    The computing module, be additionally operable to it is described the destination logical address in the multiple logical address is calculated according to default hash function before obtain the destination logical address；

    Calculated according to the destination logical address and the hash function, obtain the target cryptographic Hash；

    Determine that record has count value in the target list item, the target list item according to the target cryptographic Hash；

    Increase the count value recorded in the target list item, the objective count value is equal to the count value recorded in the target list item after the increase.
17. Device according to claim 14, it is characterised in that

    The computing module, is additionally operable to be sent to after flash memory device in the stable rank by the destination logical address and the corresponding data block of the destination logical address, the objective count value recorded in the target list item is subtracted into fixed value.
18. A kind of computer program product, it is characterised in that the computer-readable recording medium including storing program code, the instruction that described program code includes is used to perform the method as described in claim 5-8 any one.