System, apparatus and method for multi-level cache in a multi-processor/multi-controller environment

• US 6,460,122 B1
• Filed: 09/30/1999
• Issued: 10/01/2002
• Est. Priority Date: 03/31/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Short, Keith E., Skazinski, Joseph G., Brant, William A., Otterness, Noel S.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US09/409,929
• Time in Patent Office: 1,097 Days
• Field of Search: 711/114, 711/113, 711/122, 711/139, 711/154, 711/216, 711/136, 711/141
• US Class Current: 711/154
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2211/1009 Cache, i.e. caches used in RAID system with parity
• CPC Class Codes: G06F 2211/1054 Parity-fast hardware, i.e. dedicated fast hardware for RAID systems with parity
• CPC Class Codes: G06F 2212/312 In storage controller

Abstract

This inventive provides a multiple level cache structure and multiple level caching method that distributes I/O processing loads including caching operations between processors to provide higher performance I/O processing, especially in a server environment. A method of achieving optimal data throughput by taking full advantage of multiple processing resources is disclosed. A method for managing the allocation of the data caches to optimize the host access time and parity generation is disclosed. A cache allocation for RAID stripes guaranteed to provide fast access times for the XOR engine by ensuring that all cache lines are allocated from the same cache level is disclosed. Allocation of cache lines for RAID levels which do not require parity generation and are allocated in such manner as to maximize utilization of the memory bandwidth is disclosed. Parity generation which is optimized for use of the processor least utilized at the time the cache lines are allocated, thereby providing for dynamic load balancing amongst the multiple processing resources, is disclosed. An inventive cache line descriptor for maintaining information about which cache data pool the cache line resides within, and an inventive cache line descriptor which includes enhancements to allow for movement of cache data from one cache level to another is disclosed. A cache line descriptor with enhancements for tracking the cache within which RAID stripe cache lines siblings reside is disclosed. System, apparatus, computer program product, and methods to support these aspects alone and in combination are also provided.

Claims

1. In a computer I/O processing system having a plurality of processing resources, a method of optimizing data throughput to achieve maximum memory bandwidth, the method comprising steps of:

(a) providing a data cache in each of said plurality of processing resources configured to store the data;

(b) processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches;

(c) tracking the data within the plurality of processing resources and the data caches; and

(d) communicating between and among the plurality of processing resources when moving data to and from any of the data caches and invalidating data in any of the data caches, except a system level (primary) cache, to keep the data consistent in the data caches.

2. The method of claim 1, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers.

3. The method of claim 1, wherein each said cache includes a plurality of cache lines, and step (b) further includes steps of:

(b)(i) allocating data to a cache line in said at least some of said plurality of cache lines;

(b)(ii) searching each of the data caches for a particular cache line; and

(b)(iii) performing parity generation operations to encode and decode the data.

4. The method of claim 3, further including steps of:

(b)(iv) accepting data from a host system;

(b)(v) reading data from a system drive; and

(b)(vi) writing data to the system drive.

5. The method of claim 1, wherein processing the data in parallel excludes processing data stored or retrieved from RAID stripes which are processed in parallel by a SCSI input/output processor in conjunction with a cache system, where the SCSI input/output processor reads data blocks and parity from the disk subsystem into cache.

6. The method of claim 1, wherein the step of processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches excludes processing of a SCSI Chip.

7. The method of claim 1, wherein the step of processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches excludes processing of a RAID disk subsystem.

8. The method of claim 1, wherein the step of processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches utilizes a plurality of data paths.

9. The method of claim 1, wherein the step of communicating between and among the plurality of processing resources and data caches utilizes a plurality of data paths.

10. The method of claim 1, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers, such that the combination of multiple processors and multiple controllers does not include a SCSI chip.

11. The method of claim 1, wherein each said cache includes a plurality of cache lines, and step (b) further includes steps of:

(b)(i) allocating data to a cache line in said at least some of said plurality of cache lines;

(b)(ii) searching each of the data caches for a particular cache line, such that the data caches does not include data caches of a SCSI chip; and

(b)(iii) performing parity generation operations to encode and decode the data.

12. The method of claim 1, wherein the plurality of processing resources are coupled with a plurality of data paths among at least some of said plurality of processing resources.

13. The method of claim 1, wherein the processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches is in addition to any processing performed by SCSI chip or processing performed by a RAID Disk Subsystem.

14. The method of claim 1, wherein the processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches excludes SCSI input/output processor.

15. The method of claim 1, wherein the tracking the data in parallel among at least some of said plurality of processing resources and corresponding data caches utilizes a multiple level hash table.

16. The method of claim 1, wherein the communicating between and among the plurality of processing resources when moving data to and from any of the data caches and invalidating data in any of the data caches, except a system level (primary) cache, to keep the data consistent in the data caches is in addition to any processing performed by SCSI chip or processing performed by a RAID Disk Subsystem.

17. In a computer I/O processing system having a plurality of processing resources, a method of managing an allocation of data caches to optimize host access to the plurality of processing resources and parity generation for optimization of data throughput to achieve maximum memory bandwidth, the method comprising steps of:

(a) performing a first table lookup operation to identify data contained in a system level (primary) cache;

(b) performing a second table lookup operation to identify data that can be brought from a secondary cache in a single I/O operation;

(c) allocating caches for the data in order to optimize parity generation; and

(d) automatically promoting and demoting the data from one cache level to another in response to a read/write operation.

18. The method of claim 17, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers.

19. The method of managing the allocation of data caches in claim 17, wherein the data comprises a RAID stripe to provide fast access time for the computer I/O processing system, the method further comprising a step of:

(e) allocating all cache lines from the same cache level so that parity data and associated write data are maintained at the same cache level.

20. The method of claim 17, wherein step (c) further includes steps of:

(c)(i) determining an RAID level of a system drive;

(c)(ii) when the RAID level is RAID level 3 or RAID level 5, determining if any of the cache lines which form the RAID stripe (sibling cache lines) are allocated and the data cache of allocation; and

(c)(ii) querying a stripe hash table data structure to determine if the data is already contained within any of the data caches based on a host sector address on the system drive.

21. The method of claim 20, further including steps of:

(c)(iv) searching for a segment of the data in a data hash table;

(c)(v) searching for the segment of the data in the data cache;

(c)(vi) removing the cache line from a least recently used (LRU) list;

(c)(vii) allocating a new cache line to hold the segment of the data;

(c)(viii) unlocking a cache line, to release the cache line;

(c)(ix) adding the cache line to the LRU list for reuse;

(c)(x) locking a cache line to prevent it from been reused or being released; and

(c)(ix) setting an operational state for a cache line based on the data in the cache line and the operation performed on the cache line.

22. The method of claim 21, wherein the plurality of processing resources are selected from the group consisting:

of multiple processors, multiple controllers, or a combination of multiple processors and multiple controllers; and

parity generation is optimized to use a select one of the plurality processing resources which is least utilized at the time the cache lines are allocated for dynamic load balancing amongst the plurality of processing resources of the system.

23. The method of claim 17, wherein the cache lines for RAID levels do not require parity generation and the cache lines are allocated to maximize memory bandwidth to a host interface, step (c) further including steps of:

(c)(i) determining cache line availability for a split-cache; and

(c)(ii) determining which cache line was last allocated.

35. The apparatus of claim 17, wherein the plurality of processing resources excludes SCSI I/O processors (SIOP).

24. A cache line descriptor (CLD) data structure embodied in a computer readable medium in a computer system I/O processing system, wherein the CLD data structure maintains information for identification of a cache data pool in which a cache line resides, the data structure comprised of:

a system drive field indicating the system drive where data is read/written;

a sector field indicating a starting sector of the data on the system drive;

a number of blocks field indicating a size of a host read request;

a cache level field for storing an integer value of the cache level of each data stripe;

a next least recently used (LRU) link field and a previous LRU link field for maintaining a linked list of pointers to a next line in a LRU chain and a previous line in the LRU chain to handle reuse of a cache line that is not in use;

a next hash link field and a previous hash link field for maintaining a linked list of pointers to a next line in a hash link and a previous line in a hash link to enable finding a cache line based on a system drive and a sector number; and

a next stripe link field and a previous stripe link field for maintaining a linked list of pointers to all cache lines that are part of a RAID stripe.

25. The data structure of claim 24, wherein the CLD data structure allows movement of cache data from one cache level to another by a tracking the writing of the host data to disk and updating the cache level field, and also tracking the generation of parity for the RAID stripe that the cache line is part of, the data structure further including:

an XOR engine field for storing a value identifying an XOR engine that performs the parity calculation for data moved to another cache level; and

a copy complete field for storing an indicator used to indicate a start of a direct memory access (DMA) operation and a completion of the DMA operation when a copy is required to another data cache.

26. The data structure of claim 24, wherein the CLD data structure tracks the cache lines that form the RAID stripe (cache line siblings) and the data cache the cache line siblings reside within, such that the system drive field, the sector field and the number of blocks field are set to an invalid value and the next stripe link field and the previous stripe link field are set to zero to indicate that the cache line is no longer part of the RAID stripe.

27. An apparatus for processing input/output transactions in a computer system to increase data throughput and memory bandwidth, said apparatus comprising:

a plurality of processing resources and a data cache in each of said plurality of processing resources configured to store data, said processing resources and data caches being coupled for communication to move said data between said processing resources and data caches;

tracking and control logic processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches and maintaining information as to the location of data within the plurality of processing resources and the data caches;

communication means for moving said data between and among any of the data caches; and

data validation logic for validating and invalidating data in any of the data caches, except a system level cache, to keep the data consistent in the data caches.

28. The apparatus of claim 27, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers.

29. The apparatus of claim 27, wherein each said cache includes a plurality of cache lines, and said processing resources and data caches are adapted for allocating data to a cache line in said at least some of said plurality of cache lines;

searching each of the data caches for a particular cache line; and

performing parity generation operations to encode and decode the data.

30. The apparatus of claim 29, wherein and said processing resources and data caches are further adapted for accepting data from a host system;

reading data from a system drive; and

writing data to the system drive.

31. The apparatus of claim 30, further comprising means for managing allocation of data caches to optimize host access to the plurality of processing resources and parity generation for optimization of data throughput to achieve maximum memory bandwidth.

32. The apparatus of claim 27, wherein the plurality of processing resources excludes a SCSI chip.

33. The apparatus of claim 27, wherein the plurality of processing resources excludes processing of a RAID disk subsystem.

34. The apparatus of claim 27, wherein the plurality of processing resources are coupled with a plurality of data paths.

36. The apparatus of claim 27, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers such that the combination of multiple processors and multiple controllers does not include a SCSI chip.

37. An apparatus for processing input/output transactions in a computer system to increase data throughput and memory bandwidth, said apparatus comprising:

a plurality of processing resources and a data cache in each of said plurality of processing resources configured to store data, said processing resources and data caches being coupled for communication to move said data between said processing resources and data caches;

tracking and control logic processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches and maintaining information as to the location of data within the plurality of processing resources and the data caches;

communication means for moving said data between and among any of the data caches;

data validation logic for validating and invalidating data in any of the data caches, except a system level cache, to keep the data consistent in the data caches;

wherein each said cache includes a plurality of cache lines, and said processing resources and data caches are adapted for allocating data to a cache line in said at least some of said plurality of cache lines;

searching each of the data caches for a particular cache line; and

performing parity generation operations to encode and decode the data;

wherein and said processing resources and data caches are further adapted for accepting data from a host system;

reading data from a system drive; and

writing data to the system drive;

further comprising means for managing allocation of data caches to optimize host access to the plurality of processing resources and parity generation for optimization of data throughput to achieve maximum memory bandwidth;

first and second look-up tables, said first table operative to identify data contained in a system level cache, and said second table lookup operative to identify data that can be brought from a secondary cache in a single I/O operation; and

a cache allocation manager allocating caches for the data in order to optimize parity generation, and automatically promoting and demoting the data from one cache level to another in response to a read/write operation.

38. The apparatus of claim 37, wherein the plurality of processing resources are selected from the group consisting of multiple processors, multiple controllers, and a combination of multiple processors and multiple controllers.

39. The apparatus of claim 37, wherein the data comprises a RAID stripe to provide fast access time for the computer I/O processing system, and said cache allocation manager allocating all cache lines from the same cache level so that parity data and associated write data are maintained at the same cache level.

40. The apparatus of claim 37, wherein said cache allocation manager being operable to determining an RAID level of a system drive, and when the RAID level is RAID level 3 or RAID level 5, determining if any of the cache lines which form the RAID stripe are allocated and the data cache of allocation, and querying a stripe hash table data structure to determine if the data is already contained within any of the data caches based on a host sector address on the system drive.

41. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the computer system or components thereof, to function in a specified manner to improve data throughput to achieve improved memory bandwidth, the program module including instructions for;

defining a data cache in each of said plurality of processing resources configured to store the data;

processing the data in parallel among at least some of said plurality of processing resources and corresponding data caches;

tracking the data within the plurality of processing resources and the data caches; and

communicating between and among the plurality of processing resources when moving data to and from any of the data caches and invalidating data in any of the data caches, except a system level cache, to keep the data consistent in the data caches.

42. The computer program product of claim 41, wherein the instructions for tracking the data utilizes a multiple level hash table.

43. The computer program product of claim 41, wherein the program module includes instructions for communicating between and among the plurality of processing resources being coupled with a plurality of data paths.

44. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism, comprising:

a program module that directs the computer system or components thereof, to function in a specified manner to manage an allocation of data caches to improve host access to a plurality of processing resources and parity generation for improving data throughput to achieve maximum memory bandwidth, the program module including instructions for;

performing a first table lookup operation to identify data contained in a system level cache;

performing a second table lookup operation to identify data that can be brought from a secondary cache in a single I/O operation;

allocating caches for the data in order to optimize parity generation; and

automatically promoting and demoting the data from one cache level to another in response to a read/write operation.