Method for accelerating disk array write operations using segmented cache memory and data logging

• US 6,148,368 A
• Filed: 07/31/1997
• Issued: 11/14/2000
• Est. Priority Date: 07/31/1997
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: DeKoning, Rodney A.
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/904,107
• Time in Patent Office: 1,202 Days
• Field of Search: 711/113, 711/114, 711/129, 711/173, 711/118, 711/161, 711/162, 714/6, 710/53, 707/204
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/262 configured as RAID
• CPC Class Codes: G06F 2212/312 In storage controller

Abstract

Method and apparatus for accelerating write operations logging write requests in a log structured cache and by expanding the log structured cache using a cache-extension disk region. The log structured cache include a cache memory region partitioned into one or more write cache segments and one or more redundancy-data (parity) cache segments. The cache-extension disk region is a portion of a disk array separate from a main disk region. The cache-extension disk region is also partitioned into segments and is used to extend the size of the log structured cache. The main disk region is instead managed in accordance with storage management techniques (e.g., RAID storage management). The write cache segment is partitioned into multiple write cache segments so that when one is full another can be used to handle new write requests. When one of these multiple write cache segments is filled, it is moved to the cache-extension disk region thereby freeing the write cache segment for reuse. The redundancy-data (parity) cache segment holds redundancy data for recent write requests, thereby assuring integrity of the logged write request data in the log structured cache.

Claims

1. A method of utilizing cache memory in a disk storage subsystem to improve write operations, said method comprising the steps of:

a) partitioning said cache memory to logically define a plurality of log-structured write cache segments and at least one redundancy-data cache segment;

b) partitioning disk space in said subsystem to logically define log-structured cache region having at least one disk segment;

c) logging first write request data corresponding to received write requests in a first segment of said plurality of write cache segments until said first segment is full;

d) logging further write request data corresponding to received write requests in a second segment of said plurality of write cache segments in response to said first segment being full;

e) accumulating, in said redundancy-data cache segment, redundancy data corresponding to said first write request data;

f) moving said first write request data from said first write cache segment to one of said at least one disk segment in response to accumulating said redundancy data; and

g) repeating steps c) through f) where said second segment is used as said first segment.

2. The method of claim 1 wherein said disk space includes a main disk region distinct from said log-structured cache region for persistent storage of data and wherein the method further comprises the steps of:

determining to flush said first write request data from said one of said at least one disk segment to said main disk region;

reading said first write request data from said one of said at least one disk segment into a memory buffer;

subtracting redundancy data corresponding to said first segment in said memory buffer from said redundancy-data cache segment;

processing said first write request data in said memory buffer to store data contained therein in said main disk region; and

freeing said one of said at least one disk segment for reuse.

3. The method of claim 2 wherein the step of processing includes the steps of:

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said at least one disk segment; and

posting, to said main disk region, any write request data remaining valid in said memory buffer.

4. The method of claim 3 wherein said main disk region is managed in accordance with RAID storage techniques and wherein the step of posting includes the steps of:

performing write requests represented in said write request data remaining valid in said memory buffer in accordance with said RAID storage techniques.

5. The method of claim 3 wherein said cache memory includes at least one standard cache segment and wherein the step of processing further includes the steps of:

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said at least one disk segment; and

adding data associated with said write request data remaining valid in said memory buffer to said at least one standard cache segment.

6. The method of claim 5 further comprising the steps of:

receiving a read request to read data from said subsystem;

locating data requested by said read request in one of said plurality of write segments; and

locating said data requested by said read request in one of said at least one disk segment in response to a failure to locate said data requested by said read request in said plurality of write segments.

7. The method of claim 6 further comprising the step of:

locating said data requested by said read request in one of said at least one standard cache segment in response to a failure to locate said data requested by said read request in said one of said at least one disk segment.

8. The method of claim 1 wherein said at least one redundancy-data cache segments comprises a plurality of redundancy-data cache segments and wherein each of said plurality of redundancy-data cache segments is associated with a distinct subset of said plurality of write cache segments and wherein the step of accumulating comprises the step of:

e.1) accumulating, in the redundancy-data cache segment associated with the distinct subset including said first segment, redundancy data corresponding to said first write request data.

9. The method of claim 8 further comprising the step of:

e.2) switching to another distinct subset of said plurality of write cache segments and an associated one of said plurality of redundancy-data cache segments in response to filling of all write cache segments in a first distinct subset of said plurality of write cache segments.

10. The method of claim 1 wherein said at least one disk segment is distributed over a plurality of disk drives in a cache-extension disk region.

11. The method of claim 1 wherein said cache-extension disk region includes at least one redundancy-data disk segment and wherein the method further comprises the steps of:

f.1) moving said redundancy-data cache segment to one of said at least one redundancy-data disk segment in response said first write request data from said first write cache segment to one of said at least one disk segment.

12. A method for logging write requests in a disk storage subsystem to improve write operation performance, said method comprising the steps of:

partitioning a cache memory associated with said disk storage subsystem to logically define a plurality of log-structured write cache segments;

partitioning disk space in said subsystem to logically define a log-structured cache region having at least one disk segment;

logging first write request data corresponding to received write requests in a first segment of said plurality of write cache segments; and

moving said write request data from said first write cache segment to one of said at least one disk segment in response to filling of said first segment.

13. The method of claim 12 further comprising the steps of:

logging further write request data corresponding to received write requests in a second segment of said plurality of write cache segments in response to filling of said first segment; and

freeing said first segment for re-use in response to completion of said moving of write request data from said first segment to said one of said at least one disk segment.

14. The method of claim 13 further comprising the steps of:

further partitioning said cache memory to logically define at least one redundancy-data cache segment; and

accumulating, in said at least one redundancy-data cache segment, redundancy data corresponding to said first write request data.

15. The method of claim 14 wherein said disk space includes a main disk region distinct from said log-structured cache region for persistent storage of data and wherein the method further comprises the steps of:

determining to flush said first write request data from said one of said at least one disk segment to said main disk region;

reading said first write request data from said one of said at least one disk segment into a memory buffer;

subtracting redundancy data corresponding to said first write request data in said memory buffer from said redundancy-data cache segment;

processing said first write request data in said memory buffer to store data contained therein in said main disk region; and

freeing said one of said at least one disk segment for reuse.

16. The method of claim 15 wherein the step of processing includes the steps of:

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said at least one disk segment; and

posting, to said main disk region, any write request data remaining valid in said memory buffer.

17. The method of claim 16 wherein said main disk region is managed in accordance with RAID storage techniques and wherein the step of posting includes the steps of:

performing write requests represented in said write request data remaining valid in said memory buffer in accordance with said RAID storage techniques.

18. The method of claim 16 wherein said cache memory includes at least one standard cache segment and wherein the step of processing further includes the steps of:

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said at least one disk segment; and

adding data associated with said write request data remaining valid in said memory buffer to said at least one standard cache segment.

19. The method of claim 18 further comprising the steps of:

receiving a read request to read data from said subsystem;

locating data requested by said read request in one of said plurality of write segments; and

locating said data requested by said read request in one of said at least one disk segment in response to a failure to locate said data requested by said read request in said plurality of write segments.

20. The method of claim 19 further comprising the step of:

locating said data requested by said read request in one of said at least one standard cache segment in response to a failure to locate said data requested by said read request in said one of said at least one disk segment.

21. The method of claim 14 wherein said at least one redundancy-data cache segments comprises a plurality of redundancy-data cache segments and wherein each of said plurality of redundancy-data cache segments is associated with a distinct subset of said plurality of write cache segments and wherein the step of accumulating comprises the step of:

accumulating, in the redundancy-data cache segment associated with the distinct subset including said first segment, redundancy data corresponding to said first write request data.

22. The method of claim 21 further comprising the step of:

switching to another distinct subset of said plurality of write cache segments and an associated one of said plurality of redundancy-data cache segments in response to filling of all write cache segments in a first distinct subset of said plurality of write cache segments.

23. The method of claim 12 wherein said at least one disk segment is distributed over a plurality of disk drives in a cache-extension disk region.

24. The method of claim 12 wherein said cache-extension disk region includes at least one redundancy-data disk segment and wherein the method further comprises the steps of:

moving said redundancy-data cache segment to one of said at least one redundancy-data disk segment in response said first write request data from said first write cache segment to one of said at least one disk segment.

25. A computer readable storage medium tangibly embodying programmed instructions for performing a method for utilizing cache memory in a disk storage subsystem to improve write operations, the method comprising the steps of:

a) partitioning said cache memory to logically define a plurality of log-structured write cache segments and at least one redundancy-data cache segment;

b) partitioning disk space in said subsystem to logically define a log-structured cache region having at least one disk segment;

c) logging first write request data corresponding to received write requests in a first segment of said plurality of write cache segments until said first segment is full;

d) logging further write request data corresponding to received write requests in a second segment of said plurality of write cache segments in response to said first segment being full;

e) accumulating, in said redundancy-data cache segment, redundancy data corresponding to said first write request data;

f) moving said first write request data from said first write cache segment to one of said at least one disk segment in response to accumulating said redundancy data; and

g) repeating method steps c) through f) where said second segment is used as said first segment.

26. The storage medium of claim 25 wherein said disk space includes a main disk region distinct from said log-structured cache region for persistent storage of data and wherein the method further comprises the steps of:

determining to flush said first write request data from said one of said at least one disk segment to said main disk region;

reading said first write request data from said one of said at least one disk segment into a memory buffer;

subtracting redundancy data corresponding to said first segment in said memory buffer from said redundancy-data cache segment;

processing said first write request data in said memory buffer to store data contained therein in said main disk region; and

freeing said one of said at least one disk segment for reuse.

27. The storage medium of claim 26 wherein the method step of processing includes the steps of:

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said at least one disk segment; and

posting, to said main disk region, any write request data remaining valid in said memory buffer.

28. The storage medium of claim 27 wherein said main disk region is managed in accordance with RAID storage techniques and wherein the method step of posting includes the steps of:

performing write requests represented in said write request data remaining valid in said memory buffer in accordance with said RAID storage techniques.

29. The storage medium of claim 27 wherein said cache memory includes at least one standard cache segment and wherein the method step of processing further includes the steps of:

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said at least one disk segment; and

adding data associated with said write request data remaining valid in said memory buffer to said at least one standard cache segment.

30. The storage medium of claim 29 further comprising the steps of:

receiving a read request to read data from said subsystem;

locating data requested by said read request in one of said plurality of write segments; and

locating said data requested by said read request in one of said at least one disk segment in response to a failure to locate said data requested by said read request in said plurality of write segments.

31. The storage medium of claim 30 further comprising the step of:

locating said data requested by said read request in one of said at least one standard cache segment in response to a failure to locate said data requested by said read request in said one of said at least one disk segment.

32. The storage medium of claim 25 wherein said at least one redundancy-data cache segments comprises a plurality of redundancy-data cache segments and wherein each of said plurality of redundancy-data cache segments is associated with a distinct subset of said plurality of write cache segments and wherein the method step of accumulating comprises the step of:

e.1) accumulating, in the redundancy-data cache segment associated with the distinct subset including said first segment, redundancy data corresponding to said first write request data.

33. The storage medium of claim 32 wherein the method further comprises the step of:

e.2) switching to another distinct subset of said plurality of write cache segments and an associated one of said plurality of redundancy-data cache segments in response to filling of all write cache segments in a first distinct subset of said plurality of write cache segments.

34. The storage medium of claim 25 wherein said at least one disk segment is distributed over a plurality of disk drives in a cache-extension disk region.

35. The storage medium of claim 25 wherein said cache-extension disk region includes at least one redundancy-data disk segment and wherein the method further comprises the steps of:

f.1) moving said redundancy-data cache segment to one of said at least one redundancy-data disk segment in response said first write request data from said first write cache segment to one of said at least one disk segment.

36. A computer readable storage medium tangibly embodying programmed instructions for performing a method for logging write requests in a disk storage subsystem to improve write operation performance, said method comprising the steps of:

partitioning a cache memory associated with said disk storage subsystem to logically define a plurality of log-structured write cache segments;

partitioning disk space in said subsystem to logically define a log-structured cache region at least one disk segment;

logging first write request data corresponding to received write requests in a first segment of said plurality of write cache segments; and

moving said write request data from said first write cache segment to one of said at least one disk segment in response to filling of said first segment.

37. The storage medium of claim 36 wherein the method further comprises the steps of:

logging further write request data corresponding to received write requests in a second segment of said plurality of write cache segments in response to filling of said first segment; and

freeing said first segment for re-use in response to completion of said moving of write request data from said first segment to said one of said at least one disk segment.

38. The storage medium of claim 37 wherein the method further comprises the steps of:

further partitioning said cache memory to logically define at least one redundancy-data cache segment; and

accumulating, in said at least one redundancy-data cache segment, redundancy data corresponding to said first write request data.

39. The storage medium of claim 38 wherein said disk space includes a main disk region distinct from said log-structured cache region for persistent storage of data and wherein the method further comprises the steps of:

determining to flush said first write request data from said one of said at least one disk segment to said main disk region;

reading said first write request data from said one of said at least one disk segment into a memory buffer;

subtracting redundancy data corresponding to said first write request data in said memory buffer from said redundancy-data cache segment;

processing said first write request data in said memory buffer to store data contained therein in said main disk region; and

freeing said one of said at least one disk segment for reuse.

40. The storage medium of claim 39 wherein the method step of processing includes the steps of:

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said memory buffer which is overwritten by any write request data in any of said at least one disk segment; and

posting, to said main disk region, any write request data remaining valid in said memory buffer.

41. The storage medium of claim 40 wherein said main disk region is managed in accordance with RAID storage techniques and wherein the method step of posting includes the steps of:

performing write requests represented in said write request data remaining valid in said memory buffer in accordance with said RAID storage techniques.

42. The storage medium of claim 40 wherein said cache memory includes at least one standard cache segment and wherein the method step of processing further includes the steps of:

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said plurality of write cache segments;

invalidating any write request data in said at least one standard cache segment which is overwritten by any write request data in any of said at least one disk segment; and

adding data associated with said write request data remaining valid in said memory buffer to said at least one standard cache segment.

43. The storage medium of claim 42 wherein the method further comprises the steps of:

receiving a read request to read data from said subsystem;

locating data requested by said read request in one of said plurality of write segments; and

locating said data requested by said read request in one of said at least one disk segment in response to a failure to locate said data requested by said read request in said plurality of write segments.

44. The storage medium of claim 43 wherein the method further comprises the step of:

locating said data requested by said read request in one of said at least one standard cache segment in response to a failure to locate said data requested by said read request in said one of said at least one disk segment.

45. The storage medium of claim 38 wherein said at least one redundancy-data cache segments comprises a plurality of redundancy-data cache segments and wherein each of said plurality of redundancy-data cache segments is associated with a distinct subset of said plurality of write cache segments and wherein the method step of accumulating comprises the step of:

accumulating, in the redundancy-data cache segment associated with the distinct subset including said first segment, redundancy data corresponding to said first write request data.

46. The storage medium of claim 45 wherein the method further comprises the step of:

switching to another distinct subset of said plurality of write cache segments and an associated one of said plurality of redundancy-data cache segments in response to filling of all write cache segments in a first distinct subset of said plurality of write cache segments.

47. The storage medium of claim 36 wherein said at least one disk segment is distributed over a plurality of disk drives in a cache-extension disk region.

48. The storage medium of claim 36 wherein said cache-extension disk region includes at least one redundancy-data disk segment and wherein the method further comprises the steps of:

moving said redundancy-data cache segment to one of said at least one redundancy-data disk segment in response said first write request data from said first write cache segment to one of said at least one disk segment.