KR20220033976A - Enhanced read-ahead capability for storage devices - Google Patents

Abstract

In the context of data storage, an approach for pre-fetching data prior to a read request is to receive a read request and a next read request, and to send metadata corresponding to the read request to a next data storage address corresponding to the next read request. It involves updating. In response to later receiving the read request again, the next data store address may be read from the read request metadata, and the next data may be pre-fetched from the next data store address before processing the subsequent read request. Moreover, the next data may be pre-fetched during read queue idle time in anticipation of another incoming next read request in response to the next data being returned to the host from the buffer rather than a read of non-volatile memory and It can be stored in a cache buffer.

Description

ENHANCED READ-AHEAD CAPABILITY FOR STORAGE DEVICES

Cross-referencing of related applications

This application is a continuation-in-part of U.S. Patent Application No. 16/012,311, filed June 19, 2018, and claims the benefit of priority thereto, the entire contents of which are incorporated herein by reference for all purposes. incorporated by reference for

technical field

Aspects of the present disclosure relate to the field of storage devices, and more particularly, to enhanced read-ahead capability to improve speed of read operations.

As the speed of central processing units, graphics processors, and other processing elements increases, storage devices have become a bottleneck in the overall performance of computing systems. The speed at which solid state drives (SSDs) operate relative to hard disk drives (HDDs) have alleviated this problem somewhat. Regardless, a given SSD can still be an obstacle on the host, and the performance of the SSDs can vary widely from one another.

The relative performance of a storage device can be evaluated based on a number of factors, such as the capacity of a given device and its read and write speed. Although most write speeds have increased over time, read time has been a significant limiting factor in the performance of storage devices. Sequential read techniques increase the toggle rates, but instead increase the speeds to some degree with increased power consumption.

Random readout presents certain challenges for the purpose of increasing speed. In contrast to sequential reads, which allow large successive blocks of data to be read from contiguous locations on the medium, random reads search for data that is scattered across various non-contiguous locations on the medium. Thus, random reads introduce latency to the read process, which affects the overall performance of the storage device of the associated host.

A read-ahead technique is disclosed herein to increase the speed at which storage devices read data. Data for a given write operation may be written to storage such that the location of the next write is stored with the data. Later, as data is being read from storage, other data may be pre-fetched from the location of the next write that was written with the data. If the next location is the target of a subsequent read operation, other data may be returned to the host immediately after it has already been read from the location where it was stored. Thereby, this process accelerates subsequent read operations.

In the context of data storage, an approach for pre-fetching data prior to a read request is to receive a read request and a next read request, and to send metadata corresponding to the read request to a next data storage address corresponding to the next read request. It involves updating. In response to later receiving the read request again, the next data store address may be read from the read request metadata, and the next data may be pre-fetched from the next data store address before processing the subsequent read request. Moreover, the next data may be pre-fetched during read queue idle time in anticipation of another incoming next read request in response to the next data being returned to the host from the buffer rather than a read of non-volatile memory and It can be stored in a cache buffer.

A number of aspects of the present disclosure may be better understood with reference to the following drawings. Elements in the drawings are not necessarily drawn to scale, emphasis instead being placed on clearly illustrating the principles of the present disclosure. Moreover, in the drawings, the same reference numerals refer to corresponding parts throughout the various drawings. Although some embodiments are described in connection with these drawings, the present disclosure is not limited to the embodiments disclosed herein. On the contrary, the intention is to cover all alternatives, modifications, and equivalents.
1 illustrates a computing system in one implementation.
2 illustrates a write process in one implementation.
3 illustrates a read process in one implementation.
4 illustrates an operating scenario in one implementation.
5 illustrates a computing system in one implementation.
6 illustrates a write process in one implementation.
7 illustrates a read process in one implementation.
8 illustrates an operational architecture in one implementation.
9A and 9B illustrate an operational architecture in one implementation.
10 illustrates a power control process in one implementation.
11 illustrates a simplified computing system architecture in one implementation.
12 illustrates an approach for reducing read time in one implementation.
13 illustrates a method of pre-fetching data in one implementation.
14 illustrates a method of pre-fetching data into a read queue in one implementation.

An improved storage device with improved read-ahead capability is disclosed herein. In various implementations, read times are reduced (and speed is increased) by predicting which address will be read next after a given read operation. Data at that address may be pre-fetched prior to subsequent read requests targeting that address.

The predicted address may be derived from stored information about the write commands as they appear in the queue. This address tracking can be used during the read of each address as a predictor for the next read command. In one example, the predicted address is obtained from the payload of a read-ahead operation. That is, during a previous write operation, the address of the next write may be written to storage along with the data in the payload of a given write. Then, if that payload is the subject of a read request, it can be parsed to obtain the address of what becomes the next write address. The next write address may then be utilized as the next/predicted read address.

As such, data at the predicted address may be pre-fetched prior to any subsequent reads that could potentially be directed to the same address. Data may be buffered in anticipation of relevant reads. When the next read request is directed to the predicted address, the buffered data can be returned immediately without having to wait for a read operation. If the next read is not directed to the expected address, the data may be discarded.

Obtaining the address of the next write command is possible because there is a high probability of having other write commands in the queue while performing a given write due to the amount of time it takes to program data onto the medium. Conversely, the probability of having other read requests in the queue is low due to the relative speed of read versus write. Thus, predicting this next read is useful because it is likely during a read where the read queue is empty.

In some implementations, power consumption may increase as a result of enhanced read-ahead since not all predictions will be successful. A countermeasure to reduce redundancy overhead and extra power consumption is to track the success rate of the above-mentioned proposed predictions. Predictive reads may be conditionally enabled when the success rate exceeds a predetermined threshold and disabled when the success rate falls below a threshold.

In various implementations, the storage device may be, for example, a solid-state drive (SSD), a hard disk drive (HDD), a hybrid SSD-HDD, or any other type of storage device. can A device is a device that oversees how data is written to and read from a medium, such as NAND-based flash memory, dynamic random access memory (DRAM), magnetic data storage, optical data storage, and/or any other type of storage technology. includes a controller.

The controller may be implemented in hardware, firmware, software, or a combination thereof, and bridges the memory components of the device to the host. In a hardware implementation, the controller includes control circuitry coupled to the storage medium. The control circuitry includes a receive circuitry for receiving write requests from the host. Each write request includes the target address for the data as well as the data that is the target of the write request. The target address may be a logical block address (LBA), a physical block address (PBA), or other such identifier that describes where to store the data.

The control circuitry also includes a location circuit that identifies a next write address for a next write request after a previous write request. A write circuit in the control circuit writes the data for the write request and the indication of the next write address to the target address for the write request. In other words, the data that is the object of the write request is written to the address and storage of the next write request. As used herein, “indication” means any data value, bit value, signal, flag, condition that can be used to identify or confirm the location of a set of data to be subsequently stored on a medium. , offset, code, or number.

In a simple example, 4 bytes of a 16 kb page being written can be used for the address of the next write (0.025% overhead). The address of the next write can be written in the header section of a given page, but it is also possible to store the address in the user data section of the page. Examples of addresses include PBAs, LBAs, or both, as well as any other information indicating the location of the next write. In some implementations, the next write address is the absolute address of where the next data including die, page, and block information is stored. In other implementations, the indication of the next write address may be an offset from the current LBA or PBA that may be used to resolve the next address. In still other examples, the next address may be written to a short-hand version of the address. The address of the next write may be stored in encoded form, unencoded form, or in any other manner.

Subsequent to the write requests, the host may communicate a read request targeting the same address as in the initial write request. A read circuit in the control circuit reads data from the target address and the next write address. Further, the read circuit pre-reads at the position indicated by the next write address to obtain the next data prior to the next read request. As described above, the next write address serving as a read-ahead address may be indicated by LBA, PBA, offset, flag, or the like. For example, in the case of an LBA, the control circuitry converts the LBA to a PBA to fetch the next data. In another example, no conversion is required if the next write address is stored as a PBA. In the case of offsets, signals, flags, etc., the control circuitry may calculate a read-ahead PBA from the current PBA and values associated with the offset, signal, flag, etc. When the next read request is forwarded by the host, the next data is ready to be returned immediately to the host. In some cases, both the initial read request and the next read request are considered random read requests, and thus read operations are considered random reads. In some implementations, the control circuit further comprises a buffer circuit for storing the indication of the next write address and for storing the next data. An indication of the next buffered write address may be stored as a value that may be compared to the target address in relation to subsequent read requests. For example, the buffered value may be an LBA, which may be compared to the LBA in a subsequent read request. In certain embodiments, if subsequent read requests utilize PBAs, the buffered value may be a PBA instead of an LBA. In some scenarios, addresses and data associated with multiple read-ahead operations may be simultaneously stored in a buffer. The buffer may be sized to accommodate one or more pages of data. In one scenario, the buffer may be 96 kB or less of RAM, or approximately 4 pages of data in size. However, as with page size, it may be understood that RAM size may increase.

The comparator portion of the control circuit may then determine that the next target address specified in the next read request matches the next write address. This can be accomplished by comparing the value of the next write address in the buffer with the value of the address in the next read request. For example, the LBA in the next read request may be compared to the LBA in the buffer. In another example, the PBA in the next read request may be compared to the PBA in the buffer. In some alternative embodiments, the value stored in the buffer may differ by an offset from the actual value of the next write address as stored on the medium or calculated during a pre-read operation. In this situation, the control circuit will calculate the actual value before comparing it to the value in the next read request. The comparator or other element(s) of the control circuit may return the next data to the host in response to the next read request in the situation where the values match each other. If the next target address given in the next read request does not match the next write address, the comparator may discard the next data.

The controller may include a write queue and a read queue in some implementations. The read queue receives read requests from the host, and the write queue receives write requests. The read requests may indicate a location from which to read data from the non-volatile storage media, allowing the controller to fetch data from the location indicated by the given read request.

In doing so, the controller parses the predicted address of the next read request from the payload read from the location. The controller may then pre-fetch additional data from the predicted location of the next read request before actually receiving the next read request. If the actual position of the next read request is different from the predicted position, the controller may simply discard the next data and continue reading from the actual position.

For a write queue, each write request in the queue indicates where to write data for a given write request. The predictor portion of the controller identifies the predicted position for the next read request based on the position indicated by the next write request after the previous write request. The write portion of the controller may write the data for the previous write request and an indication of the predicted position at the location indicated for the previous write request. A buffer portion of the controller may store an indication of the predicted location for the next read request and also the next data.

As described above, the comparator portion may determine that the position indicated by the next read request matches the predicted position for the next read request. The comparator or other part(s) of the controller may then return data to the host. Next data may be discarded if the position indicated by the next read request does not match the predicted position for the next read request.

This enhanced read-ahead technique provides various technical advantages, as will be apparent from the discussion above and the following discussion of FIGS. 1-10. For example, pre-fetching data prior to a read request increases the read speed. This can be particularly beneficial in the case of random reads that take a longer amount of time to complete because their data is spread across the medium. In another example, the requesting application on the host does not need to be known by the controller. Rather, the controller may employ enhanced pre-reading without any knowledge of the requesting application.

Referring now to the drawings, FIG. 1 illustrates a computing system 100 in an implementation of an enhanced read-ahead technique. The computing system 100 includes a host 101 and a storage device 110 . Host 101 represents any host subsystem capable of writing data to and reading data from storage device 110 . Storage device 110 represents any device capable of internally or externally connecting to host 101 for the purpose of reading and writing data. Examples of storage device 110 include solid state drives (SSDs), thumb drives, hard disk drives (HDDs), hybrid SSD/HDD drives, and any variation or combination thereof, although , but not limited thereto. Examples of computing system 100 include personal computers, laptop computers, server computers, tablet computers, mobile phones, network drives, consumer electronic devices (eg, cameras, televisions, and media players). ), gaming devices, durable product devices, and any other system, variant, or combination thereof utilizing one or more storage devices.

Host 101 communicates with storage device 110 via connection 103 . Connection 103 represents one or more physical interconnects coupling host 101 and storage device 110 and through which storage communications may flow between host 101 and storage device 110 . When communicating with the storage device 110 , the host 101 may include a serial ATA (SATA), Fiber Channel, Firewire, Serial Attached Small Computer Systems Interface (SAS), ATA/IDE (Advanced Technology Attachment/Integrated Drive) Electronics), Universal Serial Bus (USB), and one or more interface protocols such as, but not limited to, Peripheral Component Interconnect Express (PCIe).

The storage device 110 includes a controller 111 and a storage medium 115 . The controller 111 represents one or more processing elements that perform a monitoring role for writing data to and reading data from the storage medium 115 . The controller 111 may be implemented in hardware, but also in firmware, software, or other form of program instructions executable by the controller 111 , the write process 200 described in more detail in FIGS. 2 and 3 . and read process 300 , respectively. Storage medium 115 is any non-volatile medium to which data can be written and read. Examples include, but are not limited to, NAND flash media, DRAM media, phase change media, magnetic media, and optical media. Connection 113 represents one or more physical interconnects coupling controller 111 and storage medium 115 .

In operation, the host 101 transmits read and write requests to the controller 111 to be performed on the storage medium 115 , among which the write requests 121 and the read request 125 are representative. The controller 111 executes the write process 200 when processing the write requests 121 and executes the read process 300 when processing the read request 125 . The following is a detailed discussion of the write process 200 and the read process 300, with reference to the steps in FIGS. 2 and 3 respectively in parentheses.

Referring to FIG. 2 , the controller 111 receives a given write request from the host 101 (step 201). The write request includes the data to be written and a location indicating where to write the data on the storage medium 115 . The location may be given by a physical block address (PBA), logical block address (LBA), or any other suitable indication. In some cases, the location may not be given in the write request itself, but rather may be separately provided by the host 101 or determined by the controller 111 when receiving the write request.

Next, the controller 111 identifies the next location of the next write request submitted by the host 101 (step 203). This may be accomplished, for example, by reading the address associated with the next write request from the write queue. The controller 111 then generates a payload to be written to the location specified for the initial write request (step 205). The payload may include at least data for the first write request and a next location for the next write request. The next location may be a PBA, but alternatively an LBA.

Although in this example only one of the following locations is included in the payload, it should be understood that multiple locations may be stored in a single payload. For example, both the next address and the next address thereafter may be stored in a given payload. Also, as used herein, the term “next” refers to the immediately next address in a queue, although variations are possible. For example, the immediately next address may be skipped, and the next address thereafter may be used instead and included in the payload.

When generating the payload, the controller 111 writes the payload to the initial location specified for the write request (step 207). In this way, the data for a write request is stored along with the identity of the position for the next write request in the queue. The write process 200 may continue for subsequent write requests writing the address of the next write request to follow each preceding request along with data for the request. Subsequent location information may serve as a predicted location for the reading process 300 that is discussed subsequently.

Referring to the read process 300 of FIG. 3 , the controller 111 receives a given read request from the host 101 (step 301 ). The read request includes an address from which the controller 111 reads data. The location may be specified as a PBA or an LBA, in which case the controller 111 converts the LBA to a PBA.

The controller 111 fetches the payload from the storage medium 115 at the address given by the read request (step 303 ), and its data and the payload to the next location where it was stored along with the data in the context of the write process 200 . is parsed (step 305). The data may be returned to the host 101 (step 306), and the next location is used to pre-fetch the next data (step 307).

It can be seen that the pre-fetch step need not always occur. Rather, the controller 111 may refrain from attempting to pre-fetch the data if the payload contains a null value or otherwise does not contain the next position. In another optional example, the controller 111 may suppress the parsing and pre-fetching steps if the read request is not a random read request. That is, before proceeding to steps 305 and 307, the controller 111 may first determine whether the read request is a random read request. The controller 111 may determine by itself that the read request is a random read, or it may be aware of that fact by the host 101 .

The address of the next location and the pre-fetched data may be buffered so that they are available when a subsequent read request is received. In some implementations, the payload may include more than one next address, in which case the controller may pre-fetch and buffer data from multiple locations. After that, a number of "next addresses" will also be buffered.

The controller 111 compares the address in the subsequent read request to the next address in the buffer (or multiple next addresses if present in the buffer) to determine if the address in the subsequent read request and the next address in the buffer are the same. If the address in the subsequent read request and the next address in the buffer are the same, the controller 111 may return the pre-fetched data to the host 101 in response to the subsequent read request, rather than fetching it.

Referring back to the example scenario illustrated in FIG. 1 , the host 101 submits write requests 121 to the storage device 110 . write requests 121 include a first request with data d1 and address L1; the second request includes data d2 and location L2; The nth request contains data dn and location Ln.

Applying the write process 200 to the first write request, the controller 111 generates payloads 123 to be written to the storage medium 115 . The controller 111 generates the payload d1_L2 from the data in the first request and the address in the second request. The payload is written to the storage medium 115 . Similarly, the controller 111 generates a payload d2_L3 for the second request. The payload generated for the Nth request contains the data from the nth request and the position of the next write request in the queue, or dn_Ln+.

Host 101 also submits a read request indicated by read request 125 . Read request 125 identifies location L1 as other types of reads are possible, but may represent, for example, a random read request.

Applying read process 300 , controller 111 fetches (and pre-fetches) payloads 127 in response to read requests from host 101 . For example, the controller 111 fetches the payload from location L1 or d1_L2, which is the payload for the first write request discussed above.

The controller 111 parses the payload to obtain the next location L2. The data portion of the payload d1 may be returned to the host 101 . Controller 111 also pre-fetches the payload at location L2 in anticipation of another read request directed to L2. The payload is also parsed into its data part (d2) and location part (L3).

Assuming another read request to L2 is received, the controller 111 may immediately return a response with data d2 without the need to fetch the data. However, if no read requests to L2 are received, the data d2 may be discarded or overwritten after a period of time. The controller may optionally pre-fetch the payload at location L3 and thereafter at location Ln+ until the constraint of the limit is reached.

4 illustrates an operating scenario 400 in an implementation showing various timing aspects of the enhanced read-ahead technique disclosed herein. The operational scenario 400 includes a host 401 , a write queue 403 , a read queue 404 , a controller 405 , and a medium 407 . Although shown separately, the write queue 404 and the read queue 404 may be implemented externally or internally to the controller 405 . It may be understood that other elements, connections, etc. may be involved for purposes of clarity but are not shown.

During operation, host 401 forwards two write requests to write queue 403 denoted w1 (d1, L1) and w2 (d2, L2). Although shown as a direct transfer between the host 401 and the queues, it may be understood that requests may be routed through other physical or logical elements before reaching the write queue 403 , including the controller 405 .

The controller 405 implements the write requests in the normal order in which they are received in the queue. Thus, the controller 405 implements w1 first, and then implements w2. For the first write request, the controller 405 looks in the queue to identify the address of the next write request - ie, w2. If L2 is known, controller 405 generates a payload for w1 comprising d1 and L2. Then, the controller 405 writes d1 and L2 to the medium 407 at the position specified by the first write request L1.

Following the general order of the queue, the controller 405 next processes the second write request. For illustrative purposes, it is assumed that a third write request is behind w2 in write queue 403 and addressed to L3 . Thus, the controller 405 generates a payload for w2 that includes d2 and L3. The payload is then written to L2 in medium 407 .

Later, after the writes are complete, the host 401 may submit read requests to obtain the data previously written to w1. The read queue 404 is filled with read requests indicating the address from which to obtain the data. The controller 405 fetches the payload stored at the indicated address, including the data d1 and the next location L2.

The controller 405 parses the payload into its data and location components and returns the data portion to the host 401 . By the location part, the controller 405 pre-fetches the payload at location L2. The payload contains data d2 and another "next" location (L3). The controller 405 buffers the data with the location L2 from which the data was retrieved, as opposed to the location where it was stored with the data. The controller 405 may optionally perform another pre-fetch on the payload stored in L3.

Host 401 forwards subsequent read requests. Controller 405 in response compares the position in the subsequent read request to the position stored in the buffer. In this example, addresses on both sides reflect L2. As such, the controller 405 may respond to the read request with buffered data d2 rather than having to fetch the data from the medium 407 .

5 illustrates a computing system 500 in another implementation of an enhanced read-ahead technique as applied in the context of a multi-threaded environment. The computing system 500 includes a host 501 and a storage device 510 . Host 501 represents any multi-threaded subsystem capable of writing data to and reading data from storage device 510 . Storage device 510 represents any device capable of internally or externally connecting to host 501 for the purpose of reading and writing data.

Threads 502 and 504 each represent various threads that may be available in a multi-threaded environment. Each thread may be dynamically assigned at run-time to a different application, utility, or component running on the host 501 . Threads submit read requests, represented by requests 522 (associated with thread 502 ) and requests 524 (associated with thread 504 ) to storage device 510 .

Host 501 communicates with storage device 510 via connection 503 . Connection 503 represents one or more physical interconnects that communicatively couple host 501 and storage device 510 . When communicating with the storage device 510 , the host 501 may include a serial ATA (SATA), Fiber Channel, Firewire, Serial Attached Small Computer Systems Interface (SAS), Advanced Technology Attachment/Integrated Drive (ATA/IDE), Electronics), Universal Serial Bus (USB), and one or more interface protocols such as, but not limited to, Peripheral Component Interconnect Express (PCIe).

The storage device 510 includes a controller 511 and a medium 515 . Controller 511 represents one or more processing elements that control read and write processors with respect to medium 515 . Controller 511 may execute write processor 600 and read processor 700 , which are described in greater detail in FIGS. 6 and 7 , respectively. Medium 515 is any non-volatile medium to which data can be written and read. Examples include, but are not limited to, NAND flash media, DRAM media, phase change media, magnetic media, and optical media. Connection 513 represents one or more physical interconnects coupling controller 511 and medium 515 .

In operation, host 501 forwards read and write requests to controller 511 . Controller 511 executes write process 600 when processing write requests and executes read process 700 when processing read requests. The following is a detailed discussion of the write process 600 and the read process 600, with reference to the steps of FIGS. 6 and 7 respectively in parentheses.

Referring to FIG. 6 , the controller 511 receives multiple write requests 2 from the host 501 (step 501). Each write request includes the data to be written and a location on the medium 515 indicating where to write the data. The location may be given by a physical block address (PBA), logical block address (LBA), or any other suitable address. In some cases, the location may not be given in the write request itself, but rather may be separately provided by the host 501 or determined by the controller 511 upon receiving the write request.

For any given write request, the controller 511 identifies the thread associated with the next request after any given write request (step 603). The thread may be identified in the next write request or may be determined in some other way. Controller 511 compares the thread associated with the instant request to the thread associated with the next request to determine if they are identical (step 605).

If the threads are the same, the controller 511 generates a payload consisting of the data for the instant request and the next address of the next write request (step 607). The payload is then written to the indicated address (step 609). However, if the threads are not identical, the controller 511 may conserve resources by simply writing data to the indicated address (step 606), thereby avoiding generating a payload.

Referring to Fig. 7, the controller 511 receives a read request identifying the target address (step 701). In response, controller 511 checks the read-ahead flag to determine whether any information has been buffered for the previous read request (step 703). If the flag is enabled, the controller 511 evaluates the target address in the request against the address stored in the buffer (step 705). If these addresses are the same, the controller may read data from the pre-fetched buffer in the context of processing the previous read request (step 706).

If the addresses are not the same, the controller 511 proceeds to fetch the payload at the address specified in the read request (step 707). The controller 511 parses the payload into component parts containing at least data and an address belonging to the next data to be written after the target data (step 709).

Using this data, the controller 511 can read the data to the host 501 (step 710). The controller 511 also checks whether the next address is null or some other value indicating that the next address has not been written to storage (step 711). This may be the case, for example, when the next write request following a given write request does not originate from the same thread (see step 605 above with respect to FIG. 6 ).

If the next address value is null, the controller 511 sets the flag to disable (step 712), so that when receiving a subsequent read request, the step of comparing the addresses can be omitted. If the next address is not null, the controller 511 sets (or maintains) the flag value to enable (or maintains), so that the target addresses in subsequent read requests can be compared (step 713).

Upon setting the flag, the controller 511 pre-fetches the payload stored at the location of the next address parsed from the target payload (step 715). The controller 511 stores the next data from the pre-fetched payload in a buffer, along with the address corresponding to the next data (step 717). The next address may be compared to the subsequent target address included in the subsequent read request when the read process 700 returns to step 705 .

8 illustrates an implementation of a write-side of an enhanced read-ahead technique and an operational architecture 800 in an associated example scenario. Referring to FIG. 8 , FIGS. 9A and 9B illustrate an operational architecture 900 in the implementation of the read side of the enhanced pre-read technique as well as the associated example scenario. It may be appreciated that the two architectures may be combined (without any extra elements) in connection with a suitable storage device such as an SSD, hybrid HDD/SSD, or the like.

Referring to FIG. 8 , an operational architecture 800 includes a write queue 810 , a medium 810 , and various operational modules represented by a location module 801 , a receive module 803 , and a write module 805 . include The location module 801 , the receive module 803 , and the write module may be implemented in hardware, firmware, or other software, as well as any variation or combination thereof. Write queue 810 may be implemented externally from medium 830 , but may also be implemented internally. In either case, the write queue 810 is accessible to one or more of the location module 801 , the receive module 803 , and the write module 805 . It may be appreciated that the operational architecture 800 may include other elements that are omitted for clarity, such as a system bus, interfaces, and interconnects, and the like.

In operation, write requests are received from a host (not shown) into a write queue 810 and occupy an order or place in the queue. Write requests include request w1 at location 811; request w2 at location 813; Represented by a request w3 at a location 815 , and a request wn at a location 817 . Accordingly, write requests are processed in that order: w1, w2, w3, wn, etc.

The receiving module 803 receives write requests as they are dispatched from the write queue 810 to be executed. As an example, the receiving module 803 receives the request w1 and forwards it to the writing module 805 . The request w1 contains data d1 and a location identifier L1 to which to write the data.

The positioning module 801 examines the write queue 810 to identify the position of the next write request in the queue after the target write request, which in this case is w2. The location of w2 is L2 , so the location module 801 passes L2 to the write module 805 . The writing module 805 receives both the information from the receiving module 803 and the information from the location module, and generates a payload to be written to L1 . In this example, payload 831 is a combination of d1 and L2.

A similar operation is performed for other write requests in the queue. The payload 833 is generated in association with w2 and includes data d2 and a location L3. Payload 835 is generated in association with w3 and includes data d3 and location L4. Finally, a payload 837 is generated in association with wn and includes data dn and a location Ln+. In this way, the payloads can be checked during the read process and pre-fetched where appropriate, thereby accelerating the read process.

Referring to FIG. 9A , the operational architecture 900 includes a read queue 950 , a medium 910 , and various operational modules represented by a compare module 941 , a read module 943 , and a buffer 947 . do. The read module 943 may include a parsing module 945 , but the parsing module may be implemented external to the read module 943 . The comparison module 941 , the reading module 943 , the buffer 947 , and the parsing module 945 may be implemented in hardware, firmware, or other software, as well as any variation or combination thereof. The read queue 910 may be implemented externally from the medium 930 , but may also be implemented internally. In either case, read queue 910 is accessible to one or more of compare module 941 , read module 943 , and buffer 947 . It may be appreciated that the operational architecture 900 may include other elements that are omitted for clarity, such as a system bus, interfaces, and interconnects, and the like.

In operation, read requests are received in read queue 950 from the host. The read request is represented by r1 in FIG. 9A, and r2 and r3 in FIG. 9B. Requests have an order or place in the queue, each represented by place 951 , place 953 , and place 955 . Although sequential read requests may be interspersed among random read requests, it is assumed for purposes of illustration that read requests are random read requests as opposed to sequential read requests.

Read requests are taken from the queue and passed to a comparison module 941 . The comparison module 941 compares the address in the given read request with the address buffered in the buffer 947 (if any) to determine whether the target data needs to be fetched or has already been pre-fetched. In this example, the read request r1 is associated with the location L1. L1 is compared to Lx in buffer 947. Since they do not match, the compare module 941 passes the address to the read module 943 .

The read module 943 is responsible for fetching the payload 931 from the location L1 . The parsing module 945 parses the payload into its component parts d1 and L2. The read module 943 may return d1 to the host, and pre-fetch the payload 933 from L2. Payload 933 includes data d2 and location L3. Data d2 is passed to buffer 947 to be stored in relation to location L2.

9B illustrates a continuation of the example scenario that begins in FIG. 9A . In FIG. 9B , a read request r2 is received by comparison module 941 and taken from the queue. Here, the comparison module 941 determines that the target address in r2 is the same as the stored address in the buffer 947 . Accordingly, the comparison module 941 instructs the reading module 943 to read the data d2 from the buffer 942 to the host. The reading module 943 may be omitted in this step.

Since the payload at location L2 refers to the next address in L3, the read module can selectively pre-fetch the payload 935 at L3. In doing so, the parsing module will parse the payload 935 to obtain data d3. Data d3 and location L3 will be stored in buffer 947 and compared for one or more subsequent read requests.

10 illustrates a power control process 1000 in an implementation in which the enhanced read-ahead technique disclosed herein is dynamically enabled and disabled based on various operating conditions. A controller in a solid state drive or other suitable storage device may employ the power control process 1000 , which may be implemented in hardware, firmware, or other software.

In operation, a given controller tracks the hit rate for pre-read attempts made in the context of the enhanced read process (step 1001). The hit rate may relate to the rate at which the pre-fetched data is actually requested by subsequent read requests. For example, an initial read request directed to a first location may generate a payload identifying a second location. The data at the second location will then be pre-fetched prior to any subsequent read request that may (or may not) target the second location. If the next read request is directed to the second location, the pre-fetch will be considered a hit, whereas if the next read request is directed to a different location, the pre-fetch will be considered a miss.

The controller may track the success rate of pre-fetch operations by counting the number of times the pre-fetched data is subject to a subsequent read request. The controller may also analyze whether the hit rate has fallen below a given threshold (step 1003).

If the hit rate remains above the threshold, the controller may continue to operate with the pre-read process enabled. If the hit rate drops below the threshold, the controller disables the read-ahead process (step 1005).

To re-enable the read-ahead process, the controller periodically evaluates one or more other conditions (step 1006). For example, pre-read may be disabled for a period of time and automatically re-enabled upon expiration. In another example, pre-read may remain disabled until a battery level or other power condition is met. Until then, the controller operates with the read-ahead process disabled.

Disabling the read-ahead process may conserve power, processing cycles, or other resources in terms of a high rate of missed read-ahead attempts. Re-enabling the process upon changes in conditions allows the device to recover the benefits of enhanced read-ahead.

Physical Description of Exemplary Action Context: Data Storage System

Solid state drives (SSDs) and/or hard disk drives (HDDs) and/or hybrid SSD-HDD drives or any other type of storage that can connect to host 1150 for the purpose of reading and writing data. There is a commercial need for high capacity digital data storage systems in which multiple data storage devices (DSDs), such as devices or variations or combinations thereof, can be housed in a common enclosure. A data storage system often includes a large enclosure that houses a number of shelves on which rows of DSDs are mounted.

Recall that random read performance is a performance limiting factor of data storage devices and can affect the overall performance of the device by introducing latency into the read process. Thus, any means of predicting which address will be read next may save time, which may result in a reduction in overall device latency. Thus, a way of predicting which data will be requested from the controller next and initiating a “pre-read” (or “pre-fetch”) can increase random read performance and reduce device latency.

11 is a block diagram illustrating a simplified computing system architecture in accordance with an embodiment. An exemplary computing system architecture is a data storage system including a number of data storage devices (DSDs) 1104a (DSD1), 1104b (DSD2), and 1104n (DSDn) (collectively, 1104a-1104n). 1100), where n represents any number of DSDs, which may vary from implementation to implementation. Each DSD 1104a - 1104n communicates with and is under the supervisory control of some supervisory control of the system controller 1102 via a respective communication interface 1114 according to a corresponding communication or interface protocol 1115 . Each DSD 1104a - 1104n has a corresponding non-volatile memory (NVM) 1106 controlled by a respective DSD memory controller 1108 that oversees how data is written to and read from the corresponding NVM 1106 . ) (eg, typically in the form of NAND flash memory in the case of SSDs and spinning magnetic disk media in the case of HDDs).

The system controller 1102 of the data storage system 1100 includes at least a memory 1110 , a processor 1112 , and a read queue 1113 . Read queue 1113 receives and/or fills read requests from host 1150 , where read requests are (eg, logical block address or “LBA” or physical block address or “PBA”) may indicate the location in the NVM 1106 to obtain or read the requested data from, thereby causing the corresponding DSD controller 1108 to obtain data from the appropriate NVM 1106 memory location indicated by the given read request. to be able to fetch Although shown internally and separately, read queue 1113 may be implemented externally or internally to system controller 1102 , or may be implemented within memory 1110 . It may be understood that other elements, connections, etc., may be associated with the system controller 1102 , but are not shown herein for the sake of clarity.

The process, functions, procedures, operations, method steps, etc., being performed or described herein as being executable by the system controller 1102 or by the DSD memory controller 1108 may be stored in one or more memory units. stored and comprising the enactment by execution of one or more sequences of instructions that, when executed by one or more processors, result in such performance. System controller 1102 and DSD controller 1108 may be implemented in any form and/or combination of software, hardware, and firmware. For example, the system controller 1102 may include at least one memory unit for storing such instructions (for a non-limiting example, such as firmware) enabling a read-ahead capability as described elsewhere herein. for example, an application specific integrated circuit (ASIC) including memory 1110) and at least one processor (eg, processor 1112) for executing such instructions.

Data storage system 1100 may be configured on a hardware machine (for non-limiting examples, a computer, hardware server, etc.) on which executable code is executed, or on one or more processors (for non-limiting examples, a storage server, a file server, may be communicatively coupled with host 1150 , which may be implemented as software instructions executable by a software server such as a database server, application server, media server, etc.). Host 1150 generally represents a client of data storage system 1100 and has the ability to make read and write requests (input/output or “IO”) to data storage system 1100 . System controller 1102 may also be referred to as a “host,” as the term is used in reference to a data storage device or any device that makes IO calls to an array of devices, such as DSDs 1104a - 1104n. Because it is often used in general. When the host 1150 communicates with the data storage system 1100 , Serial ATA (SATA), Fiber Channel, Firewire, Serial Attached Small Computer Systems Interface (SAS), ATA/IDE (Advanced Technology Attachment/Integrated) Drive Electronics), Universal Serial Bus (USB), Peripheral Component Interconnect Express (PCIe), etc. may utilize one or more interface protocols, such as, but not limited to.

Read prediction using metadata hints based on previous read operations

According to the analysis, the random read logs exhibit a significant amount of repeating patterns. According to one embodiment, one approach to "read ahead" involves storing the next read command address in the metadata of the current read address. This metadata update may be performed via a conventional "read-modify-write" operation that provides both reading a memory location and writing a new value to that location concurrently as an atomic operation, according to one embodiment. there is. This approach to pre-reading generally involves, for each read command that arrives, updating the metadata of the previous read command with an indication (eg, a “hint”) about the location (and size) of the current read command. can be accompanied by This information can then be used in the future, ie when receiving the same read command, to execute a pre-fetch of future random read commands. Accordingly, the quality of service (QoS) parameter can be significantly improved. That is, in the context of command execution latency (eg, from command arrival via completion posting), if the read-ahead prediction hit rate is high, the latency of command execution is reduced due to reading from the medium ahead in time. Thus, QoS, such as in the form of command execution latency, is particularly important in low queue depth scenarios, for example, where the host sends only a few (eg, up to 8) salient commands to the device at a time. This is a notable parameter.

12 is a block diagram illustrating an approach to reducing read time in accordance with one embodiment. For example, such a process may be implemented in a multi-application and/or multi-host memory system environment. This approach or operation involves two processes: (i) finding or identifying patterns underlying random read operations, distinguishing between the processes, and (ii) predicting and updating data/metadata. It can be implemented to include

12 illustrates a read queue 1113 in which a number of host read requests or commands are placed or temporarily stored awaiting processing. For example, a series of received read requests (“read n”, “read n+1” through “read n+x”) are shown in read queue 1113 , where n is the next represents a read request (ie, at the top of the queue), and x represents any number of read requests that are being held in the read queue 1113 at any given time. According to one embodiment, repeating the current read request (“read n”) (labeled process 1202 ) is where the request (“read n”) originates (eg, the host ( classifying read patterns at block 1203 from the set of read requests processed from the read queue 1113 based on an application identifier (“ID”) that identifies the application (executing on 1150 ). For example, controller 1102 (FIG. 11) can maintain a table of current application IDs that are active, and in response to an incoming read request associated with a given application ID, controller 1102 can display the next read associated with that application ID. Monitor read queue 1113 for requests (“read n+1”). Accordingly, at block 1204, for each application ID, a corresponding read pattern is determined or identified.

From the read requests identified at block 1204 , any write requests according to an embodiment (eg, as read requests and write requests are often considered separately in the context of a system performance capability/metric); Excluding commands, or pattern(s), at block 1205 , the next read request is predicted (prediction of “read n+1”). From there, based on the prediction of the next read request of block 1205 , at block 1206 , metadata 1207 corresponding to the “read n” read request, including the next storage address corresponding to “read n+1”. ) is pushed or stored in NVM 1106 . That is, the metadata 1207 in the NVM 1106 corresponding to the “read n” request is updated with the next data storage address obtained from the next read request, ie, the “read n+1” request. As discussed and in accordance with one embodiment, such as responding to processing a “read n+1” request from read queue 1113 rather than responding to a host write command, at block 1206 , “read-modify- A "write" operation is utilized to push a "read n" metadata update to the NVM 1106 . Thus, while adding "extra" write operations, the resulting benefits appear for future read performance. Moreover and according to one embodiment, the next data storage address updated in metadata 1207 corresponding to a "read n" request is a logical address (eg, LBA) rather than a physical address (eg, PBA), Avoids the performance hit associated with having to update metadata 1207 in NVM 1106 during garbage collection.

Thus, based on the above, whenever another "read n" read request is processed by the controller 1102 (FIG. 11), the storage location (eg, "read n+1") of the next read request ("read n+1") A "hint" or prediction of the storage address) is available from the metadata 1207 associated with "read n", the "read n+1" data being retrieved from the NVM 1106 (FIG. 11) prior to processing a subsequent read request. can be pre-fetched from Thus, if the prediction based on the read patterns is correct, then the data corresponding to the next read request, which is expected to be "read n+1", is already available to the controller 1102 without having to execute a response read command at that time. . According to one embodiment, given read requests classified based on their respective application IDs (at block 1203 ), metadata 1207 in NVM 1106 corresponding to “read n” is “ It is updated to include the next storage address of only "read n+1" in response to both "read n+1" corresponding to read n" and the same application ID.

According to one embodiment, the "next data" 1209 from the next storage location of the NVM 1106 identified from the previous "read n+1" which is likely to be correct data is idle corresponding to the read queue 1113 . (1208) Fetched in response to the occurrence of processing time. According to a related embodiment, the next data 1209 for the predicted next read request “read n+1”, such as pre-fetched during the idle 1208 time, is stored in the cache buffer 1211 at block 1210 , according to a related embodiment. disposed or stored (eg, implemented within memory 1110 ). Thus, the data corresponding to the next read request "read n+1" is already available in the cache buffer 1211 without the need to execute a read command in response to receiving the next read request "read n+1" again; Therefore, it can be returned directly from the cache buffer 1211 to the host 1150 (FIG. 11).

In order to maintain the above procedure for multiple application IDs, as a matter of implementation architecture, each tracker has its own application ID and corresponding corresponding "read-ahead" requests and/or metadata updates, as well as It is desirable to maintain several “tracker” processes or processing threads to be able to handle incoming read requests.

How to pre-fetch data

13 is a flowchart illustrating a method of pre-fetching data according to an embodiment. The process or procedure of FIG. 13 may be implemented for execution as one or more sequences of instructions that are stored in one or more memory units and, when executed by one or more processors, result in execution of the process. For example, sequences of instructions stored in one or more memory units (eg, memory 1110 of FIG. 11 , or read-only memory (ROM) specific to firmware) may be executed by one or more processors (eg, When executed by the processor 1112 of the system controller 1102 of FIG. 11 ) may perform and/or cause performance of the process illustrated in FIG. 13 .

At block 1302, a read request is received from a host, wherein the read request includes a corresponding data storage address and the read request is placed in a read queue. For example, a read request “read n” (FIG. 12) is received from host 1150 (FIG. 11) to read queue 1113 (FIG. 11 and FIG. 12).

At block 1304 , a next read request is received from the host, the next read request includes a corresponding next data storage address, and the next read request is placed in a read queue. For example, a read request “read n+1” ( FIG. 12 ) is received from host 1150 into read queue 1113 .

At block 1306 , the metadata corresponding to the read request is updated in the non-volatile memory with the next data storage address from the next read request. For example, the metadata 1207 corresponding to the read request “read n” is updated in the NVM 1106 with the next data storage address from the next read request “read n+1”.

At block 1308 , in response to again receiving the read request from the host, the next data storage address from the metadata corresponding to the read request is read from the non-volatile memory. For example, in response to again receiving the read request "read n" from the host 1150, the next data storage address from the metadata 1207 (FIG. 12) corresponding to the read request "read n" is the NVM ( 1106).

At block 1310, the next data from the next data storage address is fetched from the read queue prior to processing a subsequent read request. For example, at block 1308 , the next data from the next data storage address as read from the NVM 1106 is from the read queue prior to processing a subsequent read request, ie, the subsequent read request was predicted. It is fetched with the expectation that it will actually be a read request "read n+1"

14 is a flow diagram illustrating a method of pre-fetching data into a read queue according to one embodiment. 13 , the process or procedure of FIG. 14 may be implemented for execution as one or more sequences of instructions stored in one or more memory units, and when executed by one or more processors, result in execution of the process. . For example, sequences of instructions stored in one or more memory units (eg, memory 1110 of FIG. 11 , or read-only memory (ROM) specific to firmware) may be executed by one or more processors (eg, When executed by the processor 1112 of the system controller 1102 of FIG. 11 ) may perform and/or cause performance of the process illustrated in FIG. 14 , which may correspond to the process of FIG. 13 . It may be understood as an optional continuation and/or escalation process.

At block 1402, in response to the occurrence of an idle processing time associated with or corresponding to the read queue, the next data from the next data storage address is fetched. For example, the next data from the next data storage address, as read from the NVM 1106 , expects the subsequent read request in the read queue 1113 to be a read request “read n+1” as expected. and fetched from NVM 1106 during idle time.

At block 1404, the next data from the next data storage address is placed in the cache buffer. For example, based on the next data storage address (from the original read request “read n+1”) from the metadata 1207 associated with the read request “read n”, the next data that was fetched at block 1402 is It is stored in the cache buffer 1211 .

At block 1406 , in response to again receiving the next read request from the host, the next data is returned from the cache buffer 1211 to the host. For example, in response to again receiving the next read request “read n+1” from the host 1150 , the next data is read from the cache buffer 1211 and returned to the host 1150 .

This enhanced read-ahead technique provides various technical advantages as may be apparent from the foregoing description and examples. For example, pre-fetching data prior to the next predicted read request increases the read speed. This is particularly beneficial in the case of random reads that take a longer amount of time to complete because their data is spread across the medium. can do.

As will be understood by one of ordinary skill in the art, aspects of the present invention may be embodied as a system, method, or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, microcode, etc.), or an embodiment combining software and hardware aspects, all of which are generic. may be referred to herein as a “circuit”, “module”, or “system”. Moreover, aspects of the invention may take the form of a computer program product embodied on one or more computer readable medium(s) having computer readable program code embodied thereon.

The included descriptions and drawings depict specific embodiments to teach those skilled in the art how to make and use the best mode. In order to teach the principles of the present invention, some conventional aspects have been simplified or omitted. Those skilled in the art will appreciate variations from these embodiments that fall within the scope of the present disclosure. Those skilled in the art will appreciate that the features described above may be combined in various ways to form multiple embodiments. Consequently, the present invention is not limited to the specific embodiments described above, but only by the claims and their equivalents.

Claims (20)

An electronic device comprising:
non-volatile storage media;
read queue; and
coupled to the non-volatile storage medium;
receive a read request comprising a corresponding data storage address from a host, and place the read request in the read queue;
receive a next read request including a corresponding next data storage address from the host, and place the next read request in the read queue; And
update metadata corresponding to the read request in the non-volatile storage medium to the next data storage address from the next read request
configured to
An electronic device comprising a control circuit. The method of claim 1 , wherein the control circuitry is configured to: in response to again receiving the read request from the host,
read the next data storage address from the metadata corresponding to the read request from the non-volatile storage medium; And
Fetch the next data from the next data storage address prior to processing a subsequent read request.
An electronic device further configured to: The electronic device of claim 1 , wherein the control circuitry is further configured to fetch next data from the next data storage address in response to occurrence of an idle processing time corresponding to the read queue. The electronic device of claim 1 , wherein the update of the metadata corresponding to the read request in the non-volatile storage medium is based on and responsive to the next read request, except for a write request. . The electronic device according to claim 1, wherein the next data storage address updated in the metadata corresponding to the read request is a logical block address (LBA) corresponding to the next read request. The electronic device of claim 1 , wherein the control circuit is further configured to place next data from the next data storage address into a cache buffer. The electronic device of claim 6 , wherein the control circuit is further configured to return the next data from the cache buffer to the host in response to receiving back the next read request from the host. The electronic device of claim 1 , wherein updating the metadata comprises writing the next data storage address to the non-volatile storage medium utilizing a read-modify-write command. The method of claim 1 , wherein: the control circuit is further configured to classify the read requests from one or more hosts based on an application identifier corresponding to each of the read requests;
and updating the metadata corresponding to the read request in the non-volatile storage medium with the next data storage address responds only to both a read request corresponding to the same application identifier and a next read request. 10. The storage according to claim 9, wherein the control circuit is further configured to execute a respective tracker process corresponding to each different application identifier to update the metadata corresponding to read requests corresponding to each application identifier. device. The electronic device of claim 1 , wherein the apparatus is a data storage device. As a method,
receiving a read request comprising a corresponding data storage address from a host and placing the read request in a read queue;
receiving a next read request comprising a corresponding next data storage address from the host and placing the next read request in the read queue; and
updating metadata corresponding to the read request in a non-volatile storage medium with a logical address corresponding to the next data storage address from the next read request;
a method comprising 13. The method of claim 12, wherein in response to receiving the read request back from the host,
reading the next data storage address from the metadata corresponding to the read request from the non-volatile storage medium; and
fetching the next data from the next data storage address prior to processing a subsequent read request;
A method further comprising: 13. The method of claim 12, further comprising fetching next data from the next data storage address in response to the occurrence of an idle processing time corresponding to the read queue. 13. The method of claim 12, further comprising placing next data from the next data storage address into a cache buffer. 16. The method of claim 15, further comprising returning the next data from the cache buffer to the host in response to again receiving the next read request from the host. 13. The method of claim 12, wherein updating the metadata comprises utilizing a read-modify-write command to write a logical address corresponding to the next data storage address to the non-volatile storage. 13. The method of claim 12, further comprising: classifying the read requests from one or more hosts based on an application identifier corresponding to each of the read requests;
and updating the metadata corresponding to the read request is performed only in response to both a read request corresponding to the same application identifier and a next read request. 19. The method of claim 18, further comprising executing a respective tracker process corresponding to each different application identifier to update the metadata corresponding to read requests corresponding to each application identifier. A computing system comprising:
means for receiving a read request comprising a corresponding data storage address from a host and placing the read request in a read queue;
means for receiving a next read request comprising a corresponding next data storage address from the host and placing the next read request in the read queue;
means for updating metadata corresponding to the read request in a non-volatile storage medium with the next data storage address from the next read request;
in response to receiving the read request back from the host,
read the next data storage address from the metadata corresponding to the read request from the non-volatile storage medium;
means for fetching the next data from the next data storage address prior to processing a subsequent read request
A computing system comprising:

Images