CN107066393B - A method for improving the density of mapping information in the address mapping table - Google Patents

Abstract

The invention discloses a method for improving mapping information density in an address mapping table, which can improve the hit rate of a cache mapping table in a page mapping scheme based on cache part mapping information, improve the read-write performance of a flash memory conversion layer, merge continuous and adjacent mapping records on a logic address and a physical address to generate a mapping entry on the premise of not increasing the number of entries in the cache mapping table in a memory, so that one mapping entry can represent the mapping relation between a plurality of logic addresses and physical addresses, one mapping entry is inserted into the cache mapping table instead of one mapping record which can only represent the mapping relation between one logic address and one physical address, thereby increasing the number of the mapping records stored in the cache mapping table on the premise of not increasing the occupation of the cache mapping table on the memory, and obviously increasing the hit rate of the cache mapping table, the read-write efficiency of the Flash conversion layer is improved, and the method can be widely applied to management of NAND Flash memories of various systems.

Description

A method for improving the density of mapping information in the address mapping table

technical field

The invention relates to the technical field of data storage, in particular to a method for improving the density of mapping information in an address mapping table.

Background technique

NAND Flash is a kind of non-volatile semiconductor memory, which will not lose the data stored on it due to power failure. Since there are no mechanical parts inside the NAND Flash memory, it has low power consumption, low heat generation and weight. Light, small size, good shock resistance and other advantages that traditional mechanical disk storage does not have, its random read and write performance is much higher than traditional mechanical disk storage. With the breakthrough of flash memory storage capacity bottleneck, performance optimization and cost reduction, NAND Flash memory has become a very important digital storage medium.

NAND Flash is composed of many blocks (Block), and each block is composed of several pages (Page), wherein a page is the smallest unit of reading data and writing data, and a block is the smallest unit of erasing. When writing the NAND Flash, the block where the page is located must be erased first, otherwise the page cannot be written. So flash memory has three basic operations: read, write, and erase.

The three operations of NAND Flash have different performances. The reading performance is the best, the writing performance is the second, and the erasing performance is the worst. The speed of read operation is the fastest. It takes about tens of microseconds to read a page. The speed of write operation is slower than that of read operation. It takes about hundreds of microseconds to write a page, and the erase operation is very time-consuming. , erasing a block takes about a few milliseconds.

The erasing times of NAND Flash blocks are limited. Once the maximum erasing times are exceeded, the data stored on them may become unreliable.

When updating the data stored in a certain page of NAND Flash, you must first use the erase operation to erase the block where the page is located. Erase is a millisecond-level operation, which is a very expensive operation compared to a microsecond-level write operation. Therefore, if the local update (In-Place Update) method is also used, the writing speed of the flash memory will be seriously reduced. Additionally, frequent local updates of data on a block can cause the block to rapidly reach its limit of use due to constant erasure. Therefore, in actual use, NAND Flash adopts the method of Out-Place Update when updating data. All updated data will not be written to the original page, but will be rewritten to other erased pages. (free page). The storage resources of NANDFlash are allocated and managed according to the way that the page number is the physical address. With the change of the storage location of valid data on the NANDFlash, the logical-to-physical mapping relationship cannot be obtained by establishing an expression calculation, and it is necessary to establish a mapping table. Provides filesystem addressing of data. Therefore, introducing a Flash Translation Layer (FTL) and implementing an address mapping mechanism through FTL to record the mapping relationship between logical addresses and physical addresses where data is actually stored have become the current mainstream flash management solutions.

In order to achieve fast addressing, the mapping table is generally partially or fully cached in the memory, which is called the cache mapping table. How to reduce the memory occupation of the cache mapping table and allow requests to complete direct addressing through the cache mapping table is flash memory The problem that the translation layer needs to solve.

Depending on the granularity of address mapping, there are four methods for establishing cache mapping tables: PageMapping, Blocking Mapping, Hybrid Mapping, and Cached Page Mapping based on partial cache mapping information ).

Page mapping is to perform address mapping in units of pages, and store a page-based mapping table in memory. Each logical page has a corresponding physical page, which needs to be maintained by a mapping record in the mapping table, and a mapping record One mapping table entry is occupied in the mapping table, and the page mapping method is highly flexible, but since an address mapping table entry needs to be established for each logical page, the mapping table occupies a large amount of memory.

Block mapping is based on block-based address mapping, and the address offset in the logical block is consistent with the offset in the physical block. Compared with the page mapping table, the mapping table occupies less memory, but its disadvantage is that it has poor performance when processing small data updates, and the update of a small piece of data will cause the copy of the entire block content.

Synthesizing the advantages and disadvantages of page mapping and block mapping results in a hybrid mapping mechanism. The hybrid mapping functionally divides the blocks on the NAND Flash into data blocks and log blocks, with fewer log blocks. When the data in a data block is to be updated, the new data will be written to the log block. When the number of all log blocks is lower than a certain value, the data in the log block and the data block need to be merged. This operation will result in a significant drop in performance.

The page mapping scheme based on caching part of the mapping information in the memory is an improvement to the page mapping. This mapping method uses multiple pages to store the complete mapping table on the NAND Flash. This page is called the mapping table storage page and is cached in the memory. For frequently requested mapping records, the cache size is fixed, that is, the number of mapping table entries in the cache mapping table is set to an upper limit, and the number of mapping records that can be stored is the same as the number of mapping table entries, which ensures that the memory usage of the cache mapping table will not exceed. big. When a read and write request comes, if the corresponding mapping record is not in the cache, that is, the cache mapping table is not hit, the mapping record is read from the NAND Flash. When the number of mapping records in the cache mapping table reaches the upper limit, the maximum The mapping record that has not been accessed for a long time is swapped out from the cache. If the deleted mapping record is dirty, it is recorded, that is, the mapping relationship between the logical and physical pages stored in the mapping record has changed in the cache, and it needs to be written back to the cache. in the mapping table in NAND Flash. The reading and swapping of map records results in additional reads and writes to the NAND Flash.

To sum up, page mapping is flexible and has the best performance, while mixed mapping is poor, and block mapping is the worst. However, the page mapping scheme based on the partial mapping information of the cache does not generate a merge operation, so its performance is higher than that of the mixed mapping, and is similar to the performance of the page mapping method. However, because the cache mapping table can only store limited mapping records, some requests cannot hit the cache mapping table and cannot complete direct addressing, and need to exchange mapping records with the mapping table in NAND Flash, resulting in non-requests that lead to reading NAND Flash The additional read operation of the mapping table and the additional write operation of writing the mapping record to the NAND Flash, and the writing of the mapping record to the NAND Flash will also generate an additional garbage collection operation due to insufficient free blocks. These additional scratches ultimately lead to lower performance than page mapping, and the lower the hit rate, the worse the performance. Therefore, how to cache more mapping table entries in the cache mapping table without increasing the memory usage, that is, to increase the storage density of the cache mapping table to improve the hit rate is the difficulty that the page mapping scheme based on the partial mapping information of the cache needs to solve. .

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a method for improving the density of mapping information in the address mapping table, which can improve the density of mapping records in the cache mapping table and achieve the purpose of improving the read and write performance of the FTL.

The purpose of this invention is to realize through the following technical solutions:

A method for improving the density of mapping information in an address mapping table, comprising:

When writing data, the data is divided into page units, and then the data is written into the block with multiple consecutive free pages in the memory in order of logical address from low to high, and the data of each page after storage is Corresponding to a mapping record, one or more mapping entries are generated according to these mapping records;

When reading data, the read request address is divided into pages, and the cache mapping table in the memory is retrieved one by one. If the logical address of a page does not hit the cache mapping table in the memory, the read memory is used to store the mapping table. In the mapping table storage page of the table, the required target mapping record is obtained from the mapping table storage page; and at the same time, the mapping records around the target mapping record are also retrieved in the mapping table storage page, and the eligible surrounding mapping records are merged by A mapping entry is generated, and the retrieval process is as follows: read the content of the mapping table storage page, that is, the mapping table fragment, and then use the target mapping record as the starting point to retrieve the mapping table fragment in the forward and backward directions. If adjacent mappings are found in a certain direction The logical address value and the physical address value of record B and the target mapping record are both different by 1, then continue to search the mapping table in the same direction with the adjacent mapping record B as the starting point, until the two adjacent mapping records are no longer consecutive, or Although it is continuous, it has existed in the cache mapping table, or the first or last mapping record in the storage page of the mapping table is retrieved;

When writing data and reading data, the generated mapping entry is inserted into the cache mapping table in the memory.

When writing data, if the number of pages of the written data is N, the number of consecutive free pages in the block with multiple consecutive free pages in the memory is M, and when N>M, cross-block storage is required, that is, the remaining number of free pages is required. The data pages of the data are sequentially written into other blocks with multiple consecutive free pages in the order of logical addresses from low to high, until all data pages are written into the memory;

If S times of cross-block storage are generated when writing a data page, a total of S mapping entries are generated, and the data of the mapping record included in each mapping entry is the number of data pages stored in the corresponding block.

The mapping entry stores several consecutive mapping records; if a logical address LBA is a mapping record MPRec1 of L, its physical address PBA is P, and if another logical address LBA is an L+1 mapping record MPRec2, its physical address PBA If it is P+1, the mapping records MPRec1 and MPRec2 are continuous. If another logical address LBA is L+2, the mapping record MPRec3, and its physical address PBA is P+2, then the mapping records MPRec1, MPRec2 and MPRec3 are continuous. By analogy, there are N mapping records, and the value of the logical address LBA increases continuously from low to high according to L, L+1, L+2, ..., L+N-1, which are recorded in adjacent mapping records. The value of the logical address differs by 1, and the value of its physical address PBA also increases continuously from low to high according to P, P+1, P+2, ..., P+N-1. The physical address recorded in the adjacent mapping record The value of the address differs by 1, and such N mapping records are consecutive mapping records.

The mapping entry consists of the logical address and physical address in the mapping record with the smallest logical address, a length value N and a dirty flag bit in the consecutive N mapping records;

The number of bytes occupied by the logical address and physical address of the mapping entry is the same as the number of bytes occupied by the logical address and physical address in the corresponding mapping record, and another byte is used to store the length value N and the dirty flag. Bit, the dirty flag bit occupies the highest bit of the byte, which is used to identify whether the mapping entry has been changed during the lifetime of the cache mapping table. If it has changed, it is assigned a value of 1, otherwise the value is 0; in bits 0 to 7 of this byte.

Inserting mapping entries into the cache mapping table in the memory includes:

If there is a conflict between the mapping entry and the existing entry in the cache mapping table due to the intersection of logical addresses, the related mapping entry needs to be decomposed and reassembled;

If the mapping entry and the existing entry in the cache mapping table are continuous, the related mapping entry needs to be merged again.

After the mapping entry is inserted into the cache mapping table in the memory, if the received read request hits the mapping entry, the corresponding physical address is directly calculated, and the steps include:

Retrieve the cache mapping table, compare the logical address LBA in the read request and the logical address range represented by each mapping entry to determine whether the LBA falls within the logical address range represented by a mapping record;

For a mapping entry of length N, the stored logical address is LBA1 and the physical address is PBA1. When LBA>=LBA1, and LBA<=LBA1+N-1, it means that the logical address included in the request hits Cache the mapping entries in the mapping table, and the calculation method of the physical address PBA corresponding to the logical address LBA in the read request is: PBA=PBA1+LBA-LBA1, and the addressing of the physical address can be completed by calculation.

It can be seen from the above technical solutions provided by the present invention that the corresponding mapping records are generated according to the read and write operations and inserted into the cache mapping table, which can increase the density of mapping records in the cache mapping table without occupying more memory resources, thereby increasing the number of mapping records in the cache mapping table. The number of mapping records in the cache mapping table is increased, and the hit rate of the cache mapping table is improved.

Description of drawings

In order to illustrate the technical solutions of the embodiments of the present invention more clearly, the following briefly introduces the accompanying drawings used in the description of the embodiments. Obviously, the drawings in the following description are only some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort.

1 is a flowchart of a method for improving the density of mapping information in an address mapping table provided by an embodiment of the present invention;

2 is a schematic diagram of decomposing and recombining a related mapping entry when a generated mapping entry provided by an embodiment of the present invention is inserted into a cache mapping table in the memory;

3 is a schematic diagram of merging related mapping entries when a generated mapping entry provided by an embodiment of the present invention is inserted into a cache mapping table in a memory;

FIG. 4 is a schematic diagram of merging related mapping entries when a generated mapping entry is inserted into a cache mapping table in a memory according to an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present invention.

An embodiment of the present invention provides a method for improving the density of mapping information in an address mapping table, as shown in FIG. 1 , which mainly includes:

1. Conditions for judging whether adjacent mapping records on multiple logical addresses can be merged into mapping entries

In this embodiment of the present invention, when writing data and reading data, multiple mapping records that meet the conditions can be combined into mapping entries, and several consecutive mapping records are stored in the generated mapping entry; If the logical address LBA is the mapping record MPRec1 of L, and its physical address PBA is P, if another logical address LBA is the L+1 mapping record MPRec2, and its physical address PBA is P+1, then the mapping records MPRec1 and MPRec2 are continuous. If another logical address LBA is L+2 mapping record MPRec3, and its physical address PBA is P+2, then mapping records MPRec1, MPRec2 and MPRec3 are consecutive, and so on, there are N mapping records whose logical address LBA The value increases continuously from low to high according to L, L+1, L+2, ..., L+N-1. The values of the logical addresses recorded in the adjacent mapping records differ by 1, and the value of the physical address PBA is also From low to high, it increases continuously according to P, P+1, P+2, ..., P+N-1, and the values of physical addresses recorded in adjacent mapping records differ by 1. Such N mapping records are continuous. Mapping records, such N mapping records can be combined into a mapping entry.

For consecutive N mapping records, they can be combined into mapping entries: each mapping entry consists of the mapping record with the smallest logical address in the consecutive N mapping records, the length value N, and the dirty flag bit; The length value N and the dirty flag bit are stored in the same byte. The dirty flag bit occupies the highest bit of the byte and is used to identify whether the mapping entry has been changed during the lifetime of the cache mapping table. The value is "1", otherwise the value is "0", and the length value N of the entry is stored in bits 0 to 7 of this byte.

2. When writing data, divide the data into pages, and then write the data into blocks with multiple consecutive free pages in the memory (NAND Flash) in the order of logical addresses from low to high. Each page of data corresponds to a mapping record, and one or more mapping entries can be generated from these consecutive mapping records.

When writing data, if the number of pages of the written data is N, the number of consecutive free pages in the block with multiple consecutive free pages in the memory is M, and when N>M, cross-block storage is required, that is, the remaining number of free pages is required. The data pages of the data are sequentially written into other blocks with multiple consecutive free pages in the order of logical addresses from low to high, until all data pages are written into the memory.

Those skilled in the art can understand that when writing data, it is also written into a block in units of pages, and the writing order of pages in a block can only be written sequentially from low-address pages to high-address pages, but cannot be written randomly. Therefore, the data with the lower logical address is written to the page with the lower physical address, and a mapping record between the logical address and the physical address is generated. Mapping records until all the data of this request is written; if all the free pages in this free block are full during the writing process and some page data is still not written to NAND Flash in this request, cross-block writing is required Enter data, that is, allocate a new free block for writing the data in the write request. Similarly, the order of data writing is still that the data of the low logical address is written to the page of the low physical address, and a logical address to the physical address is generated. In the mapping record, the data with the second-lowest logical address is written into the page with the second-lowest physical address, resulting in a mapping record from a logical address to a physical address. This is repeated until all the data in the write request is written into the NAND Flash.

Therefore, the write request generates N mapping records. If no cross-block writing occurs during writing, the N mapping records are consecutive. Therefore, the N mapping records can be combined into one mapping entry, and the entry length is N.

If cross-block writing occurs during writing, the M mapping records corresponding to the data stored in the same block are consecutive, so the M mapping records can be combined into one mapping entry, and the entry length is M. If S times of cross-block storage are generated when writing a data page, a total of S mapping entries are generated, and the data of the mapping record contained in each mapping entry is the page in the corresponding block to which the data is written due to this request. quantity.

3. When reading data, the read request address range is divided into pages, and the cache mapping table in the memory is retrieved one by one. If the logical address of a page does not hit the cache mapping table in the memory, read the cache mapping table in the memory. The mapping table, the flash page used to save the mapping table is called the mapping table storage page. By reading the storage page of the mapping table, the mapping relationship between the logical address and the physical address of the required data is obtained, that is, the target mapping record; after reading the content of the storage page of the mapping table, the mapping around the target mapping record is retrieved in the content. Record, merge the surrounding continuous mapping records into mapping entries, and the retrieval process is as follows: first, read the content of the mapping table storage page, that is, the mapping table fragment, and then use the target mapping record as the starting point to retrieve the mapping table in both forward and backward directions If it is found in a certain direction that the logical address value and the physical address value of the adjacent mapping record B and the mapping record differ by 1, the mapping table will continue to be searched in the same direction with the adjacent mapping record B as the starting point. The conditions for aborting the retrieval are: a) The two adjacent mapping records are no longer consecutive (that is, the logical address value and the physical address value are no longer different by 1); b) The first one in the mapping table fragment has been retrieved Map records; c) have retrieved the last map record in this map segment; d) encountered a map record that is contiguous but already exists in the cache map.

4. Insert the mapping entries generated when writing data and reading data into the cache mapping table in the memory.

In the embodiment of the present invention, the generated mapping entry is also inserted into the cache mapping table in the memory, so as to make full use of the spatial locality and time locality of the request, and improve the reading and writing efficiency of the FTL. When the mapping entry is inserted into the cache mapping table, the following two different processing methods are adopted according to the specific situation:

If the mapping entry to be inserted and one or more existing entries in the cache mapping table are generated because there is an intersection in the logical address space, the related mapping entries need to be decomposed and recombined. There are many ways to overlap the two logical address spaces. , which need to be handled separately according to different situations. Exemplarily, Figure 2 shows one of the methods of decomposition and recombination: when the mapping entry whose logical first address is 1136 is inserted into the cache mapping table, this entry and the mapping entry whose logical first address is 1135 in the cache mapping table There is an intersection in the logical address space, which needs to be recombined. After the combination, three new mapping entries are generated. The entry whose logical first address is 1135 is stored in the cache mapping table in situ, while the other two entries are in a free state at this time. If In this case, if there are more than two empty entries in the cache mapping table, the two mapping entries in the free state can be directly inserted into the cache mapping table. If there are less than two empty entries in the cache mapping table, the mapping entry that has not been accessed for the longest time needs to be swapped out first, and then the new entry in the free state is inserted into the cache mapping table.

If the mapping entry and the existing entry in the cache mapping table are continuous, the related mapping entry needs to be merged again. Exemplarily, as shown in Figure 3, when a mapping entry with a logical first address of 1132 and a length of 3 is inserted into the cache, it can be merged with an entry with a logical first address of 1135 in the cache, and the merge generates a new mapping entry. The logical head of the new mapping entry is The address and physical first address are 1132 and 517 respectively, and the length of the mapping entry becomes 7. As shown in Figure 4, when a mapping entry whose logical first address is 1139 and whose length is 3 is inserted into the cache, it will be merged with the mapping entry whose first address is 1135 and whose length is 4 in the cache, and the merged mapping entry is still stored in the cache in place. middle.

In this embodiment of the present invention, a method for calculating target mapping records by mapping entries is also provided:

If the request hits a certain mapping entry in the cache mapping table, the corresponding physical address can be directly calculated, and the steps include: retrieving the cache mapping table, comparing the logical address LBA in the read request with the logical address range represented by each mapping entry To judge whether the LBA falls within the logical address range represented by a mapping record; for a mapping entry with a length of N, the stored logical address is LBA1 and the physical address is PBA1, when LBA>=LBA1, and LBA <=LBA1+N-1, it means that the logical address contained in the request hits the mapping entry in the cache mapping table, and the calculation method of the physical address PBA corresponding to the logical address LBA in the read request is: PBA=PBA1+LBA- LBA1, the addressing of the physical address can be completed by calculation.

The above solution of the embodiment of the present invention can improve the hit rate of the cache mapping table, and improve the read and write performance of the FTL. The present invention does not increase the number of entries in the cache mapping table located in the memory. Mapping entries are generated by merging, so that each mapping entry can represent the mapping relationship between multiple logical addresses and physical addresses. Each entry in the cache mapping table stores a mapping entry instead of a single entry. A mapping record that represents the mapping relationship between a logical address and a physical address, so as to increase the number of mapping records stored in the cache mapping table, which can significantly increase the hit rate of the cache mapping table. At the same time, because the mapping entry can express multiple logical addresses The continuous mapping record can effectively utilize the spatial locality of the request, improve the efficiency of FTL reading and writing, and can be widely used in the management of NAND Flash memory in various systems.

From the description of the above embodiments, those skilled in the art can clearly understand that the above embodiments can be implemented by software or by means of software plus a necessary general hardware platform. Based on this understanding, the technical solutions of the above embodiments may be embodied in the form of software products, and the software products may be stored in a non-volatile storage medium (which may be CD-ROM, U disk, mobile hard disk, etc.), including Several instructions are used to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute the methods described in various embodiments of the present invention.

The above description is only a preferred embodiment of the present invention, but the protection scope of the present invention is not limited to this. Substitutions should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be based on the protection scope of the claims.

Claims (6)

1. A method for increasing mapping information density in an address mapping table, comprising:

when data is written, dividing the data by taking a page as a unit, sequentially writing the data into a block with a plurality of continuous free pages in a memory according to the sequence of logical addresses from low to high, wherein each stored page of data corresponds to one mapping record, and generating one to a plurality of mapping entries according to the mapping records; if cross-block writing is not generated during writing, the mapping records are continuous and can be combined into 1 mapping entry; if cross-block writing is generated during writing, mapping records corresponding to data stored in the same block are continuous, and all corresponding mapping records can be combined into 1 mapping entry; thus, if S times of cross-block storage is generated when writing data pages, S pieces of mapping entries are generated together;

when reading data, dividing the read request address by taking a page as a unit, searching cache mapping tables in the memory one by one, if the logical address of a certain page does not hit the cache mapping table in the memory, reading a mapping table storage page used for storing the mapping table in the memory, and obtaining a required target mapping record from the mapping table storage page; and meanwhile, the mapping records around the target mapping record are also searched in the mapping table memory page, and a mapping entry is generated by combining the surrounding mapping records meeting the conditions, wherein the searching process comprises the following steps: reading the content of a storage page of a mapping table, namely a mapping table segment, retrieving the mapping table segment from a target mapping record in a front direction and a rear direction, if the difference between the logical address value and the physical address value of the adjacent mapping record B and the target mapping record is found to be 1 in a certain direction, continuing to retrieve the mapping table from the adjacent mapping record B in the same direction until the two adjacent mapping records are not continuous or exist in a cache mapping table or a first mapping record or a last mapping record in the storage page of the mapping table is retrieved;

and when data is written and read, the generated mapping item is inserted into a cache mapping table in the memory.

2. The method of claim 1, wherein when writing data, if the number of pages of the written data is N, the number of consecutive free pages in a block with multiple consecutive free pages in the memory is M, and N > M, then cross-block storage is required, i.e. the remaining data pages are required to write data into other blocks with multiple consecutive free pages in order of logical addresses from low to high, until all data pages are written into the memory;

if cross-block storage occurs when a data page is written, the data of the mapping record contained in each mapping entry is the number of data pages stored in the corresponding block.

3. The method for increasing mapping information density in the address mapping table according to claim 1 or 2, wherein the mapping entries store a plurality of consecutive mapping records; if one mapping record MPRec1 with LBA as L and PBA as P is available for one logical address, if another mapping record MPRec2 with LBA as L +1 is available, the mapping records MPRec1 and MPRec2 are consecutive with a physical address PBA of P +1, if the other logical address LBA is L +2 mapping record MPRec3, the physical address PBA is P +2, the mapping records MPRec1, MPRec2 and MPRec3 are consecutive, and so on, there are N mapping records, the logical address LBA values of which successively increase from low to high in accordance with L, L +1, L +2, …, L + N-1, the logical address values recorded in adjacent mapping records differ by 1, the values of the physical addresses PBA are also increased from low to high according to P, P +1, P +2, … and P + N-1, the values of the physical addresses recorded in adjacent mapping records are different by 1, and such N mapping records are consecutive mapping records.

4. A method for increasing mapping information density in an address mapping table according to claim 3, wherein a mapping entry is composed of the logical address and the physical address in the mapping record with the smallest logical address, a length value N and a dirty flag bit in the N consecutive mapping records;

the logical address and the physical address of the mapping entry occupy the same number of bytes as the logical address and the physical address in the corresponding mapping record, and one byte is additionally used for storing a length value N and a dirty flag bit, wherein the dirty flag bit occupies the highest bit of the byte and is used for identifying whether the mapping entry is changed in the life cycle of the cache mapping table, if the mapping entry is changed, the mapping entry is assigned to be 1, otherwise, the mapping entry is assigned to be 0; the length value of the entry is stored in bits 0 to 7 of the byte.

5. The method as claimed in claim 1, wherein the step of inserting the mapping entry into the cache mapping table in the memory comprises:

if the mapping entries and the existing entries in the cache mapping table generate conflicts caused by intersection on the logical addresses, the relevant mapping entries need to be decomposed and recombined;

if the mapping entries and the existing entries in the cache mapping table are consecutive, the associated mapping entries need to be merged again.

6. The method as claimed in claim 1, wherein after the mapping entries are inserted into the cache mapping table in the memory, if the received read request hits the mapping entries, the corresponding physical addresses are directly calculated, and the step includes:

searching a cache mapping table, and comparing the logical address LBA in the read request with the logical address range represented by each mapping item to judge whether the LBA falls in the logical address range represented by a certain mapping record;

for a mapping entry with a length of N, where the stored logical address is LBA1, and the physical address is PBA1, when LBA > is LBA1, and LBA < ═ LBA1+ N-1, it indicates that the logical address included in the request hits the mapping entry in the cache mapping table, and the method for calculating the physical address PBA corresponding to the logical address LBA in the read request is as follows: PBA1+ LBA-LBA1, and the addressing of the physical address can be completed through calculation.

Images