Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-05-12
2002-01-01
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S155000, C707S793000
Reexamination Certificate
active
06336164
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to log structured arrays for storage subsystems, and more particularly to preventing deadlock in log structured arrays.
BACKGROUND OF THE INVENTION
In a storage subsystem, 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, (ISA), 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 the 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 drives) 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 tracks.
A destage operation provides for the LTs in a logical cylinder to be destaged together from a cache within the storage subsystem to a 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 neighborhoods in destage 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 following problem exists during concurrent garbage collection and destaging. The process of garbage collecting a segment requires that at least one free segment exists in order to serve as the new home for live logical tracks being moved from the garbage collected segment. If no free segments are available to hold garbage collected LTs, then a deadlock may occur: future destage operations stall because there are no free segments to hold LTs that are destaged; only the GC process can produce free segments, since segments can no longer become empty through the movement of updated LTs to new segments; however, the GC process cannot proceed without a free segment. A remote possibility exists that LTs newly assigned to open segments at the time the LSA exhausts its supply of free segments will free one or more segments when those open segments eventually close and the NIDs are destaged. However reliance on this possibility does not ensure the correct functioning of the log-structured system.
Accordingly, a need exists for a method and system of preventing deadlock during garbage collection in a log structured array. The present invention addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides aspects for preventing deadlock in a log structured array. In an exemplary method aspect, and system for providing same, the method inclu
Gerdt Steven
Li Juan
Nguyen Dung Lim
Yun Hai-Fang
Ellis Kevin L.
Raissinia Abdy
Sawyer Law Group LLP
LandOfFree
Method and system for preventing deadlock in a log... 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 preventing deadlock in a log..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for preventing deadlock in a log... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823021