CN106844227A - Solid state hard disc abrasion equilibrium method and device based on grouping mechanism - Google Patents

Abstract

The present invention relates to technical field of memory, the invention discloses a kind of solid state hard disc abrasion equilibrium method based on grouping mechanism, including：Physical block in solid state hard disc is divided into multiple and physics number of blocks identical group；Record the erasable number of times of each physical block；After carrying out erasable operation with physical block in group, will be resequenced according to its erasable number of times with the physical block of group, obtained the information sequence of this group of new physical block；If predetermined condition is reached with the erasable number of times of two physical blocks on the information sequence of a physical block, by the data exchange of above-mentioned two physical block.The invention also discloses a kind of solid state hard disc abrasion equilibrium device based on grouping mechanism, including：Physical block grouping module, logging modle, order module, data exchange judge module.The present invention improves the service efficiency of physical block in solid state hard disc, realizes the optimization of abrasion equilibrium performance.

Description

Solid state disk wear leveling method and device based on grouping mechanism

technical field

The invention relates to the field of storage technology, in particular to a grouping mechanism-based solid state disk wear leveling method and device.

Background technique

Solid State Disk (SSD for short) is a computer external storage device based on permanent memory, such as flash memory, or non-permanent memory, Synchronous Dynamic Random Access Memory (SDRAM). Solid-state drive flash memory (SSD) has the problem of erasing and writing times limit. If a block is repeatedly erased and other blocks are not erased, then this block will be worn out, which greatly affects the SSD. lifespan. SSD introduces wear leveling (Wear-leveling) technology to realize that erasing and writing operations are distributed as evenly as possible on all blocks, thereby maximizing the service life of SSD. Wear leveling is divided into dynamic wear-leveling and static wear-leveling. Dynamic wear leveling will only deal with the changing and unused data area, and will not deal with the existing data area, avoiding the application program on the computer operating system side to repeatedly erase/write the same storage data block area Writing, resulting in permanent damage to the entire storage unit, and more seriously causing the solid state drive to be scrapped. Static wear leveling will move them to achieve wear leveling when it is found that the wear degree of the area with existing data is significantly lower than the average wear degree.

The algorithms of each of the current controllers of the manufacturers can be said to be similar but have their own strengths and advantages. The similarity is that each controller will distinguish the data stored in it, and the data that is frequently accessed is collectively called For hot data, infrequently accessed data are collectively referred to as cold data. If a fully balanced erase and write strategy is implemented, then cold data will be moved to accommodate hot data. This will bring additional erasing overhead (write amplification), thereby reducing the overall life of the SSD. Therefore, adopting an optimized strategy can not only ensure wear leveling, but also reduce the write amplification effect, so as to maximize the service life of SSD, which has become an urgent problem to be solved.

Contents of the invention

In view of the above technical problems, the purpose of the present invention is to provide a method and device for solid state hard disk wear leveling based on grouping mechanism, which improves the use efficiency of physical blocks in solid state hard drives and realizes the optimization of wear leveling performance.

In order to achieve the above object, the present invention is achieved through the following technical solutions:

The present invention provides a method for leveling wear of a solid state disk based on a grouping mechanism, comprising the following steps:

S1: Divide the physical blocks in the solid state disk into multiple groups with the same number of physical blocks;

S2: Record the number of erasing and writing of each physical block;

S3: After the physical block is erased and written, the physical blocks of the same group are reordered according to their erasing and writing times, and a new information sequence of the physical block of the group is obtained;

S4: If the erasing times of the two physical blocks in the information sequence of the same physical block meet a predetermined condition, exchange the data of the two physical blocks.

Further, before step S1, it also includes: establishing a data structure to maintain information of each physical block;

Further, step S2 specifically includes:

Record the number of erasing and writing of each physical block in the initial state;

Sorting the physical blocks of the same group according to their erasing times to obtain the information sequence of the physical blocks of this group in the initial state;

After the erasing and writing operation is performed on the physical block, the number of erasing and writing times of the physical block is increased by one.

Further, step S4 specifically includes:

Judging whether the maximum value of the erasing times of the physical block on the information sequence of the same physical block reaches the threshold value, if it reaches the threshold, then sequentially place the information sequence of the same physical block in a symmetrical position and the difference of the erasing times meets the predetermined value The data of the two physical blocks is exchanged, and at the same time, the number of erasing and writing of the two physical blocks of the exchanged data is increased by one, and then the mapping table of the two physical blocks of the exchanged data and their corresponding logical blocks is updated to obtain an updated erase After the write times and the information sequence of the physical block after the mapping relationship, jump to step S1 and continue to execute; if not, continue to step S2 to record the erasing times of the physical blocks in the same group.

Further, the sorting is performed from small to large or from large to small.

Further, the data structure is a double linked list structure.

Further, each physical block corresponds to a physical address, each physical block corresponds to a logical block, each logical block corresponds to a logical address, and the physical address and the logical address have a unique mapping relationship.

Further, the threshold is 50 times the number of physical blocks in each group.

The present invention also provides a solid state disk wear leveling device based on a grouping mechanism based on the above grouping mechanism based solid state disk wear leveling method, including:

The physical block grouping module is used to divide the physical blocks in the solid state disk into multiple groups with the same number of physical blocks;

A recording module for recording the number of erasing and writing of each physical block;

The sorting module is used to reorder the physical blocks of the same group according to the number of times of erasing and writing after the physical blocks are erased and written, and obtain a new information sequence of the physical blocks of this group;

Data exchange judging module: used for exchanging the data of the above two physical blocks if the erasing times of the two physical blocks in the information sequence of the same physical block meet a predetermined condition.

Further, it also includes: a physical block information maintenance module, which is used to establish a data structure to maintain the information of each physical block.

Further, the data exchange judging module further includes: a translation module, which is used to translate the physical address of the physical block into a logical address of the corresponding logical block; the data exchange judging module further includes: a mapping table updating module, which is used to translate the The mapping table between the two physical blocks of data exchange and their corresponding logical blocks is updated.

Compared with the prior art, the beneficial effects of a grouping mechanism-based solid state disk wear leveling method of the present invention are as follows:

1. The present invention is based on a grouping mechanism. When the erasing times of two physical blocks on the information sequence of the same physical block reach a predetermined condition, the data of the two physical blocks are exchanged, and the physical block and its corresponding logical block are updated. The mapping table improves the utilization efficiency of the physical blocks in the solid-state hard disk, thereby realizing the optimization of wear leveling performance;

2. The grouping of the physical blocks of the present invention can be dynamically adjusted according to the utilization rate of the physical blocks and the available storage space, and the logical addresses of the physical blocks with too many local write operations can be evenly mapped to the full physical storage space, thereby avoiding partial The data is overheated, which realizes the optimization of the wear leveling performance of the physical blocks in the global solid-state hard disk, and prolongs the service life of the solid-state hard disk to the greatest extent;

3. the present invention adopts double-linked list data structure, is convenient to it sorting, and double-linked list structure can also comprise the head and tail pointer of pointed linked list, thereby can directly obtain the pe_cnt_min and pe_cnt_max of sequence member, make because erase operation has been carried out and erase The order of the physical block whose write count is increased by one in the information sequence of the physical block will not be adjusted temporarily, and the sorting will only adjust the position of a small number of physical blocks, thus saving unnecessary overhead;

4. In the present invention, the grouping of physical blocks can be dynamically adjusted according to the utilization rate of physical blocks and the available storage space, so the number of physical blocks in each group will also be dynamically adjusted, and then the set threshold will also be dynamically adjusted, so that Optimized wear leveling performance.

The beneficial effect of a solid state disk wear leveling device based on a grouping mechanism is similar to the beneficial effect of a solid state disk wear leveling method based on a grouping mechanism, and will not be repeated here.

Description of drawings

FIG. 1 is one of the flow diagrams of the solid state disk wear leveling method based on the grouping mechanism in the present invention.

FIG. 2 is a schematic diagram of a physical block in an initial state in Embodiment 1 of the present invention.

Fig. 3 is a schematic diagram of sorting physical blocks in Embodiment 1 of the present invention.

FIG. 4 is a schematic diagram of sorting physical block update erasing times in Embodiment 1 of the present invention.

FIG. 5 is a schematic diagram of data exchange and update mapping of physical blocks in Embodiment 1 of the present invention.

FIG. 6 is the second schematic flow diagram of the solid state disk wear leveling method based on the grouping mechanism of the present invention.

FIG. 7 is one of the structural schematic diagrams of the solid state disk wear leveling device based on the grouping mechanism of the present invention.

FIG. 8 is the second schematic diagram of the structure of the solid state disk wear leveling device based on the grouping mechanism of the present invention.

detailed description

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

The nouns and concepts appearing in the following examples are explained below:

Solid state drive: English full name Solid State Drives, referred to as SSD, a hard disk made of solid state electronic memory chip array, composed of a control unit and a storage unit (FLASH chip or DRAM chip), the control unit mainly includes the firmware in a specific type of solid state drive The program, the control module such as the flash conversion layer and the flash controller, and the storage unit are mainly flash storage particles produced by semiconductor companies.

A method and device for wear leveling of solid-state hard drives based on grouping mechanism of the present invention will be further described below in conjunction with the accompanying drawings and specific embodiments:

Example 1

As shown in Figure 1, a grouping mechanism-based solid state disk wear leveling method includes the following steps:

Step S101: According to the usage rate and available storage space of the physical blocks in the solid-state hard disk, divide the physical blocks in the solid-state hard disk into multiple groups with the same number of physical blocks, and the number of physical blocks in each group is N;

Step S102: Record the erasing and writing times of each physical block;

Step S103: After performing the erasing and writing operation on the physical blocks, reorder the physical blocks in the same group according to their erasing and writing times from small to large, and obtain a new information sequence of the physical blocks in this group;

Step S104: If the number of erasing and writing times of two physical blocks in the information sequence of the same physical block reaches a predetermined condition, exchange the data of the two physical blocks.

The above step S102 specifically includes: recording the erasing times of each physical block in the initial state; sorting the physical blocks of the same group according to their erasing times to obtain the information sequence of the physical blocks in the group in the initial state; erasing the physical blocks After the write operation, add one to the erasing and writing times of the physical block.

The above step S104 specifically includes: judging whether the maximum value of the erasing times of the physical blocks on the information sequence of the same physical block reaches the threshold value, and if it reaches the threshold, then successively set the information sequence of the same physical block at a symmetrical position and the number of times of erasing and writing The data of the two physical blocks whose difference satisfies the predetermined value is exchanged, and at the same time, the erasing times of the two physical blocks of the exchanged data are increased by one, and then the mapping between the two physical blocks of the exchanged data and their corresponding logical blocks Update the table to obtain the information sequence of the physical block after updating the number of erasing times and the mapping relationship, and then jump to step S101 to continue execution; if not, continue to step S102 to record the erasing times of the physical blocks in the same group.

Each physical block above corresponds to a physical address, each physical block corresponds to a logical block, each logical block corresponds to a logical address, and the physical address and logical address have a unique mapping relationship.

As a possible implementation, according to the usage rate of the physical blocks in the solid-state hard disk and the available storage space, the physical blocks in the solid-state hard disk are divided into multiple groups with the same number of physical blocks. Physical blocks with large differences are grouped, so that the effect of this wear-balancing strategy can be better exerted. The number of physical blocks in each group is N, and N is a natural number greater than 2, such as N=8;

Please refer to Figure 2, the physical blocks in this group are respectively marked as A, B, C, D, E, F, G and H, and the corresponding logical blocks are respectively a, b, c, d, e, f, g and h, there is a one-to-one mapping relationship between the physical address of each physical block and the logical address of the corresponding logical block, and the number of erasing and writing (pe_cnt) of each physical block in the initial state is recorded, A is 5, B is 8, C is 2, D is 6, E is 10, F is 1, G is 4, H is 7;

Please refer to Figure 3, sort the 8 physical blocks according to the erasing times (pe_cnt) from small to large, and get the information sequence of the physical blocks in this group in the initial state, pe_cnt_min points to the physical block with the smallest erasing times (pe_cnt), pe_cnt_max Point to the physical block with the largest erasing times (pe_cnt);

Please refer to Figure 4, after the erase operation is performed on the physical block, its erase count (pe_cnt) is updated. After multiple erasing and writing operations on physical blocks, A is 34, B is 47, C is 20, D is 36, E is 50, F is 12, G is 28, and H is 41. The erasing times (pe_cnt) are reordered from small to large to obtain the information sequence of the new physical block of this group, pe_cnt_min points to the physical block with the smallest erasing times (pe_cnt), and pe_cnt_max points to the physical block with the largest erasing times (pe_cnt). Piece;

Please refer to Figure 5, the threshold for setting the maximum number of erasing times of a physical block is set to 50*N, N is the number of physical blocks in each group, and the information sequence of the same physical block is in a symmetrical position for erasing two physical blocks The predetermined numerical value of the difference of times is set to ten. At this point, n=1, the threshold is 50, the number of erasing and writing of the physical block E has reached 50, and the physical block F is in a symmetrical position with the physical block E in this sequence, and the erasure of the physical block E and the physical block F The difference in the number of writes is also greater than 10, so the data of the physical block E and the physical block F are exchanged, and the number of erasing and writing of the physical block E and the physical block F is increased by 1, and the mapping table of the physical block E and the physical block F is updated , in the same way, the difference between physical block B and physical block C, physical block G and physical block H is also greater than 10, so the data of physical block B and physical block C are also exchanged, and physical block B and physical block are updated. For the mapping table of physical block C, add 1 to the erasing times of physical block B and physical block C, exchange the data of physical block G and physical block H, and update the mapping table of physical block G and physical block H, and convert the physical block The erasing times of G and physical block H are increased by 1; and the difference between the erasing times of physical block A and physical block D is less than 10, data exchange, erasing times are increased by 1, and the mapping table is updated, and finally updated The information sequence of the physical block after the erasing times and the mapping relationship; according to the usage rate of the physical block in the solid state drive and the available storage space, the physical block in the solid state drive is re-divided into multiple groups with the same number of physical blocks, In the next cycle, the logical addresses of the local physical blocks with too many write operations can be evenly mapped to the entire physical storage space, thereby avoiding local data overheating and prolonging the service life of the storage medium.

In the above embodiment, the logarithm of the physical blocks for data exchange on the information sequence of the same physical block is less than or equal to N/2, and the data exchange between physical blocks on the information sequence of multiple physical blocks, the number of times of erasing and writing increases 1 and the update of the mapping table can be performed in parallel, which makes wear leveling faster.

Example 2

As shown in Figure 6, a grouping mechanism-based solid state disk wear leveling method includes the following steps:

Step S201: Establish a double linked list data structure to maintain the information of each physical block;

Step S202: Divide the physical blocks in the solid state drive into multiple groups with the same number of physical blocks according to the usage rate and available storage space of the physical blocks in the solid state drive, and the number of physical blocks in each group is N;

Step S203: Record the erasing times of each physical block;

Step S204: After performing the erasing and writing operation on the physical blocks, reorder the physical blocks in the same group according to their erasing times from large to small to obtain a new information sequence of the physical blocks in this group;

Step S205: If the number of erasing and writing times of two physical blocks in the information sequence of the same physical block reaches a predetermined condition, exchange the data of the two physical blocks.

The above step S203 specifically includes: recording the erasing times of each physical block in the initial state; sorting the physical blocks of the same group according to their erasing times to obtain the information sequence of the physical blocks in the group in the initial state; erasing the physical blocks After the write operation, add one to the erasing and writing times of the physical block.

The above step S205 specifically includes: judging whether the maximum value of the erasing times of the physical blocks on the information sequence of the same physical block reaches the threshold value, and if so, sequentially assigning the information sequence of the same physical block that is in a symmetrical position and the number of erasing times The data of the two physical blocks whose difference satisfies the predetermined value is exchanged, and at the same time, the erasing times of the two physical blocks of the exchanged data are increased by one, and then the mapping between the two physical blocks of the exchanged data and their corresponding logical blocks Update the table to obtain the information sequence of the physical block after updating the number of erasing times and the mapping relationship, and jump to step S202 to continue execution; if not, continue to step S203 to record the erasing times of the physical blocks in the same group.

Each physical block above corresponds to a physical address, each physical block corresponds to a logical block, each logical block corresponds to a logical address, and the physical address and logical address have a unique mapping relationship.

As a possible implementation, a double linked list data structure is established to maintain the information of each physical block. The double linked list structure facilitates its sorting. The double linked list structure can also contain the head and tail pointers of the linked list, so that The pe_cnt_min and pe_cnt_max of the sequence members can be obtained directly. According to the usage rate and available storage space of the physical blocks in the solid-state hard disk, the physical blocks in the solid-state hard disk are divided into multiple groups with the same number of physical blocks. Grouping, so that the effect of this wear leveling strategy can be better played out, the number of physical blocks in each group is N, and N is a natural number greater than 2, such as N=10. The smaller N is, the fewer comparisons and data movements need to be performed within the sequence, but the number of physical blocks that can be optimized is also reduced. The larger N, the larger the number of physical blocks that can be optimized, but the larger the overhead of maintaining sequence ordering and data movement.

In this embodiment, the data exchange between the physical blocks on the information sequence of multiple physical blocks, the addition of 1 to the number of erasing and writing, and the updating of the mapping table can be performed in parallel, so that the speed of wear leveling is faster.

Example 3

As shown in Figure 7, a solid state disk wear leveling device based on a grouping mechanism includes the following modules:

The physical block grouping module 301 is used to divide the physical blocks in the solid-state hard disk into multiple groups with the same number of physical blocks according to the utilization rate and available storage space of the physical blocks in the solid-state hard disk;

A recording module 302, configured to record the number of times of erasing and writing of each physical block;

The sorting module 303 is used to reorder the physical blocks of the same group according to the number of times of erasing and writing to obtain a new information sequence of the physical blocks of this group after the physical blocks are erased and written;

The data exchange judging module 304 is used for exchanging the data of the above two physical blocks if the erasing times of the two physical blocks in the information sequence of the same physical block meet a predetermined condition.

The physical block grouping module 301 is sequentially connected to the recording module 302 , the sorting module 303 , and the data exchange judging module 304 .

Example 4

As shown in Figure 8, a solid state disk wear leveling device based on a grouping mechanism includes the following modules:

The physical block information maintenance module 307 is used to establish a data structure to maintain the information of each physical block;

The physical block grouping module 301 is used to divide the physical blocks in the solid-state hard disk into multiple groups with the same number of physical blocks according to the utilization rate and available storage space of the physical blocks in the solid-state hard disk;

A recording module 302, configured to record the number of times of erasing and writing of each physical block;

The sorting module 303 is used to reorder the physical blocks of the same group according to the number of times of erasing and writing to obtain a new information sequence of the physical blocks of this group after the physical blocks are erased and written;

Data exchange judging module 304: used for exchanging the data of the above two physical blocks if the number of erasing and writing times of the two physical blocks on the information sequence of the same physical block reaches a predetermined condition;

The data exchange judging module 304 further includes: a translation module 305, configured to translate the physical address of the physical block into the logical address of the corresponding logical block;

The data exchange judging module 304 further includes: a mapping table updating module 306, configured to update the mapping table of the two physical blocks and their corresponding logical blocks for exchanging data.

The physical block information maintenance module 307 is sequentially connected to the physical block grouping module 301, the recording module 302, the sorting module 303, and the data exchange judgment module 304, and the translation module 305 and the mapping table update module 306 are connected to the data exchange judgment module 304.

The above descriptions are only illustrative specific implementations of the present invention, and are not intended to limit the scope of the present invention. Any equivalent changes and modifications made by those skilled in the art without departing from the concepts and principles of the present invention are acceptable. Should belong to the protection scope of the present invention.

Claims (10)

1. A method for leveling wear of solid-state hard drives based on a grouping mechanism, characterized in that, comprising the following steps: S1: Divide the physical blocks in the solid state disk into multiple groups with the same number of physical blocks; S2: Record the number of erasing and writing of each physical block; S3: After the physical block is erased and written, the physical blocks of the same group are reordered according to their erasing and writing times, and a new information sequence of the physical block of the group is obtained; S4: If the erasing times of the two physical blocks in the information sequence of the same physical block meet a predetermined condition, exchange the data of the two physical blocks. 2. The method for wear leveling solid state disk based on grouping mechanism according to claim 1, characterized in that, before step S1, further comprising: establishing a data structure to maintain information of each physical block. 3. The solid-state disk wear leveling method based on grouping mechanism according to claim 1, characterized in that, step S2 specifically comprises: Record the number of erasing and writing of each physical block in the initial state; Sorting the physical blocks of the same group according to their erasing times to obtain the information sequence of the physical blocks of this group in the initial state; After the erasing and writing operation is performed on the physical block, the number of erasing and writing times of the physical block is increased by one. 4. The solid-state disk wear leveling method based on grouping mechanism according to claim 1, characterized in that, step S4 specifically comprises: Judging whether the maximum value of the erasing times of the physical block on the information sequence of the same physical block reaches the threshold value, if it reaches the threshold, then sequentially place the information sequence of the same physical block in a symmetrical position and the difference of the erasing times meets the predetermined value The data of the two physical blocks is exchanged, and at the same time, the number of erasing and writing of the two physical blocks of the exchanged data is increased by one, and then the mapping table of the two physical blocks of the exchanged data and their corresponding logical blocks is updated to obtain an updated erase After the write times and the information sequence of the physical block after the mapping relationship, jump to step S1 and continue to execute; if not, continue to step S2 to record the erasing times of the physical blocks in the same group. 5. The grouping mechanism-based solid state disk wear leveling method according to claim 1 or 3, wherein the sorting is performed from small to large or from large to small. 6. The solid state disk wear leveling method based on grouping mechanism according to claim 2, characterized in that, the data structure is a double linked list structure. 7. The solid state disk wear leveling method based on the grouping mechanism according to claim 1, wherein each physical block corresponds to a physical address, each physical block corresponds to a logical block, and each logical block corresponds to a logical block. address, the physical address and logical address have a unique mapping relationship. 8. The solid state disk wear leveling method based on a grouping mechanism according to claim 4, wherein the threshold is 50 times the number of physical blocks in each group. 9. The solid state disk wear leveling device based on the grouping mechanism of the solid state disk wear leveling method based on the grouping mechanism according to any one of claims 1 to 8, characterized in that, comprising: The physical block grouping module is used to divide the physical blocks in the solid state disk into multiple groups with the same number of physical blocks; A recording module for recording the number of erasing and writing of each physical block; The sorting module is used to reorder the physical blocks of the same group according to the number of times of erasing and writing after the physical blocks are erased and written, and obtain a new information sequence of the physical blocks of this group; Data exchange judging module: used for exchanging the data of the above two physical blocks if the erasing times of the two physical blocks in the information sequence of the same physical block meet a predetermined condition. 10. The solid-state disk wear leveling device based on grouping mechanism according to claim 9, further comprising: a physical block information maintenance module, which is used to establish a data structure to maintain the information of each physical block; Preferably, the data exchange judging module further includes: a translation module for translating the physical address of the physical block into the logical address of the corresponding logical block; the data exchange judging module further includes: a mapping table updating module for translating the The mapping table between the two physical blocks of data exchange and their corresponding logical blocks is updated.