Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-11-13
2004-05-18
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S112000
Reexamination Certificate
active
06738863
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to a method for rebuilding meta-data in a data storage system and a data storage system, more particularly, to a method and system for validating segments during meta-data rebuild of a log structured array.
BACKGROUND OF THE INVENTION
A data storage subsystem having multiple direct access storage devices (DASDs) may store data and other information in an arrangement called a log structured array (LSA).
Log structured arrays combine the approach of the log structured file system architecture as described in “The Design and Implementation of a Log Structured File System” by M. Rosenblum and J. K. Ousterhout, ACM Transactions on Computer Systems, Vol. 10 No. 1, February 1992, pages 26-52 with a disk array architecture such as the well-known RAID (redundant arrays of inexpensive disks) architecture which has a parity technique to improve reliability and availability. RAID architecture is described in “A Case for Redundant Arrays of Inexpensive Disks (RAID)”, Report No. UCBICSD 87/391, December 1987, Computer Sciences Division, University of California, Berkeley, Calif. “A Performance Comparison of RAID 5 and Log Structured Arrays”, Proceedings of the Fourth IEEE International Symposium on High Performance Distributed Computing, 1995, pages 167-178 gives a comparison between LSA and RAID 5 architectures.
An LSA stores data to an array of DASDs in a sequential structure called a log. New information is not updated in place, instead it is written to a new location to reduce seek activity. The data is written in strides or stripes distributed across the array and there may be a form of check data to provide reliability of the data. For example, the check data may be in the form of a parity check as used in the RAID 5 architecture which is rotated across the strides in the array.
An LSA generally consists of a controller and N+M physical DASDs. The storage space of N DASDs is available for storage of data. The storage space of the M DASDs is available for the check data. M could be equal to zero in which case there would not be any check data. If M=1 the system would be a RAID 5 system in which an exclusive-OR parity is rotated through all the DASDs. If M=2 the system would be a known RAID 6 arrangement.
The LSA controller manages the data storage and writes updated data into new DASD locations rather than writing new data in place. The LSA controller keeps an LSA directory which it uses to locate data items in the array.
As an illustration of the N+M physical DASDs, an LSA can be considered as consisting of a group of DASDs. Each DASD is divided into large consecutive areas called segment-columns. If the DASDs are in the form of disks, a segment-column is typically as large as a physical cylinder on the disk. Corresponding segment-columns from the N+M devices constitute a segment. The array has as many segments as there are segment-columns on a single DASD in the array. One or more of the segment-columns of a segment may contain the check data or parity of the remaining segment-columns of the segment. For performance reasons, the check data or parity segment-columns are not usually all on the same DASD, but are rotated among the DASDs.
Logical devices are mapped and stored in the LSA. A logical track, sometimes referred to as a data block, is a set of data records to be stored. The data may be compressed or may be in an uncompressed form. Many logical tracks can be stored in the same segment. The location of a logical track in an LSA changes over time. The LSA directory indicates the current location of each logical track. The LSA directory is usually maintained in paged virtual memory.
Whether an LSA stores information according to a variable length format such as a count-key-data (CKD) architecture or according to fixed block architecture, the LSA storage format of segments is mapped onto the physical storage space in the DASDs so that a logical track of the LSA is stored within a single segment.
Reading and writing into an LSA occurs under management of the LSA controller. An LSA controller can include resident microcode that emulates logical devices such as CKD or fixed block DASDs. In this way, the physical nature of the external storage subsystem can be transparent to the operating system and to the applications executing on the computer processor accessing the LSA. Thus, read and write commands sent by the computer processor to the external information storage system would be interpreted by the LSA controller and mapped to the appropriate DASD storage locations in a manner not known to the computer processor. This comprises a mapping of the LSA logical devices onto the actual DASDs of the LSA.
In an LSA, updated data is written into new logical block locations instead of being written in place. Large amounts of updated data are collected as tracks in controller memory and destaged together to a contiguous area of DASD address space called a segment. A segment is usually an integral number of stripes of a parity system such as RAID 5. As data is rewritten into new segments, the old location of the data in previously written segments becomes unreferenced. This unreferenced data is sometimes known as “garbage”. If this were allowed to continue without taking any action, the entire address space would eventually be filled with segments which would contain a mixture of valid (referenced) data and garbage. At this point it would be impossible to destage any more data into the LSA because no free log segments would exist into which to destage data.
To avoid this problem, a process known as “Free Space Collection” (FSC) or “Garbage Collection” must operate upon the old segments. FSC collects together the valid data from partially used segments to produce completely used segments and completely free segments. The completely free segments can then be used to destage new data. In order to perform free space collection, data structures must be maintained which count the number of garbage and referenced tracks in each segment and potentially also statistics which indicate the relative rate of garbage accumulation in a segment. (See “An Age Threshold Scheme for Garbage Collection in a Log Structured Array” Jai Menon, Larry J Stockmeyer. IBM Research Journal 10120.)
Log structured arrays are direct access storage devices which contain meta-data, which maps a virtual storage space onto physical storage resources. The meta-data maps extents of the virtual storage space (virtual tracks) onto real tracks collated into segments stored on the physical resources. The term meta-data includes, but is not limited to, data which describes or relates to other data. For example: data held in the LSA directory regarding the addresses of logical tracks in the physical storage space; data regarding the fullness of segments with valid (live) tracks; a list of free or empty segments; data for use in free space collection algorithms; the configuration of logical volumes; topology data.
Corruption of the meta-data renders the data stored in the virtual storage space inaccessible as without the meta-data it is impossible to determine which real track corresponds to a particular virtual track. It is therefore desirable to be able to rebuild the meta-data in the event that the meta-data is corrupted in order to restore access to the data.
A secondary source of the meta-data is needed to rebuild the meta-data to allow access to the stored data. A known method of providing a secondary source of the meta-data is to provide a segment directory containing information on the data blocks or tracks in the segment and storing the segment directory as part of the segment on the storage devices. The segment directory contains all the meta-data required to describe the blocks or tracks that have been closed in that segment together with some ordering information.
U.S. Pat. No. 6,052,799 describes a method for recovering the directory of a log structured array with a secondary source of meta-data being stored in segment directories. The method
Butterworth Henry Esmond
Nicholson Robert Bruce
Inoa Midys
Kotab Dominic M.
Padmanabhan Mano
Silicon Valley IP Group PC
LandOfFree
Method for rebuilding meta-data in a data storage system and... 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 for rebuilding meta-data in a data storage system and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for rebuilding meta-data in a data storage system and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189130