CN106293521A - A kind of mapping granule adaptive flash translation layer (FTL) management method - Google Patents

Abstract

The invention discloses a flash memory conversion layer management method with self-adaptive mapping granularity, comprising: receiving a data request from a file system, and judging whether the type of the data request is a read request or a write request, and if it is a write request, according to the write request, query the page mapping table of the flash storage space to determine whether the logical page corresponding to the write request is not written for the first time, and if so, judge the type of the logical page according to the type corresponding to the logical page number in the page mapping table Whether it is a partial page or a complete page, if it is a partial page, set the subpage status in the subpage status table corresponding to the partial page to invalid, judge whether the size of the write request is greater than the size of the flash page, if so, start from the entire page to idle The leader of the queue takes out an idle physical page, and writes the data corresponding to the write request into the physical page. The invention can reduce the degradation of reading and writing performance and the waste of storage space caused by large-capacity flash memory page access.

Description

A flash translation layer management method with adaptive mapping granularity

technical field

The invention belongs to the technical field of solid-state disk storage, and more particularly relates to a flash memory conversion layer management method with self-adaptive mapping granularity.

Background technique

As the most widely used external storage device at present, the read and write performance of mechanical hard disk has gradually failed to meet the needs of upper-level applications, and the performance of storage devices has become the bottleneck of the overall performance of the computer system. In order to improve the performance of computer storage systems, in recent years, solid-state hard disks using NAND flash memory as storage media have been widely used. Solid-state drives have the characteristics of high bandwidth, low latency, low power consumption, good shock resistance, and no noise. They have partially replaced mechanical hard drives in the consumer market and enterprise-level storage, and have become one of the main storage devices. With the progress of flash memory manufacturing technology, the storage density of NAND flash memory chips is getting higher and higher, and the storage capacity is getting larger and larger. As the basic unit for reading and writing of flash memory, the capacity of flash memory page is also gradually increasing. From the previous 512 bytes, it has increased to 4KB and 8KB, and now there are 16KB page-sized single-level cell (Single-Level Cell, referred to as SLC) and multi-level cell (Multi-Level Cell, referred to as MLC) NAND flash memory chips , and may increase to 32KB or even larger in the future.

In order to provide an access interface compatible with mechanical hard disks, solid-state hard disks usually use a Flash Translation Layer (FTL for short) to hide the read, write, and erase operations of the flash memory from the upper layer. By using the flash translation layer, most file systems can be directly applied to SSDs. However, the size of the storage unit of the common file system, the file system block (File System Block, FSB for short), is basically fixed, and the storage unit of 4KB is usually used. The size of a flash page has reached several times that of a file system block. Taking a 16KB flash page as an example, four 4KB file system blocks can fill a flash page. If you need to update the 4KB data in a flash page, you need to read out the 16KB data in the entire flash page first, merge it with the 4KB update data, and then write it into a new flash page. It can be seen from Table 1 that before 2010, the flash memory page capacity of major NAND flash memory chips did not exceed 4KB. At this time, the contradiction between the flash memory page capacity and the file system block mismatch is not prominent. With the increase of flash page capacity, the impact of large-capacity flash pages on read and write performance becomes more and more obvious, and the commonly used flash translation layer method cannot solve this problem well.

Table 1 NAND flash memory and flash page capacity increase trend

Contents of the invention

In view of the above defects or improvement needs of the prior art, the present invention provides a mapping granularity adaptive flash translation layer management method (Mapping Granularity Adaptive Flash Translation Layer, referred to as MGA-FTL), the purpose of which is to use the flash memory unit can be The feature of repeated writing supports the allocation of storage space at the granularity of flash subpages and repeated writing of flash pages, which improves the space utilization and read/write performance of large-capacity flash pages. According to the granularity of different file system requests, MGA-FTL responds with a complete flash page or a part of a flash page, that is, uses a hybrid mapping management method of page-level mapping and sub-page level mapping. When the file system request size is the same as a flash page size, allocate a complete flash page to store the requested data; when the file system request size is smaller than a flash page size, allocate a subpage in the flash page to store the requested data, The remaining space in the flash page can be reserved for storing other requests smaller than the size of the flash page; in addition, the present invention proposes a subpage merge strategy. According to the access frequency of the file system request, the subpage merge strategy can better reduce the request access delay and achieve better system performance by limiting the number of file system requests that can be distributed in different flash pages.

In order to achieve the above object, according to one aspect of the present invention, a kind of mapping granularity adaptive flash memory conversion layer management method is provided, comprising the following steps:

(1) Receive a data request from the file system, and judge whether the type of the data request is a read request or a write request, if it is a write request, then enter step (2), if it is a read request, then enter step (9);

(2) query the page mapping table of the flash memory storage space according to the logical page number of this write request, to judge whether the logical page corresponding to this write request is not written for the first time, if it is then proceed to step (3), otherwise proceed to step (4);

(3) Judge whether the type of the logical page is a partial page or a complete page according to the type corresponding to the logical page number in the page mapping table, if it is a partial page, the subpage status in the subpage status table corresponding to the partial page is set to Invalidation, then proceed to step (4), if it is a complete page, the page status in the page state table corresponding to the complete page is set to invalidation, then proceed to step (4);

(4) judge whether the size of write request is greater than the size of flash memory page (it is usually 8kB or 16kB), if then proceed to step (5), otherwise proceed to step (6);

(5) Take out the free physical page from the head of the full page free queue, write the data corresponding to the write request into the physical page, and modify the page status in the page status table corresponding to the complete page to be all valid, and then process End; the full page free queue is established when the system is initialized, and is used to allocate free physical pages;

(6) Determine whether the allocation strategy of the write request is exclusive allocation or shared allocation, if it is exclusive allocation, go to step (7), if it is shared allocation, go to step (8).

(7) Find the subpage mapping table of the logical page number according to the subpage mapping table pointer corresponding to the logical page number in the page mapping table, and write the data corresponding to the write request into the same physical page. If there is no entry of the logical page number in the page mapping table, an entry is created and a free physical page is taken out from the head of the full page free queue for allocation. Then the process ends.

(8) Take out the free physical subpage from the head of the idle part of the page corresponding to the request size, write the data corresponding to the write request into the physical subpage, and write the subpage status in the subpage status table corresponding to the part of the page Set to valid, and then the process ends; some of the valid queues are dynamically established according to the usage of the full-page free queue, and are used to respond to write requests with a partial page data size;

(9) Judging whether the type of the logical page is a partial page or a complete page according to the type corresponding to the logical page number of the read request, if it is a partial page, then proceed to step (10), otherwise proceed to step (12).

(10) According to the physical subpage number corresponding to the logical page number of the read request in the subpage mapping table, read the data in the physical subpage, and add 1 to the read times counter of the logical page;

(11) According to the read times counter of the logical page and the number of physical pages associated with the logical page, it is judged whether it is necessary to merge scattered subpages, if necessary, the merge is performed, and then the process ends, otherwise the process ends.

(12) According to the physical page number corresponding to the logical page number of the read request in the page mapping table, read the data in the physical page, and then the process ends.

Preferably, step (2) is specifically, first query the page mapping table of the flash memory storage space, and judge whether there is a logical page number of the write request, if there is, it means that the logical page is not written for the first time, otherwise it means that it is the first time Write.

Preferably, the page mapping table structure includes a mapping table of two-level indexes, the first level is a page mapping table, and the entry includes a logical flash page number, a mapping type of the logical flash page and a corresponding physical flash page number, wherein if the logical flash page If the mapping type corresponding to the number is a partial page, the physical flash page number entry points to a second-level mapping table, called the subpage mapping table. The subpage mapping table entry includes the logical flash memory subpage number, and the logical flash memory subpage number corresponds to The physical flash page number, the specific physical flash subpage number in the flash page, and the number of physical pages associated with the logical page.

Preferably, the page state table structure includes a two-level flash page state table, the first level is a page state table, and the table items include the physical flash page number, the type of the physical flash page, and the state of the physical flash page, if the corresponding type of the physical flash page is For some pages, the state entry points to a subpage state table, and the subpage state table includes the physical subpage number, the state corresponding to the subpage, and the number of logical pages corresponding to the physical page.

Preferably, the free page queue includes a full page free queue and a partial page free queue. The full page free queue forms a queue with all flash memory pages that are free in the full page state, and the partial page free queue is divided into 3 sub-queues, each queue Next, do not mount flash pages with free space of 4KB, 8K, and 12KB. The conversion rule between these flash pages is that if there is still available space in the flash page after responding to the request, then link it into the corresponding free space. capacity queue.

Generally speaking, compared with the prior art, the above technical solutions conceived by the present invention can achieve the following beneficial effects:

1. The present invention is based on the repeated writing characteristics of flash memory pages, combined with specific flash memory chip access interfaces and characteristic parameters, and proposes a method for repeatedly writing large-capacity flash memory pages at the granularity of flash memory sub-pages, which reduces the need for hosts and Unnecessary data transfer between SSDs improves the utilization of flash storage space.

2. The present invention redefines the state and state transition diagram of the flash memory page. A "partially valid" flash page status has been added to describe flash pages where some subpages contain valid data. And define the transition relationship between this state and the original three states of "idle", "valid" and "expired" of the flash memory page, so as to be able to describe the physical state of the flash memory page more finely.

3. The present invention designs a two-level index address mapping table optimized for subpage-level mapping and page-level mapping, and allocates storage space for the subpage mapping table through dynamic memory allocation on the basis of page-level mapping. Sub-page-level mapping is used to process small-grained read and write requests of the file system, thereby solving the technical problem that the read and write unit of the file system is smaller than the flash memory page capacity.

4. The present invention proposes a method for fully utilizing the subpage space in the large-capacity flash memory page and preventing data distribution from being too scattered, and designs a method for subpage merging and garbage collection for the allocation scheme.

Description of drawings

FIG. 1 is a schematic diagram of flash memory cell write and write inhibit.

Fig. 2 is a schematic diagram of the data structure of the method of the present invention.

Fig. 3 shows a two-level index mapping table of the method of the present invention.

FIG. 4 shows a state transition diagram of a flash memory page in the method of the present invention.

FIG. 5 shows a flash memory page state table of the method of the present invention.

Fig. 6 shows the allocatable free page queue of the method of the present invention.

FIG. 7 shows the exclusive and shared subpage allocation methods of the method of the present invention.

Fig. 8 shows a schematic diagram of limiting the number of PPNs associated with an LPN in the method of the present invention.

FIG. 9 is a flow chart of the flash translation layer management method with self-adaptive mapping granularity of the present invention.

detailed description

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not constitute a conflict with each other.

The purpose of the present invention is to optimize the function of the flash conversion layer for solid-state hard drives using large-capacity flash pages, and reduce the decline in read and write performance and waste of storage space caused by large-capacity flash page access.

During the write operation of the flash memory page, all the flash memory cells in the same flash memory page share the programming voltage (Programming Voltage, denoted by the symbol Vp) on the corresponding word line. This voltage causes electrons in the semiconductor substrate to tunnel through the oxide layer into the floating gate. However, if the voltage of the conductive channel in the substrate is increased, the voltage drop across the oxide layer can be reduced, preventing electrons from tunneling into the floating gate, as shown in Figure 1. Figure 1(a) shows the flash memory cell in the writing state, the potential of the conductive channel is low, the electric field passing through the oxide layer is strong, and the electron capacity tunnels into the floating gate. Figure 1(b) shows a flash memory cell in a write-inhibited state. The potential of the conductive channel is high, and the electric field passing through the oxide layer is weak, so it is difficult for electrons to tunnel into the floating gate. The flash translation layer generally stipulates that after a flash page is written with data, only the flash block where the flash page is located is erased (it is "1" state after erasing), and data can be written to the flash page again. However, according to the above-mentioned write prohibition feature of the flash memory unit, if a certain bit of the flash page is "1", the bit can be modified to "0" without erasing until there is no "1" in the flash page. "until. That is, flash memory pages can be rewritten. When the flash page is repeatedly written, only a part of the flash page is modified, and the entire flash page does not need to be rewritten, which reduces the amount of transmitted data and the waste of flash memory storage space, and relatively increases the service life of the flash memory.

For convenience of description, symbols used in the present invention and their descriptions are listed in Table 2 below.

Table 2 Symbol Description

Two-level index mapping table:

MGA-FTL is a flash translation layer that combines page-level mapping and subpage-level mapping. It handles common granularity file system requests through page mapping and serves small granularity file system requests through subpage mapping. The mapping table adopts a method in which the primary mapping table is a page mapping table (Page Mapping Table, PMT), and the secondary mapping table is a subpage mapping table (Subpage Mapping Table, SPMT). In order to reduce the memory overhead of the mapping table, the secondary mapping table uses dynamic memory allocation, that is, only when the logical page needs to be written at the sub-page granularity, the memory of the secondary mapping table is allocated to it.

Figure 3 shows an example of a two-level index mapping table. The logical pages whose LPN is 0, 2, and 3 correspond to a complete flash memory page (type is FP) and directly perform page-level mapping, without the need for a secondary mapping table. Logical pages with LPN 1 and 4 correspond to some subpages of the flash memory page, and a secondary mapping table is required. At this time, the PPN field in the page mapping table entry stores a pointer to the secondary mapping table. In the subpage mapping table, the physical page number (PPN) and physical subpage number (PSPN) of each logical subpage mapping in the logical page are saved, and in addition, the physical page mapping of the logical page is also recorded The number (PPN Count) for reference during flash page allocation and merging. For the logical addresses that do not have a mapping relationship, their physical addresses are represented by "N/A" in the figure.

Flash space state information conversion:

Usually in the flash translation layer, the state of the physical flash page includes three types: free (Free), valid (Valid) and invalid (Invalid). Because MGA-FTL needs to represent the new state that some subpages in a flash page are valid, a new flash page state, Part Valid (PV), is added, which is used to describe the subpages in this flash page The situation where the data is stored for the unit. After adding this state, MGA-FTL contains four states in total, namely full page free (Full Free, FF), full page valid (Full Valid, FV), full page invalid (Full Invalid, FI) and partially valid. Figure 4 shows the conversion relationship of flash memory space state information in MGA-FTL.

MGA-FLT adds a two-level flash page state table for the new flash space state information conversion. FIG. 5 shows the information of the two-level flash memory page state table under the same storage situation as in FIG. 3 . The two-level flash page state table includes a flash page state table (Page State Table, PST) and a subpage state table (Subpage State Table, SPST). In Figure 5, the physical pages with PPNs of 0, 2, and 3 are used as complete flash memory pages, so the state is all valid (FV state); while the physical pages with PPNs of 1 and 4 only use part of the subpages, thus introducing Secondary state table. In the flash memory page with PPN 1, the subpages with PSPN 0, 1, and 2 store valid data (V state), while the subpage with PSPN 1 is idle (F state). The subpage usage of a flash page with a PPN of 4 is similar. In addition to recording the state of the physical subpage, the number of logical pages (LPN Count) corresponding to the physical page is also recorded. For example, the data in physical page PPN 1 comes from LPN 1 and LPN 4, so it is recorded as 2.

Flash memory free space allocation algorithm:

In MGA-FTL, free space available for allocation includes 1) a complete free flash page in FF state, and 2) a flash page in PV state and containing free subpages. Based on the assumption in Table 2 that a flash page size is 16KB and a flash subpage size is 4KB, MGA-FTL forms a queue of flash pages with the same maximum contiguous space that can be allocated, as shown in Figure 6, then the flash page in FF state A queue is formed, and the flash pages in the PV state are divided into three different queues, which are respectively used to respond to subpage requests of different sizes of 4KB, 8KB, and 12KB. If there is still available space in the flash memory page after responding to the request, then it is linked into the queue of corresponding free capacity. For the convenience of description, these flash page queues are divided into FF queue, PV4KB queue, PV8KB queue and PV12KB queue below.

When the file system request is smaller than the capacity of the flash page, it can be allocated a complete FF state flash page, or a PV state flash page containing enough free space. This introduces two different free space allocation strategies:

1) Exclusive Allocation (EA for short)

That is, the logical subpages belonging to the same logical page are allocated to the same physical page, that is, the physical page is exclusively occupied by the logical page, as shown in FIG. 7( a ). The advantage of exclusive allocation is that it reduces the overhead of subpage merging, but results in lower space utilization.

2) Shared Allocation (Shared Allocation, SA for short)

That is, logical subpages belonging to different logical pages can be allocated to the same physical page, as shown in FIG. 7( b ). The advantage of the shared allocation method is that the utilization rate of the subpage space is high, but the overhead of the merge operation is relatively large.

The two allocation methods have their own advantages and disadvantages. MGA-FTL introduces a parameter—AllocationThreshold (AT for short) to determine which allocation method to use, the ratio of AT and FF flash memory pages (that is, the proportion of free pages, Free Page Ratio, referred to as FPR), when FPR>=AT, there are enough free pages in the FF state in the system, and the EA allocation method is used to directly allocate free pages for responding to subpage requests. When FPR<AT, instead of consuming free pages in the FF state, use the SA allocation method to consume free subpages in the flash page in the PV state. When the free pages in the system increase with the garbage collection operation, and the FPR exceeds AT again, MGA-FTL uses the EA allocation method again. Additionally, the spatial locality of requests is taken into account when allocating free space.

The flash memory free space allocation algorithm is shown in Figure 8. When the file system write requests to allocate physical addresses, there are three methods: allocating complete flash memory pages, allocating free subpages by exclusive allocation, and allocating free subpages by shared allocation. Among them, the shared allocation selects appropriate flash memory pages from three queues with free spaces of flash memory pages of 4KB, 8KB, and 12KB respectively according to the size of the request.

Fragmented space merging algorithm and invalid data recovery algorithm:

In order to improve the utilization rate of large-capacity flash pages, MGA-FTL utilizes the unwritten free area in flash pages to handle file system requests at sub-page granularity. The problem caused by this is that the data of the same logical page may be distributed to different physical pages, resulting in the fragmentation of the flash memory storage space. When performing a read operation on a logical page, multiple physical pages need to be read, thereby reducing the read performance of the solid-state disk.

In response to this problem, MGA-FTL adopts the method of limiting the number of physical pages (PPN Count, PC) associated with a logical page for optimization, and refers to the number of reads (Read Count, RC) of the logical page. The basic idea is: The more times a logical page is read, the fewer physical pages associated with the logical page. According to the previous assumptions, when a 16KB flash memory page is used and the subpage capacity is 4KB, the number of physical pages that may be associated with the same logical page is at most 4. MGA-FTL is stipulated as follows: 1) RC==0, PC<=4; 2) 0<RC<=2, PC<=3; 3) 2<RC<=5, PC<=2; 4) RC> 5, PC=1.

When a logical page has not been read, its subpages can be written to multiple physical pages; as the number of reads increases, the number of associated physical pages decreases; when the logical page is read multiple times, the system will It is only allowed to store the logical page on one physical page, even if it causes extra space waste. As shown in FIG. 8( a ), it is assumed that four subpages LSPN 0 to 3 of a logical page LPN are distributed in physical pages PPN A and PPN B. The file system now issues a write operation to the last subpage LSPN 3 of this logical page. When the number RC of the LPN is 0, LSPN 3 can be written into the free subpage of the physical page PPN C in the PV4KB queue as shown in Figure 8(b), while LSPN 2 is still stored in the PPN In B, the number of physical pages associated with the LPN becomes 3. However, if the RC is 4, the PC cannot be greater than 2, that is, the number of physical pages associated with the LPN needs to be limited. At this time, LSPN 2 and LSPN 3 can be written to the physical pages in the PV8KB queue according to the method shown in Figure 8(c). In page PPN D, this will not increase the PC count of the LPN, but will cause redundant data migration of a subpage. If RC is 10, you need to copy all LSPN 0~3 to the physical page PPN E in the FF queue as shown in Figure 8(d). This process adds additional data migration of 3 subpages, but after When the LPN is read again, it only needs to be read from the PPN E, which reduces the overhead of the read operation.

The system uses a parameter - Garbage Collection Threshold (GCT for short) to determine the triggering timing of the garbage collection operation. When the proportion of free flash memory space is lower than the GCT, a garbage collection operation is triggered, and a flash memory block containing more invalid data is selected for recycling.

As shown in Figure 9, the flash memory conversion layer management method of the present invention with mapping granularity self-adaptation comprises the following steps:

(1) Receive a data request from the file system, and judge whether the type of the data request is a read request or a write request, if it is a write request, then enter step (2), if it is a read request, then enter step (9);

(2) query the page mapping table of the flash memory storage space according to the logical page number of this write request, to judge whether the logical page corresponding to this write request is not written for the first time, if it is then proceed to step (3), otherwise proceed to step (4); Specifically, at first query the page mapping table of the flash memory storage space, and judge whether there is a logical page number of the write request, if there is, it means that the logical page is not written for the first time, otherwise it means that it is written for the first time;

As shown in Figure 3, the page mapping table structure is given and an application example is listed. The page mapping table structure includes a mapping table with two levels of indexes. The first level is called the page mapping table. The entries include the logical flash page number (LPN), the mapping type (Type) of the logical flash page and the corresponding physical flash page number (PPN). ). If the mapping type corresponding to the logical flash page number is a partial page (PP), the physical flash page number entry points to a second-level mapping table, called a subpage mapping table. The subpage mapping table entry includes a logical flash subpage number (LSPN), which corresponds to a physical flash page number (PPN) and a specific physical flash subpage number (PSPN) in a flash page. In addition, The number of physical pages (PPN Count) associated with the logical page is also recorded for reference when allocating and merging flash memory pages. As shown in FIG. 3 , the logical pages with logical flash memory page numbers 0, 2, and 3 correspond to complete pages (type is FP) and directly perform page-level mapping without the need for a secondary mapping table. The logical pages with logical flash page numbers 1 and 4 correspond to some subpages of the flash page, and a secondary mapping table is required. At this time, the physical flash memory page number field in the page mapping table entry stores a pointer to the secondary mapping table.

(3) According to the type corresponding to the logical page number in the page mapping table, it is judged whether the type of the logical page is a partial page (Partial page, referred to as PP) or a complete page (Full page, referred to as FP). The subpage status in the subpage status table corresponding to the page is set to invalidation, and then proceeds to step (4), if it is a complete page, the page status in the corresponding page status table of the complete page is set to invalidation, and then proceeds to step ( 4);

Specifically, the subpage state table is dynamically generated under the state that the flash memory page is partially used, and is used to save the use state of the flash memory subpage; its specific state transition process is shown in Figure 4;

As shown in Figure 5, the structure of the page state table and the state table information corresponding to the mapping example in Figure 3 are given. The page state table structure includes a two-level flash page state table, the first level is called the page state table, and the entries include the physical flash page number (PPN), the type (Type) of the physical flash page and the physical flash page state (State). If the corresponding type of the physical flash memory page is a partial page (PP), the state entry points to a subpage state table. The subpage state table includes the physical subpage number (PSPN) and the state corresponding to the subpage (State), and also includes the number of logical pages (LPN Count) corresponding to the physical page. The corresponding example situation is as shown in Figure 5, the physical pages whose physical flash memory page numbers are 0, 2, and 3 are used as complete flash memory pages, so the state is all valid (FV state); and the physical flash memory page numbers are 1,4 The physical page only uses part of the subpages, thus introducing a secondary state table. In the flash memory page whose physical flash page number is 1, the subpages whose physical subpage numbers are 0, 1, and 2 store valid data (V state), while the subpage whose physical subpage number is 3 is idle (F state).

(4) judge whether the size of write request is greater than the size of flash memory page (it is usually 8kB or 16kB), if then proceed to step (5), otherwise proceed to step (6);

(5) Take out the free physical page from the head of the full page free queue, write the data corresponding to the write request into the physical page, and modify the page status in the page status table corresponding to the complete page to be all valid; The page free queue is established when the system is initialized to allocate free physical pages; then the process ends.

As shown in FIG. 6 , a schematic diagram of a free page queue that can be allocated in a flash memory system is given. The free page queue includes a full page free queue and a partial page free queue. The full-page free queue forms a queue of all flash pages whose status is full-page free; the partial-page free queue is divided into three sub-queues, and each queue mounts flash pages with free space of 4KB, 8K, and 12KB. The conversion rule among them is, if there is still available space in the flash memory page after responding to the request, then it will be linked into the queue of corresponding free capacity.

(6) Determine whether the allocation strategy of the write request is Exclusive Allocation (EA for short) or Shared Allocation (Shared Allocation, SA for short). If it is exclusive allocation, go to step (7); if it is shared allocation, go to Enter step (8).

(7) Find the subpage mapping table of the logical page number according to the subpage mapping table pointer corresponding to the logical page number in the page mapping table, and write the data corresponding to the write request into the same physical page. If there is no entry of the logical page number in the page mapping table, an entry is created and a free physical page is taken out from the head of the full page free queue for allocation. Then the process ends.

As shown in Figure 7, the allocation strategy includes exclusive allocation, otherwise shared allocation. Exclusive allocation is to allocate logical subpages belonging to the same logical page to the same physical page, and the physical page is exclusively occupied by the logical page. Shared allocation allows logical subpages of different logical pages to be allocated to the same physical page.

The description of the flash memory free space allocation algorithm is shown in Figure (8).

(8) Take out the free physical subpage from the head of the idle part of the page corresponding to the request size, write the data corresponding to the write request into the physical subpage, and write the subpage status in the subpage status table corresponding to the part of the page Set to valid; some of the valid queues are dynamically established according to the usage of the full-page free queue, and are used to respond to write requests with a partial page data size. Then the process ends.

(9) Judging whether the type of the logical page is a partial page or a complete page according to the type corresponding to the logical page number of the read request, if it is a partial page, then proceed to step (10), otherwise proceed to step (12).

(10) According to the physical subpage number corresponding to the logical page number of the read request in the subpage mapping table, read the data in the physical subpage, and add 1 to the read counter (Read Count, referred to as RC) of the logical page;

(11) According to the read times counter of the logical page and the number of physical pages associated with the logical page, judge whether to merge scattered subpages, if necessary, merge, and then transfer to (end); otherwise transfer to (13).

Specifically, the merging rules are stipulated as follows: 1) RC==0, PC<=4; 2) 0<RC<=2, PC<=3; 3) 2<RC<=5, PC<=2; 4 )RC>5, PC=1.

As shown in Figure (9), it is a schematic diagram of an example of a merge operation. As shown in FIG. 8( a ), it is assumed that four subpages LSPN 0 to 3 of an existing logical page LPN are distributed in physical pages PPN A and PPN B. As shown in FIG. 8( b ), the file system issues a write operation to the last subpage LSPN 3 of the logical page. When the number RC of the LPN is 0, write LSPN 3 into the free subpage of the physical page PPN C in the PV4KB queue, while LSPN 2 is still stored in PPN B, and the number of physical pages associated with the LPN becomes 3 . As shown in Figure 8(c), if RC is 4 and PC cannot be greater than 2, write LSPN 2 and LSPN 3 into the physical page PPN D in the PV8KB queue. As shown in Figure 8(d), if RC is 10, all LSPNs 0-3 are copied to the physical page PPN E in the FF queue.

(12) According to the physical page number corresponding to the logical page number of the read request in the page mapping table, read the data in the physical page, and then the process ends.

The experimental results show that, compared with the common page-mapped flash translation layer method, MGA-FTL effectively reduces the data transmission time and the waste of flash storage space caused by the increase of flash page capacity. In the real load tested, it can reduce the average response time of requests by up to 53%, the write amplification of SSD by 30%, and the erase operation of flash block by 40%.

Those skilled in the art can easily understand that the above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, All should be included within the protection scope of the present invention.

Claims (5)

1. A method for managing flash memory conversion layer of mapping granularity self-adaption, is characterized in that, comprises the following steps: (1) Receive a data request from the file system, and judge whether the type of the data request is a read request or a write request, if it is a write request, then enter step (2), if it is a read request, then enter step (9); (2) query the page mapping table of the flash memory storage space according to the logical page number of this write request, to judge whether the logical page corresponding to this write request is not written for the first time, if it is then proceed to step (3), otherwise proceed to step (4); (3) Judge whether the type of the logical page is a partial page or a complete page according to the type corresponding to the logical page number in the page mapping table, if it is a partial page, the subpage status in the subpage status table corresponding to the partial page is set to Invalidation, then proceed to step (4), if it is a complete page, the page status in the page state table corresponding to the complete page is set to invalidation, then proceed to step (4); (4) judge whether the size of write request is greater than the size of flash memory page (it is usually 8kB or 16kB), if then proceed to step (5), otherwise proceed to step (6); (5) Take out the free physical page from the head of the full page free queue, write the data corresponding to the write request into the physical page, and modify the page status in the page status table corresponding to the complete page to be all valid, and then process End; the full page free queue is established when the system is initialized, and is used to allocate free physical pages; (6) Determine whether the allocation strategy of the write request is exclusive allocation or shared allocation, if it is exclusive allocation, go to step (7), if it is shared allocation, go to step (8). (7) Find the subpage mapping table of the logical page number according to the subpage mapping table pointer corresponding to the logical page number in the page mapping table, and write the data corresponding to the write request into the same physical page. If there is no entry of the logical page number in the page mapping table, an entry is created and a free physical page is taken out from the head of the full page free queue for allocation. Then the process ends. (8) Take out the free physical subpage from the head of the idle part of the page corresponding to the request size, write the data corresponding to the write request into the physical subpage, and write the subpage status in the subpage status table corresponding to the part of the page Set to valid, and then the process ends; some of the valid queues are dynamically established according to the usage of the full-page free queue, and are used to respond to write requests with a partial page data size; (9) Judging whether the type of the logical page is a partial page or a complete page according to the type corresponding to the logical page number of the read request, if it is a partial page, then proceed to step (10), otherwise proceed to step (12). (10) According to the physical subpage number corresponding to the logical page number of the read request in the subpage mapping table, read the data in the physical subpage, and add 1 to the read times counter of the logical page; (11) According to the read times counter of the logical page and the number of physical pages associated with the logical page, it is judged whether it is necessary to merge scattered subpages, if necessary, the merge is performed, and then the process ends, otherwise the process ends. (12) According to the physical page number corresponding to the logical page number of the read request in the page mapping table, read the data in the physical page, and then the process ends. 2. the flash memory conversion layer management method according to claim 1, is characterized in that, step (2) is specially, at first inquires the page mapping table of flash storage space, and judges whether there is the logic page number of writing request wherein, if there is It means that the logical page is not written for the first time, otherwise it means that it is written for the first time. 3. the flash memory translation layer management method according to claim 1, is characterized in that, The page mapping table structure includes a mapping table with two levels of indexes. The first level is the page mapping table, and the table entries include the logical flash page number, the mapping type of the logical flash page and the corresponding physical flash page number. If the logical flash page number corresponds to the mapping If the type is a partial page, the physical flash page number table entry points to a second-level mapping table, called the subpage mapping table; The subpage mapping table entry includes a logical flash memory subpage number corresponding to a physical flash memory page number, a specific physical flash memory subpage number in a flash memory page, and the number of physical pages associated with the logical page. 4. the flash memory translation layer management method according to claim 1, is characterized in that, The page state table structure includes a two-level flash page state table, the first level is a page state table, and the table items include the physical flash page number, the type of the physical flash page, and the physical flash page state; If the corresponding type of the physical flash memory page is a partial page, the state entry points to a subpage state table, and the subpage state table includes the physical subpage number, the state corresponding to the subpage, and the number of logical pages corresponding to the physical page. 5. the flash memory conversion layer management method according to claim 1, is characterized in that, The free page queue includes a full page free queue and a partial page free queue; The full-page free queue forms a queue of all flash pages whose status is full-page free; Partial page free queues are divided into 3 sub-queues, and flash pages with free space of 4KB, 8K, and 12KB are respectively mounted under each queue. The conversion rule between these flash pages is that if there are still If there is space available, it will be linked into the corresponding free capacity queue.