Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-09-14
2003-08-19
Nguyen, Hiep T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S112000, C711S118000
Reexamination Certificate
active
06609176
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims the benefit of priority from the prior Japanese Patent Applications No. 11-371560, filed Dec. 27, 1999; and No. 2000-195895, filed Jun. 29, 2000, the entire contents of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
This invention relates to a data control system and a data rearrangement method. More particularly, the present invention relates to a disk control system using a log-structured write-in scheme and a data rearrangement method applicable to such a system.
In recent years, computer systems provided with a RAID (redundant array of independent disks) feature are in the main stream. Various types of RAID technology are known to date and they include the 0, 1, 10 and 5 types.
Recently, log-structured file systems (LSFS) have been proposed to improve the write-in performance of a RAID. The log-structured file system represents a technique for improving the performance of a RAID by utilizing the characteristic property of a disk unit that “the sequential access is by far faster than the random access”. The fall in the efficiency of a computer system during a random access process is attributable to the time consumed for a seek operation and in waiting for a rotary motion of the disk and hence such a fall of efficiency is desirably eliminated. Thus, with the log-structured file system technology, a buffer is used to store the data, and the data to be written into a plurality of small blocks are transformed into a large mass of data to be written by section of a technique of “batch writing” for writing data in a batch. With this technique, an operation of randomly writing data is changed to an operation of sequentially writing data to improve the writing performance of the system.
However, with the log-structured file system technology, the data to be written are rearranged according to the order of the write requests issued for the data. Therefore, once random writing occurs, data with logical addresses that are widely separated from each other are consecutively written in a single physical stripe region. As a result, data blocks with consecutive logical addresses of a file system are stored in different physical stripe regions that are physically remote from each other. Then, the operation of sequentially reading the data stored in physically dispersed regions is in fact physically a random reading operation and hence is poorly efficient.
The data to be written have to be rearranged periodically in order to correct such a situation and make the data to be physically continuously arranged. However, the operation of rearranging the data represents a heavy load to the system that involves many I/O processing operations.
BRIEF SUMMARY OF THE INVENTION
It is an object of the present invention to provide a disk control system and a data rearrangement method that are adapted to efficiently rearrange data and greatly improve the efficiency of data reading operations with a small load applied to the system.
According to the present invention, there is provided a disk control system using a log-structured write-in scheme and adapted to store data to be written in a buffer and write a plurality of data blocks, which are stored in the buffer, in a disk unit in unit of one physical stripe formed of a continuous storage region of the disk unit, the disk control system comprising a data rearrangement section configured to rearrange the data written in the disk unit in units of one block so as to make data with consecutive logical addresses to be written physically consecutively, a rearrangement stripe determination section configured to computationally determines at least one of a percentage of valid blocks and a percentage of the consecutive logical address numbers of adjacently located logical blocks in each physical stripe and determining the physical stripes to be reconstructed by the data rearrangement section as objects of rearrangement.
With a disk control system having the above configuration, the percentage of valid blocks and/or the percentage of the consecutive logical address numbers of adjacently located logical blocks is computationally determined for each physical stripe and the physical stripes to be rearranged by the data rearrangement section as objects of rearrangement are selected on the basis of the outcome of the computation. Since a physical stripe showing a low percentage of valid blocks is wasting the disk capacity, such a physical stripe should be selected with priority as object of rearrangement. A physical stripe showing a low percentage of valid blocks can be reused as empty stripe by processing it for data rearrangement. Additionally, a physical stripe containing valid blocks to a certain extent that are not arranged consecutively does not provide a high efficiency for a sequential read operation. Then, the efficiency of sequential read operation can be improved by selecting such a physical stripe as object of rearrangement.
In the present invention, when data rearrangement processing is executed, the necessity of carrying out a data rearrangement operation is determined for the physical stripes in the order of time and date of generation and the physical stripe with the oldest time and date of generation is selected as object of data rearrangement with priority. From the viewpoint of locality of file systems, a physical stripe whose time and date of generation is old can be assumed to contain valid blocks that are hardly selected as objects of rewriting. The frequency of occurrence of a new writing operation can be minimized for the data collected by data rearrangement and hence operations of ineffective rearrangement can be prevented from taking place by carrying out a data rearrangement operation for physical stripes whose time and date of generation is old.
The data rearrangement operation of the data rearrangement section is executed each time when a physical stripe is selected by the rearrangement stripe determination section as object of rearrangement. With this arrangement, the operation of computationally determining the percentage of valid blocks and/or the percentage of the consecutive logical addresses of adjacently located blocks for the next physical stripe is conducted after the completion of the operation of rearrangement for the current physical stripe selected as object of rearrangement so that the percentage of valid blocks and/or the percentage of the consecutive logical addresses of adjacently located blocks can be determined accurately by taking the invalid blocks into consideration.
A disk control system as defined above additionally comprises a management section which controls the number of times of references to any of the data contained in each physical stripe, the rearrangement stripe determination section being adapted to determine a physical stripe showing a number of times of references per unit time above a predetermined value as object of rearrangement with priority. With this arrangement of selecting data blocks that are frequently read with priority to arrange its physical storage regions continuously, the reading performance of the system can be remarkably improved.
Alternatively, a disk control system as defined above may additionally comprise a computation section which obtains an aggregate of valid blocks contained in the selected physical stripe for each of the logical stripe numbers allocated to the valid blocks on the basis of the logical addresses of the valid blocks and computing the number of elements of the aggregate having the largest number out of the aggregates formed by the section, the rearrangement stripe determination section being adapted to determine a physical stripe showing a number of elements as determined by the computation below a predetermined value as object of rearrangement with priority. Generally, data can be accessed at high speed for reading if they are not arranged consecutively in a rigorous sense of the word but found physically close to each other. Therefore, it is desirable to rea
Dinh Ngoc
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Nguyen Hiep T.
LandOfFree
Disk control system and data rearrangement method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Disk control system and data rearrangement method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disk control system and data rearrangement method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3079140