Self-adjusting caching system

An apparatus having a cache and a controller is disclosed. The controller is configured to (i) gather a plurality of statistics corresponding to a plurality of requests made from one or more hosts to access a memory during an interval, (ii) store data of the requests selectively in the cache in response to a plurality of headers and (iii) adjust one or more parameters in the headers in response to the statistics. The requests and the parameters are recorded in the headers.

FIELD OF THE INVENTION

The invention relates to cache memories generally and, more particularly, to a method and/or apparatus for implementing a self-adjusting caching system.

BACKGROUND

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 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 is negatively impacted because loading the infrequently accessed data into the cache represents additional operations.

SUMMARY

The invention concerns an apparatus having a cache and a controller. The controller is configured to (i) gather a plurality of statistics corresponding to a plurality of requests made from one or more hosts to access a memory during an interval, (ii) store data of the requests selectively in the cache in response to a plurality of headers and (iii) adjust one or more parameters in the headers in response to the statistics. The requests and the parameters are recorded in the headers.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiments of the invention include providing a self-adjusting caching system that may (i) provide weighted calculations of a heat index, (ii) give preference to one or multiple singular parameters in the system, (iii) operate either on a timer or on a number of executed input/output access requests, (iv) give different weights to different parameters based on an input/output stream analysis, (v) demote/promote windows among queues on a per window basis, (vi) calculate a different heat index for each window, (vii) balance inter-queue demotions to match inter-queue promotions, (viii) track of number of demotions per queue and/or (ix) be implemented as one or more integrated circuits.

Some embodiments provide self-adjustment of operational parameters and processes (or functions) in a caching system based on a statistical analysis run during each given interval. Cache data storage or bypass of a cache memory is based on statistical parameters. The caching is flexible in promotions and demotions of the cache data based on functions performed on each of the statistical parameters. The statistical parameters allow for preferences not only for spatial and temporal relationships of data, but can also be based on a nature of the input/output requests to read or write, a sequential relationship (or nature) of the accesses and/or ratios of reads to writes with a standard spatial and temporal nature of data.

The caching system is typically used in connection with a mass storage memory device (or circuit), such as a redundant array of independent disks (e.g., RAID). An address space of the memory circuit is divided into windows. Each window can be associated with none, one or more cache lines. Each window is tracked as an individual entity. To provide retention and replacement, the windows are organized into ascending priority queues that are double linked with a least-recently-used position at a head of the queue and a most-recently-used position being a last entry. Queue heads retain some of the heuristic parameters associated with the caching, such as a last time of access and the heat index. Each heat index is used as a priority index into the queues.

Referring toFIG. 1, a block diagram of an apparatus90is shown. The apparatus (or system)90may implement a computer system having a self-adjusting caching system. The apparatus90generally comprises one or more blocks (or circuits)92, a block (or circuit)94, one or more blocks (or circuits)96a-96g, a block (or circuit)98and a block (or circuit)100. In some embodiments, the circuit98may part of the circuit100. The circuits92-100may 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) is shown exchanged between the circuit92and the circuit100. A cache memory signal (e.g., CM) is shown exchanged between the circuit100and the circuit98. The circuit100is shown exchanging disk memory signals (e.g., DMa-DMg) with the circuit94(e.g., the circuits96a-96g).

The circuit92implements one or more host circuits. Each circuit92is operational to present access requests to the circuit100via the signal MEM. The access requests may include, but are not limited to, read access requests and write access requests. Each read access request includes a memory address from which data is to be read. Each write access request includes 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 circuit94implements a memory circuit (or mass storage device). The circuit94is operational to store data written by the circuit100and present data read by the circuit100. The circuit94may 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. In some embodiments, the circuit94is configure to operate as one or more virtual disks (or virtual memories).

Each circuit96a-96gimplements a storage drive. The circuits96a-96gare operational to store data for the circuit92. The data is received from the circuit100and sent to the circuit100via the respective signals DMa-DMg. Collectively, the circuits96a-96gform a mass storage device. A common size of the mass storage device ranges from a several terabytes to a few petabytes. In some embodiments, the mass storage device is arranged as one or more virtual devices (or virtual disks), as seen from the circuit92. In some embodiments, the circuits96a-96gare all implemented with the same technology. In other embodiments, the circuit96a-96gare implemented with a mixture of technologies. The technologies may include, but are not limited to, magnetic disk drives, optical drives, electro-magneto drives, solid-state (e.g., flash) drives and tape drives. Other drive technologies may be implemented to meet the criteria of a particular application.

The circuit98implements a cache memory circuit. The circuit98is operational to buffer data received from the circuit100via the signal CM. The buffered data is arranged as multiple cache lines. The data in the cache lines is transferred to the circuit100via the signal CM. In some embodiments, the circuit98is implemented as a solid-state drive. Common sizes of a solid-state drive range from 1 to 2 terabytes. In other embodiments, the circuit98is implemented as a double data rate memory circuit. Common sizes of a double data rate memory range from 1 to 64 gigabytes.

The circuit100may implement a redundant array of independent disks controller circuit. The circuit100is generally operational to process the access requests received via the signal MEM to store and read data to and from the circuit94(e.g., the circuits96a-96g). The circuit100includes cache operations using either an internal cache memory or the circuit98. The cache operations include generating an access (or trace) history of all access requests received from the circuit92. The circuit100gathers statistics corresponding to the access requests made from one or more circuit92to access the circuit94during an interval. The data of the access requests is stored selectively in the cache in response to a plurality of headers. One or more parameters in the headers are adjusted at an end of each interval in response to the statistics. The access requests and the parameters are recorded in the corresponding headers. The window headers divide an address space of the circuit94into a plurality of windows. Each window generally has a plurality of subwindows. Each subwindow is sized to match a cache line in the cache. Each subwindow corresponds to one or more of the addresses.

Referring toFIG. 2, a block diagram of an example implementation of the circuit100is shown in accordance with an embodiment of the invention. The circuit (or apparatus or device or integrated circuit)100generally comprises a block (or circuit)102, a block (or circuit)104, a block (or circuit)106, a block (or circuit)108and a block (or circuit)110. The circuits102-110may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

The circuit102implements a processor circuit. The circuit102is operational to control overall operations for the circuit100. The circuit102executes software (or firmware or code or programming instructions) to move data between the circuit92, the circuit94and/or the circuit98.

The circuit104implements a caching decision engine. The circuit104is operational to determine which data is stored (or copied) into the cache (e.g., the circuit98and/or the circuit106) and which data bypasses the cache. The determination is based on the statistical parameters generated by the circuit102.

The circuit106implements a dynamic random access memory (e.g., DRAM) circuit. The circuit106is operational to store the window headers (e.g., access histories) generated by the circuit100. In some embodiments, the circuit106also implements a cache memory used to cache data in transit to and from the circuit94.

The circuit108implements a replacement module. The circuit108is operational to determine (i) when and which sets of data should be stored in the cache (e.g., the circuit98and/or the circuit106) and (ii) when and which sets of data should be removed from in the cache. A store/remove (replacement) decision implemented by the circuit108utilizes the access history. Generally, hot (e.g., frequently accessed) data identified by the access history is usually populated in the cache. Cool (e.g., 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 circuit110implements a history module. The circuit110is operational to create the access histories from the access requests received from the circuit92. The circuit110generates the access histories by mapping the address space of the circuit94into a fixed size granularity called windows (or extents). Each window tracks a granularity-sized portion of host space accesses. An additional granularity underneath each window is referred to as a subwindow (or subwindow extent). Each subwindow is associated with one or more addresses (e.g., logical block addresses). Each subwindow also represents (or matches) 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 are referred to as virtual window headers.

Many more window headers are commonly allocated across the address space of the circuit94than exists in the physical cache. Covering the address space of the circuit94generally allows for large regions of host accesses to be tracked although the cache is not involved in many host accesses. The access histories generally provide detailed information about host access patterns.

Referring toFIG. 3, a diagram of an example implementation of a window header120is shown. The window header120is generated by the circuit110and stored in the circuit106. Each window header120is shown including a parameter (or field)122, a parameter (or field)124, a parameter (or field)126, a parameter (or field)128, a parameter (or field)130, a parameter (or field)132, a parameter (or field)134, a parameter (or field)136, a parameter (or field)138, and multiple parameters (or fields)140a-140n. Each window header120has a fixed size that spans a fixed amount (e.g., 1 megabyte of data or 2048 logical block addresses at 512 bytes/block) of the address space of the circuit94. 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., circuit106). Adjoining windows do not overlap.

The field122implements a window identity field. The field122provides a unique identifier of the corresponding window header120to allow the circuit110to distinguish among the various window headers120.

The field124implements a range field. The field124generally defines a range of addresses (e.g., logical block addresses) covered by the corresponding window header120.

The field126implements a start address field. The field126establishes a starting address (e.g., a particular logical block address) of the corresponding window header120.

The field128implements a virtual disk number field. The field128stores an identification number of a virtual disk for which the window header120is established.

The field130implements a last time or last input/output of access field. The field130records the last access of an address covered by the window header120.

The field132implements a heat index field. The field132records a heat value that identifies how hot or cool the access requests associated with the window header120have been during an interval.

The field134implements a number of valid cache lines field. The field134identifies how may cache lines associated with the window header120contain valid data. Virtual window headers just count line hits as no physical cache is associated with the virtual window headers.

The field136implements a forward pointer field. The field136points forward to a next window header or queue header.

The field138implements a backward pointer field. The field136points back to a previous window header or the queue header.

Each field142a-142nimplements a count field. Each field142a-142nstores a count of the number of access requests made by the circuit92into the address range covered by the corresponding field (subwindow)140a-140n. In some embodiments, the count is a running count of all access requests. In other embodiments, the count is 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.) or the interval.

Each element144a-144bimplements an access element (or indicator). For each access request received by the circuit100, an element144a-144bis generated in the appropriate field140a-140nof the subwindow corresponding to the memory address received in the access request. When created, each element144a-144bincludes 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 circuit100. Every host access request generates a cache window header access element144a-144bregardless 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 fields140a-140nin each window header120may have different numbers of the elements144a-144bin response to the number and locations (e.g., addresses) of the access requests.

Referring toFIG. 4, a block diagram of an example arrangement160of multiple priority queues162a-162nis shown. he priority queues162a-162nare arranged in an order of priority. In the example, the priority queue162ahas a lowest priority (e.g., first to have data evicted from the cache) and the priority queue162nhas a highest priority. During inter-queue promotions, a window header120will be moved from a current priority queue (e.g., the priority queue162a) to a next higher priority queue (e.g., the priority queue162b). The moved window header120is appended (e.g., attached to an end) to the new queue. During inter-queue demotions, a window header120will be prepended (e.g., attached to a front) to the new queue. Any number of the priority queues162a-162n(e.g., 3-20) are generally implemented.

Referring toFIG. 5, a block diagram of an example arrangement of window headers120a-120cwithin a priority queue162xis shown. The priority queue162xis representative of the priority queues162a-16n. The priority queue162xis represented by a header180that contains a pointer to a first element (e.g., a window header), a pointer to a last element (e.g., a window header), a number of demotions in a current interval, a minimum heat index value in order to be promoted to the queue162x(e.g., a promotion value), an interval value (e.g., either time or an input/output access request count) and minimum number of demotions value (or threshold).

Multiple window headers120a-120care illustrated arranged in ascending order. The window header120ais shown in a least recently used (or lowest) position. The window header120cis shown in a most recently used (or highest) position. The window headers120a-120cand the header180of the priority queue162xare connected as a doubly linked list.

Referring toFIG. 6, a flow diagram of an example method200of a self-adjusting feedback loop is shown. The method (or process)200is implemented by the circuit100. The method200generally comprises a step (or state)202, a step (or state)204, a step (or state)206and a step (or state)208. The steps202-208may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step202, one or more access requests are received by the circuit100from the circuit92. For the duration of an interval (e.g., a period of time or a number of input/output requests), the circuit102gathers statistics and passes commands to the circuit104. The circuit104performs caching decision operations in the step206. The caching decisions are based on the statistical data. At an end of the interval, the circuit100adjusts the techniques and parameter values in each of the priority queues162a-162n. The adjusted techniques and the adjusted parameters are feed back to the circuit104to future caching decision operations.

Each window header120is initialized with a coldest heat index value (e.g., zero). Each priority queue162a-162nhas an individual promotion setting. Each promotion setting in each lower priority queue162a-162nhas a lower value than a neighboring higher priority queue162a-162n.

The heat index value of a window120is calculated in the step208at the end of each interval per formula 1 as follows:
Heat Index+=(F1(IOtype, read or write)+F2(Additional cache lines valid))/F3(Timer or IO count difference since last access)  (1)
The function F1allows the type of input/output (e.g., IO) access requests to be weighted in each window versus a function F3of time or number of input/output access requests until a next access request is received by the circuit100. The function F2is based on a number of additional cache lines that become valid during the interval.

A demotion formula of the heat index value is calculated per formula 2 as follows:
New Heat Index=Current Heat Index/F3(Time or IO count difference)  (2)
If the new heat index value is less than the current heat index value, the window header120is demoted.

The heat index value is generally calculated on each input/output access request of the corresponding window header120. If the heat index value of a given window header120exceeds the promotion value of the next highest priority queue162a-162n, the given window header120is removed from the current priority queue162a-162nand appended to the (new) next highest priority queue162a-162n.

After completion of the promotion, the least recently used window header120in the new priority queue162a-162nis examined and demoted, if possible. If the least recently used window header120is demoted, a counter for a number of demoted windows is incremented.

After the interval has expired, the step208includes examining the counter for the number of demotions in each priority queue162a-162n. Where the counter for the number of demotions is less than the minimum number of demotions for a given priority queue162a-162n, one or more window headers120are demoted until the counter matches the minimum number of demotions threshold. The counter for the number of demotions is reset to zero for each priority queue162a-162nonce all of the demotions for the just-completed interval have been made. The heat index value in the least recently used (virtual) window header120in the lowest priority queue162ais subsequently examined to see if new data can be brought into the cache or not for the virtual window header120.

During the step208, the techniques for adjusting the parameters in the window headers120are also modified. Several examples include, but are not limited to the following modifications. If highly repetitive access requests are detected such that one access request is followed by several in the same window header (or extent region)120, the criteria for promotion from the lowest priority queue162a(e.g., promotion from virtual to physical cache) can be adjusted to a point where an initial access can be stored in the physical cache.

In another example, if the access requests are highly spatially related (e.g., in a small band of logical block address ranges), the spatial portion of the heat index function (e.g., F2) is increased. Therefore, an addition of a valid cache line in the window will increase the heat index value disproportionately to number or type of access requests.

Upon detection that every write type access request is followed by several read type access requests in the same logical block address range, the value of the writes in the type of input/output heat index function (e.g., F1) is increased so that the initial write access is cached, but possibly not in an initial read access.

The ratios of write accesses to read accesses can be examined in another value. Based on the ratios, a flushing process can be adjusted to accommodate an availability of replacement window headers.

In another example, a sequential nature of access requests are detected. In response to the nature, the step208determines whether to perform a read ahead or a write behind between the cache and the circuit94.

Generally, the window headers120are dealt with in terms of the intervals. The heat index formula allows weighting of the input/output access requests, an amount of spatial data and an amount of temporal data separately. Adjustments per each aspect of the formula are possible. In some embodiments, preferences are given to spatial relationships (e.g., number of valid lines). In other embodiments, preferences are given to either read requests or to write requests. The promotional scheme could be made nonuniform, where different values are applied to different levels of priority. The demotion of a window header for each promotion of a window header achieves balance in terms of overall window header availability for replacement. The methods and techniques will also work with elastic caches and virtual caches. Additional priority queues can be set up to reflect different aspects of behavior. For example, one or more priority queues can be established for dirty data to determine flush priority. One or more priority queues could also be established for a physical drive for proper distribution for mirror windows in an elastic cache implementation.

Referring toFIG. 7, a block diagram of example multiple window headers220a-220crelative to multiple cache lines is shown. The block diagram generally illustrates relationships between a window size granularity and a cache granularity. Each window header220a-220cis representative of the window header120. The example window header220agenerally illustrates a full header. All of the subwindow fields140a-140n(FIG. 3) in the window header220acorrespond to addresses that are currently buffered in respective cache lines222a-222kof the cache. Therefore, any access request initiated by the circuit92into the address space covered by the window header220aresults in a cache hit.

The example window header220bgenerally illustrates an empty header. None of the subwindow fields140a-140n(FIG. 3) in the window header220bcorrespond to an address that is currently buffered in the cache. The window header220bis not backed by the physical cache so the window header220bis referred to as a virtual window header. All access requests initiated by the circuit92into the address space covered by the virtual window header220bresult in a cache miss.

The example window header220cgenerally illustrates a partially full header. Some subwindow fields140a-140n(e.g., a single subwindow in the example) correspond to an address that is currently buffered in the cache line222m. The other subwindow fields140a-140ncorrespond to addresses not currently buffered in the cache. As such, some access requests initiated by the circuit92into the window220cresult in a cache hit and other access requests result in a cache miss.

Referring toFIG. 8, a flow diagram of an example method240for updating the access history is shown. The method (or process)240is implemented by the circuit100. The method240generally comprises a step (or state)242, a step (or state)244, a step (or state)246, a step (or state)248, a step (or state)250, a step (or state)252, a step (or state)254, a step (or state)256, a step (or state)258and a step (or state)260. The steps242-260may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step242, the circuit110creates multiple window headers that divide the address space of the circuit94or the resulting virtual disks. Each window header generally represents a portion of the address space. In some embodiments, the entire address space is covered by the window headers. In other embodiments, a subset of the address space are covered by the window headers at any given time.

In the step244, the circuit100receives an access request from the circuit92. The access request is presented to the circuit110to determine which window header and which subwindow is associated with the memory address (e.g., logical block address) received in the access request per the step246. In situations where the circuit92is implemented as two or more hosts, an identify of the sending host is 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 least recently used virtual window header) is 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 is updated in the step248by the circuit110. Updating the tracking information includes creating a new element in the associated subwindow to record the access request in the step250. The element indicates the type of access request and the time at which the access request was received.

In the step252, the circuit110determines 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 is considered stale and thus should be removed. In another example, if the newly added element fills the capacity of the subwindow, the oldest element is 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 step254, the tracking information (e.g., count number) of the subwindow is updated by the circuit110in the step256. The method240continues with the step258.

If no elements should be removed, or purging of elements is not implemented by a particular application, the circuit110stores the updated access (trace) history in the circuit106per the step258. The circuit110signals the circuit108in the step260that the updated access history has been posted. Once the circuit110has signaled to the circuit108, the method240ends and wait for the next access request from the circuit92.

Referring toFIG. 9, a flow diagram of an example method280for updating the cache is shown. The method (or process)280is implemented by the circuit100. The method280generally comprises a step (or state)282, a step (or state)284, a step (or state)286, a step (or state)288, a step (or state)290and a step (or state)292. The steps282-292may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step282, the circuit108receives the signal from the circuit110indicating that the updated access history is available in the circuit106. The circuit108reads the access history and the received access request in the step284. In the step286, the circuit108determine if one or more cache lines should be populated from the circuit94in 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 is raised. The replacement policy implemented by the circuit108thus concludes 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 circuit108copies a cache line containing the requested memory address from the circuits96a-96gto the cache in the step288. The method280continue with the step290.

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 circuit94(e.g., step288), the circuit108services the access request in the step290. In the step292, the circuit108signals to the circuit110the results of the replacement policy.

Referring toFIG. 10, a flow diagram of an example method300for updating the window headers is shown. The method (or process)300may be implemented by the circuit100. The method300generally comprises a step (or state)302, a step (or state)304, a step (or state)306, a step (or state)308, a step (or state)310, a step (or state)312and a step (or state)314. The steps302-314may represent modules and/or blocks that may be implemented as hardware, software, a combination of hardware and software, or other implementations.

In the step302, the circuit110receives the signal from the circuit108indicating that the access request has been serviced. The circuit110considers if one or more cache lines were populated or not from the circuit94while servicing the access request in the step304. If old data in the cache lines was replaced by new data from the circuit94, the circuit110remaps links for the cache lines from the old window headers to the new window headers. In the step306, the circuit110unlinks the cache lines from the old window headers that corresponds to the old data (or memory addresses) removed from the cache. In the step308, the circuit110links the cache lines to the new window headers that cover the new data (or memory addresses) copied into the cache. The method300may continue with the step310.

If no remapping was performed or if some cache lines were changed while servicing the access request, the circuit110determines in the step310if any of the window headers should be changed between two or more priority queues (or lists). Consider by way of example a virtual window header (e.g.,220b) that had no links to the actual cache lines before the access request. Such a virtual window header is stored in a cacheless-type priority queue (e.g.,162a). If servicing the request causes the virtual window header to acquire one or more links to one or more cache lines, the circuit110moves (or promotes) the window header from the cacheless-type queue to a cached-type queue in the step312. Likewise, if servicing the access request breaks all links between a window header in the cached-type queue, the circuit110moves (or demotes) the window header into a most recently used position in the cacheless-type queue in the step312.

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 circuit110moves the window header within a current queue (e.g., the cacheless-type queue or the cached-type queue) in the step314. For example, the window header spanning the address space of the just-serviced access request is moved to a most recently used position in the current queue. Once the window headers are properly placed in the proper queues, the method300ends and waits for the next access request from the circuit92.

Embodiments of the invention generally provide flexible functions that can provided weighted calculation of the heat index values. The weights give preference to one or multiple singular parameters in the system (e.g., reads versus writes, number of valid lines in the window, sequential versus random patterns, read/write mix etc.) The system can operate based on either a timer or a number of executed access requests. The interval parameter is kept on a per window basis. The functions used to calculate the heat indexes can be adjusted (e.g., given different weight to different parameters) based on an input/output stream analysis done by the system. Demotions/promotions are performed on per window bases, with each window having an independent heat index calculated. A balanced approach to the demotion/promotion can be implemented with one window being possibly demoted for each window being promoted. The system also keeps track of the number of demotions per priority queue. If some queues did not demote enough windows during a given interval, at expiration of the interval, one or more windows are demoted from such queues.