CN106776361B - Caching method and system for large-scale nonvolatile storage medium - Google Patents

Abstract

The invention discloses a caching method and a caching system for a large-scale nonvolatile storage medium, which comprise the following steps: the method comprises the steps of obtaining a command request, when the command request is a write command request, storing a target Mapping item into an H-Cache according to a logical address prefix, when the residual space in the H-Cache is smaller than A, migrating the Mapping item which is not accessed for the longest time in the H-Cache to a C-Cache, when the residual space in the C-Cache is smaller than B, sorting blocks in the C-Cache according to the access times, checking a Mapping item flag bit in the Block with the minimum access times, if the Mapping item flag bit is 0, writing the Mapping item into Mapping, setting the Mapping item flag bit to be 1, and if the Mapping item flag bit is 1, deleting the Mapping item; when the command request is a read command request, acquiring a logical address of a target mapping item, retrieving the target mapping item corresponding to the logical address from the H-Cache, and if the target mapping item exists, outputting a physical address of the target mapping item; if not, searching a target Mapping item corresponding to the logical address in the C-Cache, if yes, outputting a physical address of the target Mapping item, and if not, retrieving and outputting a physical address corresponding to the logical address in the Mapping area.

Description

A caching method and system for large-scale non-volatile storage media

technical field

The present invention relates to the technical field of data storage and retrieval, in particular to a cache method and system for large-scale non-volatile storage media.

Background technique

Compared with traditional disks, solid-state drives based on non-volatile storage media (Non-Volatile Memory, NVM) show many advantages such as low power consumption, fast read and write speed, and better shock resistance. In high places (such as data centers), the use ratio of NVM (Non-Volatile Memory) media devices has exceeded that of disks.

In the era of big data, the International Data Corporation predicts that in the five years from 2016, the total amount of data generated every year in the world will increase by 40%, and the total amount of global data will reach 44ZB by 2020. In the solid state disk system based on NVM medium, the disadvantages of the traditional data organization and management form begin to appear. First, as the amount of stored data increases, on the one hand, the amount of metadata that manages the mapping between logical data and physical data is large, and the cache space and storage space required for these metadata are large; on the other hand, the cache based on these metadata It is more difficult to implement and index management, especially with the application of large-capacity 3D NVM media to solid-state disk systems, traditional cache and index management methods are gradually unable to meet the needs of high-performance storage access, which will become a problem in data storage access performance. one of the bottlenecks.

In the existing solid-state disk structure, in order to be compatible with the access mode of the traditional host-side file system to the block device, an NVM device translation layer (Non-Volatile Memory Translation Layer, NVMTL) is usually designed in the solid-state disk software stack, which mainly includes address mapping. , wear leveling and garbage collection modules, among which address mapping is the core function of NVMTL, which is responsible for converting logical addresses from the file system to physical addresses in NVM devices. According to the size of the logical address and physical address mapping granularity, NVMTL address mapping can be divided into page mapping, block mapping and mixed mapping.

In most NVMTL address mapping management, the relationship entries between logical addresses and physical addresses are organized and managed in the form of a two-dimensional table. In the large-capacity storage system based on NVM media, first, when the amount of data is large, the data retrieval performance is low; in addition, the existing partial solution of NVM media adopts the method of second-level mapping to cache a part of the entire mapping items For frequently accessed mapping entries, the retrieval performance under the access miss condition is poor, and it is difficult to implement storage access management.

SUMMARY OF THE INVENTION

Based on the technical problems existing in the background art, the present invention provides a caching method and system for large-scale non-volatile storage media;

A caching method for a large-scale non-volatile storage medium proposed by the present invention, the method comprises the following steps:

S1. According to the user command request, it is judged that it is a target mapping item write command request or a target mapping item read command request, and S2 is executed when it is judged that the command request is a target mapping item write command request; when it is judged that the command request is a target mapping item Execute S3 when the read command is requested;

S2. Set the end flag position of the target mapping item to 0, and then store the target mapping item in the H-Cache area according to its logical address prefix;

S3, obtain the logical address in the target mapping item read command request, determine whether there is a target mapping item corresponding to the logical address in the H-Cache, and when the judgment result is yes, output the physical address corresponding to the target mapping item; when When the judgment result is no, retrieve whether there is a target mapping item corresponding to the logical address in the C-Cache,

When the retrieval result is yes, output the physical address corresponding to the target mapping item; when the retrieval result is no, retrieve the target mapping item corresponding to the logical address in the Mapping area and output the physical address corresponding to the target mapping item .

Step S2, specifically includes:

S20. Set the end flag position of the target mapping item to 0;

S21. Store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix, and determine whether the remaining space in the H-Cache area is less than the preset threshold A. The original mapping item in the Cache area is migrated, and S22 is executed; when the judgment result is no, no operation is performed;

S22. Migrate the mapping items that have not been accessed for the longest time in the H-Cache area to the compressed prefix complete binary tree in the C-Cache area, and determine whether the remaining space in the C-Cache area is less than the preset threshold B, when the determination result is yes , sort the blocks in the C-Cache area according to the number of accesses, and check item by item that the flag bit of the mapping item in the block with the least number of accesses is 0 or 1. If the flag bit is 0, the mapping item is migrated to Mapping If the flag bit is 1, delete the mapping item; when the judgment result is no, no operation is performed.

In step S21, before storing the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix, the method further includes: establishing an uncompressed prefix of the H-Cache area by using an uncompressed prefix complete binary tree construction method Complete binary tree, wherein the method for constructing the uncompressed prefix complete binary tree specifically includes:

S200, establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1;

S201, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

S202, store a new mapping item into the Block block again, the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address;

S203. Repeat the operation of step S202 until all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, and then complete the tree through virtual nodes to obtain a complete binary tree with uncompressed prefixes.

In step S3, before judging whether there is a target mapping item corresponding to the logical address in the H-Cache, the method includes: establishing an uncompressed prefix complete binary tree in the H-Cache area by using an uncompressed prefix complete binary tree construction method, wherein the Non-compressed prefix complete binary tree construction method, including:

S210, establish a Block block as the root node, and set the Block block prefix to 0; Wherein, the number of mapping items stored in the Block block is 1;

S211, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

S212, store a new mapping item into the Block block, and the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address;

S213, repeat the operation of step S212, until after the mapping items that need to be stored in the tree in the H-Cache area are all stored in the tree, the tree is completed by the virtual node, and the non-compressed prefix complete binary tree is obtained;

In step S3, it is judged whether there is a target mapping item corresponding to the logical address in the H-Cache through an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes:

S300. Receive the logical address of the target mapping item;

S301, according to the height k of the complete binary tree of the prefix of the H-Cache area, get the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist;

S302, search whether the logical address of the target mapping item is stored in the Block, when the search result is yes, return the physical address corresponding to the logical address of the target mapping item; when the search result is no, execute S303;

S303, set k=k-1, perform operations S301 and S302, until K=1, perform S304;

S304, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree;

In step S3, before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, the method further includes: building a compressed prefix complete binary tree in the C-Cache area by using a compressed prefix complete binary tree construction method; Before retrieving the target mapping item corresponding to the logical address in the area and outputting the physical address corresponding to the target mapping item, the method further includes: building a compressed prefix complete binary tree of the Mapping area by using a compressed prefix complete binary tree construction method; wherein, the compressed prefix Complete binary tree construction methods, including:

S310, establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1＜M;

S311, the logical address first position of the mapping item that needs to be stored in the tree is set to 0, the first mapping item is stored in the Block block and data compression is performed;

S312: Decompress the Block block, and then store new mapping items into the Block block item by item, when the number of mapping items in the Block block has reached a set threshold M, split the Block block into The prefixes of the two child nodes and the two child block nodes are set to 00 and 01 respectively, and then the mapping items in the block node with the original prefix of 0 are checked item by item for the first two bits of its logical address, and the first two bits of the logical address are The mapping item of 00 is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is based on its logic. The first two digits of the address are stored in the corresponding sub-block node;

S313, repeat the operation of step S312, until after the mapping items that need to be stored in the tree are all stored in the tree, the tree is completed through the virtual node to obtain a compressed prefix complete binary tree;

In step S3, whether there is a target mapping item corresponding to the logical address in the C-Cache is searched by a compressed prefix complete binary tree search algorithm, and whether there is a target corresponding to the logical address in the Mapping area by a compressed prefix complete binary tree search algorithm Mapping items, wherein the compressed prefix complete binary tree retrieval algorithm specifically includes:

S320, receiving the logical address of the target mapping item;

S321. According to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item. ;

S322. Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S323;

S323, set k=k-1, perform operations S321 and S322, until K=1, perform S324;

S324, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, and retrieve whether the Bloom filter of the Block block contains the storage mark of the target mapping item , when the search result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the search result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree.

In step S3, in the process of retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, when the retrieval result is yes, the process of outputting the physical address corresponding to the target mapping item specifically includes: recording this time Retrieval time, when the target mapping item corresponding to the logical address is retrieved again within the preset time, transfer the target mapping item to the H-Cache area;

In step S3, the process of retrieving the target mapping item corresponding to the logical address in the Mapping area and outputting the physical address corresponding to the target mapping item further includes: retrieving the target corresponding to the logical address in the Mapping area The Block block where the mapping item is located, and the target mapping item in the Block block is backed up to the H-Cache area, and the other mapping items in the Block block are backed up to the C-Cache area.

A cache system for large-scale non-volatile storage media, including:

The judgment module is used for judging according to the user command request that it is the target mapping item write command request or the target mapping item read command request;

The write command module is used for, when the judgment module judges that the command request is a write command request of the target mapping item, the end flag position of the target mapping item is set to 0, and then the target mapping item is stored in the H-Cache area according to its logical address prefix ;

The read command module is used to obtain the logical address in the target mapping item read command request when the judgment module judges that the command request is a target mapping item read command request, and judges whether there is a target mapping corresponding to the logical address in the H-Cache item, when the judgment result is yes, output the physical address corresponding to the target mapping item; when the judgment result is no, search whether there is a target mapping item corresponding to the logical address in the C-Cache,

When the retrieval result is yes, output the physical address corresponding to the target mapping item; when the retrieval result is no, retrieve the target mapping item corresponding to the logical address in the Mapping area and output the physical address corresponding to the target mapping item .

The writing command module includes: a marking submodule, a judging submodule, a processing submodule, and a writing submodule;

The flag submodule is used to set the flag position at the end of the target mapping item to 0;

A judging submodule for judging whether the remaining space in the H-Cache area is less than the preset threshold A;

The processing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is yes, and map the original mapping in the H-Cache area. Migrate the original mapping items that have not been accessed for the longest time to the C-Cache area, and then judge whether the remaining space in the C-Cache area is less than the preset threshold B. When the judgment result is yes, change the C-Cache area. The Block blocks in the Cache area are sorted according to the number of visits, and the flag bit of the mapping item in the Block block with the least number of visits is checked to be 0 or 1. If the flag bit is 0, the mapping item is written to the Mapping area, and then the mapping is performed. The item flag position is 1. If the flag bit is 1, the mapping item is deleted; when the judgment result is no, no operation is performed;

The writing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is no.

The write command module is further configured to: before judging whether there is a target mapping item corresponding to the logical address in the H-Cache, establish an uncompressed prefix complete binary tree in the H-Cache area by using an uncompressed prefix complete binary tree construction method, wherein , the non-compressed prefix complete binary tree construction method specifically includes:

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1;

The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address;

After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through virtual nodes to obtain a complete binary tree with uncompressed prefixes.

The read command module is specifically used to: before judging whether there is a target mapping item corresponding to the logical address in the H-Cache, establish an uncompressed prefix complete binary tree in the H-Cache area by using an uncompressed prefix complete binary tree construction method, wherein , the non-compressed prefix complete binary tree construction method specifically includes:

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1;

The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address;

After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a non-compressed prefix complete binary tree;

Whether there is a target mapping item corresponding to the logical address in the H-Cache is determined by an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes:

S400. Receive the logical address of the target mapping item;

S401, according to the height k of the complete binary tree of the prefix of the H-Cache area, take the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist;

S402, search whether the logical address of the target mapping item is stored in the Block block, when the retrieval result is yes, return the physical address corresponding to the logical address of the target mapping item; when the retrieval result is no, execute S403;

S403, set k=k-1, perform operations S401 and S402, until K=1, perform S404;

S404, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree;

Before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, a compressed prefix complete binary tree in the C-Cache area is built by a compression prefix complete binary tree construction method; the target mapping corresponding to the logical address is retrieved in the Mapping area Before outputting the corresponding physical address of the target mapping item, a compressed prefix complete binary tree in the Mapping area is established by a compressed prefix complete binary tree construction method; wherein, the compressed prefix complete binary tree construction method, including:

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1<M;

The logical address first position of the mapping item that needs to be stored in the tree is set to 0, and the first mapping item is stored in the Block block and data compression is performed;

Decompress the Block block, and then store new mapping items into the Block block item by item, when the number of mapping items in the Block block has reached the set threshold M, split the Block block into two sub-blocks node, the prefixes of the two sub-Block block nodes are set to 00 and 01 respectively, and then the mapping items in the Block block node with the original prefix of 0 are checked item by item for the first two bits of its logical address, and the first two bits of the logical address are 00. The mapping item is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is stored according to its logical address. Two bits are stored in the corresponding sub-block node;

After all the mapping items that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a complete binary tree with a compressed prefix;

Whether there is a target mapping item corresponding to the logical address in the C-Cache is searched through a compressed prefix complete binary tree retrieval algorithm, and whether there is a target mapping item corresponding to the logical address in the Mapping area through a compressed prefix complete binary tree retrieval algorithm, wherein, The compressed prefix complete binary tree retrieval algorithm specifically includes:

S410, receiving the logical address of the target mapping item;

S411. According to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item. ;

S412: Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S413;

S413, set k=k-1, perform operations S411, S412, until K=1, perform S414;

S414, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, and retrieve whether the Bloom filter of the Block block contains the storage mark of the target mapping item , when the search result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the search result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree.

The read command module is also used for: retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, and when the retrieval result is yes, in the process of outputting the physical address corresponding to the target mapping item, recording this time Retrieval time, when the target mapping item corresponding to the logical address is retrieved again within the preset time, transfer the target mapping item to the H-Cache area;

In the process of retrieving the target mapping item corresponding to the logical address in the Mapping area and outputting the physical address corresponding to the target mapping item, the Block block where the target mapping item corresponding to the logical address is located is retrieved in the Mapping area, and all The target mapping items in the Block block are backed up to the H-Cache area, and other mapping items in the Block block are backed up to the C-Cache area.

The present invention divides the Cache into two parts C-Cache and H-Cache. The H-Cache part is used to ensure the high-speed access performance of the system. The C-Cache part compresses the mapping item data so that the limited storage space can store more mapping items, which improves the hit rate of the mapping items, thereby improving the The operation efficiency of the system is realized by three prefix complete binary trees in the C-Cache, H-Cache and Mapping areas respectively, and the retrieval algorithm of the prefix complete binary tree is used to improve the retrieval efficiency; the space in the Mapping area adopts the local update feature Compared with storing mapping items in flash media, it eliminates the problem of write amplification caused by off-site updating of mapping items, and reduces the time overhead caused by copying and transferring mapping items during off-site updates. Compared with flash memory devices, using this NVM medium to store the Mapping area's read and write rate will be significantly improved; because DRAM devices have faster access speeds than other storage devices, the operation of frequent data access is completed in DRAM, which improves the system performance. Operation efficiency, fully considering the principle of data access locality, taking the block as a unit to take out the mapping item and backing it up to the cache, avoiding frequent retrieval of mapping items in the mapping area, and improving the system operation efficiency. When a block in the Cache needs to be migrated out of the Cache, only the newly generated and updated mapping items are written back to the Mapping area, which reduces the amount of data written back to the NVM device while ensuring data consistency and improves the write back time efficiency.

Description of drawings

1 is a schematic flowchart of a caching method for a large-scale non-volatile storage medium proposed by the present invention;

Fig. 2 is a schematic diagram of cache management execution logic;

FIG. 3 is a schematic structural diagram of a prefix complete binary tree;

FIG. 4 is a schematic diagram of a mapping item structure;

5 is a schematic flowchart of a prefix complete binary tree retrieval algorithm;

Fig. 6 is an address mapping module diagram;

Fig. 7 is a system logic hierarchy diagram;

Figure 8 is a system hardware architecture diagram;

Fig. 9 is a schematic diagram of an address mapping process;

FIG. 10 is a schematic block diagram of a large-scale non-volatile storage medium-oriented cache system proposed by the present invention.

Detailed ways

Referring to FIG. 1 , a caching method for large-scale non-volatile storage media proposed by the present invention includes the following steps:

Step S1, according to the user command request, judge that it is a target mapping item write command request or a target mapping item read command request, and execute S2 when judging that the command request is a target mapping item write command request; when judging that the command request is a target mapping Execute S3 when the item read command is requested;

When a user sends a command request, it is determined whether the command request is a write command request or a read command request, and corresponding operations are performed according to different command requests.

Step S2, the target mapping item end flag position is 0, and then the target mapping item is stored in the H-Cache area according to its logical address prefix;

Step S2, specifically includes:

S20. Set the end flag position of the target mapping item to 0;

S21. Store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix, and determine whether the remaining space in the H-Cache area is less than the preset threshold A. The original mapping item in the Cache area is migrated, and S22 is executed; when the judgment result is no, no operation is performed;

S22. Migrate the mapping items that have not been accessed for the longest time in the H-Cache area to the compressed prefix complete binary tree in the C-Cache area, and determine whether the remaining space in the C-Cache area is less than the preset threshold B, when the determination result is yes , sort the blocks in the C-Cache area according to the number of accesses, and check item by item that the flag bit of the mapping item in the block with the least number of accesses is 0 or 1. If the flag bit is 0, the mapping item is migrated to Mapping If the flag bit is 1, delete the mapping item; when the judgment result is no, no operation is performed;

Referring to Figure 2, since the newly generated mapping item or the updated mapping item will be stored in the H-Cache first, when the mapping item enters the H-Cache, as shown in Figure 2, the system will mark the end of the mapping item. Set to 0, which is convenient for subsequent identification when data is migrated to the C-Cache, and the mapping items are migrated to the Mapping area again, reducing the amount of data written to the Mapping area again, and then judging whether the remaining space in the H-Cache area is smaller than the expected value. Set a threshold, when the remaining space in the H-Cache area is less than the threshold, reserve space for preparing new write mapping items, play a buffering role, make writing and data migration run concurrently, and improve time efficiency. When entering the H-Cache, you need to start the mapping item data migration in the H-Cache area where the new mapping item data is written, and migrate the mapping items that have not been accessed for the longest time to the appropriate location in the C-Cache area, such as 2 in Figure 2, then judge whether the remaining space in the C-Cache area is less than the preset threshold, when the remaining space in the C-Cache area is less than the threshold, reserve space for preparing new write mapping items, and play a buffering role, so that Writing and data migration run concurrently to improve time efficiency. If there is more data into the C-Cache, you need to start the mapping item data migration in the C-Cache area while writing new mapping item data. The number of accesses of the blocks in the block in the recent period is sorted, and the block with the least number of accesses is used as the sacrifice item, and the flag bits of all mapping items in the block are retrieved item by item. If the flag bit is 0, the mapping item is written back. Go to the appropriate position in the Mapping area, write it back to the Mapping area, as shown in Figure 2, 3, and then set the flag bit of the mapping item to 1; if the flag bit is 1, directly discard the mapping item to reduce writing back to Mapping The amount of mapping item data in the area reduces the write-back time and improves system efficiency.

Referring to FIG. 3, in this step, before storing the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix, it also includes: establishing the H-Cache area by the uncompressed prefix complete binary tree construction method The uncompressed prefix complete binary tree, wherein the method for constructing the uncompressed prefix complete binary tree specifically includes:

S200, establish a Block block as the root node, and set the Block block prefix to 0; Wherein, the number of mapping items stored in the Block block is 1;

S201, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

S202, store a new mapping item into the Block block again, the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address;

S203, repeating the operation of step S202, until after the mapping items that need to be stored in the tree in the H-Cache area are all stored in the tree, the tree is completed by the virtual node, and the non-compressed prefix complete binary tree is obtained;

The binary tree in H-Cache is an uncompressed prefix complete binary tree, which can improve retrieval efficiency and eliminate the overhead of compression and decompression. Each node stores a logical address-physical address mapping item.

Referring to FIG. 4 , the flag bit in the map entry structure has two states, wherein 0 represents a newly formed map entry or an updated map entry, and 1 represents an unupdated map entry.

Step S3, obtain the logical address in the target mapping item read command request, determine whether there is a target mapping item corresponding to the logical address in the H-Cache, and when the judgment result is yes, output the physical address corresponding to the target mapping item; When the judgment result is no, retrieve whether there is a target mapping item corresponding to the logical address in the C-Cache,

When the retrieval result is yes, output the physical address corresponding to the target mapping item; when the retrieval result is no, retrieve the target mapping item corresponding to the logical address in the Mapping area and output the physical address corresponding to the target mapping item ;

In this step, when there is a target mapping item corresponding to the logical address in the retrieval C-Cache, the process of outputting the physical address corresponding to the target mapping item further includes: recording the retrieval time, when preset When the target mapping item corresponding to the logical address is retrieved again within the time limit, transfer the target mapping item to the H-Cache area; retrieve the target mapping item corresponding to the logical address in the Mapping area and output the target In the process of mapping the physical address corresponding to the item, it also includes: retrieving the Block block where the target mapping item corresponding to the logical address is located in the Mapping area, and backing up the target mapping item in the Block block to the H-Cache area. Other mapping items in the Block block are backed up to the C-Cache area.

When obtaining the logical address in the read command request of the target mapping item and looking for its corresponding logical address-physical address mapping item, the mapping item is first retrieved in the H-Cache, and if it is retrieved in the H-Cache, its corresponding item is directly returned. If the physical address result is not found, it will be retrieved in the C-Cache. When retrieved in the C-Cache, the required physical address result will be returned to the upper-level system, and the access time in the C-Cache this time will be recorded. When the mapping item corresponding to the logical address hits again in the C-Cache after a period of time, the time interval between two accesses of the mapping item is calculated, and if the time interval is less than a specific threshold, the mapping item is transferred to H -The corresponding position in the Cache area, as shown in Figure 2, 4, if it has not been retrieved, go to the Mapping area for retrieval, as shown in Figure 2, 5; find the Block where the mapping item is located in the Mapping area, and then back up the mapping item to H -The appropriate position in the tree of the Cache and return the physical address result of the mapping item. Other mapping items in the Block are backed up item by item to the appropriate position in the tree of the C-Cache. According to the principle of locality, the mapping items around the mapping item It is very likely to be accessed again, so they are backed up in the Cache together, in order to take into account the characteristics of access locality, as shown in Figure 2 6.

Referring to FIG. 3, in this step, before judging whether there is a target mapping item corresponding to the logical address in the H-Cache, the method includes: establishing an uncompressed prefix complete binary tree in the H-Cache area by using an uncompressed prefix complete binary tree construction method, Wherein, the non-compressed prefix complete binary tree construction method specifically includes:

S210, establish a Block block as the root node, and set the Block block prefix to 0; Wherein, the number of mapping items stored in the Block block is 1;

S211, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

S212, store a new mapping item into the Block block, and the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address;

S213, repeat the operation of step S212 until all the mapping items that need to be stored in the tree in the H-Cache area are stored in the tree, and then complete the tree through the virtual node to obtain a complete binary tree with a non-compressed prefix;

The binary tree in H-Cache is an uncompressed prefix complete binary tree, which can improve retrieval efficiency and eliminate the overhead of compression and decompression. Each node stores a logical address-physical address mapping item.

Referring to Fig. 5, in this step, it is judged whether there is a target mapping item corresponding to the logical address in the H-Cache through an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes:

S300. Receive the logical address of the target mapping item;

S301, according to the height k of the complete binary tree of the prefix of the H-Cache area, get the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist;

S302, search whether the logical address of the target mapping item is stored in the Block, when the search result is yes, return the physical address corresponding to the logical address of the target mapping item; when the search result is no, execute S303;

S303, set k=k-1, perform operations S301 and S302, until K=1, perform S304;

S304, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree.

In this step, before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, the method further includes: building a compressed prefix complete binary tree in the C-Cache area by using a compressed prefix complete binary tree construction method; Before retrieving the target mapping item corresponding to the logical address in the area and outputting the physical address corresponding to the target mapping item, the method further includes: building a compressed prefix complete binary tree of the Mapping area by using a compressed prefix complete binary tree construction method; wherein, the compressed prefix Complete binary tree construction methods, including:

S310, establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1＜M;

S311, the logical address first position of the mapping item that needs to be stored in the tree is set to 0, the first mapping item is stored in the Block block and data compression is performed;

S312: Decompress the Block block, and then store new mapping items into the Block block item by item, when the number of mapping items in the Block block has reached a set threshold M, split the Block block into The prefixes of the two child nodes and the two child block nodes are set to 00 and 01 respectively, and then the mapping items in the block node with the original prefix of 0 are checked item by item for the first two bits of its logical address, and the first two bits of the logical address are The mapping item of 00 is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is based on its logic. The first two digits of the address are stored in the corresponding sub-block node;

S313, repeat the operation of step S312, until after the mapping items that need to be stored in the tree are all stored in the tree, the tree is completed through the virtual node to obtain a compressed prefix complete binary tree;

In this step, whether there is a target mapping item corresponding to the logical address in the C-Cache is searched by a compressed prefix complete binary tree search algorithm, and whether there is a target corresponding to the logical address in the Mapping area by a compressed prefix complete binary tree search algorithm Mapping items, wherein the compressed prefix complete binary tree retrieval algorithm specifically includes:

S320, receiving the logical address of the target mapping item;

S321. According to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item. ;

S322. Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S323;

S323, set k=k-1, perform operations S321 and S322, until K=1, perform S324;

S324, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, and retrieve whether the Bloom filter of the Block block contains the storage mark of the target mapping item , when the retrieval result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree;

The binary tree in the C-Cache and Mapping area is a compressed prefix complete binary tree, each node is a compressed block, and each block stores multiple mapping items with the same prefix as the block prefix.

Referring to Figure 6, Cache is implemented based on DRAM and is divided into two parts: H-Cache and C-Cache. H-Cache mainly stores "active" mapping items that are frequently accessed; C-Cache mainly stores "relatively inactive" mapping items that have been migrated from H-Cache. Multiple mapping items are stored in appropriate locations according to their logical address prefixes. Compression is carried out in the block, through the compression technology, the limited Cache space can store more mapping items, improve the hit rate of mapping items, and improve the operating efficiency of the system;

The Mapping area is implemented based on NVM devices that support local updates. Its goal is to store complete mapping item data. The mapping item data is mainly derived from C-Cache migration data. Multiple mapping items are stored in the appropriate Block according to their logical address prefixes. middle.

Referring to Figure 7, D-Cache is partially implemented based on DRAM media and is used to temporarily store data written or read by users; NVM Data Storage is partially implemented based on NVM media, where only data information is stored, and other information such as address mapping is not stored.

Referring to Figure 8 and Figure 9, when the system writes data to the storage system, the upper layer of the host operating system transmits the data and the logical address, offset, and size. The data is temporarily stored in the D-Cache, and the controller stores the data for it according to the size of the data. A physical space of a suitable size is allocated on the device, and the physical address of the first address of the space is returned to form a logical address-physical address mapping item, which is stored in the address mapping module.

When the system reads data from the storage system, the upper layer of the host operating system transfers its logical address to the address mapping module, and uses the data caching and retrieval method of this scheme to obtain the physical address corresponding to the logical address, and then obtains the physical address corresponding to the logical address from the storage corresponding to the physical address. The data is read from the space and returned to the upper system through D-Cache.

Referring to FIG. 10 , a large-scale non-volatile storage medium-oriented cache system proposed by the present invention includes:

a judgment module, used to obtain a user command request, and judge that the command request is a target mapping item write command request or a target mapping item read command request;

When a user sends a command request, it is determined whether the command request is a write command request or a read command request, and corresponding operations are performed according to different command requests.

The write command module is used for, when the judgment module judges that the command request is a write command request of the target mapping item, the end flag position of the target mapping item is set to 0, and then the target mapping item is stored in the H-Cache area according to its logical address prefix ;

The writing command module includes: a marking submodule, a judging submodule, a processing submodule, and a writing submodule;

The flag submodule is used to set the flag position at the end of the target mapping item to 0;

A judging submodule for judging whether the remaining space in the H-Cache area is less than the preset threshold A;

The processing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is yes, and map the original mapping in the H-Cache area. Migrate the original mapping items that have not been accessed for the longest time to the C-Cache area, and then judge whether the remaining space in the C-Cache area is less than the preset threshold B. When the judgment result is yes, change the C-Cache area. The Block blocks in the Cache area are sorted according to the number of visits, and the flag bit of the mapping item in the Block block with the least number of visits is checked to be 0 or 1. If the flag bit is 0, the mapping item is written to the Mapping area, and then the mapping is performed. The item flag position is 1. If the flag bit is 1, the mapping item is deleted; when the judgment result is no, no operation is performed;

The writing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is no.

Referring to Figure 2, since the newly generated mapping item or the updated mapping item will be stored in the H-Cache first, when the mapping item enters the H-Cache, as shown in Figure 2, the system will mark the end of the mapping item. It is 0, which is convenient for subsequent identification when the data is migrated to the C-Cache and the mapping items are migrated to the Mapping area again, reducing the amount of data written to the Mapping area again, and then assigning a threshold to the H-Cache. When the remaining space in the Cache area is less than the threshold, space is reserved for preparing new write mapping items, which acts as a buffer, so that writing and data migration run concurrently, improving time efficiency. Then it is necessary to start the data migration of the mapping item in the H-Cache area while writing the new mapping item data, and migrate the mapping item that has not been accessed for the longest time to the appropriate location in the C-Cache area, as shown in Figure 2 in 2, Then assign a threshold value to C-Cache. When the remaining space in the C-Cache area is less than the threshold value, reserve space for preparing new write mapping items, play a buffering role, make writing and data migration run concurrently, and improve time efficiency , if there is more data into the C-Cache, you need to start the mapping item data migration in the C-Cache area while writing the new mapping item data, and the number of accesses to the Block in the C-Cache area in the recent period Sort, take the block with the least number of visits as the victim item, and retrieve the flag bits of all mapping items in the block one by one. If the flag bit is 0, write the mapping item back to the appropriate location in the Mapping area, and write back In the Mapping area, as shown in Figure 2, 3, and then the flag bit of the mapping item is set to 1; if the flag bit is 1, the mapping item is directly discarded to reduce the amount of mapping item data written back to the Mapping area and reduce write-back time and improve system efficiency.

Referring to Figure 3, the write command module is also used to: before storing the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix, establish a non-compressed prefix complete binary tree construction method in the H-Cache area. A compressed prefix complete binary tree, wherein the method for constructing the uncompressed prefix complete binary tree specifically includes:

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1;

The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address;

After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a non-compressed prefix complete binary tree;

The binary tree in H-Cache is an uncompressed prefix complete binary tree, which can improve retrieval efficiency and eliminate the overhead of compression and decompression. Each node stores a logical address-physical address mapping item.

The read command module is used to obtain the logical address in the target mapping item read command request when the judgment module judges that the command request is a target mapping item read command request, and determine whether there is a target corresponding to the logical address in the H-Cache mapping item, when the judgment result is yes, output the physical address corresponding to the target mapping item; when the judgment result is no, search whether there is a target mapping item corresponding to the logical address in the C-Cache, when the search result is yes When the corresponding physical address of the target mapping item is output, when the retrieval result is no, the target mapping item corresponding to the logical address is retrieved in the Mapping area and the physical address corresponding to the target mapping item is output;

The read command module is further configured to: record the retrieval time during the process of outputting the physical address corresponding to the target mapping item when there is a target mapping item corresponding to the logical address in the retrieval C-Cache, when the preset time When the target mapping item corresponding to the logical address is retrieved again, the target mapping item is transferred to the H-Cache area;

In the process of retrieving the target mapping item corresponding to the logical address in the Mapping area and outputting the physical address corresponding to the target mapping item, the Block block where the target mapping item corresponding to the logical address is located is retrieved in the Mapping area, and all The target mapping items in the Block block are backed up to the H-Cache area, and other mapping items in the Block block are backed up to the C-Cache area.

When obtaining the logical address in the read command request of the target mapping item and looking for its corresponding logical address-physical address mapping item, the mapping item is first retrieved in H-Cache, and if it is retrieved in H-Cache, its corresponding item is directly returned. If the physical address result is not found, it will be retrieved in the C-Cache. When retrieved in the C-Cache, the required physical address result will be returned to the upper-layer system, and the access time in the C-Cache this time will be recorded. When the mapping item corresponding to the logical address is hit again in the C-Cache after a period of time, the time interval between two accesses of the mapping item is calculated, and if the time interval is less than a specific threshold, the mapping item is transferred to H -The corresponding position in the Cache area, as shown in Figure 2, 4, if it has not been retrieved, search it in the Mapping area, as shown in Figure 2, 5; find the Block where the mapping item is located in the Mapping area, and then back up the mapping item to H -The appropriate position in the tree of the Cache and return the physical address result of the mapping item. Other mapping items in the Block are backed up item by item to the appropriate position in the tree of the C-Cache. According to the principle of locality, the mapping items around the mapping item It is very likely to be accessed again, so they are backed up in the Cache together, in order to take into account the characteristics of access locality, as shown in Figure 2 6.

The read command module is specifically used for: before judging whether there is a target mapping item corresponding to the logical address in the H-Cache, establish a non-compressed prefix complete binary tree in the H-Cache area by the non-compressed prefix complete binary tree construction method, wherein, all Describe the construction method of uncompressed prefix complete binary tree, including:

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1;

The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block;

A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address;

After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a non-compressed prefix complete binary tree;

The binary tree in H-Cache is an uncompressed prefix complete binary tree, which can improve retrieval efficiency and eliminate the overhead of compression and decompression. Each node stores a logical address-physical address mapping item.

Referring to Figure 5, the read command module is also used to: determine whether there is a target mapping item corresponding to the logical address in the H-Cache through an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes :

S400. Receive the logical address of the target mapping item;

S401, according to the height k of the complete binary tree of the prefix of the H-Cache area, take the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist;

S402, search whether the logical address of the target mapping item is stored in the Block block, when the retrieval result is yes, return the physical address corresponding to the logical address of the target mapping item; when the retrieval result is no, execute S403;

S403, set k=k-1, perform operations S401 and S402, until K=1, perform S404;

S404, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree.

The read command module is also used to: before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, build a compressed prefix complete binary tree in the C-Cache area by using the compressed prefix complete binary tree construction method; search in the Mapping area Before outputting the target mapping item corresponding to the logical address and outputting the physical address corresponding to the target mapping item, a compressed prefix complete binary tree construction method in the Mapping area is used to build a compressed prefix complete binary tree; wherein, the compressed prefix complete binary tree construction method includes: :

Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1<M;

The logical address first position of the mapping item that needs to be stored in the tree is set to 0, and the first mapping item is stored in the Block block and data compression is performed;

Decompress the Block block, and then store new mapping items in the Block block item by item, when the number of mapping items in the Block block has reached the set threshold M, split the Block block into two blocks. The prefixes of the two sub-block nodes are set to 00 and 01 respectively, and then the mapping items in the block node with the original prefix of 0 are checked one by one for the first two bits of its logical address, and the first two bits of the logical address are set to 00 The mapping item is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is based on its logical address. The first two bits are stored in the corresponding sub-block node;

After all the mapping items that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a complete binary tree with a compressed prefix;

The read command module is also used for: retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache through the compressed prefix complete binary tree retrieval algorithm, and retrieving whether there is the logical address in the Mapping area through the compressed prefix complete binary tree retrieval algorithm Corresponding target mapping items, wherein, the compressed prefix complete binary tree retrieval algorithm specifically includes:

S410, receiving the logical address of the target mapping item;

S411. According to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item. ;

S412: Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S413;

S413, set k=k-1, perform operations S411, S412, until K=1, perform S414;

S414, according to the first 1 bit of the logical address of the target mapping item and the fast calculation algorithm of the binary tree Block block sequence number, calculate the Block block number that the target mapping item may exist, and retrieve whether the Bloomfilter of the Block block contains the storage mark of the target mapping item, When the retrieval result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree;

The binary tree in the C-Cache and Mapping area is a compressed prefix complete binary tree, each node is a compressed block, and each block stores multiple mapping items with the same prefix as the block prefix.

In this embodiment, the Cache is divided into two parts, C-Cache and H-Cache. The H-Cache part is used to ensure the high-speed access performance of the system. The C-Cache part compresses the mapping item data so that the limited storage space can store more mapping items, which improves the hit rate of the mapping items, thereby improving the The operation efficiency of the system is realized by three prefix complete binary trees in the C-Cache, H-Cache and Mapping areas respectively, and the retrieval algorithm of the prefix complete binary tree is used to improve the retrieval efficiency; the space in the Mapping area adopts the local update feature Compared with storing mapping items in flash media, it eliminates the problem of write amplification caused by off-site updating of mapping items, and reduces the time overhead caused by copying and transferring mapping items when updating off-site. Compared with traditional flash memory devices, using this NVM medium to store the Mapping area will significantly increase the read and write rates; since DRAM devices have faster access speeds than other storage devices, the frequent data access operations are done in DRAM, which improves the performance. The operating efficiency of the system fully considers the principle of data access locality. The mapping items are taken out in blocks and backed up to the cache, which avoids frequent retrieval of mapping items in the mapping area, and improves the operating efficiency of the system. Through the partial write-back strategy, when C -When a block in the Cache needs to be migrated out of the Cache, only the newly generated and updated mapping items are written back to the Mapping area, which reduces the amount of data written back to the NVM device while ensuring data consistency and improves the write back time. efficiency.

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. The equivalent replacement or change of the inventive concept thereof shall be included within the protection scope of the present invention.

Claims (8)

1. A cache method for a large-scale non-volatile storage medium, characterized in that the method comprises the following steps: S1. According to the user command request, it is judged that it is a target mapping item write command request or a target mapping item read command request, and S2 is executed when it is judged that the command request is a target mapping item write command request; when it is judged that the command request is a target mapping item Execute S3 when the read command is requested; S2. Set the end flag position of the target mapping item to 0, and then store the target mapping item in the H-Cache area according to its logical address prefix; S3, obtain the logical address in the target mapping item read command request, search whether there is a target mapping item corresponding to the logical address in the H-Cache, when the judgment result is yes, output the physical address corresponding to the target mapping item; when When the judgment result is no, retrieve whether there is a target mapping item corresponding to the logical address in the C-Cache, When the retrieval result is yes, output the physical address corresponding to the target mapping item; when the retrieval result is no, retrieve the target mapping item corresponding to the logical address in the Mapping area and output the physical address corresponding to the target mapping item ; Among them, the Cache is divided into two parts: C-Cache and H-Cache; the space in the Mapping area is stored by NVM media with local update characteristics; Step S2, specifically includes: S20. Set the end flag position of the target mapping item to 0; S21. Store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix, and determine whether the remaining space in the H-Cache area is less than the preset threshold A. The original mapping item in the Cache area is migrated, and S22 is executed; when the judgment result is no, no operation is performed; S22. Migrate the mapping items that have not been accessed for the longest time in the H-Cache area to the compressed prefix complete binary tree in the C-Cache area, and determine whether the remaining space in the C-Cache area is less than the preset threshold B, when the determination result is yes , sort the blocks in the C-Cache area according to the number of accesses, and check item by item that the flag bit of the mapping item in the block with the least number of accesses is 0 or 1. If the flag bit is 0, the mapping item is migrated to Mapping If the flag bit is 1, delete the mapping item; when the judgment result is no, no operation is performed. 2. The large-scale non-volatile storage medium-oriented caching method according to claim 1, wherein in step S21, the target mapping item is stored in the non-volatile memory of the H-Cache area according to its logical address prefix. Before compressing the prefix complete binary tree, the method further includes: establishing an uncompressed prefix complete binary tree in the H-Cache area by using an uncompressed prefix complete binary tree construction method, wherein the uncompressed prefix complete binary tree construction method specifically includes: S200, establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1; S201, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block; S202, store a new mapping item into the Block block again, the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address; S203. Repeat the operation of step S202 until all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, and then complete the tree through virtual nodes to obtain a complete binary tree with uncompressed prefixes. 3. The large-scale non-volatile storage medium-oriented caching method according to claim 1, wherein in step S3, before retrieving whether there is a target mapping item corresponding to the logical address in the H-Cache, Including: building an uncompressed prefix complete binary tree in the H-Cache area by a method for constructing an uncompressed prefix complete binary tree, wherein the method for constructing an uncompressed prefix complete binary tree specifically includes: S210, establish a Block block as the root node, and set the Block block prefix to 0; Wherein, the number of mapping items stored in the Block block is 1; S211, the logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block; S212, store a new mapping item into the Block block, and the number of mapping items stored in the Block block is full, split the Block block into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set as 00 and 01, and then check the first two bits of the logical address of the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits of the logical address are 00 to the sub-block node with the prefix 00. , transfer the mapping item whose first two bits of logical address are 01 to the sub-block block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block block node according to the first two bits of its logical address; S213, repeat the operation of step S212, until after the mapping items that need to be stored in the tree in the H-Cache area are all stored in the tree, the tree is completed by the virtual node, and the non-compressed prefix complete binary tree is obtained; In step S3, whether there is a target mapping item corresponding to the logical address in the H-Cache is searched through an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes: S300. Receive the logical address of the target mapping item; S301, according to the height k of the complete binary tree of the prefix of the H-Cache area, get the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist; S302, search whether the logical address of the target mapping item is stored in the Block, when the search result is yes, return the physical address corresponding to the logical address of the target mapping item; when the search result is no, execute S303; S303, set k=k-1, perform operations S301 and S302, until K=1, perform S304; S304, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree; In step S3, before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, the method further includes: building a compressed prefix complete binary tree in the C-Cache area by using a compressed prefix complete binary tree construction method; Before retrieving the target mapping item corresponding to the logical address in the area and outputting the physical address corresponding to the target mapping item, the method further includes: building a compressed prefix complete binary tree of the Mapping area by using a compressed prefix complete binary tree construction method; wherein, the compressed prefix Complete binary tree construction methods, including: S310, establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1＜M; S311, the logical address first position of the mapping item that needs to be stored in the tree is set to 0, the first mapping item is stored in the Block block and data compression is performed; S312: Decompress the Block block, and then store new mapping items into the Block block item by item, when the number of mapping items in the Block block has reached a set threshold M, split the Block block into The prefixes of the two child nodes and the two child block nodes are set to 00 and 01 respectively, and then the mapping items in the block node with the original prefix of 0 are checked item by item for the first two bits of its logical address, and the first two bits of the logical address are The mapping item of 00 is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is based on its logic. The first two digits of the address are stored in the corresponding sub-block node; S313, repeat the operation of step S312, until after the mapping items that need to be stored in the tree are all stored in the tree, the tree is completed through the virtual node to obtain a compressed prefix complete binary tree; In step S3, whether there is a target mapping item corresponding to the logical address in the C-Cache is searched by a compressed prefix complete binary tree search algorithm, and whether there is a target corresponding to the logical address in the Mapping area by a compressed prefix complete binary tree search algorithm Mapping items, wherein the compressed prefix complete binary tree retrieval algorithm specifically includes: S320, receiving the logical address of the target mapping item; S321. According to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item. ; S322. Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S323; S323, set k=k-1, perform operations S321 and S322, until K=1, perform S324; S324, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, and retrieve whether the Bloom filter of the Block block contains the storage mark of the target mapping item , when the search result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the search result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree. 4. The large-scale non-volatile storage medium-oriented caching method according to claim 1, wherein in step S3, whether there is a target mapping item corresponding to the logical address in the retrieval C-Cache, When the retrieval result is yes, the process of outputting the physical address corresponding to the target mapping item specifically includes: recording the retrieval time, and when the target mapping item corresponding to the logical address is retrieved again within a preset time, transferring the target mapping entry to the H-Cache area; In step S3, the process of retrieving the target mapping item corresponding to the logical address in the Mapping area and outputting the physical address corresponding to the target mapping item further includes: retrieving the target corresponding to the logical address in the Mapping area The Block block where the mapping item is located, and the target mapping item in the Block block is backed up to the H-Cache area, and the other mapping items in the Block block are backed up to the C-Cache area. 5. A cache system for large-scale non-volatile storage media, characterized in that it comprises: The judgment module is used for judging according to the user command request that it is the target mapping item write command request or the target mapping item read command request; The write command module is used for, when the judgment module judges that the command request is a write command request of the target mapping item, the end flag position of the target mapping item is set to 0, and then the target mapping item is stored in the H-Cache area according to its logical address prefix ; The read command module is used to obtain the logical address in the target mapping item read command request when the judgment module judges that the command request is a target mapping item read command request, and retrieves whether there is a target mapping corresponding to the logical address in the H-Cache item, when the judgment result is yes, output the physical address corresponding to the target mapping item; when the judgment result is no, search whether there is a target mapping item corresponding to the logical address in the C-Cache, When the retrieval result is yes, output the physical address corresponding to the target mapping item; when the retrieval result is no, retrieve the target mapping item corresponding to the logical address in the Mapping area and output the physical address corresponding to the target mapping item ; The writing command module includes: a marking submodule, a judging submodule, a processing submodule, and a writing submodule; The flag submodule is used to set the flag position at the end of the target mapping item to 0; A judging submodule for judging whether the remaining space in the H-Cache area is less than the preset threshold A; The processing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree of the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is yes, and map the original mapping in the H-Cache area. Migrate the original mapping items that have not been accessed for the longest time to the C-Cache area, and then judge whether the remaining space in the C-Cache area is less than the preset threshold B. When the judgment result is yes, change the C-Cache area. The Block blocks in the Cache area are sorted according to the number of visits, and the flag bit of the mapping item in the Block block with the least number of visits is checked to be 0 or 1. If the flag bit is 0, the mapping item is written to the Mapping area, and then the mapping is performed. The item flag position is 1. If the flag bit is 1, the mapping item is deleted; when the judgment result is no, no operation is performed; The writing sub-module is used to store the target mapping item in the uncompressed prefix complete binary tree in the H-Cache area according to its logical address prefix when the judgment result of the judging sub-module is no. 6 . The large-scale non-volatile storage medium-oriented cache system according to claim 5 , wherein the write command module is further used for: retrieving whether there is a corresponding logical address in the H-Cache. 7 . Before the target mapping item, an uncompressed prefix complete binary tree construction method in the H-Cache area is used to build an uncompressed prefix complete binary tree, wherein the uncompressed prefix complete binary tree construction method specifically includes: Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1; The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block; A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address; After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through virtual nodes to obtain a complete binary tree with uncompressed prefixes. 7 . The large-scale non-volatile storage medium-oriented cache system according to claim 5 , wherein the read command module is specifically used for: retrieving whether there is a corresponding logical address in the H-Cache. 8 . Before the target mapping item, an uncompressed prefix complete binary tree construction method in the H-Cache area is used to build an uncompressed prefix complete binary tree, wherein the uncompressed prefix complete binary tree construction method specifically includes: Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is 1; The logical address first position of the mapping item that needs to be stored in the tree in the H-Cache area is set to 0, and the first mapping item is stored in the Block block; A new mapping item is then stored in the Block block, the number of mapping items stored in the Block block is full, and the Block block is split into two sub-nodes, and the prefixes of the two sub-Block block nodes are respectively set to 00 and 01, and then check the first two bits of its logical address for the mapping items in the original block node with the prefix 0, and transfer the mapping items whose first two bits are 00 to the sub-block node with the prefix 00, Transfer the mapping item whose first two bits of the logical address are 01 to the sub-block node whose prefix is 01, and finally store the newly stored mapping item in the corresponding sub-block node according to the first two bits of its logical address; After all the mapping items in the H-Cache area that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a non-compressed prefix complete binary tree; Whether there is a target mapping item corresponding to the logical address in the H-Cache is retrieved through an uncompressed prefix complete binary tree retrieval algorithm, wherein the uncompressed prefix complete binary tree retrieval algorithm specifically includes: S400, receiving the logical address of the target mapping item; S401, according to the height k of the complete binary tree of the prefix of the H-Cache area, take the first k bits of the logical address of the target mapping item, and utilize the binary tree Block block sequence number fast calculation algorithm to calculate the block number that the target mapping item may exist; S402, search whether the logical address of the target mapping item is stored in the Block block, when the retrieval result is yes, return the physical address corresponding to the logical address of the target mapping item; when the retrieval result is no, execute S403; S403, set k=k-1, perform operations S401 and S402, until K=1, perform S404; S404, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, retrieve whether the logical address of the target mapping item is stored in the Block block, when the retrieval When the result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the retrieval result is no, it means that the logical address of the target mapping item does not exist in the uncompressed prefix complete binary tree; Before retrieving whether there is a target mapping item corresponding to the logical address in the C-Cache, a compressed prefix complete binary tree in the C-Cache area is built by a compression prefix complete binary tree construction method; the target mapping corresponding to the logical address is retrieved in the Mapping area Before outputting the corresponding physical address of the target mapping item, a compressed prefix complete binary tree in the Mapping area is established by a compressed prefix complete binary tree construction method; wherein, the compressed prefix complete binary tree construction method, including: Establish a Block block as the root node, and set the Block block prefix to 0; wherein, the number of mapping items stored in the Block block is M, where 1<M; The logical address first position of the mapping item that needs to be stored in the tree is set to 0, and the first mapping item is stored in the Block block and data compression is performed; Decompress the Block block, and then store new mapping items into the Block block item by item, when the number of mapping items in the Block block has reached the set threshold M, split the Block block into two sub-blocks node, the prefixes of the two sub-Block block nodes are set to 00 and 01 respectively, and then the mapping items in the Block block node with the original prefix of 0 are checked item by item for the first two bits of its logical address, and the first two bits of the logical address are 00. The mapping item is transferred to the sub-block node with the prefix 00, the mapping item whose first two bits of the logical address are 01 are transferred to the sub-block node with the prefix 01, and finally the newly stored mapping item is stored according to its logical address. Two bits are stored in the corresponding sub-block node; After all the mapping items that need to be stored in the tree are stored in the tree, the tree is completed through the virtual node to obtain a complete binary tree with a compressed prefix; Whether there is a target mapping item corresponding to the logical address in the C-Cache is searched through a compressed prefix complete binary tree retrieval algorithm, and whether there is a target mapping item corresponding to the logical address in the Mapping area through a compressed prefix complete binary tree retrieval algorithm, wherein, The compressed prefix complete binary tree retrieval algorithm specifically includes: S410, receiving the logical address of the target mapping item; S411, according to the height k of the compressed prefix complete binary tree in the C-Cache area or the Mapping area, take the first k bits of the logical address of the target mapping item, and use the binary tree Block block sequence number fast calculation algorithm to calculate the block number that may exist in the target mapping item ; S412: Retrieve whether the Bloom filter of the Block block contains the storage tag of the target mapping item, when the retrieval result is yes, decompress the Block block and return the physical address corresponding to the logical address of the target mapping item, and then compress the Block block; when the retrieval result is no, execute S413; S413, set k=k-1, perform operations S411, S412, until K=1, perform S414; S414, according to the first 1 bit of the logical address of the target mapping item and the binary tree Block block sequence number fast calculation algorithm, calculate the Block block number that may exist in the target mapping item, and retrieve whether the Bloom filter of the Block block contains the storage mark of the target mapping item , when the search result is yes, the physical address corresponding to the logical address of the target mapping item is returned; when the search result is no, it means that the logical address of the target mapping item does not exist in the compressed prefix complete binary tree. 8. The large-scale non-volatile storage medium-oriented cache system according to claim 5, wherein the read command module is further used for: retrieving whether there is a target corresponding to the logical address in the C-Cache Mapping item, when the retrieval result is yes, in the process of outputting the physical address corresponding to the target mapping item, record the retrieval time, when the target mapping item corresponding to the logical address is retrieved again within the preset time, transferring the target mapping entry to the H-Cache area; In the process of retrieving the target mapping item corresponding to the logical address in the Mapping area and outputting the physical address corresponding to the target mapping item, the Block block where the target mapping item corresponding to the logical address is located is retrieved in the Mapping area, and all The target mapping items in the Block block are backed up to the H-Cache area, and other mapping items in the Block block are backed up to the C-Cache area.

Images