Version 0.1
The Shore Project Group
Computer Sciences Department
UW-Madison
Madison, WI
Thu Nov 3 14:14:46 CST 1994
Shore (Scalable Heterogeneous Object REpository) is a new persistent object system under development at the University of Wisconsin that represents a merger of object-oriented database (OODB) and file system technologies. While the past few years have seen significant progress in the OODB area, most applications (and application areas) have not chosen to leave file systems behind in favor of OODBs. We feel that more applications could benefit from OODB support, but are impeded by limitations in current technology.
The goal of the Shore project is to provide a system that addresses these issues, thereby enabling ``holdout'' applications to finally move their data (incrementally) out of files and into a modern persistent object repository. We also expect many current OODB clients to find Shore to be an attractive alternative.
Many of us were involved in an earlier object-oriented database effort called EXODUS [CDF+86]. Version 3.0 of EXODUS provides a client-server architecture with page-level locking, log-based recovery based on the ARIES algorithm [FZT+92], and support for multiple servers and distributed transactions. The EXODUS package includes the E programming language [RCS93], a variant of C++ that supports convenient creation and manipulation of persistent data structures. The functionality, performance, robustness, and low cost (free!) of EXODUS has made it a popular piece of software. EXODUS and its associated toolkit have been used in several projects at Wisconsin and elsewhere. Over 350 different groups from over 30 countries have taken copies of it from our ftp site, it is used as the storage manager in the TI Open Object-Oriented Database System, it serves as the storage engine for at least one commercial product (MediaDB, a recently announced multi-media DBMS), and it has been shown to have commercially competitive performance on an OODBMS benchmark [CDN93]. Nonetheless, EXODUS suffers from several limitations shared by many current persistent object stores. An exploration of these limitations may help to explain the motivation for Shore.
EXODUS storage objects are untyped arrays of bytes; correct interpretation of their contents is the responsibility of application programs. Although E allows instances of any C++ type to be stored in the database, no type information is stored. This ``compile-time'' approach to data types has several disadvantages including the following:
A second limitation of the EXODUS storage manager (ESM) is its client-server architecture. Users have constructed database servers or object servers as EXODUS client processes, leading to the ``client-level server'' problem illustrated in Figure 1. Even a query-shipping (as opposed to data-shipping) SQL server would be difficult construct efficiently with the existing software base. In contrast, a more open architecture would have allowed clients to customize the ESM server process directly. The ESM process architecture also fails to support a clean mapping onto parallel processors such as the Intel Paragon or IBM SP/2. Although one could simply run an EXODUS server on each node with mass storage attached, support for distributed transactions is not sufficient; efficient parallelism also requires the availability of extensive server-to-server communication facilities.
A third limitation of EXODUS is its lack of support for access control. As with other aspects of the system, our original thinking was that different clients might wish to implement very different protection models, and thus we provided no built-in protection support. Furthermore, EXODUS allows client processes to manipulate objects directly in cached copies of database pages, so an errant pointer can destroy not only client data but also metadata, rendering the entire database unusable. The original design of EXODUS envisioned client processes as being database systems and object servers (i.e., other trusted software layers). Shore aims to support environments in which a single storage volume may be shared by mutually mistrusting applications.
Finally, while EXODUS objects are similar to Unix files (they are untyped sequences of bytes), the interface for manipulating them is completely different. As a result, existing applications built around Unix files cannot easily use EXODUS.
The design of Shore strives to retain the good features of the EXODUS Storage Manager (such as transactions, performance, and robustness) while eliminating some of these limitations.
Each object in Shore contains a pointer to a type object that
defines its structure and interface.
The
Shore Data Language
provides a single
language-neutral notation for describing the types of all persistent
data
Shore's process architecture is different from that of EXODUS in two
key ways. First, Shore has a symmetric, peer-to-peer
structure.
Every participating processor runs a Shore server process regardless whether
it has local disks. A client process interacts with Shore by communicating
with the local Shore server (see
Figure 2
).
The design is scalable; it can run on a single
processor, a network of workstations, or a large parallel processor
such as the Intel Paragon or IBM SP/2. (For more on parallel Shore,
the reader is referred to [DNSV94]).
Second, Shore supports the notion
of a ``value-added'' server. The server code is modularly constructed
to make it relatively
simple for users to build application-specific servers without facing
the ``client-level server'' problem. For example, the Paradise
project [DLPY93] is already using the Shore
storage manager to build a geographic information system.
Finally, Shore is intended to be much more of a complete system than ESM. In addition to a more flexible process structure and support for typed objects, Shore provides other services that end users should find attractive, including a name space and access-control model similar to Unix, a Unix-compatible interface for legacy software tools, openness in the area of language bindings, and traditional database services such as associative data access, indexing, and clustering.
The remainder of this document is organized as follows. Section 2 provides an overview of the services provided by Shore, including both its file system and database features. The Shore process architecture is described in Section 3. Section 4 describes the state of the system's various features as of the Shore alpha release. Finally, we conclude in Section 5. The software described here is not simply ``paperware.''
As a hybrid system, Shore may be described as a file system augmented with database features or a DBMS with file-system features. In this section, we will describe the basic features of Shore, explaining how it combines important ideas from these two areas in order to arrive at a system capable of addressing the variety of application requirements discussed in the introduction.
Shore is a collection of cooperating data servers, with each data server containing typed persistent objects. To organize this universe of persistent Shore objects, a Unix-like name space is provided. As in Unix, named objects can be directories, symbolic links, or individual (typed) objects (the counterpart of Unix ``plain'' files). Unlike Unix, Shore allows each object to be accessed by a globally unique Object Identifier (OID) that is never reused. Shore also introduces a few new types of objects, including types and pools, as described in more detail in Section 2.3.
The type system for Shore objects is language-neutral, supporting applications in any programming language for which a language binding exists. For objects whose primary data content is textual or untyped binary data, Unix file system calls are provided to enable legacy applications (such as existing language compilers or CAD tools) to access their data content in an untyped manner. Shore is structured as a peer-to-peer distributed system; each node where objects are stored or where an application program wishes to execute contains a Shore server process that talks to other Shore servers, interfaces to locally executing applications, and caches data pages and locks in order to improve system performance.
The Shore object model, like many database object models, consists of objects and values. Every persistent datum in Shore is an object, and each object has an identity denoted by a unique object identifier or OID. Structurally, an object is a container for a value; the value can be simple or structured, and may include references to (typed OIDs of) other objects. Every value has a type, as does every object. Behaviorally, each object has a set of methods through which its contents can be accessed and manipulated. The internal structure and methods available for a given object are dictated by the object's type, referred to as its interface type, and every Shore object is tagged with a reference to a type object that captures this information.
A Shore object is much lighter-weight than a Unix file, but it may still be
too heavy to support fine-grained data structures that are customarily
represented as linked lists, trees, or other graph structures in
non-persistent programs.
To support the flexibility of dynamic structures with the efficiency of
(logically) contiguous blocks on secondary storage, Shore allows each
object to be extended with a variable-sized heap
(see
Figure 3
).
The core of an object is described by its type.
The heap is used by the system to store variable-sized components of its
value such as strings, variable arrays, and sets. The heap can also
contain dynamic values which are similar to ``top-level'' objects,
but do not have independent identity (for example, when the object is
destroyed, all of its dynamic values are destroyed as well).
Dynamic values can be linked together with local references,
which are stored on disk as offsets from the start of the heap, but are
swizzled in memory to actual memory addresses. The O2 commercial
OODBMS [Deu91]
provides a related facility with its objects/values distinction;
the main difference is that in O2 the encapsulated values must form a
set, list, or array, whereas in Shore the heap can contain an arbitrary
data structure. With demand-paging support for very large
objects, each object heap closely resembles a small
Object Store database [LLOW91]
From a file system standpoint, Shore provides two major services. First, to
support object naming and space management in a world with many persistent
objects, Shore provides a flexible object name space. Second, to enable legacy
Unix file-based applications to continue to exist while new Shore applications
are being developed, mechanisms are provided that permit Shore object data to
be accessed via Unix file system calls.
Shore provides a tree-structured, Unix-like name space in which all
persistent objects are reachable, either directly or indirectly, from a
distinguished root directory. By
doing so, Shore gives users a framework in which to
register both individual persistent objects and the roots of
large persistent data structures, a framework that provides a much
richer naming environment than the single-level ``persistent root''
directory found in EXODUS and most other current OODBs. The realization of this framework involves
extending the set of familiar Unix object types (directories,
symbolic links, and ``regular files'') with cross references,
pools, modules, and type objects.
Shore directory objects provide the same facilities as Unix directories.
Familiar Unix concepts such as path name, subdirectory, parent directory,
link (both hard and symbolic), and
root directory are all defined as they are in Unix [RT74]. As in Unix,
a directory is a set of < name, OID > pairs.
The OID can refer to any other Shore object, but the system maintains
the Unix invariant that the set of directories forms a single rooted tree.
Directories and the objects they contain are called registered objects.
Each registered object contains a set of system properties, which are
a superset of the Unix attributes:
ownership, access permissions, and time stamps.
To support lighter-weight objects,
Shore introduces a new kind of (registered) object called a
pool.
Members of a pool, called anonymous objects, are clustered
near each other on disk and share most of the Unix attributes (ownership,
etc.) with the pool. Anonymous objects do not have path names, but they
can be accessed by OID like any other object. There is also an operation to
enumerate the contents of a pool (which can be accessed by OID or path name).
The registered property is orthogonal to type:
Any type of object can be created either in a pool (as an anonymous object)
or in a directory (as a registered object). We expect that in a typical
Shore database, the vast majority of objects will be anonymous, with a few
registered objects serving as roots or entry points to graphs of anonymous
objects.
To preserve the invariant that all objects are reachable from the root of the directory system, Shore imposes different deletion semantics on registered and anonymous objects. As in Unix, a registered object is not explicitly deleted; it is reclaimed by the system when its link count (the number of directory entries referring to it) drops to zero. An anonymous object can be deleted at any time, but a pool can only be deleted when it is empty. An OID is thus a ``soft'' reference, in that it may dangle if the object to which it refers is deleted. (Since OIDs are never reused, however, it will never accidentally capture a new object.) Since OIDs can be stored in the contents of arbitrary objects, any stronger integrity guarantee would be impractical to enforce.
Shore introduces three more fundamental kinds of objects,
modules, type objects, and cross references.
Modules and type objects are similar to pools and anonymous objects,
respectively, but have different deletion semantics to preserve the
existence dependency from objects to their types.
Cross references are similar to symbolic links in that they provide a
way to insert an alias for an object into the directory name space,
but look somewhat like hard links when used through NFS.
While a symbolic link contains a path name for a registered object,
a cross reference contains the OID of an arbitrary object.
Cross references, like symbolic links, are ``soft'' (permitted to dangle).
They are intended primarily for the Unix compatibility feature described in the
following section.
Figure 4 illustrates these concepts. The directory /u/smith contains the entries project, doc, and pool1, referring to another directory, a cross reference, and a pool, respectively. The registered object /u/smith/project/entries contains pointers to members of pool1. It might be some sort of application-defined ``directory'' of entry points to a data structure. The symbolic link /u/smith/project/README is an alias for the cross reference /u/smith/doc, which is itself an alias for a member of pool1. An attempt to access either of these path names through the Unix compatibility interface will resolve to that anonymous object.
While Shore provides a much richer environment than traditional file systems, there are many situations where tools designed to be used on files need to be invoked on database objects. A typical example is provided by the CAPITL project [AS93], which uses EXODUS. CAPITL improves on current software-development environments by maintaining a rich set of attributes and relationships for each object in its repository (program sources, object files, specifications, documents, etc.) It represents each object as a directed graph, with intra- and inter-object links represented by OIDs. While tools developed as part of CAPITL take full advantage of this rich structure, it is occasionally necessary to invoke existing tools such as compilers or editors on objects stored in the database. Three possible approaches were to rewrite the tools to access CAPITL objects, to copy the contents of an object to a file before operating on it (and copy back the results), or to keep the contents permanently in files, storing only metadata and file names in the CAPITL database. All of these approaches are unsatisfactory for various reasons. The solution found for CAPITL, which we have generalized and expanded in Shore, is to provide a special Unix compatibility feature. Each Shore object may optionally designate a range of bytes as its text field. A compatibility library provides versions of Unix system calls such as open, read, write, and seek, interpreting pathname arguments in the Shore name space and satisfying requests by fetching or updating the text field of objects. Registered objects without text fields behave like /dev/null (they read as zero length and ignore attempts to change them). Anonymous objects can be accessed via cross references.
For applications that cannot even be re-linked, we have constructed
an NFS file server [SGK+85]. An entire subtree of the Shore
name space can be ``mounted'' on an existing Unix file system. When
applications attempt to access files in this portion of the name space,
the Unix kernel generates NFS protocol requests that are handled by the
Shore NFS value-added server.
As we mentioned in Section 1.1, one important motivation for Shore was to rectify some of the shortcomings of EXODUS, many of which are shared by other existing object-oriented databases. Access control and name space limitations were addressed in the previous section. Process structure is addressed in Section 3. In this section we describe the design and implementation of the Shore type system and indicate how it supports hardware and language heterogeneity.
The Shore type system is embodied by the SHORE Data Language, SDL, the language in which Shore types are defined. SDL is quite similar in nature to the Object Definition Language (ODL) proposal from the ODMG consortium [Cat93], which is descended from OMG's Interface Description Language (IDL), a dialect of the RPC interface language used in OSF's Distributed Computing Environment (DCE). Our work on SDL started at roughly the same time as ODMG's work, and we also used OMG's IDL as a starting point. We have been following the development of ODL, but we had to proceed as well rather than waiting for ODMG to complete their work. (At this time, the ODMG standards are still only in the late paper design stage, and portions are not yet entirely clear or internally consistent.) The goals of ODMG are also somewhat different from ours. They concentrate on a standardized interface to existing C++ oriented OODBs, while our focus has been support for inter-language object sharing within a large name space of objects.
All objects are instances of interface types,
types constructed with the interface type constructor. Interface
types can have methods, attributes, and relationships. The attributes of
an interface type can be of one of the primitive types (e.g., integer,
character, real), or they can be of constructed types. Shore provides the
usual set of type constructors: enumerations, structures, arrays, and
references (which are used to define relationships). In addition, Shore
provides a variety of bulk types, including sets, lists, and
sequences, that enable a Shore object to contain a collection of references
to other objects. Finally, Shore provides the notion of modules, to
enable related types to be grouped together for name scoping and type
management purposes. To provide a brief taste of SDL,
Figure 5
shows how one of the OO7
benchmark [CDN93] types can be defined.
module oo7
{
const long TypeSize = 10;
enum BenchmarkOp { Trav1, Trav2a, Trav2b, etc };
// forward declarations
interface Connection; // connector for atomic parts
interface CompositePart; // container for atomic parts
interface PartIdSet; // really just a C++ class
interface AtomicPart {
public:
attribute long id;
attribute char type[TypeSize];
attribute long buildDate;
attribute long x, y;
attribute long docId;
relationship bag to inverse from;
relationship bag from inverse to;
attribute ref partOf;
void swapXY();
void toggleDate();
void DoNothing() const;
long traverse(in BenchmarkOp op, inout PartIdSet visitedIds) const;
void init(in long ptId, in ref cp);
void Delete();
};
// Connection, CompositePart, and other types go here
}
Shore is intended to allow databases built by an
application written in one language (e.g., C++) to then be accessed and
manipulated by applications written in other object-oriented languages as
well (e.g., CLOS). This capability will be important for large-scale
applications, such as VLSI CAD; C++ might be used for
efficiency in simulating large chips, while CLOS (or perhaps Smalltalk)
might be more convenient for writing the associated design-rule checking
and user interface code. In Shore, the methods associated with SDL
interfaces can therefore be written using any of the languages for which a
Shore language binding exists. Currently, only the C++ binding is
operational, so we will illustrate Shore's language binding concepts by
briefly discussing the Shore C++ binding.
An application, such as the OO7 benchmark, is created as follows.
The first step is to write a
description of the types in SDL. In our OO7 example, this description is
saved in a file called oo7.sdl. The next step is to use the SDL type
compiler to create type objects corresponding to the new types. The type
compiler is a Shore application that creates type objects from SDL
definitions.
A language-specific tool (in our case, sdlcxx) is then used
to derive a set of class declarations and special-purpose function definitions
from the type objects.
In our example, this generated code is placed in
two files: oo7.h, and oo7.C. The header file oo7.h is
included both in the C++ source files that supply the (application-specific)
implementation of member functions such as traverse and swapXY,
and in source files that manipulate instances of AtomicPart, etc.
The OID of the type object is compiled into these files and used to
catch version mismatches at runtime.
A fragment of the generated oo7.h file is shown in Figure 6. Some of the data member types in Figure 6 correspond directly to SDL types, as C++ (like most languages) offers direct support for those simple types. For Shore types with no corresponding C++ type, like sets and references, a language-appropriate presentation of the SDL type is generated. For C++, Shore presents references, sets, and other collection types using pre-defined, macro-based classes (similar to parameterized types) such as REF and BAG_INV_DECL in Figure 6. The class REF(CompositePart) encapsulates an OID; C++ overloading features make it behave like a pointer to a read-only instance of CompositePart. The class BAG_INV_DECL(Connection, ...) encapsulates a data structure containing a set of OIDs and provides member functions that enable its contents to be accessed; the _INV_DECLsuffix and other macro arguments enable the generated class to do its part in maintaining the inverse relationship declared in the SDL schema.
module oo7
{
const long TypeSize = 10;
enum BenchmarkOp { Trav1, Trav2a, Trav2b, etc };
// forward declarations
interface Connection; // connector for atomic parts
interface CompositePart; // container for atomic parts
interface PartIdSet; // really just a C++ class
interface AtomicPart {
public:
attribute long id;
attribute char type[TypeSize];
attribute long buildDate;
attribute long x, y;
attribute long docId;
relationship bag to inverse from;
relationship bag from inverse to;
attribute ref partOf;
void swapXY();
void toggleDate();
void DoNothing() const;
long traverse(in BenchmarkOp op, inout PartIdSet visitedIds) const;
void init(in long ptId, in ref cp);
void Delete();
};
// Connection, CompositePart, and other types go here
}
Given the header file generated by the binder, the application programmer can implement the operations associated with the OO7 interfaces. In the C++ binding, access to simple data members is provided safely through the use of several techniques. As mentioned above, REF-generated classes behave like read-only pointers, so information about an atomic part could be printed by a function as follows:
void printPart(REF(AtomicPart) p) {
cout << "Type " << p->ptype
<< " part at (" << p->x << ","
<< p->y << ")\n";
}
This function can directly access
the part_type, x, and y
data members of an atomic part, but it cannot update them. (Attempts to
do so would be flagged as an error by the C++ compiler.) Similarly, member
functions that do not update the contents of an object are flagged as const in their SDL definition, as illustrated in
Figure 5
(and attempts to call a non-const member function through a REF
are also caught by the compiler).
To modify an object, the C++ application must first call a special generated member function, update, which returns a read-write reference. For example, the following code fragment directly exchanges the x and y attributes of an atomic part:
REF(AtomicPart) p = ... ;
long tmp = p->x;
p.update()->x = p->y;
p.update()->y = tmp;
The function update coerces the type of p from
REF(AtomicPart) to (non const) AtomicPart *.
It also has the runtime effect of marking the referenced object as ``dirty''
so that changes will be transmitted to the server when the transaction
commits.
Since the member function swapXY is not declared to be const in
Figure 6,
another legal way to accomplish this exchange
would be to define this member function as follows:
void AtomicPart::swapXY() {
long tmp = x;
x = y;
y = tmp;
}
Given this definition, swapXY could then be invoked to do the
job.
REF(AtomicPart) p = ... ;
p.update()->swapXY();
The Shore C++ binding implements collection types similarly to C++ OODBs [Ver92][Ont92][Obj92][LLOW91]: A template type (in this case, one implemented via the use of C++ macros) such as BAG_INV_DECL(Connection, ...) in Figure 6 contains a member function get_elt that gets a specified element from the collection. For example, the printPart function could be extended to print an atomic part's outgoing connections as follows:
void printPart(REF(AtomicPart) p) {
cout << "Type " << p->ptype << " part at ("
<< p->x << "," << p->y
<< ") with outgoing connections\n";
int i;
REF(Connection) c;
for (c = to.get_elt(i=0); c != NULL; c = to.get_elt(++i)) {
c->print();
cout << endl;
}
}
Shore provides
support for concurrency control (via locking) and crash recovery (via
logging); these services are integrated with the support
for data caching described below. Shore will also
provide users with a choice of lower levels of consistency and recovery.
Details of these reduced levels are still being worked out.
Other Shore services will include optimized object queries over
bulk types (currently being implemented based on the OQL language, as
specified by ODMG [Cat93]) and a flexible, user-controllable notion of
``sticky'' object clusters to permit users to cluster and later recluster
related objects (also being designed and implemented currently).
Figure 2
in
Section 1.2
illustrates the process structure of Shore.
Shore executes as a group of communicating processes called SHORE
servers. Shore servers consist exclusively of trusted code,
including those parts of the system that are provided as
part of the standard Shore release, as well as code for
value-added servers.
that can be added by sophisticated users to implement
specialized facilities (e.g., a query-shipping SQL server) without
introducing the ``client-level server'' problem described earlier.
Application processes (labelled ``App'' in
Figure 2
manipulate objects, while servers deal primarily with fixed-length
pages allocated from disk volumes, each of which is
managed by a single server.
Applications are not trusted, in the sense that a buggy or malicious
application can only modify objects that it is authorized to access; in
particular,
it cannot corrupt metadata such as slot tables, indexes, or the directory
structure.
Each Shore server plays several roles.
First, it is a page-cache manager. The cache may contain pages from
local volumes as well as pages from remote servers containing objects
that were requested by local client applications.
Second, the server acts as an agent for local application processes.
When an application needs an object, it sends an RPC request to
the local server, which fetches the necessary page(s) and returns the object.
(More details are provided in the following section.)
Finally, the Shore server is responsible for concurrency control and recovery.
A server obtains and caches locks on behalf of its local clients.
The owner of each page (the server that manages its volume) is
responsible for arbitrating lock requests for its objects, as well as
logging and committing changes to it.
Transaction management is described in more detail below.
This process structure provides a great deal of flexibility. When acting as an owner of a page, the Shore server performs the role of the server in a traditional data-shipping, client-server DBMS; when acting as the agent for an application, it plays the role of client. Letting the Shore server assume both roles allows data placement to be optimized according to workload. For example, data that is largely private to a single user could be owned by the Shore server on that user's workstation. The location-transparency (from the application's viewpoint) provided by the caching-based architecture allows an application on such a workstation to access both local and remote persistent data in an identical manner. Furthermore, the ability to cache pages at the local server can greatly reduce any observed performance penalty for accessing remote data. In Figure 2, applications running on Workstation 2 can access data that is largely private through the local Shore server, while obtaining other shared data from the other Shore servers. With a query-shipping architecture implemented by a ``higher level'' value-added server (such as an SQL server), applications would communicate directly with remote servers.
Figure 7 depicts the components of the Shore software linked with each application. When the application attempts to dereference an ``unswizzled'' pointer, the language binding generates a call to the object-cache manager (OC) in the language-independent library (LIL).
If the local operating system supports shared memory, the server uses
it to deliver a page of objects to the LIL more quickly.
To avoid paging, the object cache manager locks the cache in memory
and uses LRU replacement if it grows too large.
All OIDs in the cache are swizzled to point to entries in an
object table. This level of indirection allows objects to be removed
from memory before the transaction commits, without the need to track down
and unswizzle all pointers to them.
The LIL also contains the Unix compatibility library, with procedures that
emulate common file system calls such as open, read, and seek.
Finally, the LIL is responsible for
authenticating the application to the server using
the Kerberos authentication system [MNSS87].
Figure 8 shows the internal structure of the Shore server in more detail. It is divided into several components, including the Shore Value-Added Server, which communicates with applications, and the Shore Storage Manager (SSM), which manages the persistent object store.
The Shore Value-Added Server (SVAS) is responsible for providing access to Shore objects stored in the SSM. It manages the Unix-like name space and other structures described in Section 2.3. When an application connects with the server, the server associates Unix-like process state (such as a user ID and current directory name) with the connection. User ID information is checked against registered objects when they are first accessed to protect against unauthorized access. As in Unix, the current directory name information provides a context for converting file (path) names into absolute locations in the name space.
The SVAS is one example of a value-added server. Another value-added server is the NFS server described in Section 2.3.2. Each value-added server provides an alternative interface to the storage manager. They all interact with the storage manager through a common interface that is similar to the RPC interface between application processes and the server. A goal of Shore is to make it possible to debug a new value-added server as a client process and then migrate it into the server for added efficiency when it is completely debugged.
Another example of a value-added server could be an SQL
server that provides a query-shipping
interface to a relational database.
Below the server interface lies the Storage Manager. As shown in Figure 8, the SSM can be viewed as having three sub-layers. The highest is the value-added server-to-SSM interface, which consists primarily of functions to control transactions and to access objects and indexes. The middle level comprises the core of the SSM. It implements records, indexes, transactions, concurrency control, and recovery. At the lowest level are extensions to the core that implement the distributed server capabilities described in Section 3.1. In addition to these three layers, the SSM contains an operating system interface that packages together multi-threading, asynchronous I/O, and inter-process communication.
A detailed description of the storage manager is beyond the scope of this document. However, in this subsection we highlight three of the important technical issues that arise in its implementation: cache consistency, transaction management, and object identifier implementation.
In Shore, there are two types of caches-the object caches used by
applications and the page caches maintained by Shore servers. These
two types of caches are managed very differently. The Shore servers'
page caches are allowed to retain their contents across transaction
boundaries (called inter-transaction caching). Cache
consistency is maintained through the use of a callback locking
protocol [FC92][WR91][LLOW91][HMN+88].
The application/server interface, however does not support ``upcalls.''
Requiring application processes to respond to remote procedure calls
would interfere with other synchronization mechanisms used by many
application programs such as threads packages, graphics (X11 or InterViews),
and networking interfaces. Therefore, the object cache is invalidated
(and locks are released) at the end of a transaction.
We plan to explore techniques to extend the use of
the object cache across transaction boundaries later in the Shore project.
To balance efficiency against the need for fine-grain concurrency,
Shore uses an adaptive version of callback locking that
can dynamically adjust the granularity (e.g., page vs. object)
at which locking is performed depending on the presence of data
conflicts [CFZ93]. This adaptive algorithm is based on the
notion of lock de-escalation [Jos91][LC89].
When an application wishes to commit a transaction, a commit request is sent to its local server. If the transaction has modified data that is owned by multiple servers, then a two-phase commit protocol is used among the relevant servers. If the local server has a log, it will coordinate the distributed commit protocol; otherwise, it will delegate the coordinator role to another server. Transactions that only access data that is owned by the local server can commit locally. Thus, the peer-to-peer architecture incurs the additional overhead of distributed commit only when it is necessary.
The transaction rollback and recovery facilities of Shore are based on
the ARIES recovery algorithm
[MHL+92] extended for the
client-server environment of Shore. The client-server distinction
reflects the roles played by the server with respect to an object. A
server that owns an object is the one that stores the log for that
object and that performs all recovery operations on the object.
Servers caching the object behave as clients and generate log records
that are shipped to the owner of the object. The initial server-to-server
implementation of Shore relies on a simple extension of ARIES that we
call redo-at-server. In this extension, a client never ships
dirty pages back to the server, only log records; when the server receives
log records from a client, it redoes the operations indicated by the log
records. This is easy to implement, and it has the advantage of eliminating
the need to send dirty pages back to the server.
The primary disadvantage is that the server may need to reread pages if
it has flushed them from its cache.
In the future, we plan to implement the
client-server extension to ARIES that was developed and implemented
for the EXODUS Storage Manager [FZT+92] and compare its
performance to our simpler redo-at-server implementation.
The implementation of object identifiers (OIDs) has a considerable impact on how the rest of an object manager is implemented and on its performance. The Shore Storage Manager uses two types of OIDs. A physical OID records the actual location of an object on disk, while a logical OID is position independent, allowing transparent reorganization such as reclustering. The higher levels of Shore (including the object cache manager) use logical OIDs to represent object references.
A logical OID consists of an 8-byte volume identifier and an 8-byte serial number. The former is designed to be long enough to allow it be globally unique, allowing independently developed databases to be combined. The latter is large enough to avoid reuse of values under any conceivable operating conditions. When an OID is stored on disk, only the serial number is recorded. The volume identifier is assumed to be the same as the volume containing the OID. For cross-volume references, the serial number identifies a special forwarding entry that contains the full OID of the object (the identifier of the volume that contains it and its serial number relative to that volume).
To map serial numbers to physical OIDs or remote logical OIDs, each volume contains a B+ tree index called its LID index. An in-memory hash table is used to cache recently translated entries. The server also eagerly adds translations to this per-transaction translation cache. For example, whenever a server receives a request for an object whose logical OID is not currently in the cache, it requests the page containing that object from the object's server. When that page arrives, the server enters mappings for all of the objects on that page into the translation cache. This technique effectively reduces the number of LID index accesses from one lookup per object to one lookup per page of objects.
As mentioned in footnotes sprinkled throughout this document, not all of the features of Shore are supported in the alpha release. The alpha release of Shore is intended for initial SDL-level application development work. As such, it does not include support for value-added-server writers. Also, applications are restricted to using a single server at this stage.
A long-term goal is that the Shore type system will reside in the server so that the server can make the strongest reasonable guarantees about the integrity of objects and their relationships. In the alpha release, however, the entire type system is encapsulated in the language binding generated from an SDL type description. Consequently, the alpha release of Shore makes no guarantees about the integrity of any objects other than fundamental file system objects, such as directories, symbolic links, and the like.
Shore is an integration of file system and OODB concepts and services. From the file system world, Shore draws object naming services, support for lower (and cheaper) degrees of transaction-related services, and an object access mechanism for use by legacy Unix file-based tools. From the OODB world, Shore draws data modeling features and support for associative access and performance acceleration features. To provide scalability and a basis for parallelizing the system, Shore also employs a novel architecture, including support for symmetric peer-to-peer server communication and caching; in addition, it includes support for extensibility via the value-added server facility. Like our previous system, EXODUS, we will make the Shore system publicly available via anonymous FTP; we expect the first release of Shore to occur in mid-1994.