Allocation enforcement in a multi-tenant cache mechanism

• US 9,235,443 B2
• Filed: 05/21/2012
• Issued: 01/12/2016
• Est. Priority Date: 11/30/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chockler, Gregory, Laden, Guy, Parees, Benjamin M., Vigfusson, Ymir
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Ahmed, Hamdy S
• Application Number:
  US13/476,016
• Publication Number:
  US 20130138891A1
• Time in Patent Office: 1,331 Days
• Field of Search: 711/133
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Systems and methods for cache optimization are provided. The method comprises monitoring cache access rate for a plurality of cache tenants sharing same cache mechanism having an amount of data storage space, wherein a first cache tenant having a first cache size is allocated a first cache space within the data storage space, and wherein a second cache tenant having a second cache size is allocated a second cache space within the data storage space. The method further comprises determining cache profiles for at least the first cache tenant and the second cache tenant according to data collected during the monitoring; analyzing the cache profiles for the plurality of cache tenants to determine an expected cache usage model for the cache mechanism; and analyzing the cache usage model and factors related to cache efficiency or performance for the one or more cache tenants to dictate one or more occupancy constraints.

Claims

1. A computer-implemented cache optimization method comprising:

monitoring cache access rate for a plurality of cache tenants sharing the same cache mechanism having an amount of data storage space,

wherein each cache tenant is allocated a cache space having a cache size within the data storage space;

determining cache profiles for the plurality of cache tenants according to data collected during the monitoring;

analyzing the cache profiles for the plurality of cache tenants to determine an expected cache usage model for the cache mechanism;

analyzing the cache usage model and factors related to cache efficiency or performance for the plurality of cache tenants to dictate one or more occupancy constraints that define data storage space allocations to the plurality of cache tenants;

examining the data storage allocations to the plurality of cache tenants, in response to receiving a request to increase a first cache size by an amount so that additional cache space is allocated to a first cache tenant;

in response to determining that there is a second cache tenant from among the plurality of cache tenants for which reducing a second cache size allocated to the second cache tenant by the amount will not violate the occupancy constraints for a cache size allocated to the second cache tenant,

decreasing the second cache size by deallocating data storage space allocated to the second cache tenant by the amount and increasing the first cache size by allocating the same amount of data storage space to the first cache tenant to satisfy the request; and

in response to determining that there is not a second cache tenant from among the plurality of cache tenants for which reducing a second cache size allocated to the second cache tenant by the amount will not violate the occupancy constraints for a cache size allocated to the second cache tenant, increasing the first cache size by allocating the amount of data storage space to the first cache tenant without deallocating the same amount of data storage space allocated to another cache tenant from among the plurality of cache tenants.

2. The method of claim 1 wherein selecting a second tenant is performed based on a cache eviction policy shared by all tenants.

3. The method of claim 2 wherein the cache eviction policy is based on evicting the least recently used cached item from the cache.

4. The method of claim 3 wherein the cache eviction policy is implemented using a clock cache eviction mechanism.

5. The method of claim 4 wherein the clock cache eviction mechanism operates based on a data structure that supports cache entries organized into a circular array, wherein an entry in the circular array is evicted if a recently used bit associated with the entry is unset, and the entry is associated with a cache tenant for which reducing the cache space allocation to said cache tenant will not cause the resulting reduced cache allocation to move farther away from the occupancy constraints for said cache tenant.

6. The method of claim 1, wherein current distribution of the cache space among the plurality of cache tenants is represented as an allocation vector in n-dimensional space, wherein n represents number of the plurality of tenants, and the occupancy constraints are represented by a set of linear inequalities of n variables.

7. The method of claim 6 wherein an occupancy constraint defines a hyperplane.

8. The method of claim 7 wherein intersection of the occupancy constraints in the n-dimensional space defines a solution polytope.

9. The method of claim 8 wherein the solution polytope refers to a set of points that satisfy a target cache space allocation for a cache tenant based on the occupancy constraints associated with said cache tenant.

10. The method of claim 9 wherein in response to receiving a request to modify cache allocation for a cache tenant, an allocation vector resulting from the requested modification is not farther away from the solution polytope than the current cache allocation for the cache tenant.

11. The method of claim 10 wherein distance between a current allocation vector associated with the current cache allocation for the cache tenant and each hyperplane corresponding to the occupancy constraints for the cache tenant is monitored, and said distance is updated every time cache allocation of any of the tenants changes.

12. The method of claim 10 wherein distance between a current allocation vector associated with the current cache allocation for the cache tenant and each hyperplane corresponding to the occupancy constraints for the cache tenant is monitored, and said distance is updated every time a set of occupancy constraints associated with a cache tenant is updated.

13. A computer-implemented cache optimization system comprising:

a profiler for monitoring cache access rate for a plurality of cache tenants sharing same cache mechanism having an amount of data storage space,

wherein each cache tenant is allocated a cache space having a cache size within the data storage space;

the profiler determining cache profiles for the plurality of cache tenants according to data collected during the monitoring;

an assembler for analyzing the cache profiles for the plurality of cache tenants to determine an expected cache usage model for the cache mechanism;

a partitioner for analyzing the cache usage model and factors related to cache efficiency or performance for the plurality of cache tenants to dictate one or more occupancy constraints that define data storage space allocations to the plurality of cache tenants;

a partition enforcer for examining the data storage allocations to the plurality of cache tenants, in response to receiving a request to increase a first cache size by an amount so that additional cache space is allocated to a first cache tenant;

a logic unit for selecting a second cache tenant from among the plurality of cache tenants for which reducing a second cache size allocated to the second cache tenant by the amount will not violate the occupancy constraints for a cache size allocated to the second cache tenant, and decreasing the second cache size by deallocating data storage space allocated to the second cache tenant by the amount and increasing the first cache size by allocating the same amount of data storage space to the first cache tenant to satisfy the request; and

a logic unit for increasing the first cache size by allocating the amount of data storage space to the first cache tenant without deallocating the same amount of data storage space allocated to another cache tenant from among the plurality of cache tenants, in response to determining that a second cache tenant cannot be selected.