Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-06-05
2001-07-03
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S114000, C711S118000, C711S154000, C711S170000
Reexamination Certificate
active
06256705
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a storage system comprising an array of storage devices where data blocks are arranged as a log structured array. More particularly, this invention relates to arranging data blocks into segments stored in the log structured arrays for optimal performance.
BACKGROUND OF THE INVENTION
A disk array is a collection of hard disk drives (HDDS) managed as a unit. Disk arrays can provide better data I/O rate and data availability for application programs than single large capacity disks.
In “A Case for Redundant Arrays of Inexpensive Disks” report no. UCB/CSD/87/391, December 1987, Patterson et al. defined five levels of RAID. In each RAID level, redundant information is provided so that if one of the HDDs is unavailable, the data on that HDD can be reconstructed from one or more of the other HDDs in the array. RAID-1, often referred to as disk mirroring or data duplexing, stores identical images of user data on two or more member HDDS. In the RAID level 3, 4 and 5 systems, redundancy is provided through a parity technique.
In RAID level 4 and 5 systems, blocks of data are stored on each HDD in the array, and parity is calculated based on a group of blocks of data on each disk drive. A parity stripe or segment consists of a set of corresponding data blocks on each disk drive and a parity block calculated from those data blocks. Data can be striped at many levels, by blocks, tracks, multiple tracks, cylinders, and so forth. In RAID-5, parity is rotated amongst all the disk drives which makes the workload on the disks in the array uniform. Other RAID levels are also known including RAID-0 where data is striped on a set of HDDs but the array does not include any parity or other redundant information.
Customers of storage arrays are most concerned with reliability, access times, and cost per megabyte of data stored. RAID systems provide a way of addressing the reliability issue at the lowest disk cost. Access time is improved by caching data. A cache is a random access memory often included as part of a storage subsystem to improve access time. A cache stores information that either has recently been requested from the disk or that needs to be written to the disk.
Data compression techniques provide a solution for improving the cost per megabyte of data storage even further. However, there are problems with implementing compression in RAID systems where data is always stored in the same location (home address) if it continues to be modified. Although a good compression algorithm yields space savings in general, the amount of compression achieved is dependent on the actual data values. After a piece of data is updated it may not compress as well as it did before it was updated so it may not fit back into the space that had been allocated for it before the update. This creates a problem for any storage system where data is assigned a home address.
In a RAID level 5 system, parity information is updated for a write operation from the logical combination of the old data, the new data, and the old parity. While RAID-5 provides many benefits for increasing concurrent accesses, a write penalty is incurred. Rather than only having one array access for writing the new data, a write operation in RAID 5 requires four array access operations, for reading the old data, reading the old parity, writing new data and writing new parity.
In Rosenblum et al, “The Design and Implementation of a Log Structured File System,” Proceedings of the 13th ACM on Operating System Principles, October 1991, a log structured file system was proposed where modified data blocks are written to the disk sequentially in a log-like structure. Information is also written with each write operation about the data being written. This information is used in managing the system.
A log structured array (LSA) uses some of the same principles of a log structured file in an array system. There are many benefits to using an LSA over a home address based RAID system. An LSA can accommodate the size changes in data produced through data compression since data is not given a fixed location on the disk. Therefore, in an LSA, data can be stored on disks in a compressed form. Also, since an LSA writes all modifications to disk sequentially in a log like structure, it solves the RAID-5 write penalty problem described previously. There is no longer a need to read the old data and old parity, since data blocks for an entire segment are written together.
Application programs running on a host computer read and write data using logical devices independent of the physical location of the data on a storage device. The application program accesses the data from the storage system using logical cylinder, logical head, and logical record addresses. The storage system controller translates the logical address to the physical address at which the data is stored. The host computer is unaware of the manner in which requested data is accessed from the physical storage devices. The typical unit of data management within the controller is a logical track. A combination of a logical cylinder and logical head address represent the logical track address.
The log structured array consists of N+P+S physical disk drives, where N is the number of HDDs 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.
2
. 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.
One of the most important benefits of an LSA is its ability to store more data with the same amount of physical disk space. Compression (using an algorithm to shorten the physical length of the data) and compaction (organizing the storage of the data efficiently in the space provided) are the two crucial factors to make this possible. It is desirable to effectively compact the data stored in the LSA storage space in order to make efficient use of the storage space.
Logical tracks of data are mapped to physical locations in segments. Segments have a predetermined set size while logical tracks have variable sizes due to compression. Therefore each segment holds an integer number of logical tracks and possibly wasted space in which no logical tracks fit. The packing factor refers to the fraction of the available storage space that is occupied by customer data. There is a need to increase the packing factor (increase effective storage capacity) by minimizing the amount of wasted space in the storage system. In particular, the system for assigning logical tracks to segments (referred to as a “filling algorithm”) affects the packing factor for the system. An efficient system for assigning logical tracks to segments provides for better disk utilization which increases effective disk capacity and provides a lower cost per megabyte of storage.
It is also desirable to increase the performance of sequential read operations. An LSA does not update logical tracks in place, but rather assigns updated logical tracks to new locations. Over time, tracks that are logically consecutive may be physically scattered over the array unless such tracks are updated at the same time. Thus, one of the drawbacks of a logs-structured system is the performance degradation of sequential reads of logically adjacent tracks that were not written sequentially. Such read operations require multiple disk head seeks in a log-structure system, compared to one seek in a traditional update-in-place (home address) system. Therefore, there is a need for organizing data for better performance during sequential reads.
O
Li Juan
Nguyen Dung Kim
Onton Aare
Smith Kevin Frank
Yun Hai-Fang
Bluestone Randall J.
International Business Machines - Corporation
Klein Esther E.
Thai Tuan V.
LandOfFree
System and method for organizing data stored 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 System and method for organizing data stored in a log..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for organizing data stored in a log... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540856