article

Free access

Disk cache—miss ratio analysis and design considerations

Editor: Anita K. Jones Author:

Alan J. SmithAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 3, Issue 3

Pages 161 - 203

https://doi.org/10.1145/3959.3961

Published: 01 August 1985 Publication History

PDF eReader

Abstract

The current trend of computer system technology is toward CPUs with rapidly increasing processing power and toward disk drives of rapidly increasing density, but with disk performance increasing very slowly if at all. The implication of these trends is that at some point the processing power of computer systems will be limited by the throughput of the input/output (I/O) system.

A solution to this problem, which is described and evaluated in this paper, is disk cache. The idea is to buffer recently used portions of the disk address space in electronic storage. Empirically, it is shown that a large (e.g., 80-90 percent) fraction of all I/O requests are captured by a cache of an 8-Mbyte order-of-magnitude size for our workload sample. This paper considers a number of design parameters for such a cache (called cache disk or disk cache), including those that can be examined experimentally (cache location, cache size, migration algorithms, block sizes, etc.) and others (access time, bandwidth, multipathing, technology, consistency, error recovery, etc.) for which we have no relevant data or experiments. Consideration is given to both caches located in the I/O system, as with the storage controller, and those located in the CPU main memory. Experimental results are based on extensive trace-driven simulations using traces taken from three large IBM or IBM-compatible mainframe data processing installations. We find that disk cache is a powerful means of extending the performance limits of high-end computer systems.

References

[1]

AMDAHL, G.M. Storage and IO parameters and systems potential. In Proceedings of the IEEE Computer Group Conference (Washington, D.C., June 16-18). IEEE. New York, 1970, pp. 371- 372.

Google Scholar

[2]

ARTIS, H.P. Calculating head of string utilization in a shared DASD environment. In Proceedings of the CMG International Conference (Dec. 6-8, Washington, D.C.). Computer Measurement Group, 1983, pp. 62-65.

Google Scholar

[3]

BASTIAN, A. L., HYDE, J. S., AND LANGSTROTH, W. E. Characteristics of DASD use. In Proceedings of the CMG 12th International Conference (Dec. 1-4, New Orleans, Dec.). Computer Measurement Group, 1981, pp. 107-109.

Google Scholar

[4]

BASTIAN, A. L. Cached DASD performance prediction and validation. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 174-177.

Google Scholar

[5]

BATALDEN, G. D., CRABTREE, M. R. AND GOURNEAU D.A. DASD cache for file subsystem. IBM Tech. Disc. Bull. 27, 6 (Nov. 1984), 3433-3435.

Google Scholar

[6]

BELADY, L.A. A study of replacement algorithms for a virtual storage computer. IBM Sys. J. 5, 2 (1966), 78-101.

Google Scholar

[7]

BENNETT, B. T. AND MAY, C. Improving performance of buffered DASD to which some references are sequential. IBM Tech. Disc. Bull. 24, 3 {Aug. 1981), 1559-1562.

Google Scholar

[8]

BERBECK, S., SHIBAMIYA A., TOGASAKI, S., AND YOSHIDA, H. Use of direct access storage devices by MVS customersiGuide survey results. In Proceedings o/the Guide 47 Conference (Chicago, Nov. 10). 1978, pp. 1121-1138.

Google Scholar

[9]

BERETVAS, T. Performance tuning in OS/VS2 MVS. IBM Sys. d. 17, 3 {1978), 290-313.

Google Scholar

[10]

BRANDWAJN, A. Models of DASD subsystems: Basic model of reconnection. Perform. Eval. 1 (1981), 263-281.

Google Scholar

[11]

BOZEN J.P. BEST/1 analysis of the IBM 3880-13 cached storage controller. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 156-172.

Google Scholar

[12]

COMPUTERWORLD. Cache memory reduces data transfer time. Computer (Feb., 1982), 103

Google Scholar

[13]

COMPUTERWORLD. HP 3000 access time slashed 400%. Computerworld {Feb. 8, 1982), 109.

Google Scholar

[14]

COMPUTERWORLD. Cache disk system out for IBM ACP. Computerworld (June 7, 1982), 101.

Google Scholar

[15]

COMPUTERWORLD. Cache disk system speeds access for power firm. ComputerworM {Dec, 6, 1982), 34.

Google Scholar

[16]

COMPUTERWORLD. Amdahl offers cache for new, older, drives. Computerworld (Mar. 12, 1984), 4.

Google Scholar

[17]

COMPUTERWORLD. Storage Technology Corp., Sybercache statistical product. Computerworld (July 9, 1984), 80.

Google Scholar

[18]

COTE, H. J. AND DUHL, B. New horizons for cached disk and buffered tape. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, pp. 333-337.

Google Scholar

[19]

DAttMAN, K. AND GROSSMAN, G. Effective use of cached DASD in a data base/data communications environment. In Proceedings of the 1983 CMG International Conference (Washington, D.C., Dec.). 1983, pp. 425-431.

Google Scholar

[20]

DATE, C. J. An Introduction to Database Systems. 2nd ed., Addison-Wesley, Reading, Mass., 1977.

Crossref

Google Scholar

[21]

DENSINC, P.J. On modelling program behavior. In Proceedings of the Spring Joint Computer Conference, vol. AFIPS Press, Reston, Va., 1972, pp. 937-944.

Google Scholar

[22]

DIxoN, J. D., MARAZAS G. A., AND McNEILL, A.B. Mini-ops--A microcoded data transfer scheduling and execution systems for the optimized control of an I/O controller cache memory. IBM Tech. Disc. Bull. 27, 2 {July, 1984), 1226-1227.

Google Scholar

[23]

DODSON, G.W. Cached DASD evaluations for paging and non-paging data. In Proceedings of the CMG 13th International Conference (Dec. San Diego, Calif.). 1982, p. 338.

Google Scholar

[24]

DUKE, A. H., HARTUNG, M. H., HUNTLEY, J. D., AND MARSCHNER, F.J. Buffered writing in a peripheral storage hierarchy. IBM Tech. Disc. Bull. 25, 4 (Sept. 1982), 2075-2076.

Google Scholar

[25]

DUKE, A. H. AND HARTUNG, M. H. Controlling multitrack references in a cached storage system. IBM Tech. Disc. Bull. 25, 7B (Dec. 1982), 3756-3757.

Google Scholar

[26]

DUKE, A. H., HARTUNG, M. H., HUNTLEY, J. D., AND NOLAN K.P. Inhibiting cache loading. IBM Tech. Disc. Bull. 25, 12 (May 1983), 6351-6353.

Google Scholar

[27]

ELECTRONICS I. Cache memories catch on for disks. Electronics (Apr. 21, 1981), 62-63.

Google Scholar

[28]

ELECTRONIC NEWS. IBM expands CPU for system 38; adds series 1 processor, disk drive. Electron. News (Apr. 11, 1983).

Google Scholar

[29]

ELECTRONIC NEWS. New HP 16-bit CPUs Based on OS Upgrades. Electron. News (May 30, 1983), 18.

Google Scholar

[30]

ELECTRONIC NEWS. IBM Increases Memory, Cuts Tag on 3880 Controller. Electron. News (Sept. 24, 1984), 27, 39.

Google Scholar

[31]

ELECTRONIC NEWS. Storage Tek Offers Controller Upgrade. Electron. News (Aug. 13, 1984), 33.

Google Scholar

[32]

FAJMAN, R. AND BORGELT, J. Wylbur: An interactive text editing and remote job entry system. Commun. ACM 16, 5 (May, 1973), 314-322.

Crossref

Google Scholar

[33]

FRIEDMAN, M. "DASD access patterns" In Proceedings of the 1983 CMG International Conference, (Dec. 1-4 Washington, D. C.). 1983, pp. 51-61.

Google Scholar

[34]

GALE, L. Work station performs at the superminicomputer level. Electronics (Sept. 8, 1983), 119-123.

Google Scholar

[35]

HARKER, J. M., BREDE, D. W., PATTISON, R. E., SANTANA, G. R., AND TAFT, L.G. A quarter century of disk file innovation. IBM J. Res. Devel. 25, 5 (Sept. 1981), 677-689.

Google Scholar

[36]

HOAGLAND, A.S. Storage technology: Capabilities and limitations. Computer 12, 5 (May 1979) 12-18.

Google Scholar

[37]

HODGES, D.A. A review and projection of semiconductor components for digital storage. Proc. IEEE 63, 8 (Aug. 1975), 1136-1147.

Google Scholar

[38]

HUGELSHOFER W. AND SHULTZ, }~, Cache buffer for disk accelerates minicomputer performance. Electronics (Feb. 10, 1982), 155-159.

Google Scholar

[39]

HUNTER, D. Modeling real DASD configurations. IBM Res. Rep. RC 8606, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1980.

Google Scholar

[40]

HUNTER, D.W. DASD arm buffers. IBM Tech. Disc. Bull. 24, 4 (Sept. 1981), p. 2035.

Google Scholar

[41]

INFOWORLD. Cache/Q Disk buffering enhancement for CP/M. Infoworld 5, 7 (Jan. 14, 1983), 50-54.

Google Scholar

[42]

INTEL. FAST-3805 Functional Description. PN 19-1619-006 (Aug. 1979), Intel Commercial Systems Division, Phoenix, Ariz.

Google Scholar

[43]

IBC/INTEORATED BUSINESS COMPUTERS. CADET/10 cache disk memory reference manual. integrated Business Computers, Chatsworth, Calif., 1982.

Google Scholar

[44]

IBM. Reference manual for the IBM 2835 storage control and the IBM 2305 fixed head storage module. GA26-1589, IBM Corporation, 1972, San Jose, Calif.

Google Scholar

[45]

IBM. Reference manual for IBM 3830 storage control and IBM 3330 disk storage. GA26-1592, IBM Corporation, Armonk, N.Y.

Google Scholar

[46]

IBM. OS/VS2 system programming library: Service aids. GC28-0674-1, IBM Corporation, Gaithersburg, Md., 1976.

Google Scholar

[47]

IBM. Reference manual for IBM 3350 direct access storage. GA26-1638-2, IBM Corporation, San Jose, Calif., 1977.

Google Scholar

[48]

IBM. OS/VS MVS systems programming library: System management facilities (SMF). GC28- 0706-1, IBM Corporation, Poughkeepsie, N. Y., 1977.

Google Scholar

[49]

IBM. IBM 3310 direct access storage reference manual. GA26-1660, IBM Corporation, San Jose, Calif., 1979.

Google Scholar

[50]

IBM. IBM 3370 direct access storage description. Pub GAZ6-1657-2 IBM Corporation, General Products Division, San Jose, Calif., 1979.

Google Scholar

[51]

IBM. Introduction to IBM 3880 storage control, model 11. GA32-0060, IBM Corporation. Tucson, Ariz., 1981.

Google Scholar

[52]

IBM. IBM 3880 storage control model 11 description. GA32-0061, IBM Corporation, Tucson, Ariz., 1982.

Google Scholar

[53]

IBM. Introduction to IBM 3880 storage control model 13. GA32-0062, IBM Corporation, Tucson, Ariz., 1983.

Google Scholar

[54]

IBM. IBM 3880 storage control model 13 description. GA32-0067, IBM Corporation, Tucson, Ariz., 1983.

Google Scholar

[55]

IBM. Cache RMF reporter. G320-0362, IBM Corporation, Irving, Tex., 1984.

Google Scholar

[56]

KNUTH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching Addisonwelsey, Reading, Mass., 1973.

Crossref

Google Scholar

[57]

LOWMAN, R. IBM 3880 model 13 storage subsystem. Rep., IBM Corporation, General Products Division, Tucson, Ariz., 1983.

Google Scholar

[58]

LYNCH, W.C. Do disk arms move? Perform. Eval. Rev. 1 {Dec. 1972), 3-16.

Crossref

Google Scholar

[59]

MANKEKAR, P. S. AND MILLI(~AN, C.A. Performance prediction and validation of interacting multiple subsystems in skew-loaded cached DASD Proceedings 1983 CMG International Conference (Washington, D. C., Dec.). 1983, pp. 383-387.

Google Scholar

[60]

MATTSON, R. L., GECSEI, J., SLUTZ D. R., AND TRAIGER, I. L, Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.

Google Scholar

[61]

MEMOREX. 3770 Disc cache product description manual. Mernorex Corporation, Santa Clara, Calif., 1978.

Google Scholar

[62]

ORGANmK, E. The Multics System: An Examination of its Structure, MIT Press, Cambridge, Mass., 1972.

Crossref

Google Scholar

[63]

RITCHIE D. AND THOMPSON, K. The UNIX time sharing system. Commun. CACM 17, 7 (July 1974), 365-375.

Crossref

Google Scholar

[64]

SHERMAN, S., B~,SKV.TT F. AND BROWNE, J.C. Trace driven modeling and analysis of CPU scheduling in a multiprogramming system. Commun. CACM 15, 12 (Dec. 1972}, 1063-1069.

Crossref

Google Scholar

[65]

SMITH A.J. A locality model for disk reference patterns. In Proceedings of the IEEE Computer Society Conference {Feb., San Francisco, Calif.) 1975 IEEE, New York, pp. 109-112.

Google Scholar

[66]

SMITH, A.J. Analysis of a locality model for disk reference patterns. In Proceedings of the 2nd Conference on Information Sciences and Systems {Baltimore, MD., Apr.). 1976, pp. 593--601.

Google Scholar

[67]

SMITH, A.J. Bibliography on paging and related topics. Oper. Syst. Rev. 12, 4 (Oct. 1978), 39- 56.

Crossref

Google Scholar

[68]

SMITH, A.J. On the effectiveness of buffered and multiple arm disks. In Proceedings of the 5th Computer Architecture Symposium (Palo Alto, Calif., Apr.) 242-248.

Crossref

Google Scholar

[69]

SMITH, A.J. Sequentiality and prefetching in data base systems. ACM Trans. Database Syst. 3, 3 (Sept. 1978), 223-247.

Crossref

Google Scholar

[70]

SMITH, A.J. Sequential program prefetching in memory hierarchies. IEEE Computer II, 12 (Dec. 1978), 7-21.

Google Scholar

[71]

Smith, A.J. Input/Output optimization and disk architecture: A survey. Perform. Eval. 1, 2 (198i) 104-117.

Google Scholar

[72]

SMITH, A.J. Bibliography on file system and Input/Output optimization and related topics. oper. Syst. Rev. 15, 4 (Oct 1981) 39-54.

Google Scholar

[73]

SMITH, A. J. Optimization of I/O systems by cache disk and file migration, A summary. Perform. Eval. 1, 3 (1981), 249-262.

Google Scholar

[74]

SMITH, A.J. Cache Memories. ACM Comput. Surv. 14, 3 {Sept., 1982), 473-530.

Crossref

Google Scholar

[75]

Cache disk system. Sperry Univac Product Announcement, for 5057 Cache Disk Processor and 7053 Storage Unit, Sperry Univac, 1981.

Google Scholar

[76]

Storage Technology Corporation. Sybercache 8890 intelligent disk controller. Storage Technology Corporation, Louisville, Colo. 1982.

Google Scholar

[77]

TOKUNAGA, T., HmAl, Y., AND YAMAMOTO S. Integrated disk cache system with file adaptive control., in Proceedings of the IEEE Computer Society Conference, (Washington, D. C., Sept.) IEEE, New York, 1980, pp. 412-416.

Google Scholar

[78]

WELCU, T. Effects of sequential data access on memory hierarchy design. In Proceedings of the IEEE Computer Society Conference, (San Francisco, February). IEEE, New York, 1979 pp. 65- 68.

Google Scholar

[79]

WELCH, W.A. Analysis of memory hierarchies for sequential data access. Computer 12, 5 (May 1979), 19-26.

Google Scholar

Cited By

View all

Hamdi MChen ZRadenkovic M(2024)Mitigating Cache Pollution Attack Using Deep Learning in Named Data Networking (NDN)Intelligent Computing10.1007/978-3-031-62277-9_28(432-442)Online publication date: 13-Jun-2024
https://doi.org/10.1007/978-3-031-62277-9_28
RH AS KN NP P(2022)Collaborative Edge Data Caching In Online2022 Second International Conference on Advanced Technologies in Intelligent Control, Environment, Computing & Communication Engineering (ICATIECE)10.1109/ICATIECE56365.2022.10047075(1-5)Online publication date: 16-Dec-2022
https://doi.org/10.1109/ICATIECE56365.2022.10047075
(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Show More Cited By

Recommendations

Fast Miss Ratio Curve Modeling for Storage Cache

The reuse distance (least recently used (LRU) stack distance) is an essential metric for performance prediction and optimization of storage cache. Over the past four decades, there have been steady improvements in the algorithmic efficiency of reuse ...
Disk Cache -- Miss Ratio Analysis and Design Considerations
Cache miss behavior: is it √2?
CF '06: Proceedings of the 3rd conference on Computing frontiers

It has long been empirically observed that the cache miss rate decreased as a power law of cache size, where the power was approximately -1/2. In this paper, we examine the dependence of the cache miss rate on cache size both theoretically and through ...

Reviews

Reviewer: Brian T. Bennett

This paper is valuable study of disk caches. The disk cache, a buffer in electronic storage of recently used portions of the disk address space, has the potential to improve system performance significantly. Key factors affecting performance are the miss ratio, the fraction of disk requests not captured by the cache, and the response time for hits and misses. The miss ratio is primarily dependent on the workload and secondarily on the cache design. In this paper, the workload is represented by trace data of disk I/O from three mainframe IBM or IBM-compatible data processing installations. Using the trace data, the miss ratio for disk caches of various sizes and designs are simulated and compared. For example, the miss ratio of a single cache, which can be located in main memory, is compared with that of multiple caches located at the disk control units; it is also compared with the further partition to caches for each disk. The effect on miss ratio of various block sizes (of one, two, four, or eight tracks and one, two, four, or eight cylinders) are compared. The value of caching is evaluated separately by category of file (for example, paging, temporary, and system) and by source (for example, system, interactive user, or batch job). Alternate migration algorithms such as prefetching, purge behind, and whether to cache all devices and time of day effects are evaluated. The optimal static allocation of the most frequently referenced tracks is evaluated and shown inferior to the dynamic LRU allocation. The overall performance impact of disk cache involves not only the miss ratio but the response time for hits and misses. The paper does not attempt to determine this; rather, issues such as access time, bandwidth, and multipathing are discussed. Performance and data integrity issues such as write through versus copy back, consistency over multiple CPUs, and error recovery are also discussed. Ideas such as dynamically turning the cache on and off and technology choices are presented. The issue of who should manage the cache, the CPU, or the storage controller is brought up as are implications to the operating system of disk caches. Commercial disk cache products are described with particular attention to the NEC and IBM designs. The references are very extensive and will be very valuable to other authors. In all, this is a good contribution to the storage hierachy literature. As the author suggests, more comprehensive data is needed to fully explore this subject.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 3, Issue 3

Aug. 1985

94 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/3959

Editor:
Anita K. Jones

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1985

Published in TOCS Volume 3, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

189
Total Citations
View Citations
1,943
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)15

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hamdi MChen ZRadenkovic M(2024)Mitigating Cache Pollution Attack Using Deep Learning in Named Data Networking (NDN)Intelligent Computing10.1007/978-3-031-62277-9_28(432-442)Online publication date: 13-Jun-2024
https://doi.org/10.1007/978-3-031-62277-9_28
RH AS KN NP P(2022)Collaborative Edge Data Caching In Online2022 Second International Conference on Advanced Technologies in Intelligent Control, Environment, Computing & Communication Engineering (ICATIECE)10.1109/ICATIECE56365.2022.10047075(1-5)Online publication date: 16-Dec-2022
https://doi.org/10.1109/ICATIECE56365.2022.10047075
(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Thomasian A(2022)IntroductionStorage Systems10.1016/B978-0-32-390796-5.00010-3(1-87)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00010-3
Du XLi CZhang KGherbi AVenkatasubramanian NVeiga L(2021)SHARCProceedings of the 22nd International Middleware Conference10.1145/3464298.3493389(119-131)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3464298.3493389
Xia XChen FHe QGrundy JAbdelrazek MJin H(2021)Online Collaborative Data Caching in Edge ComputingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.301634432:2(281-294)Online publication date: 1-Feb-2021
https://doi.org/10.1109/TPDS.2020.3016344
Li CHershcovitch MGoel AMorrison A(2019)CLOCK-pro+Proceedings of the 12th ACM International Conference on Systems and Storage10.1145/3319647.3325838(1-7)Online publication date: 22-May-2019
https://dl.acm.org/doi/10.1145/3319647.3325838
Zhang DLiu ALi ZJia GChen FLi Q(2019)Effective shortest travel-time path caching and estimating for location-based servicesWorld Wide Web10.1007/s11280-018-0549-222:2(455-475)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s11280-018-0549-2
Li CBreitgand DYadgar GPorter DEyal I(2018)DLIRSProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211891(59-64)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211891
Swain DMarar SMotwani NHiwarkar VSingh P(2018)Dynamic Weight Ranking algorithm using R-F score for Efficient Caching2018 International Conference on Advanced Computation and Telecommunication (ICACAT)10.1109/ICACAT.2018.8933642(1-7)Online publication date: Dec-2018
https://doi.org/10.1109/ICACAT.2018.8933642
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fast Miss Ratio Curve Modeling for Storage Cache

Disk Cache -- Miss Ratio Analysis and Design Considerations

Cache miss behavior: is it √2?

Reviews

Access critical reviews of Computing literature here