Sedat Akyürek
Kenneth Salem
Abstract
An adaptive technique for reducing disk seek times is described. The technique copies frequently referenced blocks from their original locations to reserved space near the middle of the disk. Reference frequencies need not be known in advance. Instead, they are estimated by monitoring the stream of arriving requests. Trace-driven simulations show that seek times can be cut substantially by copying only a small number of blocks using this technique. The technique has been implemented by modifying a UNIX device driver. No modifications are required to the file system that uses the driver.
- AICfUREK, S. AND SALEM, K.M. 1993. Adaptive block rearrangement under UNIX. In Proceedrags of the USENIX Summer 1993 Technical Conference (Cincinnati, Ohio, June). USENIX Assoc., Berkeley, Calif., 307-321.Google Scholar
- BITTON, D. 1987. Technology trends in mass-storage systems. In Proceedings of the SIGMOD 1987 Annual Conference (San Francisco, Calif.). ACM, New York, 7-8.Google Scholar
- FLOYD, R. A. AND ELLIS, C.S. 1989. Directory reference patterns in hierarchical file systems. IEEE Trans. Knowl. Data Eng. 1, 2 (June), 238-247. Google Scholar
- FORD, D. A. AND CHRISTODOULAKIS, S. 1991. Optimizing random retrievals from CLV format optical disks. In Proceedings of the 17th International Conference on Very Large Data Bases (Barcelona, Spain, Sept.). VLDB Endowment, Saratoga, Calif., 413-422. Google Scholar
- GEIST, R. AND DANIEL, S. 1987. Continuum of disk scheduling algorithms. ACM Trans. Comput. Syst. 5, 1 (Feb.), 77-92. Google Scholar
- GROSSMAN, D. D. AND SILVERMAN, H.F. 1973. Placement of records on a secondary storage device to minimize access time. J. ACM 20, 3 (July), 429-438. Google Scholar
- HOFm, M. 1980. Disk scheduling: FCFS vs. SSTF revisited. Commun. ACM 23, 11, 645-653. Google Scholar
- KING, R.P. 1990. Disk arm movement in anticipation of future requests. ACM Trans. Cornput. Syst. 8, 3 (Aug.), 214-229. Google Scholar
- McKusIcK, M. K., JoY, W. N., LEFFLER, S. J., AND FABRY, R.S. 1984. A fast file system for UNIX. ACM Trans. Comput. Syst. 2, 3 (Aug.), 181-197. Google Scholar
- OUSTERHOUT, J. K., DA COSTA, H., HARRISON, D., KUNZE, J. A., KUPPER, M., AND THOMPSON, J. G. 1985. A trace driven analysis of the UNIX 4.2 BSD file system. In Proceedings of the l Oth ACM Symposium on Operating System Principles. ACM, New York, 15-24. Google Scholar
- RUEMMLER, C. AND WILKES, J. 1993. UNIX disk access patterns. In Proceedings of the Winter 1993 USENIX Conference (San Diego, Calif., Jan.). USENIX Assoc., Berkeley, Calif., 405-420.Google Scholar
- RUEMMLER, C. AND WILKES, J. 1991. Disk Shuffling. HPL-91-156, Hewlett-Packard Laboratories, Palo Alto, Calif. Oct.Google Scholar
- SALEM, K., BARBAR#_, D., AND LIPTON, R. J. 1992. Probabilistic diagnosis of hot spots, in Proceedings of 8th International Conference on Data Engineering (Tempe, Ariz., Feb.). 30-39. Google Scholar
- SELTZER, M., CHEN, P., AND OUSTERHOUT, j. 1990. Disk scheduling revisited. In Proceedings of the Winter 1990 USENIX Conference (Washington, D.C.). USENIX Assoc., Berkeley, Calif.Google Scholar
- SCHWETMAN, H. 1987. CSIM reference manual. Tech. Rep. ACA-ST-257-87. Microelectronics and Computer Technology Corporation, Austin, Tex.Google Scholar
- STAELIN, C. AND GARCIA-MOLINA, H. 1991. Smart filesystems. In Proceedings of the Winter 1991 USENIX Conference (Dallas, Tex.). USENIX Assoc., Berkeley, Calif., 45-51.Google Scholar
- STAELIN, C. AND GARCIA-MOLINA, H. 1990. Clustering active disk data to improve disk performance. Tech. Rep. CS-TR-283-90, Dept. of Computer Science, Princeton Univ., Princeton, N.J. Sept.Google Scholar
- VONGSATHORN, P. AND CARSON, S.D. 1990. A system for adaptive disk rearrangement. Softw. Prac. Exp. 20, 3 (Mar.), 225-242. Google Scholar
- WONG, C.K. 1980. Minimizing expected head movement in one-dimensional and two-dimensional mass storage systems. ACM Comput. Surv. 12, 2 (June), 167-178. Google Scholar
Index Terms
- Adaptive block rearrangement
Recommendations
Dynamic erasure coding decision for modern block-oriented distributed storage systems
Modern block-oriented distributed storage systems like Hadoop distributed file system have proliferated in this era of big data and cloud computing. These systems feature block-level replication in which their files are partitioned into equal-sized ...
Improving the performance of log-structured file systems with adaptive block rearrangement
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingLog-Structured File System (LFS) is famous for its optimization for write performance. Because of its append-only nature, garbage collection is needed to reclaim the space occupied by the obsolete data. The cleaning overhead could significantly decrease ...
FS2: dynamic data replication in free disk space for improving disk performance and energy consumption
SOSP '05Disk performance is increasingly limited by its head positioning latencies, i.e., seek time and rotational delay. To reduce the head positioning latencies, we propose a novel technique that dynamically places copies of data in file system's free blocks ...
Reviews
Dan Emanoil Grigoras
Large-capacity disks allow system designers to rethink their space utilization. One possibility is addressed by the authors of this paper. The main idea is to reserve some space near the middle of the disk and to keep the most frequently requested blocks of data in this region. This is the cache concept, adapted to disks and aiming at reducing the seek time. Two questions may arise: How large should this space be__?__ and How should we monitor the block traffic__?__ Also, the time interval for monitoring the traffic is a key element in making correct decisions. The authors answer these questions using simulation results drawn from many<__?__Pub Caret> experiments. The experiments are carefully chosen, although it is difficult to cover all access patterns. Even if, in particular cases, the results may not be very attractive, the idea deserves attention. Performance tuning should probably be the next stage of this research. A good idea is to copy blocks and not to move them, allowing room for further development.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments