Method of detecting sequential workloads to increase host read throughput
AssigneeHewlett-Packard Development Company, L.P.
InventorBrian S. Bearden
Life of this patent
Estimating the term…
Abstract
Exemplary systems and methods analyze cache data to detect a sequential workload to facilitate pre-fetching effectiveness. An exemplary address analysis module for sequential workload detection generates one or more addresses related to a host address. If the cache memory contains data corresponding to one or more of the related addresses, a sequential workload may be occurring, and a read pre-fetch operation may be triggered. An indexing module may be used to map host and related addresses to corresponding indices in cache memory.
Claims22
A processor-readable medium comprising processor-executable instructions configured for executing a method comprising:
- mapping storage device addresses to cache addresses using a hash table;
- reviewing, in response to a request for data at a first address, a history of memory requests within the hash table to determine if requests for data include addresses sequentially related to the first address;
- and
- if triggered by discovery of sufficient sequentially related addresses, pre-fetching data, not already in cache, at an address related to the first address.
A processor-implemented method for detecting a sequential workload in a storage device, comprising;
- receiving a data request associated with a first address;
- generating addresses related to the first address;
- hashing the related addresses to obtain indexes;
- searching a hash table, configured to map data storage to cache memory, for the indexes;
- and
- where indicated by the searching, pro-fetching data, not already in cache, from an address related to the first address.
A caching system, comprising:
- a mass storage memory;
- a cache memory;
- and
- an address analysis module configured to detect addresses sequential to an incoming address by creating related addresses by subtracting multiples of a look-back value from the incoming address, hashing the related addresses, and searching for the hashed related addresses in a hash table, wherein the hash table is configured to map addresses between the mass storage memory and the cache memory;
- wherein discovery of a sufficient quantity of the hashed related addresses in the hash table triggers a pre-fetch of data from an address related to the incoming address that has not yet been cached.
A method of detecting a sequential workload in a storage device comprising:
- receiving a first address;
- determining whether data associated with a number of addresses sequential to the first address has been cached, wherein the determining whether data associated with a number of addresses comprises generating the number of cache indices, each of the cache indices associated with one of the number of addresses, wherein the generating a cache index associated with each of the number of addresses comprises:
- generating the number of hash keys, each hash key associated with one of the number of addresses;
- hashing on the number of hash keys using a hash table;
- and
- determining whether a cache index exists in the hash table associated with each of the number of hash keys;
- and
- if the data associated with the number of addresses has been cached, caching data associated with a second address sequentially related to the first address.
A storage device comprising:
- a mass storage medium;
- a cache memory in operable communication with the mass storage medium;
- an input/output module operable to receive a request with a first address;
- and
- an address analysis module in operable communication with the input/output module and operable to detect a sequential host workload based on data in cache memory, wherein the address analysis module is further operable to determine whether the cache memory has data associated with one or more sequentially related addresses sequentially related to the first address;
- wherein the address analysis module determines whether to pre-fetch data based at least in part on data in the cache memory corresponding to a second address, the second address being related to the first address;
- a mapping module in operable communication with the address analysis module, wherein the mapping module is operable to receive a host address and generate a corresponding index into the cache memory, wherein the mapping module comprises:
- a hash table;
- and
- a hashing module in operable communication with the hash table, operable to generate one or more hash keys, each of the one or more hash keys associated with the one or more sequentially related addresses, use the hash table to hash on each of the one or more hash keys, and determine whether the hash table has a cache index for each of the one or more hash keys.
Dependencies are inferred from the claim text.