Region based admission/eviction control in hybrid aggregates

• US 9,354,989 B1
• Filed: 10/03/2011
• Issued: 05/31/2016
• Est. Priority Date: 10/03/2011
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Sehgal, Priya, Voruganti, Kaladhar, Sundaram, Rajesh
• Primary Examiner(s): Thai, Tuan
• Assistant Examiner(s): Gebril, Mohamed
• Application Number:
  US13/251,916
• Time in Patent Office: 1,702 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029

Abstract

Region based admission and eviction control can be used for managing resources (e.g., caching resources) shared by competing workloads with different SLOs in hybrid aggregates. A “region” or “phase” refers to different incoming loads of a workload (e.g., different working set sizes, different intensities of the workload, etc.). These regions can be identified and then utilized along with other factors (e.g., incoming loads of other workloads, maximum cache allocation size, service level objectives, and others factors/parameters) in managing cache storage resources.

Claims

1. A method of service level objective compliance at a storage layer for a plurality of workloads on a storage system, the method comprising:

determining, by a first workload controller for a first workload of the plurality of workloads, a current phase of the first workload based, at least in part, on

a hit ratio in a first level cache of the storage system for the first workload in a time interval t and a slope value of the time interval t, wherein the slope value is based on a hit ratio in a second level cache for the first workload in the time interval t and an amount used value of the second level cache for the first workload in the time interval t;

wherein the second level cache comprises a non-volatile solid state storage device of the storage system;

determining whether the current phase of the first workload has previously been observed;

in response to a determination that the current phase has not previously been observed,

determining a second level cache partition size based, at least in part, on a calculated hit ratio for the second level cache that corresponds to a service level objective indicated for the first workload in the time interval t;

associating the current phase with the hit ratio in the first level cache in t, the slope value of t, and the determined second level cache partition size;

in response to a determination that a preceding phase of the first workload is different than the current phase and that the current phase has been previously observed as phase n of the first workload,

determining a second level cache partition size indicated for phase n;

requesting, by the first workload controller, a master controller for allocation of the second level cache partition size indicated for phase n to the first workload;

in response to a determination that the current phase has been previously observed as phase n of the first workload and that a service level objective for the first workload is not being satisfied,

requesting, by the first workload controller, the master controller for allocation of the second level cache partition size indicated for phase n to the first workload if the amount used value of the second level cache for the first workload in time interval t is less than the second level cache partition size indicated for phase n of the first workload;

resizing, by the master controller, a second level cache partition allocated from the second level cache to the first workload in accordance with a set of one or more resizing requests from a plurality of workload controllers and states of satisfaction of service level objectives across the plurality of workloads,

wherein the plurality of workload controllers includes the first workload controller.

2. The method of claim 1, wherein the method further comprises:

collecting statistics for the plurality of workloads on a periodic interval of a first duration, wherein the time interval t has a second duration that is a multiple of the first duration; and

each of the workload controllers periodically sampling the collected statistics of a corresponding one of the plurality of workloads.

3. The method of claim 1, wherein the statistics include IO deadlines and IO response times.

4. The method of claim 2, wherein the statistics include SLO statistics that measure one or more of latency, throughput, security, reliability, or capacity.

10. The method of claim 1 further comprising:

in response to the determination that the current phase of the first workload has not previously been observed, requesting, by the first workload controller, a resize to the determined second level cache partition size if a current allocation of the second level cache to the first workload is less than the determined second level cache partition size.

11. The method of claim 1, further comprising:

in response to a determination that the first workload is using more than the second level cache partition size indicated for phase n while the first workload is in phase n and that a service level objective for the first workload is not being met, the first workload controller indicating to the master controller that the first workload fails to meet the service level objective for the first workload.

12. The method of claim 11 further comprising the master controller notifying a layer above the storage layer that the first workload is failing to meet the service level objective for the first workload.

13. The method of claim 1 further comprising:

in response to a determination that the first workload exceeds the service level objective for the first workload and that the first workload is using less than the second level cache partition size indicated for phase n while the first workload is in phase n, indicating to the master controller that the service level objective for the first workload is being exceeded and that the first workload is using less than the second level cache partition size indicated for phase n while in phase n.

14. The method of claim 13 further comprising the master controller reducing the second level cache partition size for phase n of the first workload based, at least in part, on the indication.

15. The method of claim 14, further comprising:

determining, by the master controller, that at least one of the plurality of workloads is failing to meet a corresponding service level objective,

wherein the master controller reduces the second level cache partition size for phase n of the first workload also based, at least in part, on the determination that at least one of the plurality of workloads is failing to meet a corresponding service level objective.

16. The method of claim 1 further comprising:

mapping a plurality of first level cache hit ratios collected in the time interval t for the first workload into a set of one or more hit ratio ranges;

determining a first range of the set of one or more ranges that has a greatest number of the plurality of first level cache hit ratios;

calculating the hit ratio in the first level cache for the first workload in the time interval t based, at least in part, on those of the plurality of first level cache hit ratios that mapped to the first range;

calculating a plurality of slope values with a plurality of second level cache hit ratios for the first workload in the time interval t and a plurality of second level cache used amounts for the first workload during the time interval t;

calculating the slope value based, at least in part, on the plurality of slope values.

17. The method of claim 16, wherein calculating the slope value comprises calculating an average of the plurality of slope values.

18. The method of claim 17, further comprising:

calculating a standard deviation of the plurality of slope values;

wherein determining the second level cache partition size is also based, at least in part, on the standard deviation and the average of the plurality of slope values.

19. The method of claim 1 further comprising:

determining, by the master controller, the states of satisfaction of the service level objectives across the plurality of workloads based, at least in part, on service level objective statistics collected in the time interval t for the plurality of workloads; and

determining, by the master controller, priorities among the plurality of workloads,

wherein resizing by the master controller is also based on the priorities among the plurality of workloads.

5. A method comprising:

caching, within a first level cache, file system data and metadata from a workload having a plurality of operational regions;

in response to a determination that a first operational region has not previously been

observed based, at least in part, on statistics of the workload of a time interval t,

monitoring the workload for a time period to determine whether caching data of the workload that is evicted from the first level cache into a second level cache will will meet or improve compliance with a service level objective (SLO) of the workload;

in response to a determination that caching data of the workload that is evicted from the first level cache into the second level cache will not meet or improve compliance with the SLO of the workload, updating a set of admission rules to prevent caching data of the workload into the second level cache when evicted from the first level cache and when the workload is in the first operational region;

in response to a determination that caching data of the workload that is evicted from the first level cache into the second level cache will meet or improve compliance with the SLO of the workload, updating the set of admission rules to allow caching data of the workload into the second level cache when evicted from the first level cache and when the workload is in the first operational region;

in response to a determination that the first operational region has previously been observed and that the SLO of the workload is not being met based, at least in part, on the statistics of the workload of the time interval t,

modifying the set of admission rules with respect to the first operational region of the workload based, at least in part, on a determination of whether caching data of the workload into the second level cache when evicted from the first level cache will meet or improve compliance with the SLO.

6. The method of claim 5, further comprising determining the first operational region of the workload with the statistics, wherein the statistics at least include a hit ratio in the first level cache for the workload in the time interval t, a used amount value of the second level cache by the workload for the time interval t, and a hit ratio of the workload in the second level cache for the workload in the time interval t.

7. The method of claim 5, further comprising:

determining a set of changes in the plurality of operational regions for the workload; and

updating the set of admission rules in accordance with the set of changes in the plurality of operational regions for the workload.

8. The method of claim 5, further comprising, in response to a determination that the workload has shifted from a second operational region to the first operational region, selecting an admission rule from the set of admission rules that is specified for the second operational region.

9. The method of claim 5 further comprising:

after detecting resize of a second level cache partition for the first operational region of the workload, monitoring second level cache statistics and service level objective statistics of the workload to determine whether caching data of the workload into the second level cache when evicted from the first level cache meets or improves compliance with the service level object of the workload;

updating the set of admission rules to allow caching into the second level cache for data evicted from the first level cache when the workload is in the first operational region if the monitored service level objective statistics improve and the second level cache statistics improve; and

updating the set of admission rules to prevent caching into the second level cache for data evicted from the first level cache when the workload is in the first operational region if either the monitored service level objective statistics or the second level cache statistics do not improve.

20. One or more non-transitory machine-readable media having stored thereon instructions for storage layer compliance of service level objectives across a plurality of workloads, the instructions to:

determine a current phase of a first workload of the plurality of workloads based, at least in part, on a hit ratio in a first level cache of a storage system for the first workload in a time interval t and a slope value of the time interval t, wherein the slope value is based on a hit ratio in a second level cache of the storage system for the first workload in the time interval t and an amount used value of the second level cache for the first workload in the time interval t;

determine whether the current phase of the first workload has previously been observed;

in response to a determination that the current phase has not previously been observed,

determine a second level cache partition size for the current phase of the first workload based, at least in part, on a calculated hit ratio for the second level cache that corresponds to a service level objective indicated for the first workload in the time interval t;

associate the current phase with the hit ratio in the first level cache in t, the slope value of t, and the determined second level cache partition size;

in response to a determination that a preceding phase of the first workload is different than the current phase and that the current phase has been previously observed as phase n of the first workload,

determine a second level cache partition size indicated for phase n;

request allocation of the second level cache partition size indicated for phase n to the first workload;

in response to a determination that the current phase has been previously observed as phase n of the first workload and that a service level objective for the first workload is not being satisfied,

request allocation of the second level cache partition size indicated for phase n to the first workload if the amount used value of the second level cache for the first workload in time interval t is less than the second level cache partition size indicated for phase n of the first workload;

determine resizing of second level cache partitions allocated from the second level cache to the plurality of workloads in accordance with a set of one or more resizing requests and states of satisfaction of service level objectives across the plurality of workloads.

21. The non-transitory machine-readable media of claim 20, wherein the instructions further comprise instructions to:

in response to the determination that the current phase of the first workload has not previously been observed, request a resize to the determined second level cache partition size if a current allocation of the second level cache to the first workload is less than the determined second level cache partition size.

22. The non-transitory machine-readable media of claim 20, wherein the instructions further comprise instructions to:

map a plurality of first level cache hit ratios collected in the time interval t for the first workload into a set of one or more hit ratio ranges;

determine a first range of the set of one or more ranges that has a greatest number of the plurality of first level cache hit ratios;

calculate the hit ratio in the first level cache for the first workload in the time interval t based, at least in part, on those of the plurality of first level cache hit ratios that mapped to the first range;

calculate a plurality of slope values with a plurality of second level cache hit ratios for the first workload in the time interval t and a plurality of second level cache used amounts for the first workload during the time interval t;

calculate the slope value based, at least in part, on the plurality of slope values.

23. The non-transitory machine-readable media of claim 20, wherein the instructions further comprise instructions to:

determine, with service level objective statistics of the statistics, whether the first workload exceeds the service level objective for the first workload and whether the first workload is using less than the second level cache partition size indicated for phase n while the first workload is in phase n.

24. The non-transitory machine-readable media of claim 23, wherein the instructions further comprise instructions to reduce the second level cache partition size for phase n of the first workload based, at least in part, on a determination that the first workload exceeds the service level objective for the first workload and that the first workload is using less than the second level cache partition size indicated for phase n while the first workload is in phase n.

25. A storage system comprising:

a processor;

a first level of cache;

a non-volatile solid state storage device configured as a second level of cache for the storage system;

a machine-readable medium having stored therein instructions executable by the processor to cause the storage system to,

determine a current phase of a first workload of a plurality of workloads based, at least in part, on a hit ratio in a first level cache of a storage system for the first workload in a time interval t and a slope value of the time interval t, wherein the slope value is based on a hit ratio in a second level cache of the storage system for the first workload in the time interval t and an amount used value of the second level cache for the first workload in the time interval t;

determine whether the current phase of the first workload has previously been observed;

in response to a determination that the current phase has not previously been observed,

determine a second level cache partition size for the current phase of the first workload based, at least in part, on a calculated hit ratio for the second level cache that corresponds to a service level objective indicated for the first workload in the time interval t;

associate the current phase with the hit ratio in the first level cache in t, the slope value of t, and the determined second level cache partition size;

in response to a determination that a preceding phase of the first workload is different than the current phase and that the current phase has been previously observed as phase n of the first workload,

determine a second level cache partition size indicated for phase n;

request allocation of the second level cache partition size indicated for phase n to the first workload;

in response to a determination that the current phase has been previously observed as phase n of the first workload and that a service level objective for the first workload is not being satisfied,

request allocation of the second level cache partition size indicated for phase n to the first workload if the amount used value of the second level cache for the first workload in time interval t is less than the second level cache partition size indicated for phase n of the first workload;

determine resizing of second level cache partitions allocated from the second level cache to the plurality of workloads in accordance with a set of one or more resizing requests and states of satisfaction of service level objectives across the plurality of workloads.

26. The storage system of claim 25, wherein the instructions further comprise instructions executable by the processor to cause the storage system to:

in response to the determination that the current phase of the first workload has not previously been observed, request a resize to the determined second level cache partition size if a current allocation of the second level cache to the first workload is less than the determined second level cache partition size.

27. The storage system of claim 25, wherein the instructions further comprise instructions executable by the processor to cause the storage system to:

map a plurality of first level cache hit ratios collected in the time interval t for the first workload into a set of one or more hit ratio ranges;

determine a first range of the set of one or more ranges that has a greatest number of the plurality of first level cache hit ratios;

calculate the hit ratio in the first level cache for the first workload in the time interval t based, at least in part, on those of the plurality of first level cache hit ratios that mapped to the first range;

calculate a plurality of slope values with a plurality of second level cache hit ratios for the first workload in the time interval t and a plurality of second level cache used amounts for the first workload during the time interval t;

calculate the slope value based, at least in part, on the plurality of slope values.

28. The storage system of claim 25, wherein the instructions further comprise instructions executable by the processor to cause the storage system to:

determine, with service level objective statistics of the statistics, whether the first workload exceeds the service level objective for the first workload and whether the first workload is using less than the second level cache partition size indicated for phase n while the first workload is in phase n.

29. The storage system of claim 28, wherein the instructions further comprise instructions executable by the processor to cause the storage system to reduce the second level cache partition size for phase n of the first workload based, at least in part, on a determination that the first workload exceeds the service level objective for the first workload and that the first workload is using less than the second level cache partition size indicated for phase n while the first workload is in phase n.