Sequential Detection

The goal of sequential detection is to automatically uncover a sequential access pattern. Such a pattern is not obvious to discover because of possible interleaving between various sequential streams and pauses between consecutive requests by a single stream, namely, the think time between requests.

The basic idea is to maintain a sequential detect counter with every track, and to use a parameter seqThreshold that can be set differently depending upon whether aggressive or conservative sequential detection is desired. The counter is updated as follows. On a hit or miss to track $n$ whose counter is uninitialized, if track $n-1$ is present in the cache, then set the counter of track $n$ to minimum of seqThreshold or one plus the counter value for track $n-1$. If track $n-1$ is not present in the cache, set the counter for track $n$ to $1$. Once initialized, the counter value for a track is not changed unless it reenters the cache after an eviction. When the counter equals seqThreshold, the track is termed as a sequential track. If a track gets designated as a sequential track on a miss, then we say that a sequential miss has occurred.