Methods, systems, and computer readable media for write classification and aggregation using host memory buffer (HMB)

A method for write aggregation using a host memory buffer includes fetching write commands and data specified by the write commands from a host over a bus to a non-volatile memory system coupled to the host. Writing the data specified by the write commands from the non-volatile memory system over the bus to the host. The method further includes aggregating the data specified by the write commands in a host memory buffer maintained in memory of the host. The method further includes determining whether the data in the host memory buffer has aggregated to a threshold amount. The method further includes, in response to determining that the data has aggregated to the threshold amount, reading the data from the host memory buffer to the non-volatile memory system and writing the data to non-volatile memory in the non-volatile memory system.

TECHNICAL FIELD

The subject matter described herein relates to aggregating data for write commands written by a host to a non-volatile storage device. More particularly, the subject matter described herein includes method, systems, and computer readable media for write classification and aggregation using a host memory buffer.

BACKGROUND

When writing data to non-volatile storage devices, the smallest unit of data that can be written by the host is governed by logical block addressing and is typically 512 bytes or 4 kilobytes. In contrast, the smallest unit of data that can be written to flash memory governed by a page size and is typically 16 kilobytes or 32 kilobytes. Thus, if a host device writes 4 kilobytes of data to a non-volatile storage device with flash memory with a 32 kilobyte page size, there is a 28 kilobyte difference in minimum write granularity.

One mechanism for dealing with the difference in minimum write granularity is to pad writes from the host that are smaller than the minimum flash write granularity with padding (typically zeros) and write the data and the padding to the flash memory. Performing such padding is undesirable as it wastes storage space in the flash memory and also increases wear on flash memory cells.

In light of the disadvantages associated with padding each write, aggregation of data to be written to flash memory has been performed using dynamic random access memory (DRAM) on the storage device, which is sometimes referred to as coupled DRAM. In such a scenario, when a host device writes data to the non-volatile storage device, and the amount of data from individual write commands is less than the page size of the flash memory, data from multiple write commands is aggregated in DRAM on the non-volatile storage device until a page size of data is received. When a page size of data is aggregated, the data is transferred from the DRAM on the non-volatile storage device to the flash memory. One problem with this implementation is that it requires additional DRAM on the non-volatile storage device. If such DRAM is a limited resource or is not available, such aggregation on the non-volatile storage device cannot be performed.

DETAILED DESCRIPTION

The subject matter described herein includes method, systems, and computer media for write classification and aggregation using the host memory buffer. The host memory buffer allows the controller of a storage device to use a designated portion of host memory for storing storage device data. The designated memory resources allocated on the host are for the exclusive use of the storage device controller. Host software should not modify ranges of addresses allocated for the host memory buffer without first requesting that the storage device controller release the ranges. The storage device controller is responsible for initializing the host memory resources for the host memory buffer. According to the NVMe specification (see, e.g., NVM Express, Revision 1.2.1, Jun. 5, 2016, the disclosure of which is incorporated herein by reference in its entirety), the host memory buffer has the following features:1. Allocated for the controller's exclusive use.2. Data is guaranteed to be valid.3. The host is obliged to notify the controller before any operation (e.g. in case of power loss or in the case the host might need this buffer, etc.) which might lead to data loss. In such cases, the host must permit the controller to acknowledge the operation before the data is lost.

As stated above, host read and write commands, such as NVMe read and write commands, work in the granularity of logical block address (LBA) size. On the other hand, write granularity to a flash memory device is defined as a page size or multipage size in the case of multi-plane memory configurations. In most cases, write granularity to the flash memory is not equal to the LBA size and is greater than the LBA size. For example, write granularity to the flash may be 32 kilobytes while the LBA size is 512 bytes.

In terms of flash efficiency and endurance, it is better to aggregate the data that comes from different write commands before writing the data to the flash rather than writing a small chunk of data with padding after each write command. For example, if the host sends eight random write commands each of size 4 kilobytes and the flash page size is 32 kilobytes, the table shown below illustrates two flows that might be implemented for this sequence of eight write commands:

TABLE 1Example Write Command Implementations With and WithoutPaddingWrite #1Write #2Write #3Write #4Write #5Write #6Write #7Write #8WithWrite dataWrite dataWrite dataWrite dataWrite dataWrite dataWrite dataWrite dataPaddingwithwithwithwithwithwithwithwithpadding topadding topadding topadding topadding topadding topadding topadding toflashflashflashflashflashflashflashflashWithoutAggregateAggregateAggregateAggregateAggregateAggregateAggregateWritePaddingDataDataDataDataDataDataDataaggregateddata toflash
In Table 1 above, the first row below the table header shows the addition of padding to each write command to make up for the difference between the LBA size of 4 kilobytes and the flash page size of 32 kilobytes. In such an implementation, the padding would be 28 kilobytes per write command, which is inefficient. In the second row of Table 1, random write commands may be aggregated until a sufficient amount of data is received to perform a write to the flash. In this example, eight write commands of 4 kilobytes each are received before a page size of 32 kilobytes is received, and a single write to the flash is performed after the eighth write command.

The implementation in the second row of Table 1 is better in terms of flash efficiency and endurance but it requires memory (conventionally DRAM on the non-volatile storage device) for aggregating user data. The extra memory is required to cache the data for a write command when posting a completion message to the host after each host write command and before the writing of the data to the flash. If the device posts the completion commands to the host after the writing to the flash, this will result in additional latency perceived by the host.

According to the subject matter described herein, the host memory buffer on the host side of the peripheral component interconnect express (PCIe) bus is used to aggregate data from host write commands until a threshold amount of data, such as one or more pages of data, is aggregated in the host memory buffer. When the threshold amount of data is reached, the aggregated data is written from the host memory buffer to the flash memory. Completion commands may be posted by the device controller in host completion queues after storing the data for each write command in the host memory buffer. Posting the completion commands in the host completion queues after writing the data to the host memory buffer but before writing the data to the flash memory results in less perceived latency from the host point of view. However, if a read command is received from the host for data that is stored in the host memory buffer but not yet stored in the flash memory, this is referred to herein as a collision. The subject matter described herein may deal with such a collision by satisfying the read command with data directly from the host memory buffer, as will be described in more detail below.

FIGS. 1A through 1Cillustrate exemplary operating environments for write caching using a host memory buffer according to an embodiment of the subject matter described herein.

FIG. 1Ais a block diagram illustrating a non-volatile memory system100. The non-volatile memory system100may include a controller102and non-volatile memory that may be made up of one or more non-volatile memory dies104. As used herein, the term die refers to the set of non-volatile memory cells, and associated circuitry for managing the physical operation of those non-volatile memory cells, that are formed on a single semiconductor substrate. The controller102may interface with a host system and transmit command sequences for read, program, and erase operations to the non-volatile memory die(s)104.

The interface between the controller102and the non-volatile memory die(s)104may be any suitable flash interface, such as Toggle Mode200,400, or800. In one embodiment, the memory system100may be a card based system, such as a secure digital (SD) or a micro secure digital (micro-SD) card. In an alternate embodiment, the system100may be part of an embedded memory system.

Although in the example illustrated inFIG. 1A, the non-volatile memory system100may include a single channel between the controller102and the non-volatile memory die(s)104, the subject matter described herein is not limited to having a single memory channel. For example, in some NAND memory system architectures, 2, 4, 8 or more NAND channels may exist between the controller and the NAND memory die(s)104, depending on controller capabilities. In any of the embodiments described herein, more than a single channel may exist between the controller and the memory die(s)104, even if a single channel is shown in the drawings.

InFIG. 1B, a storage module200includes a storage controller202that communicates with a storage system204having a plurality of storage devices100. The interface between the storage controller202and the non-volatile memory system100may be a bus interface, such as a serial advanced technology attachment (SATA) interface, a peripheral component interface (PCIe) interface, an embedded MultiMediaCard (eMMC) interface, a SD interface, or a Universal Serial Bus (USB), as examples. In such a system, storage controller202may allocate different portions of a host memory buffer for each storage device100, and each storage device100may perform write caching using the host memory buffer as described herein. The storage module200, in one embodiment, may be a solid state drive (SSD), such as found in portable computing devices, such as laptop computers and tablet computers and mobile phones.

FIG. 1Cillustrates a hierarchical storage system250that provides memory storage services for a plurality of host systems252. Hierarchical storage system250includes plural storage controllers202that control access to storage systems204. In such a system, write caching using a host memory buffer may be implemented by each storage controller202and the host or hosts with which he storage controller202interacts. Host systems252may access memories within the hierarchical storage system250via a bus interface. Example bus interfaces may include a non-volatile memory express (NVMe) interface, a Fiber Channel over Ethernet (FCoE) interface, an SD interface, a USB interface, a SATA interface, a PCIe interface, or an eMMC interface as examples. In one embodiment, the storage system250illustrated inFIG. 1Cmay be a rack mountable mass storage system that is accessible by multiple host computers, such as would be found in the data center or other locations where mass storage is needed.

FIG. 2is a block diagram illustrating exemplary components of a non-volatile memory storage system100that implements write caching using a host memory buffer according to an embodiment of the subject matter described herein. Referring toFIG. 2, controller102includes a front end module108and a back end module110. Front end module108includes components that interface with a host300. In the illustrated example, these components include a command fetcher and parser112, a write classifier114, a coherency table116, and a direct memory access (DMA) controller118. Command fetcher and parser112fetches commands, such as read and write commands, from host300. Write classifier114classifies host write operations as random, sequential, or other suitable classifications. Coherency table116maintains listing of logical block addresses for data that is stored in host memory buffer302. DMA controller118allows the caching of data for host write operations in host memory buffer302without impacting back end module110.

In the illustrated example, non-volatile memory system100is connected to host300via a bus122. Bus122may be any suitable bus that allows controller102to reserve and utilize a portion of host memory301for caching write operations. In one example, bus122may be a PCIe bus, and the protocol that allows controller102to cache data from write operations in host memory buffer302is the non-volatile memory express protocol. However, the subject matter described herein is not limited to the non-volatile memory express protocol. Any protocol that allows a memory or storage controller to be a bus master and cache data over the bus to the host memory is intended the within the scope of the subject matter described herein.

Back end module110includes error correction controller (ECC)124that corrects errors in data written to the non-volatile memory104. Back end module110further includes a sequencer126but sequences read and write operations to non-volatile memory104. Back end module110further includes a redundant array of inexpensive disks (RAID) interface128that allows non-volatile memory104to operate as a RAID system. Back end module110further includes a memory interface130that interfaces with non-volatile memory104. Back end module110further includes a flash controller132that performs flash control and maintenance operations, such as garbage collection and wear leveling.

Controller102further includes buffer management and bus controller160that controls communications over internal bus162between front end module108and back end module110. Controller102further includes a media management layer170that performs media management operations. In addition to communicating with non-volatile memory104, controller102may also communicate with other discrete components180, which may include other controllers and/or non-volatile memory systems.

In the illustrated example, host device300includes host memory301in which host memory buffer302is implemented. Host300also includes one or more microprocessors306that control the overall operation of host device300. Host device300may be any computing platform that includes one or more processors and memory subsystems and that communicates with a non-volatile memory system100. For example, host device300may be a carrier grade or retail grade computing device that interfaces with a flash based storage system and operates as a self-contained or network accessible computing environment. Host device300may be any of a mobile device, a personal computer, a server, a cloud computer, a large/hyper scale storage appliance, or any combination thereof.

Non-volatile memory system100may be a flash memory based storage system that is either removable or imbedded within host device300. For example, non-volatile memory system100may be implemented in any of the example systems illustrated inFIGS. 1A-1C.

In operation, DMA controller118may receive data from buffers in host memory301and write the data to host memory buffer302without impacting back end module110. Command fetcher and parser112may fetch commands from host300over bus122and parse the commands to identify the command types (e.g. read or write). Write classifier114classifies write commands as sequential, random, or long. Coherency table116is used for tracking LBA ranges for data that is aggregated in HMB302to avoid coherency issues. For example, coherency table116may maintain coherency data, such as LBA ranges for data stored in HMB302.

Because there may be more than one type of write operation that may be classified by write classifier114, controller102may implement different aggregation queues for aggregating data for the different write classes. For example, device controller102may implement a random write buffer for aggregating data for random write operations, a sequential write buffer for aggregating data for sequential write operations, and a long write buffer for aggregating data for long write operations. It is better not to mix data from different write command types in order to simplify subsequent read operations that may occur. Each aggregation queue may be used for data accumulation until a threshold, such as a full flash page, is accumulated and then a single write operation may be performed to write the data from host memory buffer302to non-volatile memory104.

When obtaining write commands from host300, the following steps may be performed by controller102:

1. Controller102may fetch the write command and then parse the write command. The fetching and parsing may be performed by command fetcher and parser112. Read and write commands are stored in work queues, referred to as submission queues, in host memory301. Fetching a command involves reading the command from a host submission queue over bus122. Parsing the commands includes reading the command opcode to identify the command type and reading the LBA ranges in the command to identify the address ranges of data specified by the command.

2. Controller102may classify the write command based on one or more parameters, such as command size and command stream. This step may be performed by write classifier114.

3. After classifying the write command, controller102may write the data from the write command to one of the aggregation queues in HMB302. This may be performed by reading the data from host memory301across bus112to non-volatile memory system100and then writing the data back to host memory buffer302. This process may be repeated until all the data in the write command has been stored in host memory buffer302.

4. After writing the command data to the host memory buffer controller102may post a completion entry in the completion queue in host memory301. The completion entry may be posted even though the data is not physically stored in non-volatile memory system100. This step may be implemented when the host allows this feature using the force unit access (FUA) bit within the write command.

In parallel with the writing of data from a write command into host memory buffer302, controller102may calculate the amount of data in each accumulation queue stored in host memory buffer302. When the size of one of the aggregation queues crosses a flash page size, the data is read from the aggregation queue and written to non-volatile memory104.

FIG. 3illustrates the flow of data associated with accumulation of write commands and writing to flash memory. Referring toFIG. 3, in step1, controller102retrieves a write command from host300and reads the corresponding data across bus122to DMA controller118. DMA controller118, in step 2, writes the data to the appropriate aggregation queue. In step3, when the aggregation queue contains enough data to satisfy a flash page size, controller102fetches the data from the aggregation queue in HMB302and writes the data to non-volatile memory104.

As stated above, when data is written to host memory buffer302, controller102updates coherency table116to indicate the LBA ranges that are maintained the host memory buffer302. In addition, when data is written from HMB302to non-volatile memory104, controller102removes the corresponding LBA ranges from coherency table116.

One difference between write aggregation on a system with HMB and caching using DRAM is PCIe bandwidth. In the case of an aggregating operation on a coupled DRAM, the storage device just fetches the data from host memory over the PCIe bus and no more PCIe traffic is required for execution of the command. All other traffic is directed to the coupled DRAM. On the other hand, when using the HMB for write aggregation, the device first fetches the data through the PCIe bus. Then the storage device writes the data to the HMB through the PCIe bus. Finally, when writing the data to the flash, the data is transferred again over the PCIe bus. Table 2 shown below summarizes the amount of data transferred over the PCIe bus in both cases. The data that is transferred over the PCIe bus is tripled when using the HMB for write caching.

TABLE 2PCIe Traffic using HMB Write Caching vs. DRAM Write CachingCoupled DRAMWrite CachingHMB Write CachingData Read over PCIe Busx2xData Written over PCIe0xBus
In Table 2, the first row after the header illustrates the amount of read data transmitted over the PCIe bus for coupled DRAM write caching and HMB write caching. The second row indicates PCIe bus utilization for data writes. In Table 2, the variable “x” represents an amount of data to be written to flash memory. For coupled DRAM write caching, data is only transferred over the PCIe bus once, i.e., when the data is read from host memory, across the PCIe bus to the storage device. The data is then cached in the DRAM on the storage device, aggregated until enough data is present to write a full page, and then the data is written from the coupled DRAM to the flash memory in a single write operation without traversing the PCIe bus. For write caching using the HMB, data is initially read over the PCIe bus to the storage device, written from the storage device over the PCIe bus to the HMB, and read from the HMB to the storage device for writing to flash memory. Thus, for HMB caching, the data traverses the PCIe bus three times versus once for coupled DRAM caching. In light of the additional utilization of the PCIe bus, the subject matter described herein includes several optimizations to implement write caching using the host memory buffer. Exemplary optimizations will be described below.

1. Host Interface DMA Operation

In order to use the PCIe more efficiently for write caching using the HMB, in one embodiment, the DMA controller closes the loop on reads from host memory and writes to the HMB with no interaction with the back end of the storage device. This operation is illustrated inFIG. 4. InFIG. 4, DMA controller118fetches the data specified by a write command from the host and writes the data in parallel to the fetching of the data to host memory buffer302. The parallel reading and writing of the data is possible because the PCIe bus is a full-duplex communication medium. Back end components of non-volatile memory system100, such as back end module110, and non-volatile memory104, are not affected by the fetching or writing of the data.

Benefits of fetching the data from write commands in parallel with writing the data to HMB302using the DMA controller include:

a) PCIe bandwidth—PCIe bandwidth is used more efficiently by taking advantage of the full-duplex capability of the PCIe bus.

b) Area—Because data is written HMB302in parallel with the fetching of data from host memory301, less buffer space is required in non-volatile memory system100to buffer data before it is written to non-volatile memory104.

c) Simplification of the back end—back end components of non-volatile memory system100are simplified because they do not interact with host device300during the aggregation of data into host memory buffer302.

2. Ordering of Read and Write to HMB and Read From HMB

The NVMe specification does not specify ordering rules between read and write commands. However, when implementing writes aggregation using the HMB and coupled DRAM or other storage on non-volatile memory system100is limited, it is more efficient to execute commands in a specified order. An exemplary ordering algorithm may utilize PCIe bus resources efficiently and also releases HMB resources after writing accumulated data to flash memory.

Since the PCIe bus is full duplex, read and write operations can be executed in parallel. PCIe read transfers are required for host write commands in two scenarios. The first scenario is when reading from host data buffers specified in the host write command and the second is when reading data from the HMB just before writing it to non-volatile memory104. PCIe write operations are required in two scenarios. The first scenario is for host read commands and the other is for host write commands when updating the HMB.

As explained above, reading from host data buffers and writing to the HMB may be performed in parallel. Similarly, the transfer of data from the storage device for host read commands and reading from the HMB can be executed in parallel. As a result, one ordering algorithm that may be used is summarized below:

a) Reading data from HMB302(just before writing to flash) is performed in parallel with the transfer of data from the storage device to satisfy host read commands. The reading from HMB302and the transfer of data from the storage device to satisfy host read commands may be given a first or highest level priority.

b) Reading data from host buffers for host write commands and writing the data to the HMB may also be executed in parallel. These transfers may be given a lower priority than reading data from the HMB in parallel with transferring data from the storage device to satisfy host read commands.

Operations may be executed according to these priorities, i.e., reading from the HMB and the transfer of data from the storage device to satisfy host read commands may have priority over reading from the host buffers and writing to the HMB. In other words, in such a system, read commands from the host should be given higher priority over write commands from the host in order to increase the overall performance and increase PCIe efficiency.

As stated above, a read-write collision may occur when the host attempts to read data that is maintained in the HMB but has not been written to flash memory. In such a case, device controller102may satisfy the read command by providing data directly from the host memory buffer without first writing the data to non-volatile memory104.

FIG. 5Ais a flow chart illustrating an exemplary process for implementing write caching using HMB according to an embodiment of the subject matter described herein. Referring toFIG. 5A, in step500, write commands are retrieved from the host. As stated above, device controller102may read or retrieve write commands from the corresponding submission queue in host memory301. In step502, the write commands are classified. Write classifier114may classify the write commands in one or more categories, such as random, sequential, long, etc. In step504, data specified by the write commands is retrieved from the host. Step504may be implemented by controller102reading the associated data from host memory301over bus122. In step506, the data retrieved is written to the aggregation queues in the host memory buffer. Steps504and506may be performed in parallel, as indicated above. In step508, the coherency table is updated to reflect the LBA ranges for data stored in the HMB.

FIG. 5Billustrates exemplary messaging between controller102and host300for a host write operation where data from the write operation is cached in host memory buffer302. Referring toFIG. 5B, in step 1, host300posts a command to a submission queue maintained in host memory. In step 2, host300writes to a submission queue tail doorbell register of controller102to signal controller102that a new command has been placed in the submission queue. In step 3, controller102fetches the command from the submission queue.

In step 4, controller102executes the command, which in this example is a host write command specifying data stored in a range of logical block addresses in host memory to be written to non-volatile memory104. This data is cached in host memory buffer302. Accordingly, in step 4a, controller102fetches the data corresponding to the LBA range from host memory. In step 4b, controller102writes the data to an aggregation queue in host memory buffer302. In step 5, controller102writes an entry to a completion queue in host memory to indicate to host300that the write command has been completed. In step 6, the controller updates the coherency table to reflect the fact that the data for the LBA range specified in the write command is stored in host memory buffer302.

In parallel with the process illustrated inFIG. 5A, the aggregation queues in the HMB are monitored and periodically written to flash memory when enough data to fill one or more flash pages is accumulated. This process is illustrated inFIG. 6A. Referring toFIG. 6A, in step600, data accumulation levels in the aggregation queues are checked. In step602, it is determined whether a level in a particular queue exceeds a threshold, such as a page threshold. If the level is not greater than the threshold, device controller102continues the monitoring process. If the accumulation level achieves or exceeds a threshold, control proceeds to step604where the data is written from the HMB to the flash memory. The steps illustrated inFIG. 6Amay be performed by controller102for each aggregation queue maintained in HMB302.

FIG. 6Billustrates exemplary operations between host300and controller102when the amount of data in an aggregation queue passes a threshold level and is written to non-volatile memory. Referring toFIG. 6B, in step 1, controller102detects that the level of data in an aggregation queue maintained in host memory buffer302has crossed a threshold level. As described above, the threshold level may be an amount of data that corresponds to a page size of non-volatile memory104. In step 2, controller102fetches the data from the aggregation queue in the host memory buffer. In the step 3, controller102writes the data to non-volatile memory104. In step 4, controller102updates the coherency table to reflect that the data has been written from the aggregation queue to non-volatile memory104.

Advantages

The following advantages may be achieved at least in part by the subject matter described herein. The efficiency of both the NVMe protocol and the flash device may be improved. One improvement is that NVMe write commands are completed extremely fast from a host perspective since the data is not written to the flash at the time that the command completion message is sent back to the host. Flash memory is more efficiently utilized than in implementations that use padding because only full pages are written from the HMB to the flash memory. Flash endurance is also improved since the number of write operations is reduced over implementations that pad and execute each write command to flash memory. The need for DRAM in the memory device is reduced by utilizing the HMB as the mechanism for caching the data for write operations.

The subject matter described herein can be implemented in any suitable NAND flash memory, including 2D or 3D NAND flash memory. Semiconductor memory devices include volatile memory devices, such as dynamic random access memory (“DRAM”) or static random access memory (“SRAM”) devices, non-volatile memory devices, such as resistive random access memory (“ReRAM”), electrically erasable programmable read only memory (“EEPROM”), flash memory (which can also be considered a subset of EEPROM), ferroelectric random access memory (“FRAM”), and magnetoresistive random access memory (“MRAM”), and other semiconductor elements capable of storing information. Each type of memory device may have different configurations. For example, flash memory devices may be configured in a NAND or a NOR configuration.

One of skill in the art will recognize that the subject matter described herein is not limited to the two dimensional and three dimensional exemplary structures described but cover all relevant memory structures within the spirit and scope of the subject matter as described herein and as understood by one of skill in the art.

A method for write aggregation using a host memory buffer includes fetching write commands and data specified by the write commands from a host over a bus to a non-volatile memory system coupled to the host. Writing the data specified by the write commands from the non-volatile memory system over the bus to the host. The method further includes aggregating the data specified by the write commands in a host memory buffer maintained in memory of the host. The method further includes determining whether the data in the host memory buffer has aggregated to a threshold amount. The method further includes, in response to determining that the data has aggregated to the threshold amount, reading the data from the host memory buffer to the non-volatile memory system and writing the data to non-volatile memory in the non-volatile memory system.

A method for write aggregation using a host memory buffer includes caching data from host write operations in a host memory buffer accessible by a non-volatile memory system coupled to a host system via a bus. The method further includes determining whether an amount of data in the host memory buffer is greater than or equal to a threshold amount. The method further includes, in response to determining that the amount of data in the host memory buffer is greater than or equal to the threshold amount, fetching the data from the host memory buffer and writing the data to non-volatile memory of the non-volatile memory system.