Using hybrid-software/hardware based logical-to-physical address mapping to improve the data write throughput of solid-state data storage devices

A method for providing logical block address (LBA) to physical block address (PBA) binding in a storage device includes: receiving at least one thread at a hardware engine of the device controller of the storage device, each thread including data and LBAs for the data; writing the data into a write buffer of the storage device; binding, by the hardware engine of the device controller, a sequence of contiguous PBAs for a section of the memory to the LBAs for the data in the write buffer; determining if the write buffer contains enough data for the section of the memory; and if the write buffer contains enough data for the section of the memory, writing the data to the section of the memory.

TECHNICAL FIELD

The present disclosure relates to the field of solid-state data storage, and more particularly to improving the write throughput performance of solid-state data storage devices.

BACKGROUND

Solid-state data storage devices, which use non-volatile NAND flash memory technology, are being pervasively deployed in various computing and storage systems. In addition to including one or multiple NAND flash memory chips, each solid-state data storage device also contains a controller that manages all the NAND flash memory chips.

NAND flash memory cells are organized in an array→block→page hierarchy, where one NAND flash memory array is partitioned into a large number (e.g., thousands) of blocks, and each block contains a number (e.g., hundreds) of pages. Data are programmed and fetched in the unit of a page. The size of each flash memory page typically ranges from 8 kB to 32 kB, and the size of each flash memory block is typically tens of MBs. Flash memory cells must be erased before being re-programmed, and the erase operation is carried out in the unit of a block (i.e., all the pages within the same block must be erased at the same time). As a result, NAND flash memory cannot support the convenient inplace data update.

Because NAND flash memory lacks an update-in-place feature, solid-state data storage devices must use indirect address mapping. Internally, solid-state data storage devices manage data storage on NAND flash memory chips in the unit of a constant-size (e.g., 4 kB) physical sector. Each physical sector is assigned a unique physical block address (PBA). Instead of directly exposing the PBAs to external hosts, solid-state data storage devices expose an array of logical block addresses (LBA) and internally manage/maintain an injective mapping between LBA and PBA. The software component responsible for managing the LBA-PBA mapping is called the flash translation layer (FTL).

In conventional practice, LBA-PBA binding is handled solely by FTL software, and the controller hardware strictly follows the LBA-PBA bindings that are determined by the FTL software for all incoming write requests. Nevertheless, such a software-based LBA-PBA binding approach can make it very difficult to fully exploit the NAND flash memory write bandwidth, especially when storage devices use multiple threads to handle and process write requests.

SUMMARY

Accordingly, embodiments of the present disclosure are directed to methods for improving the performance and the write throughput performance of solid-state data storage devices.

A first aspect of the disclosure is directed to a method for providing logical block address (LBA) to physical block address (PBA) binding in a storage device, the method including: receiving at least one thread at a hardware engine of the device controller of the storage device, each thread including data and LBAs for the data; writing the data into a write buffer of the storage device; binding, by the hardware engine of the device controller, a sequence of contiguous PBAs for a section of the memory to the LBAs for the data in the write buffer; determining if the write buffer contains enough data for the section of the memory; and if the write buffer contains enough data for the section of the memory, writing the data to the section of the memory.

A second aspect of the disclosure is directed to a storage device, including: memory; a write buffer; and a device controller, the device controller including a hardware engine, wherein the hardware engine of the device controller is configured to: receive at least one thread, each thread including data and logical block addresses (LBAs) for the data; write the data into the write buffer of the storage device; bind a sequence of contiguous physical block addresses (PBAs) for a section of the memory to the LBAs for the data in the write buffer; determine if the write buffer contains enough data for the section of the memory; and if the write buffer contains enough data for the section of the memory, write the data to the section of the memory.

A third aspect of the disclosure is directed to a method for binding logical block addresses (LBAs) to physical block addresses (PBAs) in a storage device, including: receiving at least one thread at a device controller hardware engine of the storage device, each thread including data and LBAs for the data; writing the data into a write buffer of the storage device; binding, by the device controller hardware engine, a sequence of contiguous PBAs for a section of the memory to the LBAs for the data in the write buffer; determining if the write buffer contains enough data for the section of the memory; and if the write buffer contains enough data for the section of the memory, writing the data to the section of the memory.

The drawings are intended to depict only typical aspects of the disclosure, and therefore should not be considered as limiting the scope of the disclosure. In the drawings, like numbering represents like elements between the drawings.

DETAILED DESCRIPTION

Reference will now be made in detail to embodiments of the disclosure, examples of which are illustrated in the accompanying drawings.

In order to simplify flash memory management, modern solid-state data storage devices partition the entire NAND flash memory storage space into super-blocks10, and each super-block10contains multiple NAND flash memory blocks12, as illustrated inFIG. 1. All of the flash memory blocks12in each super-block10are erased at the same time. Each super-block10further contains a number of super-pages14, where each super-page14contains multiple flash memory pages16across all the flash memory blocks12inside one super-block10. Data are programmed into NAND flash memory chips in the unit of super-pages14. The size of each flash memory page16is typically 16 kB or 32 kB. Hence, if a super-block10contain s flash memory blocks12, each super-page14contains 16s kB or 32s kB.

Solid-state data storage devices must internally buffer and accumulate the content of one complete super-page14before writing the super-page14to flash memory. Solid-state data storage devices logically partition NAND flash memory storage space into size-n physical sectors, where n denotes the data I/O sector size (e.g., 512 B or 4 kB). Each physical sector is assigned a unique physical block address (PBA). As shown inFIG. 2, each super-page14contains a number of PBAs18, and the PBAs18within each super-page14are always contiguous, as illustrated inFIG. 2, where PBA1, PBA2, . . . , PBAm, PBAm+1, PBAm+2, . . . are contiguous PBAs18. In addition, because all of the pages16within each flash memory block12must be programmed sequentially with a fixed order, the PBAs18within each super-block10are also contiguous from one super-page14to the next super-page14.

Referring simultaneously toFIGS. 4 and 5(described with reference toFIGS. 1-3), when a solid-state data storage device100receives data write requests, it needs to bind the LBA20of each to-be-written data sector (also referred to herein as data) with one PBA18, which is called LBA-PBA binding. During runtime, the solid-state data storage device100always maintains a single PBA queue that contains contiguous PBAs18associated with one or multiple contiguous super-pages14. Meanwhile, assume the solid-state data storage device100employs t threads24to handle write requests from a host computing device, where each thread24maintains its own write request queue. To this extent, there are a total of t write request queues (i.e., t LBA queues22). Note that the values of the LBAs20in each LBA queue22are not necessarily contiguous.

To realize the LBA-PBA binding between the LBAs20from the t LBA queues22and the PBAs18from the single PBA queue, current practice employs a purely software-based solution, i.e., the LBA-PBA binding is determined solely by software (e.g., flash translation layer (FTL)) in the storage device controller28(hereafter referred to as controller28) of the solid-state data storage device100. For example, assume the solid-state data storage device100employs four threads24to handle write requests (i.e., t=4), hence there are four LBA queues22. Further assume that each super-page14contains sixteen PBAs18. In this case, four contiguous PBAs18are distributed to one LBA queue22, i.e., among the total of sixteen contiguous PBAs18in one super-page14, four contiguous PBAs18bind with four LBAs20from each LBA queue22.

As illustrated inFIGS. 4 and 5, after the software-based LBA-PBA binding is handled by software in the controller28of the solid-state data storage device100, the four threads24send the data30with the LBA-PBA binding information32to the device controller hardware34of the controller28that accumulates the data30in a write buffer36and physically writes the data30from the write buffer36to NAND flash memory38, one super-page14at a time. Meanwhile, the flash translation layer (FTL) software updates a global LBA-PBA mapping table.

Because all of the PBAs18in a super-page14are already fixed and are contiguous, the controller28of the solid-state data storage device100must accumulate the data30in its write buffer36based on the PBAs18assigned to the data30through a predetermined software-based LBA-PBA binding before subsequently writing the data30to the super-page14in flash memory38. As a result, as illustrated in the flow diagram inFIG. 5, from all the data30sent by any thread24(Y at process A1), the controller28can only accept the data30for which the corresponding PBAs18belong to the current super-page14that is next to-be-written (Y at process A2). At process A3, the accepted data30is written into the write buffer36by the controller28. If the write buffer36is filled with enough data30for one super-page14(Y at process A4), the data30is written to the super-page14in the flash memory38at process A5. Flow then moves to the next super-page14at process A6.

The above-described process is, however, subject to inter-thread speed variation. For example, if one thread24for some reason fails to send the data30and the LBA-PBA binding information32to the device controller hardware34of the controller28in time, then the device controller hardware34has no choice but to wait for that thread24in order to fill the write buffer36based on the PBAs18assigned to the data30. During the waiting time, the write bandwidth of the flash memory38is not utilized, leading to the under-utilization of the flash memory bandwidth and a reduction in write throughput.

To solve this problem and hence avoid flash memory write bandwidth underutilization in the case of inter-thread speed variation, and as illustrated inFIGS. 6 and 7(described with reference toFIGS. 1-3), the present disclosure provides a hybrid software/hardware based LBA-PBA binding solution. In sharp contrast to current practice, the LBA-PBA binding is finalized “on-the-fly” by a hardware engine40of a storage device controller42(hereafter referred to as controller42) of the solid-state data storage device100. Among all the t threads24that handle data write requests, each thread24maintains one LBA queue22, and sends (e.g., at the same time) a number of data sectors (data30) and their LBAs20to the underlying hardware engine40of the controller42.

As illustrated inFIG. 6, when sending the data30and their LBAs20to the hardware engine40of the controller42, each thread24does not yet know the LBA-PBA binding for each LBA20(i.e., the LBA-PBA binding has not yet occurred). Meanwhile, LBA-PBA mapping management software44(e.g., FTL software) of the controller42sends a PBA sequence46from a PBA queue48for the contiguous PBAs18of one super-page14to the hardware engine40. Upon receiving the data30and their LBAs20from all of the t threads24, the hardware engine40writes the data30into the write buffer36and binds the LBAs20of the data30with contiguous PBAs18in accordance with the PBA sequence46. Once the hardware engine40accumulates enough data30for one super-page14in the write buffer36, it immediately physically writes the data30to the super-page14in the flash memory38. Meanwhile, the hardware engine40sends the corresponding LBA-PBA binding information50to the LBA-PBA mapping management software44, which updates a global LBA-PBA mapping table52accordingly.

FIG. 7illustrates a flow diagram of the hybrid software/hardware based LBA-PBA binding solution according to embodiments. For any thread24sending data30(Y at process B1), the hardware engine40of the controller42receives the data30and corresponding LBAs20from the thread24and writes the data30into the write buffer36at process B2. At process B3, based on the contiguous PBAs18in the PBA sequence46for the super-page14, the hardware engine40binds the contiguous PBAs18to the LBAs20of the data30in the write buffer36. If the write buffer36is filled with enough data30for the super-page14(Y at process B4), the data30is written to the super-page14in the flash memory38at process B5. At process B6, the LBA-PBA binding information50for the super-page14is sent to the LBA-PBA mapping management software44, which updates a global LBA-PBA mapping table52accordingly. The process then moves to the next super-page14at process B7.

In the conventional method described above with reference toFIGS. 4 and 5, the hardware engine34must wait to accumulate data30in the write buffer36for a given super-page14based on a predetermined software-based LBA-PBA binding before subsequently writing the data30to that super-page14in flash memory38. This may result in a reduction in the data write throughput to the flash memory38.

In accordance with embodiments of the present disclosure, however, the hardware engine40receives data30and the LBAs20for the data30from one or more threads24, stores the data30in the write buffer36, and determines an LBA-PBA binding for the received data30“on-the-fly” based the contiguous PBAs18in the PBA sequence46for a super-page14. Once enough data30for the super-page14has been written to the write buffer36, the hardware engine40writes the data30to the super-page14in the flash memory38in accordance with the LBA-PBA binding.

It is understood that aspects of the present disclosure may be implemented in any manner, e.g., as a software program, or an integrated circuit board or a controller card that includes a processing core, I/O and processing logic. Aspects may be implemented in hardware or software, or a combination thereof. For example, aspects of the processing logic may be implemented using field programmable gate arrays (FPGAs), ASIC devices, or other hardware-oriented system.

The foregoing description of various aspects of the present disclosure has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the concepts disclosed herein to the precise form disclosed, and obviously, many modifications and variations are possible. Such modifications and variations that may be apparent to an individual in the art are included within the scope of the present disclosure as defined by the accompanying claims.