Quantitative evaluation of design tradeoffs in file systems

ABSTRACT

The design of a file system has never been a simple nor a straightforward task because of its complexity. Heuristics and experience still play a major role in guiding the design process. To organize the entire design process in a more systematic manner, large scale simulation has proved to be an effective technique. The FOREM models developed during the past several years (specifically for the evaluation of file system designs) represent facilities of this type. This paper utilizes the FOREM model as the principal tool and presents a hypothetical design example dealing with many essential issues of the design process. Evaluation of designs of several other actual file systems are also being carried out and will be reported at a later date. Only through quantitative evaluation can each design decision be arrived at correctly and the possible tradeoffs be identified.

REFERENCES

• 1: BUCHOLZ, W. File organization and addressing. IBM Systems Journal, 2 (June 1963) p. 86-111.
• 2: S. P. Ghosh , M. E. Senko, File Organization: On the Selection of Random Access Index Points for Sequential Files, Journal of the ACM (JACM), v.16 n.4, p.569-579, Oct. 1969 [doi>10.1145/321541.321546]
• 3: TEICHROEW, D. A review of system design techniques. ISDOS Working Paper 17, University of Michigan, January 1969.
• 4: McCUSKEY, W. A. Toward the automatic design of data organization for large scale information processing systems. Ph. D. thesis, Case Western Reserve University, January 1969.
• 5: NUNAMAKER, JR., J. F. On the design and optimization of information processing systems. Ph.D. thesis, Case Western Reserve University, June 1961.
• 6: LANGEFORS, B. Some approaches to the theory of information systems. BIT, 3 (1963) p. 229-254.
• 7: DAY, R. H. On optimal extracting from a multiple file data storage system: An application of integer programming. Journal Op. Res., 13:3 (May-June 1965) p. 482-94.
• 8: SENKO, M. E.; LING, H.; LUM, V. Y.; MEADOW, H. R.; BRYMAN, M. R.; DRAKE, R. J.; MEYER, B. C. File design handbook. Contract Report AF 30602-69-C-0100, November 1969.
• 9: SENKO, M. E.; ABRAHAM, C. T.; GHOSH, S. P.; LUM, V. Y.; OWENS, P. W.; POMPER, I. H.; BAKER, F. T.; SCHENKEN, J. D.; WALKER, T. P. Formatted file organization techniques. Final Report AF 30602-4088, May 1967.
• 10: SENKO, M. E.; LUM, V. Y.; OWENS, P. J. A file organization evaluation model - FOREM. 1968 IFIP Congress Proceedings, p. C19-23.

INDEX TERMS

Keywords:
data management, file design, file organization, file simulation and modeling, information retrieval, inverted file, quantitative design evaluation, secondary indexes, secondary keys