Space allocation in a write anywhere file system

Details Space allocation in a write anywhere file system Space allocation in a write anywhere file system

2000-08-18

2003-10-21

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06636879

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to data storage systems.
2. Related Art
Data is arranged in physical locations on storage mediums. A collection of data, such as a file, can be written to, read from and (in most mediums) erased from a storage medium. Known disk drives store files in specific allocation areas on a hard disk known as storage blocks. These storage blocks record and store a standard quantity of information, such as 4K bytes. Therefore, files stored on known disk drives are divided into similarly sized file blocks for storage on the disk drive.
A preferred arrangement for storing files is to place as much of the data as possible in contiguous or nearly contiguous blocks. This allows the data files to be retrieved or written relatively quickly because the disk drive reads or writes from relatively contiguous data storage blocks without having to move the disk heads substantial distances before locating and reading or writing further blocks.
Known file systems allow data to be reorganized by moving data from block to block. For example, known disk defragmentation products perform this function for user workstations. This allows file blocks to be written to convenient locations on disk, and have their positions optimized later (such as by copying, moving and erasing data in disk storage blocks in order to get as many contiguous blocks per file for as many files as possible).
One aspect of a WAFL (Write Anywhere File Layout) file system (further described in the Incorporated Disclosures shown below), and possibly of other reliable file systems, is that reliability of disk data storage is improved by maintaining all file system blocks in the disk storage blocks at which they were originally written to disk. When a file system block is changed, a new disk storage block is allocated for the changed file system block, and the old file system block is retained for possible backup and other purposes. Records are kept of numerous previous consistent states of the file system. If the current state of the system fails, a previous state can be re-instated. However, this requires that all data storage blocks allocated for the previous states be protected. Thus, a storage block is not erased or reallocated until all previous states of the system using that block are no longer needed. This can often take weeks or months.
One problem with this method of user deleted file block is the distribution of free space can become extremely non-uniform. When disk storage blocks are desired for relatively contiguous storage, previously written data storage blocks generally cannot be erased for that purpose. Thus, in a reliable file system, another storage approach is needed to optimize the writing of file blocks to storage blocks.
One solution is to write file blocks to the first disk blocks encountered in a linear search of the disk or disks. However, this solution suffers from the drawback that it can result in scattered file storage blocks.
A second solution is to search through the disk or disks, seeking a sufficient number of contiguous blocks to hold a given file. However, this approach suffers from the drawback that it is relatively slow and uses a relatively excessive amount of computing resources.
Accordingly, it would be desirable to provide an improved technique for locating relatively large free locations on a storage medium in an efficient manner, that is not subject to drawback of the known art.
SUMMARY OF THE INVENTION
The invention provides a method and system for improving data access of a reliable file system.
In a first aspect of the invention, the file system determines the relative vacancy of a collection of storage blocks, herein called an “allocation area”. This is accomplished by recording an array of vacancy values. Each vacancy value in the array describes a measure of the vacancy of a collection of storage blocks. The file system examines these vacancy values when attempting to record file blocks in relatively contiguous areas on a storage medium, such as a hard disk. When a request to write to disk occurs, the system determines the average vacancy of all the allocation areas and queries the allocation areas for individual vacancy values. The system preferably writes file blocks to the allocation areas that are above a threshold related to the average storage block vacancy of the file system. If the file in the request to write is larger than the selected allocation area, the next allocation area found to be above the threshold is preferably used to write the remaining blocks of the file.


REFERENCES:
patent: 4527232 (1985-07-01), Bechtolsheim
patent: 4742447 (1988-05-01), Duvall et al.
patent: 4742450 (1988-05-01), Duvall et al.
patent: 4761785 (1988-08-01), Clark et al.
patent: 4875159 (1989-10-01), Cary et al.
patent: 4937763 (1990-06-01), Mott
patent: 5008786 (1991-04-01), Thatte
patent: 5043876 (1991-08-01), Terry
patent: 5067099 (1991-11-01), McCown et al.
patent: 5088081 (1992-02-01), Farr
patent: 5144659 (1992-09-01), Jones
patent: 5146588 (1992-09-01), Crater et al.
patent: 5155835 (1992-10-01), Belsan
patent: 5163131 (1992-11-01), Row et al.
patent: 5163148 (1992-11-01), Walls
patent: 5195100 (1993-03-01), Katz et al.
patent: 5218695 (1993-06-01), Noveck et al.
patent: 5218696 (1993-06-01), Baird et al.
patent: 5222217 (1993-06-01), Blount et al.
patent: 5235601 (1993-08-01), Stallmo et al.
patent: 5274799 (1993-12-01), Brant et al.
patent: 5274807 (1993-12-01), Hoshen et al.
patent: 5297265 (1994-03-01), Frank et al.
patent: 5305326 (1994-04-01), Solomon et al.
patent: 5315602 (1994-05-01), Noya et al.
patent: 5333305 (1994-07-01), Neufeld
patent: 5335235 (1994-08-01), Arnott
patent: 5357509 (1994-10-01), Ohizumi
patent: 5379417 (1995-01-01), Lui et al.
patent: 5490248 (1996-02-01), Dan et al.
patent: 5502836 (1996-03-01), Hale et al.
patent: 5649152 (1997-07-01), Ohran et al.
patent: 5668943 (1997-09-01), Attanasio et al.
patent: 5668958 (1997-09-01), Bendert et al.
patent: 5675726 (1997-10-01), Hohenstein et al.
patent: 5678006 (1997-10-01), Valizadeh et al.
patent: 5737744 (1998-04-01), Callison et al.
patent: 5742752 (1998-04-01), DeKoning
patent: 5819292 (1998-10-01), Hitz et al.
patent: 5819310 (1998-10-01), Vishlitzky et al.
patent: 5828876 (1998-10-01), Fish et al.
patent: 5835953 (1998-11-01), Ohran
patent: 5907672 (1999-05-01), Matze et al.
patent: 5948110 (1999-09-01), Hitz et al.
patent: 5950225 (1999-09-01), Kleiman
patent: 5963962 (1999-10-01), Hitz et al.
patent: 6000039 (1999-12-01), Tanaka et al.
patent: 6038570 (2000-03-01), Hitz et al.
patent: 6076148 (2000-06-01), Kedem
patent: 6101585 (2000-08-01), Brown et al.
patent: 6119244 (2000-09-01), Schoenthal et al.
patent: 6138126 (2000-10-01), Hitz et al.
patent: 6289356 (2001-09-01), Hitz et al.
patent: 0 462 917 (1991-12-01), None
patent: 0 492 808 (1992-07-01), None
patent: 0 497 067 (1992-08-01), None
patent: 0537098 (1993-04-01), None
patent: 0 552 580 (1993-07-01), None
patent: 0 569 313 (1993-11-01), None
patent: WO 91/13404 (1991-09-01), None
patent: WO 93/13475 (1993-07-01), None
patent: WO 94/29796 (1994-12-01), None
patent: WO 98/21656 (1998-05-01), None
patent: WO 98/38576 (1998-09-01), None
patent: WO 00/07104 (2000-02-01), None
patent: WO 01/31446 (2001-05-01), None
Chia Chao et al., “Mime: a High Performance Storage Device with Strong Recovery Guarantees”, Concurrent Systems Project Hewlett-Packard Laboratories, Mar. 18, 1992.
Wiebren De Jonge, “The Logical Disk: A new Approach to Improving File Systems”, Dept. of Mathematics and Computer Science, Vrije Universiteit, Amsterdam.
Jim Gray et al., “Parity Striping of Disc Arrays: Low-Cost Reliable Storage with Acceptable Throughput”, Proceedings of the 16thVLDB Conference, Brisbane, Australia 1990. Tandem Computers Inc., 19333 Vallco Parkway, Cupertino, California. XP000522459.
John H. Hartman, “The Zebra Striped Network File System”, Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, California.
David Hitz, “File System Design for

Affiliated with

Also associated with

Rating

Space allocation in a write anywhere file system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Space allocation in a write anywhere file system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space allocation in a write anywhere file system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3131846