Analysis of disk arm movement for large sequential reads

ABSTRACT

The common model for analyzing seek distances on a magnetic disk uses a continuous approximation in which the range of motion of the disk arm is the interval [0,1]. In this model, both the current location of the disk arm and the location of the next request are assumed to be points uniformly distributed on the interval [0,1] and therefore the expected seek distance to service the next request is 1/3. In many types of databases including scientific, object oriented, and multimedia database systems, a disk service request may involve fetching very large objects which must be transferred from the disk without interruption. In this paper we show that the common model does not accurately reflect disk arm movement in such cases as both the assumption of uniformity and the range of motion of the disk arm may depend on the size of the objects. We propose a more accurate model that takes into consideration the distribution of the sizes of the objects fetched as well as the disk arm scheduling policy. We provide closed form expressions for the expected seek distance in this model under various assumptions on the distribution of object sizes and the capability of the disk arm to read in both directions and to correct its position before the next read is performed.

REFERENCES

• BIGR88: Dina Bitton , Jim Gray, Disk Shadowing, Proceedings of the 14th International Conference on Very Large Data Bases, p.331-338, August 29-September 01, 1988
• COFF72: Coffman, E.G. Klimko, L. and Ryan B, Analysis of Scanning Policies for Reducing Disk Seek Times. SIAM J. on Computing. 1,3, pp 269-279, September 1972
• GER92: Gerchak, Yigal. Private Communication.
• GRAQ: Shahram Ghandeharizadeh , Luis Ramos , Zubair Asad , Waheed Qureshi, Object Placement in Parallel Hypermedia Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.243-254, September 03-06, 1991
• HOFR83: Hofri, M. Should the Two Headed Disk be Greedy? Yes It Should. Inf. Processing Letters., 16, pp 83- 85,
• KIM86: M Y Kim, Synchronized disk interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, Nov. 1986 [doi>10.1109/TC.1986.1676699]
• KING90: Richard P. King, Disk arm movement in anticipation of future requests, ACM Transactions on Computer Systems (TOCS), v.8 n.3, p.214-229, Aug. 1990 [doi>10.1145/99926.99930]
• KOEL91: David Kotz , Carla Schlatter Ellis, Practical prefetching techniques for parallel file systems, Proceedings of the first international conference on Parallel and distributed information systems, p.182-189, December 1991, Miami, Florida, United States
• NG91: Spencer W. Ng, Improving Disk Performance Via Latency Reduction, IEEE Transactions on Computers, v.40 n.1, p.22-30, January 1991 [doi>10.1109/12.67317]
• PGKA88: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• REBA89: A. L. Reddy , P. Banerjee, An Evaluation of Multiple-Disk I/O Systems, IEEE Transactions on Computers, v.38 n.12, p.1680-1690, December 1989 [doi>10.1109/12.40846]
• SIT86: Sitler, et al. Configuring tgiskr,. Tandem System Review, December 1986
• YU89: Clement Yu , Wei Sun , Dina Bitton , Qi Yang , Richard Bruno , John Tullis, Efficient placement of audio data on optical disks for real-time applications, Communications of the ACM, v.32 n.7, p.862-871, July 1989 [doi>10.1145/65445.65453]
• WONG83: C. K. Wong, Algorithmic Studies in Mass Storage Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Mass storage (e.g., magnetic, optical, RAID)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Formal models**

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Performance, Theory