Storage Controller and Method for Managing Metadata Operations in a Cache
A cache controller having a cache supported by a non-volatile memory element manages metadata operations by defining a mathematical relationship between a cache line in a data store exposed to a host system and a location identifier associated with an instance of the cache line in the non-volatile memory. The cache controller maintains most recently used bit maps identifying data in the cache, as well as a data characteristic bit map identifying data that has changed since it was added to the cache. The cache controller maintains a most recently used bit map to replace the recently map at an appropriate time and a fresh bitmap tracks the most recently used bit map. The cache controller uses a collision bitmap, an imposter index and a quotient to modify cache lines stored in the non-volatile memory element.
1 . A method for managing metadata operations in a cache supported by a solid-state memory element, the method comprising:
defining a mathematical relationship between a segment in a data store exposed to a host system by a target identifier and a location identifier associated with a cache line in the solid state-memory element;
using a quotient factor and the target identifier to determine when requested data is present in the cache;
maintaining a set of bitmaps that define at least one characteristic of data present in a cache line in the solid-state memory element;
maintaining a recently used bitmap that is available to replace the most recently used bitmap;
recording a collision bitmap, an imposter index, the target identifier and a quotient for respective cache lines in the cache; and
using one or more of the collision bitmap, the imposter index and the quotient to modify cache lines stored in the solid-state memory element.
2 . The method of claim 1 , wherein defining a relationship between the segment and a location identifier is responsive to a set of functions that define an M-set associative cache.
3 . The method of claim 2 , further comprising:
receiving, with a storage controller, an input/output operation request from a host, the input/output operation request defining a segment of interest;
checking if the cache line corresponding to the segment of interest is in the cache store;
when the cache line corresponding to the segment of interest is not stored in the cache, identifying a cache miss, and bypassing the cache.
4 . The method of claim 2 , wherein the set of functions include a first function that defines a direct relationship between a segment in the data store and a corresponding location in the cache store.
5 . The method of claim 4 , wherein the set of functions include a second function that defines a first alternative location in the cache store and a third function that defines a second alternative location in the cache store.
6 . The method of claim 4 , further comprising alternative locations that sequentially follow an offset location removed from the corresponding location.
7 . The method of claim 2 , further comprising:
receiving, with a storage controller, an input/output operation request from a host, the input/output operation request defining a segment of interest;
checking if the cache line corresponding to the segment of interest is in the cache store, wherein checking includes, selecting a first function from the set of functions to determine a base location;
checking the base location for a base cache hit;
when a base cache miss is identified, using the collision bitmap to identify at least one alternate location, when a bit is set to identify the at least one alternate location, checking the alternate location for an alternate cache hit; and
when an alternate cache miss is identified, storing data in a virtual window and bypassing the cache.
8 . The method of claim 7 , further comprising:
determining when the virtual window is hot;
identifying a base location, when the base location is unused, storing the data from the virtual window in the base location;
otherwise, when the base location is occupied,
checking a member of the set of bitmaps that define at least one characteristic of data present in the cache line for an unused alternate location;
when unused,
updating the collision map; and
storing the data from the virtual window;
when all alternatives are occupied,
consulting the most recently used bitmap and the recently used bitmap to identify an eviction candidate.
9 . The method of claim 1 , further comprising:
using corresponding bits in the recently used bit map, the most recently used bitmap, and the set of bitmaps that define at least one characteristic of data present in a cache line in the solid-state memory element to identify a present state of a cache line in the cache store.
10 . The method of claim 9 , wherein a cache line “n” is in a free state when an “n”-th bit in a used bitmap in the set of bitmaps that define at least one characteristic of data present in the cache is set to a predetermined logical value.
11 . The method of claim 9 , wherein a cache line “n” is in a recently used state when an “n”-th bit in an “m”-th recently used bit map is set to a predetermined logical value or when an “n”-th bit in an “m”-th−1 recently used bit map is set to a predetermined logical value.
12 . The method of claim 11 , wherein a cache line “n” is in a not recently used state when an “n”-th bit in an “m”-th recently used bit map is set to an opposed logical value and when an “n”-th bit in an “m”-th−1 recently used bit map is set to the opposed logical value.
13 . The method of claim 11 , wherein a cache line “n” is in a dirty and recently used state when it is recently used and an “n”-th bit in a dirty bitmap in the set of bitmaps that define at least one characteristic of data present in the cache is set to a predetermined logical value.
14 . The method of claim 13 , wherein a cache line “n” is in a dirty and not recently used state when it is not recently used and an “n”-th bit in a dirty bitmap in the set of bitmaps that define at least one characteristic of data present in the cache is set to a predetermined logical value.
15 . A storage controller, comprising:
a first interface for communicating with a host system, the first interface communicating data and command signals with the host system;
a processor coupled to the interface by a bus;
a solid-state memory element coupled to the processor by the bus having stored therein state machine logic responsive to a quotient and a set of functions that define a set-associative cache, a first subset of functions that define a cache address from a host managed address, a second subset of functions that define a host managed address from a cache address, the state machine logic configured to manage the reuse of cache line addresses responsive to recently used bit maps;
a global bitmap module, responsive to a global bitmap,
a collision detection module, responsive to a collision bitmap,
an imposter detection module, responsive to an imposter index; and
a second interface coupled to the processor by the bus, the second interface communicating data with a set of data storage elements supporting a logical volume.
16 . The storage controller of claim 15 , wherein the global bitmap module sets a bit associated with a respective cache line address.
17 . The storage controller of claim 15 , wherein the collision detection module uses “n” bits of a cache line to identify that a base location in the cache is in use.
18 . The storage controller of claim 15 , wherein the imposter detection module identifies when data stored at the present location arrived from an invalid base location.
19 . The storage controller of claim 15 , wherein the imposter detection module determines a valid base location.
20 . The storage controller of claim 15 , wherein the quotient store includes a value that is used to determine a logical block address.