Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2001-11-07
2004-09-14
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S153000, C711S167000, C711S203000
Reexamination Certificate
active
06792509
ABSTRACT:
TECHNICAL FIELD
The present invention relates to the field of cache design, and more particularly to adaptively allocating memory to support a partitioned cache of multiple logical levels enabling the cache to be adaptive to multiple criteria thereby improving the performance of the cache.
BACKGROUND INFORMATION
A network server, e.g., file server, database server, web server, may be configured to receive a stream of requests from clients in a network system to read from or write to a particular logical drive in an array of logical drives such as a Redundant Array of Independent Logical drives (RAID). These requests may form what is commonly referred to as a “workload” for the network server. That is, a workload may refer to the requests that need to be serviced by the network server.
Typically, a server in a network system may comprise a network interface controller configured to interface the server with an array of logical drives, e.g., RAID, via adapters, e.g., RAID adapters, coupled to one or more logical drives in the array of logical drives. A server may be configured to create a cache in its main memory, e.g., Random Access Memory (RAM), to increase the speed of accessing data. A cache is faster than a logical drive and thereby allows data to be read at higher speeds. Thus, if data is stored in the cache it may be accessed at higher speeds than accessing the data on a logical drive.
There have been many methods in designing caches that seek to increase the cache hit rate thereby improving performance of the cache. A “cache hit” is said to occur if an item, e.g., data, requested by the processor in the server or a client in a network system, is present in the cache. When an item, e.g., data, requested by the processor in the server or a client in the network system, is not present in the cache, a “cache miss” is said to occur. A “cache hit rate” may refer to the rate at which cache hits occur. By improving the cache hit rate, the performance of the system may be improved, i.e., less data needs to be serviced from the logical drive.
One method to improve the performance of a cache is commonly referred to as the Least Recently Used (LRU) replacement method as illustrated in FIG.
1
. The LRU replacement method uses a single stack
101
comprising a set of cache entries where each cache entry stores particular data. As stated above, if an item, e.g., data, requested by the processor in the server or client in a network system is present in the cache, a “cache hit” is said to occur. When a cache hit occurs, the cache entry comprising the information, e.g., data, requested moves to the first stack position as illustrated in FIG.
1
. As stated above, if an item, e.g., data, requested by the processor in the server or client in a network system is not present in the cache, a “cache miss” is said to occur. When a cache miss occurs, the requested item is retrieved from the logical drive and then stored in the first stack position as illustrated in FIG.
1
. When a new entry is inserted in stack
101
, the cache entry in the last stack position of stack
101
is evicted. The information, e.g., data, may subsequently be discarded.
Another method to improve the performance of a logical drive cache is commonly referred to as the Segmented LRU (S-LRU) replacement method as illustrated in FIG.
2
. The S-LRU replacement method may use two stacks
201
A-B. Each stack, stack
201
A-B, may comprise a set of cache entries where each cache entry stores particular data. When a cache hit occurs in the first stack, e.g., stack
201
A, the cache entry comprising the information, e.g., data, requested moves up to the first stack position of the second stack, e.g., stack
201
B, as illustrated in FIG.
2
. When a new entry is added to stack
201
B, the cache entry at the last stack position of stack
201
B is evicted to the first stack position of stack
201
A. When a new entry is inserted in stack
201
A, the cache entry at the last stack position of stack
201
A is evicted. The information, e.g., data, may subsequently be discarded. When a cache hit occurs in the second stack, e.g., stack
201
B, the cache entry comprising the information, e.g., data, requested moves up to the first stack position of that stack, e.g., stack
201
B, as illustrated in FIG.
2
. When a new entry is inserted in stack
201
B, the cache entry at the last stack position of stack
201
B is evicted to the first stack position of stack
201
A. When a new entry is inserted in stack
201
A, the cache entry at the last stack position of stack
201
A is evicted. When a cache miss occurs, the requested item is retrieved from the logical drive and then stored in the first stack position of the first stack, e.g., stack
201
A, as illustrated in FIG.
2
. When a new entry is inserted in stack
201
A, the cache entry at the last stack position of stack
201
A is evicted. The information, e.g., data, may subsequently be discarded.
Unfortunately, these methods of cache design focus on static techniques instead of adaptive techniques. For example, the length of the stacks in these caches do not adapt, i.e., change in size, to changes in the request stream, i.e., the workload. By designing a cache based on adaptive techniques, the cache hit rate may be improved. Furthermore, these methods do not design a cache that is adaptive based on multiple criteria, e.g., workload, physical characteristics of the network system such as the number of adapters or logical drives in the array of logical drives. Consequently, these methods do not efficiently use memory space thereby providing a need to improve the performance of the cache.
It would therefore be desirable to adaptively allocate memory to support a cache of multiple logical levels enabling the cache to be adaptive to multiple criteria, e.g., physical characteristics of the system, workload, thereby improving the performance of the cache, i.e., improving the cache hit rate.
SUMMARY
The problems outlined above may at least in part be solved in some embodiments by logically grouping the stacks associated with a logical drive into a particular logical grouping. A network server, e.g., file server, database server, web server, may be configured to receive a stream of requests from clients in a network system to read from or write to a particular logical drive in an array of logical drives that comprise a Redundant Array of Independent Logical drives (RAID). Each logical drive may be coupled to an adapter, e.g., RAID adapter, which may be coupled to the network server. That is, each adapter may be coupled to one or more logical drives. Each of the logically grouped stacks of the one or more logical drives coupled to an adapter may be logically grouped into a logically grouped stack associated with that adapter. By logically grouping stacks into further logical groupings, memory supporting a partitioned cache of multiple logical levels may be allocated adaptively in response to multiple criteria, e.g., physical characteristics of the system, workload, thereby improving the performance of the cache, i.e., improving the cache hit rate.
In one embodiment of the present invention, a method for reallocating memory space for storing a partitioned cache may comprise the step of allocating a portion of memory to store a plurality of partitions. A partition may refer to a segment of memory space in memory configured to store a stack comprising one or more cache entries where each cache entry may store information, e.g., data. Each stack may be configured to store information in a particular range of logical block addresses associated with a particular logical drive in an array of logical drives that comprise a Redundant Array of Independent Logical drives (RAID). Each particular logical drive may be coupled to a particular adapter, e.g., RAID adapter. That is, an adapter, e.g., RAID adapter, may be coupled to one or more logical drives. A plurality of adapters may then be coupled to a server configured to receive requests to retrieve information, e.g., data, from a particular logical drive. The ser
Elmore Reba I.
Winstead Sechrest & Minick
LandOfFree
Partitioned cache of multiple logical levels with adaptive... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partitioned cache of multiple logical levels with adaptive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partitioned cache of multiple logical levels with adaptive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207406