Method and system for increasing concurrency during staging...

Details Method and system for increasing concurrency during staging... Method and system for increasing concurrency during staging...

1999-05-12

2002-10-08

Nguyen, Than (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S111000, C711S112000, C711S113000, C711S155000, C711S157000, C711S158000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06463503

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to log structured arrays for storage subsystems, and more particularly to increasing concurrency during staging and destaging in a log structured array.
BACKGROUND OF THE INVENTION
In storage subsystems, a redundant array of inexpensive disks, RAID, is one solution to I/O (input/output) bottleneck problems. RAID typically increases disk bandwidth through parallelism for accessing data and provides high data availability through redundancy. One problem associated with some levels of RAID is the write penalty; a write operation actually requires two disk reads (of old data and parity) and two disk writes (of updated data and the newly calculated parity). Log Structured Array (LSA) writes all customer data to disk sequentially in a log-like structure and enables RAID to support data compression. The amount of compression achieved is dependent on the actual data values. After a piece of data is modified, it may not compress to the same number of bytes and thus will not fit into the space originally allocated to it. This problem is encountered in any storage system that assigns a piece of data to a disk fixed location; LSA avoids this problem, since updated data is written to end of the log structure.
Through LSA, a logical track, LT, which is the typical unit accessed by I/O programs, is allowed to be updated to a different location on disk. Since the physical address of a logical track changes over time, a directory, called LSA directory, is necessary to keep track of the current LT's physical address on the array. Each directory entry also records the logical track's current length, as this may vary with compression.
The log structured array consists of N+P+S physical disk drives, where N is the number of HDDs' (hard disk drive) worth of physical space available for customer data, P is the number of HDDs' worth of physical space for parity data, and S is the number of HDDs' worth of physical space for spare drives. Each HDD is divided into large consecutive areas called segment columns. Typically, a segment column is as large as a logical cylinder. Corresponding segment columns from the N+P+S HDDs constitute a segment. The array has as many segments as there are segment columns on a HDD disk in the array. An example of the layout for such a system is shown in FIG.
1
. In a RAID-
5
configuration, one of the segment columns of a segment contains the parity of the remaining data segment columns of the segment.
Referring to
FIG. 1
, the storage for the partition
52
is arranged as segments
56
, where each segment has N data segment columns
58
and one parity segment column
59
. The logical tracks
60
are stored within segment columns. A segment directory
62
contains information on each of the logical tracks in the segment which is used during garbage collection and recovery procedures. The segment directory
62
is stored in a small number of sectors out of a segment's total disk space. As shown, the entire segment directory resides in one same segment column in each of the segments. Alternatively, the segment directory can be spread among the devices. In a RAID-
5
system, parity is distributed among the devices as shown.
A segment column is defined as an arbitrary number of contiguous physical tracks as described above. Typically it is desirable to define a segment column to be the same size as a logical cylinder. The collection of disk recording areas comprising corresponding segment columns from each of the HDDs forms what is called a segment.
LSA segments are categorized as one of the following types: free, which refers to a segment that contains no valid data; open, which refers to a segment that is available to hold LTs being destaged; closed, which refers to a segment containing some valid data, but to which no destaged data can be further assigned; and being garbage collected, GC, which refers to a closed segment that is currently being garbage collected, as discussed hereinbelow. A closed segment consists of ‘live’ LTs and ‘holes’. The former are LTs that were assigned to the segment during the segment's open phase and still reside in the segment. The latter is space vacated by LTs that were assigned to the segment but have subsequently been updated and assigned to different open segments. A closed segment's occupancy is the sum of the lengths of the segment's live LT.
A destage operation allows the LTs in a logical cylinder to be destaged together from a cache within the storage subsystem to the storage device to enhance the seek affinity of sequential accesses. A logical cylinder is typically called a neighborhood, and a group of logical tracks in a logical cylinder destaged together is called a neighborhood in destage (NID) or neighborhood destage request. Destaging a neighborhood essentially involves the following steps:
1. The neighborhood in destage is assigned to an open segment.
2. An open segment remains available to accept other neighborhoods in destage until it is deemed full enough to close in accordance with a desired algorithm.
3. The data and parity of the segment is written to disk before the segment is considered closed.
4. Each LT in the open segment has an entry in the segment directory that describe the LT's location in the segment. The segment directory is written on disk, as part of the segment.
An LT in a closed segment may be updated and destaged again, at which time it is assigned to another open segment. This causes the previous copy of the LT to become obsolete, thus forming a ‘hole’ in the closed segment. Garbage collection (GC) is the process of reclaiming ‘holes’ in closed segments. GC is started when the number of free segments falls below a certain threshold.
The process of garbage collecting a segment involves reading the segment's directory from disk, then scanning each segment directory entry and comparing the LT's address as indicated by the segment directory entry with the address as indicated by the LSA directory entry. If the two entries match, then the LT still resides in the segment and is considered ‘live’. All the live LTs are then read from disk into memory and sorted by neighborhood. These NIDs then proceed to be destaged in the same manner as described above. These NIDs are assigned to open segments; when such open segments close successfully, the NIDs are garbage collected, thus decreasing the occupancy of the segments in which the NIDs previously resided. When a segment's occupancy declines to zero, either as a result of garbage collection or as a result of movement of tracks from normal destage activity, the segment becomes free.
The LSA directory keeps track of LTs' length and physical address in the disk array in terms of segment number, segment column number, and offset within the segment column. An LT's LSA directory entry is accessed whenever the LT is involved in any one of the three major processes: staging of data from disk, destaging of data to disk, and garbage collection. When an LT is staged, its LSA directory entry is read to determine the LT's physical location in the array. When an LT is destaged, its physical address changes and its LSA directory entry must be updated to indicate the new location. Likewise, when the LT is garbage collected, the track changes physical location, and the LSA directory entry must be updated.
Conflicts in access of the LSA directory entry arise when a logical track is involved in the following combination of concurrent operations: destage and garbage collection, or stage and garbage collection. Design of the interface between the disk control unit's caching component and its array component prohibits concurrent stage and destage of the same LT. Similarly, an LT cannot be destaged a second time before a first destage operation completes; and an LT cannot be staged a second time before a first stage operation completes. In the other cases, the LSA directory entry locking mechanism provided by the LSA subcomponent mus

Affiliated with

Also associated with

Rating

Method and system for increasing concurrency during staging... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for increasing concurrency during staging..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for increasing concurrency during staging... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2966122