Storage-assisted quality of service (QoS)

• US 6,901,484 B2
• Filed: 06/05/2002
• Issued: 05/31/2005
• Est. Priority Date: 06/05/2002
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kaminsky, David L., Doyle, Ronald P., Ogle, David M.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): HO, THANG H
• Application Number:
  US10/162,966
• Publication Number:
  US 20030229760A1
• Time in Patent Office: 1,091 Days
• Field of Search: 711/134, 711/135, 711/133, 370/351
• US Class Current: 711/134
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2212/6042 Allocation of cache space to multiple users or processors
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems

Abstract

Storage-Assisted QoS. To provide storage-assisted QoS, a discriminatory storage system able to enforce a service discrimination policy within the storage system can include re-writable media; a storage system controller; a cache; and, a QoS enforcement processor configured to selectively evict entries in the cache according QoS terms propagated into the storage system through the storage system controller.

Claims

1. A storage system comprising:

re-writable media;

a storage system controller;

a cache; and

,

a Quality of Service (QoS) enforcement processor configured to selectively evict entries in said cache according to QoS terms propagated into the storage system through said storage system controller, said QoS terms specifying a guaranteed level of responsiveness minimally owed to particular requestors of content.

2. In a storage system, a cache eviction method comprising the steps of:

categorizing entries in a cache according to common Quality of Service (QoS) metrics, said QoS metrics specifying a guaranteed level of responsiveness minimally owed to particular requestors of content;

identifying categorizations whose entries consume an excessive portion of said cache; and

,

evicting an entry from among one of said identified categorizations.

3. The method of claim 2, wherein said identifying step comprises the steps of:

computing a weighted average of entries in said cache for each of said categorized entries; and

,

identifying categorizations which have a weighted average which exceed a corresponding preferred allocation.

4. The method of claim 3, wherein said computing step comprises the steps of:

for each category from among j total categories, computing an average according to the equation (Requests)(QoS Metric_j)/Requests(Total); and

,

weighting each computed average by QoS Metric_j.

5. The method of claim 3, wherein said identifying step comprises the steps of:

establishing a threshold hysterisis value; and

,

identifying only those categorizations which have a weighted average which exceeds said corresponding preferred allocation by at least said threshold hysterisis value.

6. The method of claim 3, wherein said evicting step comprises the step of evicting an entry from among one of said identified categorizations whose weighted average most exceeds said corresponding preferred allocation.

7. The method of claim 3, wherein said evicting step further comprises evicting said entry according to a cache replacement methodology selected from the group consisting of least recently used, first-in first-out, last-in first out, and least frequently used.

8. A method for enforcing Quality of Service (QoS) terms in a storage system, the QoS terms specifying a guaranteed level of responsiveness minimally owed to particular requestors of content, said method comprising the steps of:

(A) propagating a QoS metric into the storage system in conjunction with a request to retrieve data from the storage system;

(B) locating said data in a caching component in the storage system;

(C) if said data can be located, retrieving said data from said caching component; and

,

(D) if said data cannot be located;

(1) retrieving said data from fixed storage in the storage system,

(2) determining whether said caching component can accommodate a new cache entry,

(3) if said caching component cannot accommodate a new cache entry;

(a) selecting an existing cache entry from among a group of cache entries which share a common QoS metric, but which have consumed more cache then permitted according to said common QoS metric, and,

(b) evicting said selected cache entry,

(4) caching said data retrieved from fixed storage in said caching component along with said propagated QoS metric.

9. A machine readable storage having stored thereon a computer program for performing cache eviction in a storage system, said computer program comprising a routine set of instructions for causing the machine to perform the steps of:

categorizing entries in a cache according to common Quality of Service (QoS) metrics, said QoS metrics specifying a guaranteed level of responsiveness minimally owed to particular requestors of content;

identifying categorizations whose entries consume an excessive portion of said cache; and

,

evicting an entry from among one of said identified categorizations.

10. The machine readable storage of claim 9, wherein said identifying step comprises the steps of:

computing a weighted average of entries in said cache for each of said categorized entries; and

,

identifying categorizations which have a weighted average which exceed a corresponding preferred allocation.

11. The machine readable storage of claim 10, wherein said computing step comprises the steps of:

for each category from among j total categories, computing an average according to the equation (Requests)(QoS Metric_j)/Requests(Total); and

,

weighting each computed average by QoS Metric_j.

12. The machine readable storage of claim 10, wherein said identifying step comprises the steps of:

establishing a threshold hysterisis value; and

,

identifying only those categorizations which have a weighted average which exceeds said corresponding preferred allocation by at least said threshold hysterisis value.

13. The machine readable storage of claim 10, wherein said evicting step comprises the step of evicting an entry from among one of said identified categorizations whose weighted average most exceeds said corresponding preferred allocation.

14. The machine readable storage of claim 10, wherein said evicting step further comprises evicting said entry according to a cache replacement methodology selected from the group consisting of least recently used, first-in first-out, last-in first out, and least frequently used.

15. A machine readable storage having stored thereon a computer program for enforcing Quality of Service (QoS) terms in a storage system, the QoS terms specifying a guaranteed level of responsiveness minimally owed to particular requestors of content, said computer program comprising a routine set of instructions for causing the machine to perform the steps of:

(A) propagating a QoS metric into the storage system in conjunction with a request to retrieve data from the storage system;

(B) locating said data in a caching component in the storage system;

(C) if said data can be located, retrieving said data from said caching component; and

,

(D) if said data cannot be located;

(1) retrieving said data from fixed storage in the storage system,

(2) determining whether said caching component can accommodate a new cache entry,

(3) if said caching component cannot accommodate a new cache entry;

(a) selecting an existing cache entry from among a group of cache entries which share a common QoS metric, but which have consumed more cache then permitted according to said common QoS metric, and,

(b) evicting said selected cache entry,

(4) caching said data retrieved from fixed storage in said caching component along with said propagated QoS metric.