CN106293521B - A kind of flash translation layer (FTL) management method that mapping granule is adaptive - Google Patents
A kind of flash translation layer (FTL) management method that mapping granule is adaptive Download PDFInfo
- Publication number
- CN106293521B CN106293521B CN201610623356.XA CN201610623356A CN106293521B CN 106293521 B CN106293521 B CN 106293521B CN 201610623356 A CN201610623356 A CN 201610623356A CN 106293521 B CN106293521 B CN 106293521B
- Authority
- CN
- China
- Prior art keywords
- page
- subpage
- logical
- flash
- memory pages
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
- G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
- G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/0608—Saving storage space on storage systems
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0629—Configuration or reconfiguration of storage systems
- G06F3/0631—Configuration or reconfiguration of storage systems by allocating resources to storage systems
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0673—Single storage device
- G06F3/0679—Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/72—Details relating to flash memory management
- G06F2212/7201—Logical to physical mapping or translation of blocks or pages
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Human Computer Interaction (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a kind of flash translation layer (FTL) management methods that mapping granule is adaptive, it include: to receive request of data from file system, and judge that the type of the request of data is read request or write request, if it is write request, the page map table of flash memory space is then inquired according to the logical page number (LPN) of the write request, to judge whether the corresponding logical page (LPAGE) of the write request is not to write for the first time, if it is judge that the type of the logical page (LPAGE) is partial page or the complete page according to the corresponding type of the logical page number (LPN) in page map table, then the subpage state in the corresponding subpage state table of the partial page is set as failing if it is partial page, judge whether the size of write request is greater than the size of Hash memory pages, if it is idle Physical Page is taken out from the head of the queue of whole page idle queues, the corresponding data of write request are written in the Physical Page.The present invention can reduce the decline of readwrite performance caused by high-capacity flash memory access to web page and waste of storage space.
Description
Technical field
The invention belongs to solid-state disk technical field of memory, turn more particularly, to a kind of flash memory that mapping granule is adaptive
Change layer-management method.
Background technique
As most widely used at present peripheral storage device, the readwrite performance of mechanical hard disk is not able to satisfy upper layer gradually
The demand of application, the performance for storing equipment have become the bottleneck of computer system overall performance.In order to improve computer storage
The performance of system is had been widely used using the solid state hard disk with nand-type (NAND) flash memory as storage medium in recent years.Gu
State hard disk has the characteristics that high bandwidth, low latency, low-power consumption, shock resistance are good, noiseless, in consumer level market and enterprise-level
Mechanical hard disk is partially substituted in storage, becomes one of main storage equipment.With the progress of flash memory fabrication technique, NAND type is dodged
The storage density for depositing chip is higher and higher, and memory capacity is increasing.As the basic unit of flash reading and writing, the capacity of Hash memory pages
Also the trend gradually increased is presented.From 512 previous bytes, increase to 4KB, 8KB, has already appeared 16KB pages of size now
Single layer cell (Single-Level Cell, abbreviation SLC) and multilevel-cell (Multi-Level Cell, abbreviation MLC) NAND type
Flash chip, future are also possible to increase to 32KB even more big.
In order to provide the access interface of compatible mechanical hard disk, solid state hard disk generallys use flash translation layer (FTL) (Flash
Translation Layer, abbreviation FTL) reading and writing, the erasing operation of flash memory are hidden to upper layer.By using flash translation layer (FTL),
Most of file system can be directly applied in solid state hard disk.And the storage cell file system blocks of common file systems
The size of (File System Block, abbreviation FSB) is substantially stationary, usually all uses the storage cell of 4KB.The appearance of Hash memory pages
Amount has reached the several times of file system blocks.By taking the Hash memory pages of 16KB as an example, the file system blocks of 4 4KB can just fill up one
Hash memory pages.If necessary to update the data of 4KB in a Hash memory pages, need first to read the data of 16KB in entire Hash memory pages,
With 4KB after more new data merges, then be written in a new Hash memory pages.As shown in Table 1, before 2010, main NAND
The Hash memory pages capacity of type flash chip is no more than 4KB.At this point, Hash memory pages capacity and the unmatched contradiction of file system blocks is not convex
It is aobvious.With the increase of Hash memory pages capacity, influence of the high-capacity flash memory page to readwrite performance is more and more obvious, common flash memory conversion
Layer method not can solve this problem.
1 NAND-type flash memory of table and Hash memory pages capacity increase tendency
Summary of the invention
Aiming at the above defects or improvement requirements of the prior art, the present invention provides a kind of flash memories that mapping granule is adaptive
Conversion layer management method (Mapping Granularity Adaptive Flash Translation Layer, abbreviation MGA-
FTL), it is intended that the characteristic of write-in can be repeated using flash cell, support to distribute storage by granularity of flash memory subpage
Space and Hash memory pages are repeatedly written, improve the space utilization rate and readwrite performance of high-capacity flash memory page.MGA-FTL needle
It to the granularity of different file system requests, is responded using complete Hash memory pages or Hash memory pages segment space, that is, uses page
Grade mapping and the mapping of subpage grade mix the management method of mapping.When file system requests size is identical as a Hash memory pages size
When, the data of the complete Hash memory pages storage request of distribution one；When file system requests size is less than a Hash memory pages size,
A subpage in distribution Hash memory pages stores the data of request, and remaining space can be preserved for storing it in the Hash memory pages
He is less than the request of Hash memory pages size；In addition, the present invention is by proposing a kind of subpage consolidation strategy.Subpage consolidation strategy is according to this
The frequency of file system requests access can be distributed in the number in different Hash memory pages by limiting file system requests, more preferably
Reduction request access delay, so that system is reached better performance.
To achieve the above object, according to one aspect of the present invention, a kind of flash memory that mapping granule is adaptive turn is provided
Change layer-management method, comprising the following steps:
(1) request of data is received from file system, and judges that the type of the request of data is read request or write request, such as
Fruit is write request, then enters step (2), if it is read request, then enters step (9)；
(2) page map table of flash memory space is inquired, according to the logical page number (LPN) of the write request to judge the write request pair
Whether the logical page (LPAGE) answered is not to write for the first time, is if it is transferred to step (3), is otherwise transferred to step (4)；
(3) according to the corresponding type of the logical page number (LPN) in page map table judge the logical page (LPAGE) type be partial page or
Subpage state in the corresponding subpage state table of the partial page then is set as failing by the complete page if it is partial page,
Then step (4) are transferred to, then are set as failing by the page status in the corresponding page status table in complete page face if it is the complete page,
Then step (4) are transferred to；
(4) judge whether the size of write request is greater than the size (it is usually 8kB or 16kB) of Hash memory pages, if it is
Step (5) are transferred to, step (6) are otherwise transferred to；
(5) idle Physical Page is taken out from the head of the queue of whole page idle queues, and the physics is written into the corresponding data of write request
In page, and the page status in the corresponding page status table in complete page face is revised as all effectively, then process terminates；Wherein whole page
It is established when idle queues are system initializations, for distributing idle Physical Page；
(6) allocation strategy for judging write request is exclusive formula distribution or shared distribution, is turned if it is the distribution of exclusive formula
Enter step (7), is transferred to step (8) if it is shared distribution.
(7) subpage LMT pointer is corresponded to according to the logical page number (LPN) in page map table, the subpage for finding the logical page number (LPN) reflects
The corresponding data of write request are written in the same Physical Page firing table.If there is no the list item of the logical page number (LPN) in page map table,
Creation list item is simultaneously allocated in the Physical Page that the head of the queue of whole page idle queues takes out the free time.Then process terminates.
(8) idle physics subpage is taken out from the head of the queue of request size corresponding partial page free time, write request is corresponding
Data are written in the physics subpage, and set the subpage state in the corresponding subpage state table of partial page to effectively, then
Process terminates；Part of effectively queue is established according to the service condition dynamic of whole page idle queues, and response section is used for
The write request of page data size；
(9) judge that the type of the logical page (LPAGE) is partial page or complete according to the corresponding type of the logical page number (LPN) of the read request
The whole page is then transferred to step (10) if it is partial page, is otherwise transferred to step (12).
(10) it according to the corresponding physics subpage number of the logical page number (LPN) of the read request in subpage mapping table, reads in physics subpage
Data, and the reading number counter of the logical page (LPAGE) is added 1；
(11) according to the reading number counter of the logical page (LPAGE) and the associated Physical Page quantity of the logical page (LPAGE), judge whether to need
The subpage for merging dispersion, merges if necessary, and then process terminates, and else process terminates.
(12) according to the corresponding physical page number of logical page number (LPN) of the read request in page map table, data in Physical Page are read,
Then process terminates.
Preferably, step (2) specifically, inquire the page map table of flash memory space, and judge wherein whether have first
The logical page number (LPN) of write request is to write for the first time if there is then indicating logical page (LPAGE) not, otherwise indicates it is to write for the first time.
Preferably, page map table structure includes the mapping table of two-stage index, and the first order is page map table, and list item includes logic
Flash memory page number, the map type of the logical flash page and corresponding physics Hash memory pages number, wherein if logical flash page number correspondence is reflected
Penetrating type is partial page, then physical flash page number list item is directed toward a second level mapping table, and referred to as subpage mapping table, subpage reflects
Firing table list item includes logical flash subpage number, specific object in the corresponding physics Hash memory pages number of the logical flash subpage number, Hash memory pages
Manage flash memory subpage number, the associated Physical Page quantity of the logical page (LPAGE).
Preferably, page status table structure includes two-stage Hash memory pages state table, and the first order is page status table, and list item includes physics
Flash memory page number, the type of physical flash page and physical flash page status, if physical flash page corresponding types are partial page
Face, then state list item be directed toward a sub- page status table, the subpage state table include physics subpage number, subpage corresponding states and
The quantity of the corresponding logical page (LPAGE) of Physical Page.
Preferably, free page queue includes a whole page idle queues and a partial page idle queues, whole page free time team
Stateful Hash memory pages one queue of composition for the whole page free time of institute, partial page idle queues are divided into 3 subqueues, every team by column
The lower anti-other carry free space of column is the Hash memory pages of 4KB, 8K and 12KB size, and the transformation rule between these Hash memory pages is, such as
There are also available space in the Hash memory pages after fruit respond request, then in the queue that its chain is entered to respective free capacity again.
In general, through the invention it is contemplated above technical scheme is compared with the prior art, can obtain down and show
Beneficial effect:
1, it is repeatedly written characteristic the present invention is based on Hash memory pages, joined in conjunction with specific flash chip access interface and characteristic
It is several, a kind of method being repeatedly written as granularity to high-capacity flash memory page using flash memory subpage is proposed, reduces host and consolidates
Unnecessary data transmission between state hard disk, and then improve the utilization rate of flash memory space.
2, the present invention has redefined the state and state transition graph of Hash memory pages.Increase the flash memory of one " part is effectively "
Page status includes the Hash memory pages of valid data for description section subpage.And it defines the state and Hash memory pages is original " empty
Transformational relation between spare time ", " effective " and " expired " three states, it is more fine from that can be carried out to Hash memory pages physical state
Description.
3, the present invention devises the address mapping table of the two-stage index optimized for the mapping of subpage grade and the mapping of page grade,
On the basis of the mapping of page grade, memory space is distributed for subpage mapping table by way of dynamic memory distribution.Using subpage grade
The small grain size read-write requests of mapping processing file system, thus solve the skill that file system read-write unit is less than Hash memory pages capacity
Art problem.
4, the invention proposes one kind not only to have made full use of the subpage space in high-capacity flash memory page, but also prevents data distribution mistake
In the method for dispersion, and for the method that the allocation plan devises subpage merging and garbage reclamation.
Detailed description of the invention
Fig. 1 is the schematic diagram of flash cell write-in and writing prohibition.
Fig. 2 is the data structure schematic diagram of the method for the present invention.
Fig. 3 shows the two-stage index mapping table of the method for the present invention.
Fig. 4 shows the Hash memory pages state transition graph of the method for the present invention.
Fig. 5 shows the Hash memory pages state table of the method for the present invention.
What Fig. 6 showed the method for the present invention distributes free page queue.
Fig. 7 shows the exclusive formula and the shared formula page method of salary distribution of the method for the present invention.
Fig. 8 shows the schematic diagram that the associated PPN quantity of LPN is limited in the method for the present invention.
Fig. 9 is the flow chart of the adaptive flash translation layer (FTL) management method of mapping granule of the present invention.
Specific embodiment
In order to make the objectives, technical solutions, and advantages of the present invention clearer, with reference to the accompanying drawings and embodiments, right
The present invention is further elaborated.It should be appreciated that the specific embodiments described herein are merely illustrative of the present invention, and
It is not used in the restriction present invention.As long as in addition, technical characteristic involved in the various embodiments of the present invention described below
Not constituting a conflict with each other can be combined with each other.
It is an object of the present invention to optimize the function of flash translation layer (FTL) for the solid state hard disk using high-capacity flash memory page,
Reduce the decline of readwrite performance caused by high-capacity flash memory access to web page and waste of storage space.
In Hash memory pages write operation, voltage is written in the shared corresponding wordline of all flash cells in same Hash memory pages
(Programming Voltage is indicated with symbol Vp).The voltage passes through the electronics in semiconductor substrate using tunnel-effect
Oxide layer enters in floating gate.But if improving the voltage of conducting channel in substrate, so that it may reduce the voltage in oxide layer
Drop, to prevent electronics from entering floating gate using tunnel-effect, as shown in Figure 1.Fig. 1 (a) is the flash cell in write state,
Conducting channel potential is low, and across the electric-field strength of oxide layer, electron capacitance occurs tunnel-effect and enters floating gate.Fig. 1 (b) is in writing
Enter the flash cell of illegal state, conducting channel potential is high, and the electric field across oxide layer is weak, and tunnel-effect is less likely to occur electronics
Into floating gate.Flash translation layer (FTL) usually provides after a Hash memory pages are written into data, only to the flash memory where the Hash memory pages
Block is wiped (being one state after erasing), data could be written to the Hash memory pages again.But according to above-mentioned flash memory list
First writing prohibition characteristic, if a certain position of Hash memory pages is that the position can be revised as " 0 ", directly by " 1 " in the case where not wiping
Into Hash memory pages there is no until " 1 ".I.e. Hash memory pages can be repeated write-in.When Hash memory pages are repeatedly written, only modify
Partial region in Hash memory pages does not need to re-write entire Hash memory pages, reduces transmitted data amount and flash memory space
Waste, it is also opposite to enhance the service life of flash memory.
For convenience of description, the symbol used in the present invention and their explanation are listed in the following table 2.
2 symbol description of table
Two-stage index mapping table:
MGA-FTL is that a kind of page of grade mapping and subpage grade map the flash translation layer (FTL) mixed, is handled by page mapping
The file system requests of normal granulometry service the file system requests of small grain size by subpage mapping.Mapping table uses level-one
Mapping table is page map table (Page Mapping Table, PMT), and second level mapping table is subpage mapping table (Subpage
Mapping Table, SPMT) mode.In order to reduce the memory overhead of mapping table, second level mapping table is using dynamic memory point
Match, i.e., only when logical page (LPAGE) needs to carry out the write-in of subpage granularity, just distributes second level mapping table memory for it.
Fig. 3 gives an example case of two-stage index mapping table.The logical page (LPAGE) that wherein LPN is 0,2,3 is corresponding complete
Hash memory pages (type FP) directly carry out the mapping of page grade, do not need second level mapping table.The logical page (LPAGE) that LPN is 1,4 corresponds to flash memory
The part subpage of page, needs using second level mapping table.At this point, the PPN field in page map table list item store be directed to second level
The pointer of mapping table.In subpage mapping table, the physical page number (PPN) of each logic subpage mapping in the logical page (LPAGE) is saved
In addition to this quantity (PPN Count) of the Physical Page of logical page (LPAGE) mapping is also recorded, uses with physics subpage number (PSPN)
It is referred in when Hash memory pages are distributed and are merged.For the logical address of mapping relations is not present, physical address is in figure
It is indicated with " N/A ".
The conversion of flash memory space status information:
Usually in flash translation layer (FTL), the state of physical flash page includes idle (Free), effective (Valid) and invalid
(Invalid) three kinds.Because MGA-FTL needs to indicate effectively this new state of the part subpage in a Hash memory pages, add
A new flash memory page status is added, part is effective (Part Valid, PV), for describing in this Hash memory pages with subpage as list
The situation of position storage data.After adding this state, MGA-FTL includes four states altogether, i.e., whole page idle (Full Free, FF),
Whole page effectively (Full Valid, FV), whole page invalid (Full Invalid, FI) and part are effectively.Fig. 4 gives MGA-FTL
Middle flash memory space status information transformational relation.
MGA-FLT is converted for new flash memory space status information, increases two-stage Hash memory pages state table.Fig. 5 gives
Two-stage Hash memory pages state table information under storage situation identical as Fig. 3.Two-stage Hash memory pages state table includes Hash memory pages state table
(Page State Table, PST) and subpage state table (Subpage State Table, SPST).In Fig. 5, PPN 0,2,3
Physical Page used as complete Hash memory pages, therefore state be all effectively (FV states)；And PPN is the Physical Page of Isosorbide-5-Nitrae
Part subpage has been used, thus has introduced second level state table.In the Hash memory pages that PPN is 1, the subpage of PSPN 0,1,2 is saved
Valid data (V state), and the subpage that PSPN is 1 is idle (F state).The subpage service condition and its class for the Hash memory pages that PPN is 4
Seemingly.State in addition to recording physics subpage, is also recorded the quantity (LPN Count) of the corresponding logical page (LPAGE) of the Physical Page.For example,
Data in Physical Page PPN 1 are denoted as 2 from LPN 1 and LPN 4.
Flash memory free space allocation algorithm:
In MGA-FTL, complete free flash memory page of the distributable free space including 1) being in FF state, 2) at
It in PV state, and include the Hash memory pages of idle subpage.Based on table 2 it is big to a Hash memory pages size 16KB and a flash memory subpage
Small 4KB's it is assumed that the identical Hash memory pages of assignable maximum continuous space are formed a queue by MGA-FTL, as shown in fig. 6,
Then the Hash memory pages of FF state form a queue, and the Hash memory pages of PV state are then divided into three different queues, are respectively used to respond
The different size of subpage request of 4KB, 8KB and 12KB.If there are also available spaces in the Hash memory pages after respond request, then
In the queue that its chain is entered to respective free capacity.For convenience of description, hereafter by these Hash memory pages queues be divided into as FF queue,
PV4KB queue, PV8KB queue and PV12KB queue.
When file system requests are less than Hash memory pages capacity, the Hash memory pages of a complete FF state can be distributed for it,
The Hash memory pages of a PV state comprising enough free spaces can also be distributed.Thus two different free spaces point are introduced
With strategy:
1) the formula method of salary distribution (Exclusive Allocation, abbreviation EA) is monopolized
The logic subpage that the same logical page (LPAGE) will be belonged to is assigned in the same Physical Page, i.e., the Physical Page is by logic
Page is exclusive, as shown in Fig. 7 (a).The advantages of exclusive formula distribution, resides in reduced expense when subpage merges, but causes space
Utilization rate is lower.
2) the shared method of salary distribution (Shared Allocation, abbreviation SA)
The logic subpage for belonging to Different Logic page can be assigned in the same Physical Page, as shown in Fig. 7 (b).Altogether
It is high that the advantages of enjoying the formula method of salary distribution is subpage space utilization rate, but the expense of union operation is larger.
Two kinds of methods of salary distribution respectively have its advantage and disadvantage, and MGA-FTL introduces a parameter --- allocation threshold (Allocation
Threshold, abbreviation AT) determine use which kind of method of salary distribution, the Hash memory pages of AT and FF state ratio (i.e. free page ratio,
Free Page Ratio, abbreviation FPR) it is related, as FPR >=AT, the free page in system in FF state is sufficient, uses EA
The method of salary distribution directly distributes free page for responding subpage request.As FPR < AT, not in consumption FF idle page, then
Using the SA method of salary distribution, the idle subpage in the Hash memory pages of PV state is consumed.When in system free page with garbage collection operation
Progress by increasing, when FPR is again above AT, MGA-FTL reuses the EA method of salary distribution.In addition, in allocation of free space,
Further account for the spatial locality of request.
Flash memory free space allocation algorithm is as shown in Figure 8.When file system write request allocated physical address, it is divided into and distributes
Whole Hash memory pages distribute idle subpage using exclusive formula distribution method, distribute idle three kinds of subpage using the shared method of salary distribution
Mode.Wherein, shared distribution is again according to the size of request, respectively from three that Hash memory pages free space is 4KB, 8KB, 12KB
Suitable Hash memory pages are chosen in queue.
Fragment space merges algorithm and invalid data recycles algorithm:
MGA-FTL in order to improve the utilization rate of high-capacity flash memory page, using the free area being not written into Hash memory pages come
Handle the file system requests of subpage granularity.Difference may be distributed to by doing so the data that the problem of bringing is the same logical page (LPAGE)
Physical Page in, cause the fragmentation of flash memory space.When carrying out read operation to logical page (LPAGE), need to read multiple physics
Page, to reduce the reading performance of solid state hard disk.
For this problem, MGA-FTL use limitation one associated Physical Page of logical page (LPAGE) quantity (PPN Count,
PC method) optimizes, and with reference to the reading number (Read Count, RC) of logical page (LPAGE), basic ideas are: one is patrolled
The reading number for collecting page is more, and the associated Physical Page of the logical page (LPAGE) is fewer.According to above it is assumed that when the Hash memory pages using 16KB
And subpage capacity is when being 4KB, same logical page (LPAGE) may associated Physical Page quantity be up to 4.MGA-FTL is provided 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 certain logical page (LPAGE) by read it is out-of-date, its subpage can be write in multiple Physical Page；With reading number
Increase, associated Physical Page quantity is reduced；After the logical page (LPAGE) is repeatedly read, system will only allow to deposit on a Physical Page
The logical page (LPAGE) is stored up, even if additional space is caused to waste.As shown in Fig. 8 (a), it is assumed that four sons of an existing logical page (LPAGE) LPN
Page LSPN 0~3 is distributed in Physical Page PPN A and PPN B.Present file system issues last height to the logical page (LPAGE)
The write operation of page LSPN 3.When the LPN all numbers RC be 0, then LSPN 3 can be write according to mode shown in Fig. 8 (b)
In the idle subpage for entering the Physical Page PPN C in PV4KB queue, and LSPN 2 is still stored in PPN B, and the LPN is associated
The quantity of Physical Page becomes 3.But if RC is that 4, PC cannot be greater than 2, that is, need to limit the quantity of the associated Physical Page of LPN,
LSPN 2 and LSPN 3 can be written in the Physical Page PPN D in PV8KB queue in the way of in Fig. 8 (c) at this time,
It not will increase the PC counting for changing LPN in this way, but will cause the redundant data migration an of subpage.If RC is 10, need
According to shown in Fig. 8 (d), LSPN 0~3 is all copied in the Physical Page PPN E in FF queue, this process increases 3
The extra data of a subpage migrates, but when carrying out reading playground to the LPN again later, it is only necessary to it reads, reduces from PPN E
The expense of read operation.
System uses parameter --- and garbage reclamation threshold value (Garbage Collection Threshold, abbreviation GCT) is come
Determine the trigger timing of garbage collection operation.When the ratio of idle flash memory space is lower than GCT, garbage collection operation is triggered,
The flash block comprising more invalid data is chosen to be recycled.
As shown in figure 9, the adaptive flash translation layer (FTL) management method of mapping granule of the present invention the following steps are included:
(1) request of data is received from file system, and judges that the type of the request of data is read request or write request, such as
Fruit is write request, then enters step (2), if it is read request, then enters step (9)；
(2) page map table of flash memory space is inquired, according to the logical page number (LPN) of the write request to judge the write request pair
Whether the logical page (LPAGE) answered is not to write for the first time, is if it is transferred to step (3), is otherwise transferred to step (4)；Specifically, first
The page map table of flash memory space is inquired, and judges the logical page number (LPN) for wherein whether having write request, if there is then indicating logic
Page is not to write for the first time, otherwise indicates it is to write for the first time；
As shown in figure 3, giving page map table structure and listing an application example.Page map table structure includes two-stage
The mapping table of index, the first order are known as page map table, and list item includes logical flash page number (LPN), the mapping of the logical flash page
Type (Type) and correspondence physics Hash memory pages number (PPN).If logical flash page number correspondence mappings type is partial page (PP),
Then physical flash page number list item is directed toward a second level mapping table, referred to as subpage mapping table.Subpage mapping table list item includes logic
Flash memory subpage number (LSPN), the logical flash subpage number correspond to which specific object in physics Hash memory pages number (PPN) and Hash memory pages
Reason flash memory subpage number (PSPN) is in addition to this also recorded the associated Physical Page quantity of the logical page (LPAGE) (PPN Count), is used for
It is referred to when Hash memory pages are distributed and are merged.Example case is as shown in Figure 3, the logical page (LPAGE) that logical flash page number is 0,2,3
The corresponding complete page (type FP) directly carries out the mapping of page grade, does not need second level mapping table.Logical flash page number is 1,4 to patrol
The part subpage that page corresponds to Hash memory pages is collected, is needed using second level mapping table.At this point, the physical flash page number in page map table list item
The pointer for being directed to second level mapping table of field storage.
(3) judge that the type of the logical page (LPAGE) is partial page according to the corresponding type of the logical page number (LPN) in page map table
(Partial page, abbreviation PP) or the complete page (Full page, abbreviation FP), if it is partial page then by the part
Subpage state in the corresponding subpage state table of the page is set as failing, and is then transferred to step (4), then will if it is the complete page
Page status in the corresponding page status table in complete page face is set as failing, and is then transferred to step (4)；
Specifically, subpage state table is the dynamic generation in the state of use of Hash memory pages part, for saving flash memory
The use state of subpage；Its particular state conversion process is as shown in Figure 4；
As shown in figure 5, giving the corresponding state table information situation of map example in page status table structure and Fig. 3.Laminated
State table structure includes two-stage Hash memory pages state table, and the first order is known as page status table, and list item includes physical flash page number (PPN), object
Manage the type (Type) and physical flash page status (State) of Hash memory pages.If physical flash page corresponding types are partial page
(PP), then state list item is directed toward a sub- page status table.Subpage state table includes that physics subpage number (PSPN) is corresponding with the subpage
State (State) additionally includes the quantity (LPN Count) of the corresponding logical page (LPAGE) of the Physical Page.Corresponding instance situation such as Fig. 5
Shown in, the Physical Page that physical flash page number is 0,2,3 is used as complete Hash memory pages, therefore state is whole effectively (FV
State)；And the Physical Page that physical flash page number is Isosorbide-5-Nitrae has only used part subpage, thus introduce second level state table.Physics dodges
It deposits in the Hash memory pages that page number is 1, the subpage that physics subpage number is 0,1,2 saves valid data (V state), and physics subpage number
It is idle (F state) for 3 subpage.
(4) judge whether the size of write request is greater than the size (it is usually 8kB or 16kB) of Hash memory pages, if it is
Step (5) are transferred to, step (6) are otherwise transferred to；
(5) idle Physical Page is taken out from the head of the queue of whole page idle queues, and the physics is written into the corresponding data of write request
In page, and the page status in the corresponding page status table in complete page face is revised as all effectively；Wherein whole page idle queues are to be
It is established when system initialization, for distributing idle Physical Page；Then process terminates.
As shown in fig. 6, free page queue schematic diagram can be distributed by giving flash memory system.Free page queue includes a whole page
Idle queues and a partial page idle queues.Whole page idle queues by the stateful Hash memory pages for the whole page free time form one
Queue；Partial page idle queues are divided into 3 subqueues, and anti-other carry free space is 4KB, 8K and 12KB size under every queue
Hash memory pages.Transformation rule between them is, if there are also available spaces in the Hash memory pages after respond request, then will
Its chain enters in the queue of respective free capacity.
(6) allocation strategy for judging write request is that exclusive formula distributes (Exclusive Allocation, abbreviation EA) still
Shared distribution (Shared Allocation, abbreviation SA) is transferred to step (7) if it is the distribution of exclusive formula, if it is shared
Distribution is transferred to step (8).
(7) subpage LMT pointer is corresponded to according to the logical page number (LPN) in page map table, the subpage for finding the logical page number (LPN) reflects
The corresponding data of write request are written in the same Physical Page firing table.If there is no the list item of the logical page number (LPN) in page map table,
Creation list item is simultaneously allocated in the Physical Page that the head of the queue of whole page idle queues takes out the free time.Then process terminates.
As shown in fig. 7, allocation strategy includes exclusive formula distribution, it is otherwise shared distribution.Exclusive formula distribution will belong to
It is assigned in the same Physical Page in the logic subpage of the same logical page (LPAGE), which is monopolized by logical page (LPAGE).Shared distribution
The logic subpage of Different Logic page is allowed to be assigned in the same Physical Page.
The description of flash memory free space allocation algorithm is as shown in figure (8).
(8) idle physics subpage is taken out from the head of the queue of request size corresponding partial page free time, write request is corresponding
Data are written in the physics subpage, and set effective for the subpage state in the corresponding subpage state table of partial page；Wherein
Part effectively queue is established according to the service condition dynamic of whole page idle queues, for response section page data size
Write request.Then process terminates.
(9) judge that the type of the logical page (LPAGE) is partial page or complete according to the corresponding type of the logical page number (LPN) of the read request
The whole page is then transferred to step (10) if it is partial page, is otherwise transferred to step (12).
(10) it according to the corresponding physics subpage number of the logical page number (LPN) of the read request in subpage mapping table, reads in physics subpage
Data, and the reading number counter of the logical page (LPAGE) (Read Count, abbreviation RC) is added 1；
(11) according to the reading number counter of the logical page (LPAGE) and the associated Physical Page quantity of the logical page (LPAGE), judge whether to need
The subpage for merging dispersion, merges if necessary, is then transferred to (end)；Otherwise (13) are transferred to.
It is provided as follows specifically, merging rule: 1) RC==0, PC≤4；2) 0 < RC≤2, PC≤3；3)2<RC<
=5, PC≤2；4) RC > 5, PC=1.
It is an example schematic of union operation as shown in figure (9).Shown in Fig. 8 (a), it is assumed that an existing logical page (LPAGE)
Four subpage LSPN 0~3 of LPN are distributed in Physical Page PPN A and PPN B.Shown in Fig. 8 (b), file system is issued to this
The write operation of the last one subpage LSPN 3 of logical page (LPAGE).When numbers RC of the LPN is 0, by the write-in PV4KB queue of LSPN 3
In Physical Page PPN C idle subpage in, and LSPN 2 is still stored in PPN B, the quantity of the associated Physical Page of the LPN
Become 3.Shown in Fig. 8 (c), if RC is that 4, PC cannot be greater than 2, object LSPN 2 and LSPN 3 being written in PV8KB queue
It manages in page PPN D.Shown in Fig. 8 (d), if RC is 10 to, LSPN 0~3 is all copied to the Physical Page PPN E in FF queue
In.
(12) according to the corresponding physical page number of logical page number (LPN) of the read request in page map table, data in Physical Page are read,
Then process terminates.
The experimental results showed that compared to the flash translation layer (FTL) method of common page mapping, MGA-FTL effectively reduces flash memory
Page capacity increases the waste of bring data transmission period and flash memory space.In the real load tested, at most may be used
To reduce 53% request average response time, 30% solid state hard disk write-in amplification and 40% flash block erasing operation.
As it will be easily appreciated by one skilled in the art that the foregoing is merely illustrative of the preferred embodiments of the present invention, not to
The limitation present invention, any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention should all include
Within protection scope of the present invention.
Claims (5)
1. a kind of flash translation layer (FTL) management method that mapping granule is adaptive, which comprises the following steps:
(1) request of data is received from file system, and judges that the type of the request of data is read request or write request, if it is
Write request then enters step (2), if it is read request, then enters step (9)；
(2) page map table of flash memory space is inquired, according to the logical page number (LPN) of the write request to judge that the write request is corresponding
Whether logical page (LPAGE) is not to write for the first time, is if it is transferred to step (3), is otherwise transferred to step (4)；
(3) judge that the type of the logical page (LPAGE) is partial page or complete according to the corresponding type of the logical page number (LPN) in page map table
Subpage state in the corresponding subpage state table of the partial page then is set as failing, then by the page if it is partial page
Step (4) are transferred to, then are set as failing by the page status in the corresponding page status table in complete page face if it is the complete page, then
It is transferred to step (4)；
(4) judge whether the size of write request is greater than the size of Hash memory pages, be if it is transferred to step (5), be otherwise transferred to step
(6)；
(5) idle Physical Page is taken out from the head of the queue of whole page idle queues, and the corresponding data of write request are written in the Physical Page,
And be revised as the page status in the corresponding page status table in complete page face all effectively, then process terminates；Wherein whole page is idle
It is established when queue is system initialization, for distributing idle Physical Page；
(6) allocation strategy for judging write request is exclusive formula distribution or shared distribution, is transferred to step if it is the distribution of exclusive formula
Suddenly (7) are transferred to step (8) if it is shared distribution；
(7) subpage LMT pointer is corresponded to according to the logical page number (LPN) in page map table, finds the subpage mapping table of the logical page number (LPN),
The corresponding data of write request are written in the same Physical Page, if not having the list item of the logical page number (LPN) in page map table, are created
List item is simultaneously allocated in the Physical Page that the head of the queue of whole page idle queues takes out the free time, and then process terminates；
(8) idle physics subpage is taken out from the head of the queue of the corresponding partial page idle queues of request size, write request is corresponding
Data are written in the physics subpage, and set the subpage state in the corresponding subpage state table of partial page to effectively, then
Process terminates；Wherein, partial page idle queues are established according to the service condition dynamic of whole page idle queues, are used for response portion
The write request of paging face data size；
(9) judge that the type of the logical page (LPAGE) is partial page or complete page according to the corresponding type of the logical page number (LPN) of the read request
Face is then transferred to step (10) if it is partial page, is otherwise transferred to step (12)；
(10) according to the corresponding physics subpage number of the logical page number (LPN) of the read request in subpage mapping table, number in physics subpage is read
According to, and the reading number counter of the logical page (LPAGE) is added 1；
(11) according to the reading number counter of the logical page (LPAGE) and the associated Physical Page quantity of the logical page (LPAGE), judge whether to need to close
And the subpage dispersed, it merges if necessary, then process terminates, and else process terminates；
(12) according to the corresponding physical page number of logical page number (LPN) of the read request in page map table, data in Physical Page are read, then
Process terminates.
2. flash translation layer (FTL) management method according to claim 1, which is characterized in that step (2) specifically, inquire first
The page map table of flash memory space, and judge the logical page number (LPN) for wherein whether having write request, if there is then indicating logical page (LPAGE) not
It is to write for the first time, otherwise indicates it is to write for the first time.
3. flash translation layer (FTL) management method according to claim 1, which is characterized in that
Page map table structure includes the mapping table of two-stage index, and the first order is page map table, and list item includes logical flash page number, is somebody's turn to do
The map type of logical flash page and corresponding physics Hash memory pages number, wherein if logical flash page number correspondence mappings type is part
The page, then physical flash page number list item is directed toward a second level mapping table, referred to as subpage mapping table；
Subpage mapping table list item includes logical flash subpage number, the logical flash subpage number corresponding physics Hash memory pages number, Hash memory pages
In specific physical flash subpage number, the associated Physical Page quantity of the logical page (LPAGE).
4. flash translation layer (FTL) management method according to claim 1, which is characterized in that
Page status table structure includes two-stage Hash memory pages state table, and the first order is page status table, and list item includes physical flash page number, object
Manage the type and physical flash page status of Hash memory pages；
If physical flash page corresponding types are partial page, state list item is directed toward a sub- page status table, the subpage state
Table includes the quantity of physics subpage number, subpage corresponding states and the corresponding logical page (LPAGE) of Physical Page.
5. flash translation layer (FTL) management method according to claim 1, which is characterized in that
Free page queue includes a whole page idle queues and a partial page idle queues；
Whole page idle queues by the stateful Hash memory pages for the whole page free time form a queue；
Partial page idle queues are divided into 3 subqueues, and anti-other carry free space is 4KB, 8KB and 12KB size under every queue
Hash memory pages, the transformation rule between these Hash memory pages is, if there are also available space in the Hash memory pages after respond request,
In the queue that its chain is then entered to respective free capacity again.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610623356.XA CN106293521B (en) | 2016-08-02 | 2016-08-02 | A kind of flash translation layer (FTL) management method that mapping granule is adaptive |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610623356.XA CN106293521B (en) | 2016-08-02 | 2016-08-02 | A kind of flash translation layer (FTL) management method that mapping granule is adaptive |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106293521A CN106293521A (en) | 2017-01-04 |
| CN106293521B true CN106293521B (en) | 2019-04-12 |
Family
ID=57664190
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610623356.XA Active CN106293521B (en) | 2016-08-02 | 2016-08-02 | A kind of flash translation layer (FTL) management method that mapping granule is adaptive |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106293521B (en) |
Families Citing this family (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107256196A (en) * | 2017-06-13 | 2017-10-17 | 北京中航通用科技有限公司 | The caching system and method for support zero-copy based on flash array |
| TWI633434B (en) * | 2017-07-12 | 2018-08-21 | 宏碁股份有限公司 | Method, system, and computer readable medium for managing solid state drive |
| CN107632942A (en) * | 2017-08-29 | 2018-01-26 | 记忆科技(深圳)有限公司 | A kind of method that solid state hard disc realizes LBA rank TRIM orders |
| CN107766001B (en) * | 2017-10-18 | 2021-05-25 | 成都索贝数码科技股份有限公司 | Storage quota method based on user group |
| CN107943719B (en) * | 2017-11-28 | 2020-07-21 | 杭州电子科技大学 | A Flash Translation Layer Control Method Based on Request Classification |
| CN108647157B (en) * | 2018-03-14 | 2021-10-01 | 深圳忆联信息系统有限公司 | Mapping management method based on phase change memory and solid state disk |
| CN108829346B (en) * | 2018-05-28 | 2020-11-17 | 华中科技大学 | User writing request processing method of solid state disk adapting to flash memory page difference |
| CN109446117B (en) * | 2018-09-06 | 2023-02-28 | 杭州电子科技大学 | Design method for page-level flash translation layer of solid state disk |
| KR102746564B1 (en) | 2018-09-17 | 2024-12-24 | 삼성전자주식회사 | Memory controller, method of operating the memory controller and storage device comprising memory controller |
| CN109189348B (en) * | 2018-10-08 | 2020-07-24 | 华中科技大学 | Read performance optimization method of storage system based on charge trapping type 3D T L C flash memory |
| CN110727604B (en) * | 2019-08-26 | 2022-04-29 | 华为技术有限公司 | Data processing method and device |
| CN111143313B (en) * | 2019-12-25 | 2023-07-25 | 成都三零嘉微电子有限公司 | Method for improving log block read-write performance of hybrid mapping algorithm |
| CN112559386B (en) * | 2020-12-22 | 2024-06-18 | 深圳忆联信息系统有限公司 | Method, device, computer equipment and storage medium for improving SSD performance |
| CN113835639B (en) * | 2021-09-26 | 2024-03-19 | 深圳大普微电子科技有限公司 | I/O request processing method, device, equipment and readable storage medium |
| CN114327272B (en) * | 2021-12-28 | 2024-08-09 | 苏州大普微电子科技有限公司 | Data processing method, solid state disk controller and solid state disk |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1783032A (en) * | 2004-11-12 | 2006-06-07 | 国际商业机器公司 | Method and device for providing flexible sub-column to sub-row mapping for sub-page activation |
| CN1795437A (en) * | 2002-10-28 | 2006-06-28 | 桑迪士克股份有限公司 | Method and apparatus for grouping pages within a block |
| CN102467455A (en) * | 2010-10-29 | 2012-05-23 | 三星电子株式会社 | Memory system, data storage device, user device and data management method thereof |
| CN102779096A (en) * | 2012-07-11 | 2012-11-14 | 山东华芯半导体有限公司 | Page, block and face-based three-dimensional flash memory address mapping method |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8024545B2 (en) * | 2007-10-19 | 2011-09-20 | Inha-Industry Partnership Institute | Efficient prefetching and asynchronous writing for flash memory |
| US7855916B2 (en) * | 2007-10-24 | 2010-12-21 | Rao G R Mohan | Nonvolatile memory systems with embedded fast read and write memories |
-
2016
- 2016-08-02 CN CN201610623356.XA patent/CN106293521B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1795437A (en) * | 2002-10-28 | 2006-06-28 | 桑迪士克股份有限公司 | Method and apparatus for grouping pages within a block |
| CN1783032A (en) * | 2004-11-12 | 2006-06-07 | 国际商业机器公司 | Method and device for providing flexible sub-column to sub-row mapping for sub-page activation |
| CN102467455A (en) * | 2010-10-29 | 2012-05-23 | 三星电子株式会社 | Memory system, data storage device, user device and data management method thereof |
| CN102779096A (en) * | 2012-07-11 | 2012-11-14 | 山东华芯半导体有限公司 | Page, block and face-based three-dimensional flash memory address mapping method |
Also Published As
| Publication number | Publication date |
|---|---|
| CN106293521A (en) | 2017-01-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106293521B (en) | A kind of flash translation layer (FTL) management method that mapping granule is adaptive | |
| CN103608782B (en) | Selective data storage in LSB page face and the MSB page | |
| US9652386B2 (en) | Management of memory array with magnetic random access memory (MRAM) | |
| CN106547703B (en) | A kind of FTL optimization method based on block group structure | |
| TWI399644B (en) | Block management method for a non-volatile memory | |
| CN101425041B (en) | Optimizing method for establishing FAT file systems on NAND FLASH memory | |
| CN106815152B (en) | A method of optimization page grade flash translation layer (FTL) | |
| US20140129758A1 (en) | Wear leveling in flash memory devices with trim commands | |
| US10108555B2 (en) | Memory system and memory management method thereof | |
| CN104572478A (en) | Data access method and data access device | |
| CN101819509A (en) | Solid state disk read-write method | |
| US11960756B2 (en) | Management of storage space in solid state drives to support proof of space activities | |
| KR101403922B1 (en) | Apparatus and method for data storing according to an access degree | |
| CN108108128A (en) | A kind of abrasion equilibrium method and SSD for mixing SSD | |
| KR20090038386A (en) | Mixed Density Memory Storage Devices | |
| CN102841851A (en) | Flash memory management method and flash memory device | |
| CN102819494B (en) | Optimization method when a kind of flash memory is sequentially written in | |
| CN102945207A (en) | Cache management method and system for block-level data | |
| CN108762671A (en) | Hybrid memory system based on PCM and DRAM and management method thereof | |
| US20230244394A1 (en) | Gradually Reclaim Storage Space Occupied by a Proof of Space Plot in a Solid State Drive | |
| CN105278875B (en) | A kind of mixing isomery NAND solid state hard disk | |
| CN105607862A (en) | Solid state disk capable of combining DRAM (Dynamic Random Access Memory) with MRAM (Magnetic Random Access Memory) and being provided with backup power | |
| CN109074318A (en) | System and method for executing the adaptive host memory buffers cache of conversion layer list | |
| TWI718710B (en) | Data storage device and non-volatile memory control method | |
| CN104298615B (en) | Method for equalizing swap partition loss of memory |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |