Propeties of storage hierarchy systems with multiple page sizes and redundant data

ABSTRACT

The need for high performance, highly reliable storage for very large on-line databases, coupled with rapid advances in storage device technology, has made the study of generalized storage hierarchies an important area of research. This paper analyzes properties of a data storage hierarchy system specifically designed for handling very large on-line databases. To attain high performance and high reliability, the data storage hierarchy makes use of multiple page sizes in different storage levels and maintains multiple copies of the same information across the storage levels. Such a storage hierarchy system is currently being designed as part of the INFOPLEX database computer project. Previous studies of storage hierarchies have primarily focused on virtual memories for program storage and hierarchies with a single page size across all storage levels and/or a single copy of information in the hierarchy. In the INFOPLEX design, extensions to the least recently used (LRU) algorithm are used to manage the storage levels. The read-through technique is used to initially load a referenced page of the appropriate size into all storage levels above the one in which the page is found. Since each storage level is viewed as an extension of the immediate higher level, an overflow page from level i is always placed in level i + 1. Important properties of these algorithms are derived. It is shown that depending on the types of algorithms used and the relative sizes of the storage levels, it is not always possible to guarantee that the contents of a given storage level i is always a superset of the contents of its immediate higher storage level i - 1. The necessary and sufficient conditions for this property to hold are identified and proved. Furthermore, it is possible that increasing the size of intermediate storage levels may actually increase the number of references to lower storage levels, resulting in reduced performance. Conditions necessary to avoid such an anomaly are also identified and proved.

REFERENCES

• 1: ARORA, S.R., AND CALLO, A. Optimal sizing, loading and re-loading in a multi-level memory hierarchy system. Proc. AFIPS 1971 SJCC, Vol. 38, AFIPS Press, Montvale, N.J., pp. 337-344.
• 2: BELADY, L.A. A study of replacement algorithms for a virtual-storage computer. IBM Syst. J. 5, 2 (1966), 78-101.
• 3: L. A. Belady , R. A. Nelson , G. S. Shedler, An anomaly in space-time characteristics of certain programs running in a paging machine, Communications of the ACM, v.12 n.6, p.349-353, June 1969 [doi>10.1145/363011.363155]
• 4: CHEN, P.P.S. Optimal file allocation in multi-level storage systems. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 277-282.
• 5: CONTI, C.J. Cohncepts for buffer storage. IEEE Computer Group News, March 1969,6-13.
• 6: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 7: FRANASZEK, P.A., AND BENNETT, B.T. Adaptive variation of the transfer unit in a storage hierarchy. IBM J. Res. and Deuelop. 22,4 (March 1978), 405-412.
• 8: M. A. Franklin , G. Scott Graham , R. K. Gupta, Anomalies with variable partition paging algorithms, Communications of the ACM, v.21 n.3, p.232-236, March 1978 [doi>10.1145/359361.359451]
• 9: GREENBERG, B.S., AND WEBBER, S.H. MULTICS multilevel paging hierarchy. LEEE INTER- CON, Session 20/3, New York, April 8-10, 1975.
• 10: HATFIELD, D.J. Experiments on page size, program access patterns, and virtual memory. ZBM J. Res. and Deuelop. 16, 1 (Jan. 1972), 58-66.
• 11: HATFIELD, D.J., AND GERALD, J. Program restructuring for virtual memory. ZBM Syst. J. 20, 3 (1971), 168-192.
• 12: HSIAO, D.K., AND MADNICK, S.E. Data base machine architecture in the context of information technology evolution. Proc. Very Large Data Base Conf., Tokyo, Japan, Oct. 1977, pp. 63-84.
• 13: JOHNSON, C. IBM 3850-Mass storage system. IEEE INTERCON, Session 20/2, New York, April 8-10,1975.
• 14: J. Johnson, PROGRAM RESTRUCTURING FOR VIRTUAL SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 15: LAM, C.Y., AND MADNICK, S.E. INFOPLEX data base computer architecture-concepts and directions. Working Paper Sloan School of Management, No. 1046-79, M.I.T., Cambridge, Mass., 1979.
• 16: V. Y. Lum , M. E. Senko , C. P. Wang , H. Ling, A cost oriented algorithm for data set allocation in storage hierarchies, Communications of the ACM, v.18 n.6, p.318-322, June 1975 [doi>10.1145/360825.360843]
• 17: S. E. Madnick, STORAGE HIERARCHY SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1973
• 18: MADNICK, S.E. INFOPLEX-hierarchical decomposition of a large information management system using a microprocessor complex. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., DP, 581-586.
• 19: MADNICK, S.E. Design of a general hierarchical storage system. IEEE INTERCON, Session 20 1, New York, April 6-10, 1975.
• 20: MADNICK, S.E. The INFOPLEX database computer: Concepts and directions. Proc. IEEE Comptr. Conf., Feb. 26,1979, pp. 168-176.
• 21: MATTSON, R.L., GECSEI, J., SLUTZ, D.R., AND TRAIGER, I.L. Evalulation techniques for storage hierarchies. ZBMSyst. J. 9, 2 (1970), 78-117.
• 22: C. V. Ramamoorthy , K. M. Chandy, Optimization of Memory Hierarchies in Multiprogrammed Systems, Journal of the ACM (JACM), v.17 n.3, p.426-445, July 1970 [doi>10.1145/321592.321596]

INDEX TERMS

Primary Classification:
  H. Information Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Storage hierarchies

General Terms:
Design, Performance, Reliability

Keywords:
data storage hierarchy, database computer, inclusion properties, modeling, perform and reliability analysis, storage management algorithms, very large databases