CN110515859A - A method for parallel processing of read and write requests for solid state disks - Google Patents

Abstract

The invention discloses a kind of solid state disk read-writes to request method for parallel processing.The present invention is made of address mapping module, channel distribution module, channel queue's module, Queue module to be processed, data buffer zone and six part of garbage reclamation module.In preprocessing process, for read-write requests, corresponding read/write channel is calculated, is subsequently sent to the corresponding read-write queue in channel；In flash memory access process, according to request order of arrival Parallel Scheduling from the read-write queue in each channel；For garbage reclamation, using active by the way of passively combining, to reduce influence of the garbage reclamation to solid state disk read-write performance.The present invention is using the channel level parallel organization inside solid state hard disk, as unit of page, is maximized parallel by rational management with realizing data write-in and reading, so that high degree reduces the average response time of request, lifting system overall performance.

Description

A method for parallel processing of read and write requests for solid state disks

technical field

The invention belongs to the field of firmware optimization design of solid-state hard disks, and in particular relates to a parallel processing method for reading and writing requests of solid-state hard disks.

Background technique

With the rapid development of new-generation information technologies such as cloud computing and mobile Internet, the amount of data shows an exponential growth trend, so higher requirements are placed on data storage speed and bandwidth. Solid-state hard drives based on NAND flash memory are known as one of the current mainstream storage devices due to their high performance, low power consumption, noise-free and many other advantages.

The NAND flash memory used in solid-state drives has the following characteristics: 1) It is composed of pages, blocks, planes, and dies, which are nested from small to large. 2) Basic operations are divided into: read, write, erase, read and write in units of pages, and erase in units of blocks. 3) The response times of the three operations of reading, writing, and erasing are different, and the reading is the fastest, followed by the writing, and the erasing is the slowest. 4) It must be erased before writing data, and in-place update is not supported. 5) The number of times of erasing is limited. If more than a certain number of times of erasing is exceeded, the overall performance of NAND flash memory will be greatly reduced, and the service life is limited.

Due to the unique operating characteristics of flash memory chips, solid state drives need to add a flash translation layer (FlashTranslation Layer, FTL) in firmware to manage a large number of flash memory chips. The flash conversion layer simulates the solid-state hard disk as a traditional hard disk with only read and write operations, and converts the read and write requests of the upper file system into the operation commands of the flash memory. Specifically, the flash translation layer needs to complete the mapping between logical addresses and physical addresses, control the wear leveling of each flash memory chip, and perform garbage collection on invalid data.

SSDs have rich internal parallel mechanisms. A general solid-state drive consists of multiple independent channels, and each independent channel connects multiple independent flash memory chips; each chip contains multiple wafers; each wafer contains multiple planes; each plane contains multiple blocks, each A block contains multiple pages. Therefore, the SSD internally includes channel-level parallelism, chip-level parallelism, wafer-level parallelism, and plane-level parallelism. In the process of request processing by the flash conversion layer, the internal parallel mechanism of the flash memory is used to allow read and write requests to access the flash memory in parallel, which will greatly reduce the request response time.

Contents of the invention

Aiming at the shortcomings of the above-mentioned prior art, the present invention discloses a method for parallel processing of read and write requests of solid state disks. The present invention utilizes the channel-level parallel structure inside the solid-state hard disk, takes pages as units, and realizes maximum parallelism of data writing and reading through reasonable scheduling, thereby greatly reducing the average response time of requests and improving the overall performance of the system.

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

A parallel processing method for reading and writing requests of a solid state disk, which is composed of six parts: an address mapping module, a channel allocation module, a channel queue module, a waiting queue module, a data buffer and a garbage collection module. The address mapping module is responsible for realizing the mapping from the requested logical address to the physical address. It adopts the page-level mapping method and is composed of the address mapping table and the page allocation module; the channel allocation module is responsible for calculating the channel that each page actually needs to access in the request; the channel queue module It consists of a queue for each channel. The queue for each channel is divided into a read request queue and a write request queue. Read and write access requests are inserted into the read and write queue of the channel in units of pages; For requests that have not been fully completed for reading and writing, the scheduling of the queue to be processed is completed in a first-in-first-out manner; the data buffer is used to temporarily store the data read from the flash memory; the garbage collection module is responsible for the recovery of invalid blocks of the solid-state hard disk, and completes garbage collection operate.

A method for parallel processing of read and write requests of a solid state disk, the processing flow includes three processes of preprocessing, flash memory access and garbage collection, and the three processes can be executed in parallel, and the specific steps are as follows.

When a new read and write request arrives and the queue to be processed is not full, the preprocessing process is triggered. The specific working process is as follows:

P1, determine the type of arrival request: if it is a read request, execute P2; otherwise, it is a write request, execute P4.

P2, calling the address mapping module, accessing the address mapping table, and obtaining the physical page number PPN corresponding to each logical page of the read request.

P3, call the channel allocation module, obtain the flash channel where it is located according to the PPN of each page, and then insert each page into the tail of the read queue corresponding to the flash channel, and execute P6.

P4, call the page allocation module of the address mapping module, adopt the off-site update strategy, allocate a new physical page number PPN for each page of the write request, and update the address mapping table, and execute P5.

P5, call the channel allocation module, obtain the flash channel where it is located according to the PPN of each page, then insert each page into the tail of the write queue corresponding to the flash channel, and finally execute P6.

P6, insert the request into the tail of the queue to be processed, and end this preprocessing.

When the queue to be processed is not empty, the flash memory access process is triggered, and the specific working process is as follows:

A1, determine the type of the queue head request to be processed: if it is a read request, execute A2; otherwise, execute A5.

A2. Determine whether the first read request of the request queue is completed: if yes, execute A4; otherwise, execute A3.

A3, read the page at the head of the read queue for all channels from the flash memory into the data buffer, then remove the head of the read queue for all channels, and execute A2.

A4. Merge the read data from the same request in the data buffer, and respond to the upper file system, remove the queue head request to be processed, and end this flash memory access operation.

A5. Determine whether the first write request in the request queue is completed: if yes, execute A7; otherwise, execute A6.

A6. Write the request for the head of the write queue of all channels into the physical page under the corresponding channel, and remove the head of the write queue of all channels at the same time, and execute A5.

A7. Respond to the upper file system, remove the queue head request to be processed, and end this flash memory access operation.

The garbage collection process is completed by the garbage collection module, which uses a combination of active garbage collection and passive garbage collection. When the queue to be processed is empty and the number of free blocks in a certain channel is less than the threshold TH ₁ , an active garbage collection operation is triggered. When performing a flash memory access operation, when the number of free blocks in a certain channel is less than the threshold TH ₂ , the flash memory access operation is suspended, and a passive garbage collection operation is triggered. Further, the specific method of the garbage collection operation is to select the data block containing the most invalid pages under the channel as the invalid block, migrate the valid pages in the invalid block to the free blocks in the same channel, and then remove the invalid pages erase. In addition, in order to trigger passive garbage collection operations as little as possible, TH ₁ should be greater than TH ₂ .

Further, the specific flow of the page allocation method for the write request in step P4 of the preprocessing flow is as follows:

P41, calculate the erasing times of each channel flash memory block, and sort according to the erasing times from small to large;

P42, the number of physical pages N required by the write request is expressed in the form of N=n*C+q (C is the number of channels, n is the quotient of N/C, and q is the remainder of N/C);

P43, according to the strategy of first assigning writes to the channel with the smallest number of erasures and maximizing channel parallel writing, first assign n page writes to each channel to maximize parallel writing; then assign q page writes to the number of erasures The smallest top q channels to equalize the wear of each channel.

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

The parallel processing method for reading and writing requests of the solid-state hard disk proposed by the present invention utilizes the channel-level parallel structure of the solid-state hard disk to maximize the parallelism of reading and writing requests. In the preprocessing process, for read and write requests, calculate the corresponding read and write channels, and then send them to the corresponding read and write queues of the channels; during the flash memory access process, they are scheduled in parallel from the read and write queues of each channel according to the order of request arrival; for Garbage collection adopts a combination of active and passive methods to reduce the impact of garbage collection on the read and write performance of SSDs. In addition, channel parallelism and wear leveling are taken into account during channel allocation of write requests. Compared with the existing flash memory conversion layer technology, the method disclosed by the invention can greatly reduce the request execution time and improve the read-write performance of the solid-state hard disk.

Description of drawings

Fig. 1: overall frame diagram of the present invention

Fig. 2: the pretreatment process flowchart of the present invention

Fig. 3: flash memory access process flowchart of the present invention

Fig. 4: the specific case of the pretreatment process of the present invention

Fig. 5: the specific case of the present invention's access flash memory process

Detailed ways

In order to enable those skilled in the art to better understand the technical solutions of the present invention, the present invention will be described in detail below in conjunction with the accompanying drawings and specific implementation methods. Apparently, the described embodiments are only some of the embodiments of the present invention, but not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

In addition, the present invention assumes that the minimum unit for the upper file system to read and write to the solid-state hard disk is a flash memory page, that is, the entire page is read or written. In an actual system, the minimum unit for the file system to read and write to the SSD is 1 sector. Through the alignment operation, sector access can be easily converted into page access, which will not be repeated in this invention.

The method for parallel processing of read and write requests for solid-state hard drives proposed by the present invention consists of six parts: an address mapping module, a channel allocation module, a channel queue module, a waiting queue module, a data buffer and a garbage collection module, as shown in FIG. 1 .

The address mapping module is responsible for realizing the mapping from the requested logical address to the physical address, adopts the page-level mapping method, and is composed of an address mapping table and a page allocation module. The address mapping table records the mapping relationship between the logical page and the physical page, and the page allocation module allocates a new physical page to the write request. When a read request comes, the physical page corresponding to the logical page is obtained through the address mapping table of the address mapping module; when a write request comes, a new physical page is allocated to each logical page in the write request through the page allocation module of the address mapping module, and updated Address mapping table.

The channel allocation module is responsible for calculating the channel that each page in the request actually needs to access. The channel allocation module calculates the channel corresponding to each page according to the physical page number obtained by the address mapping module, and inserts it into the read-write queue of the corresponding channel.

The channel queue module is composed of a queue for each channel, and the queue for each channel is divided into a read request queue and a write request queue. The channel allocation module inserts read and write access requests into the read and write queue of the channel in units of pages.

The pending queue saves requests for which the channel allocation is completed but the actual flash memory read and write is not completed, and the scheduling of the pending queue is completed in a first-in first-out manner.

The data buffer is used to temporarily store the data read from the flash memory.

The garbage collection module is used to complete the garbage collection process, using a combination of active garbage collection and passive garbage collection.

The method for parallel processing of read and write requests for solid-state hard drives proposed by the present invention involves three processes of preprocessing, flash memory access and garbage collection when actually processing access requests. The trigger conditions and processing flow of these three processes are as follows:

When a new read and write request arrives and the queue to be processed is not full, the preprocessing process is triggered. The process is shown in Figure 2. The specific working process is as follows:

Step 1. Determine the type of the incoming request: if it is a read request, go to step 2; otherwise, go to step 4.

Step 2, call the address mapping module, access the address mapping table, and obtain the physical page number PPN corresponding to each logical page of the read request.

Step 3, call the channel allocation module, obtain the corresponding flash memory channel according to the PPN of each page, then insert each page into the tail of the read queue of the corresponding flash memory channel, and finally perform step 6.

Step 4, calling the page allocation module of the address mapping module, adopting an off-site update strategy, assigning a new physical page number PPN to each page of the write request, updating the address mapping table, and performing step 5.

Step 5, call the channel allocation module, obtain the corresponding flash memory channel according to the PPN of each page, then insert each page into the tail of the write queue corresponding to the flash memory channel, and finally perform step 6.

Step 6, insert the request into the tail of the queue to be processed, and end this preprocessing.

Further, the specific flow of the page allocation method for the write request in step 4 is as follows:

P41, calculate the erasing times of each channel flash memory block, and sort according to the erasing times from small to large;

P42, the number of physical pages N required by the write request is expressed in the form of N=n*C+q (C is the number of channels, n is the quotient of N/C, and q is the remainder of N/C);

P43, according to the strategy of first assigning writes to the channel with the smallest number of erasures and maximizing channel parallel writing, first assign n page writes to each channel to maximize parallel writing; then assign q page writes to the number of erasures The smallest top q channels to equalize the wear of each channel.

When the queue to be processed is not empty, the flash memory access process is triggered, and its implementation process is shown in Figure 3. The specific working process is as follows:

Step 1. Determine the type of the pending queue head request: if it is a read request, go to step 2; otherwise, go to step 5.

Step 2, judge whether the execution of the first read request of the request queue is completed: if yes, execute step 4, otherwise execute step 3.

Step 3: Read the pages at the head of the read queues of all channels from the flash memory into the data buffer, and then remove the heads of the read queues of all channels, and perform step 2.

Step 4, merge the read data from the same request in the data buffer, and respond to the upper file system, remove the request from the head of the queue to be processed, and end this flash memory access operation.

Step 5, judging whether the first write request of the request queue is completed: if yes, go to step 7, otherwise go to step 6.

Step 6: Write the request for the head of the write queue of all channels into the physical page under the corresponding channel, and delete the head of the write queue of all channels at the same time, and perform step 5.

Step 7: Respond to the upper file system, remove the queue head request to be processed, and end this flash memory access operation.

When the queue to be processed is empty and the number of free blocks in a certain channel is less than the threshold TH ₁ , an active garbage collection operation is triggered. When a flash memory access operation is being performed and the number of free blocks in a certain channel is less than the threshold TH ₂ , the flash memory access operation is suspended and a passive garbage collection operation is triggered. The actual garbage collection operation is to select the data block containing the most invalid pages under the channel as an invalid block, migrate the valid pages in the invalid block to free blocks in the same channel, and then erase the invalid block. In addition, in order to trigger passive garbage collection operations as little as possible, TH ₁ should be greater than TH ₂ .

In order to further explain the parallel processing flow of the present invention, it will be described in conjunction with specific actual requests. For the convenience of description, assume that the number of flash memory channels C=4, and the flash memory array of each channel contains 128 physical pages, that is, physical pages 1-128 correspond to channel 1, physical pages 129-256 correspond to channel 2, and physical pages 257-384 Pages correspond to channel 3, and physical pages 385-512 correspond to channel 4. Both the request queue and the channel read/write queue are empty, and the channels are arranged as 4, 3, 2, 1 according to the erasing times of flash memory blocks from small to large.

Embodiment 1: pretreatment operation.

The preprocessing operations in the queue are shown in Figure 4. Requests R1, W1, and R2 arrive in chronological order, where R represents a read request, W represents a write request, and the numbers represent the order of arrival. Its processing is as follows:

C1, the queue to be processed is not full, and the request preprocessing operation is started, and the read request R1(78,2) is started. Here 78 represents the start logical page number of the access operation, and 2 represents access to two pages (the same below). According to the address mapping table shown in Figure 4, it can be obtained that the actual physical page numbers to be accessed are 66 and 301, and C2 is executed.

C2, physical pages 66 and 301 are in channels 1 and 3 respectively. The channel allocation module inserts them into the read queues of channel 1 and channel 3 respectively, and executes C3.

C3, the queue to be processed is not full, continue to execute the request preprocessing operation, and write the request W1(236,5). The address mapping module allocates the first 4 pages in W1 to 4 channels, and allocates the fifth page to channel 4. Suppose the distribution information is 236-103, 237-247, 238-331, 239-500, 240-501. Update the mapping information to the address mapping module, and execute C4.

C4, physical pages 103, 247, 331, 500, and 501 are in channels 1, 2, 3, 4, and 4 respectively. The channel allocation module inserts them into the write queues of channel 1, channel 2, channel 3 and channel 4 respectively, and executes C5.

C5, the queue to be processed is not full, continue to execute the request preprocessing operation, and read the request R2(126,3). Access the address mapping module to obtain the address mapping information as 126-79, 127-210, 128-407, and execute C6.

C6, physical pages 79, 210, and 407 are in channels 1, 2, and 4, respectively. The channel allocation module inserts them into the read queues of channel 1, channel 2 and channel 4 respectively, and executes C7.

C7, the queue to be processed is not full, but there is no subsequent request, and the execution of the preprocessing operation ends.

Embodiment 2: flash memory access operation.

The processing of read requests in the queue is shown in Figure 5, and the processing process is as follows:

C1, the queue to be processed is not empty, the leader of the queue is the read request R1, and R1 has not been executed, so read the first page number of the read queue of the four channels, that is, read the physical pages 66, 210, and 301 from the four channels respectively , 407 to the data buffer. Remove the head requests of the 4 channel read queues. At this time, the execution of R1 is completed, and R1 is removed from the pending queue. The physical pages 66 and 301 of R1 in the buffer are merged and uploaded, and C2 is executed.

C2, the queue to be processed is not empty, the head of the queue is the read request W1, and W1 has not been executed, so write to the head of the 4-channel write queue, and write data to 103,247,331,500 physical pages under the 4 channels. Remove the head requests of the 4 channel write queues and execute C3.

C3, the queue to be processed is not empty, the leader is the read request W1, and W1 has not been executed, so write to the leader of the write queue of 4 channels, only the write queue of channel 4 is not empty, write the data to channel 4 The 501 physical page. Remove the leader of the channel 4 write queue, and at this time W1 is executed, remove W1 from the queue to be processed, and execute C4.

C4, the queue to be processed is not empty, the head of the queue is the read request R2, and R2 has not been executed, so the read queue head of 4 channels is read, only the read queue of channel 1 is not empty, and the physical page is read from channel 1 79. Remove the head of the channel 1 read queue, and at this time, the execution of R2 ends, remove R2 from the pending queue, merge and upload the physical pages 79, 210, and 407 in the buffer, and execute C5.

C5, the queue to be processed is empty, and the execution ends.

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 modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (6)

1. A solid-state disk read and write request parallel processing device is characterized in that it comprises an address mapping module, a channel distribution module, a channel queue module, a pending queue module, a data buffer and a garbage collection module; the address mapping module is responsible for realizing the logic of the request The mapping from address to physical address adopts the page-level mapping method, which is composed of address mapping table and page allocation module; the channel allocation module is responsible for calculating the channel that each page actually needs to access in the request; the channel queue module is composed of the queue of each channel, The queue of each channel is divided into a read request queue and a write request queue. Read and write access requests are inserted into the read and write queue of the channel in units of pages; the pending queue stores the requests that the channel allocation is completed but the actual flash memory reads and writes are not fully completed. Complete the scheduling of the queue to be processed according to the first-in-first-out method; the data buffer is used to temporarily store the data read from the flash memory; the garbage collection module is responsible for the recovery of invalid blocks of the solid-state hard disk, and completes the garbage collection operation. 2. A method for parallel processing of solid state disk read and write requests, characterized in that it comprises three processes of preprocessing, flash memory access and garbage collection, and the three processes can be performed in parallel, and its concrete steps are as follows: When a new read and write request arrives and the pending queue is not full, the preprocessing process is triggered; When the pending queue is not empty, trigger the flash memory access process; The garbage collection process is completed by the garbage collection module, which adopts the combination of active garbage collection and passive garbage collection; when the queue to be processed is empty and the number of free blocks in a certain channel is less than the threshold TH ₁ , the active garbage collection operation is triggered; When performing a flash memory access operation, when the number of free blocks in a certain channel is less than the threshold TH ₂ , the flash memory access operation is suspended and a passive garbage collection operation is triggered; further, the specific method of the garbage collection operation is to select the channel under the channel The data block containing the most invalid pages is used as an invalid block, and the valid pages in the invalid block are migrated to free blocks in the same channel, and then the invalid block is erased; in addition, in order to trigger passive garbage collection operations as little as possible, TH ₁ should greater than TH ₂ . 3. a kind of solid-state hard disk read and write request parallel processing method according to claim 2, it is characterized in that the preprocessing flow realization step is as follows: P1. Determine the type of arrival request: if it is a read request, execute P2; otherwise, it is a write request, execute P4; P2. call the address mapping module, access the address mapping table, and obtain the physical page number PPN corresponding to each logical page of the read request; P3. Call the channel allocation module, obtain the flash memory channel where it is located according to the PPN of each page, then insert each page into the tail of the read queue of the corresponding flash memory channel, and execute P6; P4. Call the page allocation module of the address mapping module, adopt the off-site update strategy, allocate a new physical page number PPN for each page of the write request, and update the address mapping table, and execute P5; P5. Call the channel allocation module, obtain the flash memory channel where it is located according to the PPN of each page, then insert each page into the tail of the write queue of the corresponding flash memory channel, and finally execute P6; P6. Insert the request to the end of the queue to be processed, and end this preprocessing. 4. a kind of solid-state hard disk read and write request parallel processing method according to claim 3 is characterized in that flash memory access process realization steps are as follows: A1. Determine the type of the queue head request to be processed: if it is a read request, execute A2; otherwise, execute A5; A2. Determine whether the execution of the first read request of the request queue is completed: if yes, execute A4, otherwise execute A3; A3. Read the pages at the head of all channel read queues from the flash memory into the data buffer, then remove the heads of all channel read queues, and execute A2; A4. Merge the read data from the same request in the data buffer, and respond to the upper file system, remove the queue head request to be processed, and end this flash memory access operation; A5. Determine whether the first write request of the request queue is completed: if yes, execute A7, otherwise execute A6; A6. Write the request for the head of the write queue of all channels into the physical page under the corresponding channel, and remove the head of the write queue of all channels at the same time, and execute A5; A7. Respond to the upper file system, remove the request from the head of the queue to be processed, and end this flash memory access operation. 5. a kind of solid state disk read and write request parallel processing method according to claim 4, it is characterized in that the concrete process of the page allocation method of the write request in the preprocessing flow P4 step is as follows: P41. Calculate the erasing times of each channel flash memory block, and sort according to the erasing times from small to large; P42. Express the number of physical pages N required by the write request in the form of N=n*C+q, where C is the number of channels, n is the quotient of N/C, and q is the remainder of N/C; P43. According to the strategy of first assigning writes to channels with the smallest number of erasures and maximizing channel parallel writing, first assign n page writes to each channel to maximize parallel writes; then assign q page writes to the number of erasures The smallest top q channels to equalize the wear of each channel. 6. according to claim 3 or 4 or 5 described a kind of solid-state disk read and write request parallel processing method, it is characterized in that the method relates to address mapping module, channel distribution module, channel queue module, pending queue module, data buffer and garbage collection module; the address mapping module is responsible for realizing the mapping from the requested logical address to the physical address, adopting the page-level mapping method, composed of the address mapping table and the page allocation module; Channel; the channel queue module is composed of a queue for each channel. The queue for each channel is divided into a read request queue and a write request queue. Read and write access requests are inserted into the read and write queue of the channel in units of pages; the pending queue saves channel allocation Completed, but the actual read and write of the flash memory is not all completed, the scheduling of the queue to be processed is completed according to the first-in-first-out method; the data buffer is used to temporarily store the data read from the flash memory; the garbage collection module is responsible for the invalid blocks of the solid state drive Recycle, to complete the garbage collection operation.