.\"
.\"  This document describes the storage manager switch and Inversion
.\"  file system provided with POSTGRES.  This work was performed in
.\"  partial satisfaction of the requirements for a M.Sc. degree from
.\"  UC Berkeley.
.\"
.nr pi 3n
.nr pp 11
.nr tp 11
.nr sp 11
.\"
.\" $0 is the section-header trap
.\"
.nr xu 0
.de $0
.nr QQ \\n($0+2
.(x
.if \\n($0=1 .sp 0.7v
.ti \\n(QQm
\\*($n. \\$1
.)x
..
.de RV
.ie "\\$2"" \
\{\
.	ds VN "0.0
.	ds VD "(No date)
.	ds VT "UNAUDITED VERSION
.\}
.el \
\{\
.	ds VN \\$3
.	ds VD \\$4
.	ie "\\$7"Exp" \
.		ds VT "DRAFT
.	el \
.		ds VT \\$7
.\}
..
.de BU
.ip \0\0\0\(bu
..
.de CW
\\f(CW\\$1\\fP\\$2
..
.de (E
.(b
.ft CW
..
.de )E
.ft R
.)b
..
.ds PG "\\s-2POSTGRES\\s0
.ds PQ "\\s-2POSTQUEL\\s0
.ds UX "\\s-2UNIX\\s0
.ps 11
.\" on my printer, .79+.11 == 1 && .75 == 1.
.m1 0.79i
.m2 0.11i
.m3 0
.m4 0.75i
.ba +0.5i
.ll 6.5i
.ls 2
.RV $Header: /private/postgres/doc/papers/RCS/smgr.me,v 1.1 1992/07/14 20:10:41 mao Exp $
.rm RV
.EQ
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.ps 10
.ft 2
.ps 11
.ps \n(99
.ft \n(98
.EN
.he '''\fR%\fP'
.ft B
.ce
ABSTRACT
.sp 0.5v
.lp
Advances in mass storage technology are producing
devices capable of holding terabytes of data.
These new devices,
often called
.i "tertiary storage devices" ,
have dramatically different performance characteristics than magnetic disks.
Conventional database systems
include explicit dependencies on magnetic disk,
and so are unsuited to manage tertiary storage devices.
A layer of abstraction has been introduced between the access methods
and physical storage devices in \*(PG.
This abstraction layer supports the addition of tertiary storage.
An example implementation of a tertiary storage device manager
is presented.
Finally,
the architecture of a novel file system
that takes advantage of POSTGRES database system services is discussed.
This file system may use any of the storage devices managed by
\*(PG.
.sh 1 "INTRODUCTION"
.pp
The research presented here investigates strategies for supporting massive data
storage devices in a relational database management system.
Such devices,
often called
.i "tertiary storage devices"
because they are slower and cheaper than magnetic disk (secondary) storage,
have recently become widely available commercially.
.pp
This thesis describes contributions in three key areas.
First,
a new internal interface for the \*(PG database system
makes it easy to add new kinds of hardware to the set of storage devices
available to users.
This abstraction,
called the
.i "storage manager switch" ,
hides characteristics of underlying storage devices,
allowing the data manager to treat all devices the same.
.pp
Second,
as an example of device extensibility,
the \*(PG data storage pool incorporates
a 327GByte Sony write-once optical disk jukebox.
This device stores relational data under \*(PG version 4.0 at Berkeley.
.pp
Finally,
a new file system has been designed and implemented on top of \*(PG.
Since it is built on top of the database system,
this file system provides functionality not available in
any other file system.
Some of the services provided are time travel and transaction
protection for user file updates.
The file system also takes advantage of the storage manager switch
to provide file storage on any device known to \*(PG.
.sh 2 "An Overview of the POSTGRES Database System"
.pp
The \*(PG database system [MOSH92]
uses a novel no-overwrite technique for managing storage.
This technique allows the user to see the entire history of the database
and obviates the need for a conventional write-ahead log,
speeding recovery [STON87].
When a tuple is updated or deleted,
the original tuple is marked invalid,
but remains in place.
For updates,
a new tuple containing the new values
is added to the database.
By using transaction start times and a special status file
that records whether or not a transaction has committed,
\*(PG can present a transaction-consistent view of the database
at any moment in history.
This capability is referred to as
.i "time travel" .
Since only the start time and commit state of a transaction
must be recorded in the status file,
no special log processing is required at crash recovery time.
.pp
Periodically,
obsolete tuples must be garbage-collected from the database,
and either moved elsewhere or physically deleted.
If the tuples are not saved elsewhere,
some historical state of the database is lost.
If time travel is desired,
the tuples must be saved forever somewhere.
This process is referred to as
.i "tuple archiving" .
.pp
\*(PG includes a special-purpose process,
called the
.i "vacuum cleaner" ,
that archives tuples.
Obsolete tuples are physically removed from the relation in which they
originally appeared,
and are inserted into a separate relation.
This keeps the relation storing current state of the database small,
but the database may still grow without bound.
.sh 2 "The Importance of Tertiary Storage"
.pp
Tertiary storage is generally an order of magnitude or more
slower,
both in access latency and throughput,
than magnetic disk storage.
In most cases,
physical recording media are managed by robotics,
which move them between shelves and players on demand.
Moving a platter typically takes thousands of times longer
than transferring a data block.
However, the use of robotics multiplies
the amount of storage available to a single reader,
typically by two or three orders of magnitude.
.pp
The inclusion of tertiary storage in relational database systems
is important for several reasons.
As described in [STON87],
\*(PG relies on tertiary storage to hold historical database state.
More generally,
the relatively low cost per byte of tertiary storage
makes it attractive to systems builders,
which puts pressure on software vendors to support it.
In addition,
new data types like voice,
video,
and still images will require orders of magnitude more
space than conventional data types.
Finally,
there is strong commercial pressure to support ever-larger
conventional databases.
For example,
retailers and stockbrokers
would store every financial transaction forever
if they had sufficient space [BERN88].
.sh 2 "Thesis Overview"
.pp
This thesis describes two key extensions to the \*(PG database system.
First,
\*(PG has been made device-extensible,
so that new storage technologies may be used to store data.
Second,
a file system has been implemented on top of the database system,
providing important semantic guarantees to file system users
by taking advantage of database services.
.pp
Other device-extensible database systems include Starburst [HAAS90].
However,
Starburst does not provide a file system interface to non-database users.
Current file systems research is exploring ways of adding
functionality to existing file systems.
[CABR88], [CHUT92], and [SELT90] describe transaction-protected file systems,
and [ROOM92] supports time travel,
but none of these systems offers both services simultaneously.
.pp
The remainder of this thesis is organized as follows.
Section two gives a brief overview of the new storage manager,
and the important differences it exhibits from [STON87].
Section three presents the new storage manager architecture.
Section four describes the inclusion of a particular new storage device,
namely a 327GByte Sony write-once optical disk jukebox.
Section five introduces the Inversion file system,
which is built on top of the \*(PG database system.
Section six shows performance measurements for the Inversion file system.
Section seven presents conclusions,
and section eight lists some directions for future research.
.sh 1 "OVERVIEW OF THE NEW POSTGRES STORAGE MANAGER"
.pp
Throughout this paper,
the term
.i "storage manager"
refers to an interface layer in \*(PG that accepts requests for
operations on the data store.
This layer determines which storage device must be used to
satisfy the request and calls device-specific code to handle it.
Each device has a set of interface routines for use by the storage manager.
The collection of these routines for a single device is called a
.i "device manager" .
.sh 2 "An Arbitrary Storage Hierarchy"
.pp
[STON87] proposed a two-level storage hierarchy
consisting of magnetic disk and tertiary storage,
as shown in Figure 1.
.(z
.in +0.5i
.hl
... 0.36 7.01 4.74 10.19 0 0 4096 4096
... 0u 1831u 2522u 0u -206u 5867u 2358266u -2352605u
.PS 1831 2522 
.br
.ps 11
\h'290u'\v'1290u'\D'a288u -539u 288u 540u'
.sp -1
\h'282u'\v'714u'\D'e590u 84u'
.sp -1
\h'290u'\v'714u'\D'l0u 576u'
.sp -1
\h'865u'\v'714u'\D'l0u 576u'
.sp -1
\v'357u'\D'l0u -357u'
.sp -1
\D'l1152u 0u'
.sp -1
\h'1152u'\D'l0u 357u'
.sp -1
\h'1152u'\v'357u'\D'l-1152u 0u'
.sp -1
\h'578u'\v'354u'\D'l0u 324u'
.sp -1
\h'563u'\v'621u'\D'l15u 57u'
.sp -1
\h'592u'\v'621u'\D'l-14u 57u'
.sp -1
\h'578u'\v'948u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fImagnetic\fP'u/2u'\s11\fImagnetic\fP\h'-\w'\s11\fImagnetic\fP'u/2u'
.sp -1
\h'578u'\v'1128u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIdisk\fP'u/2u'\s11\fIdisk\fP\h'-\w'\s11\fIdisk\fP'u/2u'
.sp -1
\h'578u'\v'192u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'\s11\fIPOSTGRES data manager\fP\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'
.sp -1
\h'541u'\v'480u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRNew data stored\fP'u'\s11\fRNew data stored\fP
.sp -1
\h'541u'\v'588u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRon magnetic disk\fP'u'\s11\fRon magnetic disk\fP
.sp -1
\h'1658u'\v'1543u'\D'l0u -1151u'
.sp -1
\h'1658u'\v'392u'\D'l864u 0u'
.sp -1
\h'2522u'\v'392u'\D'l0u 1151u'
.sp -1
\h'2522u'\v'1543u'\D'l-864u 0u'
.sp -1
\h'1727u'\v'605u'\D'l0u -70u'
.sp -1
\h'1727u'\v'535u'\D'l507u 0u'
.sp -1
\h'2234u'\v'535u'\D'l0u 70u'
.sp -1
\h'2234u'\v'605u'\D'l-507u 0u'
.sp -1
\h'2303u'\v'749u'\D'l0u -219u'
.sp -1
\h'2303u'\v'530u'\D'l144u 0u'
.sp -1
\h'2447u'\v'530u'\D'l0u 219u'
.sp -1
\h'2447u'\v'749u'\D'l-144u 0u'
.sp -1
\h'1729u'\v'678u'\D'l503u 0u'
.sp -1
\h'1729u'\v'714u'\D'l503u 0u'
.sp -1
\h'1729u'\v'750u'\D'l503u 0u'
.sp -1
\h'1729u'\v'786u'\D'l503u 0u'
.sp -1
\h'1729u'\v'822u'\D'l503u 0u'
.sp -1
\h'1729u'\v'858u'\D'l503u 0u'
.sp -1
\h'1729u'\v'894u'\D'l503u 0u'
.sp -1
\h'1729u'\v'930u'\D'l503u 0u'
.sp -1
\h'1729u'\v'966u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1002u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1038u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1074u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1110u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1146u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1182u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1218u'\D'l503u 0u'
.sp -1
\h'1729u'\v'1254u'\D'l503u 0u'
.sp -1
\h'2088u'\v'1416u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fItertiary storage\fP'u/2u'\s11\fItertiary storage\fP\h'-\w'\s11\fItertiary storage\fP'u/2u'
.sp -1
\h'720u'\v'1831u'\D'l0u 0u'
.sp -1
\h'720u'\v'1831u'\D'l0u 0u'
.sp -1
\h'720u'\v'1831u'\D'l0u 0u'
.sp -1
\h'720u'\v'1831u'\D'l0u 0u'
.sp -1
\h'865u'\v'966u'\D'l792u 0u'
.sp -1
\h'1599u'\v'981u'\D'l58u -15u'
.sp -1
\h'1599u'\v'952u'\D'l58u 14u'
.sp -1
\h'1009u'\v'1092u'\h'-0.0m'\v'0.2m'\s11\fROld data moves\fP
.sp -1
\h'1009u'\v'1200u'\h'-0.0m'\v'0.2m'\s11\fRto tertiary\fP
.sp -1
\h'1009u'\v'1308u'\h'-0.0m'\v'0.2m'\s11\fRstorage\fP
.sp -1
.sp 1+1831u
.PE
.sp -2v
.ce
Figure 1: Architecture of the \*(PG Storage Manager Proposed in [STON87]
.hl
.in -0.5i
.)z
.pp
The new storage manager,
described here,
is more general.
New devices may be added to the system
by writing a set of interface routines.
When a user creates a new relation,
he assigns it to a particular device,
where it resides until it is destroyed.
The relation's archive may also be assigned to any device manager.
Thus the fixed two-level hierarchy proposed in [STON87]
is replaced by a pool of storage,
as shown in Figure 2.
.(z
.in +0.5i
.hl
... 0.24 6.89 5.24 10.01 0 0 4096 4096
... 0u 1797u 2880u 0u -137u 5766u 2359158u -2353529u
.PS 1797 2880 
.br
.ps 11
\h'2086u'\v'629u'\h'-0.0m'\v'0.2m'\s11\fRUser controls\fP
.sp -1
\h'575u'\v'1475u'\D'a288u -539u 287u 540u'
.sp -1
\h'568u'\v'899u'\D'e590u 84u'
.sp -1
\h'575u'\v'899u'\D'l0u 576u'
.sp -1
\h'863u'\v'1133u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fImagnetic\fP'u/2u'\s11\fImagnetic\fP\h'-\w'\s11\fImagnetic\fP'u/2u'
.sp -1
\h'863u'\v'1313u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIdisk\fP'u/2u'\s11\fIdisk\fP\h'-\w'\s11\fIdisk\fP'u/2u'
.sp -1
\h'1150u'\v'899u'\D'l0u 576u'
.sp -1
\v'950u'\D'l0u -86u'
.sp -1
\v'864u'\D'l432u 0u'
.sp -1
\h'432u'\v'864u'\D'l0u 86u'
.sp -1
\h'432u'\v'950u'\D'l-432u 0u'
.sp -1
\v'1037u'\D'l0u -87u'
.sp -1
\v'950u'\D'l432u 0u'
.sp -1
\h'432u'\v'950u'\D'l0u 87u'
.sp -1
\h'432u'\v'1037u'\D'l-432u 0u'
.sp -1
\v'1123u'\D'l0u -86u'
.sp -1
\v'1037u'\D'l432u 0u'
.sp -1
\h'432u'\v'1037u'\D'l0u 86u'
.sp -1
\h'432u'\v'1123u'\D'l-432u 0u'
.sp -1
\v'1210u'\D'l0u -87u'
.sp -1
\v'1123u'\D'l432u 0u'
.sp -1
\h'432u'\v'1123u'\D'l0u 87u'
.sp -1
\h'432u'\v'1210u'\D'l-432u 0u'
.sp -1
\v'1296u'\D'l0u -86u'
.sp -1
\v'1210u'\D'l432u 0u'
.sp -1
\h'432u'\v'1210u'\D'l0u 86u'
.sp -1
\h'432u'\v'1296u'\D'l-432u 0u'
.sp -1
\h'2339u'\v'1365u'\D'l0u -69u'
.sp -1
\h'2339u'\v'1296u'\D'l109u 0u'
.sp -1
\h'2448u'\v'1296u'\D'l0u 69u'
.sp -1
\h'2448u'\v'1365u'\D'l-109u 0u'
.sp -1
\h'2483u'\v'1365u'\D'l0u -69u'
.sp -1
\h'2483u'\v'1296u'\D'l109u 0u'
.sp -1
\h'2592u'\v'1296u'\D'l0u 69u'
.sp -1
\h'2592u'\v'1365u'\D'l-109u 0u'
.sp -1
\h'2627u'\v'1365u'\D'l0u -69u'
.sp -1
\h'2627u'\v'1296u'\D'l109u 0u'
.sp -1
\h'2736u'\v'1296u'\D'l0u 69u'
.sp -1
\h'2736u'\v'1365u'\D'l-109u 0u'
.sp -1
\h'2339u'\v'1475u'\D'l0u -70u'
.sp -1
\h'2339u'\v'1405u'\D'l109u 0u'
.sp -1
\h'2448u'\v'1405u'\D'l0u 70u'
.sp -1
\h'2448u'\v'1475u'\D'l-109u 0u'
.sp -1
\h'2483u'\v'1475u'\D'l0u -70u'
.sp -1
\h'2483u'\v'1405u'\D'l109u 0u'
.sp -1
\h'2592u'\v'1405u'\D'l0u 70u'
.sp -1
\h'2592u'\v'1475u'\D'l-109u 0u'
.sp -1
\h'2627u'\v'1475u'\D'l0u -70u'
.sp -1
\h'2627u'\v'1405u'\D'l109u 0u'
.sp -1
\h'2736u'\v'1405u'\D'l0u 70u'
.sp -1
\h'2736u'\v'1475u'\D'l-109u 0u'
.sp -1
\h'2304u'\v'1728u'\D'l0u -864u'
.sp -1
\h'2304u'\v'864u'\D'l576u 0u'
.sp -1
\h'2880u'\v'864u'\D'l0u 864u'
.sp -1
\h'2880u'\v'1728u'\D'l-576u 0u'
.sp -1
\h'2339u'\v'1008u'\D'l0u -69u'
.sp -1
\h'2339u'\v'939u'\D'l109u 0u'
.sp -1
\h'2448u'\v'939u'\D'l0u 69u'
.sp -1
\h'2448u'\v'1008u'\D'l-109u 0u'
.sp -1
\h'2483u'\v'1008u'\D'l0u -69u'
.sp -1
\h'2483u'\v'939u'\D'l109u 0u'
.sp -1
\h'2592u'\v'939u'\D'l0u 69u'
.sp -1
\h'2592u'\v'1008u'\D'l-109u 0u'
.sp -1
\h'2627u'\v'1008u'\D'l0u -69u'
.sp -1
\h'2627u'\v'939u'\D'l109u 0u'
.sp -1
\h'2736u'\v'939u'\D'l0u 69u'
.sp -1
\h'2736u'\v'1008u'\D'l-109u 0u'
.sp -1
\h'2771u'\v'1043u'\D'l0u -110u'
.sp -1
\h'2771u'\v'933u'\D'l69u 0u'
.sp -1
\h'2840u'\v'933u'\D'l0u 110u'
.sp -1
\h'2840u'\v'1043u'\D'l-69u 0u'
.sp -1
\h'2771u'\v'1187u'\D'l0u -110u'
.sp -1
\h'2771u'\v'1077u'\D'l69u 0u'
.sp -1
\h'2840u'\v'1077u'\D'l0u 110u'
.sp -1
\h'2840u'\v'1187u'\D'l-69u 0u'
.sp -1
\h'2771u'\v'1331u'\D'l0u -110u'
.sp -1
\h'2771u'\v'1221u'\D'l69u 0u'
.sp -1
\h'2840u'\v'1221u'\D'l0u 110u'
.sp -1
\h'2840u'\v'1331u'\D'l-69u 0u'
.sp -1
\h'2771u'\v'1475u'\D'l0u -110u'
.sp -1
\h'2771u'\v'1365u'\D'l69u 0u'
.sp -1
\h'2840u'\v'1365u'\D'l0u 110u'
.sp -1
\h'2840u'\v'1475u'\D'l-69u 0u'
.sp -1
\h'2339u'\v'1117u'\D'l0u -69u'
.sp -1
\h'2339u'\v'1048u'\D'l109u 0u'
.sp -1
\h'2448u'\v'1048u'\D'l0u 69u'
.sp -1
\h'2448u'\v'1117u'\D'l-109u 0u'
.sp -1
\h'2483u'\v'1117u'\D'l0u -69u'
.sp -1
\h'2483u'\v'1048u'\D'l109u 0u'
.sp -1
\h'2592u'\v'1048u'\D'l0u 69u'
.sp -1
\h'2592u'\v'1117u'\D'l-109u 0u'
.sp -1
\h'2627u'\v'1117u'\D'l0u -69u'
.sp -1
\h'2627u'\v'1048u'\D'l109u 0u'
.sp -1
\h'2736u'\v'1048u'\D'l0u 69u'
.sp -1
\h'2736u'\v'1117u'\D'l-109u 0u'
.sp -1
\h'2339u'\v'1221u'\D'l0u -69u'
.sp -1
\h'2339u'\v'1152u'\D'l109u 0u'
.sp -1
\h'2448u'\v'1152u'\D'l0u 69u'
.sp -1
\h'2448u'\v'1221u'\D'l-109u 0u'
.sp -1
\h'2483u'\v'1221u'\D'l0u -69u'
.sp -1
\h'2483u'\v'1152u'\D'l109u 0u'
.sp -1
\h'2592u'\v'1152u'\D'l0u 69u'
.sp -1
\h'2592u'\v'1221u'\D'l-109u 0u'
.sp -1
\h'2627u'\v'1221u'\D'l0u -69u'
.sp -1
\h'2627u'\v'1152u'\D'l109u 0u'
.sp -1
\h'2736u'\v'1152u'\D'l0u 69u'
.sp -1
\h'2736u'\v'1221u'\D'l-109u 0u'
.sp -1
\h'2339u'\v'1259u'\D'l395u 0u'
.sp -1
\h'2590u'\v'1565u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIExabyte 8mm\fP'u/2u'\s11\fIExabyte 8mm\fP\h'-\w'\s11\fIExabyte 8mm\fP'u/2u'
.sp -1
\h'2590u'\v'1673u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fItape jukebox\fP'u/2u'\s11\fItape jukebox\fP\h'-\w'\s11\fItape jukebox\fP'u/2u'
.sp -1
\h'789u'\v'1728u'\D'l0u 0u'
.sp -1
\h'789u'\v'1728u'\D'l0u 0u'
.sp -1
\h'789u'\v'1728u'\D'l0u 0u'
.sp -1
\h'789u'\v'1728u'\D'l0u 0u'
.sp -1
\h'432u'\v'501u'\D'l0u -144u'
.sp -1
\h'432u'\v'357u'\D'l1728u 0u'
.sp -1
\h'2160u'\v'357u'\D'l0u 144u'
.sp -1
\h'2160u'\v'501u'\D'l-1728u 0u'
.sp -1
\h'1294u'\v'143u'\D'l0u 216u'
.sp -1
\h'1280u'\v'301u'\D'l14u 58u'
.sp -1
\h'1309u'\v'301u'\D'l-15u 58u'
.sp -1
\h'1043u'\v'503u'\D'l-756u 360u'
.sp -1
\h'333u'\v'825u'\D'l-46u 38u'
.sp -1
\h'345u'\v'851u'\D'l-58u 12u'
.sp -1
\h'1150u'\v'503u'\D'l-287u 360u'
.sp -1
\h'888u'\v'809u'\D'l-25u 54u'
.sp -1
\h'910u'\v'827u'\D'l-47u 36u'
.sp -1
\h'1438u'\v'503u'\D'l288u 360u'
.sp -1
\h'1679u'\v'827u'\D'l47u 36u'
.sp -1
\h'1702u'\v'809u'\D'l24u 54u'
.sp -1
\h'1582u'\v'503u'\D'l864u 360u'
.sp -1
\h'2388u'\v'854u'\D'l58u 9u'
.sp -1
\h'2399u'\v'827u'\D'l47u 36u'
.sp -1
\h'1365u'\v'1077u'\D'l0u -69u'
.sp -1
\h'1365u'\v'1008u'\D'l507u 0u'
.sp -1
\h'1872u'\v'1008u'\D'l0u 69u'
.sp -1
\h'1872u'\v'1077u'\D'l-507u 0u'
.sp -1
\h'1941u'\v'1221u'\D'l0u -213u'
.sp -1
\h'1941u'\v'1008u'\D'l144u 0u'
.sp -1
\h'2085u'\v'1008u'\D'l0u 213u'
.sp -1
\h'2085u'\v'1221u'\D'l-144u 0u'
.sp -1
\h'1366u'\v'1151u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1187u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1222u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1259u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1294u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1331u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1366u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1403u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1438u'\D'l504u 0u'
.sp -1
\h'1366u'\v'1475u'\D'l504u 0u'
.sp -1
\h'1296u'\v'1797u'\D'l0u -933u'
.sp -1
\h'1296u'\v'864u'\D'l864u 0u'
.sp -1
\h'2160u'\v'864u'\D'l0u 933u'
.sp -1
\h'2160u'\v'1797u'\D'l-864u 0u'
.sp -1
\h'576u'\v'144u'\D'l0u -144u'
.sp -1
\h'576u'\D'l1440u 0u'
.sp -1
\h'2016u'\D'l0u 144u'
.sp -1
\h'2016u'\v'144u'\D'l-1440u 0u'
.sp -1
\h'1294u'\v'449u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fINew POSTGRES storage manager switch\fP'u/2u'\s11\fINew POSTGRES storage manager switch\fP\h'-\w'\s11\fINew POSTGRES storage manager switch\fP'u/2u'
.sp -1
\h'1331u'\v'269u'\h'-0.0m'\v'0.2m'\s11\fRAll data treated identically\fP
.sp -1
\h'2230u'\v'737u'\h'-0.0m'\v'0.2m'\s11\fRdata placement\fP
.sp -1
\h'215u'\v'1385u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fImain\fP'u/2u'\s11\fImain\fP\h'-\w'\s11\fImain\fP'u/2u'
.sp -1
\h'215u'\v'1493u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fImemory\fP'u/2u'\s11\fImemory\fP\h'-\w'\s11\fImemory\fP'u/2u'
.sp -1
\h'1726u'\v'1601u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fISony optical disk\fP'u/2u'\s11\fISony optical disk\fP\h'-\w'\s11\fISony optical disk\fP'u/2u'
.sp -1
\h'1726u'\v'1709u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIjukebox\fP'u/2u'\s11\fIjukebox\fP\h'-\w'\s11\fIjukebox\fP'u/2u'
.sp -1
\h'1294u'\v'89u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'\s11\fIPOSTGRES data manager\fP\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'
.sp -1
.sp 1+1797u
.PE
.sp
.ce
Figure 2: New \*(PG Storage Manager Architecture
.hl
.in -0.5i
.)z
The \*(PG data manager no longer communicates directly
with devices to read or write data.
Instead,
a new interface layer handles data placement
and retrieval.
.pp
Device managers currently exist for magnetic disk,
battery-backed main memory,
and the Sony optical disk jukebox.
Other devices that may be incorporated in the future
include rewritable optical disk jukeboxes
and helical scan tape jukeboxes.
The user may elect to locate a new relation on any of these devices.
Once the relation is assigned to a device manager,
its location is transparent to the user.
It is accessed in exactly the same way,
regardless of its placement.
.sh 2 "Using Criteria other than Time to Determine Data Placement"
.pp
Since archiving historical data is an important feature in \*(PG,
the vacuum cleaner uses tuple update times to move data from
a
.q current
relation into a
.q historical
one.
The original storage manager proposal declared that current
data would be stored on a fast device
(magnetic disk),
and historical data on some slower device.
The implicit assumption is that current data will
be accessed more frequently than historical data.
The desired policy is to make the most frequent accesses fastest.
.pp
The design proposed in [STON87] has several limitations.
First,
there exist databases from which no tuples ever get deleted.
Consider,
for example,
a library of books.
New volumes are purchased,
but old ones remain in the collection forever.
In this case,
there is no historical data,
and the current database state grows without bound.
.pp
Second,
the assumption that current data will be read more frequently
than historical data is not always correct.
For example,
accountants at the Internal Revenue Service audit tax returns
two years after they are filed.
In this case,
the best policy would be to place all two-year-old tax returns
on magnetic disk,
and returns that are younger or older on tertiary storage.
IRS employees could then more quickly choose two-year-old returns to audit.
.pp
Finally,
users may want to specify criteria other than time for
data placement.
For example,
consider a credit-card billing database.
Tuples for customers who make many purchases
should be stored in main memory,
to speed up billing updates on their accounts.
Tuples for less active customers might be stored on magnetic
disk.
The least active customers of all could have their tuples
migrated to an optical disk store,
since the extra cost of fetching their bills would not be
incurred very often.
.pp
In all of these examples,
the user is able to predict his access patterns reliably,
and can instruct the database system how data should be laid
out in order to minimize access times.
Current systems support caches intended to speed up accesses,
but these caches are not subject to user control.
.pp
The new storage manager
supports a more general model than its predecessor.
First,
the storage manager
does away with the notion of a fixed two-level data storage hierarchy.
New devices with new performance characteristics may be added
to the database system.
When new relations are created,
they may be located on any storage device,
and their archives may be located on any storage device.
Thus,
a relation's current data may be put on the Sony write-once jukebox
and its historical data on magnetic disk,
if desired.
This would make accesses to old data faster than accesses to new data.
.pp
Second,
using the \*(PG rule system [POTA92],
the user may create a logical relation that is a view
of many physical relations.
These physical relations may be located on different storage devices.
Further,
the user may specify rules that move data from one physical relation
to another in response to an update.
Thus the user may choose to partition a logical relation
based on an arbitrarily complex function of any of its attributes.
The same strategy applies to historical data:
the user may partition the single logical relation storing history
among several physical relations,
according to whatever policy he desires.
.pp
For example,
consider a relational schema for storing tuples on employees.
For each employee,
the system should record an employee number,
a name,
a salary,
and a scanned photograph for security purposes.
A conventional schema would be
.(E
EMP(id = int, name = text, salary = float,
    picture = image)
.)E
where
.CW image
is a type known to the database system,
and used to store pictures.
.pp
One problem with the schema above is that it stores all data
in every employee tuple on magnetic disk.
Since scanned photographs are likely to be very large,
storing them on magnetic disk will be expensive.
In addition,
it might be preferable to store salaries in memory,
so that functions that operate on them can run more quickly.
Since the user may have a good idea of the sizes and access
frequencies of columns in the
.CW EMP
table,
he should be able to partition tuples to reduce storage
costs and speed up common queries.
.pp
The new storage manager allows the user to declare a more flexible schema.
The example above can be rewritten as
.(E
ENAME (id = int, name = text) store = "magnetic disk"
ESAL (id = int, salary = float) store = "main memory"
EPHOTO (id = int, photo = image) store = "sony jukebox"
.)E
The original
.CW EMP
relation has been decomposed into three new physical relations.
The following \*(PG rule will reconstruct the logical
.CW EMP
relation on demand:
.(E
on retrieve to EMP do instead
    retrieve (n.id, n.name, s.salary, p.photo)
        from n in ENAME, s in ESAL, p in EPHOTO
        where n.id = s.id and s.id = p.id
.)E
In addition,
a rule may be declared to handle updates on the logical
.CW EMP
relation:
.(E
on append to EMP do instead
    append ENAME (id = new.id, name = new.name)
    append ESAL (id = new.id, salary = new.salary)
    append EPHOTO (id = new.id, photo = new.photo)
.)E
.pp
Thus,
the new storage manager eliminates the fixed two-level storage
hierarchy.
Data may be placed on a device in order to conserve space
(as in the case of
.CW EMP.photo )
or in order to speed up accesses
(as in the case of
.CW EMP.salary ).
Using the \*(PG rules system in conjunction with the new storage manager
gives the user considerable freedom to horizontally or vertically
partition data tables to achieve good performance while conserving
expensive storage space.
.sh 1 "ARCHITECTURE OF THE NEW POSTGRES STORAGE MANAGER"
.pp
This section describes the architecture of the new storage manager in detail.
It begins with the design changes that were necessary
in the \*(PG data manager,
and is followed by the new design.
.sh 2 "Changes to POSTGRES"
.pp
Before the design and installation of the new storage manager,
\*(PG contained hard-coded dependencies on magnetic disk.
These dependencies were manifested in the following ways.
.BU
The query optimizer used a cost function that assumed
the performance characteristics of magnetic disk for
data stored in the database.
.BU
The code that handled updates to the database assumed
that data blocks could be overwritten in place.
.BU
The query planner and executor used system calls on the \*(UX file system
to compute characteristics like
the length and modification times of files storing relations.
.pp
Tertiary storage has dramatically different performance
characteristics than magnetic disk.
For example,
throughput and seek times for optical disk are typically
an order of magnitude worse than those for magnetic disk.
Tape performs poorly under random access patterns.
Robotics introduce sharp discontinuities into the performance
curves of jukebox devices,
because moving a tape or disk from a shelf to a drive takes tens of
seconds.
.pp
Hard-coded dependencies on magnetic disk made it very hard
to add new storage devices to the old system.
Even if it were possible to store data on the new devices,
the query optimizer and executor would make poor decisions
for queries that accessed tertiary storage.
.pp
Thus,
the most important change to \*(PG was to extract
dependencies on magnetic disk.
First,
the operations that the data manager carried out on storage devices
were determined.
From these operations,
an abstraction was created that hid device differences.
These abstractions are discussed in section 3.3.
A set of interface routines was defined that supported this
abstraction.
These interface routines are listed in detail in section 3.4.
.sh 2 "The Storage Manager Switch"
.pp
The abstraction that hides device-specific characteristics from
the data manager is called the
.i "storage manager switch" .
The storage manager switch is similar
to the
.i cdevsw
and
.i bdevsw
interfaces of \*(UX [LEFF89]
and the user-supplied backing store interface in Mach [RASH88].
.pp
As discussed in the previous section,
installing the storage manager switch required
that the abstract operations required on the data store be identified.
For example,
the interface requires
routines for opening relations and instantiating particular
8kByte relation blocks.
.pp
Once the abstract interface was defined,
an appropriate structure
(the
.i "storage manager switch table" )
was compiled into the data manager.
This structure contains an entry for all existing device managers.
New device types are added by editing a source file,
adding appropriate entries to the storage manager switch table,
and recompiling the \*(PG database system.
.pp
Whenever a device operation is required,
the data manager calls the storage manager to carry it out.
Every relation is tagged in \*(PG with the device manager
on which it appears.
The storage manager identifies the appropriate device and routine in
the storage manager switch table,
and calls the device manager to execute the routine
on behalf of the data manager.
.pp
Data may be located on a particular device manager
at the granularity of a relation.
Physical relations may not be horizontally or vertically partitioned,
but as mentioned before,
the \*(PG rules system can be used to create a partitioned logical relation.
.sh 2 "Isolation of Device Differences"
.pp
New device managers are written to manage new types of devices.
For example,
main memory,
magnetic disk,
and the Sony optical disk jukebox
are all managed by different device managers.
To isolate the database system from the underlying devices,
device managers are required to accept and return data
in the format used internally by the data manager.
This means,
among other things,
that data pages from user relations must be accepted and returned
in units of 8kBytes.
.pp
Nevertheless,
there is no requirement that a device manager use the internal
representation when writing a page to persistent storage.
Data pages may be compressed,
broken into pieces,
or concatenated into larger units by a device manager,
as long as the original page can be reconstructed on demand.
.pp
In addition,
device managers may implement caches managed according
to an appropriate policy.
This means that the new \*(PG architecture supports a multi-level cache.
A main-memory cache of recently-used blocks is maintained in
shared memory by the buffer manager.
The buffer manager calls the storage manager to
migrate pages between shared memory and persistent storage.
A device manager may implement a separate cache for its own use,
subject to whatever policy it likes.
For example,
the Sony jukebox device manager maintains a cache of
.i extents
(contiguous collections of user data blocks)
on magnetic disk.
If there is locality of reference in accesses to a Sony jukebox relation,
then some requests may be satisfied without accessing the jukebox
device at all.
This cache will be described in more detail in section 4.2.
.sh 2 "The Storage Manager Switch Interface"
.pp
This section defines the interface presented by the storage manager switch.
Although the routines presented here are specific to \*(PG,
the strategy of isolating storage management from data management is general,
and similar routines should exist for conventional database management
systems.
.pp
Figure 3 shows the storage manager switch data structure,
.CW f_smgr .
.(z
.in +0.5i
.hl
.ft C
.nf
typedef struct f_smgr {
    int         (*smgr_init)();         /* may be NULL */
    int         (*smgr_shutdown)();     /* may be NULL */
    int         (*smgr_create)();
    int         (*smgr_unlink)();
    int         (*smgr_extend)();
    int         (*smgr_open)();
    int         (*smgr_close)();
    int         (*smgr_read)();
    int         (*smgr_write)();
    int         (*smgr_flush)();
    int         (*smgr_blindwrt)();
    int         (*smgr_nblocks)();
    int         (*smgr_commit)();       /* may be NULL */
    int         (*smgr_abort)();        /* may be NULL */
    int         (*smgr_cost)();
} f_smgr;
.ft
.fi
.sp
.ce
Figure 3: The \fCf_smgr\fP Storage Manager Switch Structure
.hl
.in -0.5i
.)z
This structure defines the interface routines
that all device managers must define.
When a new device type is added to \*(PG,
this structure is filled in with function pointers appropriate to the device,
and \*(PG is recompiled.
The storage manager calls these routines in response
to requests from the data manager.
In some cases,
the switch entry for an interface routine may be
.CW NULL .
This means that the corresponding operation is not defined for the
device in question.
Unless otherwise stated in the sections that follow,
all interface routines return an integer status code
indicating success or failure.
.pp
Table 1 summarizes the responsibilities
of these interface routines.
.(z
.in +0.5i
.ft R
.hl
.TS
.if \n+(b.=1 .nr d. \n(.c-\n(c.-1
.de 3f
.ps \n(.s
.vs \n(.vu
.in \n(.iu
.if \n(.u .fi
.if \n(.j .ad
.if \n(.j=0 .na
..
.nf
.nr #~ 0
.if \n(.T .if n .nr #~ 0.6n
.ds #d .d
.if \(ts\n(.z\(ts\(ts .ds #d nl
.fc
.nr 3d \n(.s
.rm 4g 4h
.nr 3e \n(.lu
.eo
.am 4h
.br
.di a+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Called at startup to allow initialization.
.br
.di
.nr a| \n(dn
.nr a- \n(dl
..
.ec \
.eo
.am 4h
.br
.di b+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Called at shutdown to allow graceful exit.
.br
.di
.nr b| \n(dn
.nr b- \n(dl
..
.ec \
.eo
.am 4h
.br
.di c+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Create relation \fIr\fP.
.br
.di
.nr c| \n(dn
.nr c- \n(dl
..
.ec \
.eo
.am 4h
.br
.di d+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Destroy relation \fIr\fP.
.br
.di
.nr d| \n(dn
.nr d- \n(dl
..
.ec \
.eo
.am 4h
.br
.di e+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Add a new block to the end of relation \fIr\fP
and fill it with data from \fIbuf\fP.
.br
.di
.nr e| \n(dn
.nr e- \n(dl
..
.ec \
.eo
.am 4h
.br
.di f+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Open relation \fIr\fP.
The relation descriptor includes
a pointer to the state for the open object.
.br
.di
.nr f| \n(dn
.nr f- \n(dl
..
.ec \
.eo
.am 4h
.br
.di g+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Close relation \fIr\fP.
.br
.di
.nr g| \n(dn
.nr g- \n(dl
..
.ec \
.eo
.am 4h
.br
.di h+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Read block \fIblock\fP of relation \fIr\fP into the buffer
pointed to by \fIbuf\fP.
.br
.di
.nr h| \n(dn
.nr h- \n(dl
..
.ec \
.eo
.am 4h
.br
.di i+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Write \fIbuf\fP as block \fIblock\fP of relation \fIr\fP.
.br
.di
.nr i| \n(dn
.nr i- \n(dl
..
.ec \
.eo
.am 4h
.br
.di j+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Write \fIbuf\fP synchronously as block \fIblock\fP of relation \fIr\fP.
.br
.di
.nr j| \n(dn
.nr j- \n(dl
..
.ec \
.eo
.am 4h
.br
.di k+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Do a ``blind write'' of buffer \fIbuf\fP as block \fIblk\fP
of the relation named \fIn\s-2\dr\u\s0\fP in the database named
\fIn\s-2\dd\u\s0\fP.
.br
.di
.nr k| \n(dn
.nr k- \n(dl
..
.ec \
.eo
.am 4h
.br
.di l+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Return the number of blocks in relation \fIr\fP.
.br
.di
.nr l| \n(dn
.nr l- \n(dl
..
.ec \
.eo
.am 4h
.br
.di m+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Force all dirty data to stable storage.
.br
.di
.nr m| \n(dn
.nr m- \n(dl
..
.ec \
.eo
.am 4h
.br
.di n+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Changes made during this transaction may be discarded.
.br
.di
.nr n| \n(dn
.nr n- \n(dl
..
.ec \
.eo
.am 4h
.br
.di o+
.3f
.ft \n(.f
.ll 3in
.if \n(.l<\n(4h .ll \n(4hu
.in 0
.na
.fi
Return in \fIc\fP the estimated cost of accessing
.i nblock
blocks and
.i ntuples
tuples of relation \fIr\fP.
.br
.di
.nr o| \n(dn
.nr o- \n(dl
..
.ec \
.3f
.nf
.ll \n(3eu
.nr 4g 0
.nr 3i \w\fIRoutine\fP
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_init()
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_shutdown()
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_create(\fIr\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_unlink(\fIr\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_extend(\fIr\fP, \fIbuf\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_open(\fIr\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_close(\fIr\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_read(\fIr\fP, \fIblock\fP, \fIbuf\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_write(\fIr\fP, \fIblock\fP, \fIbuf\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_flush(\fIr\fP, \fIblock\fP, \fIbuf\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_blindwrt(\fIn\s-2\dd\u\s0\fP, \fIn\s-2\dr\u\s0\fP, \fIi\s-2\dd\u\s0\fP, \fIi\s-2\dr\u\s0\fP, \fIblk\fP, \fIbuf\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_nblocks(\fIr\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_commit()
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_abort()
.if \n(4g<\n(3i .nr 4g \n(3i
.nr 3i \wsmgr_cost(\fIr\fP, \fInblocks\fP, \fIntuples\fP, \fIc\fP)
.if \n(4g<\n(3i .nr 4g \n(3i
.4g
.rm 4g
.nr 4h 0
.nr 3i \w\fIPurpose\fP
.if \n(4h<\n(3i .nr 4h \n(3i
.4h
.rm 4h
.nr 3i \n(a-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(b-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(c-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(d-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(e-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(f-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(g-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(h-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(i-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(j-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(k-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(l-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(m-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(n-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i \n(o-
.if \n(4h<\n(3i .nr 4h \n(3i
.nr 3i 3in
.if \n(4h<\n(3i .nr 4h \n(3i
.3f
.nf
.ll \n(3eu
.nr 3i 1n
.nr 4f 0
.nr 4a \n(4f+((2*\n(3i)/2)
.nr 4g +\n(4a
.nr 4b \n(4g+((6*\n(3i)/2)
.nr 4h +\n(4b
.nr TW \n(4h
.nr TW +((2*\n(3i)/2)
.if t .if \n(TW>\n(.lu .tm Table at line 1247 file Input is too wide - \n(TW units
.ne 16v+30p
.nr #I \n(.i
.in +(\n(.lu-\n(TWu-\n(.iu)/2u
.fc  
.nr #T 0-1
.nr #a 0-1
.nr #a 0-1
.eo
.de T#
.nr 3f 1m
.ds #d .d
.if \(ts\n(.z\(ts\(ts .ds #d nl
.mk ##
.nr ## -1v
.ls 1
.if \n(#T>=0 .nr #a \n(#T
.if \n(T. .vs \n(.vu-\n(.sp
.if \n(T. \v'-1p'\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0\v'2p'\h'|0'\h'-1p'\s\n(3d\l'|\n(TWu+1p\(ul'\s0\v'-1p'
.if \n(T. .vs
.if \n(#a>=0 .sp -1
.if \n(#a>=0 \h'|0'\h'-1p'\v'1p'\s\n(3d\h'-\n(#~u'\L'|\n(#au-1v-2p'\s0\v'\n(\*(#du-\n(#au+1v+1p'\h'2p'\v'-1p'\s\n(3d\h'-\n(#~u'\L'|\n(#au-1v+2p'\s0\v'\n(\*(#du-\n(#au+1v-1p'\h'|\n(TWu'
.if \n(#a>=0 .sp -1
.if \n(#a>=0 \h'(|\n(4bu+|\n(4gu)/2u'\v'-1p'\s\n(3d\h'-\n(#~u'\L'|\n(#au-1v+2p'\s0\v'\n(\*(#du-\n(#au+1v-1p'\h'|\n(TWu'
.if \n(#a>=0 .sp -1
.if \n(#a>=0 \h'|\n(TWu'\h'-1p'\v'-1p'\s\n(3d\h'-\n(#~u'\L'|\n(#au-1v+2p'\s0\v'\n(\*(#du-\n(#au+1v-1p'\h'2p'\v'1p'\s\n(3d\h'-\n(#~u'\L'|\n(#au-1v-2p'\s0\v'\n(\*(#du-\n(#au+1v+1p'
.ls
..
.ec
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\v'-1p'\h'|0'\h'-1p'\s\n(3d\l'|\n(TWu+1p\(ul'\s0\v'2p'\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0\v'-1p'
.vs \n(3gu
.mk #a
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'\fIRoutine\fP\h'|\n(4bu'\fIPurpose\fP
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\v'-1p'\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0\v'2p'\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0\v'-1p'
.vs \n(3gu
.ne \n(a|u+\n(.Vu
.if (\n(a|+\n(#^-1v)>\n(#- .nr #- +(\n(a|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_init()\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.a+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(b|u+\n(.Vu
.if (\n(b|+\n(#^-1v)>\n(#- .nr #- +(\n(b|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_shutdown()\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.b+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(c|u+\n(.Vu
.if (\n(c|+\n(#^-1v)>\n(#- .nr #- +(\n(c|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_create(\fIr\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.c+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(d|u+\n(.Vu
.if (\n(d|+\n(#^-1v)>\n(#- .nr #- +(\n(d|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_unlink(\fIr\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.d+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(e|u+\n(.Vu
.if (\n(e|+\n(#^-1v)>\n(#- .nr #- +(\n(e|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_extend(\fIr\fP, \fIbuf\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.e+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(f|u+\n(.Vu
.if (\n(f|+\n(#^-1v)>\n(#- .nr #- +(\n(f|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_open(\fIr\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.f+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(g|u+\n(.Vu
.if (\n(g|+\n(#^-1v)>\n(#- .nr #- +(\n(g|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_close(\fIr\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.g+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(h|u+\n(.Vu
.if (\n(h|+\n(#^-1v)>\n(#- .nr #- +(\n(h|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_read(\fIr\fP, \fIblock\fP, \fIbuf\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.h+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(i|u+\n(.Vu
.if (\n(i|+\n(#^-1v)>\n(#- .nr #- +(\n(i|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_write(\fIr\fP, \fIblock\fP, \fIbuf\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.i+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(j|u+\n(.Vu
.if (\n(j|+\n(#^-1v)>\n(#- .nr #- +(\n(j|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_flush(\fIr\fP, \fIblock\fP, \fIbuf\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.j+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(k|u+\n(.Vu
.if (\n(k|+\n(#^-1v)>\n(#- .nr #- +(\n(k|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_blindwrt(\fIn\s-2\dd\u\s0\fP, \fIn\s-2\dr\u\s0\fP, \fIi\s-2\dd\u\s0\fP, \fIi\s-2\dr\u\s0\fP, \fIblk\fP, \fIbuf\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.k+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.sp 0.1v
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(l|u+\n(.Vu
.if (\n(l|+\n(#^-1v)>\n(#- .nr #- +(\n(l|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_nblocks(\fIr\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.l+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(m|u+\n(.Vu
.if (\n(m|+\n(#^-1v)>\n(#- .nr #- +(\n(m|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_commit()\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.m+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(n|u+\n(.Vu
.if (\n(n|+\n(#^-1v)>\n(#- .nr #- +(\n(n|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_abort()\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.n+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.nr 3g \n(.v
.vs \n(.vu-\n(.sp
\h'|0'\h'1p'\s\n(3d\l'|\n(TWu-1p\(ul'\s0
.vs \n(3gu
.ne \n(o|u+\n(.Vu
.if (\n(o|+\n(#^-1v)>\n(#- .nr #- +(\n(o|+\n(#^-\n(#--1v)
.ta \n(4gu \n(4hu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'smgr_cost(\fIr\fP, \fInblocks\fP, \fIntuples\fP, \fIc\fP)\h'|\n(4bu'
.mk ##
.nr 3b \n(##
.sp |\n(##u-1v
.nr 3h \n(4bu
.in +\n(3hu
.o+
.in -\n(3hu
.mk 3c
.if \n(3c>\n(3b .nr 3b \n(3c
.sp |\n(3bu
.fc
.nr T. 1
.T# 1
.in \n(#Iu
.3f
.nr #a 0
.rm a+
.rm b+
.rm c+
.rm d+
.rm e+
.rm f+
.rm g+
.rm h+
.rm i+
.rm j+
.rm k+
.rm l+
.rm m+
.rm n+
.rm o+
.TE
.if \n-(b.=0 .nr c. \n(.c-\n(d.-106
.ft B
.sp 0.5v
.ce
Table 1: The \*(PG Storage Manager Switch Interface
.ft
.hl
.in -0.5i
.)z
The rest of this section gives more detailed descriptions.
.sh 3 "smgr_init"
.pp
The routine
.(E
int
smgr_init()
.)E
is called when \*(PG starts up,
and should initialize any private data used by a device manager.
In addition,
the first call to this routine should initialize any shared
data.
Typically,
this is done by noticing whether shared data exists,
and creating and initializing it if it does not.
If a particular device manager requires no initialization,
it may define this routine to be NULL.
.sh 3 "smgr_shutdown"
.pp
The routine
.(E
int
smgr_shutdown()
.)E
is analogous to
.CW smgr_init() ,
but is called when \*(PG exits cleanly.
Any necessary cleanup may be done here.
If no work is required,
this routine may be NULL.
.sh 3 "smgr_create"
.pp
The routine to create new relations on a particular device manager is
.(E
int
smgr_create(reln)
    Relation reln;
.)E
The
.CW reln
argument points to a \*(PG relation descriptor for the relation to
be created.
The device manager should initialize whatever storage structure
is required for the new relation.
For example,
the magnetic disk device manager creates an empty file with the
name of the relation.
.sh 3 "smgr_unlink"
.pp
The routine
.(E
int
smgr_unlink(reln)
    Relation reln;
.)E
is called by the storage manager to destroy the relation described by
.CW reln .
Device managers may take whatever action is appropriate.
For example,
the magnetic disk device manager removes the relation's associated
file and archive, and reclaims the disk blocks they occupy.
Since the Sony write-once drive cannot reclaim blocks once they are used,
the Sony jukebox device manager simply marks the relation as
destroyed and returns.
.sh 3 "smgr_extend"
.pp
When a relation must be extended with a new data block,
the data manager calls
.(E
int
smgr_extend(reln, buffer)
    Relation reln;
    char *buffer;
.)E
to do the work.
The buffer is an 8kByte buffer in the format used by the data manager
internally.
The data manager assumes that 8kByte data blocks in relations are numbered
starting from one.
Thus
.CW smgr_extend()
must logically allocate a new block for the relation pointed to by
.CW reln
and store some representation of
.CW buffer
there.
.sh 3 "smgr_open"
.pp
The routine
.(E
int
smgr_open(reln)
    Relation reln;
.)E
should open the relation pointed to by
.CW reln
and return a file descriptor for it.
The notion of file descriptors is a holdover from
the pre-storage manager switch days,
and is no longer necessary.
If file descriptors make no sense for a given device,
then the associated device manager may return any non-negative value.
A negative return value indicates an error.
.sh 3 "smgr_close"
.pp
When the data manager is finished with a relation,
it calls
.(E
int
smgr_close(reln)
    Relation reln;
.)E
The device manager may release resources associated with the
relation pointed to by
.CW reln .
.sh 3 "smgr_read"
.pp
To instantiate an 8kByte data block from a relation,
the data manager calls
.(E
int
smgr_read(reln, blocknum, buffer)
    Relation reln;
    BlockNumber blocknum;
    char *buffer;
.)E
As stated above,
8kByte blocks in a relation are logically numbered from one.
The storage manager must locate the block of interest
and load its contents into
.CW buffer .
.sh 3 "smgr_write"
.pp
The routine
.(E
int
smgr_write(reln, blocknum, buffer)
    Relation reln;
    BlockNumber blocknum;
    char *buffer;
.)E
writes some representation of
.CW buffer
as block number
.CW blocknum
of the relation pointed to by
.CW reln .
This write may be asynchronous;
the device manager need not guarantee
that the buffer is flushed through to stable storage.
Synchronous writes are handled using the
.CW smgr_flush
routine,
described below.
As long as this routine
guarantees that the buffer has been copied somewhere safe
for eventual writing,
it may return successfully.
.pp
The buffer is an 8kByte \*(PG page in the format used
by the data manager.
It may be stored in any form,
but must be reconstructed exactly when the
.CW smgr_read
routine is called on it.
.sh 3 "smgr_flush"
.pp
This routine synchronously writes a block to stable storage.
The \*(PG data manager almost never needs to do synchronous writes
of single blocks.
In some cases,
however,
like the write of the transaction status file that marks a transaction
committed,
a single block must be written synchronously.
In this case,
the data manager calls the device manager's
.CW smgr_flush
routine.
The interface for this routine is
.(E
int
smgr_flush(reln, blocknum, buffer)
    Relation reln;
    BlockNumber blocknum;
    char *buffer;
.)E
The behavior of
.CW smgr_flush
is almost exactly the same as that of
.CW smgr_write ,
except that
.CW smgr_flush
must not return until
.CW buffer
is safely written to stable storage.
.sh 3 "smgr_blindwrt"
.pp
Under normal circumstances,
\*(PG moves dirty pages from memory to stable storage
by calling the
.CW smgr_write
routine for the appropriate storage manager.
In order to call
.CW smgr_write ,
the buffer manager must construct and pass a relation descriptor.
.pp
In certain cases,
\*(PG is unable to construct the relation descriptor
for a dirty buffer that must be evicted from the shared buffer cache.
This can happen,
for example,
when the relation descriptor has just been created in another process,
and has not yet been committed to the database.
In such a case,
\*(PG must write the buffer without constructing a relation descriptor.
.pp
The buffer manager can detect this case,
and handles it using a strategy called
.q "blind writes."
When a blind write must be done,
the buffer manager determines the name and object id of the database,
the name and object id of the relation,
and the block number of the buffer to be written.
All of this information is stored with the buffer in the buffer cache.
The device manager is responsible for determining,
from this information alone,
where the buffer must be written.
This means,
in general,
that every device manager must use some subset of these
values as a unique key for finding the proper location
to write a data block.
.pp
The interface for this routine is
.(E
int
smgr_blindwrt(dbname, relname, dbid, relid, blkno,
              buffer)
    Name dbname;
    Name relname;
    ObjectId dbid;
    ObjectId relid;
    BlockNumber blkno;
    char *buffer;
.)E
.pp
It is expected that most device managers will write data much
more efficiently using
.CW smgr_write
than
.CW smgr_blindwrt .
.sh 3 "smgr_nblocks"
.pp
The routine
.(E
int
smgr_nblocks(reln)
    Relation reln;
.)E
should return the number of blocks stored for the relation
pointed to by
.CW reln .
The number of blocks is used
during query planning and execution.
.pp
Since this is a potentially expensive operation,
the storage manager maintains a shared-memory cache of relation sizes
recently computed by device managers.
.sh 3 "smgr_commit"
.pp
When a transaction finishes,
the data manager calls the
.CW smgr_commit
routine for every device manager.
This routine must flush any pending asynchronous writes for this
transaction to disk,
so that all relation data is on persistent storage before
the transaction is marked committed.
In addition,
the device manager can release resources or update its state
appropriately.
.pp
This routine may be NULL,
if there is no work to do for a device manager at transaction commit.
If it is supplied,
its interface is
.(E
int
smgr_commit()
.)E
.pp
There is one important issue regarding transaction commit
that should also be mentioned.
Much research has been done in database systems to support
.i distribution ,
or databases that span multiple computers in a network.
Although \*(PG is not a distributed database system,
it does support
.i "data distribution"
by means of the storage manager switch
and device managers.
.pp
Data distribution means that different tables,
or parts of tables,
may reside on storage devices connected to different computers
on a network.
\*(PG does all data manipulation at a single site,
but the data it works with may be distributed.
The data manager will call the device manager,
which can operate on a local device,
or use the network to satisfy requests on a remote device.
In fact,
the Sony jukebox device manager works correctly whether it runs
on the host computer to which the jukebox is connected,
or on some other computer on the Internet.
.pp
At transaction commit time,
the data manager informs each device manager that all its
data must be on stable storage.
Each device manager flushes any pending writes synchronously,
and returns.
Once all device managers have forced data to stable storage,
the data manager synchronously records that the transaction
has committed by writing a ten-byte record to the
.i "transaction status file"
on one of the storage devices.
If the system crashes before the commit record is stored
in the transaction status file,
\*(PG will consider the transaction to be aborted when
the transaction's changes are encountered later.
.pp
Thus the
.CW smgr_commit
interface supports data distribution without
using a traditional multi-phase commit protocol ([KIM84], [SKEE81]).
In particular,
device managers are not notified whether a transaction actually
commits,
once they have forced data to stable storage.
.sh 3 "smgr_abort"
.pp
If a transaction aborts,
the data manager calls
.CW smgr_abort
in place of
.CW smgr_commit .
In this case,
it does not matter if changes made to user relations
during the aborted transaction are reflected on stable storage.
Device managers may deschedule pending writes,
as long as the writes include no data from other transactions.
.pp
This routine may be NULL,
if there is no work to do for a device manager at transaction abort.
.sh 3 "smgr_cost"
.pp
Query optimization requires cost estimates for different access paths
on relations [SELI79].
Since the cost function depends on the performance characteristics
of the device storing the relation,
each device manager must provide a cost estimator.
.pp
The interface is
.(E
int
smgr_cost(reln, nblocks, ntuples, costOutP)
    Relation reln;
    int nblocks;
    int ntuples;
    double *costOutP;
.)E
This function should compute an estimate of the cost of
instantiating
.CW nblocks
blocks
and
.CW ntuples
tuples from the relation pointed to by
.CW reln .
The
.CW costOutP
parameter is a pointer to a location for the returned cost.
An example cost function for a tertiary storage device is given
in section 4.
.sh 2 "Architecture Summary"
.pp
The new storage manager architecture
assigns a particular device manager to manage each device,
or class of devices,
available to the database system.
A well-defined set of interface routines makes relation accesses
device-transparent.
.pp
The new architecture uses a
.i "storage manager switch"
to record the interface routines for all the device managers
known to the system.
An earlier version of this architecture
stored these interface routines in a database relation,
and made the set of device managers dynamically extensible.
All existing device managers,
however,
use \*(PG shared memory and spinlocks.
Since existing device managers could not be developed outside
the \*(PG data manager,
the mechanism for doing so was eliminated.
.pp
So far,
three device managers exist.
The magnetic disk device manager is only 440 lines of C code,
including comments.
The main memory device manager is 600 lines,
most of which is a dynamically-extensible hashing package
to make block lookups fast.
The most complicated device manager by far \*-
the Sony optical disk write-once jukebox device manager \*-
is less than 3000 lines of code.
This complexity is largely due to the fast recovery and aggressive
sharing techniques used.
The design and implementation of the Sony jukebox device manager
are described in the next section.
.sh 1 "IMPLEMENTATION OF THE SONY JUKEBOX DEVICE MANAGER"
.pp
The tertiary storage device currently supported by \*(PG
is a jukebox of 50 double-sided write-once platters with
a total capacity of 327GByte.
A robotic arm moves platters between a bank of shelves and
two read/write decks.
The device is connected via a SCSI bus to a host computer.
A complete description of the hardware can be found in [SONY89a]
and [SONY89b].
.pp
\*(PG uses this device via a client/server protocol described in
section 4.1.
The Sony jukebox device manager caches optical disk blocks
on magnetic disk for faster access;
the cache management policy,
and some important issues in the cache design,
are described in section 4.2.
Section 4.3 describes the various shared-memory caches
used by the jukebox device manager.
Sections 4.4, 4.5, and 4.6 respectively discuss issues raised by the
write-once properties of the device,
how commits and aborts are handled,
and the cost function provided in
.CW sj_cost .
.sh 2 "POSTGRES Access to the Sony Jukebox"
.pp
The Sony jukebox must be physically connected to a host computer
over a SCSI bus.
This host computer
is not necessarily the computer on which users want to run \*(PG.
In order to make the device accessible from other computers,
a server on the host accepts requests to mount platters
and to read and write data over the network [MCFA91].
The network connection uses TCP/IP over BSD sockets [LEFF84].
.pp
The server manages a queue of requests from multiple clients,
so \*(PG is not necessarily the only user of the jukebox.
When requests on more than two platters appear in the request queue,
the server provides the illusion that all are mounted simultaneously
by moving platters among the two drives and shelves as necessary.
The request queue managed by the server is completely external to \*(PG,
so no information about the queue's length or contents can be used
when optimizing queries.
A future version of the jukebox server will make
queue status available to clients.
This will allow \*(PG to estimate query costs more accurately
than it does now
(see section 4.6 for more details),
and will result in better query optimization.
.pp
Figure 4 shows the jukebox server architecture.
In this figure,
there are three clients of the jukebox server;
\*(PG and two others.
.(z
.in +0.5i
.hl
... 0.24 7.51 4.99 10.26 0 0 4096 4096
... 0u 1584u 2736u 0u -137u 5910u 2359158u -2353385u
.PS 1584 2736 
.br
.ps 11
\h'1208u'\v'920u'\D'l-58u 15u'
.sp -1
\h'1208u'\v'949u'\D'l-58u -14u'
.sp -1
\h'1150u'\v'935u'\D'l720u 0u'
.sp -1
\h'1813u'\v'949u'\D'l57u -14u'
.sp -1
\h'1813u'\v'920u'\D'l57u 15u'
.sp -1
\h'2109u'\v'321u'\D'l49u -34u'
.sp -1
\h'2099u'\v'294u'\D'l59u -7u'
.sp -1
\h'2158u'\v'287u'\D'l-1151u 432u'
.sp -1
\h'1056u'\v'685u'\D'l-49u 34u'
.sp -1
\h'1066u'\v'712u'\D'l-59u 7u'
.sp -1
\h'1401u'\v'333u'\D'l37u -46u'
.sp -1
\h'1384u'\v'310u'\D'l54u -23u'
.sp -1
\h'1438u'\v'287u'\D'l-575u 432u'
.sp -1
\h'900u'\v'673u'\D'l-37u 46u'
.sp -1
\h'918u'\v'696u'\D'l-55u 23u'
.sp -1
\h'475u'\v'327u'\D'l-44u -40u'
.sp -1
\h'451u'\v'343u'\D'l-20u -56u'
.sp -1
\h'431u'\v'287u'\D'l288u 432u'
.sp -1
\h'675u'\v'679u'\D'l44u 40u'
.sp -1
\h'699u'\v'663u'\D'l20u 56u'
.sp -1
\h'432u'\v'1152u'\D'l0u -432u'
.sp -1
\h'432u'\v'720u'\D'l720u 0u'
.sp -1
\h'1152u'\v'720u'\D'l0u 432u'
.sp -1
\h'1152u'\v'1152u'\D'l-720u 0u'
.sp -1
\h'1941u'\v'933u'\D'l0u -69u'
.sp -1
\h'1941u'\v'864u'\D'l507u 0u'
.sp -1
\h'2448u'\v'864u'\D'l0u 69u'
.sp -1
\h'2448u'\v'933u'\D'l-507u 0u'
.sp -1
\h'2517u'\v'1077u'\D'l0u -219u'
.sp -1
\h'2517u'\v'858u'\D'l144u 0u'
.sp -1
\h'2661u'\v'858u'\D'l0u 219u'
.sp -1
\h'2661u'\v'1077u'\D'l-144u 0u'
.sp -1
\h'1942u'\v'1007u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1043u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1079u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1115u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1151u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1187u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1223u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1259u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1295u'\D'l504u 0u'
.sp -1
\h'1942u'\v'1331u'\D'l504u 0u'
.sp -1
\h'1872u'\v'288u'\D'l0u -144u'
.sp -1
\h'1872u'\v'144u'\D'l576u 0u'
.sp -1
\h'2448u'\v'144u'\D'l0u 144u'
.sp -1
\h'2448u'\v'288u'\D'l-576u 0u'
.sp -1
\h'1152u'\v'288u'\D'l0u -144u'
.sp -1
\h'1152u'\v'144u'\D'l576u 0u'
.sp -1
\h'1728u'\v'144u'\D'l0u 144u'
.sp -1
\h'1728u'\v'288u'\D'l-576u 0u'
.sp -1
\h'357u'\v'144u'\D'l0u 0u'
.sp -1
\h'357u'\v'144u'\D'l0u 0u'
.sp -1
\h'357u'\v'144u'\D'l0u 0u'
.sp -1
\h'357u'\v'144u'\D'l0u 0u'
.sp -1
\v'288u'\D'l0u -288u'
.sp -1
\D'l1008u 0u'
.sp -1
\h'1008u'\D'l0u 288u'
.sp -1
\h'1008u'\v'288u'\D'l-1008u 0u'
.sp -1
\h'1872u'\v'1584u'\D'l0u -864u'
.sp -1
\h'1872u'\v'720u'\D'l864u 0u'
.sp -1
\h'2736u'\v'720u'\D'l0u 864u'
.sp -1
\h'2736u'\v'1584u'\D'l-864u 0u'
.sp -1
\h'2627u'\v'212u'\h'-0.0m'\v'0.2m'\h'-\w'\s24\fR. . .\fP'u/2u'\s24\fR. . .\fP\h'-\w'\s24\fR. . .\fP'u/2u'
.sp -1
\h'503u'\v'161u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'\s11\fIPOSTGRES data manager\fP\h'-\w'\s11\fIPOSTGRES data manager\fP'u/2u'
.sp -1
\h'1438u'\v'233u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIclient\fP'u/2u'\s11\fIclient\fP\h'-\w'\s11\fIclient\fP'u/2u'
.sp -1
\h'2158u'\v'233u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIclient\fP'u/2u'\s11\fIclient\fP\h'-\w'\s11\fIclient\fP'u/2u'
.sp -1
\h'791u'\v'845u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIjukebox server\fP'u/2u'\s11\fIjukebox server\fP\h'-\w'\s11\fIjukebox server\fP'u/2u'
.sp -1
\h'791u'\v'989u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIprocess\fP'u/2u'\s11\fIprocess\fP\h'-\w'\s11\fIprocess\fP'u/2u'
.sp -1
\h'1510u'\v'1025u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRSCSI bus\fP'u/2u'\s11\fRSCSI bus\fP\h'-\w'\s11\fRSCSI bus\fP'u/2u'
.sp -1
\h'1798u'\v'485u'\h'-0.0m'\v'0.2m'\s11\fRTCP/IP connections over\fP
.sp -1
\h'1798u'\v'593u'\h'-0.0m'\v'0.2m'\s11\fRnetwork\fP
.sp -1
\h'2302u'\v'1421u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fISony optical disk\fP'u/2u'\s11\fISony optical disk\fP\h'-\w'\s11\fISony optical disk\fP'u/2u'
.sp -1
\h'2302u'\v'1529u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fIjukebox\fP'u/2u'\s11\fIjukebox\fP\h'-\w'\s11\fIjukebox\fP'u/2u'
.sp -1
.sp 1+1584u
.PE
.sp
.ce
Figure 4: Sony Jukebox Client/Server Process Architecture
.hl
.in -0.5i
.)z
These others are not clients of \*(PG;
they are processes that have their own data stored on optical
platters,
which they manage themselves.
Clients of the database system connect to \*(PG,
which manages relational data stored on platters for them.
.pp
The jukebox server uses platter names and ownership to provide
some data protection,
and to keep users other than \*(PG from reading or writing \*(PG platters.
\*(PG must be the only user of platters that it owns,
so that it can handle block allocation cleanly.
.sh 2 "Cache Design"
.pp
Transfers from the jukebox to the database system are
expensive to set up
and slow to execute.
This is because the device itself is slow,
and because there may be a network between the database system
and the storage device.
In order to mask some of the latency,
the Sony jukebox device manager caches blocks from optical disk
on magnetic disk.
This cache is used for both reads and writes;
writes are flushed to the Sony jukebox in LRU order
when dirty cache entries are reclaimed.
This section describes the cache's structure,
contents,
and replacement policy.
.sh 3 "Persistent Magnetic Disk Cache"
.pp
The magnetic disk cache of optical disk blocks is
.i persistent .
This means that its contents are valid across executions of \*(PG.
Logically,
data stored either in the cache or on an optical platter
is considered to be on the Sony jukebox.
This is distinct from write-through techniques;
writes to the magnetic disk cache must survive system crashes,
but need not be flushed immediately to an optical disk platter.
.pp
There were two motivations for this decision.
First,
a persistent cache means that the cache need not be populated
when a data manager starts up,
and simplifies issues of sharing,
since all instantiations of \*(PG use the same cache.
Cache population is extremely expensive,
since transfers from the jukebox are so slow.
If there is any locality of reference between executions
of the database system,
then the persistent cache should speed up queries that
use the jukebox.
.pp
The second motivation for persistence
is to allow \*(PG to delay
writes to the jukebox device
for as long as possible,
to avoid paying unnecessary transfer costs.
Data written to the jukebox device manager
first hits the magnetic disk cache.
If the cache is persistent,
then it need not be write-through.
Blocks may remain in the magnetic disk cache,
since they will be found by subsequent invocations of \*(PG.
.pp
Persistence introduces substantial complexity into cache management.
For reasons described in section 4.2.2,
user blocks are stored as contiguous chunks of data in the
magnetic disk cache,
and cache metadata is stored separately.
Since individual writes to the cache are very large,
atomicity of writes is a problem.
Since the metadata and the data it describes are stored separately,
the atomicity problem is exacerbated.
.pp
In general,
the problem is that the cache data and metadata must be written
out separately.
If one,
but not both,
of the writes completes before a system crash,
then the cache is in an inconsistent state.
This state must be detected and repaired before the
associated data is used.
.pp
To solve this problem,
the Sony jukebox device manager uses a
.i "link token"
technique like the one described in [SULL92].
The cache data and its associated metadata are tagged with a unique number,
which is generated by the \*(PG object id service.
Whenever a cache entry is used,
the metadata and data are checked to be sure that they match.
If not,
then the cache's internal locking scheme guarantees that the inconsistency
was caused by a crash, and the correct state must be recovered.
.pp
The recovery strategy is to throw away both the cache data and metadata
and reinstate it from the optical disk jukebox.
The order in which cache operations are performed
guarantees that any inconsistent data in the cache
is either present on the Sony jukebox,
or is new data from a transaction in progress when the
system crashed.
In either case,
the inconsistent cache data may be discarded.
If it is on the jukebox,
then it may be reinstated later.
If it was new data from a transaction in progress at the
time of a system crash,
then it is invalid and need not be recovered.
.pp
This cache management strategy supports fast recovery,
an important feature of \*(PG [STON87], [STON90].
Since cache inconsistencies are discovered and repaired on first use,
no special recovery code needs to run when \*(PG restarts
after a crash.
.sh 3 "Device Manager Block Allocation and Caching"
.pp
The Sony jukebox device manager allocates
space to relations in units of
.i extents .
The extent size is configurable when \*(PG is compiled.
The current implementation uses 32 8kByte blocks,
or 256kBytes of user data.
When a new block is requested for a relation
(via
.CW smgr_extend )
and there is no existing extent with free space,
a new extent is allocated for it.
Subsequent
.CW smgr_extend
calls consume subsequent blocks in the new extent.
.pp
Large extents were chosen for several reasons.
First,
they favor sequential access patterns by guaranteeing
contiguity of user data.
Second,
large extents favor large transfers,
and large transfers are more efficient than smaller ones.
This is due to the high cost of setting up a transfer
on the Sony optical disk jukebox.
Finally,
the device manager maintains an index to locate extents quickly.
A single index entry can point at an entire extent,
so large extents require fewer index entries than small ones,
saving space.
.pp
Whenever possible,
the Sony jukebox device manager attempts to locate multiple extents
for a single relation on the same side of the same platter.
If the platter is full,
the next choice is to locate new extents on a new platter.
The last choice is to put them on the reverse side of the same platter.
This is because reading from one side of a platter,
flipping it over,
and reading from the other side is more expensive
than reading from one side of two different platters.
Only one side of a single platter may be mounted at a time.
Since there are two read/write decks in the jukebox,
two separate platters can be mounted simultaneously.
.pp
The current implementation
moves user data between the Sony jukebox and the magnetic
disk cache in units of full extents.
The transfer size is configurable,
and can be any size less than or equal to a full extent.
Full extents favor locality of reference.
The next section describes the replacement policy for
cached extents,
and addresses some issues raised by the write-once nature of the jukebox.
.sh 3 "Replacement Policy for Cached Extents"
.pp
Extents stored in the magnetic disk cache are flushed
to the Sony jukebox in least-recently-used order.
When space in the cache is required for a new extent,
the oldest unused extent is evicted.
If the extent is dirty
(that is,
some block in it has been modified since the extent entered the cache),
it must be written to the Sony jukebox.
Clean extents may be evicted without being written.
.pp
The important complications in this scheme come about
because of the write-once nature of the Sony optical disk jukebox.
If only part of an extent has been allocated and written since it
appeared in the cache,
then only the parts that contain new data should be written to the jukebox.
The unused part of the extent must be left free on the jukebox
for use later.
This requires the device manager to do transfers in units
smaller than complete extents
under some circumstances.
.pp
A worse problem is that the magnetic disk cache
may not always contain the most recent version of an extent.
This situation can come about because the \*(PG buffer manager
has a cache of relation blocks in shared memory.
If some dirty blocks in the shared memory cache have
not been written to the magnetic disk cache,
then incorrect or incomplete blocks may be written to the jukebox.
Once written,
these blocks can never be replaced.
Thus the jukebox device manager must guarantee that it has the
latest copies of all the blocks in the extent before
it attempts to write them to the Sony jukebox.
.pp
These two problems have distinct solutions.
Writing partial extents to the jukebox is straightforward;
among the information stored in the magnetic disk cache metadata
is a map of the dirty pages in an extent,
so only those pages need to be written.
Partial writes are less efficient than full-extent writes,
but are only necessary if cached extents must be forced out
before they are filled.
In the long term,
extents should fill up with data,
so reads will eventually transfer whole extents.
.pp
Locating the latest version of every block in an extent
required a change to the \*(PG buffer manager.
A new interface routine was added to the code that maintains
the shared memory buffer cache.
.(E
int
DirtyBufferCopy(reln, blocknum, buf)
    Relation reln;
    BlockNumber blocknum;
    char *buf;
.)E
If block
.CW blocknum
of relation
.CW reln
appears in the buffer pool and is dirty,
then it is copied to
.CW buf ,
marked clean,
and
.CW DirtyBufferCopy
returns
.CW TRUE .
Otherwise,
.CW DirtyBufferCopy
just returns
.CW FALSE .
.pp
Just before writing a dirty segment to optical disk,
the Sony jukebox device manager calls
.CW DirtyBufferCopy
once for each buffer that appears in the extent.
This assembles the latest copy of the dirty extent.
This is guaranteed to behave correctly,
since the Sony jukebox device manager acquires an
exclusive lock on the extent beforehand.
The exclusive lock guarantees that no user can
update blocks that appear in the extent until
the lock is released.
.pp
One final issue in cache replacement is detecting and recovering
from crashes during flushes of dirty extents.
Consider the case in which a dirty extent is being
written to the Sony jukebox,
and the system crashes before the write completes.
In that case,
the cache data and metadata are still consistent,
but some of the blocks marked
.q dirty
in the cache already appear on the jukebox.
.pp
Because the jukebox obeys the write ordering specified by \*(PG,
this case is easy to detect and handle.
Just before writing a dirty extent,
the Sony jukebox storage manager attempts to read the first block
it will write.
If the read succeeds,
then part of the extent was successfully written before a crash.
The amount written can be determined by reading the extent from
the Sony jukebox,
and the remaining dirty blocks can be written safely.
Attempts to overwrite blocks on the Sony jukebox actually destroy
the data stored there,
so the jukebox device manager must be very careful about this.
.sh 2 "Use of Shared Memory"
.pp
The fact that the magnetic disk block cache is shared
by all \*(PG processes requires that the Sony jukebox device
manager coordinate cache operations with its peers.
Specifically,
only a single \*(PG process may update a particular cache
region at a time.
In addition,
cache metadata is stored in memory for efficiency.
Processes that want to examine cache metadata can do so
without accessing the magnetic disk version.
Only processes that change the metadata must force their
changes to disk.
.pp
To support sharing,
the Sony jukebox device manager uses the \*(PG shared memory
and semaphore abstractions.
Cache metadata is stored at a named location in shared memory,
and all concurrent processes can attach this region
to their address spaces.
Semaphores with well-known names exist to control exclusive
access to objects in shared memory.
The rest of this section describes what is stored in shared memory
and how access to it is controlled.
.pp
As mentioned in section 4.2,
the magnetic disk block cache is logically divided into
.i "user data"
and
.i metadata .
The user data portion consists of a control block
followed by a sequence of data blocks.
The control block stores the name and object identifier
of the relation owning the data blocks,
the link token described in the previous section,
and some extra administrative information.
The metadata identifies dirty data and unallocated data blocks
and stores the link token,
among other information.
The
.i extent
allocated by the jukebox storage manager is the
user data portion,
including the control block.
This entire extent is read from and written to the jukebox.
The metadata is never stored on the jukebox.
It is maintained only on magnetic disk,
and is recreated from the control block when an extent
moves from an optical disk platter into the magnetic disk cache.
.pp
Both the metadata and the user data portions of the cache
are persistent,
as defined in section 4.2.1.
When the first \*(PG process starts up after a crash,
the Sony jukebox device manager
detects the fact that its shared memory is not yet initialized
and loads the cache metadata into shared memory.
This requires an exclusive lock on the cache metadata for the
duration of the load.
Such a lock is acquired using the \*(PG semaphore abstraction.
As the metadata is loaded,
a hash table is constructed in shared memory to make lookups
of particular extents (by relation, database, and block numbers) fast.
This initialization takes on the order of fifty milliseconds
on a DECstation 3100 running Ultrix 4.2.
.pp
Once the metadata is loaded into shared memory
and the hash table is initialized,
the exclusive lock is released.
This is the only case in which an exclusive lock is held
on a shared data structure during a disk access.
.pp
When a \*(PG process wants access to a particular cached extent,
it takes the following steps:
.np
It acquires an exclusive lock on the hash table
and looks up the extent.
The exclusive lock keeps concurrent processes from changing
the hash table during lookup.
This lock need not exclude other readers,
but does so (for the sake of simplicity)
in the current implementation.
For the purposes of this discussion,
assume that the extent is present in the cache.
.np
It releases the exclusive lock on the hash table.
.np
It acquires an exclusive lock on the particular extent.
Every cache entry has an associated semaphore that controls access to it.
Since semaphores are a scarce resource,
the \*(PG shared lock table could be used instead.
.np
It verifies that the extent is the one desired.
The extent may have changed,
for example,
if some concurrent process evicted the extent and replaced it with another
before the exclusive lock on the extent was acquired.
Another possibility is that the cache is inconsistent due to a crash.
It is possible to detect and recover from this case
as described in section 4.2.1.
.np
\*(PG then sets the
.CW IO_INPROGRESS
flag on the extent's metadata
and releases the exclusive lock.
Concurrent processes will notice that the
.CW IO_INPROGRESS
flag is set and defer their accesses until it is cleared.
Sleeping and wakeup are coordinated using spinlocks or semaphores,
depending on operating system support.
.np
Finally,
it releases the exclusive lock on the extent.
.pp
At this point,
the extent may be read or written freely.
.pp
If the extent sought does not yet appear in the cache,
\*(PG must evict an existing extent and load the one desired.
The process for doing so is similar to that for reading an extent,
except that there is a second round of locking to update the cache
metadata and the shared hash table.
In addition,
the code is careful to detect and handle race conditions,
such as the case where two concurrent processes instantiate the same
extent in the cache at the same time.
.pp
The cache management and locking protocol are loosely based on that
used by the \*(PG buffer manager.
The implementation holds exclusive locks on objects for as short a
period as possible,
and never holds an exclusive lock during an I/O
(except during initialization after a crash,
as described above).
In addition,
it guarantees that different processes can update different parts of
the cache simultaneously.
.pp
The complexity involved in managing the cache for such aggressive
sharing is substantial.
This,
along with cache persistence,
are the primary reasons that the Sony jukebox device manager requires
3000 lines of code.
.sh 2 "Managing Write-Once Media"
.pp
Another source of complexity in the Sony jukebox device manager
is the fact that the optical platters are write-once.
Although [STON87] claims that the \*(PG storage manager
is no-overwrite,
it would be more correct to call it
.q seldom-overwrite. \|
There are circumstances in which tuples or blocks
are overwritten in place,
and these cases cause problems for the Sony jukebox storage manager.
.pp
One such case is when a tuple is deleted or replaced.
The no-overwrite storage manager in \*(PG reserves some space
in the tuple to mark it with the
transaction ID of the updating transaction.
Marking a tuple constitutes an overwrite-in-place of the existing tuple,
and cannot be supported by the Sony jukebox device manager.
.pp
Another case requiring overwrite is when the \*(PG vacuum cleaner runs.
This process fills in the commit times of transactions affecting
tuples.
Commit times are recorded in fields in the tuples themselves,
and so this also constitutes overwrite-in-place.
Furthermore,
the vacuum cleaner assumes that it can physically remove
expired tuples from data pages.
This is not true for write-once media.
.pp
The present implementation of the Sony jukebox device manager
fails to solve either problem.
It detects attempts to overwrite existing pages,
and returns a failure error code to the caller.
This means that relations stored on the Sony jukebox cannot be vacuumed,
and that tuples stored on the jukebox can never be deleted.
Since vacuuming is only a performance optimization,
failure to support it does not lead to incorrect behavior.
The fact that jukebox tuples are permanent is a more serious flaw.
Essentially,
this makes physical device characteristics visible to the user.
The design goal of the storage manager switch was to make
relations location-transparent,
and this property violates location transparency.
.pp
A possible solution would be to change the representation of pages
stored inside the Sony jukebox device manager.
The pages would be separated into overwritable parts
(updating transaction ID and transaction commit times for tuples
on the page),
which would be stored on magnetic disk,
and non-overwritable parts
(the tuple data),
which would be stored on the jukebox.
The overwritable parts of a tuple consume thirteen bytes of storage,
so this strategy will increase the amount of magnetic disk space required.
Under this scheme,
conventional \*(PG data pages could be reassembled
by the Sony jukebox device manager on demand.
.pp
Another problem raised by write-once storage devices is the
fact that data blocks in \*(PG relations do get overwritten
in place.
For example,
a data block is overwritten every time a new tuple is added to it.
As above,
this causes problems for the Sony jukebox device manager.
.pp
In this case,
the solution is straightforward.
The current version of \*(PG does not cluster data in relations,
so all insertions to heap relations happen on the relation's
highest-numbered block.
The Sony jukebox device manager stores the last block of every
relation it manages on magnetic disk.
When a new block is allocated,
the old last block is moved to the optical disk jukebox,
and the new one replaces it on magnetic disk.
Note that the Sony jukebox device manager does not
use the magnetic disk device manager for this;
it operates on the magnetic disk directly.
.pp
The current system flags write-once device managers
in the storage manager switch,
and the data manager is careful not to vacuum relations stored on these.
In addition,
since indexed access methods generally require block overwrite-in-place
at random locations in the relation,
these cannot be located on write-once device managers.
The correct solution is to support logical overwrite-in-place
on write-once device managers
by writing software to handle overwrites-in-place,
but this has not yet been done in the Sony jukebox device manager.
.sh 2 "Commit and Abort Processing"
.pp
When a transaction commits or aborts,
the data manager calls the
.CW smgr_commit
or
.CW smgr_abort
interface routines to guarantee that all data managed by all
device managers is on stable storage.
.pp
Writes to the physical jukebox device are synchronous and unbuffered,
so no special processing needs to be done for them.
Writes to magnetic disk may be captured by the file system buffer cache,
and must be forced through at transaction commit.
In addition,
the Sony jukebox device manager must flush changes to stable storage
even in case of a transaction abort.
This is because the device manager may write a page to disk
on behalf of some other transaction.
For example,
a page in the buffer cache may be dirtied by one transaction,
and written by a device manager in another transaction
which evicts the page from the cache.
.pp
To guarantee that all changes are on stable storage,
the Sony jukebox device manager keeps track of all magnetic disk
file descriptors on which it has done writes.
At transaction commit or abort,
the jukebox device manager issues an
.CW fsync
system call on each of these file descriptors.
This forces all pending writes to disk.
On completion,
the device manager returns successfully.
.sh 2 "Query Cost Estimation"
.pp
The \*(PG optimizer is based on the design proposed by [SELI79]
and is described in detail in [FONG86].
To support multiple devices,
the query optimizer must call the
.CW smgr_cost
function for the device managers that manage relations under consideration.
The optimizer uses selectivity functions
defined by the access methods to estimate the number
of blocks and number of tuples in the relation that
the query plan will touch.
These values are passed to
.CW smgr_cost .
This section describes the cost estimation function provided by
the Sony jukebox device manager.
.pp
[SELI79] proposes a cost estimation function
.EQ
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.ps 11
.ft 2
.ds 11 "cost
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(eq
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "W
.ds 13 "\f11\fP
.as 12 \v'20u'\s-3\|\*(13\s+3\v'-20u'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "\v'-.3m'.\v'.3m'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "nblocks
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(pl
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "W
.ds 13 "\f12\fP
.as 12 \v'20u'\s-3\|\*(13\s+3\v'-20u'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "\v'-.3m'.\v'.3m'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "ntuples
.as 11 "\*(12
.ds 11 \x'0'\f2\s11\*(11\|\s\n(99\f(\n(98\x'3u'
.nr 11 \w'\*(11'
.nr MK 0
.if 108>\n(.v .ne 108u
.rn 11 10
\*(10
.ps \n(99
.ft \n(98
.EN
.sp 0.3v
to estimate the cost of a particular access path to a relation.
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f11\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " is a coefficient that
.ps \n(99
.ft \n(98
\*(12
approximates the cost of instantiating a block from the storage device,
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.as 12 "and 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f12\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " is a coefficient that approximates the CPU cost of processing
.ps \n(99
.ft \n(98
\*(12
a single tuple.
These coefficients are set empirically.
.pp
The Sony jukebox storage manager adds a term to this equation.
It uses
.EQ
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.ps 11
.ft 2
.ds 11 "cost
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(eq
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "W
.ds 13 "\f10\fP
.as 12 \v'20u'\s-3\|\*(13\s+3\v'-20u'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "\v'-.3m'.\v'.3m'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "npswitches
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(pl
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "W
.ds 13 "\f11\fP
.as 12 \v'20u'\s-3\|\*(13\s+3\v'-20u'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "\v'-.3m'.\v'.3m'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "nblocks
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(pl
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "W
.ds 13 "\f12\fP
.as 12 \v'20u'\s-3\|\*(13\s+3\v'-20u'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "\v'-.3m'.\v'.3m'
.as 11 "\*(12
.ds 12 "\|
.as 11 "\*(12
.ds 12 "ntuples
.as 11 "\*(12
.ds 11 \x'0'\f2\s11\*(11\|\s\n(99\f(\n(98\x'3u'
.nr 11 \w'\*(11'
.nr MK 0
.if 108>\n(.v .ne 108u
.rn 11 10
\*(10
.ps \n(99
.ft \n(98
.EN
.sp 0.3v
The new term estimates the cost of platter switches
associated with the access path under consideration.
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f10\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " approximates the cost of a single platter switch,
.ps \n(99
.ft \n(98
\*(12
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.as 12 "and 
.ps 11
.ft 2
.ds 13 "npswitches
.ds 13 \x'0'\f2\s11\*(13\|\s\n(99\f(\n(98
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " estimates the number of platter switches
.ps \n(99
.ft \n(98
\*(12
required.
.pp
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f10\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " is set empirically.
.ps \n(99
.ft \n(98
\*(12
A platter switch on the Sony jukebox takes,
on the average,
6.7 seconds.
This is roughly the amount of time it takes to read 5MByte,
or 625 8kByte data pages,
from an optical platter.
Thus
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f10\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 14 "\ 
.as 13 "\*(14
.ds 14 "\(eq
.as 13 "\*(14
.ds 14 "\ 
.as 13 "\*(14
.ds 14 "\f16\fP\f12\fP\f15\fP
.as 13 "\*(14
.ds 14 "W
.ds 15 "\f11\fP
.as 14 \v'20u'\s-3\|\*(15\s+3\v'-20u'
.as 13 "\*(14
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 ".
.ps \n(99
.ft \n(98
\*(12
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "W
.ds 14 "\f11\fP
.as 13 \v'20u'\s-3\|\*(14\s+3\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 ",
.ps \n(99
.ft \n(98
\*(12
in turn,
is set empirically to 40 times the cost of instantiating a
magnetic disk block.
In general,
device managers in \*(PG normalize their cost function coefficients
to the values used by the magnetic disk device manager.
.pp
The number of platter switches,
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "npswitches
.ds 13 \x'0'\f2\s11\*(13\|\s\n(99\f(\n(98
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 ",
.ps \n(99
.ft \n(98
\*(12
is estimated in the following way.
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.as 12 "Let 
.ps 11
.ft 2
.ds 13 "nblocks
.ds 14 "r
.as 13 \v'20u'\s-3\*(14\s+3\|\v'-20u'
.ds 13 \x'0'\f2\s11\*(13\s\n(99\f(\n(98\x'3u'
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " be the total number of blocks stored in
.ps \n(99
.ft \n(98
\*(12
the relation under consideration.
Then the probability that any particular platter must be loaded
is assumed to be
.EQ
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.ps 11
.ft 2
.ds 11 "nblocks
.ds 12 "nblocks
.ds 13 "r
.as 12 \v'20u'\s-3\*(13\s+3\|\v'-20u'
.nr 11 \w'\s11\*(11'
.nr 12 \w'\s11\*(12'
.nr 13 \n(11
.if \n(12>\n(13 .nr 13 \n(12
.nr 13 \n(13+\s11.5m\s0
.ds 11 \v'62u'\h'\n(13u-\n(12u/2u'\*(12\
\h'-\n(12u-\n(11u/2u'\v'-114u'\*(11\
\h'-\n(13u-\n(11u/2u+.1m'\v'26u'\l'\n(13u-.2m'\h'.1m'\v'26u'
.ds 11 \x'0'\x'0-35u'\f2\s11\*(11\s\n(99\f(\n(98\x'65u'
.nr 11 \w'\*(11'
.nr MK 0
.if 222>\n(.v .ne 222u
.rn 11 10
\*(10
.ps \n(99
.ft \n(98
.EN
.sp 0.3v
where
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "nblocks
.ds 13 \x'0'\f2\s11\*(13\|\s\n(99\f(\n(98
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 " is the parameter passed in by the query optimizer.
.ps \n(99
.ft \n(98
\*(12
This assumes that the probability of touching a given block is
uniform over all platters storing data for the relation;
that is,
that every platter storing data for the relation
has an equal chance of being loaded to satisfy the query.
In general,
this is an invalid assumption,
since it ignores the number of blocks stored on a given platter,
but it simplifies cost estimation substantially.
.pp
The number of platters storing data for the relation,
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.rm 12 
.ps 11
.ft 2
.ds 13 "nplatters
.ds 13 \x'0'\f2\s11\*(13\|\s\n(99\f(\n(98
.as 12 \*(13
.ps \n(99
.ft \n(98
.as 12 ",
.ps \n(99
.ft \n(98
\*(12
is computed by examining the system catalogs.
Then the number of platter switches is computed as
.EQ
.nr 99 \n(.s
.nr 98 \n(.f
.af 98 01
.ps 11
.ft 2
.ds 11 "npswitches
.ds 12 "\ 
.as 11 "\|\*(12
.ds 12 "\(eq
.as 11 "\*(12
.ds 12 "\ 
.as 11 "\*(12
.ds 12 "\f1max\fP
.as 11 "\*(12
.ds 12 "\|
.ds 13 "\f11\fP
.ds 14 "\|
.as 13 "\*(14
.ds 14 "\f1,\fP
.as 13 "\*(14
.ds 14 "\|
.as 13 "\*(14
.ds 14 "nblocks
.ds 15 "nblocks
.ds 16 "r
.as 15 \v'20u'\s-3\*(16\s+3\|\v'-20u'
.nr 14 \w'\s11\*(14'
.nr 15 \w'\s11\*(15'
.nr 16 \n(14
.if \n(15>\n(16 .nr 16 \n(15
.nr 16 \n(16+\s11.5m\s0
.ds 14 \v'62u'\h'\n(16u-\n(15u/2u'\*(15\
\h'-\n(15u-\n(14u/2u'\v'-114u'\*(14\
\h'-\n(16u-\n(14u/2u+.1m'\v'26u'\l'\n(16u-.2m'\h'.1m'\v'26u'
.as 13 "\*(14
.ds 14 "\v'-.3m'.\v'.3m'
.as 13 "\*(14
.ds 14 "nplatters
.as 13 "\*(14
.as 12 "\*(13
.ds 13 "\|
.as 12 "\|\*(13
.ds 12 \|\v'0u'\b'\(lt\(bv\(lb'\v'0u'\*(12\|\v'0u'\b'\(rt\(bv\(rb'\v'0u'
.as 11 "\*(12
.ds 11 \x'0'\x'0-56u'\f2\s11\*(11\s\n(99\f(\n(98\x'86u'
.nr 11 \w'\*(11'
.nr MK 0
.if 264>\n(.v .ne 264u
.rn 11 10
\*(10
.ps \n(99
.ft \n(98
.EN
.sp 0.3v
This formula assumes that at least one platter must be mounted
in order to satisfy a query.
.pp
The cost function described in this section favors access plans
that touch fewer blocks of relations on the Sony jukebox.
This cost function provides only a rough estimate query's actual cost.
The contents of the magnetic disk cache are ignored,
and no attempt is made to determine whether a desired
platter is already mounted in the jukebox.
In addition,
the actual distribution of data pages across platters is
not considered.
Section 8 suggests some improvements to the existing cost function.
.sh 2 "Summary of Sony Jukebox Device Manager Implementation"
.pp
This section has described the design of the Sony optical disk
jukebox device manager.
The most important features of this device manager
are the magnetic disk cache of recently-used optical disk blocks
and the write-once nature of the recording medium.
These two features make the device manager more complex
than the magnetic disk or main memory device managers.
.pp
The Sony jukebox device manager demonstrates that the
storage manager switch abstraction was successful.
New storage devices may be integrated into \*(PG
by a sophisticated programmer with knowledge of
the database system's internals.
.pp
The next section introduces the Inversion file system,
which was implemented on top of \*(PG and takes advantage
of the storage manager switch to provide a file system
on any device supported by \*(PG.
.sh 1 "DESIGN OF THE INVERSION FILE SYSTEM"
.pp
Conventional database systems are generally built on top of file
systems [STON92].
This section describes the design and implementation of a file system
built on top of the database system.
This file system,
called
.q Inversion
because the conventional roles of the file system
and database system are inverted,
runs under \*(PG version 4.0.
It supports file storage on any device managed by \*(PG,
and provides useful services not found in many conventional file systems.
.pp
Current file systems researchers are concentrating on providing
new services to administrators and users.
For example,
Episode [CHUT92] embeds transaction protection in the file system directly.
However,
transactions protect only file system metadata,
to speed recovery after crashes,
and are not available to users.
[SELT90] proposes embedding user-level transaction support
directly in existing file systems,
and QuickSilver [CABR88] is an early example of such a system.
Other researchers are investigating support for time travel.
For example,
Plan 9 [PIKE90] and 3DFS [ROOM92]
allow the user to see past states of the file system.
However,
most such systems provide coarse temporal granularity.
Both Plan 9 and 3DFS take periodic snapshots of the file system,
and states that existed between snapshots are not recoverable.
.pp
The Inversion file system provides transactions and fine-grained
time travel to users by taking advantage of the
\*(PG no-overwrite storage manager.
File data is stored in the database,
so that file updates are transaction-protected.
In addition,
the user may ask to see the state of the file system at
any time in the past.
All transactions that had committed as of that time will
be visible,
so the file system state will be exactly the same as it was at that moment.
This is an important improvement on the coarse-grained time travel
provided by other systems.
.pp
Another feature provided by Inversion is fast recovery.
No file system consistency checker needs to run on the Inversion file
system after a crash,
since recovery is managed by the \*(PG storage manager.
File system recovery is essentially instantaneous.
Any updates that were in progress at the time of the crash,
but had not committed,
will be rolled back.
Any committed updates are guaranteed to be persistent across crashes.
LFS [ROSE91] uses a log to provide similar guarantees about
recovery time,
but does not support transactions.
.pp
In addition,
files in the Inversion file system may be located on any
device manager in \*(PG.
This means that the Inversion file system can span multiple
devices (and device types) transparently.
.pp
A less conventional,
but nonetheless important,
feature of Inversion is that files are strongly typed.
Since \*(PG supports the dynamic loading of user code for
execution in the data manager,
this means that users can arrange for their applications to run
in the file system manager itself,
rather than in a separate address space.
By exploiting typing,
operations may be defined that can be applied
to certain groups of files.
For example,
object files can be treated differently from text files.
Locus [WALK83] supports typed files,
but the set of file types is small and difficult to extend.
.pp
Finally,
the fact that Inversion is built on top of \*(PG
makes it possible to issue
.i "ad hoc"
queries on the file system metadata,
or even file data itself.
Instead of mastering the use of many different programs,
the user may examine the file systems structure and contents
by formulating simple \*(PQ queries.
In addition,
indices may be defined to make selected queries run faster,
at the user's discretion.
.pp
.i "Ad hoc"
queries are especially powerful because they support
attribute-based naming of files [SECH91].
For example,
in Inversion,
it is possible to store revision control information
about a file in a relation.
The user can then formulate queries on the database
to find files based on revision control information.
Since arbitrary schemas are permitted,
any attribute of interest may be stored in the database
and used to look up files.
.pp
In summary,
the Inversion file system provides services not available
in conventional file systems,
including
.BU
transaction-protected file updates,
.BU
fine-grained time travel,
.BU
device independence,
.BU
strong typing of files,
and
.BU
.i "ad hoc"
queries on the file system state.
.pp
The rest of this section describes the design and implementation
of Inversion.
.(z
.in +0.5i
.hl
... 0 -1.2 5.25 0.1 0 0 4096 4096
... 0u 749u 3023u 0u 0u 58u 2358516u -2358458u
.PS 749 3023 
.br
\v'58u'\h'-0.0m'\v'0.2m'\h'-\w'\s11'u/2u'\s11\h'-\w'\s11'u/2u'
.sp -1
\h'173u'\v'58u'\h'-0.0m'\v'0.2m'\h'-\w'filename'u/2u'filename\h'-\w'filename'u/2u'
.sp -1
\v'115u'\D'l0u -115u'
.sp -1
\D'l345u 0u'
.sp -1
\h'345u'\D'l0u 115u'
.sp -1
\h'345u'\v'115u'\D'l-345u 0u'
.sp -1
\h'561u'\v'173u'\h'-0.0m'\v'0.2m'\h'-\w'0'u/2u'0\h'-\w'0'u/2u'
.sp -1
\h'345u'\v'230u'\D'l0u -115u'
.sp -1
\h'345u'\v'115u'\D'l432u 0u'
.sp -1
\h'777u'\v'115u'\D'l0u 115u'
.sp -1
\h'777u'\v'230u'\D'l-432u 0u'
.sp -1
\h'561u'\v'58u'\h'-0.0m'\v'0.2m'\h'-\w'\fIchunkno\fP'u/2u'\fIchunkno\fP\h'-\w'\fIchunkno\fP'u/2u'
.sp -1
\h'561u'\v'288u'\h'-0.0m'\v'0.2m'\h'-\w'1'u/2u'1\h'-\w'1'u/2u'
.sp -1
\h'345u'\v'345u'\D'l0u -115u'
.sp -1
\h'345u'\v'230u'\D'l432u 0u'
.sp -1
\h'777u'\v'230u'\D'l0u 115u'
.sp -1
\h'777u'\v'345u'\D'l-432u 0u'
.sp -1
\h'561u'\v'403u'\h'-0.0m'\v'0.2m'\h'-\w'2'u/2u'2\h'-\w'2'u/2u'
.sp -1
\h'345u'\v'461u'\D'l0u -116u'
.sp -1
\h'345u'\v'345u'\D'l432u 0u'
.sp -1
\h'777u'\v'345u'\D'l0u 116u'
.sp -1
\h'777u'\v'461u'\D'l-432u 0u'
.sp -1
\h'777u'\v'230u'\D'l0u -115u'
.sp -1
\h'777u'\v'115u'\D'l1152u 0u'
.sp -1
\h'1929u'\v'115u'\D'l0u 115u'
.sp -1
\h'1929u'\v'230u'\D'l-1152u 0u'
.sp -1
\h'1353u'\v'58u'\h'-0.0m'\v'0.2m'\h'-\w'\fIchunk\fP'u/2u'\fIchunk\fP\h'-\w'\fIchunk\fP'u/2u'
.sp -1
\h'777u'\v'345u'\D'l0u -115u'
.sp -1
\h'777u'\v'230u'\D'l1152u 0u'
.sp -1
\h'1929u'\v'230u'\D'l0u 115u'
.sp -1
\h'1929u'\v'345u'\D'l-1152u 0u'
.sp -1
\h'777u'\v'461u'\D'l0u -116u'
.sp -1
\h'777u'\v'345u'\D'l1152u 0u'
.sp -1
\h'1929u'\v'345u'\D'l0u 116u'
.sp -1
\h'1929u'\v'461u'\D'l-1152u 0u'
.sp -1
\h'345u'\v'461u'\D'l0u 288u'
.sp -1
\h'345u'\v'749u'\D'l1584u 0u'
.sp -1
\h'1929u'\v'749u'\D'l0u -288u'
.sp -1
\h'1281u'\v'489u'\h'-0.0m'\v'0.2m'\h'-\w'.'u/2u'.\h'-\w'.'u/2u'
.sp -1
\h'1281u'\v'547u'\h'-0.0m'\v'0.2m'\h'-\w'.'u/2u'.\h'-\w'.'u/2u'
.sp -1
\h'1281u'\v'605u'\h'-0.0m'\v'0.2m'\h'-\w'.'u/2u'.\h'-\w'.'u/2u'
.sp -1
\h'2678u'\v'58u'\h'-0.0m'\v'0.2m'\h'-\w'\s-2POSTGRES\s0 tuples'u/2u'\s-2POSTGRES\s0 tuples\h'-\w'\s-2POSTGRES\s0 tuples'u/2u'
.sp -1
\h'2332u'\v'58u'\D'l-403u 115u'
.sp -1
\h'1980u'\v'143u'\D'l-51u 30u'
.sp -1
\h'1988u'\v'171u'\D'l-59u 2u'
.sp -1
\h'2332u'\v'58u'\D'l-403u 230u'
.sp -1
\h'1972u'\v'247u'\D'l-43u 41u'
.sp -1
\h'1986u'\v'272u'\D'l-57u 16u'
.sp -1
\h'2332u'\v'58u'\D'l-403u 345u'
.sp -1
\h'1963u'\v'355u'\D'l-34u 48u'
.sp -1
\h'1982u'\v'377u'\D'l-53u 26u'
.sp -1
.sp 1+749u
.PE
.ce
Figure 5: Decomposition of files into relations in Inversion
.hl
.in -0.5i
.)z
.sh 2 "Decomposing Files into Relations"
.pp
Files,
generally viewed by users as byte streams,
are stored in conventional file systems
as a series of data blocks.
The Inversion file system similarly
.q chunks
user data.
Figure 5 shows the schema used to store file data
in \*(PG relations.
.pp
For every file,
a uniquely-named relation is created.
File data is collected into chunks slightly smaller than 8kBytes.
The size of the chunk is calculated so that a single
tuple will fit exactly on a \*(PG data manager page.
This page size was chosen early in the design of \*(PG,
and was intended to make magnetic disk transfers fast.
Although Inversion does not require magnetic disk in order
to function,
the page size inherited from the data manager survives.
.pp
When a user writes a new data chunk to a file,
a tuple is created consisting of the
.i "chunk number" ,
or index of this chunk into the file,
and the data chunk.
This tuple is appended to the relation storing the file.
.pp
The Inversion file system provides a set of interface routines
to create, open, close, read, write, and seek on files.
Byte-oriented operations are turned into operations on chunks
by calculating the chunk numbers of the affected chunks.
In order to be compatible with existing \*(UX filesystems,
Inversion uses longwords to communicate a file's current read
or write position.
This limits Inversion files to 2GBytes in size.
This constraint is easy to remove,
at the cost of compatibility with existing file systems.
.pp
A file is located on particular device manager at creation.
From that point on,
accesses are device-transparent,
both to the user and to the Inversion file system itself.
The underlying device manager is called to instantiate blocks
of the relation storing the file.
Inversion does not know anything about devices.
.pp
When a file is modified,
the tuples storing changed chunks are replaced
in the normal way.
In order to speed up seeks on files,
Inversion maintains a Btree index on the chunk number attribute.
.sh 2 "Namespace and Metadata Management"
.pp
Inversion stores the file system namespace in a class
.(E
pg_largeobject(poid, fname)
.)E
where
.CW poid
is the
.CW pg_largeobject
object identifier of the parent directory,
and
.CW fname
is the file name.
The
object identifier associated with
the
.CW pg_largeobject
tuple for the file is its filesystem-wide unique identifier.
.pp
The names of the relations containing file data are computed
from the file's
.CW pg_largeobject
object identifier.
If the object identifier is 12345,
then the relation containing the file data is
.CW inv12345 ,
and the block number index on the relation is called
.CW inx12345 .
.pp
In addition to namespace management,
most file systems manage other metadata associated with a file.
For example,
the file's owner,
size,
and last access,
modification,
and creation times are typically stored by the file system.
Inversion also maintains this data for all files.
The owner and creation time for a file may be determined
by examining the
.CW pg_class
tuple for the relation in which the file is stored.
.pp
In the current version of \*(PG,
relations are append-at-end only,
so frequently changing data consumes space quickly.
Since file sizes,
last access times,
and last modification times typically change frequently,
Inversion does not store them in a relation,
in order to conserve space.
Instead,
these attributes are stored in a hash table on magnetic disk,
and updated in place.
Once \*(PG can cluster data in relations and reuse free space
on data pages,
these items should be stored in a relation.
.sh 2 "File System Management Issues"
.pp
Two important issues in file system management
are the policy for caching filesystem blocks for fast access
and the policy for laying files out on storage devices.
The current implementation of Inversion does not address
either of these issues.
.pp
\*(PG supports a multi-level cache,
since the buffer manager caches buffers in shared memory
and device managers
(like the Sony jukebox device manager)
can implement caches for their own use.
These caches may be distributed among different storage technologies.
For example,
the Sony jukebox device manager maintains its cache of recently-used
extents on magnetic disk.
The \*(PG shared buffer cache resides in main memory.
This separation of cache location solves a commonly-cited
problem of multi-level caches.
Since the caches are on different devices,
they do not compete for resources.
.pp
Despite the fact that device managers can provide custom caching,
there is no special cache of file system data blocks
maintained by Inversion.
Inversion is built entirely above the storage manager switch
layer,
and so has no knowledge of a file's location.
It would have been possible to create an in-memory cache of file
system blocks,
but this is precisely the service already supplied by the
\*(PG shared buffer cache.
.pp
Since Inversion does not control file location,
it cannot control placement of file blocks on storage media.
Device managers enforce policies for block layout
in the current implementation.
At some point,
\*(PG implementors will have to move this policy
higher in the system,
since support for data clustering in relations
requires that the data manager make decisions on block layout.
In either case,
no support currently exists for enforcement of a layout policy
in the Inversion file system code.
.sh 1 "PERFORMANCE OF THE INVERSION FILE SYSTEM"
.pp
This section presents measurements of the performance
of the Inversion file system.
Inversion is intended to support physical scientists
working on the Sequoia 2000 project [STON91], [KATZ91].
In general,
these scientists will use Inversion as a network file server.
The system configuration evaluated here is the same
as will be used by Sequoia researchers.
Inversion is compared to NFS [SAND85] running on identical
hardware.
.sh 2 "System Configuration"
.pp
Inversion was installed on a DECstation 5900 with 128MBytes of main memory.
The operating system running on the machine was Ultrix 4.2.
Files were located on a 1.3GByte DEC RZ58 disk drive attached
to the DECsystem 5900.
.pp
Files were opened, read, and written from a remote client
running on a DECstation 3100 under Ultrix 4.2.
Client/server communication was via TCP/IP over a 10Mbit/sec Ethernet.
.pp
Inversion was compared to the Ultrix 4.2 implementation of NFS.
The NFS server was run on the same DECsystem 5900,
using the same disk,
as Inversion.
The NFS client was the same DECstation 3100.
.pp
The NFS implementation on the DECsystem 5900 used a service
called PRESTOserve to speed up writes.
To guarantee that NFS servers remain stateless,
NFS must force every write to stable storage synchronously [SAND85].
PRESTOserve consists of a board containing 1MByte of battery-backed
RAM and driver software to cache NFS writes in non-volatile memory.
As will be seen below,
this substantially improved the write throughput of NFS under Ultrix.
This non-volatile memory was not used by Inversion.
.sh 2 "The Benchmark"
.pp
The benchmark consisted of the following operations:
.BU
Create a 25MByte file.
.BU
Measure the latency to read or write a single byte
at a random location in the file.
.BU
Read 1MByte in a single large transfer.
.BU
Read 1MByte sequentially in page-sized units.
The page size was chosen to be efficient for the file system under test.
.BU
Read 1MByte in page-sized units distributed
at random throughout the file.
.BU
Repeat the 1MByte transfer tests,
writing instead of reading.
.pp
All caches were flushed before each test.
These tests measure worst-case throughput
for operations that Sequoia researchers are likely to carry out.
.(z
.in +0.5i
.hl
... 0.925 7.668 5.737 10.262 0 0 4096 4096
... 0u 1494u 2771u 0u -532u 5909u 2358157u -2352779u
.PS 1494 2771 
.br
.ps 11
\h'36u'\v'720u'\D'l72u 0u'
.sp -1
\h'36u'\v'432u'\D'l72u 0u'
.sp -1
\h'36u'\v'144u'\D'l72u 0u'
.sp -1
\h'216u'\v'1009u'\D'l0u -801u'
.sp -1
\h'216u'\v'208u'\D'l144u 0u'
.sp -1
\h'360u'\v'208u'\D'l0u 801u'
.sp -1
\h'360u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'584u'\v'1009u'\D'l0u -317u'
.sp -1
\h'584u'\v'692u'\D'l144u 0u'
.sp -1
\h'728u'\v'692u'\D'l0u 317u'
.sp -1
\h'728u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'72u'\D'l0u 1008u'
.sp -1
\h'72u'\v'1008u'\D'l864u 0u'
.sp -1
\v'738u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR50.0\fP'u'\s11\fR50.0\fP
.sp -1
\v'450u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR100.0\fP'u'\s11\fR100.0\fP
.sp -1
\v'162u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR150.0\fP'u'\s11\fR150.0\fP
.sp -1
\h'288u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'648u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
\h'648u'\v'1206u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRNFS\fP'u/2u'\s11\fRNFS\fP\h'-\w'\s11\fRNFS\fP'u/2u'
.sp -1
\h'432u'\v'1385u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR(a) Time to create\fP'u/2u'\s11\fR(a) Time to create\fP\h'-\w'\s11\fR(a) Time to create\fP'u/2u'
.sp -1
\h'432u'\v'1494u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRa 25MByte object\fP'u/2u'\s11\fRa 25MByte object\fP\h'-\w'\s11\fRa 25MByte object\fP'u/2u'
.sp -1
\h'36u'\v'17u'\h'-0.0m'\v'0.2m'\h'-\w'\s12\fRsec\fP'u'\s12\fRsec\fP
.sp -1
\h'1152u'\v'432u'\D'l72u 0u'
.sp -1
\h'1152u'\v'576u'\D'l72u 0u'
.sp -1
\h'1152u'\v'720u'\D'l72u 0u'
.sp -1
\h'1152u'\v'864u'\D'l72u 0u'
.sp -1
\h'1396u'\v'1009u'\D'l0u -288u'
.sp -1
\h'1396u'\v'721u'\D'l144u 0u'
.sp -1
\h'1540u'\v'721u'\D'l0u 288u'
.sp -1
\h'1540u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'2404u'\v'1009u'\D'l0u -219u'
.sp -1
\h'2404u'\v'790u'\D'l144u 0u'
.sp -1
\h'2548u'\v'790u'\D'l0u 219u'
.sp -1
\h'2548u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1702u'\v'1009u'\D'l0u -374u'
.sp -1
\h'1702u'\v'635u'\D'l144u 0u'
.sp -1
\h'1846u'\v'635u'\D'l0u 374u'
.sp -1
\h'1846u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'2122u'\v'1009u'\D'l0u -202u'
.sp -1
\h'2122u'\v'807u'\D'l144u 0u'
.sp -1
\h'2266u'\v'807u'\D'l0u 202u'
.sp -1
\h'2266u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1187u'\v'216u'\D'l0u 792u'
.sp -1
\h'1187u'\v'1008u'\D'l1584u 0u'
.sp -1
\h'1115u'\v'882u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR0.1\fP'u'\s11\fR0.1\fP
.sp -1
\h'1115u'\v'738u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR0.2\fP'u'\s11\fR0.2\fP
.sp -1
\h'1115u'\v'594u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR0.3\fP'u'\s11\fR0.3\fP
.sp -1
\h'1115u'\v'450u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR0.4\fP'u'\s11\fR0.4\fP
.sp -1
\h'1475u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRread\fP'u/2u'\s11\fRread\fP\h'-\w'\s11\fRread\fP'u/2u'
.sp -1
\h'1763u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRwrite\fP'u/2u'\s11\fRwrite\fP\h'-\w'\s11\fRwrite\fP'u/2u'
.sp -1
\h'2195u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRread\fP'u/2u'\s11\fRread\fP\h'-\w'\s11\fRread\fP'u/2u'
.sp -1
\h'2483u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRwrite\fP'u/2u'\s11\fRwrite\fP\h'-\w'\s11\fRwrite\fP'u/2u'
.sp -1
\h'2339u'\v'1242u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix NFS\fP'u/2u'\s11\fRUltrix NFS\fP\h'-\w'\s11\fRUltrix NFS\fP'u/2u'
.sp -1
\h'1619u'\v'1242u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'1979u'\v'1385u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR(b) Time to read or write a single byte\fP'u/2u'\s11\fR(b) Time to read or write a single byte\fP\h'-\w'\s11\fR(b) Time to read or write a single byte\fP'u/2u'
.sp -1
\h'1979u'\v'1494u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRat a random location\fP'u/2u'\s11\fRat a random location\fP\h'-\w'\s11\fRat a random location\fP'u/2u'
.sp -1
\h'1152u'\v'268u'\h'-0.0m'\v'0.2m'\h'-\w'\s12\fRsec\fP'u'\s12\fRsec\fP
.sp -1
.sp 1+1494u
.PE
.sp
.ce
.ps 11
Figure 6:  Elapsed time to create 25MByte file, read or write a single byte
.sp 0.5v
.hl
.in -0.5i
.)z
.sh 2 "Benchmark Results"
.pp
Figure 6a shows the elapsed time to create a 25MByte file
under Inversion and under Ultrix NFS.
As shown,
Inversion gets about 36% of the throughput of NFS for
file creation.
This difference is due primarily to the extra overhead in maintaining
indices in Inversion.
For every page written to the file,
Inversion must create a Btree index entry so that the page
can be located quickly later.
Btree writes are interleaved with data file writes,
penalizing Inversion by forcing the disk head to move frequently.
The NFS implementation does not maintain as much
indexing information on the data file,
and so can postpone writing its index until all data blocks
have been written.
This means that NFS writes the data file sequentially,
improving throughput.
.pp
Figure 6b shows the overhead for reading or writing a single
byte of the 25MByte file just created.
Since all caches were flushed prior to running the test,
a disk access is required.
For single-byte reads,
Inversion gets 70 percent of the throughput of NFS.
Single-byte writes are slightly worse;
Inversion is 61 percent of NFS.
Since Inversion never overwrites data in place,
a new entry must be written to the Btree block index,
accounting for the difference.
.(z
.in +0.5i
.hl
... 0.6 7.981 4.987 10.262 0 0 4096 4096
... 0u 1313u 2526u 0u -344u 5909u 2358099u -2352535u
.PS 1313 2526 
.br
.ps 11
\h'43u'\v'720u'\D'l72u 0u'
.sp -1
\h'43u'\v'432u'\D'l72u 0u'
.sp -1
\h'43u'\v'144u'\D'l72u 0u'
.sp -1
\h'43u'\v'288u'\D'l72u 0u'
.sp -1
\h'43u'\v'576u'\D'l72u 0u'
.sp -1
\h'43u'\v'864u'\D'l72u 0u'
.sp -1
\h'288u'\v'1009u'\D'l0u -478u'
.sp -1
\h'288u'\v'531u'\D'l144u 0u'
.sp -1
\h'432u'\v'531u'\D'l0u 478u'
.sp -1
\h'432u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'582u'\v'1009u'\D'l0u -398u'
.sp -1
\h'582u'\v'611u'\D'l143u 0u'
.sp -1
\h'725u'\v'611u'\D'l0u 398u'
.sp -1
\h'725u'\v'1009u'\D'l-143u 0u'
.sp -1
\h'1088u'\v'1009u'\D'l0u -697u'
.sp -1
\h'1088u'\v'312u'\D'l144u 0u'
.sp -1
\h'1232u'\v'312u'\D'l0u 697u'
.sp -1
\h'1232u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1376u'\v'1009u'\D'l0u -317u'
.sp -1
\h'1376u'\v'692u'\D'l144u 0u'
.sp -1
\h'1520u'\v'692u'\D'l0u 317u'
.sp -1
\h'1520u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1877u'\v'1009u'\D'l0u -783u'
.sp -1
\h'1877u'\v'226u'\D'l144u 0u'
.sp -1
\h'2021u'\v'226u'\D'l0u 783u'
.sp -1
\h'2021u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'2176u'\v'1009u'\D'l0u -346u'
.sp -1
\h'2176u'\v'663u'\D'l144u 0u'
.sp -1
\h'2320u'\v'663u'\D'l0u 346u'
.sp -1
\h'2320u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'79u'\D'l0u 1008u'
.sp -1
\h'79u'\v'1008u'\D'l2447u 0u'
.sp -1
\h'7u'\v'162u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR6.0\fP'u'\s11\fR6.0\fP
.sp -1
\h'7u'\v'306u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR5.0\fP'u'\s11\fR5.0\fP
.sp -1
\h'7u'\v'450u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR4.0\fP'u'\s11\fR4.0\fP
.sp -1
\h'7u'\v'594u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR3.0\fP'u'\s11\fR3.0\fP
.sp -1
\h'7u'\v'738u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR2.0\fP'u'\s11\fR2.0\fP
.sp -1
\h'7u'\v'882u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1.0\fP'u'\s11\fR1.0\fP
.sp -1
\v'18u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRseconds\fP'u'\s11\fRseconds\fP
.sp -1
\h'511u'\v'1097u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRSingle 1MByte read\fP'u/2u'\s11\fRSingle 1MByte read\fP\h'-\w'\s11\fRSingle 1MByte read\fP'u/2u'
.sp -1
\h'1302u'\v'1097u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1MByte read\fP'u/2u'\s11\fR1MByte read\fP\h'-\w'\s11\fR1MByte read\fP'u/2u'
.sp -1
\h'1302u'\v'1313u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'\s11\fRpage-sized chunks\fP\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'
.sp -1
\h'2094u'\v'1097u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1MByte read\fP'u/2u'\s11\fR1MByte read\fP\h'-\w'\s11\fR1MByte read\fP'u/2u'
.sp -1
\h'2094u'\v'1206u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRat random in\fP'u/2u'\s11\fRat random in\fP\h'-\w'\s11\fRat random in\fP'u/2u'
.sp -1
\h'2094u'\v'1313u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'\s11\fRpage-sized chunks\fP\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'
.sp -1
\h'367u'\v'486u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'1158u'\v'270u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'1950u'\v'162u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'655u'\v'558u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
\h'1446u'\v'630u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
\h'1302u'\v'1206u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRsequentially in\fP'u/2u'\s11\fRsequentially in\fP\h'-\w'\s11\fRsequentially in\fP'u/2u'
.sp -1
\h'2238u'\v'594u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
.sp 1+1313u
.PE
.sp 2
.ce
Figure 7: Elapsed read times for Inversion and Ultrix NFS
.sp 0.5v
.hl
.in -0.5i
.)z
.pp
Figure 7 compares Inversion to Ultrix NFS on large and small
reads.
The first pair of bars compares throughput using a single
large transfer to move data from the server to the client.
In this case,
Inversion gets eighty percent of the throughput of NFS.
When smaller transfers are used,
Inversion drops to 47 percent of NFS.
Profiling reveals that extra work is done in allocating and
copying buffers in Inversion.
If some of this overhead were eliminated,
Inversion's performance could be brought closer to that of NFS.
Since single-byte transfer times are much closer under the
two file systems,
there is reason to believe that tuning will improve Inversion.
.pp
The final pair of bars in Figure 7 compares the transfer
rates of Inversion and Ultrix NFS when the pages read are
distributed at random throughout the 25MByte file.
In this case,
Inversion gets 43 percent the throughput of NFS.
The additional overhead incurred by traversing the Btree page index
in Inversion accounts for much of the slowdown.
.pp
Figure 8 presents the write performance of Inversion and Ultrix NFS.
.(z
.in +0.5i
.hl
... 0.613 7.981 4.987 10.262 0 0 4096 4096
... 0u 1314u 2519u 0u -352u 5910u 2358546u -2352988u
.PS 1314 2519 
.br
.ps 11
\h'36u'\v'864u'\D'l72u 0u'
.sp -1
\h'36u'\v'720u'\D'l72u 0u'
.sp -1
\h'36u'\v'576u'\D'l72u 0u'
.sp -1
\h'36u'\v'432u'\D'l72u 0u'
.sp -1
\h'36u'\v'288u'\D'l72u 0u'
.sp -1
\h'36u'\v'144u'\D'l72u 0u'
.sp -1
\h'286u'\v'1009u'\D'l0u -645u'
.sp -1
\h'286u'\v'364u'\D'l144u 0u'
.sp -1
\h'430u'\v'364u'\D'l0u 645u'
.sp -1
\h'430u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'574u'\v'1009u'\D'l0u -276u'
.sp -1
\h'574u'\v'733u'\D'l144u 0u'
.sp -1
\h'718u'\v'733u'\D'l0u 276u'
.sp -1
\h'718u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1081u'\v'1009u'\D'l0u -806u'
.sp -1
\h'1081u'\v'203u'\D'l144u 0u'
.sp -1
\h'1225u'\v'203u'\D'l0u 806u'
.sp -1
\h'1225u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1369u'\v'1009u'\D'l0u -236u'
.sp -1
\h'1369u'\v'773u'\D'l144u 0u'
.sp -1
\h'1513u'\v'773u'\D'l0u 236u'
.sp -1
\h'1513u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'1870u'\v'1009u'\D'l0u -881u'
.sp -1
\h'1870u'\v'128u'\D'l144u 0u'
.sp -1
\h'2014u'\v'128u'\D'l0u 881u'
.sp -1
\h'2014u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'2169u'\v'1009u'\D'l0u -236u'
.sp -1
\h'2169u'\v'773u'\D'l144u 0u'
.sp -1
\h'2313u'\v'773u'\D'l0u 236u'
.sp -1
\h'2313u'\v'1009u'\D'l-144u 0u'
.sp -1
\h'72u'\D'l0u 1008u'
.sp -1
\h'72u'\v'1008u'\D'l2447u 0u'
.sp -1
\v'162u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR6.0\fP'u'\s11\fR6.0\fP
.sp -1
\v'306u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR5.0\fP'u'\s11\fR5.0\fP
.sp -1
\v'450u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR4.0\fP'u'\s11\fR4.0\fP
.sp -1
\v'594u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR3.0\fP'u'\s11\fR3.0\fP
.sp -1
\v'738u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR2.0\fP'u'\s11\fR2.0\fP
.sp -1
\v'882u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1.0\fP'u'\s11\fR1.0\fP
.sp -1
\v'54u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRseconds\fP'u'\s11\fRseconds\fP
.sp -1
\h'504u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRSingle 1MByte write\fP'u/2u'\s11\fRSingle 1MByte write\fP\h'-\w'\s11\fRSingle 1MByte write\fP'u/2u'
.sp -1
\h'1295u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1MByte written\fP'u/2u'\s11\fR1MByte written\fP\h'-\w'\s11\fR1MByte written\fP'u/2u'
.sp -1
\h'1295u'\v'1206u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRsequentially in\fP'u/2u'\s11\fRsequentially in\fP\h'-\w'\s11\fRsequentially in\fP'u/2u'
.sp -1
\h'1295u'\v'1314u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'\s11\fRpage-sized chunks\fP\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'
.sp -1
\h'2087u'\v'1098u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fR1MByte written\fP'u/2u'\s11\fR1MByte written\fP\h'-\w'\s11\fR1MByte written\fP'u/2u'
.sp -1
\h'2087u'\v'1206u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRat random in\fP'u/2u'\s11\fRat random in\fP\h'-\w'\s11\fRat random in\fP'u/2u'
.sp -1
\h'2087u'\v'1314u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'\s11\fRpage-sized chunks\fP\h'-\w'\s11\fRpage-sized chunks\fP'u/2u'
.sp -1
\h'360u'\v'306u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'648u'\v'666u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
\h'1151u'\v'126u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'1439u'\v'702u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
\h'1943u'\v'54u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRInversion\fP'u/2u'\s11\fRInversion\fP\h'-\w'\s11\fRInversion\fP'u/2u'
.sp -1
\h'2231u'\v'702u'\h'-0.0m'\v'0.2m'\h'-\w'\s11\fRUltrix\fP'u/2u'\s11\fRUltrix\fP\h'-\w'\s11\fRUltrix\fP'u/2u'
.sp -1
.sp 1+1314u
.PE
.sp 2
.ce
Figure 8: Elapsed write times for Inversion and Ultrix NFS
.sp 0.5v
.hl
.in -0.5i
.)z
The tests run were identical to those performed for Figure 7,
except that reads became writes.
In these tests,
the effect of the PRESTOserve board used by NFS is dramatic.
.pp
Since NFS must flush every write to stable storage,
Inversion should have dramatically better performance
than NFS without non-volatile RAM.
The reason for this is that NFS is forced to treat every
write as a single transaction,
and commit it to disk immediately.
Inversion,
however,
can obey the transaction constraints imposed by the client program,
and commit a large number of writes simultaneously.
.pp
Figure 8 shows that Inversion is slower than Ultrix NFS
backed by PRESTOserve.
For a single large write request,
Inversion gets 43 percent the throughput of NFS.
For page-sized sequential writes,
Inversion does worse,
getting only 31 percent of NFS' throughput.
For random accesses,
Inversion has only 28 percent the performance of NFS.
In fact,
the NFS measurements show no degradation due to random accesses,
since the whole 1MByte write fits in the PRESTOserve cache,
and is not flushed to disk.
.sh 2 "Evaluation of Benchmark Results"
.pp
[STON92] presents results from a benchmark of Inversion
run on a symmetric multiprocessor.
The results from that study are substantially better than those
observed here.
On a multi-processor,
Inversion gets between 50 and 95 percent of the throughput
of a native file system running on the same hardware.
.pp
The most important difference between this study and that
conducted for [STON92] is the process structure used to
evaluate the file system.
In the current benchmark,
the client program ran on a remote machine from the file server.
In [STON92],
both processes ran on the same machine.
When the client and server are on the same hardware,
more intelligent IPC mechanisms can be used.
In particular,
buffers shared by the two processes can be marked copy-on-write.
This eliminates an extra data copy.
Since no traffic crosses the Ethernet,
the savings are even more substantial.
Finally,
the symmetric multiprocessor examined in [STON92] allowed
one processor to move blocks between a main memory cache
and the file system
while other processors were carrying out computations.
As a result,
the earlier performance study achieved better results than
those presented here.
.pp
The results presented in [STON92] make it clear that the
communication overhead incurred by the current implementation
of Inversion is high.
In order to determine just how high,
another version of the benchmark was run.
In this case,
the benchmark tests were dynamically loaded into the \*(PG
process being used as the Inversion file server.
Since users can dynamically load their routines into the data manager,
this is an available option in cases where performance in critical.
In this case,
the Inversion
.q client
and
.q server
run in the same address space on the DECsystem 5900.
.pp
In this configuration,
data is never copied across address space boundaries,
and protocol overhead is eliminated.
The performance presented here is the best that a user
could achieve with the current implementation of Inversion.
Note that the same file system can be used simultaneously
by dynamically-loaded code
and by the more conventional client/server architecture.
.pp
Table 2 shows the performance of the single-process benchmark.
For convenience,
the performance of client/server Inversion and Ultrix NFS,
presented in the previous section,
are included.
.(z
.in +0.5i
.hl
.TS
.if \n+(b.=1 .nr d. \n(.c-\n(c.-1
.de 3f
.ps \n(.s
.vs \n(.vu
.in \n(.iu
.if \n(.u .fi
.if \n(.j .ad
.if \n(.j=0 .na
..
.nf
.nr #~ 0
.if \n(.T .if n .nr #~ 0.6n
.ds #d .d
.if \(ts\n(.z\(ts\(ts .ds #d nl
.fc
.nr 3d \n(.s
.rm 4k 4l 4m 4n
.nr 4k 0
.nr 3i \w\fIOperation\fP
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wCreate 25MByte file
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wSingle 1MByte read
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wPage-sized sequential 1MByte read
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wPage-sized random 1MByte read
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wSingle 1MByte write
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wPage-sized sequential 1MByte write
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wPage-sized random 1MByte write
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wRead single byte
.if \n(4k<\n(3i .nr 4k \n(3i
.nr 3i \wWrite single byte
.if \n(4k<\n(3i .nr 4k \n(3i
.4k
.rm 4k
.nr 4l 0
.nr 3i \w\fIInversion\fP
.if \n(4l<\n(3i .nr 4l \n(3i
.nr 3i \w\fIclient/server\fP
.if \n(4l<\n(3i .nr 4l \n(3i
.nr 3b 0
.nr 3c 0
.nr 3i \w141
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.5
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w3
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w4
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.8
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w5
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.5
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w4
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.6
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w5
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.6
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w6
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.0
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.02
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.03
.if \n(3c<\n(3i .nr 3c \n(3i
.4l
.rm 4l
.nr 4g \n(3b
.nr 3i \n(4g+\n(3c
.if \n(3i>\n(4l .nr 4l \n(3i
.if \n(3i<\n(4l .nr 4g +(\n(4l-\n(3i)/2
.nr 4m 0
.nr 3i \w\fIUltrix NFS\fP
.if \n(4m<\n(3i .nr 4m \n(3i
.nr 3b 0
.nr 3c 0
.nr 3i \w50
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.6
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w2
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.8
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w2
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.2
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w2
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w2
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.0
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w1
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.7
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w1
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.7
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.01
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.02
.if \n(3c<\n(3i .nr 3c \n(3i
.4m
.rm 4m
.nr 4h \n(3b
.nr 3i \n(4h+\n(3c
.if \n(3i>\n(4m .nr 4m \n(3i
.if \n(3i<\n(4m .nr 4h +(\n(4m-\n(3i)/2
.nr 4n 0
.nr 3i \w\fIInversion\fP
.if \n(4n<\n(3i .nr 4n \n(3i
.nr 3i \w\fIsingle process\fP
.if \n(4n<\n(3i .nr 4n \n(3i
.nr 3b 0
.nr 3c 0
.nr 3i \w111
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.6
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.8
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w1
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w1
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.4
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w2
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.9
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.01
.if \n(3c<\n(3i .nr 3c \n(3i
.nr 3i \w0
.if \n(3b<\n(3i .nr 3b \n(3i
.nr 3i \w.02
.if \n(3c<\n(3i .nr 3c \n(3i
.4n
.rm 4n
.nr 4i \n(3b
.nr 3i \n(4i+\n(3c
.if \n(3i>\n(4n .nr 4n \n(3i
.if \n(3i<\n(4n .nr 4i +(\n(4n-\n(3i)/2
.nr 3i 1n
.nr 4j 0
.nr 4a \n(4j+((0*\n(3i)/2)
.nr 4k +\n(4a
.nr 4b \n(4k+((6*\n(3i)/2)
.nr 4l +\n(4b
.nr 4g +\n(4b
.nr 4c \n(4l+((6*\n(3i)/2)
.nr 4m +\n(4c
.nr 4h +\n(4c
.nr 4d \n(4m+((6*\n(3i)/2)
.nr 4n +\n(4d
.nr 4i +\n(4d
.nr TW \n(4n
.if t .if \n(TW>\n(.lu .tm Table at line 3960 file Input is too wide - \n(TW units
.nr #I \n(.i
.in +(\n(.lu-\n(TWu-\n(.iu)/2u
.fc  
.nr #T 0-1
.nr #a 0-1
.eo
.de T#
.nr 3f 1m
.ds #d .d
.if \(ts\n(.z\(ts\(ts .ds #d nl
.mk ##
.nr ## -1v
.ls 1
.ls
..
.ec
.ta \n(4ku \n(4lu \n(4mu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'\h'|\n(4bu'\fIInversion\fP\h'|\n(4cu'\h'|\n(4du'\fIInversion\fP
.ta \n(4ku \n(4lu \n(4mu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'\fIOperation\fP\h'|\n(4bu'\fIclient/server\fP\h'|\n(4cu'\fIUltrix NFS\fP\h'|\n(4du'\fIsingle process\fP
.sp 0.5v
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Create 25MByte file\h'|\n(4bu'141.5\h'|\n(4cu'50.6\h'|\n(4du'111.6
.sp 0.5v
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Single 1MByte read\h'|\n(4bu'3.4\h'|\n(4cu'2.8\h'|\n(4du'0.4
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Page-sized sequential 1MByte read\h'|\n(4bu'4.8\h'|\n(4cu'2.2\h'|\n(4du'0.4
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Page-sized random 1MByte read\h'|\n(4bu'5.5\h'|\n(4cu'2.4\h'|\n(4du'0.8
.sp 0.5v
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Single 1MByte write\h'|\n(4bu'4.6\h'|\n(4cu'2.0\h'|\n(4du'1.4
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Page-sized sequential 1MByte write\h'|\n(4bu'5.6\h'|\n(4cu'1.7\h'|\n(4du'1.4
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Page-sized random 1MByte write\h'|\n(4bu'6.0\h'|\n(4cu'1.7\h'|\n(4du'2.9
.sp 0.5v
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Read single byte\h'|\n(4bu'0.02\h'|\n(4cu'0.01\h'|\n(4du'0.01
.ta \n(4ku \n(4gu \n(4lu \n(4hu \n(4mu \n(4iu \n(4nu 
.nr 3f 1m
.nr 3b \n(.f
\&\h'|\n(4au'Write single byte\h'|\n(4bu'0.03\h'|\n(4cu'0.02\h'|\n(4du'0.02
.fc
.nr T. 1
.T# 1
.in \n(#Iu
.3f
.TE
.if \n-(b.=0 .nr c. \n(.c-\n(d.-20
.sp
.ce
Table 2: Elapsed time in seconds for benchmark tests in three configurations
.hl
.in -0.5i
.)z
The elapsed time for each test is reported in seconds.
The measurements shown are the means of ten runs.
In all cases,
the standard deviation was negligible.
.pp
As Table 2 shows,
the single-process Inversion benchmark is faster than either
of the network benchmarks in virtually all categories.
The important exception is in random write time,
for which Ultrix NFS using PRESTOserve is fastest,
since no disk seeks are required.
Note,
however,
that the single-process implementation of Inversion
is faster than Ultrix with PRESTOserve for sequential transfers.
File creation is slower in both Inversion benchmarks,
due to the overhead of creating the Btree index of blocks.
.pp
The important comparison is between Inversion running on two machines
and Inversion running in a single process.
For 1MByte operations,
remote access adds between three and five seconds to the
elapsed time of each test.
It is clear that the client/server communication protocol
used by the file system is much too heavy-weight,
and should be optimized.
Given this optimization,
it is reasonable to expect performance within fifty percent of
Ultrix NFS and PRESTOserve from Inversion.
.sh 1 "CONCLUSIONS"
.pp
The research presented here makes contributions in three areas.
These contributions are
.BU
introducing a storage manager switch
abstraction into a database system,
making it easy to add new device types to a data manager;
.BU
the design and implementation of a device manager for
a Sony write-once optical disk jukebox;
and
.BU
the design and implementation of a novel filesystem,
Inversion,
which provides important semantic guarantees.
.pp
As tertiary storage devices are more widely deployed,
the importance of the storage manager switch abstraction will increase.
Current commercial relational databases include hard-coded
dependencies on magnetic disk.
Experience with \*(PG indicates that these dependencies
can be subtle and hard to identify.
Eliminating these dependencies is critical,
since tertiary storage has dramatically different characteristics
from magnetic disks.
.pp
The issues raised in designing the Sony jukebox device manager
include cache management policies,
allocation strategies,
and transfer size optimizations.
The Sony jukebox device manager achieves aggressive sharing
and supports fast recovery
by implementing a persistent cache.
The expense of setting up transfers from optical platters
is amortized by doing extent-based allocation,
and making extent sizes sufficiently large.
The cache size,
extent size,
and transfer size are all configurable.
.pp
The Inversion file system provides transaction protection,
fine-grained time travel,
fast recovery,
device independence,
strong typing,
and support for
.i "ad hoc"
queries on file system metadata and data.
As shown in the performance evaluation section,
Inversion gets between thirty and eighty percent of the throughput of
an optimized version of Ultrix NFS, which uses special-purpose
hardware to accelerate file system accesses.
Tuning should improve Inversion's performance further.
.sh 1 "FUTURE WORK"
.pp
The work presented here raises several new research problems.
This section lists some of the ways in which the storage manager,
the Sony jukebox device manager,
the Inversion file system,
or \*(PG as a whole could be improved.
.sh 2 "Better Integration of the Storage Manager into POSTGRES"
.pp
There are several ways in which the integration of the new
storage manager into \*(PG could be improved.
Most important of these is making relations truly location-transparent.
Doing so requires hiding the fact that some devices are actually
write-once.
As mentioned above,
this requires writing software to support logical
overwrite-in-place on relation data blocks.
Overwrite should work on all device managers.
.pp
Another area for future work is improving the cost estimation
functions for tertiary storage.
This may require more extensive changes to the query optimizer,
so that device managers can,
for example,
estimate locality of particular access paths.
The current cost estimation function for the Sony jukebox device manager
provides only a coarse guide in choosing an optimal execution plan.
One way to improve the ability of device managers to correctly
estimate plan cost would be to allow them to collect device-specific
statistics on the relations that they store.
.pp
There are also interesting research issues
in designing new access paths to relations on tertiary storage.
For example,
it may be desirable to invent new join strategies or indexing structures
that are optimized for high-latency,
low-bandwidth devices.
Such strategies would make tertiary storage much more attractive.
.pp
Finally,
when \*(PG supports clustering of relation data,
some design decisions in (for example) the Sony jukebox device manager
will need to be rethought.
If blocks at arbitrary locations in relations may be overwritten,
then the current strategy of keeping the highest-numbered block
on magnetic disk will not work.
.sh 2 "Tuning the Sony Jukebox Device Manager"
.pp
More experiments should be done on the Sony jukebox device manager,
to quantify the costs of cache maintenance,
transfer setup,
and extent-based allocation.
The behavior of the device manager could certainly be tuned
with some analysis of its current behavior.
In addition,
cache replacement policies other than LRU should be investigated.
.pp
Another strategy would be to reimplement the caching code completely.
The current implementation assumes a cache size on the order of tens
of megabytes.
If this were scaled to,
say,
a gigabyte,
different cache layout strategies would make sense.
For example,
extents could be laid out using a hash function,
rather than contiguously on disk.
.sh 2 "Work on the Inversion File System"
.pp
The Inversion file system,
similarly,
should be profiled and tuned to improve its performance.
It may make sense to use other indices,
or other indexed access methods altogether,
on the blocks and metadata of files stored in Inversion.
The protocol used for network file access should be
redesigned to speed up transfers.
.pp
One issue that should be addressed is the programmatic
interface to Inversion files.
Since Inversion provides a strict superset of the services
provided by conventional \*(UX systems,
the interface to Inversion will be different from the
interface to the native file system.
For example,
time travel requires the specification of timestamps
when opening a file.
This interface is not yet clearly defined.
.pp
Two other important issues are management of a file system cache
and the policy used to lay out file data blocks on storage devices.
Unfortunately,
both of these require violating the storage manager abstraction.
It would be interesting to see if a clean interface
could be devised that would continue to support device extensibility,
and still allow Inversion to handle layout and caching.
.sh 2 "Addition of New Device Managers"
.pp
Finally,
new device managers should be added to \*(PG.
Hardware that will soon become available to the project
includes
a Metrum videocassette jukebox,
an Exabyte 8500 8mm helical scan jukebox,
and a Hewlitt-Packard magneto-optical disk jukebox.
New device managers should be written for these.
.pp
Currently,
a version of \*(PG exists that optimizes and executes
parallel query plans [HONG92].
Parallel \*(PG uses striping,
or horizontal partitioning of relations,
in order to achieve data parallelism.
A striping device manager for magnetic disk would be easy to write,
and would eliminate a good deal of special-case code
in the parallel version of the system.
.sh 1 "ACKNOWLEDGEMENTS"
.pp
Joey Hellerstein and Wei Hong
reviewed early versions of this thesis
and suggested many improvements.
Margo Seltzer and Mark Sullivan,
Sin City's senior citizens,
offered useful advice
on the design and implementation of the storage manager
switch and the Inversion file system.
Dr. Randy Katz and Dr. Ray Larson
served as members of my thesis committee.
Dr. Michael Stonebraker's guidance and encouragement
have been invaluable throughout the project.
Finally,
I want especially to thank my wife Teresa
and my son Matthew for their patience and support over the
course of an apparently endless academic career.
.sh 1 "REFERENCES"
.ls 1
.nr ps 1v
.nr ii 0.9i
.ip [BERN88]
Bernstein, P., \fIet al.\fP, ``Future Directions in DBMS Research'',
\fIThe Laguna Beach Report\fP, Laguna Beach, CA, February 1988.
.ip [CABR88]
Cabrera, L., and Wyllie, J., ``QuickSilver Distributed File Services:
An Architecture for Horizontal Growth'', \fIProc. 2nd IEEE Conference
on Computer Workstations\fP, March 1988.
.ip [CHUT92]
Chutani, S., \fIet al.\fP, ``The Episode File System'', \fIProc. USENIX
Winter 1992 Technical Conference\fP, San Francisco, CA, January 1992.
.ip [FONG86]
Fong, Z., ``The Design and Implementation of the \*(PG Query Optimizer'',
M.Sc. Report, University of California at Berkeley,
Berkeley, CA, Aug. 1986.
.ip [HAAS90]
Haas, L., \fIet al.\fP, ``Starburst Midflight: As the Dust Clears'',
\fIIEEE Transactions on Knowledge and Data Engineering\fP, March 1990.
.ip [HONG92]
Hong, W., ``Exploiting Inter-Operation Parallelism in XPRS'', \fIProc.
1992 ACM-SIGMOD International Conference on Management of Data\fP,
San Diego, CA, June, 1992 (to appear).
.ip [KATZ91]
Katz, R., \fIet al.\fP, ``Robo-line Storage: Low Latency, High Capacity
Storage Systems Over Geographically Distributed Networks,''
Sequoia 2000 Technical Report 91/3, UC Berkeley, October 1991.
.ip [KIM84]
Kim, W., ``Highly Available Systems for Database Applications'', \fIACM
Computing Surveys\fP 16(1), 1984.
.ip [LEFF84]
Leffler, S., \fIet al.\fP, ``An Advanced 4.3BSD Interprocess Communication
Tutorial'', \fI\s-1UNIX\s0 Programmer's Manual Supplementary Documents\fP
vol. 1, Berkeley, CA, 1984.
.ip [LEFF89]
Leffler, S., \fIet al.\fP, \fIThe Design and Implementation of the
4.3 BSD Operating System\fP, Prentice-Hall, 1989.
.ip [MCFA91]
McFadden, A., ``C Library Interface for the Sony Optical Disk Changer'',
CS199 Project Report, UC Berkeley, May 1991.
.ip [MOSH92]
Mosher, C., \fIed.\fP, ``The \*(PG Reference Manual, Version 4'',
UCB Technical Report M92/14, Electronics Research Laboratory, University
of California at Berkeley, Berkeley, CA, March 1992.
.ip [PIKE90]
Pike, R., \fIet al.\fP, ``Plan 9 From Bell Labs'', \fIProc. Summer 1990
UKUUG Conference\fP, London, England, July 1990.
.ip [POTA91]
Potamianos, J., ``Semantics and Performance of Integrated DBMS Rule
Systems'', Ph.D. Dissertation, University of California at Berkeley,
Berkeley, CA, January 1992.
.ip [RASH88]
Rashid, R., \fIet al.\fP, ``Machine-Independent Virtual Memory Management
for Paged Uniprocessor and Multiprocessor Architectures'', \fIIEEE
Transactions on Computers\fP Vol. 37 No. 8, August 1988.
.ip [ROOM92]
Roome, W.D., ``3DFS: A Time-Oriented File Server'', \fIProc. USENIX Winter
1992 Technical Conference\fP, San Francisco, CA, January 1992.
.ip [ROSE91]
Rosenblum, M. and Ousterhout, J., ``The Design and Implementation of
a Log-Structured File System'', \fIProc. 13th Symposium on Operating
Systems Principles\fP, 1991.
.ip [SAND85]
Sandberg, R., \fIet al.\fP, ``Design and Implementation of the Sun
Network File System'', \fIProc. Usenix Summer 1985 Technical Conference\fP,
June 1985.
.ip [SECH91]
Sechrest, S., ``Attribute-Based Naming of Files'', University of Michigan
Technical Report CSE-TR-78-91, January 1991.
.ip [SELI79]
Selinger, P., \fIet al.\fP, ``Access Path Selection in a Relational
Database Management System'', \fIProc. 1979 ACM-SIGMOD Conference on
Management of Data\fP, Boston, MA, June 1979.
.ip [SELT90]
Seltzer, M., and Stonebraker, M., ``Transaction Support in Read Optimized
and Write Optimized File Systems,'' \fIProc. 16th International Conference
on Very Large Data Bases\fR, Brisbane, Australia, August 1990.
.ip [SKEE81]
Skeen, D., ``Nonblocking Commit Protocols'', \fIProc. 1981 ACM SIGMOD
Conference\fP, 1981.
.ip [SONY89a]
Sony Corporation, ``Writable Disk Auto Changer WDA-610 Specifications
and Operating Instructions'', 3-751-106-21 (1), Japan, 1989.
.ip [SONY89b]
Sony Corporation, ``Writable Disk Drive WDD-600 and Writable Disk WDM-6DL0
Operating Instructions'', 3-751-047-21 (1), Japan, 1989.
.ip [STON87]
Stonebraker, M., ``The \*(PG Storage System'', \fIProc. 1987 VLDB
Conference\fP, Brighton, England, Sept. 1987.
.ip [STON90]
Sonebraker, M., \fIet al.\fP, ``The Implementation of \*(PG'',
\fIIEEE Transactions on Knowledge and Data Engineering\fP, March 1990.
.ip [STON91]
Stonebraker, M., and Dozier, J., ``Sequoia 2000:  Large Capacity
Object Servers to Support Global Change Research,''
Sequoia 2000 Technical Report 91/1, UC Berkeley, July 1991.
.ip [STON92]
Stonebraker, M., and Olson, M., ``Large Object Support in \*(PG'',
submitted to \fIProc. 1992 VLDB Conference\fP, Vancouver, BC, Canada.
.ip [SULL92]
Sullivan, M.  and Olson, M., ``An Index Implementation Supporting Fast
Recovery for the \*(PG Storage System'', \fIProc. 8th Annual International
Conference on Data Engineering\fP, Tempe, AZ, February 1992.
.ip [WALK83]
Walker, B., \fIet al.\fP, ``The LOCUS Distributed Operating System'',
\fIOperating Systems Review\fP v. 17 no. 5, November 1983.
.nr % 0
.af % i
.he ''''
.bp
.rs
.sp |2i
.ce 99
.ps 14
.ft B
Extending the \*(PG Database System
.sp 0.2v
to Manage Tertiary Storage
.ps 12
.he '''\fR%\fP'
.sp 2
.ft R
Michael Allen Olson
.sp 0.2v
Department of Electrical Engineering and Computer Science
University of California at Berkeley
.sp
Master's Thesis
.sp 3.5i
Version \*(VN (\*(VD)
\*(VT
Printed \*(td
.ce 0
.bp
.rs
.sp |4i
.ps 11
.ce 99
Extending the \*(PG Database System to Manage Tertiary Storage
.sp
Copyright \(co 1992
.sp
by
.sp
Michael Allen Olson
.bp
.ce
.ps 12
Table of Contents
.ps
.sp 2
.nr pi 0
.xp
