% File:    tsp-paper.tex
% Author:  RM, FM, JWS
% Date:    01-JUL-1996
% Purpose: Publication ADBIS'96
%
\documentstyle[xple_sl,epsf]{acmconf}
\newcommand{\figwidth}{\textwidth}

\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}

\title{Towards a Unified Model of\\ Untyped Object Stores:\\
Experience with the Tycoon Store Protocol}

\author{Florian Matthes, Rainer M\"uller, Joachim W.\ Schmidt\\
	Universit\"at Hamburg\\Vogt-K\"olln Stra{\ss}e 30\\
        D-22527 Hamburg, Germany\\
	{\tt matthes,mueller,J\_Schmidt@informatik.uni-hamburg.de}}
 

\begin{document} 


\maketitle

\begin{abstract}
The Tycoon Store Protocol (TSP) specifies a clean interface between the
frontend and the backend of fully integrated persistent environments. In
contrast to high-level relational or object-oriented database languages, TSP is
based on a low level, untyped, but highly flexible tagged store model that is
particularly well-suited for the implementation of higher-order persistent
polymorphic languages.  We describe the TSP operations in some detail and give
insight into TSP's design rationale. We also report on the existing set of
TSP-compliant backends including TSP adaptors to commercial object stores. A
TSP client can choose dynamically between these backends and it is possible to
exchange complex object graphs between all TSP-compliant stores via a
platform-independent external data representation.
\end{abstract}

\section{Introduction and Motivation}

Virtually all systems that have to work with large-scale persistent data 
have a system architecture where there is a clean separation between a 
\e{frontend} performing data manipulation and visualization and a \e{backend} responsible for reliable persistent bulk data storage.  Since actions 
in the frontend trigger data access operations performed by the backend, 
this separation naturally leads to a client-server architecture, where a 
\e{store protocol} defines possible interactions between a client program 
and a database server.

\begin{figure*}[t]
\begin{center} \leavevmode
\epsfxsize=14cm
\epsffile{Scal.ps}
\end{center}
\caption{The role of the Tycoon Store Protocol in scalable persistent 
systems}
\label{Fig:Scale}
\end{figure*}


For standard database applications like business applications, SQL is the 
store protocol of choice: SQL provides \e{standardized} high-level, 
application-oriented store operations, it is available on a wide range of 
platforms, and there are standardized mechanisms to perform the frontend to
backend binding (static language bindings via preprocessors,  
dynamic SQL invocation via an application programming interface like 
ODBC).  The ODMG standard \cite{Cate94,Catt94} and the ISO STEP standards \cite{EXPRESS} define similar high-level store protocols to access 
object-oriented databases and repositories of construction data, 
respectively.

Unfortunately, these commercially well-supported store protocols turn out 
to be of little help in the construction of fully integrated persistent 
programming environments since their hard-wired high-level data models do 
not match the flexibility requirements of persistent languages (see 
\cite{MMS92,Mue91b} for a more detailed discussion):

\begin{itemize} 
\item Full persistence abstraction \cite{AtBu86} requires 
a 
uniform, efficient element-oriented access to persistent and 
non-persistent 
data, code and threads \cite{MaSc95a} which leads to an overly expensive 
two-level store management if implemented via standard database
call interfaces. 

\item Polymorphic data structures, higher-order (polymorphic) functions and 
user-defined abstract data types are very hard to realize in  
monomorphic high-level data models.

\item Incremental program construction and reflective programming 
techniques require schema modifications at runtime and dynamic binding 
techniques which are beyond the scope of most standard store protocols.  
\end{itemize}

As a consequence of these difficulties, virtually each persistent 
programming environment comes with its own tailored object store (and vice 
versa).  If one looks at existing pairs of object stores and their 
persistent languages, like Exodus and E, O$_2$ and O$_2$C or ObjectStore 
and Persistent C, their internal object store protocols are often well 
below the abstraction level of SQL or of the ODMG languages.  Furthermore, 
these store protocols are characterized by heavy dependencies between 
language processor and storage subsystem and by several ad-hoc design 
decisions regarding object layout and object lifetime.

In this paper we describe the Tycoon Store Protocol (TSP) that has been 
developed during the last three years by our group
to overcome the above problems and to provide a well-defined, 
standardized interface between the frontend and the backend of fully 
integrated persistent environments.  This interface is based on the widely 
accepted notion of an \e{untyped persistent heap} (\cite{MoSi88,BrMo91,KKD89}).
Despite the fact that 
TSP has been implemented and evaluated in the context of the Tycoon 
project \cite{MaSc93b}, TSP is fully independent of the Tycoon system and supports 
multiple (generic) clients and multiple database servers.

This paper is organized as follows: We first sketch how TSP contributes to the construction of scalable persistent systems. In section~\ref{TSPTypes} we describe the untyped TSP store model followed by a detailed discussion of the TSP operations in section~\ref{operations}. Section~\ref{experience} reports on our experience implementing TSP backends by adaptors to existing object stores and extending the TSP functionality systematically by TSP-compliant layers. 

%------------------------------------------------------------------------------

\section{On the Construction of Scalable Persistent Systems} \label{ScaleSys}


TSP has been designed to support the construction of 
\e{scalable} persistent systems, i.e., configurable systems where the 
complexity and size of the entire system is proportional to the 
operational 
support required by a particular client.  For example, it should be 
possible to add features like multi-user access, distribution and access 
control to the basic persistent storage services without perturbating the 
overall system architecture of a persistent system.
On the other hand, the performance of clients 
that do not need these advanced features should not be deteriorated by the 
extensibility of the system.

Figure~\ref{Fig:Scale} explains the role of TSP in such a persistent 
system 
scenario.  The data access operations defined in TSP are issued by client 
programs and executed by database servers.  Currently, TSP is used by the 
runtime system of two persistent languages (TL \cite{MaSc92a}, TooL \cite{GaMa95a})
 developed at Hamburg 
University and by a network file system (NFS) implementation of our group 
that makes it possible to read and manipulate persistent store objects 
like ordinary Unix files or directories enhanced by a 
transactional recovery mechanism.  Further TSP clients like runtime 
systems 
for other persistent languages such as Fibonacci \cite{ABDGOR94} are under 
development.  Each of these clients can choose dynamically between one of the 
following 
TSP implementations with distinct operational qualities and performance 
characteristics: 

\begin{itemize}

\item \p{Tymem} is a portable main memory store developed by our group that 
achieves persistence and recovery through standard file system services.

\item \p{Tysin} is a portable disk-based single user store that was developed 
by our group specifically for systems without virtual memory support 
like Microsoft Windows and Macintosh OS.

\item \p{Napier} is a store adaptor to the Napier disk-based single user store 
for SunOS systems \cite{Brow89}.  This store makes heavy use of memory-mapped 
files \cite{RHBMM90} to achieve very fast object addressing.

\item \p{Object} is a store adaptor to the commercial product ObjectStore \cite{LLOW91}, a multi-user store with a client-server architecture.

\end{itemize}

Furthermore, TSP is intended to be a stackable protocol.  For example, it 
is possible to add access control, persistent savepoints or version 
management on top of arbitrary stores that adhere to TSP.  These 
optional system layers utilize TSP as their lower and upper interfaces and 
extend the semantics of individual TSP operations (e.g., store object 
update) and provide additional TSP operations (e.g., rollback to 
savepoint).

TSP defines a stable application programming interface for client programs 
(expressed by a standard C header file) that is complemented by a 
platform-independent external data representation (TXR) that can be 
generated and parsed by all TSP backends.  The TXR makes it possible to 
transfer arbitrary complex, graph-structured persistent store objects via a 
linear data representation from one backend to another without exposing 
private implementation details of individual persistent stores.  We have 
found the TXR to be extremely valuable for backup, communication, 
migration and system evolution purposes.  Some of these application areas 
are described in \cite{MMS95a,MMS95b}.
 
A client can use TSP to access multiple stores (possibly of 
multiple architectures) concurrently and a multi-user database server like 
ObjectStore supports multiple TSP clients at a time which may run on 
different client nodes in a local area network accessing a shared
persistent store.

%--------------------------------------------------------------------------

\section{An Untyped Store Model} \label{TSPTypes}

A primary design goal behind TSP has been to provide efficient data storage 
as independent as possible from the data and language model supported by 
TSP store clients.  In particular, TSP should be capable of supporting 
polymorphically typed models where the components of store objects can 
contain values of multiple types that cannot be fixed in a separate schema 
definition phase.  TSP therefore uses an \e{untyped} low-level store model, 
i.e., there is no separate dictionary of type or schema information 
maintained by the backend.  Instead of this, store values are made 
self-descriptive by imposing a regular object layout and a uniform 
tagging scheme.  As a result, TSP achieves data model independence without 
sacrificing the advantages of self-descriptive statically-typed databases.


\subsection{Atomic Data Values}

On the one hand, TSP is to be defined without knowledge of the 
particular base types (integer, string, real, \ldots) and type constructors 
(record, object, array, set, list, \ldots) supported by its various 
clients.  On the other hand, TSP has to perform algorithms on store objects 
like concurrency control, garbage collection and portable data exchange 
that require a limited knowledge of the semantics of data values.  
Furthermore, TSP has to provide efficient access mechanisms to read and 
update atomic data values like integers, addresses or object identifiers.
     
\begin{figure}[ht]
\begin{center} \leavevmode
\epsfxsize=8cm
\epsfbox{Thierarchy.ps}
\end{center}
\caption{The type hierarchy underlying TSP}
\label{Fig:AtomicTypes}
\end{figure}

To match best the data modeling requirements of a given  TSP client / server pair the TSP definition is \e{parameterized} by the following 
``abstract'' atomic types  (see figure ~\ref{Fig:AtomicTypes}):
 
\begin{description} 

\item[\p{tsp\_Bool}] is a parameter type for TSP operations with the constants 
\p{tsp\_TRUE} and \p{tsp\_FALSE}.

\item[\p{tsp\_Word}] is the supertype from which most other TSP types 
like object identifiers or tagged values are derived as subtypes.  In particular, the size of \p{tsp\_Word} 
values has to be greater or equal to the size of values of these other 
types. Typical bit sizes for tsp\_Word values are 16, 32 or 64.

\item[\p{tsp\_Byte}] is the type of values stored in byte array objects.

\item[\p{tsp\_Value}] is the type of values manipulated by client programs.

\end{description}

Technically, these parametric type definitions are provided by a platform 
and storage-system dependent C header file (e.g.  \p{tsp32.h}).  This file 
has to precede the TSP C header file that is shared between all TSP implementations. The TSP header file defines additional derived or 
abstract types as shown in figure ~\ref{Fig:AtomicTypes}.

The type \p{tsp\_Tagged} is the union of values from type 
\p{tsp\_OID}, the type of persistent object identifiers, and of type 
\p{tsp\_Immediate}, the type of TSP immediate values.  The type 
\p{tsp\_Tagged} is used in those contexts where both \p{tsp\_OID} and 
\p{tsp\_Immediate} values are valid.  As the type name \p{tsp\_Tagged} 
indicates, it is possible to distinguish OIDs from immediate values at 
runtime based on a tagging scheme.

The conversion between tagged store values (\p{tsp\_Immediate}) and client 
values (\p{tsp\_Value}) is encapsulated by two TSP mapping functions:

\begin{xple} 
tsp\_Immediate
    tsp\_valueToImmediate(tsp\_Store s, tsp\_Value val); 
tsp\_Value
     tsp\_immediateToValue(tsp\_Store s, tsp\_Immediate imm);
\end{xple}

It should be noted that the size of client values is conceptually not 
dependent on the word size of the TSP implementation.  Thus, the bitsize of 
a value of type \p{tsp\_Value} can be smaller, equal or larger than the 
bitsize of a value of type \p{tsp\_Word}. For example, in some stores polymorphic array objects have to implemented with an additional level of indirection such that client values can be larger than the slot size. The actual size supported by an TSP 
implementation can be retrieved by the TSP operation:

\begin{xple} 
tsp\_Word tsp\_nValueBits(tsp\_Store s); 
\end{xple}

Values of type \p{tsp\_Format} are used to define the format of structured 
persistent objects in the store and are explained in the next section.


\subsection{Structured Data Objects} \label{StructObj}
\label{objProp}

TSP supports only two kinds of persistent data structures which are called array 
objects and byte array objects.  In any context where both array and byte 
array objects are valid, we use the term object.  Therefore, array objects 
and byte array objects are specializations of type object.  Since there are 
no instances of type object, this type is similar to an abstract class in 
C++.
 
Every object has an object identifier (OID) that is guaranteed to be unique 
within a given TSP store.  Object identifiers can be stored in arrays to 
establish bindings between objects.  TSP does not guarantee object 
identifiers to be immutable over the lifetime of an object.  For example, 
some TSP implementations re-assign OIDs during garbage collection.  
However, any implementation of the TSP guarantees that bindings 
between objects within the store are preserved.

Objects are allowed to hold atomic data values (as described in the 
previous section) only.  Complex objects are constructed by establishing 
bindings between objects and not through object nesting.  Since all TSP 
operations on objects have reference semantics, the signatures of TSP 
object operations uniformly use the type \p{tsp\_OID}.

\begin{figure}[ht]
\begin{center} \leavevmode
\epsfxsize=8cm
\epsfbox{Object.ps}
\end{center}
\caption{Structure of a TSP object}
\label{Fig:Objects}
\end{figure}

As depicted in figure~\ref{Fig:Objects}, a TSP object conceptually 
consists of two parts: an object header (holding information about the 
object size, object mutability and object format) and a number of slots.  
When an object is created, the number of slots and the format have to be 
specified.  An object is allowed to contain no slots at all.  The first 
slot in an array has index 0.  Conceptually, the maximum number of slots of 
a TSP object is infinite but there might be TSP implementations that define 
an upper limit.  However, this limit is expected to be much larger than the 
page size of a traditional database system.  In some persistent 
applications (e.g.  B-Tree index management) TSP clients would like to 
create objects that fit exactly onto a single page of the underlying 
persistent store.  In such applications, the function
\begin{xple}
tsp\_Word tsp\_nWordsPerPage(tsp\_Store s); 
\end{xple}
can be used to return an integer value to be used as a size 
specification for a subsequent array object creation operation.
Except for this ``hint'', page sizes of the TSP backend are fully transparent
to TSP clients.

TSP provides operations to inspect the format and size of an object. The 
operation (\p{tsp\_getFormat}) returns a value of type \p{tsp\_Format} which is 
organized as a bit vector.  The size of the bit vector 
depends on the TSP implementation.  The lowest two bits of the vector are 
reserved for TSP purposes to distinguish between the three built-in array 
formats described below.  The number of remaining format bits available to 
the client can be retrieved by the following TSP operation:
\begin{xple} 
tsp\_Word tsp\_nFormatBits(tsp\_Store s);
\end{xple}
These bits can be utilized by TSP clients to define specialized array or byte 
array objects, for example arrays of real numbers, as subtypes of the 
following two predefined object types:

\begin{description} 

\item[\k{Array Objects}:] TSP supports two builtin formats for array objects.  
The format determines which values can be stored in the slots of an array 
object.

Array objects with format \p{tsp\_Format\_TAGGED } contain values of 
type \p{tsp\_Tagged}.  In particular, such array objects must not contain 
untagged values of type \p{tsp\_Word} because a TSP server uses the tagging 
information to differentiate between object identifiers and immediate 
values.
      
Array objects with format \p{tsp\_Format\_WORD} contain untagged values of 
type \p{tsp\_Word}.  It is not allowed to store object identifiers in 
such arrays.  On the other hand, the full bit size of type \p{tsp\_Word} is 
available in each array slot.  The format information \p{tsp\_Format\_WORD} 
is used heavily by the garbage collector and the TSP operations 
\p{tsp\_intern} and \p{tsp\_extern} to reduce the execution time for these 
operations.

\item[\k{Byte Array Objects}:] The size of an individual slot in a byte array 
is given by the size of values of type \p{tsp\_Byte}.  The predefined format 
code for byte arrays is \p{tsp\_Format\_BYTE}.

\end{description}       

After creation, the slot values of an object can be updated.  Therefore, 
the state of a newly created object is called mutable.  It is possible to 
set the state of an object to immutable (\p{tsp\_setImmutable}).  
Subsequently, it is not allowed to update the object and it is not possible 
to change the state of an object from immutable back to mutable.  The TSP 
operation \p{tsp\_isImmutable} can be used to test whether an object is 
immutable.  The immutability information is exploited by many TSP 
implementations to optimize storage management, concurrency control and 
recovery.
     
%------------------------------------------------------------------------------
    

\section{Overview of the Tycoon Store Protocol}\label{operations}

Due to the simplicity of TSP's data model, it is possible to define concisely 
all its operations which are clustered into operations on 
persistent stores, failure handling, that are detailed in the following
sections.
\begin{figure}[ht]
\begin{center} \leavevmode
\epsfxsize=8cm
\epsffile{State.ps}
\end{center}
\caption{Store state diagram}
\label{StoreStates}
\end{figure}

\subsection{Operations on Persistent Stores} \label{StoreOps}

Figure ~\ref{StoreStates} shows the possible states of a TSP store and 
the operations that trigger state transitions of a store.

A TSP store must be created before it can be used.  A TSP store can be 
created only within a TSP session.  A client starts a session by calling 
the TSP function \p{tsp\_init}.  A session is finished by terminating the 
operating system process that started the session.  It is not allowed to 
call \p{tsp\_init} multiple times within a session.

A TSP store has a unique root value of type \p{tsp\_Tagged} that serves as an entry point into the store.  On creation
of a store, an initial root value has to be specified.
The initial root value must be an immediate value.  If the store can be
created it changes its state from \p{non\_existent} to \p{open} and a
handle for the store is returned to the client.  The store handle is
used by virtually all TSP operations to identify the store for which
the operation is to be executed.  This is necessary because TSP allows
a client to operate on multiple stores simultaneously (some
implementations, like the Napier Store, restrict the number of stores
to one).  Cross references between different stores are not supported
by the basic TSP.

Consistent states of an object store can be made persistent 
(``committed'').  The initial state of a newly created store is committed 
automatically.  Subsequently, a client  creates objects and links 
them together using TSP operations to form an object graph in the store.  
To make the object graph persistent, the client has to perform the following 
three steps:

\begin{enumerate}

\item Update the root of the store with the object identifier of the root 
of the graph (\p{tsp\_setRoot(store, oid))}.  This object is also called 
the root object of the store. Alternatively, if an object store already contains some 
objects, a newly created object graph can be made reachable through its 
OIDs from the existing object graph.
 
\item Ensure that the store can be committed \\(\p{tsp\_prepareCommit)}.  
This function must be called before calling \p{tsp\_commit} and returns \p{tsp\_TRUE} to indicate that a subsequent \p{tsp\_commit} will succeed (otherwise \p{tsp\_FALSE} is returned but no automatic rollback is triggered).  The state of the store changes from \p{open} to \p{committable}.

\item Define a new persistent state by committing the changes made to the 
store (\p{tsp\_commit}).  When a store is committed, all modifications to 
the store are written atomically to the persistent storage device the store 
resides on.  Because TSP defines persistence by reachability, the root 
object and any object transitively reachable from the root object are made 
persistent.  Moreover, the store changes its state from \p{committable} to 
\p{open}.
             
\end{enumerate}

The description above assumes that a TSP backend supports an explicit two-phase commit protocol. This store property can be inquired at runtime with the TSP function \p{tsp\_hasTwoPhaseCommit}. If no two-phase commit is supported by a store \p{tsp\_prepareCommit} always returns \\\p{tsp\_TRUE}.

As long as the store is in the \p{open} state, the client has the ability 
to create new objects, to modify objects and to commit the new state of the 
store.  It is also possible for a client to rollback to the last committed 
state of the store, by calling \p{tsp\_rollback}.  \p{tsp\_rollback} 
deletes all objects the client has created since the last call to 
\p{tsp\_commit} and cancels the modifications of all other objects.  This 
function can also be called if the state of the store is \p{committable}.
     
If an open store is no longer used within a session, it can be closed by 
calling \p{tsp\_closeStore}.  \p{tsp\_closeStore} does not commit the store 
automatically.  On successful completion of the operation, the store 
changes its state to \p{closed} and TSP invalidates the store handle.  It 
is not allowed to call a TSP function with an invalidated store handle (the 
result of such operations is undefined).  The only valid TSP operations 
that can be applied to a \p{closed} store are \p{tsp\_openStore} and 
\p{tsp\_deleteStore}.  The first one must be called before working on a 
store and sets the state of the store to \p{open}.  The second one, 
\p{tsp\_deleteStore}, irrevocably destroys the store and sets its state to 
\p{non\_existent}.


The following table summarizes the restrictions on the set of TSP 
operations that are applicable in a given state of the store.

\begin{center}
\begin{tabular}{|l|l|} 
\hline
Store State      & Valid Operations \\
\hline 
\hline
\p{open} 	    & all TSP operations except \p{tsp\_deleteStore,} \\& \p{tsp\_commit} \\ 
\hline
\p{closed}	    & \p{tsp\_openStore, tsp\_deleteStore} \\ 
\hline
\p{committable} & \p{tsp\_commit, tsp\_rollback} \\ 
\hline	
\end{tabular}
\end{center}

  

\subsection{Failure Handling and Recovery}

If any of the TSP operation cannot be executed correctly, a standard 
failure handling procedure is called that prints an error message and then 
terminates the client process undoing all changes to the store since the 
last commit operation.  TSP provides operations to substitute this default 
failure handling procedure and to retrieve the currently defined failure 
handler.  The client-defined handler must be of type 
\p{tsp\_FailureHandler}.  A handler has two parameters.  The type of the 
first one is \p{tsp\_Store} (a store handle) and the type of the second one 
is \p{tsp\_Failure} (the reason of the failure).  The client process is 
also terminated if a failure handler returns control back to the calling 
TSP operation.  The set of possible failures is represented by the 
enumeration type \p{tsp\_Failure}.  The meaning of each failure value of 
type \p{tsp\_Failure} is given below.

\begin{description} 

\item[\p{tsp\_Failure\_ERROR}] is a generic error code that can be raised 
by any TSP operation, e.g. if illegal argument values have been supplied 
to an operation.
	
\item[\p{tsp\_Failure\_DEADLOCK}] is raised if a deadlock is detected.  
Before this failure is signaled to the TSP client, TSP automatically 
performs a rollback.  The resulting state of the store is \p{open} (see 
section~\ref{StoreOps}).

\item[\p{tsp\_Failure\_STORE\_FULL}] is raised if the maximum size of a 
store has been reached.  It depends on the implementation of TSP whether 
the maximum size is limited by the number of objects or the total byte size 
of the store (or both).

\item[\p{tsp\_Failure\_OUT\_OF\_MEMORY}] is raised if TSP cannot allocate 
sufficient main memory to execute a TSP operation.
         
\item[\p{tsp\_Failure\_COMMIT}] is raised if the \p{tsp\_commit} operation 
fails.  TSP automatically triggers a rollback. This failure is only raised by backends that do not support a two-phase commit protocol.

\end{description}


\subsection{Operations on Store Objects}

TSP provides two different operations to create array objects and five 
operations to update and retrieve data from array objects.  For each of 
these operations there exists an equivalent operation on byte array 
objects.  The signatures of these operations look as follows:

\begin{xple}
tsp\_OID 
   tsp\_newArray(tsp\_Store s, tsp\_Format f, tsp\_Word nSlots);
tsp\_OID 
  tsp\_newArrayInit(tsp\_Store s, tsp\_Format f,
                         tsp\_Word nSlots, tsp\_Word wInit); 
tsp\_Word 
   tsp\_getWord(tsp\_Store s, tsp\_OID array, tsp\_Word iIndex); 
\k{void} 
  tsp\_setWord(tsp\_Store s, tsp\_OID array, tsp\_Word iIndex,
                   tsp\_Word w);
\k{void} 
   tsp\_getWords(tsp\_Store s, tsp\_Word nWords, tsp\_OID array, 
                    tsp\_Word iStart, tsp\_Word *pwBuffer);
\k{void} 
    tsp\_setWords(tsp\_Store s, tsp\_Word nWords, tsp\_OID array, 
                     tsp\_Word iStart, tsp\_Word *pwBuffer);
\k{void} 
   tsp\_moveWords(tsp\_Store s, tsp\_Word nWords,
                        tsp\_OID oidFrom, tsp\_Word iFromStart,
                        tsp\_OID oidTo, tsp\_Word iToStart);
\end{xple}

Note that TSP provides built-in block move operations between persistent 
objects as well as between persistent objects and main memory data structures. 

TSP also provides a set of operations that are applicable on all objects 
(arrays and byte arrays).  The operation \p{tsp\_nSlots} returns the number 
of slots of an object.  The returned value does not reflect the allocation 
size because the slot size of array objects and byte array objects are 
different.
   
For the efficient implementation of some higher-level dynamic data 
structures,  TSP exports the operation
\begin{xple}
tsp\_OID tsp\_resize(tsp\_Store s, tsp\_OID oid, tsp\_Word nSlots); 
\end{xple}
which changes the number of slots of an object.  Some store implementations 
support object resizing without restrictions.  In this case, the returned 
object identifier is equal to the object identifier \p{oid} passed as an 
input parameter.  If a store does not support growing or shrinking of 
objects, a new object with a fresh identifier is returned.  In this case, 
\p{tsp\_resize} is an efficient execution of the operation sequence to 
create a new object and to copy the slot values and the header information 
from the old object into the new object.

The format of an object as well as its mutability state can be retrieved 
and and changed by the following operations:
    \begin{xple}   
tsp\_Format tsp\_getFormat(tsp\_Store s, tsp\_OID oid); 
\k{void} tsp\_setFormat(tsp\_Store s, tsp\_OID oid, tsp\_Format f); 
tsp\_Bool tsp\_isImmutable(tsp\_Store s, tsp\_OID oid); 
\k{void} tsp\_setImmutable(tsp\_Store s, tsp\_OID oid); 
\end{xple}
While it is possible to dynamically change the format of an object, the 
mutability state of an object can be changed only once from mutable to 
immutable.


\subsection{Main Memory Mapping of Store Objects}\label{MainMemory}

For some applications, like the implementation of string operations, the 
procedure call and addressing overhead incurred by repeated calls to object 
level operations as described in the previous section cannot be tolerated.  

\begin{figure}[ht]
\begin{center} \leavevmode
\epsfxsize=8cm
\epsffile{Space.ps}
\end{center}
\caption{Storage Hierarchy and Object Identification}
\label{Fig:StoreHiera}
\end{figure}

Therefore, TSP provides three additional operations \\(\p{tsp\_openReadLock}
and \p{tsp\_openReadWriteLock} and \\
\p{tsp\_openRead}) to support fast object access.  Each of these
operations returns the address of a main memory representation of an
object (see figure ~\ref{Fig:StoreHiera}).  The client can use the return value as a pointer to an array
of \p{tsp\_Tagged} or \p{tsp\_Word} values if the object is an array,
or as a pointer to an array of \p{tsp\_Byte} values if the object is a
byte array.  Any open object must be closed explicitly using the
operation \p{tsp\_close} before calling \p{tsp\_prepareCommit}.  This
deliberate restriction on the use of open objects greatly simplifies
the implementation of TSP store adaptors while preserving much of the
usefulness of main memory mapping.

If a persistent storage server support direct object access via main memory 
addresses, no main memory copy of an object has to be created to implement 
the \p{tsp\_open} operations.  Otherwise, a main memory copy is created by 
an intermediate layer of the TSP architecture.  If \p{tsp\_open} routines 
are called several times for the same object, TSP returns the same address 
on each call.  It is not allowed to update an open object via TSP 
operations using its object identifier.  Again, this design decision was 
made deliberately, balancing the complexity of TSP implementations against 
the additional burden put on TSP clients.

\subsection{Management of Object Identifiers} \label{ManageId}

A TSP client is allowed to store object identifiers in state variables 
outside the persistent store.  As mentioned already in section~\ref{StructObj}, 
object identifiers are mutable.  More specifically, they can be changed by 
a TSP implementation during the execution of \p{tsp\_gc} (explicit garbage 
collection), \p{tsp\_prepareCommit}, \p{tsp\_commit} and 
\p{tsp\_rollback}. Furthermore, an object creation operation 
(\p{tsp\_new\ldots}) can also trigger an implicit garbage collection.

TSP provides a mechanism to automatically remap modified object identifiers 
held outside the persistent store.  To make use of this mechanism, a client 
has to implement a function that enumerates all relevant object 
identifiers.  This client-defined function has to be installed explicitly
each time a store is opened (\p{tsp\_setEnumerator}). The type of an 
enumerator function and its argument function is given by the following 
type definitions:

\begin{xple}
\k{typedef} tsp\_Tagged (*tsp\_VisitFunction)
                       (tsp\_Store s, tsp\_Tagged tagged); 
\k{typedef} \k{void} (*tsp\_EnumFunction)
                       (tsp\_Store s, tsp\_VisitFunction visit);
\end{xple}

The argument function \p{visit} is provided by a TSP backend.  It 
maps old object identifiers to new object identifiers.  A simple example of 
a client-defined enumerator function for an OID buffer is given below:
      
\begin{xple}
tsp\_Tagged oidBuffer[10]; 
\k{void} enumerate(tsp\_Store s, tsp\_VisitFunction visit)
\{  \k{int} i = 0; 
    \k{for}(; i$<$10; i++) oidBuffer[i] = visit(s, oidBuffer[i]);\} 
\end{xple}

The client-defined enumerator must not call TSP functions recursively.

A similar communication mechanism from the TSP backend to its client 
exists to notify a client prior to an implicit or explicit garbage 
collection:
\begin{xple}
\k{typedef void} (*tsp\_GcHandler)(tsp\_Store s); 
\k{void} tsp\_setGcHandler(tsp\_Store s, tsp\_GcHandler handler); 
tsp\_GcHandler tsp\_getGcHandler(tsp\_Store s);
\end{xple}

The garbage collection handler of a newly created or opened store is 
initialized with the function \p{tsp\_garbageCollect}.  It can be 
overridden by the TSP client, for example, to close all open objects to 
improve the efficiency of the garbage collector or to display messages in 
an interactive application.  Clients have to be aware that nested object 
creation operations may fail with an \p{tsp\_Failure\_STORE\_FULL} 
exception.


\subsection{Linearization of Object Store Subgraphs} 
\label{linear}

As mentioned already in section~\ref{ScaleSys}, the external data representation 
TXR enables data exchange between arbitrary TSP stores.  The operation 
\p{tsp\_extern} transforms an object graph into a linear byte stream.  Such 
a byte stream can be parsed with the operation \p{tsp\_intern} to recreate 
an isomorphic object graph (object cycles and shared objects are 
preserved). The signatures of these TSP functions are defined as follows:

\begin{xple}
tsp\_Word tsp\_extern(tsp\_Store s, tsp\_Tagged tagged, 
                            \k{void} *handle, tsp\_WriteFunction wr);
tsp\_Tagged tsp\_intern(tsp\_Store s, \k{void} *handle, 
                             tsp\_ReadFunction rd); 
\end{xple}

The stream functionality is factored out from the TSP by passing functions 
of type \p{tsp\_WriteFunction} and \\ \p{tsp\_ReadFunction}, respectively, 
as function arguments to the \p{intern} and \p{extern} algorithms.
\begin{xple}
\k{typedef} tsp\_Word (*tsp\_WriteFunction)(\k{void} *handle, 
                           tsp\_Byte *pbBuffer,tsp\_Word nBytes);
\end{xple}
A \p{tsp\_WriteFunction} is similar to the C low level \p{write} function defined on 
files.  It takes a pointer to a buffer of bytes (\p{pbBuffer}) and writes 
\p{nBytes} starting at position \p{*pbBuffer} to the stream 
identified by \p{handle}.  A write function has to return the number of 
bytes that have been successfully written.

\begin{xple}
\k{typedef} tsp\_Word (*tsp\_ReadFunction)(\k{void} *handle,
                           tsp\_Byte *pbBuffer, tsp\_Word nBytes);
\end{xple}
The semantics of a \p{tsp\_ReadFunction} is similar to the Unix \p{read} 
function defined on files.  It takes a pointer to a buffer of bytes 
(\p{pbBuffer}) and reads \p{nBytes} from the stream identified by 
\p{handle} into the buffer.  A read function has to return the number of 
bytes successfully read.

In order to introduce client-defined linearization algorithms for 
client-defined atomic data values (identified by user-defined tags) or 
client-defined subtypes of array and byte array store objects (identified 
by user-defined format values), clients can use the following TSP types and 
TSP functions: 
\begin{xple}         
\k{typedef} tsp\_Word (*tsp\_ExternHandler)
          (tsp\_Store s, tsp\_XDR xdr, tsp\_OID oid, 
          \k{void} *handle, tsp\_WriteFunction wr);
\k{void} tsp\_setExternHandler(tsp\_Store s, 
          tsp\_ExternHandler externHandler); 
tsp\_ExternHandler tsp\_getExternHandler(tsp\_Store s); 

\k{typedef} tsp\_OID (*tsp\_InternHandler)
           (tsp\_Store s, tsp\_XDR xdr, tsp\_Tagged taggedMeta,
              tsp\_Format f, tsp\_Bool fImmutable, tsp\_Word nSlots,
          \k{void} *handle, tsp\_ReadFunction rd);
\k{void} tsp\_setInternHandler(tsp\_Store s, 
          tsp\_InternHandler internHandler); 
tsp\_InternHandler tsp\_getInternHandler(tsp\_Store s); 
\end{xple}

The extern handler is called by a TSP implementation for each 
store object to be linearized while the intern handler is called to 
create a new object based on its header information and the contents of a 
stream. 

Finally, some TSP extensions require a client-defined processing to be 
performed on each newly created object during \p{intern} operations, for 
example, to perform authentication checks in a distributed system. These 
checks can be installed as an \p{internVisit} operation for an individual 
store:
\begin{xple}
\k{typedef void} (*tsp\_InternVisit)(tsp\_Store s, tsp\_OID oid);
\k{void} tsp\_setInternVisit(tsp\_Store s, tsp\_InternVisit visit); 
tsp\_InternVisit tsp\_getInternVisit(tsp\_Store s); 
\end{xple}

\section{Experience with TSP Implementations}\label{experience}

In this section we report on our experience in implementing TSP backends by 
adaptors to existing object stores and extending the TSP functionality 
systematically by TSP\\-compliant layers.

In addition to the store adaptors described in the following subsections, 
our group at Hamburg University implemented two stand-alone object stores, 
called \p{Tymem} and \p{Tysin} that realize TSP with different performance 
characteristics.  Both implementations are written in C and can be compiled 
on Unix, Linux, Windows, OS/2 and Macintosh OS platforms.

\p{Tymem} is a fast single user, main-memory based implementation of TSP 
biased towards applications that perform complex computations on rather 
small (up to 32MB) stores.  The operation \p{tsp\_commit} dumps the linear 
address space to a file and \p{tsp\_openStore} reads the whole persistent 
store into main memory.  Therefore, the size of a \p{Tymem} store is 
limited by the available virtual memory.

\p{Tysin} is a single user, disk-based store that performs data exchange 
between main and secondary memory on a segment basis.  That is, on an 
object fault only the store segment(s) the persistent object resides in are 
brought into main memory and a \p{commit} only writes newly created or 
modified segments to secondary memory.  Another difference between the two 
stores is the fact that \p{Tymem} garbage collects the whole object store 
on each invocation while \p{Tysin} limits most garbage collections to 
uncommitted store segments.  Generally speaking, \p{Tysin} 
outperforms \p{Tymem} in all persistent applications that only work with a 
limited subset of the full persistent store.  Furthermore, \p{Tysin} is 
also suitable for machines with poor virtual memory management support 
(like PC or Macintosh computers).

\subsection{TSP Store Adaptors}

The purpose of a store adaptor is to implement the functionality defined by 
TSP using the operations and data modeling features offered by a specific 
storage system.  Our group has developed object store adaptors for the 
object oriented database system ObjectStore from Object Design 
\cite{LLOW91} and for the proprietary object store of the University of 
St.\ Andrews \cite{Brow89,BrMo91,B*92,Munr93} also used by the Napier88 
\cite{DCBM89} system.  The University of Pisa is implementing a store 
adaptor for the O$_2$ \cite{BDK92,CDKK85} object-oriented database engine.  
The following two subsections give a brief implementation overview of the 
existing TSP adaptors.

\subsubsection{The ObjectStore Adaptor}

ObjectStore poses very few restrictions on the kind of C++ or C values that 
can be stored persistently, for example, instances of classes, integers, 
strings, arrays and union typed values can be made persistent.  ObjectStore 
supports object identification \cite{OS93} through reference classes as 
well as through virtual memory addresses.  The current ObjectStore adaptor 
uses the virtual address object identification scheme, i.e.  values of type 
\p{tsp\_OID} are virtual memory addresses valid in a single ObjectStore 
session.  We now show how these ObjectStore features are used to implement 
the two basic TSP storage structures of polymorphic array and byte array 
objects.

A TSP (byte) array object is mapped to a C array with elements of type 
\p{tsp\_Word} (\p{tsp\_Byte}) preceded by a fixed-sized header. 

The TSP type \p{tsp\_Tagged} is mapped to an ObjectStore union type \p{Poly} defined as 
follows:

\begin{xple}
\k{union} Poly \{ tsp\_Immediate immediate; Poly *obj;\}
\end{xple}
Such a polymorphic value is either an immediate value or the address of another 
ObjectStore object.  An array object with format \p{tsp\_Format\_TAGGED} is mapped to an array of \p{Poly} values.  At runtime, the memory 
mapping mechanism of ObjectStore must be able to differentiate between 
virtual memory addresses and immediate values to change virtual 
addresses within objects in case the mapping of persistent objects into main memory has to be changed.  Therefore, 
a user-defined discriminant function has to be associated with the 
user-defined union type \p{Poly} that inspects the actual value of the union typed value at runtime and tells ObjectStore which type it is, \p{tsp\_Immediate} or  \p{Poly*}.  The TSP discriminant function is give below.

\begin{xple} 
tsp\_Word Poly::discriminant( )\{ 
   \k{if} (IS\_IMMEDIATE(imm)) \k{return} 1; \k{else return} 2; \} 
\end{xple}

The value returned by the function is an integer indicating the union's 
active field (1 for the first field and 2 for the second field).  The 
implementations of the object operations of TSP are obvious given the above 
information.  ObjectStore has no builtin garbage collector.  Therefore, the 
TSP adaptor contains a copying garbage collector that is based on the 
possibility to structure ObjectStore databases into partitions.

\subsubsection{The Napier Store Adaptor}

The stable heap concept of the Napier Object Store is quite similar to the 
untyped TSP store model.  A Napier store object is divided into three parts; an 
object header, an identifier and a data part.  All object references must 
be stored in the identifier part.  In addition, the client can store tagged 
immediates within the identifier part.  The data part can be used to store 
data of any type.  Thus, a TSP object, its header and the data part, are 
mapped to the identifier and data part of a Napier Object Store object.  
TSP does not separate object identifiers and immediate values.  Therefore, 
all TSP client values must be stored in the tagged format.  The minor 
difference of the two object concepts eases the implementation of the TSP 
object operations.  For example, the read and write operations of TSP 
directly call the read and write operations of the Napier Object Store.  
Only the offsets of the addressed data items must be adapted.
 
The Napier Object Store uses a mechanism to handle cached object 
identifiers that is different from the TSP mechanism described in 
section~\ref{MainMemory}.  The client of a Napier Object Store has to install a 
\e{save} functions that is called before garbage collecting or stabilizing 
the store and a \e{restore} function that is called after these store 
activities.  The purpose of these functions is to write identifiers to the 
store before store activities modify these object identifiers and to read 
the possibly changed object identifiers back into the cache after garbage 
collection and stabilization.  The store adaptor maps the enumeration 
mechanism of TSP to the \e{save/restore} mechanism.  This is done by 
implementing two \p{visit} functions passed as an argument to the TSP 
client enumerator function.  This enumerator function is called prior to a 
stabilization/garbage collection with the visit function \p{visitSave}, 
that writes all cached object identifiers to a pre-created object in the 
Napier Object Store.  After a stabilization/garbage collection the 
enumerator function is called with a visit function \p{visitRestore} that 
reads the possibly modified object identifiers back into the cache.  
Furthermore, the store adaptor implements a mechanism to correctly handle 
open objects (see section~\ref{ManageId}) before and after garbage collection.

\subsection{Extending the TSP Functionality}

TSP has been designed to provide a standardized access to the core 
functionality of persistent stores.  Systems where an extended 
functionality is required can enhance the TSP by additional operations.  
Some of these enhancements can be implemented in a way that does not depend 
on specific properties of the backend.  In this case, the resulting 
software layers can be reused for multiple TSP stores. At Hamburg 
University, we have experimented with three such TSP extensions.

The first extension adds \e{persistent savepoints} to TSP by 
re-implementing the basic TSP operations and adding operations to rollback 
to a named savepoint.  This feature makes it possible to structure 
long-running transactions in a way that simplifies application-controlled 
recovery.  By rolling back to a named savepoint, the effects of a 
transaction on a persistent store are undone only partially.  The store is 
responsible for keeping the necessary recovery logs and to re-establish the 
object store state of a specific savepoint. 

The second extension adds \e{access control} on TSP objects.  The security 
layer checks for each TSP operation whether a specific user has the right 
to perform this operation on a given persistent object.  The underlying 
generic authorization scheme can be configured by clients of the security 
layer.  The implementation utilizes callbacks and (optional) persistent 
access control structures attached to individual TSP objects.
  
A third extension provides \e{NFS access} to object stores by implementing a 
standard network file system (NFS \cite{NFS90}) server using TSP operations.  
This server can be ``mounted'' directly by most commercial operating 
systems (Unix, MS-Windows, Macintos OS etc.).  The NFS/TSP gateway maps
operating systems files and directories directly and efficiently 
onto TSP store objects.  This way, any tool that operates on operating 
system files, for example a text editor, an audio recorder or an image 
browser, can be used to access ``exported '' object store objects.  Files 
managed by this NFS/TSP gateway can be manipulated through NFS file 
operations and TSP operations simultaneously.  In particular for large 
multi-media objects, file access to recoverable persistent store objects 
is of high practical relevance.

%------------------------------------------------------------------------------

\section{Concluding Remarks}

The main contribution of this paper is the in-depth description of an 
object store protocol that we regard as an excellent starting point for a 
\e{standardized} interface between the frontend and the backend of fully 
integrated persistent environments.  In developing the TSP specification, its 
single-user implementations and its adaptors to commercial object stores 
available to other research groups, we hope to establish TSP as a widely 
accepted protocol within persistent language implementations.  This would 
not only simplify the development of new persistent languages but also 
facilitate system measurements, comparative performance studies and 
interoperability experiments between multiple persistent languages.

\nocite{CMMSS94}
\bibliographystyle{florian}
{\small
\bibliography{/users/dbis1/matthes/txt/bib/florian-macros,/users/dbis1/matthes/txt/bib/florian}
}
\end{document}

