Virtual cache window headers for long term access history

A method of virtual cache window headers for long term access history is disclosed. The method may include steps (A) to (C). Step (A) may receive a request at a circuit from a host to access an address in a memory. The circuit generally controls the memory and a cache. Step (B) may update the access history in a first of the headers in response to the request. The headers may divide an address space of the memory into a plurality of windows. Each window generally includes a plurality of subwindows. Each subwindow may be sized to match one of a plurality of cache lines in the cache. A first of the subwindows in a first of the windows may correspond to the address. Step (C) may copy data from the memory to the cache in response to the access history.

FIELD OF THE INVENTION

The present invention relates to data caches generally and, more particularly, to a method and/or apparatus for implementing virtual cache window headers for long term access history.

BACKGROUND OF THE INVENTION

Effective leveraging of solid state disk drives as a data cache is dependent on accurate detection and retention of frequently accessed data. A challenging aspect is to find the frequently accessed data by observing only a stream of host commands coming from an operating system to a controller of a redundant array of independent disks. Once detected, the data is loaded into the cache for higher performance on subsequent requests. However, if the data is infrequently accessed, cache space is wasted and performance negatively impacted because loading the infrequently access data into the cache represents additional operations.

It would be desirable to implement virtual cache window headers for long term access history.

SUMMARY OF THE INVENTION

The present invention generally concerns a method of virtual cache window headers for long term access history. The method may include steps (A) to (C). Step (A) may receive a request at a circuit from a host to access an address in a memory. The circuit generally controls the memory and a cache. Step (B) may update the access history in a first of the headers in response to the request. The headers may divide an address space of the memory into a plurality of windows. Each window generally includes a plurality of subwindows. Each subwindow may be sized to match one of a plurality of cache lines in the cache. A first of the subwindows in a first of the windows may correspond to the address. Step (C) may copy data from the memory to the cache in response to the access history.

The objects, features and advantages of the present invention include providing a method and/or apparatus for implementing virtual cache window headers for long term access history that may (i) trace cache access history, (ii) use cache header meta data to track input/output accesses beyond what is stored in the cache, (iii) provide a spatio-temporal historical record of all accesses to the storage underlying the cache, (iv) actively avoid loading unnecessary data in the cache, (v) allow for better cache efficiency and/or (vi) operate with large caches.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Some embodiments of the present invention generally facilitate tracking of large spaces of disk memory that may not actually be backed by a cache memory. The tracking may allow for low-overhead detection of hot (e.g., frequently accessed) data. The tracking may also mitigate penalties caused by loading infrequently accessed data into the cache memory. By allocating window headers that cover more memory space than exists in an actual physical cache memory, several advantages arise. For example, the tracking generally permits efficient detection of hot data from a stream of operating system accesses. The tracking may also help prevent pollution of the cache by non-hot data. The virtual cache headers generally allow for a very large space to be tracked (e.g., much larger that the amount of memory allocated for the cache) thereby facilitating (i) hotspot detection of isolated data areas not detectable in a simple least recently used (e.g., LRU) backed cache and (ii) mitigating a penalty of populating the cache when data is not hot.

Referring toFIG. 1, a block diagram of an apparatus100is shown in accordance with a preferred embodiment of the present invention. The apparatus (or circuit or device or integrated circuit)100may implement virtual cache window headers for long term access history. The apparatus100generally comprises one or more blocks (or circuits)102, a block (or circuit)104, a block (or circuit)106and one or more blocks (or circuits)108a-108g. In some embodiments, the circuit106may part of the circuit104. The circuit104generally comprises a block (or circuit)110, a block (or circuit)112and a block (or circuit)114. The circuits102-114may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

A memory signal (e.g., MEM) may be exchanged between the circuit102and the circuit104. A cache memory signal (e.g., CM) may be exchanged between the circuit104and the circuit106. The circuit104may exchange disk memory signals (e.g., DMa-Dmg) with the circuits108a-108g.

The circuit102may implement one or more host circuits. Each circuit102is generally operational to present access requests to the circuit104via the signal MEM. The access requests may include, but are not limited to, read accesses and write accesses. Each read access may include a memory address from which data is to be read. Each write access may include both data and a memory address at which the data is to be stored. The addresses may be in the form of logical block addresses (e.g., LBAs). Other addressing schemes may be implemented to meet the criteria of a particular application.

The circuit104may implement a redundant array of independent disks (e.g., RAID) controller circuit. The circuit104is generally operational to process the access requests received via the signal MEM to store and read data to and from a mass storage device (e.g., the circuits108a-108g). The circuit104may be configured to operate in a RAID 0, RAID 1, RAID 2, RAID 3, RAID 4, RAID 5, RAID 6, RAID 0+1, RAID 1+0 and/or RAID 5+1 configurations. The circuit104may also configure the mass storage to operate as one or more virtual disks (or virtual memories).

The circuit104may include cache operations using either an internal cache memory or the circuit106. The cache operations may include generating an access (or trace) history of all access requests received from the circuit102. One or more requests may be received by the circuit104from the from the circuit102to access an address in circuits108a-108g. The circuit104may update the access histories in corresponding window headers in response to the access requests. The circuit104may be configured to control the circuits108a-108gand the circuit106to copy data from the circuits108a-108gto the circuit106in response to the access histories. The window headers may divide an address space of the circuits108a-108ginto a plurality of windows. Each window generally comprises a plurality of subwindows. Each subwindow may be sized to match a cache line in the circuit106. Each subwindow may corresponds to one or more of the addresses.

The circuit106may implement a cache memory circuit. The circuit106is generally operational to buffer data received from the circuit104via the signal CM. The buffered data may be arranged as multiple cache lines. The data in the cache lines may be transferred to the circuit104via the signal CM. In some embodiments, the circuit106may be implemented as a sold state drive. Common sizes of a solid state drive may range from 1 to 2 terabytes. In other embodiments, the circuit106may be implemented as a double data rate (e.g., DDR) memory circuit. Common sizes of a DDR memory may range from 1 to 64 gigabytes.

Each circuit108a-108gmay implement a hard disk drive (e.g., HDD) circuit. The circuits108a-108gare generally operational to store data for the circuit102. The data may be received from the circuit104and sent to the circuit104via the respective signals DMa-DMg. Collectively, the circuits108a-108gmay form a mass storage device. A common size of the mass storage device may range from a several terabytes to a few petabytes. The mass storage device may be arranged as one or more virtual devices (or virtual disks), as see from the circuit102. In some embodiments, the circuits108a-108gmay be implemented as magnetic disk drives. Other memory technologies may be implemented in the circuits108a-108gto meet the criteria of a particular application.

The circuit110may implement a dynamic random access memory (e.g., DRAM) circuit. The circuit110may be operational to store the window headers (e.g., access histories) generated by the circuit104. In some embodiments, the circuit110may also implement a cache memory used to cache data in transit to and from the circuits108a-108g.

The circuit112may implement a replacement module. The circuit112is generally operational to determine (i) when and which sets of data should be stored in the cache (e.g., the circuit106or the circuit110) and (ii) when and which sets of data should be removed from in the cache. A store/remove (replacement) decision implemented by the circuit112may utilize the access history generated by the circuit104. Generally, hot (e.g., frequently accessed) data identified by the access history may be populated in the cache. Infrequently access data may be kept out of the cache to avoid performance penalties incurred by moving the infrequent data into the cache. Standard replacement decision techniques generally include, but are not limited to, a least recently used replacement policy, a not frequently used replacement policy and an aging replacement policy. Other replacement decision policies may be implemented to meet the criteria of a particular application.

The circuit114may implement a history module. The circuit114is generally operational to create the access histories from the access requests received from the circuit102. The circuit114may generate the access histories by mapping the address space of the circuits108a-108ginto a fixed size granularity called windows. Each window generally tracks the granularity worth of host space accesses. An additional granularity underneath each window may be referred to as a subwindow (or subwindow extent). Each subwindow may be associated with one or more addresses (e.g., LBAs). Each subwindow may also represent (or match) a cache line granularity. At different times, the various windows and subwindows may or may not be associated with data in the actual cache. Windows without any associated cache data may be referred to as virtual window headers.

Many more window headers may be allocated across the address space of the circuits108a-108gthan exists in the physical cache (e.g., the DDR cache or the SSD cache). Covering the address space of the circuits108a-108ggenerally allows for large regions of host accesses to be tracked even though the cache is not involved in many of the host accesses. The access histories generally provide detailed information about host access patterns.

Referring toFIG. 2, a diagram of an example implementation of a window header120is shown. The window header120may be generated by the circuit114and stored in the circuit110. Each window header120generally comprises a parameter (or field)122, a parameter (or field)124, a parameter (or field)126, a parameter (or field)128and multiple parameters (or fields)130a-130n. Each window header120may have a fixed size that spans a fixed amount (e.g., 1 megabyte of data or 2048 LEAS at 512 bytes/block) of the address space of the circuits108a-108g. Other sizes of the window headers120may be implemented to meet the criteria of a particular application. A size of each window header120may be a power of 2 such that the headers are easily shifted and/or aligned in memory (e.g., circuit110). Adjoining windows may not overlap.

The field122may implement a window identity field. The field122may provide a unique identifier of the corresponding window header120to allow the circuit114to distinguish among the various window headers120.

The field124may implement a range field. The field124generally defines a range of addresses (e.g., LBAs) covered by the corresponding window header120.

The field126may implement a start address field. The field126generally establishes a starting address (e.g., a particular LBA) of the corresponding window header120.

The field128may implement a virtual disk number field. The field128may store an identification number of a virtual disk for which the window is established.

Each field130a-130nmay implement a subwindow field. Each field130a-130nmay store a corresponding count number field132a-132nand zero to several elements134a-134b. Each field130a-130nmay represent a portion of the address space of the circuits108a-108g. Adjoining subwindows may not overlap. Each field130a-130nmay also match a cache line in terms of size. For example, if a cache line may hold data for N addresses (e.g., 32 LBAs), each field130a-130nmay cover an address space of the N addresses.

Each field132a-132nmay implement a count field. Each field132a-132nmay store a count of the number of access requests made by the circuit102into the address range covered by the corresponding field (subwindow)130a-130n. In some embodiments, the count may be a running count of all access requests. In other embodiments, the count may be a limited count of the number of access requests made within a given time frame (e.g., 0.1 seconds, 1 second, 1 minute, etc.).

Each element134a-134bmay implement an access element (or indicator). For each access request received by the circuit104, an element134a-134bmay be generated in the appropriate field130a-130nof the subwindow corresponding to the memory address received in the access request. When created, each element134a-134bmay include a type of the access request (e.g., a read access or a write access) and a time that the access request was received by the circuit104. Every host access request may generate a cache window header access element134a-134bregardless of whether or not the cache is populated for the access request (e.g., independent of a cache hit or a cache miss). The various fields130a-130nin each window header120may have different numbers of the elements134a-134bin response to the number and locations (e.g., addresses) of the access requests.

Referring toFIG. 3, a block diagram of example multiple window headers140a-140crelative to multiple cache lines is shown. The block diagram generally illustrates relationships between a window size granularity and a cache granularity. Each window header140a-140cmay be representative of the window header120. The example window header140agenerally illustrates a full header. All of the subwindow fields130a-130nin the window header140amay correspond to addresses that are currently buffered in respective cache lines142a-142kof the cache. Therefore, any access request initiated by the circuit102into the address space covered by the window header140amay result in a cache hit.

The example window header140bgenerally illustrates an empty header. None of the subwindow fields130a-130nin the window header140bmay correspond to an address that is currently buffered in the cache. The window header140bis not backed by the physical cache so the window header140bmay be referred to as a virtual window header. All access requests initiated by the circuit102into the address space covered by the virtual window header140bmay result in a cache miss.

The example window header140cgenerally illustrates a partially full header. Some subwindow fields130a-130n(e.g., a single subwindow in the example) may correspond to an address that is currently buffered in the cache line142m. The other subwindow fields130a-130nmay correspond to addresses not currently buffered in the cache. As such, some access requests initiated by the circuit102into the window140cmay result in a cache hit and other access requests may result in a cache miss.

Referring toFIG. 4, a flow diagram of an example method150for updating the access history is shown. The method (or process)150may be implemented by the circuit104. The method150generally comprises a step (or state)152, a step (or state)154, a step (or state)156, a step (or state)158, a step (or state)160, a step (or state)162, a step (or state)164, a step (or state)166, a step (or state)168and a step (or state)170. The steps152-170may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step152, the circuit114may create multiple window headers that divide the address space of the circuits108a-108gor the resulting virtual disks. Each window header generally represents a portion of the address space. In some embodiments, the entire address space may be covered by the window headers. In other embodiments, a subset of the address space may be covered by the window headers at any given time.

In the step154, the circuit104may receive an access request from the circuit102. The access request may be presented to the circuit114to determine which window header and which subwindow is associated with the memory address (e.g., LBA) received in the access request per the step156. In situations where the circuit102is implemented as two or more hosts, an identify of the sending host may be disregarded for purposes of the tracking information. If a new window is created for tracking the access request, an oldest virtual window header (e.g., the LRU virtual window header) may be examined and reused if the oldest virtual window header is not determined to be useful anymore.

The tracking information (e.g., the count number) in the subwindow associated with the received memory address may be updated in the step158by the circuit114. Updating the tracking information may also include creating a new element in the associated subwindow to record the access request in the step160. The element may indicate the type of access request and the time at which the access request was received.

In the step162, the circuit114may determine if one or more older elements should be purged from the associated subwindow and/or window header. A variety of techniques may be used to determine when to purge and when not to purge an old element. For example, any element created more than a set amount of time before the current time may be considered stale and thus should be removed. In another example, if the newly added element fills the capacity of the subwindow, the oldest element may be removed (e.g., first in first out). Other purge techniques may be implemented to meet the criteria of a particular application. Once the older elements have been removed in the step164, the tracking information (e.g., count number) of the subwindow may be updated by the circuit114in the step166. The method150may continue with the step168.

If no elements should be removed, or purging of elements is not implemented by a particular application, the circuit114may store the updated access (trace) history in the circuit110per the step168. The circuit114may signal the circuit112in the step170that the updated access history has been posted. Once the circuit114has signaled to the circuit112, the method150may end and wait for the next access request from the circuit102.

Referring toFIG. 5, a flow diagram of an example method180for updating the cache is shown. The method (or process)180may be implemented by the circuit104. The method180generally comprises a step (or state)182, a step (or state)184, a step (or state)186, a step (or state)188, a step (or state)190and a step (or state)192. The steps182-192may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step182, the circuit112may receive the signal from the circuit114indicating that the updated access history is available in the circuit110. The circuit112may read the access history and the received access request in the step184. In the step186, the circuit112may determine if one or more cache lines should be populated from the circuits108a-108gin response to the access request. The determination may be made, at least in part, based on the tracking information available in the corresponding window header and subwindow. For example, if the tracking information shows that a recent number of access requests to the corresponding subwindow exceeds a threshold count, a flag may be raised. The replacement policy implemented by the circuit112may thus conclude that the cache should be populated due to the access request and the access history. Other replacement policies may be implemented to meet the criteria of the particular application.

Where the replacement policy decides to populate the cache in response to the access request, the circuit112may copy a cache line containing the requested memory address from the circuits108a-108gto the cache in the step188. The method180may continue with the step190.

Where the replacement policy decides not to populate the cache, the requested memory address is already available in the cache (e.g., a cache hit) or the requested data was recently retrieved from the circuits108a-108g(e.g., step188), the circuit112may service the access request in the step190. In the step192, the circuit112may signal to the circuit114the results of the replacement policy.

Referring toFIG. 6, a flow diagram of an example method200for updating the window headers is shown. The method (or process)200may be implemented by the circuit104. The method200generally comprises a step (or state)202, a step (or state)204, a step (or state)206, a step (or state)208, a step (or state)210, a step (or state)212and a step (or state)214. The steps202-214may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step202, the circuit114may receive the signal from the circuit112indicating that the access request has been serviced. The circuit114may consider if one or more cache lines were populated or not from the circuits108a-108gwhile servicing the access request in the step204. If old data in the cache lines was replaced by new data from the circuits108a-108g, the circuit114may remap links for the cache lines from the old window headers to the new window headers. In the step206, the circuit114may unlink the cache lines from the old window headers that corresponds to the old data (or memory addresses) removed from the cache. In the step208, the circuit114may link the cache lines to the new window headers that cover the new data (or memory addresses) copied into the cache. The method200may continue with the step210.

If no remapping was performed or if some cache lines were changed while servicing the access request, the circuit114may determine in the step210if any of the window headers should be changed between two or more queues (or lists). Consider by way of example a virtual window header that had no links to the actual cache lines before the access request. Such a virtual window header may be stored in a cacheless-type queue. If servicing the request causes the virtual window header to acquire one or more links to one or more cache lines, the circuit114may move the window header from the cacheless-type queue to a cached-type queue in the step212. Likewise, if servicing the access request breaks all links between a window header in the cached-type queue, the circuit114may move the window header into a most recently used (e.g., MRU) position in the cacheless-type queue in the step212.

If servicing the access request does not pull the window header from the cacheless-type queue or move the window header into the cacheless-type queue, the circuit114may move the window header within a current queue (e.g., the cacheless-type queue or the cached-type queue) in the step214. For example, the window header spanning the address space of the just-serviced access request may be moved to a most recently used (e.g., MRU) position in the current queue. Once the window headers are properly placed in the proper queues, the method200may end and wait for the next access request from the circuit102.

Referring toFIG. 7, a block diagram of an example set220of queues for the window headers is shown. The diagram generally illustrates the relationships between windows with links to the cache lines and widows without links to the cache lines. The set220generally comprises multiple queues (or lists) Q0, Q1and Q2. The queue Q0may be used to organize the virtual window headers (e.g.,140b) that have no corresponding data in the physical cache. The queue Q1may be used to organize the window headers (e.g.,140c) having some subwindows that correspond to data in the physical cache. The queue Q2may be used to organize the window headers (e.g.,140a) having all subwindows correspond to data in the physical cache. Other numbers and/or arrangements of the queues may be implemented to meet the criteria of a particular application.

Although the use of the window headers has been described in terms of caching virtual disks for one or more hosts, the window headers may be used in other applications. For example, the window headers may be used to track queries into a database to determine where frequently accessed data is located. In another example, the window headers may be used in a trend analysis to locate high density areas for entries (e.g., reported flu cases) made into a grid array (e.g., a city or county map).

The elements of the invention may form part or all of one or more devices, units, components, systems, machines and/or apparatuses. The devices may include, but are not limited to, servers, workstations, storage array controllers, storage systems, personal computers, laptop computers, notebook computers, palm computers, personal digital assistants, portable electronic devices, battery powered devices, set-top boxes, encoders, decoders, transcoders, compressors, decompressors, pre-processors, post-processors, transmitters, receivers, transceivers, cipher circuits, cellular telephones, digital cameras, positioning and/or navigation systems, medical equipment, heads-up displays, wireless devices, audio recording, storage and/or playback devices, video recording, storage and/or playback devices, game platforms, peripherals and/or multi-chip modules. Those skilled in the relevant art(s) would understand that the elements of the invention may be implemented in other types of devices to meet the criteria of a particular application.