Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-05-08
2003-11-18
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S111000, C711S217000
Reexamination Certificate
active
06651147
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to allocating electronic storage space for data storage.
2. Description of the Related Art
Data is placed on storage media, such as disk drives, in physical regions referred to as “blocks”. The storage system, such as a database or file system, essentially divides an object such as a file to be stored into block-sized portions, and then places them in the block-size regions of the disk drive. When a portion of a file is smaller than a block, the entire block nonetheless is allocated. The unused space in the block is referred to as “internal fragmentation”.
Conventional allocation schemes such as those disclosed in Knuth,
The Art of Computer Programming
, vol. 1, Addison-Wesley Longman, Third Ed., 1998 allocate free space on an empty disk drive from first block to last block sequentially. This means that while initially, a file might be allocated a contiguous series of physical blocks, subsequent updates to the file will be placed in a disk region that is physically spaced from the remainder of the file by other blocks that have been recorded in the interim. This happens when, for instance, a point-in-time snapshot of a file system is to be made, with only changes to file blocks since the last snapshot being recorded. In such an instance, if an original block B of a three-block file has been changed to a modified block B′, the original three blocks remain stored together as a record of the original version of the file, and the modified block B′ is stored apart from the other blocks. Should a user subsequently desire to access the most recent version of the file, the system retrieves the two original unchanged blocks and the modified block B′.
The present invention understands that a disk drive can read and deliver a single large read or write (say, 256 Kbytes long) in less time than it takes to perform two very much smaller operations. This is because the read head, which must move along the disk from one operation to the next, can be physically moved only so fast, with even a small movement generally consuming a large amount of time as compared to the time required to execute a single long read or write. For this reason, larger block sizes are advantageous. Competing with this, however, is the fact that smaller block sizes result in less internal fragmentation, i.e., less wasted space on the disk drive. That is, as block size increases, so does internal fragmentation.
With the above considerations in mind, the present invention critically observes that sequentially allocating free blocks on a disk can result in later versions of file blocks being stored apart from the remainder of the file, particularly in cases of point-in-time snapshots. Moreover, the present invention recognizes that large file blocks are desirable from a performance view, and that apart from the block size, it is desirable to minimize I/O operations, i.e., head movement. Accordingly, the present invention recognizes a need to provide a system in file blocks associated with a single file are generally stored contiguous to each other, even if written to disk at different times, which could otherwise result in data “sparseness”. The present invention also recognizes a need to minimize I/O operations when reading or writing file blocks when the blocks might not be exactly contiguous with each other. The solutions below have been provided to address one or more of the above-recognized needs.
SUMMARY OF THE INVENTION
A general purpose computer is programmed according to the inventive steps herein to allocate storage space in a storage system. The invention can also be embodied as an article of manufacture—a machine component—that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to execute the present logic. This invention is realized in a critical machine component that causes a digital processing apparatus to perform the inventive method steps herein.
The invention can be implemented by a computer system including a data storage system having and a processor associated with a data storage system. The processor has logic for receiving a data object for storage, and randomly determining an original position on the storage medium to which to write the object. Updated blocks of the object are written in the original position or as close thereto as possible pursuant to, e.g., a copy-on-write operation of a point-in-time snapshot, or when data is written through multiple allocations. When an object is to be read from the medium, an entire region containing both the object and “chaff” data other than the object is read, with the “chaff” data being discarded subsequent to reading. The chaff can be discarded by a file subsystem, or prior to delivery to the subsystem by an input/output processor using a bit mask provided by the file subsystem.
In a preferred embodiment, the logic can determine a minimum desired data region density on the storage medium. Data is written into the region at least until the minimum desired data region density for the region is reached. The minimum desired data region density can be determined dynamically during system operation.
In another aspect, a computer program device includes a computer program storage device that is readable by a processor. A program is on the program storage device and includes instructions which can be executed by the processor for allocating space in a data storage system. The program includes computer readable code means for randomly determining, for each object, a start offset on a storage medium associated with the storage system. Computer readable code means write each object starting at its respective randomly determined start offset.
In still another aspect, a computer-implemented method for transferring data objects to and from a storage medium includes writing a first data object to a region of a data storage medium. A portion of a second object can be physically juxtaposed between two portions of the first object. The It first object is read along with the interposed portions of the second objects, and then subsequently the read portions of the second object are discarded.
The details of the present invention, both as to its structure and operation, can best be understood in reference to the accompanying drawings, in which like reference numerals refer to like parts, and in which:
REFERENCES:
patent: 5897662 (1999-04-01), Corrigan et al.
patent: 6341341 (2002-01-01), Grummon et al.
patent: 6381677 (2002-04-01), Beardsley et al.
patent: 6427184 (2002-07-01), Kaneko et al.
Pechura et al. “Estimating file access time of floppy disks”, Computing practices Communications of the ACM v.26 n.10 Oct. 1983.*
Albers et al, “Average-Case Analysis of First Fit and Random Fit Bin Packing”, Proc of the 9th annual ACM-SIAM symposium on Discrete Algorithms, Jan. 1998.*
Maymournkov, “Divergence-proving Techniques for Best Fit Bin Packing and Random Fit,” Senior Thesis Harvard College, May 7, 2001.*
Insession Technologies, “A Review of Technical Features in AutoDBA”, 2001 http://www.insession.com/autoDBA/autodba_wp.pdf.
Burns Randal Chilton
Long Darrell D. E.
Rees Robert Michael
Baker Paul A
Bragdon Reginald G.
International Business Machines - Corporation
Rogitz John L.
LandOfFree
Data placement and allocation using virtual contiguity does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data placement and allocation using virtual contiguity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data placement and allocation using virtual contiguity will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178983