Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-09-29
2003-01-14
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06507890
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to disk arrays and, more particularly, the invention relates to expanding a disk array.
BACKGROUND OF THE INVENTION
In general, a computer reads data from, and writes data to, a disk connected to the computer. A disk is capable of storing huge amounts of data. Typically, however, a disk cannot read or write data at, or near, the speed at which the computer communicates with the disk. Thus, the amount of time a disk needs to read or write data, referred to as disk access time, may slow the performance of the computer.
In one method to offset this limitation, the workload of a single disk is distributed across a cluster of disks. In this method, referred to as a disk array, the computer communicates with an input/output control processor which, in turn, communicates with the cluster of disks. To the computer, the disk array appears as a single disk. In general, a disk array having a particular capacity provides better performance, in other words, can better respond to the computer, than a single disk of the same capacity.
In another method to offset this limitation, a portion of system memory is used to “store” the most recent reads and writes from a computer to the disk. This method, referred to as caching, improves performance because a computer can access system memory much faster than a computer can access the disk. However, despite the improvements obtained with disk arrays and caching, disk access time still continues to slow the performance of a computer.
Taking a different approach to improving disk performance, Mendel Rosenblum and John K. Ousterhout introduced, in the article “The Design and Implementation of a Log-Structured File System,” ACM Transactions on Computer Systems, February 1992, a new disk storage structure called a log-structured file system. In a log-structured file system, the computer, or input/output control processor, writes data to the disk in a sequential structure, referred to as a log. In general, a log improves the write performance of a disk because a log eliminates the time needed for the disk to, for example, find the location in which previously stored data is located and overwrite the previously stored data with newly modified data. However, because the disk writes data to the end of the log, the disk needs free space available at the end of the log in which to write the newly modified data, or in which to write new data.
To resolve the problem of free space, Rosenblum and Ousterhout divided the log into segments. A segment can be rewritten when the live data in the segment has been copied out of the segment. A segment cleaner process packs the live data from various segments and rewrites the packed live data to, for example, the beginning of the log.
As noted, though, a log-based file structure improves the write performance of a disk, as opposed to the read performance of a disk. Thus, a log-based file structure improves a disk's performance when, among other things, most of the read requests from a computer, or input/output control processor, to a disk drive are found in memory-based cache. When most of the read requests are not found in memory-based cache, however, the performance of a disk configured as a log structure is no better than the performance of a disk configured as a more conventional structure in which, for example, the disk must first find the location in which previously stored data is located and then overwrite the previously stored data with newly modified data.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, a system and method for expanding a log structure in a disk array, wherein the disk array is being expanded from M-width to N-width, the disk array includes a storage level, the log structure includes one or more sequential used segments, and the one or more sequential used segments includes live data, the system and method locates one or more sequential used segments, writes live data from the one or more located segments to the storage level, enlarges the size of the one or more located segments from M-width to N-width, and places the one or more enlarged segments on a first free segment list.
In a further embodiment of this invention, the system and method includes repeating the above four processes for at least one more sequential used segment. In this embodiment, the system and method may use a pointer to track progression through the log structure. In an alternate embodiment of this further embodiment, the disk array may include a second free segment list. In this alternate embodiment, the process of repeating the above four processes may include placing at least one enlarged segment on the second free segment list. In addition, the system and method may use the enlarged segments placed on the first free segment list and the second free segment list to continue the operation of the log structure during the expansion.
In accordance with another aspect of the invention, a system and method for expanding a log structure in a disk array, wherein the disk array is being expanded from M-width to N-width, the disk array includes a storage level, the log structure includes unused segments and sequential used segments, the unused segments are located on a first free segment list and second free segment list, and the sequential used segments include live data, the system and method clears the first free segment list and the second free segment list, locates one or more sequential used segments, writes live data from the one or more located segments to the storage level, enlarges the size of the one or more located segments from M-width to N-width, and places the one or more enlarged segments on the first free segment list.
In a further embodiment of this invention, the system and method includes repeating the last four processes for at least one more sequential used segment. In this embodiment, the system and method may use a pointer to track progression through the log structure. In an alternate embodiment of this further embodiment, the process of repeating the last four processes may include placing at least one enlarged segment on the second free segment list. In addition, the system and method may use the enlarged segments placed on the first free segment list and the second free segment list to continue the operation of the log structure during the expansion.
In a further embodiment of both aspects of the invention, the system and method uses the one or more enlarged segments placed on the first free segment list to continue the operation of the log structure during the expansion.
In alternate embodiments of the both aspects of the invention, the log structure may be configured as a Redundant Array of Independent Disks structure. In addition, the storage level may be configured as a Redundant Array of Independent Disks structure.
REFERENCES:
patent: 4761785 (1988-08-01), Clark et al.
patent: 5524204 (1996-06-01), Verdoorn, Jr.
patent: 5829053 (1998-10-01), Smith et al.
patent: 5875456 (1999-02-01), Stallmo et al.
Rosenblum et al., “The Design and Implementation of a Log-Structured File System” ACM Transactions on Computer Systems vol. 10, No. 1, pp. 26-52 Feb. 1992.
Matthews et al., “Improving the Performance of Log-Structured File Systems with Adaptive Methods” Proc. Sixteenth ACM Symposium on Operating System Principles Oct. 1997 [Retrieved on Jun. 13, 2000] Retrieved from Internet: <URL:http://.cs.berkeley.edu/~neefe/papers/sosp97/sosp97.htm>.
Whitaker et al., “Design of the Server for the Spiralog File System” Compaq Digital Technical Journal Oct. 15, 1966 [Retrieved Jun. 13, 2000] Retrieved from Internet: <URL:http://www.digital.com/DTJM02HM.HTM>.
“RAID: Use of Log Disks for an Efficient RAID Design” IBM Technical Disclosure Bulletin pp. 19-20 Feb. 1994.
“Reducing Data Movement in Log Structure File System Garbage Collection” IBM Technical Disclosure Bulletin pp. 323-326 Feb. 1995.
DesRoches David
Morley Steve
Percy John
Solomon Robert C.
Bromberg & Sunstein LLP
EMC Corporation
Verbrugge Kevin
LandOfFree
System and method for expanding a log structure in a disk array 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 expanding a log structure in a disk array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for expanding a log structure in a disk array will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044813