US5613085A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for parallel striping of multiple ordered data strings onto a multi-unit DASD array for improved read and write parallelism
Assignee: International Business Machines Corp
•
Filing: 1994-12-27
•
Granted: 1997-03-18
•
Expires: 2014-12-27
Abstract
Abstract A system for storing sortwork data in a storage subsystem to maximize parallelism during subsequent merging operations. One implementation of the invention employs a computing system with a sort/merge application module and a storage subsystem such as a RAID arrangement. Each DASD unit preferably includes multiple disks in a vertically-stacked array, and each disk is configured with at least one track. Each disk corresponds to one disk of each of the other DASD units. A group of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit forms. And, the aggregate of all identically-positioned tracks from all disks in all DASD units makes up a logical array cylinder. To perform sorting and merging operations in accordance with the invention, the sort/merge application module first internally sorts a data packet to generate a string. The string is then stored in the storage subsystem, with a particular storage scheme that maximizes the parallelism of subsequent merge operations. Specifically, the string is stored such that, after all strings have been stored, each string will be evenly striped across disks of all DASD units after all data has been sorted and stored in the disk storage subsystem. Striping is most advantageously made in a diagonal pattern with wrap-around. Moreover, string size permitting, striping is preferably confined to a single logical array cylinder to minimize actuator movement in reading and writing to the disks. Storage is accomplished such that each logical block contains one string-block from each string, and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings.
Inventors
- 👤 Paul K.-W. Lee
- 👤 Zvi Y. Yehudai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 21:14
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/061; G06F3/0613; G06F3/0628; G06F3/0638; G06F3/064; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689; G06F7/00; G06F7/22; G06F7/32
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
181 words
A method for storing and retrieving sorted strings in an array of DASD units to improve parallelism during subsequent merge operations, each DASD unit comprising multiple disks configured with at least one track where each disk of a DASD unit corresponds to one disk of each of the other DASD units, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, and wherein all identically-positioned tracks of all disks together from a logical array cylinder, said method comprising the steps of: receiving multiple data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping catch string evenly across all of the DASD units, such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 2
Independent Claim
181 words
A method for storing and retrieving sorted strings in an array of DASD units to improve parallelism during subsequent merge operations, each DASD unit comprising multiple disks configured with at least one track where each disk of a DASD unit corresponds to one disk of each of the other DASD units, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, and wherein all identically-positioned tracks of all disks together from a logical array cylinder, said method comprising the steps of: receiving multiple data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping catch string evenly across all of the DASD units, such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein each string is striped a ross the DADS units in a diagonal pattern.
Claim 4
Dependent Claim
14 words
The method of claim 2, wherein the diagonal pattern comprises a wrap-around diagonal pattern.
Claim 5
Dependent Claim
16 words
The method of claim 1, wherein the strings are stored in a single logical array cylinder.
Claim 6
Dependent Claim
15 words
The method of claim 1, wherein the strings are stored in multiple logical array cylinders.
Claim 7
Dependent Claim
16 words
The method of claim 1, wherein each DASD unit comprises a vertically-stacked array of multiple disks.
Claim 8
Dependent Claim
23 words
The method of claim 6, wherein each logical block comprises an aggregate of identically-positioned tracks of similarly positioned disks from each DASD unit.
Claim 9
Dependent Claim
26 words
The method of claim 1, further comprising steps of reading the stored strings, merging the read strings, and storing the merged strings in a storage device.
Claim 10
Dependent Claim
31 words
The method of claim 4, wherein each disk is associated with at least one actuator, and the step of storing is performed while maintaining all of said actuators in fixed positions.
Claim 11
Independent Claim
146 words
A method for storing and retrieving strings in an array of DASD units to improve parallelism during subsequent merge operations, each DASD unit comprising a single disk configured with at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk, said method comprising the steps of: receiving a number of data strings from a computing system, each string being divisible into a number of ordered string-blocks: storing the strings in the DASD array by striping each string evenly across all of the disks, such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 12
Independent Claim
146 words
A method for storing and retrieving strings in an array of DASD units to improve parallelism during subsequent merge operations, each DASD unit comprising a single disk configured with at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk, said method comprising the steps of: receiving a number of data strings from a computing system, each string being divisible into a number of ordered string-blocks: storing the strings in the DASD array by striping each string evenly across all of the disks, such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 13
Independent Claim
188 words
A method for distributing sortwork onto an array of DASD units and retrieving data therefrom to improve parallelism during subsequent merge operations, wherein each string is divisible into a number of ordered string-blocks, each DASD unit including multiple disks each sub-divided into at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, and wherein identically-positioned tracks from all disks together form a logical array cylinder, said method comprising the steps of: retrieving data from a storage device and sorting the data according to pre-determined criteria to generate strings; sequentially storing the strings in the DASD array such that each string is evenly striped across all of the DASD units after all data has been sorted and stored in the DASD array, such that each logical block contains one string-block from each string, each string-block within a logical block having the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 14
Independent Claim
188 words
A method for distributing sortwork onto an array of DASD units and retrieving data therefrom to improve parallelism during subsequent merge operations, wherein each string is divisible into a number of ordered string-blocks, each DASD unit including multiple disks each sub-divided into at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, and wherein identically-positioned tracks from all disks together form a logical array cylinder, said method comprising the steps of: retrieving data from a storage device and sorting the data according to pre-determined criteria to generate strings; sequentially storing the strings in the DASD array such that each string is evenly striped across all of the DASD units after all data has been sorted and stored in the DASD array, such that each logical block contains one string-block from each string, each string-block within a logical block having the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 15
Dependent Claim
202 words
An electronic sorting apparatus, comprising: a storage subsystem including multiple DASD units with synchronized access, each DASD unit including multiple disks, wherein each disk of a DASD unit corresponds to one disk of each of the other DASD units, and wherein each disk is subdivided into a number of tracks corresponding to identically-positioned tracks of the other disks, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit: and a computer system interfaced to the storage subsystem, including a sort/merge application module programmed to perform method steps comprising: systematically retrieving data from a storage device and sorting the data to generate strings, each string being divisible into an identical number of ordered string-blocks; storing the strings in the storage subsystem such that, after all strings have been stored, each string is evenly striped across all of the DASD units, and each logical block contains one string-block from each string, wherein each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 16
Dependent Claim
202 words
An electronic sorting apparatus, comprising: a storage subsystem including multiple DASD units with synchronized access, each DASD unit including multiple disks, wherein each disk of a DASD unit corresponds to one disk of each of the other DASD units, and wherein each disk is subdivided into a number of tracks corresponding to identically-positioned tracks of the other disks, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit: and a computer system interfaced to the storage subsystem, including a sort/merge application module programmed to perform method steps comprising: systematically retrieving data from a storage device and sorting the data to generate strings, each string being divisible into an identical number of ordered string-blocks; storing the strings in the storage subsystem such that, after all strings have been stored, each string is evenly striped across all of the DASD units, and each logical block contains one string-block from each string, wherein each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 17
Dependent Claim
22 words
The apparatus of claim 12, wherein the module is programmed to stripe each string across the DASD units in a diagonal pattern.
Claim 18
Dependent Claim
14 words
The apparatus of claim 13, wherein the diagonal pattern comprises a wrap-around diagonal pattern.
Claim 19
Dependent Claim
31 words
The apparatus of claim 12, wherein identically-positioned tracks from all disks together form a logical array cylinder, and the module programmed to stripe the strings across a single logical array cylinder.
Claim 20
Dependent Claim
31 words
The apparatus of claim 12, wherein identically-positioned tracks from all disks together form a logical array cylinder, and the module is programmed to stripe the strings across multiple logical array cylinders.
Claim 21
Dependent Claim
16 words
The apparatus of claim 12, wherein each DASD unit comprises a vertically-stacked array of multiple disks.
Claim 22
Dependent Claim
23 words
The apparatus of claim 17, wherein each logical block comprises an aggregate of identically-positioned tracks of similarly positioned disks from each DASD unit.
Claim 23
Dependent Claim
33 words
The apparatus of claim 12, wherein the module is further programmed to perform method steps comprising reading the stored strings, merging the read strings, and storing the merged strings in a storage device.
Claim 24
Dependent Claim
35 words
The apparatus of claim 15, wherein each disk is associated with at least one actuator, and the module is programmed to perform the step of storing while maintaining all of said actuators in fixed positions.
Claim 25
Dependent Claim
176 words
An electronic sorting apparatus, comprising: a storage subsystem including multiple DASD units with synchronized access, each DASD unit including a single disk sub-divided into a number of tracks corresponding to identically-positioned tracks of the other disks, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk; and a computer system interfaced to the storage subsystem, including a sort/merge application module programmed, to perform method steps comprising: systematically retrieving data from a storage device and sorting the data to generate strings, each string being divisible into an identical number of ordered string-blocks; storing the strings in the storage subsystem such that, after all strings have been stored, each string is evenly striped across all of the disks, and each logical block contains one string-block from each string, wherein each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and strings. for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 26
Dependent Claim
176 words
An electronic sorting apparatus, comprising: a storage subsystem including multiple DASD units with synchronized access, each DASD unit including a single disk sub-divided into a number of tracks corresponding to identically-positioned tracks of the other disks, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk; and a computer system interfaced to the storage subsystem, including a sort/merge application module programmed, to perform method steps comprising: systematically retrieving data from a storage device and sorting the data to generate strings, each string being divisible into an identical number of ordered string-blocks; storing the strings in the storage subsystem such that, after all strings have been stored, each string is evenly striped across all of the disks, and each logical block contains one string-block from each string, wherein each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and strings. for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 27
Dependent Claim
154 words
A machine-readable program data storage device tangibly embodying a program of instructions executable by the machine to perform method steps to store sortwork data to an array of DASD units, each DASD unit including at least one disk configured with at least one track, wherein a logical block comprises an aggregate of identically sized locations from identically-positioned tracks from each disk, said method steps comprising: receiving a number of sorted data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all disks, such that each logical block contains one string-block from each string, each string-block within a logical block having the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 28
Dependent Claim
154 words
A machine-readable program data storage device tangibly embodying a program of instructions executable by the machine to perform method steps to store sortwork data to an array of DASD units, each DASD unit including at least one disk configured with at least one track, wherein a logical block comprises an aggregate of identically sized locations from identically-positioned tracks from each disk, said method steps comprising: receiving a number of sorted data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all disks, such that each logical block contains one string-block from each string, each string-block within a logical block having the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 29
Dependent Claim
26 words
The data storage device of claim 22, wherein the step of storing includes steps of striping each string across the DASD units in a diagonal pattern.
Claim 30
Dependent Claim
16 words
The data storage device of claim 23, wherein the diagonal pattern comprises a wrap-around diagonal pattern.
Claim 31
Dependent Claim
25 words
The data storage device of claim 22, wherein the step of storing includes a step of storing the strings in a single logical array cylinder.
Claim 32
Dependent Claim
24 words
The data storage device of claim 22, wherein the step of storing includes a step of storing the strings in multiple logical array cylinders.
Claim 33
Dependent Claim
17 words
The data storage device of claim 22, wherein each DASD comprises a vertically-stacked array of multiple disks.
Claim 34
Dependent Claim
25 words
The data storage device of claim 27, wherein each logical block comprises an aggregate of identically-positioned tracks of similarly positioned disks from each DASD unit.
Claim 35
Dependent Claim
33 words
The data storage device of claim 22, wherein the method steps further comprise the steps of reading the stored strings, merging the read strings, and storing the merged strings in a storage device.
Claim 36
Dependent Claim
33 words
The data storage device of claim 25, wherein each disk is associated with at least one actuator, and the step of storing is performed while maintaining all of said actuators in fixed positions.
Claim 37
Dependent Claim
203 words
A combination operable in conjunction with a digital processing apparatus to store sortwork data to an array of DASD units, each DASD unit comprising multiple disks configured with at least one track where each disk of a DASD unit corresponds to one disk of each of the other DASD units, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, said combination comprising: a data storage medium operable in conjunction with a data storage system of the digital processing apparatus: and a sort/merge application module residing on the data storage medium and executable by the digital processing apparatus to perform method steps comprising: receiving a number of sorted data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all DASD units such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 38
Dependent Claim
203 words
A combination operable in conjunction with a digital processing apparatus to store sortwork data to an array of DASD units, each DASD unit comprising multiple disks configured with at least one track where each disk of a DASD unit corresponds to one disk of each of the other DASD units, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit, said combination comprising: a data storage medium operable in conjunction with a data storage system of the digital processing apparatus: and a sort/merge application module residing on the data storage medium and executable by the digital processing apparatus to perform method steps comprising: receiving a number of sorted data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all DASD units such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and each one of at least one predetermined logical block, simultaneously reading all string-blocks within the predetermined logical block.
Claim 39
Dependent Claim
183 words
A combination operable in conjunction with a digital processing apparatus to store sortwork data to an array off DASD units, each DASD unit comprising a single disk configured with at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk, said combination comprising: a data storage medium operable in conjunction with a data storage system of the digital processing apparatus; and a sort/merge application module residing on the data storage medium and executable by the digital processing apparatus to perform method steps comprising: receiving a number of stored data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all disks such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string blocks within the predetermined logical block.
Claim 40
Dependent Claim
183 words
A combination operable in conjunction with a digital processing apparatus to store sortwork data to an array off DASD units, each DASD unit comprising a single disk configured with at least one track, wherein a logical block comprises an aggregate of identically-sized locations from identically-positioned tracks of each disk, said combination comprising: a data storage medium operable in conjunction with a data storage system of the digital processing apparatus; and a sort/merge application module residing on the data storage medium and executable by the digital processing apparatus to perform method steps comprising: receiving a number of stored data strings from a computing system, each string being divisible into a number of ordered string-blocks; storing the strings in the DASD array by striping each string evenly across all disks such that each logical block contains one string-block from each string and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings; and for each one of at least one predetermined logical block, simultaneously reading all string blocks within the predetermined logical block.
Claim 41
Dependent Claim
25 words
The method of claim 1, further comprising the steps of operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
Claim 42
Dependent Claim
25 words
The method of claim 10, further comprising the steps of operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
Claim 43
Dependent Claim
25 words
The method of claim 11, further comprising the steps of operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
Claim 44
Dependent Claim
51 words
The data storage device of claim 22, further tangibly embodying a program of instructions executable by the machine to perform method steps to read sortwork data from the array of DASD units, said method steps comprising operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
Claim 45
Dependent Claim
36 words
The combination of claim 31, said sort/merge application module further being executable by the digital processing apparatus to perform steps comprising operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
Claim 46
Dependent Claim
37 words
The combination of claim 32, said sort/merge application module further being s executable by the digital processing apparatus to perform steps comprising operating the DASD units to simultaneously read all string-blocks stored in a selected logical block.
References Cited (Backward Citations)
US5263145A
Cited
US5265098A
Cited
US5208813A
Cited
US5220653A
Cited
US5257362A
Cited
US5258984A
Cited
US5351246A
Cited
US5301297A
Cited
US5331646A
Cited
US5459853A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-17 | 2000-09-16 | 2001-03-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-17 | 2004-09-16 | 2005-03-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-17 | 2008-09-16 | 2009-03-18 | $7700.00 | Window Closed / Lapsed |