Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-09-29
2003-08-26
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06611852
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to a log structure and, more particularly, the invention relates to cleaning a log structure.
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 cleaning a log structure, wherein the log structure includes one or more segments and each segment includes live data, orders the one or more segments into a hot list according to age, with the youngest segment at the beginning of the hot list and the oldest segment at the end of the hot list, the youngest segment being the most recently used segment and the oldest segment being the least recently used segment. Next, the system and method pushes one or more of the oldest segments in the hot list to a cleaning matrix, the cleaning matrix grouping segments according to age and percent of live data in the segment. Then, the system and method traverses the cleaning matrix looking for a segment, determines whether enough live data has been found to write a complete segment, and sequentially repeats the previous two processes until enough live data has been found to write a complete segment. Last, the system and method reads data from the one or more found segments and then writes the read live data into an unused segment.
In accordance with another aspect of the invention, a system and method for cleaning one or more log structures in a disk array, wherein the disk array includes one or more log-enabled logical units, each log-enabled logical unit includes one or more segments, and each segment includes live data, for each log-enabled logical unit the system and method orders the one or more segments into a hot list according to age, with the youngest segment at the beginning of the hot list and the oldest segment at the end of the hot list, the youngest segment being the most recently used segment and the oldest segment being the least recently used segment. Next, for each log-enabled logical unit, the system and method pushes one or more of the oldest segment in the hot list to a cleaning matrix, the cleaning matrix grouping segments according to age and percent of live data in the segment. Then, for each log-enabled logical unit, the system and method traverses the cleaning matrix looking for a segment, determines whether enough live data has been found to write a complete segment, and sequentially repeats the previous two processes until enough live data has been found to write a complete segment. Last, for each log-enabled logical unit, the system and method reads data from the one or more found segments and then writes the read live data into an unused segment.
In a further embodiment of both aspects of the invention, the process of pushing one or more segments in the hot list to the cleaning matrix occurs when the one or more segments fall below a pre-determined point in the hot list. In a still further embodiment of both aspects of the invention, the process of traversing the cleaning matrix includes balancing the segment's age against the segment's utilization. For example, the process of balancing may result in a substantially vertical traversal of the cleaning matrix. Or, the process of balancing may result in a substantially diagonal traversal of the cleaning matrix. Or, the process of balancing may result in a mixed traversal of the cleaning matrix.
In yet still further embodiments of both aspects of the invention, the system and method includes placing at least one found segment on a free segment list. Or, the system and method includes placing the written segment back into the cleaning matrix. The written segment may be placed in the location in the cleaning matrix in which the last segment was found.
In alternate embodiments of both aspects of the invention, the log structure may be part of a disk. In addition, the disk may include a storage level. In these alternate embodiments, the system and method may include identifying one or more segments in the cleaning matrix to migrate, the one or more segments selected being the oldest segments with the highest percent of live data, writing live data from the identified oldest segments to the storage level, and placing the identified oldest segments on a free segment list.
In further alternate embodiments of both aspects of the invention, the log structure may be part of a disk array. In addition, the disk array may include a storage level. In these alternate embodiments, the system and method may include identifying one or more segments in the cleaning matrix to migrate, the one or more'segments selected being the oldest segments with the highest percent of live data, writing live data from the identified oldest segments to the sto
DesRoches David
Morley Steve
Percy John
Solomon Robert C.
Bromberg & Sunstein LLP
EMC Corporation
Nguyen Merilyn
LandOfFree
System and method for cleaning a log structure 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 cleaning a log structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for cleaning a log structure will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101291