Prefetching Techniques for Client/Server, Object-Oriented
Database Systems
Nils Knafla
Graduated Ph.D. July 1999
Abstract
The performance of many object-oriented database applications suffers
from the page fetch latency which is determined by the expense of disk
access. In this work we suggest several prefetching techniques to
avoid, or at least to reduce, page fetch latency. In practice no
prediction technique is perfect and no prefetching technique can
entirely eliminate delay due to page fetch latency. Therefore we are
interested in the trade-off between the level of accuracy required for
obtaining good results in terms of elapsed time reduction and the
processing overhead needed to achieve this level of accuracy. If
prefetching accuracy is high then the total elapsed time of an
application can be reduced significantly otherwise if the prefetching
accuracy is low, many incorrect pages are prefetched and the extra
load on the client, network, server and disks decreases the whole
system performance.
Access pattern of object-oriented databases are often complex and
usually hard to predict accurately. The main thrust of our work
therefore concentrates on analysing the structure of object
relationships to obtain knowledge about page reference patterns. We
designed a technique, called OSP, which prefetches pages according to
a time constraint established by the duration of a page fetch. In
addition, every page has an associated weight that decides about the
execution of a prefetch. We implemented OSP in the EXODUS storage
manager by adding multithreading to the database client. The
performance of OSP is evaluated on different machines in interaction
with buffer management, distributed databases and other system
parameters.
For another prefetch algorithm, called PMC, we used a
Discrete-Time Markov Chain to model object relationships. We
assigned transition probabilities to object relationships and applied
the hitting times method to compute page probabilities and the
mean time to access a page. The page probability is used for the
prefetch decision and for the order of the disk queue. If the probability
of a page is higher than a threshold defined by cost/benefit
parameters then the page is a candidate for prefetching. We developed
a cost model for the benefit of a prefetch and the extra cost of an
incorrect prefetch. The effectiveness of this technique was verified
in a simulation in view of different degrees of clustering and buffer
replacement strategies.
The granularity of a prefetch is also studied by comparing the
performance of a page server and object server system that perform
prefetching. The page server requests only a single page from the
server and the object server always requests a group of objects. We
compare both systems in a simulation in which we distinguish the case
where all pages are resident at the server's buffer pool and where
pages have to be read from disk first when the page is not in buffer
pool. In addition, we suggest some optimisation techniques for the
object server.
Last modified: Wed Oct 6 17:10:36 BST 1999
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.
