Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-21
2002-06-11
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06405217
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to file systems operating in a transaction environment, and more particularly to implementing file system transactions using a state-based scheme.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright© 1997, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
File systems in transaction-oriented environments support transactions performed against the components of the file system, i.e., the directories and files. The components make up the namespace of the file system.
Transaction-oriented file systems usually maintain a log of changes made to the names in the namespace and write the changes to persistent storage when the transaction commits the changes. Current file systems use a time-based list as the log and record each and every name change made in the namespace in chronological order so that the changes can be applied when the modifying transaction commits.
However, when more than one change is made to the same namespace component before the changes are committed, only the final change is of interest and using space to store the intermediate changes in the log is wasteful. Additionally, applying the intermediate changes in chronological order when the transaction commits is usually unnecessary and slows the performance of the file system.
Therefore, a way is needed to collapse the unnecessary intermediate changes into a final state for the file system namespace and to apply the final state to each component in the namespace.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
State-based offspring objects are created to correspond to each object in a file system namespace when the corresponding object is opened. Each offspring object contains two fields, an original name field containing the name of the object when opened and a final name field. Each change made to the object is written to the final name field so that the final name field always reflects the last change made to the name of the object. The various combinations of the fields define the offspring object's state. The offspring objects are arranged in a hierarchical structure that mimics the structure of the namespace with the offspring object corresponding to the top level open object as its root. When the changes are committed, the state of the offspring object is used to determine the correct operation to be performed on the corresponding object. Once the commit completes, the final name is written into the original name field. If changes are aborted, the original name is written into the final name field.
In one aspect of the invention, the final names for objects at intermediate levels in the namespace hierarchy are written to memory when the changes are committed and only written to the file system's persistent storage when a commit is made at the top level open object. In another aspect of the invention, a temporary offspring object is created to accommodate a circular rename transaction.
Because an offspring object needs only the original and final name fields to define the state of a file system object and maintains only the last state of the object, the offspring objects of the present invention are less wasteful of memory space than the time-based log of the previous file system implementations. Additionally, a file system that uses the offspring objects of the present invention applies only the final state of the offspring object to the object, thus saving processing time. Special situations that require applying intermediate changes to the object are also implemented using the offspring objects so no special object types need be created.
The present invention can be practiced in a non-object-based file system using any data structure that incorporates the characteristics detailed above for the offspring object. Furthermore, the invention is applicable to file formats which support a hierarchical arrangement of data within a file that mimics a traditional file system.
REFERENCES:
patent: 4935869 (1990-06-01), Yamamoto
patent: 5455947 (1995-10-01), Suzuki et al.
patent: 5465365 (1995-11-01), Winterbottom
patent: 5623666 (1997-04-01), Pike et al.
patent: 5729696 (1998-03-01), Goodwin, III et al.
patent: 5794252 (1998-08-01), Bailey et al.
patent: 5835689 (1998-11-01), Braun et al.
patent: 5857204 (1999-01-01), Lordi et al.
patent: 5909540 (1999-06-01), Carter et al.
patent: 5918229 (1999-06-01), Davis et al.
patent: 5941947 (1999-08-01), Brown et al.
patent: 6009266 (1999-12-01), Brownell et al.
patent: 6026474 (2000-02-01), Carter et al.
patent: 6161125 (2000-12-01), Traversat et al.
Kistler et al., “Disconnected Operation in the Coda File System,” School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, pp. 213-225 (1991).
Conradi et al., “Version Models for Software Configuration Management,”ACM Computing Surveys, vol. 30, No. 2 (Jun. 1998).
Rosenblum et al., “The Design and Implementation of a Log-Structured File System,” Electrical Engineering and Computer Sciences, Computer Science Division, University of California, Berkeley, CA, pp. 1-15 (1991).
Gray et al., “Transaction Processing: Concepts and Techniques,” Morgan Kaufmann Publishers, San Francesco, CA, pp. 5-22, 67-78, 661-688 (1993).
Black Thomas
Klarquist & Sparkman, LLP
Microsoft Corporation
Wang Mary
LandOfFree
State-based implementation of transactions on a 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 State-based implementation of transactions on a file system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and State-based implementation of transactions on a file system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2952329