Determining a criterion for movement of data from a primary cache to a secondary cache

A new segment of data is copied to a volatile, primary cache based on a host data read access request. The primary cache mirrors a first portion of a non-volatile main storage criterion is determined for movement of data from the primary cache to a non-volatile, secondary cache that mirrors a second portion of the main storage. The criterion gives higher priority to segments having addresses not yet selected for reading by the host. In response to the new segment of data being copied to the primary cache, a selected segment of data is copied from the primary cache to the secondary cache in response to the selected segment satisfying the criterion.

CROSS-REFERENCE TO RELATED APPLICATIONS

U.S. patent application Ser. Nos. 13/542,990 and 13/543,036 are hereby incorporated by reference.

SUMMARY

The present disclosure is related to systems and methods that facilitate determining a criterion for movement of data from a primary cache to a secondary cache. In one embodiment, a new segment of data is copied to a volatile, primary cache based on a host data read access request. The primary cache mirrors a first portion of a non-volatile main storage criterion is determined for movement of data from the primary cache to a non-volatile, secondary cache that mirrors a second portion of the main storage. The criterion gives higher priority to segments having addresses not yet selected for reading by the host. In response to the new segment of data being copied to the primary cache, a selected segment of data is copied from the primary cache to the secondary cache in response to the selected segment satisfying the criterion.

DETAILED DESCRIPTION

The present disclosure is generally related to data storage devices, such as solid-state, hybrid, hard disk drives (HDDs). Generally, a hybrid HDD utilizes a combination of non-volatile, solid-state memory (e.g., flash memory) and conventional HDD media (e.g., magnetic disks) to provide performance approaching that of a solid-state drive (SSD), yet without the costs commonly associated with SSDs. In the present disclosure, a hybrid drive architecture is described that uses an SSD as a non-volatile cache for HDD media, and is sometimes referred to as an HDD/SSD hybrid storage device. However, it will be appreciated that the concepts described herein may be applicable to any data storage device that utilizes similar caching mechanisms.

An HDD/SSD hybrid drive combines features and technologies of conventional HDDs and SSDs. A hybrid drive may include a main storage (e.g., one or more rotating magnetic disks), a volatile primary cache, and a non-volatile secondary cache. The primary cache may use a relatively small amount of volatile random access memory (RAM), while the secondary cache may uses a relatively large amount of non-volatile solid state memory that is kept coherent with the main storage. The description below is directed to, among other things, a scheme for selecting data to be moved into the secondary cache. The scheme may be tailored to optimize performance under certain environments, such as enterprise storage or other uses where the drive may be highly/fully utilized.

In reference now toFIG. 1, a block diagram illustrates an apparatus102that includes caching features according to an example embodiment. The apparatus102includes main storage104that, in this example, includes one or more magnetic disks106as storage media. The disks106store data as magnetic patterns that are read by sensors (e.g., magnetic read/write sensors) mounted on a pivoting arm assembly108. A controller110is coupled to the arm assembly and controls movement of the arm via an actuator (not shown). The controller110sends and receives signals (e.g., via encoder and decoder circuits, not shown) to/from one or more read/write heads on the arms, the signals ultimately being converted to data stored on the main storage104. While this embodiment shows rotating magnetic disks106, the concepts described below may be applicable to alternate non-volatile main storage media, including optical or solid-state media.

The apparatus102includes a host interface112that communicatively couples the apparatus102to a host114. The host interface112at least provides a mechanism that allows the host114to store and retrieve information to/from the main storage104. The host interface112may utilize standard communication interfaces and protocols, such as SATA, SCSI, eSATA, SAS, USB, etc. The host interface112may provide both a standard means of communication between the apparatus102and host114, as well as abstracting operations of the controller110and main storage104. For example, the host114may access data by way of logical block addresses (LBAs) that are mapped to a different physical addressing scheme used internally by the apparatus102, e.g., a physical address scheme based on cylinders, heads, and sectors of the disks106.

The controller110may utilize various internal adaptations of the apparatus102to improve performance or otherwise provide efficient operation with the host114. For example, the apparatus102may include a volatile random-access memory (RAM)116, such as Dynamic-RAM (DRAM). The apparatus102may also include non-volatile RAM (NVRAM)118, such as NAND flash memory. These memory devices116,118may have a number of different uses, such as acting as temporary and permanent stores for data needed internally by the controller110during operation. The memory devices116,118may also be used for caching host data, as represented by respective caches120,122.

Data retrieved from main storage104can be held in one or more caches120,122to improve throughput. The caches120,122have faster access and retrieval times than the main storage104, although generally with less storage capacity. While there is some processing and data transfer overhead in using the one or more caches120,122, the faster media used by the cache can improve data access performance of the apparatus102under many conditions. Generally, data access may include at least host read and/or write requests, and the caches120,122may be configured to mirror equivalent data (e.g., referenced by the same logical block address) in portions of the main storage104.

In the illustrated configuration, the non-volatile cache122is configured as a secondary cache, being faster and smaller than the main storage104. The volatile cache120is a primary cache, being faster and smaller than the secondary, non-volatile cache122. Generally, the terms “primary” and “secondary” refer generally to hierarchy of time and/or priority relative to commands received via the host interface112. For example, current read/write requests from the host114may be processed first via the primary cache120(e.g., identified by the data's logical block address). This enables host commands to complete quickly should the requested data be stored in the primary cache120. If there is a miss in the primary cache120, the requested data may be searched for in the secondary cache122. If not found in either, requested data may be processed via the main storage104.

While the secondary cache122is described herein as non-volatile, the concepts may be equally applicable to a secondary cache that uses volatile memory. For example, non-volatile memory may be chosen as secondary cache media for cost considerations and not for data retention upon loss of power. In such a case, the system may be configured so that no state information is stored for recovery of the secondary cache should power be unexpectedly be lost. In such a configuration, it may be possible to substitute volatile memory in place of the non-volatile memory without loss of functionality, because the data retention capability of the non-volatile memory is not being used.

Some of the data stored in the primary cache120may either be copied or moved to the secondary cache122as new requests come in. The copying/movement from primary cache120to secondary cache122may also occur in response to other events, e.g., a background scan. Both copying and moving involve placing a copy of data associated with an LBA range in the secondary cache, and moving may further involve freeing up some the LBA range in the primary cache for other uses, e.g., storing newly cached data.

The secondary cache122in this example may optionally be read-only, in that only data marked for read operations by the host114are placed in the secondary, non-volatile cache122. In such a configuration, data marked for writing (write data) are sent directly to the main storage104, either directly from the host interface112or via the primary, volatile cache120. In some applications and configurations (e.g., enterprise storage), it has been found that writing to NVRAM118instead of the main storage104may not provide sufficient performance improvements to justify the overhead needed to track and synchronize write operations between the secondary cache122and main storage104.

The apparatus102includes functional modules124that perform various functions related to moving data in and out of the caches120,122. These modules124may include any combination of custom logic circuitry, general-purpose processors/controllers, firmware, and software. The modules124include an analysis controller module126configured to determine one or more criteria associated with the host operations. The criteria may be at least indicative of costs associated with moving data in and out of the primary and/or secondary caches120,122, and importance of the data in regards to caching in the primary and/or secondary caches120,122.

The analysis controller module126may track history of address ranges, and may assign an importance metric to the address ranges that influence whether the ranges should be targeted for the primary cache120and/or secondary cache122. Examples of determining cache importance metrics are described in U.S. patent application Ser. No. 13/542,990 that has been incorporated by reference.

The importance metrics may also be used to determine the importance of both newly requested data and currently cached blocks of data. Metrics of cached data can be compared to the same metric applied to a block of unrequested, speculative read data that is being considered for caching. If the importance metric of the speculative data meets or exceeds that of the cached data, the speculative data can be loaded from the main storage104and cached, which may cause eviction of the currently cached data from at least one of the caches120,122or movement therebetween.

The analysis controller module126may also define optimum ranges of speculative data to be pulled from the main storage104into at least one of the caches120,122for purposes of fulfilling host read requests. Due to certain conditions (e.g., a latency incurred in later retrieving the data) it may be beneficial to speculatively read data that has not been requested but is proximate to host requested data on the disk. Examples of how speculative cache ranges may be determined are described in U.S. patent application Ser. No. 13/543,036, which has been incorporated by reference.

The size of the speculative range may depend on characteristics of the caches120,122and expected use conditions of the storage apparatus102. For example, it may be more efficient to place speculative data in the caches120,122that fills out an entire line of the secondary cache122. The speculative data may include data that is before the requested block (read look-behind) or after the host-requested data (read look-ahead). The speculative data may be placed in one or both caches120,122when fulfilling the immediate request, in the anticipation that the unrequested, speculative data may be the subject of a later request.

One or more cache monitors128may track operations affecting both the primary and secondary caches120,122, and cause cache controller module130(discussed further below) to perform certain actions to cached data based on system policies. Generally, the cache monitor128may track conditions used by the cache controller module130to evict data from one of the caches120,122or move data between caches120,122. Where the caches120,122are configured to be independent, e.g., not storing the same mirrored data of the main storage104, then moving data may involve copying data associated with an LBA range to the one cache and removing data of the LBA range from the other cache. There may be a single cache monitor128that monitors both primary and secondary caches120,122, or the functionality may be separately provided individual monitors associated with each of the caches120,122.

The cache controller module130is configured to cause data from the main storage104to be copied to the volatile cache120and/or non-volatile cache122. The cache controller130may control both primary and secondary caches120,122, or the functionality may be separately provided by individual controller modules associated with each cache120,122. The cache controller module130may be coupled to any combination of the cache monitor128, main storage104, controller110, host interface112, and caches120,122to cause transfers of data to the caches120,122. Any combination of the criteria and speculative read metadata can be stored in a database132. The database132may be coupled to any of the modules124, as well as being coupled to other components of the device102.

In reference now toFIG. 2, a block diagram illustrates an example of cache monitoring and control using various modules shown inFIG. 1. A host command processor202processes commands received via a host interface (e.g., host interface112inFIG. 1). The command processor202may queue, de-queue, sort, prioritize, and otherwise process commands that cause data to be written to and read from a storage device. Example command204is a host request for data, at starting address LBA1 and length=SIZE. This command204is first directed to the cache controller130, which will perform a lookup206in the primary cache120and, if needed, the secondary cache122. This may be performed using a single lookup206, or may involve a second lookup request (not shown) directed to the secondary cache122.

In this example, it may be assumed that the lookup206results in a cache miss in both the primary cache120and the secondary cache122. In response to the cache miss, the data corresponding to LBA1 is retrieved208from the main storage104and placed in the primary cache120at location210. The data is also returned211,212to the host command processor202for communication to the host. While path211indicates the data is read from location210of the primary cache120, it may be returned directly to the controller130from the main storage104before, during or after being placed in the cache120. Subsequent requests for LBA1 will return211,212the data directly from the primary cache120, until such time that the data is evicted.

In order to make room for addition208of the data to location210of the primary cache120, a corresponding amount of data from another cache location213may need to be evicted216from the primary cache120The selection of the location213for eviction is based on data maintained by a cache monitor128A of the primary cache120. It should be noted that the policy for eviction from the primary cache120may be separate and independent from the policy for copying data from the primary cache120to the secondary cache122. For example, although data being copied to the primary cache120may trigger copying of data from primary to secondary caches120,122, this is not necessarily done to free up space in the primary cache. This event may be a convenient trigger to evaluate data for the secondary cache, and may also be in response to other conditions discussed below, such as high spatial locality of host read history.

In this example, the primary cache monitor128A maintains sorted lists220of metadata related to priority of segments within the primary cache120. In this disclosure, the term “list” is used generically, and may be include using any data collection structure known in the art, e.g., array, linked list, set, map, binary tree, etc. Each cache segment identified in the cache priority lists220may correspond to a fixed-size data unit of the cache120(e.g., integer number of cache lines) or may be variable sized data units (e.g., corresponding to a contiguous ranges of LBAs, where the range of each segment may be different sizes). For purposes of this illustration, each block of data in the primary cache120corresponds to a variable length segment, a segment generally referring to a range of LBAs that are acted on together (e.g., contiguous range).

The primary cache monitor128A may use the lists220as part of a multi-level priority scheme. One level of priority is based on the usage type of the data (e.g., write, read, promoted). Another level of priority is based on the order of access to the data (e.g., least recently used, most recently used). The result of this assignment of priority is the set of lists220, one list for each usage type, where each list is sorted from most recently used (MRU) to least recently used (LRU). Finding an eviction candidate involves first locating a non-empty list with the lowest retention priority, and then selecting the LRU element from that list.

The usage-type lists can be used to efficiently filter candidate data based on read usage. For example, a usage type of “promoted” is given lower retention priority in the primary cache120. Usage types of “read” and “write” have the next higher orders of priority, in that order. When a read segment (e.g., segment214) is copied218to cluster224of the secondary cache122, the primary cache entry in lists220related to segment214may be lowered in retention priority by moving it from a “read” list to a “promoted” list, as indicated by arrow222. This may only be done if all of the cluster-aligned data from the entry214has been copied to the secondary cache122. Otherwise, the entry remains on the “read” list of the primary cache120but may be marked “do not promote” to prevent repeated selection.

Besides usage type, the cache monitor128A may maintain other attributes of primary cache entries related to promotion of primary cache segments to the secondary cache122. This metadata may be stored in one or more of the lists220. These attributes may include, “reserved for promotion,” “promoted to flash cache,” “prohibit promotion reservation,” etc. These attributes may be used in determining whether to evict a segment from primary cache120, as well as controlling whether the segment is copied to the secondary cache122.

The analysis controller126may be used to determine a cache importance metric of segments such as described in U.S. patent application Ser. No. 13/542,990. This metric may take on a value within a numerical range (e.g., 1-10) and the metric may be adjusted over time. For example, some data may have this importance metric determined at the time the data was requested, e.g., in cases where the metric triggered the obtaining of speculative data from the primary storage along with the requested data. In other cases, this metric may be determined later, e.g., when determining whether to copy non-speculative data to the secondary cache.

The cache importance metric, along with other cache metadata noted above, may govern the selection of a segment such as214for copying to the secondary cache. For example, as long as a primary cache segment is marked with “promoted to flash cache” or “prohibit promotion reservation” attributes, it will not be considered for copying to the secondary cache. Also, a logical address range of the primary cache segments may govern whether or not they are eligible for copying to the secondary cache. For example, segments may have to satisfy size and alignment conditions of the secondary cache in order for its LBA range to be eligible for copying.

The copying214of data in segment214to the secondary cache122may trigger an eviction228of a cluster of data from the secondary cache122. For purposes of this discussion, the term “cluster” will be used to annotate ranges of data within the secondary cache122. Similar to a segment of the primary cache120, a cluster generally refers to a range of LBAs within the secondary cache122that are acted on together. As with the primary cache120, it is assumed in this example that the secondary cache122has at least one cluster224ready to receive the data, although another cluster226may need to be evicted228, either immediately or some time thereafter, in order to facilitate insertion into cluster224. A secondary cache monitor128B may maintain a separate list230for purposes of determining priorities of the secondary cache122.

The secondary cache priority list230may maintain a set of metrics targeted to clusters within the secondary cache122. These metrics may at least include the last access time, and may be maintained in response to events such recent host interface activity. Elements of the list230may make reference to fixed or variable sized clusters of the secondary cache122, and a single insertion may include multiple evictions228from the secondary cache122. The secondary cache monitor128B may also access cache importance metrics data from analysis controller126and/or database132, e.g., using one or more LBAs as an index.

It should be noted that in this example, the secondary cache122is assumed to be read-only, and so eviction228is shown as the only option. However, if the secondary cache122is configured to store both read and write data, then another option (not shown) may be to sync the data with the main storage104before clearing the cluster224for other uses. Similarly, if the primary cache120stores read/write data, then eviction216may also involve synchronizing the cached data with the main storage104.

In reference now toFIG. 3, a block diagram illustrates an example of how segments are selected and retained for primary cache120. The primary cache120distinguishes read data from write data. Read data may be distinguished from write data by assigning a cache use identifier to primary cache segments. For example, segments302-306are identified as read data that are available for movement to the secondary cache122. In this example, each block within the segments302-306represents a unit of data, e.g., n-LBAs, where n is the same for all segments302-306. The blocks with the segments302-306are also linked together, e.g., a contiguous range of LBAs within each segment302-306. The primary cache120may also have write data, and it is assumed in this example that the secondary cache is populated only with read data from segments in the primary cache.

The process of searching for new read data to copy into secondary cache may be initiated when new valid read data is added to the primary cache120. This search may also be dependent of the host read history spatial locality being high, which can be determined via the analysis controller module126and/or database132. Generally, spatial locality refers to grouping of a relatively large number of requests over a relatively small range of LBAs and over a particular time range. High spatial locality of requests may be indicative that data in or near that range may be read or re-read at some point in the future. The likelihood of some of the data being requested near-term may not be high enough to justify storage in the primary cache120, but might be sufficient to move the data to the larger secondary cache122.

A retention priority is used to guide the selection of segments302-306that have eligible data for the secondary cache122. The retention priority of the segments302-306in the primary cache will be lowered when all possible data from that segment302-306have been copied into secondary cache. For example, segment303is shown having all data copied to segment313in the secondary cache122, and so segment303will have a low (or zero) retention priority. In such a case, a reference to the segment303may be maintained in a sorted list, and a low retention priority relative to other segments causes segment303to be at the top of the list for removal.

Read data that is not yet copied to the secondary cache122is given higher retention priority, while read data that has been copied to secondary cache is given lower retention priority. A primary cache segment may include some portions that have been copied, and others that have not been. Other retention priority relates to the last access time of LBAs within the segment.

One way to manage retention priority is to store a reference to eligible segments on one or more lists308-309. For example, the lists308-309may have a collection of elements each referencing segments302-306. Additional data may also be stored with the list elements, such as access time, cache priority, etc. Lists308and309are ordered from least-recently-used (LRU) to most-recently-used (MRU), based on cache use of at least part of the segment. These lists308-309may be combined into a single list (e.g., sorted on primary and secondary fields, use a combined sorting value), or be used to collectively to define a retention priority. When an eviction is necessary, the lists308-309may be consulted in order of retention priority, the lowest priority elements being at the top of the lists308-309.

The elements placed in the lists308-309may be limited to read segments (e.g., using cache use identifier noted above) that are not yet copied to the secondary cache122. This can provide boundaries on the search for candidate segments to move to the secondary cache122. In order to qualify for selection, the segment may need to satisfy any or all of the following criteria: (a) not already be reserved for copying to secondary cache (b) not prohibited from being copied to secondary cache; (c) not already copied to secondary cache, (d) overlap with the range of LBAs that may be copied into secondary cache, and (e) contain at least one full cluster within its LBA range (for implementations in which the secondary cache is organized into fixed sized clusters); (f) contain data supplied by a read look-ahead or read look-behind operation, or have a maximum cache importance that is greater than or equal to that of any LBA predicted to be evicted from the secondary cache if qualifying segment data were copied into secondary cache. The last criteria relates to additional speculative reading that may have been performed expressly for the purpose of promoting to secondary cache. In that case, a cache importance eviction test may have already been performed at the time the speculative reading was being determined, and the data would already have been marked “promotion recommended”.

Criterion (a) above refers to a segment being reserved but not yet having been copied to the secondary cache122. For example, segments already included in the lists308-309that have not yet been copied over would not need to be further considered for addition to the list(s). If an when such segment is copied to the secondary cache122, it would be removed from list(s)308-309, and while still resident in the secondary cache122, would not later be added in to the list(s)308-309due to criteria (c).

Criterion (b) refers to situations where the number of LBAs to copy into the secondary cache122from a single segment has a maximum value that may be smaller than some segments. When that is the case, the range of data to copy is selected in a way that gives priority to the lowest non-requested LBAs in the segment. The lowest non-requested LBA is maintained within the segment by the primary cache. When such a segment is returned to primary cache, it remains on the list of read segments (rather than being moved to the list of segments already copied to secondary cache) and is marked as prohibited from copying to secondary cache.

For example, a high-water mark may be maintained of the last requested LBA within each read segment of the primary cache120. When a limit is imposed on the amount of data that may be copied into secondary cache from a single segment, the data selected from that segment is chosen to give higher priority to non-requested LBAs over requested LBAs, and highest priority to the lowest non-requested LBAs. Using segment304as an example, LBAs from the beginning (leftmost end) of the segment304up to and including block304A have been requested. Further, as shown with cache line312in the secondary cache, the cluster size of the secondary cache122is six blocks. As a result, region304B is given priority for copying into the secondary cache122over any other region of segment304. If the segment304extended beyond the end of region304B (e.g., there was another range of LBAs to the right of304B) then304B would be given priority over that other range.

There may be a maximum LBA range that is permitted to be copied into secondary cache. Criterion (d) enforces that some part of the segment is within the allowable range. The LBA range to be copied from the segment may be truncated if necessary.

Criterion (e) relates to selecting data for the secondary cache122that satisfies an address criterion of the secondary cache. For example, eligible segments may include those that satisfy a minimum size, e.g., fully filling out one or more cache lines. Also, a secondary cache cluster may define both alignment and size constraints of the LBA ranges that may be copied into secondary cache122, assuming that it is organized into fixed size cache lines. For example, if the cluster size is 30 LBAs, then any LBA range to be copied into secondary cache should have a starting LBA and number of LBAs that are each multiples of 30. Using LBASand LBAFas respective start and final addresses of the segment, the addresses in this example may have to satisfy the following (where “%” represents the integer modulus operator): LBAS% 30=0 and (LBAF−LBAS+1) % 30=0. After selecting a segment, its LBA range may further be adjusted to comply with the cluster alignment/size requirements. For example, the start LBA is rounded up to the nearest cluster boundary if not already aligned, and the end LBA is rounded down to the nearest cluster boundary −1, if not already so aligned. If that is not possible, then the segment may be disqualified.

Criterion (f) relates to an algorithm for filling the primary cache120with speculative data, as discussed in U.S. patent application Ser. No. 13/543,036. Speculative data generally refers to data that is adjacent to data of an existing host access operation (e.g., sectors preceding and following read-requested sectors) that are not currently requested but are read anyway. By loading speculative data into the cache, latency of future requests for speculatively cached data can be greatly reduced.

When determining candidates for copying to the secondary cache, a secondary cache eviction test may be performed if it was not already performed during the setup of speculative reading. The test involves comparing the maximum cache importance of the next ‘n’ clusters to be evicted from the secondary cache122to the maximum cache importance of the candidate data to be added. The ‘n’ value is the maximum size of data that can be added to secondary cache122at a time, but may also be matched to the size of the candidate data to be added. Because the secondary cache eviction test may already be performed during set up of speculative reading, it will be marked as “promotion recommended.” In such a case, there is no need to do an eviction test again when evaluating that data for promotion into the secondary cache

The controller for the caches120,122should be able to service cache hits and invalidations on a primary cache segment while copying that segment's data into the secondary cache122. Once a segment is selected for copy, it may be reserved for the duration of the copy operation into the secondary cache122. During this time, the segment can be used to serve cache hits from the primary cache120and won't be evicted. If a host issues an invalidate request for that segment, the segment will be disabled for further cache hits, but will otherwise remain intact until the copy into secondary cache completes, at which time the remaining processing for the invalidation can be performed.

A qualifying segment that successfully copies all of its cluster-aligned data into secondary cache122will be removed from the list of read segments (e.g., lists308,309) and may be added to a list (not shown) of segments already copied to secondary cache122. Otherwise, the segment remains on the list(s)308,309of available read segments. If criteria (d), (e), or (f) above are not met, the segment is not eligible to be copied to the secondary cache, although at some later time it might be, e.g., if secondary cache priorities are changed.

In reference now toFIG. 4, a flowchart illustrates a procedure for selecting primary cache segments available for copying to a secondary cache according to an example embodiment. The procedure iterates through all the currently used segments as indicated by loop entry point402. Alternatively, the loop402may iterate just through eligible segments with a “read” usage type, which excludes data of “promoted” or “write” usage types. Decision blocks404-408represent criteria (a)-(e) described above. Note that decision block408is indicated as optional, based on whether the system is designed to ensure data is selected to fully fill out secondary cache lines. Decision blocks409-410relate to criterion (f) above.

Note that if loop402only iterates through eligible “read” usage type segments, then the check at405may not be needed. However, the check at block406may still be used. For example, in some cases “write” data is characterized during idle time, and/or “write” data can be re-characterized as read data via segment merging or other events. In such a case, a segment marked as a “read” usage may still have unverified write data. In such a case, the segment would be disqualified for copying to secondary cache.

If the respective decision blocks404-410have the indicated outcomes (“yes” or “no”, as appropriate), the selected segment is added412to a list of segments eligible for copying to the secondary cache, otherwise the selected segment is not added414. This repeats for each segment until exiting the loop at416. It should be noted that the order of decision blocks404-410is shown for purposes of example, and can be arranged in any order. For example, the decision blocks404-410that most often leads to finishing loop via414would be placed first to reduce processing time in the loop402. After the procedure is completed, the list is updated with primary segments eligible for copy to the secondary cache. This list may be sorted, e.g., based on last access time, primary cache priority, etc. For example, by starting a search with the lowest priority entries and proceeding toward the higher priority entries lowers the probability of losing eligible data to eviction before it gets copied to secondary cache. Segments corresponding to elements at the end of the list (lowest primary cache priority) will be copied to the secondary cache under the appropriate conditions.

In reference now toFIG. 5A, a flowchart illustrates a procedure according to an example embodiment. The process involves causing502a block of data to be copied in a volatile, primary cache based on a host data read access request. The primary cache mirrors a first portion of a non-volatile main storage. The procedure further involves determining504a criterion for movement of data from the primary cache to a non-volatile, secondary cache that mirrors a second portion of the main storage. The criterion gives higher priority to blocks having addresses not yet selected for reading by the host. The criterion may also optionally give higher priority to the blocks having the longest elapsed time since last host access. The criterion may optionally prevent the movement of the data based on whether an address range of the blocks overlaps with a range of addresses already copied or reserved for copying to the secondary cache, and/or the data not satisfying a minimum size associated with a cache line of the secondary cache.

In response to the block of data being copied to the primary cache, a selected segment of data is moved506from the primary cache to the secondary cache and in response to the selected segment satisfying the criterion. Moving the selected segment of data from the primary cache to the secondary cache may cause a cluster of the secondary cache to be evicted. In such a case, determining the criterion may optionally involve determining whether the selected segment has an equal or higher priority than the evicted cluster. In another arrangement, the secondary cache may be used for storing read data only. In such a case, the criterion may optionally prevent the movement of the data based the segment containing write data.

In reference now toFIG. 5B, a flowchart illustrates a procedure according to another example embodiment. The procedure involves defining512a list that references segments of a primary cache eligible for moving to a secondary cache. The primary and secondary caches respectively mirroring first and second portions of a non-volatile main storage. The list may include any data structure that stores a collection of data objects, in this example a reference to segments of the primary cache.

Candidate segments from the primary cache are added514to the list in response to logical block address ranges of the candidate segments satisfying an address criterion of the secondary cache. The address criterion of the secondary cache may include a cache line size of the secondary cache. In such a case, the candidate segments satisfy the criterion if a size of the candidate segments is greater than or equal to the cache line size. The candidate range may also need to meet alignment requirements relating to the line size of the secondary cache. For example, the address criterion may also include an allowable starting logical block address of a cache line of the secondary cache. In that case, the candidate segments satisfy the criterion if a logical block address of the candidate segments satisfies the allowable starting logical block address. In an arrangement where the secondary cache stores read data only, the candidate segments may be added to the list further based on the candidate segments not including write data.

In optional block516, additional conditions may be used to add candidate segments from the primary cache. Those conditions may include candidate segments not including write data, not having already been copied or reserved for copying to the secondary cache, having addresses not yet selected for reading by the host, and/or having a secondary cache importance metric greater than an equivalent metric of a segment of the secondary cache that would be evicted in response to moving the candidate segments to the secondary cache.

In response to new data being added to the primary cache, at least one of the candidate segments is moved518to the secondary cache. In one arrangement, the list is optionally sorted based on a primary cache priority of the candidate segments. In response to this sorting, candidate segments having a lower cache priority are selected for moving to the secondary cache ahead of candidate segments with a higher cache priority.

The various embodiments described above may be implemented using circuitry and/or software modules that interact to provide particular results. One of skill in the computing arts can readily implement such described functionality, either at a modular level or as a whole, using knowledge generally known in the art. For example, the flowcharts illustrated herein may be used to create computer-readable instructions/code for execution by a processor. Such instructions may be stored on a computer-readable medium and transferred to the processor for execution as is known in the art. The structures and procedures shown above are only a representative example of embodiments that can be used to facilitate managing caching in data storage devices as described above.