US5802344A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dynamic segment allocation in log structured arrays
Assignee: International Business Machines Corp
•
Filing: 1995-11-03
•
Granted: 1998-09-01
•
Expires: 2015-11-03
Abstract
Abstract An array controller of a log structured array dynamically defines segments as data is taken from a write buffer and recorded into disk storage units of the log structured array such that a segment includes blocks selected from the various disk storage units at the time of segment definition so as to minimize disk arm travel. Each time a segment from the write buffer must be written to disk, the new disk segment is defined in response to current disk arm position for each disk platter in a disk storage unit. The array controller maintains a segment definition table that indicates the disk storage unit locations corresponding to each segment. In addition, garbage collection of used blocks is performed in response to disk arm idle time such that garbage collection is not performed only when there are too few empty segments. Rather, garbage collection is performed when a disk arm has been idle for a predetermined time. A variety of garbage collection schemes are described.
Inventors
- 👤 Jaishankar Moothedath Menon
- 👤 Richard Lewis Mattson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 01:14
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0604; G06F3/0607; G06F3/0628; G06F3/0629; G06F3/0631; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689; G11; G11B; G11B20/00; G11B20/10; G06F3/0655; G06F3/0656
Claims Analysis
Total Claims: 49
Claim 1
Independent Claim
156 words
An array controller that records data into segments of storage locations in a plurality of disk drive storage devices organized as a log structured array having segment-columns, each storage device having one or more disk platters, the array controller comprising: a write buffer in which data received from a host computer for recording into the storage locations of the disk drive storage devices is temporarily stored; a log structured array (LSA) directory containing disk locations that define segments of the disk drive storage devices comprising log structured array segments; a segment definition table that contains a storage device location definition for each segment of the LSA directory; and a control processor that dynamically modifies the segment definition table so as to define a new segment into which data is recorded by selecting sufficient segment-columns independently from each disk drive storage device of the array to define a new segment, and maintains the segment definition table accordingly.
Claim 2
Dependent Claim
156 words
An array controller that records data into segments of storage locations in a plurality of disk drive storage devices organized as a log structured array having segment-columns, each storage device having one or more disk platters, the array controller comprising: a write buffer in which data received from a host computer for recording into the storage locations of the disk drive storage devices is temporarily stored; a log structured array (LSA) directory containing disk locations that define segments of the disk drive storage devices comprising log structured array segments; a segment definition table that contains a storage device location definition for each segment of the LSA directory; and a control processor that dynamically modifies the segment definition table so as to define a new segment into which data is recorded by selecting sufficient segment-columns independently from each disk drive storage device of the array to define a new segment, and maintains the segment definition table accordingly.
Claim 3
Dependent Claim
35 words
An array controller as defined in claim 1, wherein the control processor selects a segment-column nearest a current arm position of a disk arm in each disk drive storage device to define a new segment.
Claim 4
Dependent Claim
43 words
An array controller as defined in claim 1, wherein the control processor selects a segment-column that is located within a predetermined relative distance from a current arm position of a disk arm in each disk drive storage device to define a new segment.
Claim 5
Dependent Claim
69 words
An array controller as defined in claim 3, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein a live data block corresponding to the current arm position is moved if the current arm position indicates that the disk arm has been idle for a time greater than a predetermined idle threshold time.
Claim 6
Dependent Claim
57 words
An array controller as defined in claim 4, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined percentage of live data blocks.
Claim 7
Dependent Claim
52 words
An array controller as defined in claim 4, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that has less than a predetermined percentage of live data blocks.
Claim 8
Dependent Claim
80 words
An array controller as defined in claim 4, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined first percentage of live data blocks; and if the disk arm is located on a segment-column that has less than a predetermined second percentage of live data blocks.
Claim 9
Dependent Claim
105 words
An array controller as defined in claim 4, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a first segment-column of a first segment having less than a predetermined first percentage of live data blocks, and if a second segment-column on that same disk is the closest segment-column less than a predetermined number of segment-columns away, and if the second segment-column has less than a predetermined second percentage of live data blocks, wherein the live data blocks are moved from the second segment-column.
Claim 10
Dependent Claim
47 words
An array controller as defined in claim 4, wherein the control processor further performs the garbage collection process by locating the segment number having the largest number of empty blocks, moving the idle disk arm to the corresponding segment-column, and proceeding with garbage collection in that segment-column.
Claim 11
Dependent Claim
91 words
An array controller as defined in claim 1, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the array controller moves the disk arm to a target segment-column from a present location and moves the corresponding live data blocks if the target segment-column has less than a predetermined percentage of live data blocks and if the present location of the disk arm is less than a predetermined number of segment-columns from the target segment-column.
Claim 12
Dependent Claim
35 words
An array controller as defined in claim 1, further including: an arm position table containing disk arm position data that indicates current relative disk position for a disk arm of each disk drive storage device.
Claim 13
Dependent Claim
60 words
An array controller as defined in claim 1, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein the live data blocks are moved from the target segment-column if the number of empty segments in the log structured array falls below a predetermined number.
Claim 14
Independent Claim
163 words
A method of storing data as segments in a log structured array having a plurality of data storage devices in response to requests received from a host computer for data read and write operations into the data storage devices, the method comprising the steps of: recording data received from the host computer into a write buffer; determining disk arm position data that indicates position of a disk arm in each data storage device; maintaining a log structured array (LSA) directory data structure that contains disk locations that define segments of the data storage devices comprising log structured array segments; recording data in the write buffer into segments of the data storage devices when the write buffer becomes full, such that the segments into which data is written are dynamically defined according to which segment-columns are nearest to a present disk arm position; and maintaining a segment definition table that indicates a data storage device location corresponding to the segment-columns that define each segment.
Claim 15
Independent Claim
163 words
A method of storing data as segments in a log structured array having a plurality of data storage devices in response to requests received from a host computer for data read and write operations into the data storage devices, the method comprising the steps of: recording data received from the host computer into a write buffer; determining disk arm position data that indicates position of a disk arm in each data storage device; maintaining a log structured array (LSA) directory data structure that contains disk locations that define segments of the data storage devices comprising log structured array segments; recording data in the write buffer into segments of the data storage devices when the write buffer becomes full, such that the segments into which data is written are dynamically defined according to which segment-columns are nearest to a present disk arm position; and maintaining a segment definition table that indicates a data storage device location corresponding to the segment-columns that define each segment.
Claim 16
Dependent Claim
49 words
A method of storing data as defined in claim 13, wherein the step of recording data into segments of the data storage devices comprises selecting a segment-column for recording according to the segment-column nearest a current disk arm position of each data storage device to form a new segment.
Claim 17
Dependent Claim
71 words
A method of storing data as defined in claim 13, further including the step of performing garbage collection by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein a live data block corresponding to a current arm position is moved if the disk arm position data indicates that the disk arm has been idle for a time greater than a predetermined idle threshold time.
Claim 18
Dependent Claim
57 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined percentage of live data blocks.
Claim 19
Dependent Claim
52 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that has less than a predetermined percentage of live data blocks.
Claim 20
Dependent Claim
86 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined first percentage of live data blocks; and if the disk arm position data indicates the disk arm is located on a segment-column that has less than a predetermined second percentage of live data blocks.
Claim 21
Dependent Claim
105 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed if a disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a first segment-column of a first segment having less than a predetermined first percentage of live data blocks, and if a second segment-column on that same disk is the closest segment-column less than a predetermined number of segment-columns away, and if the second segment-column has less than a predetermined second percentage of live data blocks, wherein the live data blocks are moved from the second segment-column.
Claim 22
Dependent Claim
46 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed by locating the segment having the largest number of empty blocks, moving the idle disk arm to the corresponding segment-column, and proceeding with garbage collection in that segment-column.
Claim 23
Dependent Claim
34 words
A method of storing data as defined in claim 15, wherein the step of garbage collection is performed if the number of empty segments in the array is below a threshold empty segment number.
Claim 24
Dependent Claim
114 words
A method of storing data as defined in claim 13, further including the step of performing a garbage collection process to free up an entire target segment by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the controller moves the disk arm to the target segment-column from a present location and moves the live data blocks from the target segment-column if the target segment-column has less than a predetermined number of live data blocks and if the present location of the disk arm is less than a predetermined number of segment-columns from the target segment-column and has less than a predetermined number of live data blocks.
Claim 25
Dependent Claim
71 words
A method of storing data as defined in claim 13, further including the step of performing a garbage collection process to free up an entire target segment by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the controller moves the live data blocks from the target segment-column if the number of empty segments in the log structured array falls below a predetermined number.
Claim 26
Dependent Claim
176 words
A data storage system that communicates with a host computer that generates requests for data read and write operations, the data storage system comprising: a plurality of disk drive storage devices having one or more platters, each of which includes storage locations in which data is stored by a disk arm; a write buffer in which data received from the host computer for writing into the data storage devices is temporarily stored; a log structured array (LSA) directory containing disk storage locations that define segments of the disk drive storage devices comprising log structured array segments; a segment definition table containing a location definition for each segment of the LSA directory; and a control processor that controls the storing of data in the disk drive storage devices such that the control processor dynamically defines a new segment into which data is recorded by selecting a segment-column independently from each disk drive storage device and maintains a segment definition table containing storage locations in the disk drive storage devices corresponding to the segment-columns that define each segment.
Claim 27
Dependent Claim
176 words
A data storage system that communicates with a host computer that generates requests for data read and write operations, the data storage system comprising: a plurality of disk drive storage devices having one or more platters, each of which includes storage locations in which data is stored by a disk arm; a write buffer in which data received from the host computer for writing into the data storage devices is temporarily stored; a log structured array (LSA) directory containing disk storage locations that define segments of the disk drive storage devices comprising log structured array segments; a segment definition table containing a location definition for each segment of the LSA directory; and a control processor that controls the storing of data in the disk drive storage devices such that the control processor dynamically defines a new segment into which data is recorded by selecting a segment-column independently from each disk drive storage device and maintains a segment definition table containing storage locations in the disk drive storage devices corresponding to the segment-columns that define each segment.
Claim 28
Dependent Claim
36 words
A data storage system as defined in claim 24, wherein the control processor selects a segment-column nearest a current arm position of a disk arm in each disk drive storage device to define a new segment.
Claim 29
Dependent Claim
44 words
A data storage system as defined in claim 24, wherein the control processor selects a segment-column that is located within a predetermined relative distance from a current arm position of a disk arm in each disk drive storage device to define a new segment.
Claim 30
Dependent Claim
69 words
A data storage system as defined in claim 26, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein a live data block corresponding to the current arm position is moved if the arm position indicates that the disk arm has been idle for a time greater than a predetermined idle threshold time.
Claim 31
Dependent Claim
58 words
A data storage system as defined in claim 27, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined percentage of live data blocks.
Claim 32
Dependent Claim
53 words
A data storage system as defined in claim 27, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that has less than a predetermined percentage of live data blocks.
Claim 33
Dependent Claim
81 words
A data storage system as defined in claim 27, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined first percentage of live data blocks; and if the disk arm is located on a segment-column that has less than a predetermined second percentage of live data blocks.
Claim 34
Dependent Claim
106 words
A data storage system as defined in claim 27, wherein the control processor further performs the garbage collection process if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a first segment-column of a first segment having less than a predetermined first percentage of live data blocks, and if a second segment-column on that same disk is the closest segment-column less than a predetermined number of segment-columns away, and if the second segment-column has less than a predetermined second percentage of live data blocks, wherein the live data blocks are moved from the second segment-column.
Claim 35
Dependent Claim
48 words
A data storage system as defined in claim 27, wherein the control processor further performs the garbage collection process by locating the segment number having the largest number of empty blocks, moving the idle disk arm to the corresponding segment-column, and proceeding with garbage collection in that segment-column.
Claim 36
Dependent Claim
93 words
A data storage system as defined in claim 24, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the data storage system moves the disk arm to the target segment-column from a present location and moves the corresponding live data blocks if the target segment-column has less than a predetermined percentage of live data blocks and if the present location of the disk arm is less than a predetermined number of segment-columns from the target segment-column.
Claim 37
Dependent Claim
35 words
A data storage system as defined in claim 24, further including: an arm position table containing disk arm position data that indicates relative disk position for a disk arm of each disk drive storage device.
Claim 38
Dependent Claim
61 words
A data storage system as defined in claim 24, wherein the control processor performs a garbage collection process by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein the live data blocks are moved from the target segment-column if the number of empty segments in the log structured array falls below a predetermined number.
Claim 39
Dependent Claim
185 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for storing data as segments in a log structured array having a plurality of data storage devices in response to requests received from a host computer for data read and write operations into the data storage devices, the method steps performed by the machine comprising: recording data received from the host computer into a write buffer; determining disk arm position data that indicates position of a disk arm of each data storage device; maintaining a log structured array (LSA) directory data structure that contains disk locations that define segments of the data storage devices comprising log structured array segments; recording data in the write buffer into segments of the data storage devices when the write buffer becomes full, such that the segments into which data is written are dynamically defined according to which segment-columns are nearest to a present disk arm position; and maintaining a segment definition table that indicates a data storage device location corresponding to the segment-columns that define each segment.
Claim 40
Dependent Claim
185 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for storing data as segments in a log structured array having a plurality of data storage devices in response to requests received from a host computer for data read and write operations into the data storage devices, the method steps performed by the machine comprising: recording data received from the host computer into a write buffer; determining disk arm position data that indicates position of a disk arm of each data storage device; maintaining a log structured array (LSA) directory data structure that contains disk locations that define segments of the data storage devices comprising log structured array segments; recording data in the write buffer into segments of the data storage devices when the write buffer becomes full, such that the segments into which data is written are dynamically defined according to which segment-columns are nearest to a present disk arm position; and maintaining a segment definition table that indicates a data storage device location corresponding to the segment-columns that define each segment.
Claim 41
Dependent Claim
50 words
A program storage device as defined in claim 36, wherein the machine performed method step of recording data into segments of the data storage devices comprises selecting a segment-column for recording according to the segment-column nearest a current position of each disk drive storage device to form a new segment.
Claim 42
Dependent Claim
79 words
A program storage device as defined in claim 36, wherein the machine performed method steps further include the step of: performing a garbage collection process by moving live data blocks of segment-columns in a target segment to a temporary storage buffer, wherein a live data block corresponding to the current arm position is moved if the current disk arm position data indicates that the disk arm has been idle for a time greater than a predetermined idle threshold time.
Claim 43
Dependent Claim
56 words
A program storage device as defined in claim 38, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined percentage of live data blocks.
Claim 44
Dependent Claim
51 words
A program storage device as defined in claim 38, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that has less than a predetermined percentage of live data blocks.
Claim 45
Dependent Claim
79 words
A program storage device as defined in claim 38, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a segment-column that is part of a segment having less than a predetermined first percentage of live data blocks; and if the disk arm is located on a segment-column that has less than a predetermined second percentage of live data blocks.
Claim 46
Dependent Claim
107 words
A program storage device as defined in claim 38, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located on a first segment-column of a first segment having less than a predetermined first percentage of live data blocks, and if a second segment-column on that same disk is the closest segment-column less than a predetermined number of segment-columns away, and if the second segment has less than a predetermined second percentage of live data blocks, wherein garbage collection is performed to move live data blocks from the second segment-column.
Claim 47
Dependent Claim
58 words
A program storage device as defined in claim 38, wherein the step of garbage collection is performed if the disk arm that has been idle for a time greater than the predetermined idle threshold time is located in a segment having the largest number of empty blocks in the array, and in a corresponding segment-column in that segment.
Claim 48
Dependent Claim
98 words
A program storage device as defined in claim 36, wherein the machine performed method steps further include the step of: performing a garbage collection process by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the controller moves the disk arm to the target segment-column from a present location and moves the corresponding live data blocks if the target segment-column has less than a predetermined percentage of live data blocks and if the present location of the disk arm is less than a predetermined number of segment-columns from the target segment-column.
Claim 49
Dependent Claim
63 words
A program storage device as defined in claim 36, further including the step of performing a garbage collection process by moving live data blocks of segment-columns in the target segment to a temporary storage buffer, wherein the controller moves the live data blocks from the target segment-column if the number of empty segments in the log structured array falls below a predetermined number.
References Cited (Backward Citations)
US5124987A
Cited
US5155835A
Cited
US5555371A
Cited
US5557770A
Cited
US5550998A
Cited
US5530850A
Cited
US5537588A
Cited
US5488701A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-31 | 2002-03-02 | 2002-09-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-31 | 2006-03-02 | 2006-09-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-31 | 2010-03-02 | 2010-09-01 | $7700.00 | Window Closed / Lapsed |