CN108845957B - A permutation and write-back adaptive buffer management method - Google Patents

Abstract

The invention provides an adaptive buffer management method for replacement and write-back, which divides the buffer into a buffer block record table, a write buffer zone and a read buffer zone; wherein, the buffer block record table is used to record data belonging to the same logical data block. The location information of the data page in the buffer. The write buffer is used to cache the data pages that have been modified in response to the write request, and the read buffer is used to cache the data pages that have not been modified in response to the read request. The present invention adopts a page-level management method when loading and removing data pages, and adjusts the read buffer threshold value adaptively through a period, so that the change of the read and write characteristics of the load can be sensed, so that the management method can achieve higher performance under various load conditions. cache hit rate. At the same time, the use of dirty page adaptive cluster write-back can sense the pressure of FTL layer garbage collection and adaptively adjust the write-back strategy, which can effectively reduce the number of extra block erasures caused by FTL garbage collection and improve the performance of solid-state drives. Overall performance and longevity.

Description

A permutation and write-back adaptive buffer management method

technical field

The invention belongs to the technical field of firmware optimization method design based on flash solid state disks, and discloses a buffer management method for replacement and write-back adaptive.

Background technique

Toshiba proposed a new type of non-volatile storage medium - NAND flash memory in 1989, which is widely used in embedded devices because of its high performance, low power consumption and good shock resistance. Laptops and enterprise storage systems. The flash memory mentioned in this article is NAND flash memory.

The buffer is an integral part of the storage system. By storing frequently accessed data in a small-capacity cache, the I/O performance of the storage system can be effectively improved. For decades, researchers have proposed many classical and effective buffer methods for storage systems with mechanical hard disks as the main storage medium, such as FIFO (first-in first-out method), LRU (longest unused method), LFU (least used replacement method) ), and LRFU (Recent and Least Frequently Used Permutation Method), etc. However, the underlying storage medium of solid-state drives is flash memory, which has distinct characteristics different from traditional magnetic media. Therefore, traditional cache management algorithms for mechanical hard disks are difficult to apply in the design of solid-state disk cache areas.

The underlying NAND flash memory of solid-state drives has the following limitations: 1) Flash memory only provides three operations: read, write, and erase, and the performance of these three operations is asymmetric, with the fastest read, followed by write, and the slowest erase; 2) Flash memory It is organized according to the structure of page, block and plane; page is the smallest unit of read/write, generally 2/4/8KB; block is the smallest unit of erasure, and a block generally contains 64/128 pages; 3) The flash memory can only be written once after erasing, the so-called erase-before-write, which causes the flash memory to not support in-place updates; 4) Program/erase (P/ E) The number of times is limited. After the P/E times are exceeded, the data stored in the flash memory is no longer reliable.

Aiming at the read-write asymmetry of flash memory, researchers have proposed a series of flash-oriented buffer methods, which can be divided into page-level buffer methods and block-level buffer methods according to the operation granularity.

Page-level buffer method: Most of the improved methods are based on LRU. The classic and effective methods include CFLRU (clean page first least recently replaced) method, CCF-LRU (cold clean page first least recently replaced) method, AD- LRU (Adaptive Double Queue Least Cold Region Replacement) method. However, these methods only consider the status of the replacement page in the buffer, while ignoring the characteristics of the current access load, resulting in various methods only applicable to specific loads to obtain better performance. Compared with the page-level buffer method, which uses a single page for the write-back operation, the block-level buffer method uses the block as the organizational unit to perform the write-back operation during the write-back operation, which can effectively reconstruct the access mode and convert random write requests into continuous write requests. The write request can effectively reduce the garbage collection overhead of the underlying FTL.

Block-level buffer method: Based on the BPLRU (block filling least recently replaced) method and the FAB (largest block first replacement) method, the PUD-LRU (Predicted average Update Distance aware LRU) method is derived, and the CLC (Cold and Largest Cluster) method is derived. method. However, these block-level buffer methods only cache write requests, and their performance is poor in a load environment dominated by read requests. In addition, these block-level cache methods do not distinguish between hot and cold data pages in the same write-back block when dirty pages are written back, resulting in some hot data pages being written back prematurely, and the underlying flash conversion cannot be sensed during write-back. Layer (Flash Translation Layer, FTL) garbage collection pressure, using a single write-back strategy, resulting in additional garbage collection overhead of the FTL layer.

SUMMARY OF THE INVENTION

Aiming at the above-mentioned deficiencies in the prior art, the present invention discloses an adaptive buffer management method for replacement and write-back, which can not only dynamically adjust the replacement strategy according to the load reading and writing characteristics to improve the buffer read and write hit rate, but also can improve the buffer read and write hit rate during aggregation. Retains hot data pages during cluster write-back and adjusts the write-back strategy according to Flash Translation Layer (FTL) garbage collection pressure to reduce the number of erasures of underlying flash blocks.

For realizing the purpose of the present invention, the present invention adopts the following technical solutions:

An adaptive buffer management method for replacement and write-back, wherein the buffer is divided into a cache block record table, a write buffer and a read buffer; the cache block record table is used to record data pages belonging to the same logical data block The location information of the buffer, the write buffer is used to cache the data pages that have been modified in response to the write request, and the read buffer is used to cache the unmodified data pages that only respond to the read request;

The management method includes the following steps:

S1, when the access request arrives, check whether the cache block record table contains the cache block information corresponding to the request, if so, execute S2, otherwise, execute S4;

S2, query whether there is a location pointer pointing to the requested data page in the cache block record table, if so, execute S3, otherwise, execute S5;

S3, migrate the hit data page to the MRU position of the corresponding buffer, and update the position pointer list in the corresponding cache block record table; then execute S8;

S4, add the corresponding record block information to the cache block record table, initialize all the information of the record block at the same time, and then execute S5;

S5, determine whether the current buffer is full; if it is full, execute S6, otherwise, execute S7;

S6, compare the size of the read buffer with the target threshold Tau; if it is greater than the size of the read buffer, select the data page at the LRU position of the read buffer to be culled, otherwise, select the data page at the LRU position of the write buffer as the culling item and perform adaptive clustering Write back; update the record block information corresponding to the excluded data page, and then execute S7;

S7, load the missing request data page into the corresponding buffer zone, add the position pointing to the data page to the position pointer list of the corresponding cache block record table, and update the corresponding record block information; then execute S8;

S8, start the replacement policy threshold adjustment mechanism to adjust the threshold Tau; finally, end the processing of this request.

Further, the read buffer and the write buffer use LRU to manage the queue, and when the buffer hits the request and loads the new data page, the hit request and the new data page loaded are migrated to the MRU position of the queue.

Further, in the described cache block record table, the information of a record block includes: the cache block number BlkNum, the number BlkSize of the data pages that belong to the record block in the buffer, and the clean page position pointer list C-list that belongs to the record block. -index, the list of dirty page location pointers D-list-index that belong to the same record block.

Further, in the step S3, updating the position pointer list in the corresponding cache block record table is specifically:

Remove the old position pointer pointing to the migrated data page from the C-list-index or D-list-index list, and then determine the migration position. If the read buffer is moved into the read buffer, the position pointer is stored in the corresponding cache block C -list-index; otherwise, store the location pointer of the data page in D-list-index in the record block.

Further, in the step S6, the updating and eliminating the record block information corresponding to the data page is specifically:

Find the old position pointer pointing to the culled data page from the C-list-index or D-list-index list and cull it, and update BlkSize=BlkSize-1 of the corresponding record block.

Further, in the step S7, the position pointing to the data page is added to the position pointer list of the corresponding cache block record table, and the corresponding record block information is updated, specifically:

Determine the request type. If it is a read request, store the location pointer of the newly added data page into the C-list-index in the corresponding cache record block; otherwise, store the location pointer of the data page into the D-list-index in the record block. index, and then update the BlkSize=BlkSize+1 of the corresponding record block.

Further, in the step S6, the process of the adaptive cluster write-back is:

S61, select the data page at the LRU position of the write buffer as the culling object, and query the D-list-index information in the cache record block corresponding to the data page, and then execute S62;

S62, sequentially read the data pages pointed to by the position pointer of the D-list-index, and according to the principle that the first half of the cache queue is hot data, determine the data pages pointed to by the position pointer of the D-list-index, and Add the data pages judged to be hot to the reserved set Ф, and then execute S63;

S63, calculate the current write amplification factor

Calculate the current writeback threshold according to the current write amplification factor W

Among them, Bw is the statistical value of the number of write-backs in the cache area in a fixed period; Fw is the statistical value of the number of flash write operations in a fixed period; BlkMaxSize is the size of the logical data block, and t is a constant coefficient;

Then execute S64;

S64, calculate the number of filling pages E=BlkMaxSize-N, where N is the number of data pages of the current record block in the write buffer, then compare and compare the sizes of E and Th; if E≤Th, execute S65; otherwise, execute S66 ;

S65, enable page filling, read E filling pages from the underlying flash memory and write-back dirty pages to form an entire data block and write back to the underlying flash memory; then execute S67;

S66, do not enable page filling, write all the dirty pages in the D-list-index back into the underlying flash memory, and execute S67;

S67: Move all the data pages in the set Ф into the read buffer, delete the location information of the D-list-index in the cache block record table of the original data block, and store the transferred new location pointer in the C-list at the same time -index; finally end the cluster write-back operation.

Further, in the step S8, the threshold adjustment mechanism of the replacement strategy is activated to adjust the threshold Tau, and the specific adjustment process is as follows:

S81, determine whether the current request is a hit, if so, execute S82, otherwise, execute S83;

S82, judge the request type and the hit area, if the read buffer hits the read, then CRH increases by 1; if the read buffer hits the write, then the CWH increases by 1; if the write buffer hits the read, the DRH increases by 1; if the write buffer writes If it hits, then CRH is incremented by 1; finally, S83 is executed;

S83, update the current TCount, that is, TCount=TCount+1, and update the statistical value Bw and the statistical value Fw at the same time, and then execute S84;

S84, determine whether TCount reaches the threshold update cycle CycleTime, if so, execute S85, otherwise, end the current update operation of the threshold Tau;

Among them, CRH is the read hit statistics variable of the read buffer, CWH is the write hit statistics variable of the read buffer; DRH is the read hit statistics variable of the write buffer, DWH is the write hit statistics variable of the write buffer; TCount is the current request Operation count; CycleTime is the threshold update period;

S85, calculate the unity gain DR of the target write buffer and the unity gain CR of the target read buffer:

Where BufSize is the size of the total buffer for reading and writing, Tau' is the threshold before updating,

Cr and Cw are the normalized calculation to obtain the read and write delay cost coefficient:

Among them, ReadDelay and WriteDelay are the read delay and write delay in the cycle respectively; then execute S86.

S86, update the threshold Tau:

At the same time, the periodical buffer write-back count Bw=0, the period flash write-back count Fw=0, and the period count TCount=1 are updated, and the current update operation of the threshold Tau is finally ended.

Compared with the prior art, the present invention has the following beneficial effects:

The replacement and write-back adaptive buffer management method proposed by the present invention adopts a page-level management method when loading and culling data pages, and adjusts the read buffer threshold value adaptively through cycles, so as to be able to sense the change of load read and write characteristics, Therefore, the management method can obtain a higher cache hit rate under various load conditions. Secondly, the management method proposed in the present invention can sense the pressure of garbage collection at the FTL layer when the dirty page is clustered and write back, adjust the write-back strategy adaptively, and can effectively reduce the number of extra block erasures caused by FTL garbage collection. , to improve the overall performance and service life of the SSD.

Description of drawings

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

Fig. 1 is a schematic diagram of the cache block record table of the present invention.

Figure 2: Schematic diagram of the structure of the read-write buffer queue of the present invention.

Figure 3: The adaptive cluster write-back flow chart of the present invention.

Figure 4: The flow chart of the period threshold adjustment of the present invention.

Figure 5: General flow chart of request processing of the present invention.

Figure 6: An example process diagram of the present invention.

Detailed ways

In order to make those skilled in the art better understand the technical solutions of the present invention, the present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

In order to further describe the invention in detail, it is first necessary to provide the definitions of the related concepts of the present invention:

Cache data page: The basic read and write unit of the cache, which is consistent with the physical page size of the flash memory.

Cache data block: The physical block size is divided by the data request page address to obtain a set of data pages with consistent quotients. The maximum number of pages contained in the data block is consistent with the number of physical pages contained in the underlying physical block.

Logical page address: the logical address number (Logical Page Number, LPN) of the host I/O request P according to the identification of its file system.

Logical block number: It is also the number of the cache data block (Block Number, BlkNum). The BlkNum of the specified request P is the quotient obtained by dividing the LPN by the maximum number of pages of the data block.

The invention proposes a replacement and write-back adaptive buffer management method, which divides the cache into three parts: a cache block record table, a write buffer (Write Buffer) and a read buffer (Read Buffer).

The cache block record table is used to record the position and status of different data pages belonging to the same data block in the buffer. By recording the location pointers of different data pages, the cache block record table speeds up the query, update, and write-back operations of requesting data pages.

As shown in Figure 1, in the cache block record table, the information of the record block specifically includes: the current cache block number BlkNum, the number of data pages BlkSize that belong to the same record block in the current buffer, and the clean page position pointer that belongs to the same record block. List C-list-index, which also belongs to the dirty page location pointer list D-list-index of the record block. The size of the cache block is consistent with the size of the actual underlying physical block, that is, the number of data pages contained is the same, and its size is BlkMaxSize. The logical page address (LPN) of the corresponding data page is divided by BlkMaxSize, and the result obtained is recorded as the number of the cache block to which it belongs, and the corresponding remainder is the offset of the cache block.

The write buffer is used to cache the modified data pages (dirty pages) after responding to the write request. The data pages in the buffer are managed by forming a queue according to the LRU principle; at the same time, the data pages in the buffer are divided into hot and cold. The data pages are hot pages, and the data pages in the second half are cold pages.

The read buffer is used to cache only unmodified data pages (clean pages) in response to read requests, and the data pages of this buffer are also managed by LRU queues. The data pages in the buffer will be moved into the write buffer after responding to the write request, and the hot data pages in the write buffer will also be moved into the read buffer when the write-back occurs.

As shown in Figure 2, in the queue structure of the read and write buffers, the queue sizes of the two buffers will change due to the dynamic selection of the replacement object during the replacement process.

Periodic statistics are performed on the hits of the read and write buffers, the underlying read and write delays, the number of buffer writebacks, and the number of updates and writes of the underlying data pages.

The read hit statistical variable of the write buffer in the fixed observation period is recorded as DRH, and the write hit statistical variable of the write buffer is recorded as DWH; the read hit statistical variable of the read buffer is recorded as CRH, and the write hit statistical variable of the read buffer is recorded as DRH. It is recorded as CWH; the number of cache write-backs in this cycle is recorded as Bw, the number of flash write operations in this cycle is recorded as Fw; the write delay in this cycle is recorded as WriteDelay, and the read delay is recorded as ReadDelay.

The adaptive cluster writeback mechanism is triggered when the data page of the write buffer is selected as the replacement object and written back to flash.

As shown in Figure 3, in the adaptive cluster write-back mechanism, the write-back cache block is determined by the replacement data page, and the set of write-back dirty pages is determined with the help of the record information of the D-list-index in the cache block record, and the reserved pages are identified and reserved. Hot dirty pages. In the cluster write-back process, whether to use page filling is dynamically selected according to the current write amplification factor. Its operation process is as follows:

S61, select the data page V at the LRU position of the write buffer as the object to be eliminated, and query the D-list-index information in the cache record block corresponding to the data page, and then execute S62.

S62: Read the data pages pointed to by the location pointer of D-list-index in turn, and judge these data pages according to the principle that the first half of the cache queue is hot data, and add the data pages judged to be hot to the reserved set Ф , and then execute S63.

其中，

之后执行S64。S63, calculate the current write-back threshold

in,

After that, S64 is executed.

S64, calculate the number of filling pages E=BlkMaxSize-N, where N is the number of data pages of the current record block in the write buffer, then compare and compare the sizes of E and Th; if E≤Th, execute S65; otherwise, execute S66 .

S65, enable page filling, read E filling pages from the underlying flash memory and write back dirty pages to form an entire data block and write back to the underlying flash memory, and then execute S67.

S66, do not enable page filling, write back all the dirty pages in the D-list-index to the underlying flash memory, and execute S67.

S67: Move all the data pages in the set Ф into the read buffer, delete the location information of the D-list-index in the cache block record table of the original data block, and store the transferred new location pointer in the C-list at the same time -index, and finally end the cluster write-back operation.

In the management method proposed by the present invention, when replacing a data page, the replacement buffer object is selected by comparing the threshold value Tau (current target read buffer size) with the current read buffer size. The threshold Tau will be adjusted periodically based on the hits of the current read and write buffers and the underlying read and write delays. The threshold adjustment mechanism is shown in Figure 4. The process is as follows:

S81, determine whether the current request is a hit, if so, execute S82, otherwise, execute S83;

S82, judge the request type and the hit area, if the read buffer hits the read, then CRH increases by 1; if the read buffer hits the write, then the CWH increases by 1; if the write buffer hits the read, the DRH increases by 1; if the write buffer writes If it hits, then CRH is incremented by 1; finally, S83 is executed;

S83, update the current TCount, that is, TCount=TCount+1, update the statistical value Bw and the statistical value Fw at the same time, and then execute S84;

S84, determine whether TCount reaches the threshold update cycle CycleTime, if so, execute S85, otherwise, end this threshold update operation;

Among them, CRH is the read hit statistics variable of the read buffer, CWH is the write hit statistics variable of the read buffer; DRH is the read hit statistics variable of the write buffer, DWH is the write hit statistics variable of the write buffer; TCount is the current request Operation count; CycleTime is the threshold update period;

S85, calculate the unity gain DR of the target write buffer and the unity gain CR of the target read buffer:

Where BufSize is the size of the total buffer for reading and writing, Tau' is the threshold before updating,

Cr and Cw are the normalized calculation to obtain the read and write delay cost coefficient:

Among them, ReadDelay and WriteDelay are the read delay and write delay in the cycle respectively; then execute S86.

S86, update the threshold Tau:

At the same time, the periodical buffer write-back count Bw=0, the period flash write-back count Fw=0, and the period count TCount=1 are updated, and the current update operation of the threshold Tau is finally ended.

As shown in Figure 5, the general flow of request processing of the present invention includes the following steps:

S1, when a request P arrives, find the corresponding cache block number pBlkNum according to the LPN number conversion of the request P, query whether the cache block number exists in the cache block record table, if so, execute S2, otherwise, execute S4;

S2, traverse the location pointer in the cache block record entry, query whether the request P exists in the buffer, if so, execute S3, otherwise, execute S5;

S3, interpret the buffer position where the requested data page is located, move the hit data page to the MRU position of the corresponding buffer, update the position pointer list in the corresponding cache block record entry, and remove the old pointer to the data page, Store a new pointer to the location of the data page; then execute S8;

S4, add the number pBlkNum cache block entry information to the cache block record table, initialize BlkNum=pBlkNum, BlkSize=0 of the entry, D-list-index and C-list-index are empty, then execute S5;

S5, judge whether the current buffer is full, if it is full, execute S6, otherwise execute S7;

S6, compare the size of the current read buffer with the size of the threshold Tau, if it is greater than the size of the read buffer, select the data page at the LRU position of the read buffer to be eliminated; otherwise, select the data page at the LRU position of the write buffer as the replacement buffer, and Execute the adaptive cluster write-back mechanism; find the old position pointer pointing to the culled data page from the C-list-index or D-list-index list and cull it, and update the corresponding record block's BlkSize=BlkSize-1; then , execute S7;

S7, read the missing requested data page from the flash memory into the buffer, and at the same time interpret its request type; if it is a read request, load the data page into the read buffer, and store the pointer to the location of the data page into the cache at the same time In the C-list-index of the block record; otherwise, load the data page into the write buffer, and store the location pointer in the D-list-index of the corresponding cache block record; then update the cache record table BlkSize=BlkSize+1 , after that, execute S8;

S8 , start the period threshold Tau, perform period adjustment on the threshold value Tau, and finally, end the processing of this request.

In the step S3, updating the position pointer list in the corresponding cache block record table is specifically:

S31, interpret the buffer position where the requested data page is located, if it is a write buffer, execute S32; if it is a read buffer, execute S33;

S32, move the hit data page to the MRU position of the write buffer, update the D-list-index in the corresponding cache block record entry at the same time, remove the old pointer pointing to the data page, and replace the pointer pointing to the data page position The new pointer is stored in D-list-index; then execute S8;

S33, move the hit data page to the MRU position of the read buffer, update the corresponding C-list-index at the same time, remove the old pointer to the data page, and store the new position pointer into the C-list-index; Then execute S8.

In order to further illustrate the processing flow of the management method of the present invention, the description will be given in conjunction with a specific set of actual request processing examples, and the processing process of the example is shown in FIG. 6 .

In this example, the size of the data block is 4 data pages, the size of the buffer is 10 data pages, the read and write delay delay ratio is fixed at W/R=4/1, and the write amplification factor is constant at W=1.5, The threshold update cycle is 10, the current cycle count value TCount=1, and the initial value of the threshold Tau is 5.

In this example, the request sequence is shown in FIG. 6 and consists of the logical address of the request and the request type, for example (R, 20), which represents a read request to access the data page with LPN of 20.

In this example, the processing flow for the first request (R, 20):

C1, the cache block number pBlkNum=20/4=5 is obtained by conversion according to the LPN, and the cache block record table is queried whether the record information of the cache block number exists.

C2, there is no information about the cache block, load the record entry with pBlkNum=5 into the cache block record table, and update the block number BlkNum=5, BlkSize=0, C-list-index and D-list- index is empty.

C3, load the request page into the buffer, find that the buffer is full, compare the read buffer size RL(4) with the current threshold Tau(5), and select the write buffer LRU position LPN=13 as the replacement object.

取整为2，填补页为2，选择整块回写，且读缓冲区包含其余数据页，不需要额外的读取操作，直接整块回写即可。C4, the replacement page (LPN=13) belongs to the cache block VBlkNum=13/4=3, the dirty page LPN=14 belonging to the cache block is reserved for hot needs, the current write-back threshold

The rounding is 2, the padding page is 2, and the whole block is written back, and the read buffer contains the rest of the data pages. No additional read operations are required, and the whole block can be written back directly.

C5, empty the D-list-index in the VBlkNum=3 cache block, move the data page of LPN=14 into the tail of the read buffer queue, and store the location pointer to the data page in the C-list-index

C6, load the request into the buffer, determine that the request is a read type, load the data page with LPN=20 into the MRU position of the read buffer, and store the position pointer into C with pBlkNum=20/4=5 -list-index, while updating its BlkSize=1

C7, start the update of the cycle threshold Tau, because the request is not hit, the cycle count value TCount is accumulated to 2, and it is judged that TCount is less than the update cycle CycleTime, so the update adjustment is directly ended, and the operation of this request is ended.

In this example, the processing flow for the second request (W, 1):

C8, obtain the cache block number pBlkNum=1/4=0 according to the LPN conversion, and query whether there is record information of the cache block number in the cache block record table.

C9, traverse the cache block C-list-index and find that the data page with LPN=1 is located in the read buffer

C10, judging that the type of the request is a write request, move the data page from the read buffer to the MRU position of the write buffer, clear the position pointer of C-list-index, and store the new position pointer of the data page into In the D-list-index of the cache block record table

C11, start the cycle threshold Tau update, because it is a read buffer write hit, so the statistic value CWH is accumulated, and then the cycle count value TCount is accumulated to 3, and the end of the update cycle adjustment has not been reached, and the operation of this request is ended.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (8)

1. A replacement and write-back self-adaptive buffer management method,

the buffer area is divided into a buffer block record table, a write buffer area and a read buffer area;

the cache block record table is used for recording the position information of data pages belonging to the same logical data block in a buffer area, the write buffer area is used for caching the data pages which are modified in response to a write request, and the read buffer area is used for caching the data pages which are only in response to a read request and are not modified; it is characterized in that the preparation method is characterized in that,

the management method comprises the following steps:

s1, when the access request comes, inquiring whether the cache block record table contains the cache block information corresponding to the request, if yes, executing S2, otherwise, executing S4;

s2, inquiring whether a position pointer pointing to the requested data page exists in the cache block record table, if so, executing S3, otherwise, executing S5;

s3, migrating the hit data page to the MRU position of the corresponding buffer area, wherein the MRU refers to the nearest access end; updating a position pointer list in a corresponding cache block record table; then executing S8;

s4, adding corresponding record block information to the buffer block record table, initializing all information of the record block, and then executing S5;

s5, judging whether the current buffer area is full; if yes, executing S6, otherwise, executing S7;

s6, comparing the size of the read buffer with a target threshold Tau; if so, selecting the data page at the LRU position of the read buffer area to be removed, otherwise, selecting the data page at the LRU position of the write buffer area as a removal item and executing self-adaptive cluster write-back; updating record block information corresponding to the removed data page, and then executing S7;

s7, loading the missing request data page into the corresponding buffer area, adding the position pointer pointing to the data page into the position pointer list of the corresponding cache block record table, and updating the corresponding record block information; then executing S8;

s8, starting a replacement strategy threshold value adjusting mechanism to adjust the threshold value Tau; and finally, ending the processing of the request.

2. The method of permute and write back adaptive buffer management according to claim 1,

and the read buffer area and the write buffer area adopt LRU management queues, and when the buffer area hits requests and loads new data pages, the hit requests and the loaded new data pages are migrated to the MRU position of the queues.

3. The method of permute and write back adaptive buffer management according to claim 1,

in the cache block record table, the information of one record block includes: the number BlkNum of the cache block, the number BlkSize of data pages belonging to the same record block in the buffer area, a clean page position pointer list C-list-index belonging to the same record block and a dirty page position pointer list D-list-index belonging to the same record block.

4. The method of permute and write back adaptive buffer management according to claim 3,

in step S3, the step of updating the location pointer list in the corresponding cache block record table specifically includes:

removing an old position pointer pointing to the migration data page from the C-list-index or D-list-index list, then judging a migration position, and if the migration position is migrated into the read buffer area, storing the position pointer into the corresponding C-list-index in the cache block; otherwise, the position pointer of the data page is stored into the D-list-index in the record block.

5. The method of permute and write back adaptive buffer management according to claim 3,

in step S6, the updating and removing the recording block information corresponding to the data page specifically includes:

and finding an old position pointer pointing to the removed data page from the C-list-index or D-list-index list, removing the old position pointer, and updating the BlkSize of the corresponding recording block to be BlkSize-1.

6. The method of permute and write back adaptive buffer management according to claim 3,

in step S7, the adding the position pointing to the data page to the position pointer list of the corresponding cache block record table, and updating the corresponding record block information specifically includes:

judging the type of the request, and if the request is a read request, storing the position pointer of the newly added data page into the corresponding cache record block C-list-index; otherwise, the position pointer of the data page is stored in the D-list-index of the recording block, and then the BlkSize of the corresponding recording block is updated to be BlkSize + 1.

7. The method of permute and write back adaptive buffer management according to claim 1,

in step S6, the adaptive clustering write-back process includes:

s61, selecting the data page at the position of the write buffer LRU as a removal object, inquiring the D-list-index information in the cache record block corresponding to the data page, and then executing S62;

s62, sequentially reading data pages pointed by the position pointers of the D-list-index, judging the data pages pointed by the position pointers of the D-list-index according to the principle that the data pages positioned at the front half part of the cache queue are hot data, adding the data pages judged to be hot into the reserved set phi, and then executing S63;

s63, calculating the current write amplification factor

Calculating the current write back threshold according to the current write amplification factor W

Wherein Bw is a statistical value of write-back times of the cache region in a fixed period; fw is a flash memory write operation frequency counting value in a fixed period; BlkMaxSize is the logical data block size, t is a constant coefficient; then executing S64;

s64, calculating the filling page number E ═ BlkMaxSize-N, wherein N is the number of data pages of the current recording block in the writing buffer area, and then comparing the sizes of E and Th; if E is less than or equal to Th, executing S65; otherwise, go to S66;

s65, starting page filling, reading E filling pages from the bottom layer flash memory and writing back dirty pages to form a whole data block and writing back the whole data block into the bottom layer flash memory; then executing S67;

s66, not starting page filling, completely writing back the dirty pages in the D-list-index into the bottom layer flash memory, and executing S67;

s67, all data pages in the aggregate phi are moved to a read buffer area, the position information of the D-list-index in a cache block record table of an original data block is deleted, and a new position pointer after transfer is stored in the C-list-index; and finally ending the cluster write-back operation.

8. The method for replacement and write-back adaptive buffer management according to claim 7,

in step S8, the starting of the replacement policy threshold adjustment mechanism adjusts the threshold Tau, and the specific adjustment process is as follows:

s81, judging whether the current request is hit, if yes, executing S82, otherwise, executing S83;

s82, judging the request type and the hit area, if the read buffer area hits, adding 1 to CRH; if the read buffer write hits, then CWH adds 1; if the write buffer area is read hit, DRH adds 1; if the write buffer zone is hit, adding 1 to CRH; finally, executing S83;

s83, updating the current TCount, that is, TCount +1, and updating the statistical value Bw and the statistical value Fw, and then executing S84;

s84, judging whether TCount reaches the threshold updating cycle cycleTime, if so, executing S85, otherwise, ending the updating operation of the threshold Tau;

wherein, CRH is the read hit statistical variable of the read buffer, CWH is the write hit statistical variable of the read buffer; DRH is a read hit statistical variable of a write buffer area, and DWH is a write hit statistical variable of the write buffer area; TCount is the current request operation count; the CycleTime is a threshold updating period;

s85, calculating a target write buffer unity gain DR, a target read buffer unity gain CR:

wherein BufSize is the size of the total read-write buffer, Tau' is the threshold before updating,

cr and Cw are normalized to obtain a read-write delay cost coefficient:

wherein, ReadDelay and WriteDelay are read delay and write delay in a period respectively; then executing S86;

s86, update threshold Tau:

and simultaneously updating the write-back frequency statistic Bw of the period buffer area to be 0, the period flash memory write operation frequency statistic Fw to be 0, the period count value TCount to be 1, and finally ending the updating operation of the threshold Tau.

Images