US6148368A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for accelerating disk array write operations using segmented cache memory and data logging
Assignee: Avago Technologies International Sales Pte Ltd
•
Filing: 1997-07-31
•
Granted: 2000-11-14
•
Expires: 2017-07-31
Abstract
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.
Inventors
- 👤 Rodney A. DeKoning
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 20:22
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0866; G06F2212/00; G06F2212/26; G06F2212/261; G06F2212/262; G06F2212/31; G06F2212/312
Claims Analysis
Total Claims: 52
Claim 1
Independent Claim
182 words
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.
Claim 2
Independent Claim
182 words
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.
Claim 3
Dependent Claim
127 words
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.
Claim 4
Dependent Claim
83 words
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.
Claim 5
Dependent Claim
50 words
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.
Claim 6
Dependent Claim
110 words
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.
Claim 7
Dependent Claim
73 words
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.
Claim 8
Dependent Claim
52 words
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.
Claim 9
Dependent Claim
78 words
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.
Claim 10
Dependent Claim
55 words
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.
Claim 11
Dependent Claim
25 words
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.
Claim 12
Dependent Claim
64 words
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.
Claim 13
Independent Claim
111 words
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.
Claim 14
Independent Claim
111 words
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.
Claim 15
Dependent Claim
71 words
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.
Claim 16
Dependent Claim
43 words
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.
Claim 17
Dependent Claim
129 words
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.
Claim 18
Dependent Claim
83 words
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.
Claim 19
Dependent Claim
50 words
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.
Claim 20
Dependent Claim
110 words
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.
Claim 21
Dependent Claim
73 words
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.
Claim 22
Dependent Claim
52 words
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.
Claim 23
Dependent Claim
77 words
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.
Claim 24
Dependent Claim
54 words
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.
Claim 25
Dependent Claim
25 words
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.
Claim 26
Dependent Claim
63 words
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.
Claim 27
Dependent Claim
195 words
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.
Claim 28
Dependent Claim
195 words
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.
Claim 29
Dependent Claim
128 words
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.
Claim 30
Dependent Claim
85 words
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.
Claim 31
Dependent Claim
52 words
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.
Claim 32
Dependent Claim
112 words
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.
Claim 33
Dependent Claim
74 words
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.
Claim 34
Dependent Claim
53 words
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.
Claim 35
Dependent Claim
80 words
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.
Claim 36
Dependent Claim
59 words
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.
Claim 37
Dependent Claim
26 words
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.
Claim 38
Dependent Claim
65 words
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.
Claim 39
Dependent Claim
121 words
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.
Claim 40
Dependent Claim
121 words
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.
Claim 41
Dependent Claim
75 words
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.
Claim 42
Dependent Claim
47 words
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.
Claim 43
Dependent Claim
130 words
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.
Claim 44
Dependent Claim
85 words
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.
Claim 45
Dependent Claim
52 words
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.
Claim 46
Dependent Claim
112 words
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.
Claim 47
Dependent Claim
77 words
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.
Claim 48
Dependent Claim
56 words
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.
Claim 49
Dependent Claim
79 words
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.
Claim 50
Dependent Claim
58 words
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.
Claim 51
Dependent Claim
26 words
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.
Claim 52
Dependent Claim
64 words
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.
References Cited (Backward Citations)
US5163132A
Cited
US5195100A
Cited
US5375128A
Cited
US5297258A
Cited
US5379417A
Cited
US5418921A
Cited
US5408644A
Cited
US5309451A
Cited
US5418925A
Cited
US5490248A
Cited
US5463765A
Cited
US5557770A
Cited
US5390327A
Cited
US5432922A
Cited
US5548711A
Cited
US5542066A
Cited
US5623700A
Cited
US5634109A
Cited
US5479653A
Cited
US5497457A
Cited
US5533190A
Cited
US5640506A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-14 | 2004-05-15 | 2004-11-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-14 | 2008-05-15 | 2008-11-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-14 | 2012-05-15 | 2012-11-14 | $7700.00 | Window Closed / Lapsed |