Sieved caching for increasing data rate capacity of a heterogeneous striping group

• US 6,742,019 B1
• Filed: 07/23/1999
• Issued: 05/25/2004
• Est. Priority Date: 07/23/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dan, Asit, Song, Junehwa, Sitaram, Dinkar
• Primary Examiner(s): Thompson, Marc D.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US09/360,324
• Time in Patent Office: 1,768 Days
• Field of Search: 709/204, 709/231, 709/225, 709/202, 709/217, 709/232, 709/226, 709/234, 709/105, 709/218, 709/245, 709/212, 709/102, 709/227, 711/112, 711/114, 711/113, 711/119, 711/118, 711/111, 714/5, 370/310, 370/233, 370/230, 370/412, 370/60, 370/422, 710/4, 710/131, 710/60, 725/92, 725/115, 345/328, 345/169, 358/1.14, 340/825, 375/240
• US Class Current: 709/213
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/2318 using striping
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Under the present invention, a small cache is used for the selective buffering of devices of a heterogeneous striping group (i.e., striping group made of devices with unequal capacities) to match the load on each device to its capacity. The inventive caching algorithm utilizes a device map, or disk map, and applies a cache distribution factor for each device of a group to determined how to selectively buffer blocks read from different devices of a striping group; thereby placing different loads on the different devices of a striping group in accordance with their capacities.

Claims

1. A method for increasing the data rate for provision of data from a plurality of devices in a striping group associated with a server in response to client requests comprising the steps of:

evaluating the respective capabilities of each of the plurality of devices in the striping group;

retrieving data in response to a first client request;

determining if said data is to be used again for a successive client request; and

selectively caching data from said plurality of devices, which data is to be used for a successive client request, in accordance with said capabilities.

2. The method of claim 1 wherein said selectively caching comprises caching data from less than all of said plurality of devices.

3. The method of claim 1 wherein said selectively caching comprises caching less than all of said data.

4. The method of claim 1 wherein said selectively caching comprises caching non-consecutive data.

5. The method of claim 1 wherein said selectively caching comprises the steps of:

identifying data to be cached;

computing the number of cache blocks required to store said identified data to be cached; and

determining if said identified data can be cached based on said computed number of cache blocks.

6. The method of claim 5 wherein at least one interval is already stored at said cache and wherein said determining if said data can be cached further comprises deallocating at least one interval from said cache.

7. The method of claim 1 wherein said evaluating said respective capacities comprises calculating a cache distribution factor for each of said plurality of devices.

8. The method of claim 1 wherein said retrieving data comprises the steps of:

determining if a preceding stream exists for said data;

ascertaining the storage location for said preceding stream; and

accessing said preceding stream from its storage location.

9. A server for optimizing the data rate for provision of requested data to a client, said data being stored in a striping group comprising a plurality of devices associated with said server, comprising:

at least one cache memory for storing data;

a cache manager for receiving client requests for data, said cache manager comprising a cache management component for selectively caching data from said plurality of devices in said striping group; and

wherein said server comprises at least one component for evaluating the respective capabilities of each of the plurality of devices and wherein said selectively caching data from said plurality of devices in said striping group comprises caching based on said respective capabilities.

10. The server of claim 9 wherein said cache management component comprises said at least one component for evaluating the respective capabilities of each of the plurality of devices.

11. The server of claim 10 wherein said at least one component for evaluating the respective capabilities of each of said plurality of devices comprises a disk map component for assigning at least a cache distribution factor to each of said plurality of devices.

12. The server of claim 10 wherein said at least one component for evaluating the respective capabilities of each of said plurality of devices comprises a disk access table including at least a cache distribution factor to each of said plurality of devices.

13. The server of claim 9 wherein said cache manager further comprises a component for determining if said requested data is to be used again for a successive client request.

14. The server of claim 9 wherein said cache management component includes means for identifying data to be cached;

computing the number of cache blocks required to store said identified data to be cached; and

determining if said identified data can be cached based on said computed number of cache blocks.

15. The system of claim 14 wherein at least one interval is already stored at said cache and wherein said determining if said data can be cached further comprises deallocating at least one interval from said cache.

16. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for a cache management component to increase the data rate for provision of data from a plurality of devices in a striping group associated with the component in response to client requests, said method steps comprising:

evaluating the respective capabilities of each of the plurality of devices in the striping group;

retrieving data in response to a first client request;

determining if said data is to be used again for a successive client request; and

selectively caching data from said plurality of devices, which data is to be used for a successive client request, in accordance with said capabilities.

17. A video server for optimizing the data rate for provision of requested video data to a client, said video data being stored in a striping group comprising a plurality of devices associated with said video server, comprising:

at least one cache memory for storing video data; and

a cache manager for receiving client requests for video data, said cache manager comprising a cache management component for selectively caching data from said plurality of devices in said striping group, said cache management component including at least one device access data structure for evaluating the respective capabilities of each of the plurality of devices, and wherein said selectively caching data from said plurality of devices in said striping group comprises caching based on said respective capabilities.

18. The video server of claim 17 further comprising a component for determining if said requested video data is to be used again for a successive client request.

19. The video server of claim 17 wherein said cache management component includes means for identifying data to be cached;

computing the number of cache blocks required to store said identified data to be cached; and

determining if said identified data can be cached based on said computed number of cache blocks.

20. The video server of claim 19 wherein at least one interval is already stored at said cache and wherein said cache management component deallocates at least one interval from said cache.