System for managing log structured array (LSA) of DASDS by managing segment space availability and reclaiming regions of segments using garbage collection procedure

• US 5,551,003 A
• Filed: 02/14/1994
• Issued: 08/27/1996
• Est. Priority Date: 12/11/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mattson, Richard L., Menon, Jaishankar M.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): MEKY, MOUSTAFA M
• Application Number:
  US08/196,047
• Time in Patent Office: 925 Days
• Field of Search: 395/439, 395/441, 395/440, 395/404, 395/463, 395/250, 395/500, 395/600, 395/700
• US Class Current: 711/136
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Seek affinity is preserved in a segment oriented, cached, log structured array (LSA) of DASDs responsive to accesses dominated by sequential read and random writes of logical tracks stored in the segments. This is achieved by collecting all the write modified read active tracks and clean read active tracks either destaged from the cache or garbage collected from the LSA and rewriting them out to the LSA as segments into regions of contiguous segments of read active tracks. Also, all write modified read inactive tracks and clean read inactive tracks either destaged from cache or garbage collected from the LSA are collected and rewritten out to the LSA as segments into regions of contiguous segments of read inactive tracks. Garbage collection is initiated when the detected free space in a region falls below a threshold and continues until the collected segments exceed a second threshold. Alternatively, write age of logical tracks may be used instead of read activity so as to cluster LSA DASDs into a region of segments formed from old write active logical tracks and a region of current write active logical tracks.

Claims

1. In a system having a segment-oriented and buffered log structured array (LSA) of DASDs, directory controlled means for establishing read and write access paths to logical tracks stored in said segments on said LSA as referenced by a source of external commands, cache means coupling the source and the LSA for separately read or write enqueuing the referenced logical tracks and for managing segment space availability by destaging tracks to the buffer of the LSA according to a usage discipline, and means for reclaiming regions of segments of the LSA by a garbage collection procedure, said reclaimed regions being available for recording segments formed from write modified logical tracks thereon, a method comprising the steps of:

(a) accumulating neighborhoods of tracks in the buffer in a destage path from the cache means and in a garbage collection path from the LSA, and performing read-activity-based sorting of the accumulated neighborhoods of tracks into corresponding segments formed from write modified read active logical tracks, write modified read inactive logical tracks, clean read active logical tracks, and clean inactive logical tracks;

(b) writing segments from the buffer formed from write modified or clean read active tracks into an LSA DASD region of contiguous segments of read active tracks and writing segments from the buffer formed from write modified or clean read inactive tracks into an LSA DASD region of contiguous segments of read inactive tracks; and

(c) ascertaining the number of free space segments in each region and garbage collecting segments having either free space, old write age, or read inactive tracks in the regions in the LSA where the detected number is less than a first threshold, continuing the collection until the number of collected segments exceeds a second threshold, and applying the collected segments to the garbage collection path.

17. The method according to any one of the claims 1, 2, or 15, wherein the logical tracks may be formatted to accept fixed block records or variable length records.

2. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold.

3. The method according to claim 2, wherein the CPU initiated read and write access patterns are dominated by sequential read and random write access patterns, and further wherein in step (c) the ascertained read activity being the activity measured per step (a) at the time a logical track was destaged or collected per step (b).

4. The method according to claim 2, wherein each segment is partitionable into at least N data segment columns+one parity segment column, said segment columns being counterpart to an array of N+1 DASDs, the method further comprises the steps of:

concurrently destaging all logically adjacent modified tracks from the caching means into the same segment-column of the buffer in the event that any other modified tracks are written to the cache and which constitute adjacent tracks to those already write enqueued, if said other tracks are written to cache prior to the first write enqueued track being destaged to said buffer from said caching means.

5. The method according to claim 4, wherein said method further comprises the steps of:

periodically ascertaining the fraction of the caching means occupied by write modified tracks; and

responsive to the ascertained fraction exceeding a threshold, destaging any write modified track and other logically adjacent write modified tracks from the caching means into the same segment-column of the buffer.

6. The method according to claim 5, wherein the method further includes the step of:

concurrently destaging to the buffer from the caching means any clean logical tracks exceeding a predetermined number and which are logically adjacent the write modified tracks.

7. The method according to claim 2, wherein the method further comprises the steps of:

ascertaining, at a time prior to a predetermined space in said caching means occupied by a clean track is scheduled for reuse, whether at least a predetermined number m of logically adjacent clean tracks are stored in the caching means and not contiguously stored in the LSA of DASDs; and

responsive to the presence of such tracks destaging the clean track and the m logically adjacent clean tracks from the caching means to the same memory segment-column in the buffer.

8. The method according to claim 2, wherein a neighborhood consists of an ordered set of logical tracks, a track is logically adjacent to another if they are both in the same neighborhood.

9. The method according to claim 2, wherein step (a) further includes the steps of:

initializing a read activity counter for each logical track stored in said caching means;

counting only those read accesses to a logical track not available in the read enqueued tracks in the caching means and noting access time of occurrence; and

weighting the read accesses inversely according to their relative time of occurrence.

10. The method according to claim 9, wherein for a given group of N+1 DASDs, said DASDs being partitioned into regions of segments formed from read active data tracks and read inactive data tracks.

11. The method according to claim 10, wherein the region of segments formed from read active data tracks occupies the middle cylinders of the DASDs, and further wherein the region of segments formed from read inactive data tracks occupies the extremity cylinders of the DASDs.

12. The method according to claim 2, wherein the buffer includes a first, a second, a third and a fourth segment accumulating buffer, and further wherein the method comprises the steps of:

destaging write modified read active tracks from the cache into the first buffer, and write modified read inactive tracks from the cache into the second buffer;

destaging clean read active tracks from the cache and copying garbage collected read active tracks to the third buffer;

destaging clean read inactive tracks from the cache and copying garbage collected read inactive tracks to the fourth buffer; and

writing the contents of the first and third buffers to regions formed from segments of read active tracks and writing the contents of the second and fourth buffers to regions formed from segments of read inactive tracks.

13. The method according to claim 12, wherein the LSA includes groups of N+1 DASDs, and further wherein the method comprises the steps of:

identifying the least busy group of N+1 DASDs, the least busy group of N+1 DABDs being that group whose busiest DASD is less busy than the busiest DABD of all the other groups of N+1 DABDs, busyness being proportional to the number of access requests queued against the DABD; and

writing the contents of the first and third buffers on the identified least busy group into a region of segments formed from read active tracks and writing the contents of the second and fourth buffers on the identified least busy group into a region of segments formed from read inactive tracks.

14. The method according to claim 2, wherein each track is identified by a track number, the buffer includes counterpart buffers for write modified read active tracks, write modified read inactive tracks, clean read active tracks and clean read inactive tracks, and further wherein step (f) includes the steps of:

accumulating tracks in a dedicated buffer and writing the contents thereof into the segment buffers until the number of accumulated tracks is reasonably large;

sorting the tracks by track number and accumulating them into neighborhoods;

computing the average read activity per neighborhood; and

writing the read active tracks into the buffer for clean read active tracks and writing read inactive tracks into the buffer for clean inactive tracks.

15. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining write age activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the cache according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into separate counterpart buffers based on the ascertained write age activity of the tracks exceeding or not exceeding a threshold for the destaged tracks and otherwise for the garbage collected tracks;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from write active logical tracks are contiguous with each other and the regions of segments formed from write inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting regions having free space segments, old write age segments, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold.

16. The method according to claim 15, wherein regions formed from segments of recently written modified tracks exhibit a write age dominated by an age less than that of segments formed from garbage collected tracks.

18. In a system having a segment-oriented and buffered log structured array (LSA) of DASDs, directory controlled means for establishing read and write access paths to logical tracks stored in said segments on said LSA as referenced by a source of external commands, cache means coupling the source and the LSA for separately read or write enqueuing the referenced logical tracks and for managing segment space availability by destaging tracks to the buffer of the LSA according to a usage discipline, and means for reclaiming regions of segments of the LSA by a garbage collection procedure, said reclaimed regions being available for recording segments formed from write modified logical tracks thereon, wherein the improvement comprises:

means for accumulating racks in the buffer in a destage path from the cache means and in a garbage collection path from the LSA, means for sorting the accumulated tracks into corresponding segments formed from write modified read active logical tracks, write modified read inactive logical tracks, clean read active logical tracks, and clean inactive logical tracks;

means for writing segments from the buffer formed from write modified or clean read active tracks into an LSA region of contiguous segments of read active tracks and for writing segments form the buffer formed from write modified or clean read inactive tracks into an LSA region of contiguous segments of read inactive tracks; and

means for detecting the number of free space segments in each region and garbage collecting segments having either free space ore read inactive tracks in the regions in the LSA as a function of a first threshold, for continuing the collection until the number of collected segments exceeds a second threshold, and for applying the collected segments to the garbage collection path.

19. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold;

wherein each segment is partitionable into at least N data segment columns+one parity segment column, said segment columns being counterpart to an array of N+1 DASDs; and

(g) concurrently destaging all logically adjacent modified tracks from the caching means into the same segment-column of the buffer in the event that any other modified tracks are written to the cache and which constitute adjacent tracks to those already write enqueued, if said other tracks are written to cache prior to the first write enqueued track being destaged to said buffer from said caching means.

20. The method according to claim 19, wherein said method further comprises the steps of:

periodically ascertaining the fraction of the caching means occupied by write modified tracks; and

responsive to the ascertained fraction exceeding a threshold, destaging any write modified track and other logically adjacent write modified tracks from the caching means into the same segment-column of the buffer.

21. The method according to claim 20, wherein the method further includes the step of:

concurrently destaging to the buffer from the caching means any clean logical tracks exceeding a predetermined number and which are logically adjacent the write modified tracks.

22. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time;

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold;

(g) ascertaining, at a time prior to a predetermined space in said caching means occupied by a clean track is scheduled for reuse, whether at least a predetermined number m of logically adjacent clean tracks are stored in the caching means and not contiguously stored in the LSA of DASDs; and

(h) responsive to the presence of such tracks destaging the clean track and the m logically adjacent clean tracks from the caching means to the same memory segment-column in the buffer.

23. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold;

wherein a neighborhood consists of an ordered set of logical tracks, a track is logically adjacent to another if they are both in the same neighborhood.

24. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks, initializing a read activity counter for each logical track stored in said caching means, counting only those read accesses to a logical track not available in the read enqueued tracks in the caching means and noting access time of occurrence, and weighting the read accesses inversely according to their relative time of occurrence;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold;

wherein for a given group of N+1 DASDs, said DASDs being partitioned into regions of segments formed from read active data tracks and read inactive data tracks.

25. The method according to claim 24, wherein the region of segments formed from read active data tracks occupies the middle cylinders of the DASDs, and further wherein the region of segments formed from read inactive data tracks occupies the extremity cylinders of the DASDs.

26. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, said buffer including a first, a second, a third and a fourth segment accumulating buffer, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the buffers to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time;

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold;

(g) destaging write modified read active tracks from the cache into the first buffer, and write modified read inactive tracks from the cache into the second buffer;

(h) destaging clean read active tracks from the cache and copying garbage collected read active tracks to the third buffer;

(i) destaging clean read inactive tracks from the cache and copying garbage collected read inactive tracks to the fourth buffer; and

(j) writing the contents of the first and third buffers to regions formed from segments of read active tracks and writing the contents of the second and fourth buffers to regions formed from segments of read inactive tracks.

27. The method according to claim 26, wherein the LSA includes groups of N+1 DASDs, and further wherein the method comprises the steps of:

identifying the least busy group of N+1 DASDs, the least busy group of N+1 DASDs being that group whose busiest DASD is less busy than the busiest DASD of all the other groups of N+1 DASDs, busyness being proportional to the number of access requests queued against the DASD; and

writing the contents of the first and third buffers on the identified least busy group into a region of segments formed from read active tracks and writing the contents of the second and fourth buffers on the identified least busy group into a region of segments formed from read inactive tracks.

28. In a system having a CPU and means for establishing directory controlled read and write access paths to logical tracks stored in a segment-oriented buffered log structured array (LSA) of DASDs via caching means coupling the buffered array, said caching means managing segment space availability by destaging one or more logical tracks according to a usage discipline (LRU) to the buffer, said caching means including means for reclaiming regions of segments of the LSA by a garbage collection procedure for recording write modified logical tracks thereon, said logical tracks including write modified and clean tracks, wherein each track is identified by a track number, the buffer includes counterpart buffers for write modified read active tracks, write modified read inactive tracks, clean read active tracks and clean read inactive tracks, a method for preserving seek affinity on CPU initiated read and write access patterns to the LSA, comprising the reiterative steps of:

(a) ascertaining read activity of neighborhood accumulations of logical tracks;

(b) destaging logical tracks from the caching means according to the cache usage discipline and garbage collecting selected tracks from the LSA;

(c) sorting neighborhood accumulations of logical tracks obtained according to step (b) into counterpart buffers based on the ascertained read activity of the tracks exceeding or not exceeding a threshold;

(d) batch writing contents of the butters to counterpart regions of segments on the DASD array such that the regions of segments formed from read active logical tracks are contiguous with each other and the regions of segments formed from read inactive logical tracks are contiguous with each other;

(e) ascertaining the number of free space segments in each region, free space segments being formed in a region as logical tracks stored in the segments of a region are modified or deleted over time; and

(f) garbage collecting segments in regions having either free space, old write age, or read inactive tracks in the DASD array responsive to the ascertained number of free segments in any given region falling below a first threshold and continuing said garbage collection until the number of collected segments exceeds a second threshold, by performing steps comprising;

accumulating tracks in a dedicated buffer and writing the contents thereof into the segment buffers until the number of accumulated tracks is reasonably large;

sorting the tracks by track number and accumulating them into neighborhoods;

computing the average read activity per neighborhood; and

writing the read active tracks into the buffer for clean read active tracks and writing read inactive tracks into the buffer for clean inactive tracks.