Scheduling storage accesses for rate-guaranteed and non-rate-guaranteed requests

• US 20040205166A1
• Filed: 02/26/2004
• Published: 10/14/2004
• Est. Priority Date: 10/06/1999
• Status: Active Grant

• Current Assignee: Michael A. DeMoney
• Original Assignee: Michael A. DeMoney
• Inventors: DeMoney, Michael A.
• Granted Patent: US 8,566,432 B2
• Time in Patent Office: Days
• US Class Current: 709/219
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H04N 21/2326 Scheduling disk or memory reading operations
• CPC Class Codes: H04N 21/2396 characterized by admission policies admission control, resource allocation in open networks H04L12/5692; arrangements for network security using user profiles for access control H04L63/102; access security in wireless networks H04W12/08

Abstract

A system for managing storage accesses for rate guaranteed continuous data streams and non-rate-guaranteed storage requests may include a plurality of rate guaranteed requestors for data streams and one or more non-rate guaranteed requestors. A disk scheduler for the system may have a guaranteed rate queue for queuing storage requests from the rate guaranteed requestors and a non-rate-guaranteed queue for queuing requests from the non-rate-guaranteed requesters. The disk scheduler may include a bandwidth allocator coupled to the guaranteed rate queue and the non-rate-guaranteed queue. The bandwidth allocator may be configured to allocate bandwidth of a storage system between the guaranteed rate queue and the non-rate-guaranteed queue according to a predetermined ratio. The rate guaranteed requestors may be limited so that an aggregate of maximum stream rates guaranteed for each rate guaranteed requestor does not exceed the portion of the bandwidth allocated to the guaranteed rate queue.

Claims

1. A system for managing multiple rate guaranteed data stream requests, comprising:

an admission controller configured to negotiate a maximum stream rate with each of a plurality of rate guaranteed requesters; and

a disk scheduler, comprising;

a guaranteed rate queue for queuing storage requests from said rate guaranteed requesters; and

a bandwidth allocator coupled to said guaranteed rate queue, and further coupled to a storage system, wherein said bandwidth allocator is configured to allocate a predetermined portion of the bandwidth of the storage system to said guaranteed rate queue;

wherein the admission controller is further configured to allow an additional rate guaranteed request only if an aggregate of negotiated maximum stream rates for all current rate guaranteed requests and the additional rate guaranteed request does not exceed a calculated throughput, wherein said calculated throughput is based on said predetermined portion.

2. The system as recited in claim 1, wherein the disk scheduler further comprises a non-rate-guaranteed queue for queuing requests from non-rate-guaranteed requesters, wherein said bandwidth allocator is configured to allocate bandwidth of the storage system between said guaranteed rate queue and said non-rate-guaranteed queue according to a predetermined ratio.

3. The system as recited in claim 2, wherein said bandwidth allocator is configured to migrate requests from said guaranteed rate queue and said non-rate-guaranteed queue to the storage system according to the predetermined ratio, wherein bandwidth not used by said guaranteed rate queue is made available to said non-rate-guaranteed queue.

4. The system as recited in claim 2, wherein said bandwidth allocator is configured to migrate requests from said guaranteed rate queue and said non-rate-guaranteed queue to the storage system according to the predetermined ratio, wherein bandwidth not used by said non-rate-guaranteed queue is made available to said guaranteed rate queue.

5. The system as recited in claim 1, wherein requests are ordered in said guaranteed rate queue according to a deadline, wherein the deadline for each request indicates a latest time by which that request must be fulfilled to meet a guaranteed maximum stream rate for the corresponding stream.

6. The system as recited in claim 1, wherein the disk scheduler is repeated for each of a plurality of storage systems.

7. The system as recited in claim 1, further comprising a buffer ring for each stream for one of the rate guaranteed requesters, wherein said buffer ring buffers stream data between an associated rate-guaranteed requester and the disk scheduler.

8. The system as recited in claim 7, wherein said buffer ring contains a number of buffers chosen to prevent buffer underrun at a guaranteed maximum stream rate, wherein each buffer is sized to hold one block of data.

9. The system as recited in claim 8, wherein the buffers of each buffer ring are consumed by the associated rate guaranteed requester one after another in a circular order, wherein as each buffer is consumed, a request and a deadline for the just consumed buffer is issued to the guaranteed rate queue, wherein the deadline indicates a time by which the request must be fulfilled to prevent underrun.

10. The system as recited in claim 9, wherein each deadline is calculated as:

current_time+(N−

1)*buf_time;

wherein current_time is a time reference for the system, N is the number of buffers in the corresponding buffer ring, and buf_time is the minimum time in which the stream requestor can consume one of the buffers without exceeding the guaranteed maximum stream rate.

11. The system as recited in claim 1, wherein said calculated throughput is further based on a characterized maximum sustainable throughput for the storage system.

12. The system as recited in claim 11, wherein said calculated throughput is further based on said characterized maximum sustainable throughput for the storage system decreased by a configurable derate parameter.

13. The system as recited in claim 11, wherein said characterized maximum sustainable throughput is characterized by:

creating a synthetic load of data blocks in the storage system; and

determining said maximum sustainable throughput using said synthetic load.

14. The system as recited in claim 13, wherein said creating a synthetic load comprises allocating blocks randomly in inner and outer storage disk zones, wherein said allocating blocks randomly alternates between the inner and outer zones.

15. The system as recited in claim 1, wherein the admission controller is further configured to allow an additional rate guaranteed request only if sufficient memory is available for buffering to be established for the additional rate guaranteed request sufficient to prevent underrun at the negotiated maximum stream rate.

16. A method for managing multiple rate guaranteed data stream requests, the method comprising:

negotiating a maximum stream rate with each of a plurality of rate guaranteed requesters

allocating a predetermined portion of a storage system'"'"'s bandwidth to stream requests from said rate guaranteed requesters; and

admitting an additional rate guaranteed request only if an aggregate of negotiated maximum stream rates for all current rate guaranteed requests and the additional rate guaranteed request does not exceed a calculated throughput, wherein said calculated throughput is based on said predetermined portion.

17. The method as recited in claim 16, further comprising:

allocating a remaining portion of the storage system'"'"'s bandwidth to requests from non-rate-guaranteed requesters;

queuing storage requests from rate guaranteed requesters in a guaranteed rate queue;

queuing storage requests from non-rate-guaranteed requesters in a non-rate-guaranteed queue; and

selecting either the guaranteed rate queue or the a non-rate-guaranteed queue according to the bandwidth allocation to migrate one of the requests to the storage system.

18. The method as recited in claim 17, further comprising dynamically reallocating unused bandwidth for rate guaranteed requests to non-rate-guaranteed requests.

19. The method as recited in claim 17, further comprising dynamically reallocating unused bandwidth for non-rate-guaranteed requests to rate guaranteed requests.

20. The method as recited in claim 17, further comprising ordering requests in said guaranteed rate queue according to a deadline, wherein the deadline for each requests indicates a latest time by which that request must be fulfilled to meet a guaranteed maximum stream rate for a corresponding multimedia data stream.

21. The method as recited in claim 16, further comprising establishing a buffer ring for each data stream from one of the rate guaranteed requesters, said buffer ring buffering stream data between an associated rate-guaranteed requester and the storage system.

22. The method as recited in claim 21, further comprising sizing said buffer ring to contain a number of buffers chosen to prevent buffer underrun at a guaranteed maximum stream rate, wherein each buffer is sized to hold one block of multimedia data.

23. The method as recited in claim 22, further comprising:

consuming the buffers of each buffer ring by the associated rate guaranteed requester one after another in a circular order; and

as each buffer is consumed, issuing a request and a deadline for the just consumed buffer to a guaranteed rate queue, wherein the guaranteed rate queue queues storage requests from rate guaranteed requesters, wherein the deadline indicates a time by which the request must be fulfilled to prevent underrun.

24. The method as recited in claim 23, further comprising calculating each deadline as:

current_time+(N−

1)*buf_time;

wherein current_time is a time reference for the system, N is the number of buffers in the corresponding buffer ring, and buf_time is the minimum time in which the rate guaranteed requester can consume one of the buffers without exceeding the guaranteed maximum stream rate.

25. The method as recited in claim 16, further comprising determining said calculated throughput, wherein said wherein said determining said calculated throughput comprises characterizing a maximum sustainable throughput for the storage system, wherein said calculated throughput is further based on said characterized maximum sustainable throughput.

26. The method as recited in claim 25, wherein said determining said calculated throughput comprises basing said calculated throughput on said characterized maximum sustainable throughput decreased by a configurable derate parameter.

27. The method as recited in claim 25, wherein said characterizing a maximum sustainable throughput comprises:

creating a synthetic load of data blocks in the storage system; and

determining said maximum sustainable throughput using said synthetic load.

28. The method as recited in claim 27, wherein said creating a synthetic load comprises allocating blocks randomly in inner and outer storage disk zones, wherein said allocating blocks randomly alternates between the inner and outer zones.

29. The method as recited in claim 16, wherein said admitting an additional rate guaranteed request comprises admitting an additional rate guaranteed request only if sufficient memory is available for establishing buffering for the additional rate guaranteed request sufficient to prevent underrun at the negotiated maximum stream rate.